[신호처리] Least Mean Square(LMS) Algorithm

An Application of Stochastic Gradient Decent Method

Stochastic Gradient Decent 방법론은 내가 배우는 Adaptive Filtering 알고리즘에서 Iterative Adaptation을 통해 Gradient를 찾는데에 사용된다. 여기서 Adaptive Filtering이란 Unknown Environment의 Statistical Variations^{통계학적 변화}에 “Adapt”^적응 하는 성질을 가진 Filter^{또는 알고리즘, 시스템} 를 말한다.

[1] What is Stochastic Gradient Dscent?

“Stochasitc” 이란 단어의 어원은 “Random Choice” 라는 뜻을 의미하는 그리스어에서 왔으며, Stochastic Gradient Descent는 Object function^{목적함수 또는 Loss/Cost function}를 최적화 하기 위해 쓰이는 Iterative Method^{반복적인 방법론}이다. Stochastic Gradient Descent는 오랜 역사를 가지고 있는데, 통계학 분야에서 특정 Sequential Parameter Estimation^{순차 매개변수 추정} 문제를 푸는데 사용되는 방법으로 1951년에 Robbins와 Monro에 의해 소개가 되었다. 요즘 들어서는, Machine Learning^기계학습에서 최적화 문제에 요긴하게 쓰이는 알고리즘이기도 하다.

[2] Optimization and Complexity

Stochastic Gradient Descent 방법론은 “Suboptimal”하다.

• 즉, 완벽한 최적화를 보장하지 않는다고 보면 된다. Stochastic한 성질 때문에 Convex Optimization Problem에서 우리가 원하는 Desired Optimum Solution에 다다를 수 없다.
• 오히려 Local Minima (i.e. Local Neighborhood^국소범위에서의 Optimum Solution)에 한번 빠지게 되면, 그 근처를 Random-walk 방법으로 배회하다가 결국 Equilibrium Point^평형점에 안착하지 못하게 된다.

• 하지만, Stochastic Gradient Descent 방법론은 이러한 계산적 결함을 Adjustable Parameters^{조정가능한 매개변수}에 대한 Linear law of scaling^{선형 크기조정 방법}으로 가장 간단한 형태로 보상해준다.
• 따라서 시간에 따라 사이즈가 증가하는 Information-bearing data를 다룰 때와 같이 계산 복잡도가 중요시 될 때 실용적으로 활용할 수 있다.

[3] Efficiency

• Efficiency는 만족하는 해를 찾을 때 사용되는 비용 의미한다.
• 이를 측정하는 방법에는 실행시간, Adaptation을 위해 돈 Algorithm Cycle 횟수 등 여러가지가 있지만 Rate of Convergence</sup>수렴률</sup>이 쓰인다.
• Rate of Convergence는 Stationary environment에서 돌아가는 LMS^{Least-Mean-Square}나 RLS^{Recursive Least-squares} 알고리즘 등과 같은 Linear Adaptive Filtering Algorithm을 기준으로 통계학적 학습론과 Wiener solution을 포함한다.

[4] Robust

[5] Curse of Dimensionality

[6] Time-varing Problems

[7] Monte Carlo Simulations

Least Mean Square(LMS) Algorithm

LMS 알고리즘은 Widrow와 Hoff가 고안한 알고리즘으로, 다음과 같은 특징이 있어서 Adaptive Filtering Algorithm으로 가장 널리 쓰인다.

[1] Features

1. Simple
   • FIR(Finite-duration Impulse Response) filter의 차원에 따라 계산복잡도가 Linearly sclae된다.
2. No Statistical Characteristics
   • Wiener filter와는 다르게 LMS 알고리즘은 돌아가는 환경에 대한 통계학적 특징을 요구하지 않는다.
3. Robust in Deterministic Sense
   • Unknown Envrionment Distrubance가 있어도 알고리즘은 Single Realization을 해낸다.
4. No Inversion of the Correlation Matrix of the regressor
   • Regressor(Input vector)의 correlation matrix의 역행렬이 필요하지 않아서 반대 경우인 RLS 알고리즘보다 더 간단하다.

[2] Structural Description

LMS 알고리즘은 FIR filter와 Comparator, Adaptive Weight-Control Mechanism 세 가지 구조로 구성되어 있다.

1. FIR Filter

   • Desired Response의 Estimate $\hat{d}(n

     \mathcal{U}_n)$를 얻기 위해 Regressor(Input Vector) $\textbf{u}(n)$을 계산한다.

   • 여기서 $\mathcal{U}_n$은 Input Vector $\textbf{u}(n)$이 존재하는 공간을 말한다.
2. Comparator

   • Desired Signal $d(n)$에서 Estimate $\hat{d}(n

     \mathcal{U}_n)$를 뺀 Estimation Error (Error Signal) $e(n)$이다.

3. Adaptive Weight-Control Mechanism
   • Estimation Error $e(n)$에서 얻어진 정보를 이용해 FIR filter의 각 Tap Weight들의 Incremental Adjustment을 조정하는 함수이다.