최소 평균 제곱 필터

**최소 평균 제곱**(Least mean squares filter, **LMS**) 알고리즘은 원하는 신호와 실제 신호 간의 차이인 오차 신호의 최소 평균 제곱을 생성하는 필터 계수를 찾아 원하는 필터를 모방하는 데 사용되는 적응 필터의 한 종류이다. 필터가 현재 시간의 오차에만 기반하여 적응한다는 점에서 확률적 경사 하강법의 한 방법이다. 1960년 스탠퍼드 대학교 교수 버나드 위드로와 그의 첫 박사 과정 학생 테드 호프가 단층 신경망 연구를 기반으로 발명했다. 특히, 그들은 아달라인(ADALINE)을 훈련하여 패턴을 인식하는 데 경사 하강법을 사용했으며, 이 알고리즘을 "델타 규칙"이라고 불렀다. 그들은 이 규칙을 필터에 적용하여 LMS 알고리즘을 만들었다.
# 문제 공식화
그림은 필터의 다양한 부분을 보여준다. x는 입력 신호이며, 우리가 \hat h를 사용하여 일치시키려는 알 수 없는 필터 h에 의해 변환된다. 알 수 없는 필터의 출력은 y이며, 여기에 노이즈 신호 \nu가 간섭하여 d = y + \nu를 생성한다. 그런 다음 오차 신호 e = d - \hat y = y + \nu - \hat y가 계산되고, 이 신호는 평균 제곱 오차, \sum e^2/n를 최소화하기 위해 매개변수를 조정하도록 적응 필터에 피드백된다. LMS 필터
## 위너 필터와의 관계
인과적인 위너 필터의 실현은 신호 처리 영역을 제외하고는 최소제곱 추정량의 해와 유사하다. 입력 행렬 \mathbf{X}와 출력 벡터 \boldsymbol y에 대한 최소제곱 해는 다음과 같다. : \boldsymbol{\hat\beta} = (\mathbf{X} ^\mathbf{T}\mathbf{X})^{-1}\mathbf{X}^{\mathbf{T\boldsymbol y . 유한 임펄스 응답(FIR) 최소 평균 제곱 필터는 위너 필터와 관련이 있지만, 전자의 오차 기준을 최소화하는 것은 상호 상관 관계나 자기상관에 의존하지 않는다. 그 해는 위너 필터 해로 수렴한다. 대부분의 선형 적응 필터링 문제는 위 블록 다이어그램을 사용하여 공식화할 수 있다. 즉, 알 수 없는 시스템 \mathbf{h}(n)을 식별해야 하며, 적응 필터는 x(n), d(n) 및 e(n)과 같은 관측 가능한 신호만 사용하면서 필터 \hat{\mathbf{h(n)를 \mathbf{h}(n)에 가능한 한 가깝게 적응시키려고 시도한다. 그러나 y(n), v(n) 및 h(n)은 직접 관측할 수 없다. 그 해는 위너 필터와 밀접하게 관련되어 있다.
## 기호 정의
:n은 현재 입력 샘플의 수이다. :p는 필터 탭의 수이다. : \\{\cdot\\}^H (켤레 전치) :\mathbf{x}(n) = \left[x(n), x(n-1), \dots, x(n-p+1)\right]^T :\mathbf{h}(n) = \left[h_0(n), h_1(n), \dots, h_{p-1}(n)\right]^T,\quad \mathbf{h}(n) \in \mathbb{C}^p :y(n) = \mathbf{h}^H(n) \cdot \mathbf{x}(n) :d(n) = y(n) + \nu(n) :\hat{\mathbf{h(n) 추정된 필터; n 샘플 후 필터 계수의 추정량으로 해석 :e(n) = d(n) - \hat{y}(n) = d(n) - \hat{\mathbf{h^H(n) \cdot \mathbf{x}(n)
# 아이디어
LMS 필터의 기본 아이디어는 최적 필터 가중치 (R^{-1}P)에 수렴하도록 필터 가중치를 업데이트함으로써 최적 필터 가중치에 접근하는 것이다. 이는 경사 하강법 알고리즘을 기반으로 한다. 이 알고리즘은 작은 가중치(대부분 0)를 가정하고 시작하며, 각 단계에서 평균 제곱 오차의 기울기를 찾아 가중치를 업데이트한다. 즉, MSE-기울기가 양수이면 동일한 가중치를 사용하여 추가 반복을 해도 오차가 계속 양수로 증가한다는 의미이므로 가중치를 줄여야 한다. 마찬가지로, 기울기가 음수이면 가중치를 늘려야 한다. 가중치 업데이트 방정식은 다음과 같다. : W_{n+1} = W_n - \mu\nabla \varepsilon [n], 여기서 \varepsilon 는 평균 제곱 오차를 나타내고 \mu 는 학습률 계수이다. 음수 부호는 오차를 최소화하는 필터 가중치 W_i 를 찾기 위해 오차 \varepsilon 의 기울기를 따라 내려가는 것을 보여준다. 필터 가중치의 함수로서의 평균 제곱 오차는 이차 함수이며, 이는 평균 제곱 오차를 최소화하는 유일한 극값, 즉 최적 가중치를 가진다는 것을 의미한다. 따라서 LMS는 평균 제곱 오차 대 필터 가중치 곡선을 따라 오르내림으로써 이 최적 가중치에 접근한다.
# 유도
LMS 필터의 기본 아이디어는 최급강하법을 사용하여 손실 함수를 최소화하는 필터 가중치 \hat{\mathbf{h(n)를 찾는 것이다. 비용 함수를 다음과 같이 정의하는 것으로 시작한다. : C(n) = E\left\\{|e(n)|^{2}\right\\} 여기서 e(n)은 현재 샘플 n에서의 오차이고 E\\{\cdot\\}는 기댓값을 나타낸다. 이 비용 함수(C(n))는 평균 제곱 오차이며, LMS에 의해 최소화된다. 이것이 LMS의 이름이 유래된 곳이다. 최급강하법을 적용한다는 것은 필터 계수(가중치) 벡터의 개별 항목에 대해 편미분을 취하는 것을 의미한다. :\nabla_{\hat{\mathbf{h^H} C(n) = \nabla_{\hat{\mathbf{h^H} E\left\\{e(n) \, e^{*}(n)\right\\}=2E\left\\{\nabla_{\hat{\mathbf{h^H} ( e(n)) \, e^{*}(n) \right\\} 여기서 \nabla는 기울기 (벡터) 연산자이다. :\nabla_{\hat{\mathbf{h^H} (e(n))= \nabla_{\hat{\mathbf{h^H} \left(d(n) - \hat{\mathbf{h^H \cdot \mathbf{x}(n)\right)=-\mathbf{x}(n) :\nabla C(n) = -2E\left\\{\mathbf{x}(n) \, e^{*}(n)\right\\} 이제 \nabla C(n)은 비용 함수의 최급 상승 방향을 가리키는 벡터이다. 비용 함수의 최솟값을 찾으려면 \nabla C(n)의 반대 방향으로 한 걸음 나아가야 한다. 이를 수학적 용어로 표현하면 다음과 같다. :\hat{\mathbf{h(n+1)=\hat{\mathbf{h(n)-\frac{\mu}{2} \nabla C(n)=\hat{\mathbf{h(n)+\mu \, E\left\\{\mathbf{x}(n) \, e^{*}(n)\right\\} 여기서 \frac{\mu}{2}는 스텝 크기(적응 상수)이다. 즉, 비용 함수를 최소화하는 순차 업데이트 알고리즘을 찾은 것이다. 불행히도, E\left\\{\mathbf{x}(n) \, e^{*}(n)\right\\} 를 알 때까지는 이 알고리즘을 구현할 수 없다. 일반적으로 위 기댓값은 계산되지 않는다. 대신, LMS를 온라인(새로운 샘플이 수신될 때마다 업데이트) 환경에서 실행하기 위해 해당 기댓값의 순간적인 추정량을 사용한다. 아래를 참조하라.
# 단순화
대부분의 시스템에서 기댓값 함수 {E}\left\\{\mathbf{x}(n) \, e^{*}(n)\right\\} 는 근사되어야 한다. 이는 다음의 비편향 추정량으로 수행될 수 있다. :\hat{E}\left\\{\mathbf{x}(n) \, e^{*}(n)\right\\}=\frac{1}{N}\sum_{i=0}^{N-1}\mathbf{x}(n-i) \, e^{*}(n-i) 여기서 N은 해당 추정량에 사용하는 샘플의 수를 나타낸다. 가장 간단한 경우는 N=1이다. :\hat{E}\left\\{\mathbf{x}(n) \, e^{*}(n)\right\\}=\mathbf{x}(n) \, e^{*}(n) 이 간단한 경우 업데이트 알고리즘은 다음과 같다. :\hat{\mathbf{h(n+1)=\hat{\mathbf{h(n)+\mu \mathbf{x}(n) \, e^{*}(n) 실제로, 이것이 LMS 필터의 업데이트 알고리즘을 구성한다.
# LMS 알고리즘 요약
p차 필터에 대한 LMS 알고리즘은 다음과 같이 요약할 수 있다. {| | 매개변수: || p= 필터 차수 |- | || \mu= 스텝 크기 |- |초기화: || \hat{\mathbf{h(0)=\operatorname{zeros}(p) |- |계산: || n=0,1,2,... 에 대해 |- ||| \mathbf{x}(n) = \left[x(n), x(n-1), \dots, x(n-p+1)\right]^T |- ||| e(n) = d(n)-\hat{\mathbf{h^{H}(n)\mathbf{x}(n) |- ||| \hat{\mathbf{h(n+1) = \hat{\mathbf{h(n)+\mu\,e^{*}(n)\mathbf{x}(n) |}
# 평균에서의 수렴과 안정성
LMS 알고리즘은 기댓값의 정확한 값을 사용하지 않으므로 가중치는 절대적인 의미에서 최적 가중치에 도달하지 못하지만, 평균에서는 수렴이 가능하다. 즉, 가중치가 작은 양만큼 변할 수 있지만, 최적 가중치를 중심으로 변한다. 그러나 가중치가 변하는 분산이 크면, 평균에서의 수렴은 오해의 소지가 있을 수 있다. 이 문제는 스텝 크기 \mu 의 값이 적절하게 선택되지 않았을 때 발생할 수 있다. 만약 \mu 가 크게 선택되면, 가중치가 변하는 양은 기울기 추정량에 크게 의존하며, 따라서 가중치가 큰 값으로 변하여 첫 순간에 음수였던 기울기가 이제 양수가 될 수 있다. 그리고 두 번째 순간에, 가중치는 음수 기울기 때문에 반대 방향으로 큰 양만큼 변할 수 있으며, 따라서 최적 가중치 주변에서 큰 분산으로 계속 진동할 것이다. 반면에 \mu 가 너무 작게 선택되면, 최적 가중치로 수렴하는 데 걸리는 시간이 너무 길어질 것이다. 따라서 \mu 의 상한이 필요하며, 이는 다음과 같이 주어진다. 0<\mu<\frac{2}{\lambda_{\mathrm{max , 여기서 \lambda_{\max}는 자기상관 행렬 {\mathbf{R = E\\\mathbf{x(n){\mathbf{x}^H}(n)\\}의 가장 큰 고유값이다. 이 조건이 충족되지 않으면 알고리즘은 불안정해지고 \hat{h}(n)은 발산한다. 최대 수렴 속도는 다음과 같을 때 달성된다. :\mu=\frac{2}{\lambda_{\mathrm{max+\lambda_{\mathrm{min, 여기서 \lambda_{\min}은 {\mathbf{R의 가장 작은 고유값이다. \mu가 이 최적값보다 작거나 같다고 가정할 때, 수렴 속도는 \lambda_{\min}에 의해 결정되며, 값이 클수록 수렴이 빠르다. 이는 \lambda_{\max}가 \lambda_{\min}에 가까울 때 더 빠른 수렴이 달성될 수 있음을 의미하며, 즉 달성 가능한 최대 수렴 속도는 {\mathbf{R의 고유값 스펙트럼에 따라 달라진다. 백색 잡음 신호는 {\mathbf{R=\sigma^2 {\mathbf{I라는 자기상관 행렬을 가지며, 여기서 \sigma^2은 신호의 분산이다. 이 경우 모든 고유값이 같고, 고유값 확산은 가능한 모든 행렬에 대해 최소이다. 이 결과의 일반적인 해석은 따라서 LMS가 백색 입력 신호에 대해 빠르게 수렴하고, 저역 통과 또는 고역 통과 특성을 가진 프로세스와 같은 유색 입력 신호에 대해서는 느리게 수렴한다는 것이다. \mu에 대한 위 상한은 평균에서의 안정성만을 강제하지만, \hat{h}(n)의 계수는 여전히 무한히 커질 수 있으며, 즉 계수의 발산이 여전히 가능하다는 점에 유의하는 것이 중요하다. 더 실용적인 경계는 다음과 같다. :0<\mu<\frac{2}{\mathrm{tr}\left[{\mathbf{R\right]}, 여기서 \mathrm{tr}[{\mathbf{R]는 {\mathbf{R의 대각합을 나타낸다. 이 경계는 \hat{h}(n)의 계수가 발산하지 않도록 보장한다 (실제로는 이 경계의 유도에서 사용된 근사 및 가정 때문에 다소 낙관적이므로 \mu의 값을 이 상한에 가깝게 선택해서는 안 된다).
# 정규화된 최소 평균 제곱 필터 (NLMS)
"순수" LMS 알고리즘의 주요 단점은 입력 x(n)의 스케일링에 민감하다는 것이다. 이로 인해 알고리즘의 안정성을 보장하는 학습률 \mu를 선택하기가 매우 어렵다 (불가능하지는 않더라도) (Haykin 2002). 정규화된 최소 평균 제곱 필터(NLMS)는 입력의 전력으로 정규화하여 이 문제를 해결하는 LMS 알고리즘의 변형이다. NLMS 알고리즘은 다음과 같이 요약할 수 있다. {| | 매개변수: || p= 필터 차수 |- | || \mu= 스텝 크기 |- |초기화: || \hat{\mathbf{h(0)=\operatorname{zeros}(p) |- |계산: || n=0,1,2,... 에 대해 |- ||| \mathbf{x}(n) = \left[x(n), x(n-1), \dots, x(n-p+1)\right]^T |- ||| e(n) = d(n)-\hat{\mathbf{h^{H}(n)\mathbf{x}(n) |- ||| \hat{\mathbf{h(n+1) = \hat{\mathbf{h(n)+\frac{\mu\,e^{*}(n)\mathbf{x}(n)}{\mathbf{x}^H(n)\mathbf{x}(n)} |}
## 최적 학습률
간섭이 없는 경우(v(n)=0) NLMS 알고리즘의 최적 학습률은 다음과 같음을 보일 수 있다. :\mu_{opt}=1 이는 입력 x(n)과 실제(알 수 없는) 임펄스 응답 \mathbf{h}(n)에 독립적이다. 간섭이 있는 일반적인 경우(v(n) \ne 0), 최적 학습률은 다음과 같다. :\mu_{opt}=\frac{E\left[\left|y(n)-\hat{y}(n)\right|^2\right]}{E\left[|e(n)|^2\right]} 위 결과는 신호 v(n)과 x(n)이 서로 상관 관계가 없다고 가정하며, 이는 일반적으로 실제로 그렇다.
## 증명
필터 불일치를 \Lambda(n) = \left| \mathbf{h}(n) - \hat{\mathbf{h(n) \right|^2로 정의하면, 다음 샘플에 대한 예상 불일치는 다음과 같이 유도할 수 있다. : E\left[ \Lambda(n+1) \right] = E\left[ \left| \hat{\mathbf{h(n) + \frac{\mu\,e^{*}(n)\mathbf{x}(n)}{\mathbf{x}^H(n)\mathbf{x}(n)} - \mathbf{h}(n) \right|^2 \right] : E\left[ \Lambda(n+1) \right] = E\left[ \left| \hat{\mathbf{h(n) + \frac{\mu\, \left( v^*(n)+y^*(n)-\hat{y}^*(n) \right) \mathbf{x}(n)}{\mathbf{x}^H(n)\mathbf{x}(n)} - \mathbf{h}(n) \right|^2 \right] \mathbf{\delta}=\hat{\mathbf{h(n)-\mathbf{h}(n) 및 r(n) = \hat{y}(n)-y(n)라고 하자. : E\left[ \Lambda(n+1) \right] = E\left[ \left| \mathbf{\delta}(n) - \frac{\mu\, \left( v(n)+r(n) \right) \mathbf{x}(n)}{\mathbf{x}^H(n)\mathbf{x}(n)} \right|^2 \right] : E\left[ \Lambda(n+1) \right] = E\left[ \left( \mathbf{\delta}(n) - \frac{\mu\, \left( v(n)+r(n) \right) \mathbf{x}(n)}{\mathbf{x}^H(n)\mathbf{x}(n)} \right)^H \left( \mathbf{\delta}(n) - \frac{\mu\, \left( v(n)+r(n) \right) \mathbf{x}(n)}{\mathbf{x}^H(n)\mathbf{x}(n)} \right) \right] 독립성을 가정하면 다음을 얻는다. : E\left[ \Lambda(n+1) \right] = \Lambda(n) + E\left[ \left( \frac{\mu\, \left( v(n)+r(n) \right) \mathbf{x}(n)}{\mathbf{x}^H(n)\mathbf{x}(n)} \right)^H \left( \frac{\mu\, \left( v(n)+r(n) \right) \mathbf{x}(n)}{\mathbf{x}^H(n)\mathbf{x}(n)} \right) \right] - 2 E\left[\frac{\mu|r(n)|^2}{\mathbf{x}^H(n)\mathbf{x}(n)}\right] : E\left[ \Lambda(n+1) \right] = \Lambda(n) + \frac{\mu^2 E\left[|e(n)|^2\right]}{\mathbf{x}^H(n)\mathbf{x}(n)} - \frac{2 \mu E\left[|r(n)|^2\right]}{\mathbf{x}^H(n)\mathbf{x}(n)} 최적 학습률은 \frac{dE\left[ \Lambda(n+1) \right]}{d\mu} = 0 에서 발견되며, 이는 다음으로 이어진다. : 2 \mu E\left[|e(n)|^2\right] - 2 E\left[|r(n)|^2\right] = 0 : \mu = \frac{E\left[|r(n)|^2\right]}{E\left[|e(n)|^2\right]}