Machine Learning (Regularization)

1. Regularization

 Regularization은 말 그대로 제약이다. 기계 학습에서 무엇을 왜 어떻게 제약하는지에 대해서 알아보자. 직관적으로 생각하면, 어떤 문제를 해결하는 분류기를 찾고 싶을 때, 해당 분류기가 들어있는 통이 너무 커서 적절한 답을 찾기 힘들 때, 분류기들을 일단 채에 한번 걸른 후에 걸러진 것들 중에 답을 찾는 것과 비슷하다. 채의 구멍의 크기, 혹은 모양이 서로 다른 regularization을 의미한다. (정확한 비유는 아니다.)

 조금 수학적으로 써보면, 우리에게 들어오는 데이터 '$y = f + \epsilon$'는 에러 '$\epsilon$' 이 들어가있다. 그래서 우리의 모델은 에러를 같이 학습하려는 경향이 있다. 그래서 in-sample error '$E_{in}$'은 좋게 나올 수 있으나, out-sample error '$E_{out}$'은 나빠지는 현상이 발생하곤 한다. 어려운 말로는 generalization이 잘 되지 않는 것이다. 그래서 우리의 Hypothesis set '$H$'가 있을 때, 단순히 '$E_{in}$'을 줄이는 것뿐 아니라 특정 제약 조건, Regularization term, 을 추가해서 generalization property를 좋게하는데 그 목적이 있다. 

Regularization은 '$E_{out}$'을 좋게 하는데 목적이 있다. 

 아래 그림이 그 효과를 보여준다. (물론! 잘 되는 경우다.)

 즉 에러나 model complexity 등에 인한 문제로 overfit되는 것을 막아주는 것을 알 수 있다. 사실 우리의 목적인 target이 푸른색 선과 같이 있었을 수도 있다. 결국 regularization을 사용하는 것 이면에는 우리가 갖고 있는 데이터는 우리의 model complexity보다 간단하다는 가정이 있다고 봐도 무관할 것 같다. 이러한 regularization을 해석하는데는 크게 두 가지 관점이 있다. 

1. mathematical: ill-posed problems in function approximation

2. heuristic: handicapping the minimization of '$E_{in}$'

그리고 사실 (비밀이지만?) 후자의 비중이 훨씬 더 크다. 교수님은 이것은 과학이 아닌 예술의 영역이라고 하셨다. 

1.1 Heuristic methods 

 

 먼저 Heuristic 한 방법부터 살펴보자. VC dimension 관점에서 '$E_{out}$'의 generalization bound를 써보면 다음과 같다. 

$$ E_{out}(g) \le E_{in}(g) + \Omega(H) $$

 위의 식에서 '$\Omega(H)$'에 해당하는 것이 우리가 찾아볼 hypothesis의 공간이고, VC bound는 이 공간의 크기에 따라 결정된다. 결국 이 공간의 크기가 작아지게 되면 vc bound가 tight해질 것을 예상할 수 있다. 그래서 이제 우리가 찾고 싶은 '$\hat{h} \in H$'는 단순히 '$E_{in}$' 만을 줄이는 것이 아니라 새로운 regularize term인 '$\Omega(h)$' 역시 같이 줄이는 hypothesis인 것이다. 결국 이 regularization term이 우리의 목적함수에 포함 될 것을 예상할 수 있다.  

1.2 Weight Decay ('$l_2$' regularization, Ridge regression)

Regularization 기법 중 가장 대표적인 것이 바로 이 weight decay이다. 그리고 이 방법은 어떤 hypothesis '$h$'에 대한 복잡도 ('$\Omega(h)$')를 평가하는 기준으로 coefficient의 크기를 사용한다. (그 중에서도 '$l_2$' norm) 즉 쉽게 생각해서 2차원 공간에서 기울기가 곧 coefficient가 되므로, 기울기가 큰 함수들 보다는 기울기가 작은 함수들을 더 선호하겠다는 의미를 갖는다. 

이를 이용해서 sin함수를 regression하면 다음과 같이 된다고 한다. 결과를 보면 얼마나 잘 fit되었는지에 의미하는 bias는 약간 나빠지는 대신 generalization에 해당하는 variance가 엄청나게 줄어드는 것을 알 수 있다. 간단한게 짱이다. 

1.3 Soft Order Constraints

 자 이제 수학적으로 조금 들어가보자. 우리는 Legendre polynomial를 이용해보겠다. 이 polynomial은 수열의 order에 따라 다른 값을 갖고, 다른 order에 해당하는 모양과 곱한 후에 -1~1사이를 적분하면 (아마도?) 0이 되는 orthogonal한 특징이 있다고 한다. (분명 배웠을텐데 기억이 나질 않는다..)

 여튼 우리에게 어떤 input '$x$'가 주어졌을 때, '$Q$'-order Legendre polynomial로 mapping해주는 '$\Phi$'가 있다고 하자. 

 이 때 우리가 사용할 Hypothesis set은 다음과 같다. 

$$ H_Q = {h | h(x) = w^Tz = \sum_{q = 0}^{Q} w_qL_q(x) }$$

여기서 '$L_q(x)$'는 '$q$'-order Legendre polynomial에 '$x$'를 넣어서 얻은 값이다. 즉 다음과 같은 단계를 거쳐서 어떤 출력이 나온다. 

1. '$x \in R$' 가 주어진다. 

2. '$\Phi$'를 통해 '$z \in R^{Q+1}$'을 얻는다. (Legendre mapping) '$Q+1$'인 이유는 +1의 bias가 있기 때문이다. 

3. 이 공간에서 linear combination을 통해 '$y =h(x)$'를 얻는다. 

자! 그렇다면 이제 앞에서 헀던 것과 같이 '$E_{in}$'을 정의해보자. 이렇게 정의된 '$E_{in}(w)$'을 최소로 하는 '$w$'를 찾을 것이다. 

$$ E_{in}(w) = \frac{1}{N} \sum_{n=1}^{N} (w^Tz_n -y_n)^2 $$

이를 Matrix form으로 써보면

$$ E_{in}(w) = \frac{1}{N} ||  Zw - Y  ||^2 = \frac{1}{N} (Zw - Y)^T(Zw - Y) $$

와 같다. 어디서 많이 본 꼴이 아닌가? 바로 ordinary least square (OLS)에 나온 그 식이고 답은 다음과 같다. 

$$ w_{lin} = (Z^TZ)^{-1}Z^TY$$

여기까진 앞에서 했던 것과 다를바가 없다. 그런데 문제가 생겼다. 우리가 원래 '$Q = 10$'으로 했다고 하자. 즉 '$10$'-th order Legendre polynomial까지 사용해서 11 차원의 feature vector를 얻었는데, 교수님이 오셔서 이건 너무 복잡하니 복잡도를 낮춰! 라고 하셨다고 하자... 자, 이제 어떻게 할 것인가? 

 간단한 방법은 그냥 '$H_{10}$' 대신에 '$H_{2}$'를 쓰는 것이다. 즉 간단하게 2차 Legendre polynomial까지만 쓰는 것이다. 

위의 식과 같이 할 경우, 모든 것이 간단하지만, 몬가 조금 아쉽다. 사람이 조금 유도리가 있어야... 그래서 매정하게 딱 2차 까지만 쓰는게 아니라 그 중간을 지점의 solution을 찾아보는 것이다. 즉 우리가 애초에 잡은 '$Q =10$'까지의 모든 polynomial을 다 씀과 동시에 다음과 같은 soft order constraint를 추가하는 것이다.

$$ \sum_{q = 0}^{Q} w_q^2 \le C $$

즉, weight 들을 0으로 fix하는 hard order constraint 대신에, 이 값들의 squared sum에 대한 constraint를 주는 soft order constraint를 주는 것이다. 그림으로 표현해보면 아래와 같다. 

물론 위의 식에서 '$C$'를 어떻게 잡는지에 대한 문제가 남아있긴 하다. 하지만 우리가 직관적으로 알 수 있는 것이 '$C$'가 크면 클 수록 regularization에 조금 될 것을 알 수 있다. 

위의 soft order constraint를 포함한 optimization 식은 다음과 같다. 

minimize     '$ E_{in}(w) = \frac{1}{N} (Zw-Y)^T(Zw-Y) $'

subject to   '$w^Tw \le C$'

자 이제 위의 문제만 풀어서 '$w_{reg}$'를 구하면 된다! 하지만 어디 세상이 그리 호락호락 하겠는가... 위의 문제를 푸는 것은 생각보다 쉽지 않다. Convex optimization을 배워본 사람이라면 알겠지만 위와 같은 inequality constraint를 처리하는 것은 꽤나 어렵다. Interior point method란 걸 써야하는데, 어렵다.. 구현해보면 안다. (주제와는 멀지만, 예전에 과제로 Semidefinite programming을 primal-dual interior point method를 이용해서 구현하려다가 피똥싼적있다. 그 뒤론 optimization 관련 식 볼때마다 inequality constraint를 어떻게 처리하나 보는데, 최근 나오고 있는 augmented Lagrangian 이나, proximal mapping 관련 논문들에선 신기할 정도로 inequality constraint에 대한 언급을 하지 않는다. 모두가 암묵적으로 안건들이는 듯하다. 물론 대부분의 경우 auxiliary variable을 놓아서 equality constraint로 바꾼 뒤에 auxiliary variable을 원래 cost function에 추가하는 방법을 쓴다고 하지만, 정작 그들이 푼 문제를 들어가보면 아예 inequality constraint가 없는 경우가 참 많다. )

 여튼 그래서 우리는 이 문제를 equality constraint로 바꿔서 풀겠다. 

위의 optimization 문제를 그림으로 그려보면 위와 같다. 먼저 파란색 선이 '$E_{in}$'에 대한 등고선이다. '$w_{lin}$'이 의미하는 것이 원래 '$E_{in}(w) = \frac{1}{N}(Zw-Y)^T(Zw-Y)$' 를 최소로 하는 '$w$'의 위치이다. 여기에 한 가지 제약 조건이 붙었는데 그것은 '$w$'가 붉은 색 선 위에 있어야 한다는 것이다. 이것이 의미하는 것은 linear constraint를 만족하는 feasible set이다. 결국 '$w_{lin}$' (OLS의 solution)에 가장 가까우면서 붉은 색 선 위에 있는 '$w$'를 찾는 것이다. 

이러한 문제를 풀기 위해선 Lagrange multiplier를 도입한 후에 KKT condition을 통해 풀면되는데, 교수님은 convex 수업을 안들은 사람들도 이해할 수 있게 위의 그림을 통해서 설명하셨다. (사실 같은 내용이다.)

우리가 찾고 싶은 '$w_{reg}$'는 아래 그림과 같은 조건에서 존재한다. 

즉 '$w^Tw = C$'에 해당하는 gradient인 '$w$'와 '$\nabla E_{in}$'이 서로 다른 방향에 있으면 된다. 

$$ \nabla E_{in}(w_{reg}) \propto -w_{reg} = -2\frac{\lambda}{N} w_{reg} $$

와 같이 표현된다. '$-2\frac{\lambda}{N}$'이 붙은 이유는 뒤에서 계산을 편하게 하기 위해서이고 '$\lambda$'가 바로 Lagrange multiplier이다. 

 여튼 이 문제를 unconstrained optimization 문제로 바꿀 준비가 다 되었다. 

$$ E_{aug}(w) = E_{in}(w) + \frac{\lambda}{N}w^Tw $$

를 최소로 하는 '$w$'를 찾으면 된다. 

사실 KKT를 바로 쓰면 원래 cost function인 '$E_{in}(w)$'와 equality constraint인 '$w^Tw - C = 0$'아페 Lagrange multiplier인 '$\frac{\lambda}{N}$'을 곱한 후에 '$w$'로 미분한 뒤에 '$=0$'을 한 것과 같다. 

여튼 이렇게 정리하고 보면 우리의 문제가 

$$ E_{aug}(w) = E_{in}(w) + \frac{\lambda}{N}w^Tw $$

이렇게 바꾸게 된다. 더이상 '$C$'는 존재하지 않지만 대신에 '$\lambda$'가 그 역할을 해준다. 이 값이 크면 regularization이 더 강하게 된다. 즉 '$C$'가 작아지는 효과가 있다. 

위의 식은 OLS 때와 같이 '$w$'로 미분이 잘 된다. 

위와 같이 정리가 되고, 우리의 최종 solution은 다음과 같다. 이러한 꼴을 ridge regression이라고 한다. 

$$ w_{reg} = (Z^TZ  + \lambda I)^{-1}Z^TY$$

한 가지 재밌는 사실은 일반적으로 어떤 matrix가 invertable하지 않을 때 우리가 numerical한 stability를 위해서 자주 사용되는 기법이 바로 저거이다. 저렇게 diagonal term에 작은 수를 더해주면 matrix가 대부분의 경우 non singular해지기 때문이다. 

물론 '$lambda$'를 잘 고를 필요가 있다. 아래 그림이 다른 '$lambda$'에 따른 regression의 결과 차이를 보여준다. 

1.4 Augmented Error

 지금까지는 '$w$'에 대한 regularization으로 '$w^w = C$'라는 꼴의 제약을 두었다. 하지만 이를 좀 더 일반적으로 표현하면 다음과 같다. 

$$ E_{aug}(h) = E_{in}(h) + \frac{\lambda}{N} \Omega(h)$$

 뒤에 붙은 부분이 penalty이고, '$\lambda$'는 얼마나 penalty를 많이 줄지 (이 값이 커지면 penalty가 커진다)를 정하고, '$\frac{1}{N}$'이 붙는 이유는 보통 '$E_{in}(h)$'에 '$\frac{1}{N$'이 있어서 계산 상의 편의를 위해서인듯 하다. 

결과적으로 이러한 penalty가 추가된 '$E_{aug}$'는 '$E_{in}$' 만을 사용했을 때보다 더 좋은 '$E_{out}$'의 proxy이다. 

일반적으로 가장 유명한 regularizer는 '$l_1$'과 '$l_2$'이고, '$l_1$' regression은 lasso라고 불리며 최근 유행하는 (했던) sparse representation에 적합하다. 각각을 그림으로 표현해보면 다음과 같다. 

elastic net penalty라고 이 둘의 중간 정도 되는 것도 있는데, 말그대로 중간 정도의 성능을 보인다. 

$$ \Omega(w) =\sum_q {\frac{1}{2}(1-\alpha)w_q^2 + \alpha |w_q|  } $$

'$\alpha$'가 이 둘 사이의 weight를 정해준다.