Least-Mean-Square Algorithm

요약

 LMS 알고리즘은 가장 유명한 학습법 중 하나이며, LMS 알고리즘은 성능이 좋으면서도, 빠르고 효율적이며 코드 짜기도 쉽다. 본 포스트에서는 선형회귀만을 다룹니다.

Adpative Filter

 LMS 알고리즘은 adaptive filter라고 할 수 있으며 filtering process와 adaptive process가 합쳐져 있다. $w$와 i번째 샘플 $x(i)$로부터 예상된 결과가 $y(i)$라 할때, $y(i)$와 실제 정답 $d(i)$를 비교함으로써 error $e(i)$를 얻는 과정이 filtering process이고, $e(i)$로부터 $w$를 적절하게 수정해 나가는 과정이 adaptive process이다.

 

 어떤 이상적인 분류기의 모델로서 optimal solution $w*$가 있다고 할때, 실제 $w*$는 알 수가 없으므로, 우리의 목표는 가지고 있는 sample들로부터 error를 가장 작게 만드는 $w$를 찾는 것이다. $w$에 관한 error를 $\mathcal{E}$라 하면, $\mathcal{E}(w*) <= \mathcal{E}(w)$ 일 것이며, $w*$가 optimal solution일 조건은 $\triangledown\mathcal{E}(w*) = 0$ 이다.

 $w$가 $w*$에 가까워지도록 하는 adaptive filter는 iterative descent의 방식으로 진행된다. 즉 i번째 iteration에서의 error를 $\mathcal{E}(w(n)) $라 하면 $\mathcal{E}(w(n+1)) < \mathcal{E}(w(n)) $가 된다.

Steepest Decsent Algorithm

 말그대로 가장 가파른 곳으로 내려가는 알고리즘으로, $w$에 대한 에러 $\mathcal{E}(w)$의 경사가 가장 가파른 곳으로 내려가는 알고리즘으로, 

 $w(n+1) = w(n) - \eta $\triangledown\mathcal{E}(w)$

 $ \triangle w(n) = w(n+1) = w(n) = - \eta $\triangledown\mathcal{E}(w) = -\eta g(n)$

가 된다. 이러한 방식을 통해 $w$가 $w*$에 가까워지는 이유는 다음과 같이 error를 테일러 전개 함으로써 알 수 있다.

 $\mathcal{E}(w(n+1)) = \mathcal{E}(w(n)) + \triangledown \mathcal{E}(w(n))^T \triangle w(n) + \mathcal{O}((\triangle w(n))^2) \simeq \mathcal{E}(w(n)) - \eta g^T(n)g(n) = \mathcal{E}(w(n)) - \eta \parallel g(n) \parallel^2$

 $ \therefore \mathcal{E}(w(n+1)) < \mathcal{E}(w(n)) $

Newton's Method

 이번에는 에러 함수를 이차항까지 테일러전개를 하면 아래와 같다.

 $ \triangle(\mathcal{E}(w(n))) = \mathcal{E}(w(n+1)) - \mathcal{E}(w(n)) $

        $ = \mathcal{E}(w(n)) + \triangledown \mathcal{E}(w(n))^T \triangle w(n) + \frac{1}{2} \triangledown^2 \mathcal{E}(w(n))^T (\triangle w(n))^2 + \mathcal{O}((\triangle w(n))^3) - \mathcal{E}(w(n)) $

        $ = g^T(n) \triangle w(n) + \frac{1}{2} \triangle w^T(n) H(n) \triangle w(n)$, H(n)은 헤세 행렬 ( H(n) = \triangledown^2 \mathcal{E}(w(n))

 즉, $g(n) + H(n) \triangle w(n) =0$ 일때 에러의 차가 최소가 된다.

$\therefore w(n+1) = w(n) - H^{-1}(n)g(n)$

Gauss-Newton Method

 Todo

The Least Mean Square Algorithm

 에러 함수를 다음과 같이 정의하면

 $\mathcal{E}(w) = \frac{1}{2} e^2(n)$,

 gradient vector는 다음과 같다.

 $ g(n) = \frac{\partial \mathcal{E}(w)}{\partial w} = e(n) \frac{\partial e(n)}{\partial w} = - e(n)x(n)$

 여기서 Steepest Descent를 활용하여 $w$를 업데이트 시키면 다음과 같다.

 $ w(n+1) = w(n) + \eta x(n)e(n)$

 

LMS 알고리즘은 environment에 대한 정보가 하나도 없어도 적용이 가능하다.

 

코드로 구현한 내용은 전에 작성한 포스트에 있습니다.

Lecture2 Linear classifiers, SGD