Multivariate Adaptive Regression Splines

---

이번 포스팅에서는 Friedman의 명작 Multivariate Adaptive Regression Splines(MARS)를 읽고 정리해본다.

 

- 목차 -

1. Introduction

2. Existing Methodology

3. Adaptive Regression Splines

4. Simulation Studies and Examples

5. Remarks

6. Conclusion

 

---

   1. Introduction

관측 데이터 $(x_i, y_i), i=1, \ldots, n$가 있다고 해보자. 이때 $x_i=(x_{i1}, \ldots, x_{ip})$이다.

이때 반응 변수와 설명 변수 간에 다음과 같은 관계가 있다고 가정해보자.

$$y =  f(x_1, \ldots, x_p)+\epsilon\tag{1}$$

회귀 분석의 목적은 $f$를 잘 근사하도록 관측 데이터를 잘 사용하는 것이다.

 

잘 근사하는지 판단하는 척도는 다음과 같이 적분 오차

$$I = \int_Dw(x)\Delta[\hat{f}(x), f(x)]dx\tag{2}$$

또는 평균 오차

$$E=\frac{1}{n}\sum_{i=1}^nw(x_i)\Delta[\hat{f}(x_i), f(x_i)]\tag{3}$$

가 있다. 

 

회귀 분석에서 예측만을 목적으로 한다면 (2), (3)을 최적화하는 것만 신경 쓰면 된다. 하지만 모형의 해석과 때때로 계산 속도도 중요한 관심이 될 수 있다.

 

이 논문에서는 앞에서 소개한 여러 목적을 달성하는 새롭고 유연한 비모수적 회귀 모델링 방법을 제안한다.

---

   2. Existing Methodology

여기서는 다변량 회귀 모델링에 대한 기존 방법론을 소개한다. 이때 각 방법의 어려운 점을 알아보고 이 논문에서 이를 어떻게 해결하는지 뒤에서 소개한다고 한다.

 

2.1 Global Parametric Modeling

최소 제곱법을 이용한 모수적 추정법(예: 선형 회귀 모형)은 실제 모형이 가정한 모수적 모형과 매우 다를 경우 그 정확성에 문제가 생길 수 있다.

 

2.2 Nonparametric Modeling

Global Parametric Modeling은 piecewise, local parametric 적합, 거칠기 벌점화(roughness penalty)를 통하여 일반화되었다.

 

piecewise  parametric fitting은 전체 도메인을 서브 도메인으로 나누고 이러한 서브 도메인 위에서 parametric 한 모형을 적합하는 것이다. 하지만 이러한 방법은 설명 변수 벡터의 차원이 커지면 소위 차원의 저주로 인해 적합이 힘들어진다. 

 

그다음으로 생각해 볼 수 있는 것이 설명 변수 포인트 주변에서의 로컬 적합을 생각해 볼 수 있을 것이다. 로컬 적합이라는 것도 가중 최소 제곱법을 사용하는데 이때 가중치 함수를 어떻게 설정하는지가 어려운 문제이다.

 

거칠기 벌점화 근사 방법은 다음을 만족하는 $x$의 함수 $g$를 찾는 것이다.

$$\sum_{i=1}^n(y_i-g(x_i))^2+\lambda R(g)$$

이때 $R(g)$는 거칠기 정도를 나타내는 함수로써 다음과 같이 정의된 것이 많이 연구되었다.

$$R(g) = \sum_{k=1}^p\sum_{j=1}^p\int\left | \frac{\partial^2g}{\partial x_k \partial x_j}\right |^2 dx$$

거칠기 벌점화 근사 방법은 고차원에서의 적용이 제한되어 있다고 한다.

 

2.3 Low Dimensional Expansions

$f$가 실제 $x$의 함수이고 이를 근사한다고 했을 때 $x=(x_1, \ldots, x_p)$에 대한 함수로 근사하는 것이 아닌 이들의 부분집합 $z \subset \{x_1, \ldots, x_p \}$의 함수 $g$로 근사하는 것을 생각해볼 수 있다.

$$\hat{f} = \sum_{j=1}^Jg(z_j)$$

 

하지만 이러한 접근 방법도 모든 부분 집합을 고려할 수 없다는 현실적인 문제가 있고 최적 부분 변수 집합은 실제 함수 $f$에 의존하는데 $f$ 알지 못하여 최적 집합을 제대로 예측할 수 없다는 제약이 있다. 그리고 개별 함수 $g$의 Smoothness를 조절하는 파라미터가 들어간다면 전체적으로 추정하거나 사전에 정해줘야 할 파라미터가 너무 많아진다는 문제도 있다. 

 

2.4 Adaptive Computation

Adaptive한 계산에 기반한 함수 근사 방법을 소개한다.

2.4.1 Projection Pursuit Regression

Projection Pursuit 방법은 다음과 같이 기존 설명 변수의 선형 결합의 함수의 가산(Additive) 형태의 함수 클래스를 고려한다.

$$\hat{x} = \sum_{m=1}^Mf_m \left ( \sum_{j=1}^p\alpha_{jm}x_j \right ) \tag{14}$$

 

그 어떤 매끄러운 $p$개 변수를 갖는 함수는 (14)의 형태로 근사가 충분히 가능하다고 알려져 있다. 하지만 $M$이 커질수록 근사를 잘하기 위해 시간이 많이 걸리며 때로는 간단한 함수임에도 큰 $M$으로 근사해야 할 때도 있다고 한다.

2.4.2 Recursive Partitioning Regression

결국 의사결정나무를 말하는 것이다. 하지만 더 일반화된 개념으로써 의사결정나무는 보통 각 터미널 노드에서 상수로 예측을 하지만 선형 모형도 고려할 수도 있다. 비록 터미널 노드에서의 선형 모형은 잘 안 쓴다고 한다. 

 

하지만 이렇게 해서 얻어진 모형은 터미널 노드의 바운더리에서 불연속이라는 단점이 있다. 특히 실제 함수가 연속이라면 이는 더 큰 문제가 된다. 또한 단순한 선형 모형과 복잡한 교호항이 있는 모형을 잘 식별해내지 못한다고 알려져 있다.

---

   3. Adaptive Regression Splines

이번 섹션에서는 앞서 소개한 기존 방법론들의 단점을 극복하는 Multivariate Adaptive Regression Splines(MARS)를 소개한다. 

 

3.1 Recursive Partitioning Regression Revisited

RPR(Recursive Partitioning Regression)은 다음과 같이 기저 함수의 선형 결합으로 볼 수 있다.

$$\hat{x} = \sum_{m=1}^Ma_mB_m(x)$$

여기서 기저 함수 $B_m(x) = I(x\in R_m)$이다.

 

RPR은 데이터를 이용하여 계수 $a_m$의 최적값을 찾는 것뿐만 아니라 최적 기저 함수 집합 $B_m(x)$도 찾게 된다. 논문의 저자는 다음의 알고리즘을 제안하였다.

 

 

RPR은 Forward Stepwise Regression 과정과 동일하게 표현할 수 있다. 물론 Backward Stepwise Regression도 고려할 수 있다. 하지만 Backward Step(특정 기저 함수 제거 스텝)이 들어가면 일부 공간에 구멍이 생겨서 설명 변수가 해당 공간에 있으면 무조건 0으로 예측하게 되는 참사가 빚어질 수 있다.

 

3.2 Continuity

RPR은 Piecewise Constant 모형으로 이에 대한 단점은 연속성이 부족하다는 점이다. 연속성이 부족하면 불연속 지점에서의 근사가 잘 안 되기 때문에 문제가 된다. 이때 앞에서 소개한 알고리즘 1을 수정하면 연속성뿐만 아니라 연속 미분을 갖는 모형을 만들어 낼 수 있다. 수정해야 할 부분은 기저 함수를 스텝 함수를 사용하는 대신 연속함수를 사용하는 것이다.

 

스텝 함수를 일반화한 Spline 기저 함수로써 한쪽 방향 절단 Power 기저 함수를 고려한다.

$$b_q(x-t) = (x-t)^q_+$$

물론 양방 절단 Power 기저 함수도 고려할 수 있다.

$$b_q^{\pm}(x-t) = [\pm (x-t)]^q_+$$

알고리즘 1에서의 스텝 함수는 $q=0$인 경우로 볼 수 있다.

 

알고리즘 1을 통하여 얻은 기저 함수는 텐서곱으로 표현되는데 중요한 것은 각 곱마다 다른 변수들이 포함된다는 것이다. 때로는 각 곱마다 똑같은 변수와 분리 기준이 있을 수도 있는데도 말이다.

 

3.3 A Further Generalization

RPR의 또 다른 단점은 꽤나 단순한 함수 클래스인 강한 교호항이 없거나 있더라도 일부 변수에 대한 교호 작용이 있는 가산 모형에 대하여 근사를 잘하지 못한다는 점이다.

 

하지만 기저 함수를 이용하면 이러한 단점도 극복 가능하다는 것이다. 알고리즘 1에서 상수 기저 함수를 부모 노드로 선택하면 순수한 가산 모형을 만들어 낼 수 있고 교호항을 갖는 모형은 하나의 변수만을 갖는 기저 함수를 부모 노드로 선택하면 근사를 잘할 수 있다는 것이다.

 

부모 노드를 제외하지 않음으로써 앞서 소개한 동일 변수의 여러 분리가 가능하다는 것이다.

 

이때 절단 기저 함수에서 $q$를 어떤 것을 선택하느냐에 대한 문제가 남았는데 통계적으로 트레이드 오프가 있다고 한다.

 

3.4 MARS Algorithms

여기서는 MARS 알고리즘을 소개한다. 먼저 MARS의 Foward Stepwise 부분(알고리즘 2)는 다음과 같다.

알고리즘 1과의 차이는 스텝 함수 대신 절단 Spline 기저 함수를 넣었다는 것이다. 하지만 알고리즘 2를 통하여 얻은 기저 함수의 영역이 배타적이지 않고 겹친 부분이 있다. 따라서 이를 위해 Backward Stepwise 단계(알고리즘 3)를 다음과 같이 도입한다.

 

3.5 ANOVA Decomposition

알고리즘 2, 3을 통해 얻는 모형을 잘 정리하면 다음과 같다고 한다.

$$\hat{f}(x) = a_0 + \sum_{K_m=1}f_i(x_i) + \sum_{K_m=2}f_{i,j}(x_i, x_j) + \sum_{K_m=3}f_{i, j, k}(x_i, x_j, x_k)\tag{24}$$

 

즉, MARS는 주 효과뿐만 아니라 2개 이상 변수의 교호까지 모델링할 수 있다는 것을 의미한다.

 

3.6 Model Selection

MARS 알고리즘에는 적합도를 측정하는 측도와 기저 함수의 최대 개수를 선택해야 하는 문제가 있다. 이때 적합도 측도는 제곱 손실을 고려한다. 왜냐하면 계산과 관련하여 매력적인 성질을 갖고 있기 때문이다. 

 

그리고 기저 함수 개수는 교차 검증을 이용하여 구하게 된다.

 

MARS는 기본적으로 주어진 데이터에서 반응 변수의 관계를 중점적으로 활용하므로 편의는 작지만 분산이 크다는 단점이 있다. 따라서 적합도를 측도를 제곱 손실에서 기저 함수가 많을수록 페널티를 주는 측도를 고려하기도 한다.

 

3.7 Degree-of-Continuity

절단 Spline 기저 함수의 파라미터 $q$가 연속의 정도를 결정한다. 만약 근사의 정확성 자체만이 중요하다면 연속의 정도를 결정함으로써 얻는 이득은 많이 없을 것이다. 만약 이차 미분이 어느 영역에서도 크지 않다면 연속적인 1차 미분성으로 연속성 정도에 제한을 주면 약간의 정확도 향상이 있을 수 있다고 한다. 하지만 그 이상으로 연속성의 정도에 제약을 가하면 얻는 것보다 잃는 게 많다고 한다.

 

또한 설명 변수 영역의 바운더리에서 정확도가 현저히 낮아지는 경향이 있다. 이때 바운더리에서 기저 함수를 1차 함수 즉, 직선으로 설정하여 바운더리 효과를 보정한다고 한다.

 

기존 절단 Spline 기저 함수에서 중간 영역에 절단 큐빅 함수를 도입함으로써 $q=1$인 경우와 비슷하면서도 연속 미분을 갖는 근사 함수를 생성하는 전략을 제시하였다.

 

3.8 Knot Optimization

Knot 사이에 들어갈 최소 관측치 수를 정하는 것 같은데 사실 뭔 말인지 잘 모르겠다 ㅠㅠ

 

3.9 Computational Considerations

MARS 알고리즘의 계산 효율을 높이기 위하여 QR 분해, Cholesky 분해 방법을 적용하는 것을 제안한다.

---

   4. Simulation Studies and Examples

MARS를 이용한 모의실험과 실제 데이터의 적용을 통하여 기존 방법보다 무엇이 나아졌는지 이해하고자 한다.

 

4.1 Modeling Pure Noise

노이즈 밖에 없는 데이터는 사실 제대로 적합하면 안 될 것이다. 안 그러면 노이즈가 마치 어떤 구조적인 모형이 있는 것 같은 착각을 불러일으키니까 말이다. 그래서 MARS가 이런 노이즈 밖에 없는 데이터 구조에 대해서 이게 진짜 노이즈라고 모델링하는지 보고자 한다.

 

실제로  MARS로 적합된 것과 평균으로 모델링한 것과 비교했을 때 MARS가 평균 모델보다 더 좋지 않은 것으로 나타났고 이는 MARS가 순수한 노이즈에 대하여 적절하게 적합하고 있음을 암시한다고 볼 수 있다. 

 

4.2 MARS Modeling on Additive Data

실제 모형이 교호항이 없는 가산 모형인 경우에 교호항이 있는 MARS와 없는 MARS 중에서 교호항이 없는 MARS의 적합도가 나쁘지 않다는 것을 보여주는 것 같다.

 

4.3 A Simple Function of Ten Variables

샘플은 상대적으로 작고 변수 차원은 상대적으로 높은 상황에서 실제 모형의 복잡한 교호항을 잘 잡아내는지 확인하는 실험을 했고 MARS가 잘 모델링했다는 내용인 것 같다.

dd

 

4.4 Alternating Current Series Circuit

도대체 MARS의 능력이 어디까지인지 확인하고 싶었던 실험이라고 한다. 이를 통해 변수간 관계에 대해서 인사이트를 얻고 싶었다고 한다.

 

4.5 Portuguese Olive Oil

MARS를 로지스틱 회귀에 적용한 것이다. 

 

4.6 Low Dimensional Modeling

MARS는 확실히 고차원 데이터에 대해서 잘 작동하지만 저차원($p\leq 2$)인 상황에서도 기존 방법들과 비교하여 경쟁력이 있다는 것을 실제 데이터와 인공 데이터를 통하여 증명했다.

 

4.7 Slicing a MARS Model

2개 보다 더 많은 변수의 교호 작용을 해석 가능하도록 시각화하기 위한 방법을 소개한다. 

---

   5. Remarks

여기에서는 확장할 문제와 한계점에 대해서 소개한다.

5.1 Constraints

주어진 데이터 외에 새로운 데이터에 대해서 제약을 가하면 편의는 조금 증가할 수 있지만 분산을 많이 줄일 수 있다고 한다. 그 제약 중 하나가 교호항의 차수를 기껏해야 2로 하는 것이다. 사전에 특정 변수가 그 어떤 다른 변수와 교호 작용이 없을 것이라는 사전 지식이 있다면 이러한 변수를 주효과로만 넣는다면 정확도가 향상될 수 있다.

 

5.2 Semiparametric Modeling

사전에 설명 변수와 반응 변수간 의존성을 알 수 있다면 해당 의존성을 Parametric하게 설정하고 나머지 부분을 MARS로 추정할 수도 있다는 것이다.

 

5.3 Colinearity

MARS에서는 다중 공선성이 큰 문제가 된다고 한다. 반응 변수와 상관성이 강한 설명 변수 하나를 단독으로 분리하기 어려울 뿐만 아니라 주 효과와 교호항 또한 다중 공선성 관계에 있는 변수들로부터 분리하는 게 어렵다.

 

이를 해결하기 위해 교호항의 차수를 늘리는 방법이 있다. 또 다른 방법으로 모형에 들어가는 변수의 수를 적게 하는 방법도 있다. 이렇게 하면 이상한 교호 작용을 나타내는 모형을 피할 수 있다고 한다.

 

5.4 Robustness

MARS는 반응 변수 이상치에 민감하다. 왜냐하면 제곱 손실 함수를 쓰기 때문인데 이건 필수가 아니라고 한다. 따라서 이상치에 민감하지 않은 손실 함수를 고려하면 이상치 문제를 어느 정도 커버할 수 있다. 또한 EDA를 통해 이상치가 발견되었으면 MARS를 적용하기 전에 제거하는 것을 고려해보라고 한다. 

 

MARS는 설명 변수 이상치에는 일반적으로 덜 민감하나 바운더리 효과에는 강력한 영향을 미친다고 한다. 

---

   6. Conclusion

MARS은 RPR과 Spline의 장점을 최대한 유지하면서 단점을 약화함으로써 그 가치가 있다. MARS는 RPR과는 달리 연속형 모형을 생성하고 교호 작용을 더 잘 해석할 수 있는 모형도 생성할 수 있다. 또한 기존 RPR 보다 더 데이터 구조를 잘 파악하는 모형도 생성할 수 있다.

---