ESL: Ch 5. Basis Expansions and Regularization
Contents
5.1 Introduction
5.2 Piecewise Polynomials and Splines
5.3 Filtering and Feature Extraction
5.4 Smoothing Splines
5.5 Automatic Selection of the Smoothing Parameters
5.6 Nonparametric Logistic Regression
5.7 Multidimensional Splines
5.8 Regularization and Reproducing Kernel Hilbert Spaces
5.9 Wavelet Smoothing
5.1 Introduction
기본적인 통계 모형에서는 input feature들 사이의 선형성(linearity)을 가정하는 경우가 많다. 실제 예측변수와 목적변수 사이의 true relationship은 linear하지 않겠지만, 이를 linear한 모형으로 근사한 것이다.
- 예를 들면, 선형회귀분석은 true function f(X)를 “예측변수 X에 대한 목적변수 Y의 조건부 평균”으로 다음과 같이 설정한다.
- 예측변수와 목적변수 사이의 true relationship f(X)는 X에 대해 linear, additive하다는 보장이 없다.
- 다만, 분석 결과의 해석이 더 용이하다는 점, 그리고 β0+β1X1+…+βpXp는 f(X)의 1차 Taylor approximation이라는 점 등의 이유 때문에, X의 선형성을 가정하는 경우가 많다.
What is “basis” and “basis expansion”?
어떤 부분집합 B={b1,b2,…,bn}⊂V의 원소들의 선형결합으로 B가 속한 벡터공간 V의 모든 원소들을 나타낼 수 있다면, 우리는 B가 V를 span한다고 나타내거나, 혹은 B를 V의 spanning set이라고 부른다. 한 벡터공간을 span하는 집합은 무수히 많을 수 있다. 그 중에서도 Basis는 선형독립이면서 어떤 벡터공간을 span하는 set, 즉 어떤 벡터 공간의 minimal spanning set을 말한다.
예를 들면, a⋅1+b⋅x+c⋅x2+d⋅x3의 꼴로 3차 이하의 다항식을 모두 나타낼 수 있고, {1,x,x2,x3}는 서로 선형독립이기 때문에, {1,x,x2,x3}는 3차 이하의 모든 다항식들의 집합 P3의 basis가 될 수 있다. 위의 linear model의 예의 경우 true function f(X)를 나타내는 basis는 각 input feature {1,X1,X2,…,Xp}가 된다.
따라서 이 챕터에서 다루는 basis expansion의 의미는 더이상 input feature X1,X2,…,Xp를 그대로 basis로 쓰지 않고, X의 transformation인 새로운 변수들을 모형의 basis로 사용하는 것을 말한다. 이를 linear basis expansion이라고 부르고, 다음과 같이 나타낸다.
hm:Rp→R,m=1,2,...,M f(X)=M∑m=1βmhm(X)=β1h1(X)+β2h2(X)+...+βMhM(X)이제 true function f(X)는 input feature X에 대해서는 nonlinear일 수 있지만, 새로운 feature들 h1(X),..,hM(X)에 대해서는 linear, additive한 model이다.
회귀분석에서 특정 예측변수를 log transformation하거나, 이차항 및 interaction 항을 추가하는 작업은 이와 같은 linear basis expansion의 한 예이다. 그 외에도 hm(X)를 어떻게 설정하는지에 따라 다양한 모형이 있는데 이는 아래에서 다루도록 하겠다.
또한, basis function hm(X)를 적절하게 설정하는 것도 중요하지만, 모형의 복잡도를 조절하는 방법 역시 요구된다. 이에는 크게 다음과 같은 세 가지 방법이 있다.
- Restriction method : basis function hm의 class를 사전에 결정하는 방법.
- Selection method : 모형의 fit에 유의미한 기여를 하는 basis function만 모형에 포함시키는 방법. ex) CART, MARS
- Regularization method : 가능한 basis function hm(X)를 모두 모형에 포함시키지만, 그 계수 βm(X)에 제약을 거는 방법. ex) ridge regression
- lasso regression은 selection method와 regularization method를 동시에 사용하는 모형이다.
5.2 Piecewise Polynomials and Splines
우선 Section 5.7까지는 X가 1개의 예측변수를 갖는 것으로 가정한다.
Piecewise polynomial function
Piecewise polynomial 함수, f(X)는 X의 정의역을 (겹치지 않고 서로 인접하는) 구간들로 잘라, 각 구간들 내에서 polynomial로 나타낼 수 있는 함수를 말한다. 아래의 그림과 같은 piecewise polynomial은 다음과 같은 basis로 나타낼 수 있다. 이 때, f(X)는 6개의 basis function으로 나타내어지므로 자유도(degrees of freedom)는 6이다.
f(X)=θ1h1(X)+θ2h2(X)+...+θ6h6(X)
위와 같은 piecewise linear polynomial f(X)에 정의역 전체에서 연속이 될 조건을 추가하면 어떻게 될까? (책에서는 표현 상 이 부분에서 linear라는 표현을 affine과 구분하여 사용하지 않았다.) 추가되는 연속성 조건은 다음과 같다.
f(ξ−1)=f(ξ+1)⇒θ1+θ2ξ1=θ3+θ4ξ1 f(ξ−2)=f(ξ+2)⇒θ3+θ4ξ2=θ5+θ6ξ2piecewise linear polynomial f(X)에 연속의 조건인 두 개의 제약식이 추가되면, 6−2=4개의 basis function으로 f(X)를 나타낼 수 있게 된다. 그 basis는 다음과 같다.
f(X)=θ1h1(X)+θ2h2(X)+θ3h3(X)+θ4h4(X)
- h3(X)=(X−ξ1)+=max{0,X−ξ1}는 다음 그림과 같은 함수를 의미한다.
이외에도 각 구간마다 일차함수가 아닌 M차 이하의 polynomial을, 그리고 연속 뿐만 아니라 Ck class 조건 (k계 도함수까지 연속)도 부여할 수 있다. 예를 들면, 세 개의 knot (ξ1,ξ2,ξ3)으로 나뉜 각 구간마다, 3차 polynomial을 이용하여, 2계 도함수까지 연속인 f(X)의 basis를 생각해보자. 먼저, 세 개의 knot은 정의역을 네 개의 구간으로 나누며 각 구간마다 4개, 16개의 basis function이 필요하다. (4×4=16) 여기에 각 knot마다 연속, 1계도함수 연속, 2계도함수 연속과 같이 세 개의 제약식이 필요하므로, 9개의 basis function이 사라진다. (3×3=9) 따라서, f(X)는 총 16−9=7개의 basis function으로 나타낼 수 있을 것이다.
Regression spline
A “spline” is a thin strip of wood that can be easily bent to follow a curved line. Historically, it was used in drafting for drawing smooth curves. Regression splines, a statistical translation of this idea, are a way to represent nonlinear, but unknown, mean functions.
위의 사진과 같이, spline은 부드러운 곡선을 그리기 위해 사용된 얇고 긴 나무조각을 가리키는 말이다. 부드러운 곡선을 그리는 spline wood와 같이, 통계학에서 spline은 nonlinear한 (unknown) mean function을 그리는 방법을 의미하며, 크게 regression spline과 smoothing spline으로 나눌 수 있다. 이 절에서는 knot의 개수, 위치, 차수를 사전적으로 결정한 후 mean function을 그리는 regression spline을 다룬다.
order-M spline은 M−1차 polynomial들로 이루어진 CM−2 class의 piecewise polynomial function로 정의된다. 즉, M−2번 미분한 도함수까지 연속인 M−1차 이하의 piecewise polynomial을 (order-M) spline이라고 부른다. 만약 M−1차 piecewise polynomial이 (M−2번이 아닌) M−1번 미분한 도함수까지 연속이라면, 이는 더이상 piecewise polynomial이 아니라 global M−1차 polynomial이 될 것이다. 가장 많이 쓰이는 Cubic spline은 order-4 spline이다. K개의 knot를 갖는 order-M spline의 basis는 다음과 같이 나타낼 수 있다.
hj(X)=Xj−1,j=1,...,M,hM+l(X)=(X−ξl)M−1+,l=1,...,K f(X)=θ1h1(X)+θ2h2(X)+...+θM+KhM+K(X)다음 그림의 초록색 선은 두 개의 knot를 갖는 Cubic spline, 즉 order-4 spline을 나타낸 것이다. 구간과 구간 사이의 경계에서 연속이며 부드럽게 연결되는 것을 확인할 수 있다.
Natural cubic spline
데이터를 piecewise polynomial로 fit하는 경우, 양 끝 값에서는 연속성 제약이 없고 그 주변에는 data도 적을 것이기 때문에, 정의역의 양 끝 값 주변에서 fitted value가 불안정해질 가능성이 있다. 여기서 불안정하다는 것은 데이터가 어떻게 뽑히는가에 따라서 fitted value가 크게 달라지게 되는 것을 의미한다. 우리가 관측한 observation은 데이터의 한 random realization일 것이다. 그런데 이 randomness에 따라 fitted value(여기서는 spline curve)가 그때그때 크게 달라진다면, 이는 큰 문제가 된다. 이를 모형의 variance가 크다고 하는데, Natural cubic spline은 이를 해결하고자 한 모형이다.
Natural cubic spline은 좌우의 양 끝 boundary knot(ξ1과 ξK) 밖에서는 linear(일차함수 꼴)이고 그 이외의 구간에서는 3차 polynomial로 나타내어지는 spline을 말한다. 다시 말해서, Natural cubic spline은 “좌우 양 끝 구간에서, 차수가 2차 이상인 항의 계수=0”의 제약이 추가된 cubic spline이다. K개의 knot을 갖는 cubic spline이 K+4의 자유도를 갖는 것에 반해(M=4), K개의 knot을 갖는 Natural cubic spline은 (K+4)−4=K개의 자유도를 갖는다. 양 끝 구간에서 각각 2 개씩, 총 4 개의 자유도를 아낄 수 있기 때문이다. 같은 차수의 cubic spline과 비교했을 때, Natural cubic spline은 다음과 같은 이점이 있다.
- 같은 자유도를 갖는 cubic spline에 비해, interior region에서 4개의 knot을 더 가져갈 수 있다는 뜻이 된다.
- Boundary 근처에서 fitting model의 bias가 약간 올라가는 대신, model의 variance를 낮출 수 있다.
- 어떤 데이터가 관측되더라도, spline curve가 크게 달라지지 않는다.
- Boundary knot 밖 구간에서는 어차피 많은 정보가 없으므로, linear 가정을 하는 것이 큰 문제가 없다.
Example: South African heart disease
5.3 Filtering and Feature Extraction
5.4 Smoothing Splines
Regression spline을 그릴 때는 knot의 개수 및 위치를 임의로, 혹은 fit에 대한 어떤 measure를 통해 사전에 결정하여야 했다. 이 절에서는 사전에 knot의 개수 및 위치를 결정할 필요가 없는 smoothing spline에 대해 알아보고자 한다. 이 방법의 특징은 penalty항을 통해 각 knot들이 fitted value에 영향을 주는 정도에 제약을 걸어 overfitting을 방지한다는 것이다. 몇몇 knot으로부터의 영향은 penalty항에 의해 완전히 사라질 수도 있다. 이처럼 penalty를 준다는 점에서 ridge regression과 lasso와 닮아있지만, smoothing spline은 새로운 종류의 penalty를 적용함으로써 X와 Y 사이의 nonlinear 관계를 허용한다.
(x1,y1),(x2,y2),…,(xN,yN)과 같은 N개의 observed data가 있을 때, 다음과 같은 식을 최소화하는 함수 f를 생각해보자.
RSS(f,λ)=N∑i=1{yi−f(xi)}2+λ∫{f″(t)}2dt- 첫 번째 항은 fit이 observed data와 얼마나 가까운지를 측정하는 기준이 된다.
- 두 번째 항은 함수 f의 curvature, 즉 f의 굴곡진 정도를 제한하고 spline을 smoothing하는 기준이 된다.
- f의 이계도함수, f″의 L2-norm의 제곱으로 이해할 수도 있다.
- f(x)=a+bx와 같이 f의 curvature가 전혀 없을 때, 즉 이계도함수 f″이 y=0일 때, 아래와 같이 두번째 항은 0이 된다.
- λ는 위 식 전체를 최소화함에 있어, 두 기준들 간의 비중을 정해주는 smoothing parameter이다.
- λ=0일 때, f는 전혀 smoothing되지 않고 모든 observed points (x1,y1),…,(xN,yN)를 지나가는 곡선이 될 것.
- λ=∞일 때, f는 이계도함수가 0이 되어야하므로 least square로 직선(일차함수)을 fit한 결과가 나올 것.
따라서, 주어진 λ에 대해서, 위 식을 최소화하는 함수 ˆf는 observed data와의 fit도 좋으면서, curvature도 크지 않은 smoothing spline이 될 것이다.
x에 대해 선형이라는 가정 없이, f는 ∫f″(t)2dt (두번째 항)의 값이 정의되는 이 세상 모든 함수가 위 최소화문제의 해가 될 수 있다. 그렇다면 어떻게 위 최소화문제의 해 ˆf를 찾을 것인가? 그런데 놀랍게도, 위 최소화문제는 x1,x2,…,xN에서 knot을 갖는 natural cubic spline을 유일한 해로 갖는다는 것이 밝혀져 있다. (증명은 이 포스트에 정리해 두었다.) 따라서 이 사실을 이용하여, f를 x1,x2,…,xN에서 knot을 갖는 natural cubic spline으로 둔다면, 함수 f는 N개의 basis function을 갖는 다음과 같은 natural cubic spline이 된다.
f(x)=N∑i=1Nj(x)θj where N1(x),...,NN(x): basis functions/ˆθ1,...,ˆθN: coefficients이 때, smoothing spline의 최소화문제는 아래와 같이 나타낼 수 있다.
RSS(θ,λ)=(y−Nθ)T(y−Nθ)+λθTΩNθ wherey=[y1y2⋮yN],θ=[θ1θ2⋮θN] N=[N1(x1)N2(x1)⋯NN(x1)N1(x2)N2(x2)⋯NN(x2)⋮⋮⋱⋮N1(xN)N2(xN)⋯NN(xN)],ΩN=[⋱⋮⋯∫N″j(t)N″k(t)dt⋯⋮⋱]위 식을 최소화하는 Natural cubic spline을 찾기 위해서는 위 RSS식을 θ에 대해 최소화하면 된다. θ의 해를 찾기 위해 일계조건을 풀면 다음과 같다.
∂RSS∂θ=∂∂θ(yTy−yTNθ−θTNTy+θTNTNθ+λθTΩNθ) =−2NTy+2NTNθ+2λΩNθ=0 ˆθ=(NTN+λΩN)−1NTy따라서 도출한 smoothing spline은 아래와 같은 형태의 Natural cubic spline이다.
ˆf(x)=N∑i=1Nj(x)ˆθj where N1(x),...,NN(x): basis functions/ˆθ1,...,ˆθN: coefficientsN개의 observation에 대한 smoothing spline의 fitted value를 벡터를 이용하여 나타내면 다음과 같다. ˆy, 는 아래와 같이 y에 Sλ=N(NTN+λΩN)−1NT를 곱한형태인데, 이 때, smoothing spline의 fitted value를 구하기 위해 반응변수 벡터 y에 곱해주는 행렬 Sλ를 Smoother matrix라고 부른다.
ˆy=Nˆθ=N(NTN+λΩN)−1NTy=Sλy그리고 Smoother matrix, Sλ, 는 N개 observation의 input 변수들 x1,x2,…,xN과 λ의 값에 의해 결정된다는 것을 알 수 있다.
Smoother Matrix & Degrees of Freedom
λ는 위와 같이 Smoothing spline을 구하는 과정에서, curvature 제약의 강도를 결정하는 최소화문제의 tuning parameter이다. 지금까지는 λ가 smoothing spline을 구하기 앞서, 사전에 주어진 상수라고 놓고 논의를 전개했다. 먼저 Smoother matrix와 degrees of freedom에 대한 몇 가지 성질을 알아보고, 그에 따라 λ를 사전에 결정하는 방법에 대해 알아보고자 한다.
λ가 사전에 결정되어 있다면, y에 Sλ라는 행렬을 곱함으로써 얻은 Smoothing spline, ˆy은 y에 대해 linear한 smoother이다. (Matrix multiplication은 linear transformation이기 때문.) 이와 같은 linear smoother의 다른 예는 선형회귀분석의 Hat matrix, H가 있다. Hat matrix는 다음과 같이 회귀모형의 fitted value를 구해주는 linear operator이다.
H=X(XTX)−1XT,ˆyreg=X(XTX)−1XTy=Hy회귀분석의 Hat matrix와의 비교를 통해, Smoother matrix Sλ의 성질에 대해 몇 가지 알아보자.
- H와 Sλ는 대칭행렬, positive semidefinite행렬이라는 특징이 있다.
- H는 H2=HH=H, 즉 idempotent한 특징이 있다. Sλ는 Sλ2=SλSλ⪯Sλ인 성질이 있다. 이는 Sλ가 SλSλ보다 어떤 positive semidefinite행렬만큼 더 크다는 것을 의미한다. 이는 smoother matrix가 curvature 제약에 의해 shrinking(수축하는, 쪼그라드는) 된 것 때문인데, 이에 대해서는 뒤에 그 의미와 이유를 더 설명하겠다.
- rank란 어떤 linear operator의 column space의 차원, 다시 말해서 linear operator의 결과로 이루어진 공간(치역:range)의 차원을 의미한다. 회귀모형이 p개의 항을 가질 때 X는 p개의 열로 이루어진 행렬이 되며, H는 p의 rank를 갖는다. Sλ는 N의 rank를 갖는다.
여기서 눈여겨볼 부분이 있다. 회귀분석의 경우 N개의 자료가 있고 p개의 변수로 이를 설명하고자 할 때, fitted value는 p개의 설명변수 X1,X2,…,Xp 가 이루는 공간, 즉 p차원 공간 위에 놓이게 된다. 그렇기 때문에 반응변수 벡터 y를 fitted value인 ˆy로 변환하는 linear operator, H의 rank가 p인 것이다.
Smoothing spline의 최소화문제는 x1,x2,…,xN에서 knot을 갖는 natural cubic spline을 그 해로 갖는다. 5.3에 서술된 대로 N개의 knot를 가지는 natural cubic spline은 N개의 basis로 표현할 수 있으며, 다시 말해서 N을 자유도를 갖는다. 자유도가 N이라는 것은 모형 내 추정해야 할 parameter(ˆθ1,…,ˆθN) 가 N개임을 의미한다.
ˆf(x)=N∑i=1Nj(x)ˆθj그런데 smoothing spline이 N의 rank를 갖는다면, (N개의 자료를 통해 얻은 fitted curve가 N개의 basis로 나타내어진다면,) smoothing spline은 아래와 같이 그저 N개의 점을 잇는 의미없는 선일 뿐일까?
그렇지 않다. Smoothing spline을 처음 소개할 때, 아래와 같이 서술하였다.
이 절에서는 사전에 knot의 개수 및 위치를 결정할 필요가 없는 smoothing spline에 대해 알아보고자 한다. 이 방법의 특징은 penalty항을 통해 각 knot들이 fitted value에 영향을 주는 정도에 제약을 걸어 overfitting을 방지한다는 것이다. 몇몇 knot으로부터의 영향은 penalty항에 의해 완전히 사라질 수도 있다.
(중략)
그런데 놀랍게도, 위 최소화문제는 x1,x2,…,xN에서 knot을 갖는 natural cubic spline을 유일한 해로 갖는다는 것이 밝혀져 있다 (증명 Reinsch (1967)). 따라서, f를x1,x2,…,xN에서 knot을 갖는 natural cubic spline으로 둔다면, 함수 f는 N개의 basis function을 갖는 다음과 같은 natural cubic spline이 된다.
smoothing spline은 N개의 basis의 합으로 나타내어지고 N개의 계수를 갖는다. 하지만, curvature 제약 하의 최소화의 해로 도출하였기 때문에, smoothing spline은 더 적은 수의 자유도로 나타내어질 수 있다. 그럼 smoothing spline의 “실제” 자유도(Effective degrees of freedom)는 어떻게 구할까? 우리는 회귀분석의 Hat matrix와의 비교를 통해 그 아이디어를 얻을 수 있다. 회귀분석의 smoother matrix, H의 자유도는 다음과 같이 나타낼 수 있다.
trace(H)=trace(X(XTX)−1XT)=trace(XTX(XTX)−1)=trace(Ip)=p rank(H)=p=trace(H)따라서 우리는 Sλ의 “실제” 자유도(Effective degrees of freedom)를 다음과 같이 정의한다.
dfλ=trace(Sλ)=trace(N(NTN+λΩN)−1NT)이와 같이 Sλ의 자유도를 정의하는 것은 특정 자유도 값의 smoothing spline을 도출하고자 할 때 유용하다. 예를 들어, 자유도가 12인 smoothing spline을 구하고 싶다면, 간단하게 trace(Sλ)=12를 만족하는 λ의 값을 numerical한 방법으로 구하면 된다. 자유도의 개념은 회귀분석 등 다른 smoothing 모형들에도 적용되는 개념이기 때문에, 그와 일관적인 방법으로 smoothing spline을 parameterize하는 데 유용하다.
Shrinking Nature of Smoother Matrix Sλ
왜 smoothing spline의 smoother matrix, Sλ가 수축하는(shrinking) smoother로 불리는 것일까? 그 이유를 간단히 확인해 보자.
Sλ의 고유값을 ρ1(λ),ρ2(λ),…,ρN(λ)이라고 하자. (λ가 변하면 Sλ도 변하고 그에 따라 Sλ의 고유값도 변하므로, λ에 대한 함수로 나타내었다.) Sλ는 symmetric, positive semidefinite한 행렬이므로, 0 이상의 실수 고유값(eigenvalue)으로 다음과 같이 eigen-decomposition할 수 있다 (Wikipedia).
Sλ=N(NTN+λΩN)−1NT를 Reinsch form으로 나타내면 다음과 같다.
N(NTN+λΩN)−1NT=NN−1(I+λ(NT)−1ΩNN−1)−1(NT)−1NT=(I+λ(NT)−1ΩNN−1)−1 Sλ=N(NTN+λΩN)−1NT=(I+λ(NT)−1ΩNN−1)−1
Smoother matrix, Sλ는 다음과 같이 나타낼 수 있다.
K는 λ의 영향을 받지 않는 symmetric 행렬이 된다. Sλ=(I+λK)−1와 K의 고유값(d1,…,dN)을 이용하여, Sλ의 고유값 ρ1(λ),…,ρN(λ)를 나타내면 다음과 같다.
ρk(λ)=11+λdk,wherek=1,2,...,N Sλ=N∑k=111+λdkukuTk위와 같은 변형을 거치고 나면, λ를 통해 제약을 가하여 도출한 smoothing spline이 수축하는(shrinking) 특징을 갖는 이유를 한 눈에 확인할 수 있다. smoothing spline 최소화 문제에서 fitted curve의 구불구불한 정도(curvature)를 제한하는 penalty가 강하게 부과될 수록, λ의 값은 더 커지게 되고, Sλ 행렬의 원소들의 절대값은 전체적으로 줄어들게 된다. 즉 λ의 값이 클 수록, 더 smooth한 spline이 도출될 것을 예상해 볼 수 있다.
위의 사진은 같은 데이터에 λ의 값을 달리하여 smoothing spline을 적용한 결과를 나타낸 그림이다. 더 높은 값의 λ가 적용된 (즉, 더 curvature 제약이 강하게 적용된) 빨간색 smoothing spline이 초록색 smoothing spline보다 더 smooth한 곡선을 이루고 있는 것을 볼 수 있다. 따라서 이와 같은 curvature 제약 때문에, smoothing spline은 N개의 데이터로부터 N개의 basis로 이루어진 Natural cubic spline을 도출하는데도, 단순히 N개의 점을 모두 지나는 곡선이 아니라, 점들의 추세를 나타내는 smoothing 곡선이 될 수 있는 것이다.
5.5 Automatic Selection of the Smoothing Parameters
그렇다면 데이터가 주어졌을 때, 위와 같이 Smoothing spline을 구하는 과정에서, curvature 제약의 강도를 결정하는 최소화문제의 tuning parameter, λ의 값은 어떻게 결정할까?
5.6 Nonparametric Logistic Regression
5.7 Multidimensional Splines
5.8 Regularization and Reproducing Kernel Hilbert Spaces
5.9 Wavelet Smoothing
Reference
Hastie, T., Tibshirani, R.,, Friedman, J. (2001). The Elements of Statistical Learning. New York, NY, USA: Springer New York Inc..