[통계계산방법론] RIDGE 와 LASSO

Stein's Paradox 

통계학에서의 추정량의 Efficiency의 정도는 MSE를 기준으로 한다. MSE(Mean Squared Error)가 작으면 작을수록 그 추정량은 좋은 추정량이라고 할 수 있다. 보통 bias가 0인 비편향추정량으로 MLE와 UMVUE가 좋은 추정량으로 생각되는데 Stein's Paradox는 bias가 있다 하더라도 MSE가 더 작게 만들 수 있는 더 좋은 추정량을 생각해낸다. 그 추정량은 'James-Stein Estimator'라고 불린다. 

 

JS estimator의 형태는 다음과 같다.

모수의 개수 p가 3보다 크거나 같은 경우에는 JS 추정량의 Risk는 MLE나 UMVUE의 것보다 작은 것을 확인할 수 있다.

 

 

JS 추정량은 각각의 component들을 origin쪽으로 잡아당기는 역할을 한다. 그렇게 함으로써 bias는 증가하게 되지만, variance는 작아지게 되는 효과를 기대하는 것이다(Variance가 작아지면 통계량의 값은 커지는 효과를 가지기 때문에 signal이 커질 수 있음.). 추정량을 구할 때는 Normality assumption은 그리 중요하지 않다고 한다. 또한 이러한 Stein 현상은 각각의 개별 추정량을 구하는 것보다 모든 추정량을 동시에 추정할 때만을 다룬다.

 

Ridge Regression (능형회귀)

일반적인 선형모형에서는 X가 full-rank임을 가정하여 ols추정량을 구한다. 하지만 X가 full-rank가 아닐 때는 어떤 추정량을 사용해야 할까? 이때 우리는 다음과 같은 추정량을 생각해 볼 수 있다. lambda항을 추가하여 inverse가 존재하는nonsingular matirx를 만드는 아이디어이다.

이 beta tilda는 다음과 같은 식을 만족하는 solution임을 알 수 있다.

Ridge Regression은 이러한 아이디어를 착안하여 다음과 같이 penalized form 또는 constrained form을 풀어서 Ridge Regression 추정량을 구할 수 있다는 것이다.

Penalized form

constrained form

여기서의 lambda와 t는 tuning parameters이며 반비례관계이다.

 

다음과 같은 그림에서 확인할 수 있듯이, RR 추정량은 OLS 추정량 중에서 contraints를 만족시키는(보통 0에 가까운) 값이다. 적절하게 tuning을 해준다면 OLS 추정량보다 MSE가 작은 RR 추정량을 찾을 수 있을 것이다.

출처: Kyoosik Kim, towards data science

Training data에서 구한 추정량을 통하여 구하고 이를 이용하여 test data를 예측해보면, 원래의 자료와 예측된 자료 사이의 Predition Error가 발생한다. Predicition Error는 pure error와 model error로 구분된다.

이때 pure error는 irreducible한 오차로, 데이터가 반드시 가질 수밖에 없는 값을 의미한다. Model Error는 수정할 수 있기 때문에 우리는 이 오차를 작게 만드는 것에 목적을 둔다.

Model Error

Model Error는 위와 같이 decomposed 될 수 있는데 이는 bias와 variance이고, 적절히 조절만 한다면 OLS보다 MSE가 더 작은 좋은 추정량을 구할 수 있다.

 

LASSO (Least Absolute Shrinkage and Selection Operator)

Ridge 모형에서는 Constraint가 L2-norm으로 주어진다. 이제 Lasso에서는 제약 조건이 L1-norm으로 주어진다. Lasso 추정량은 다음과 같은 식을 만족하는 베타 값이다.

penalized form

Constrained form

이때 tuning parameter인 t와 lambda는 서로 반비례관계이다. 

 

Lasso는 Sparse matrix(벡터 상 원소들의 몇 개는 0이고 몇 개는 0이 아닌 것)를 만들기 때문에 0의 값을 가지는 변수에 대한 variable selection을 할 수 있으면서 RR 추정량처럼 ols추정량보다 MSE값이 작게 만들 수 있다. 

 

Ridge와 비슷하게 그 솔루션의 location을 다음 그림으로부터 확인할 수 있다.

그림에서 확인할 수 있듯이 ols의 추정량 중에서 L1 norm을 만족하는 경우의 solution은 (0, x)의 값으로 Ridge와는 달리 0의 값을 포함하는 것이 보인다. 이는 앞서 말했던 sparse matrix와의 관계가 보인다. 

 

Convex Optimality 

Optimization 문제는 어떤 주어진 조건 하에서 목적함수를 최대/최소화 하는 것이다. 여러 가지 optimization 기법이 있는데 그 중에서 convex optimality를 다뤄본다. Convex optimization은 목적함수 및 constraints가 convex function에 속하는 것이고, 범위에 해당하는 domain이 convex set으로 정의된 경우에 해당한다. 

 

Convex function과 Convex set은 다음과 같이 정의된다. 

따라서 위의 조건을 만족하는 함수에 대해서 convex optimization은, 그 목적함수를 최소화하는 optimal한 값을 찾는 것이다. (optimal한 포인트는 unique하지 않을 수 있지만 optimal한 값은 unique함.) 

 

Differentiable한 함수에서 beta*가 다음을 만족하고 convex set에 속하면 global Optimum이라고 한다. (이 theorem은 왜 갑자기 나오는 지 모르겠네,,,) 

하지만 convec function이라고 해서 다 differentiable한 것은 아니다. 예를 들면 Lasso 추정량을 구할 때의 목적함수는 L1-norm의 형태가 절댓값이기 때문에 미분가능하지 않다. 따라서 미분의 개념을 확장해야 한다. 그 확장된 개념이 바로 Subgradient이다. 그에 대한 정의는 아래와 같다. 

beta1에서는 f가 diffrentiable하기 때문에 그 포인트에서는 subgradient는 f'(beta1)으로 오직 하나만 존재한다. 하지만 beta2의 포인트에서는 미분이 가능하지 않기 때문에 여러 개의 subgradients가 존재한다. Beta라는 포인트에서의 모든 subgradients들의 집합을 subdifferential이라고 부르고 $\partial f(\beta)$ 라고 쓴다. zero-gradient는 이에 포함된다. 

 

Coordinate Decent Algorithm (좌표별 강하 알고리즘)

Coordinate descent는 반복적으로 각 좌표축을 따라 움직이며 목적함수의 최솟값을 찾는 최적화 알고리즘이다. 각 반복(iteration)에서 좌표 선택 규칙(coordinate selection rule)에 따라 좌표축(coordinate) 또는 좌표축 블록(coordinate block)을 결정한 뒤, 선택되지 않은 좌표축 또는 좌표축 블록은 고정한 채로 축의 방향을 따라 함수를 최소화시킨다 (exact or inexactly). Coordinate descent는 gradient를 이용하는 방식뿐 아니라 gradient를 이용하지 않는 방식으로도 활용할 수 있다.

 

우리는 LASSO 문제에서 CD 알고리즘을 사용하려고 한다. 우리의 목적함수는 위에 나와있는 LASSO 함수를 $\beta$에 대해서 minimize 시키는 것이다. 알고리즘의 단계는 다음과 같다.

1. $\beta^{(0)}$ 를 initializing한다. 

2. t번째 iteration에서 $\beta_j$를 업데이트한다. ( j=1,...,p)

betak 만을 업데이트 시키고 나머지 beta들은 현재 값으로 고정시키는 것이다. 

3. 이 과정을 converge될 때까지 반복한다. 

 

이 과정에서 CD 알고리즘은 j를 순서대로 선택하는 것이 아니고, ramdom하게 선택한다. 그리고 이 알고리즘은 closed form의 solution을 가지고 있는 one-dimensional 문제에 유용하다. 

 

Reference

• 고려대학교 신승준 교수님 ST509 강의자료
• http://sanghyukchun.github.io/63/

Machine learning 스터디 (7) Convex Optimization - README

• https://wikidocs.net/23359

위키독스