LMS 필터

1. 개요

LMS 필터 Least Mean Squares Filter
갱신식	w ← w + μ e x
비용	샘플당 곱셈 약 2N (N = 탭 수)
목표	평균제곱오차 E[e²] 최소화 (위너 해)
제안	위드로·호프, 1960 (ADALINE)
대표 변형	NLMS · 부호 LMS · 누설 LMS · FxLMS

행렬도 역행렬도 없다. 오차에 입력을 곱해서 가중치에 조금 더한다. 그게 전부인데 60년 넘게 전화기·이어폰·모뎀 안에서 돌아가고 있다.

LMS 필터(least mean squares filter)는 FIR 필터의 탭 가중치 $\mathbf w$ 를, 원하는 신호 $d_k$ 와 필터 출력 $y_k = \mathbf w^{\mathsf T}\mathbf x_k$ 의 오차 $e_k = d_k - y_k$ 를 써서 샘플마다

$$\mathbf w_{k+1} = \mathbf w_k + \mu\, e_k\, \mathbf x_k$$

로 갱신하는 적응 필터 알고리즘이다. 평균제곱오차 $J(\mathbf w) = \mathrm E[e_k^2]$ 의 기울기를 샘플 하나로 추정해 내려가는 확률적 경사하강법 그 자체이고, 1960년 스탠퍼드의 버나드 위드로와 대학원생 테드 호프가 적응 뉴런 ADALINE 을 학습시키려고 만들었다.¹

샘플당 $O(N)$ 이라 탭이 수천 개인 음향 에코 제거기도 실시간으로 돈다. 대신 수렴 속도가 입력 신호의 통계에 강하게 휘둘린다. 이 문서는 그 거래 — 스텝 크기 $\mu$ 하나가 수렴 속도·정상상태 오차·안정성을 동시에 정하는 구조 — 를 실험 수치와 함께 정리한다. 같은 문제를 $O(N^2)$ 으로 똑똑하게 푸는 쪽은 재귀 최소제곱이다.

2. 위너 해와 기울기

입력 자기상관 $R = \mathrm E[\mathbf x\mathbf x^{\mathsf T}]$, 교차상관 $\mathbf p = \mathrm E[d\,\mathbf x]$ 라 하면

$$J(\mathbf w) = \sigma_d^2 - 2\mathbf p^{\mathsf T}\mathbf w + \mathbf w^{\mathsf T} R\,\mathbf w$$

는 $\mathbf w$ 의 이차식이고, 최소점은 위너 해 $\mathbf w_\star = R^{-1}\mathbf p$ 다(위너 필터). 기울기 $\nabla J = -2(\mathbf p - R\mathbf w)$ 를 따라 정확한 최급강하를 하려면 $R$ 과 $\mathbf p$ 를 알아야 한다. LMS 는 기댓값을 지우고 순간값 $\mathbf x_k\mathbf x_k^{\mathsf T}$, $d_k\mathbf x_k$ 로 바꿔 $\nabla J \approx -2e_k\mathbf x_k$ 를 쓴다. 계수 2는 $\mu$ 에 흡수했다(교재에 따라 $2\mu$ 로 쓰니 안정 조건을 옮길 때 주의).

이 추정은 매 샘플 잡음투성이지만 불편이다. 그래서 $\mu$ 가 작으면 가중치는 평균적으로 최급강하 궤적을 따라가고, 잡음은 가중치가 최적점 근처에서 떠는 정도로 남는다.

3. 수렴 속도 — 고유값이 정한다

평균 가중치 오차 $\mathrm E[\mathbf w_k] - \mathbf w_\star$ 를 $R$ 의 고유벡터로 풀면 모드마다

$$v_{i,k+1} = (1 - \mu\lambda_i)\, v_{i,k}$$

로 독립적으로 줄어든다. 따라서

• 평균이 수렴할 조건은 $0 < \mu < 2/\lambda_{\max}$,
• 모드 $i$ 의 시정수는 대략 $\tau_i \approx 1/(\mu\lambda_i)$ 샘플,
• 가장 느린 모드는 $\lambda_{\min}$ 이 정한다.

$\mu$ 는 $\lambda_{\max}$ 에 막혀 위로 못 키우고, 그 $\mu$ 로 $\lambda_{\min}$ 모드를 끌어내려야 한다. 결국 수렴 시간은 고유값 퍼짐 $\lambda_{\max}/\lambda_{\min}$, 즉 $R$ 의 조건수에 비례한다. 백색 입력($R = \sigma_x^2 I$)이 이상적이고, 저역통과된 음성처럼 상관이 센 입력이 최악이다.

4. 정상상태 — 오조정과 진짜 안정 한계

$\mu$ 가 0이 아니면 가중치는 수렴한 뒤에도 기울기 잡음 때문에 떤다. 그만큼 MSE 가 위너 최소값 $J_{\min}$ 보다 커지고, 그 초과분의 비율을 오조정(misadjustment) $M = (J_\infty - J_{\min})/J_{\min}$ 이라 한다. $\mu$ 가 작을 때

$$M \approx \frac{\mu}{2}\,\mathrm{tr}(R)$$

이다. 빠르게 수렴시키려 $\mu$ 를 키우면 정상상태가 정확히 그만큼 시끄러워진다. 이게 LMS 설계의 기본 거래다.

4.1. 검산 — 8탭 시스템 식별

미지의 8탭 FIR $\mathbf h = (0.5, -0.3, 0.2, 0.1, -0.05, 0.02, 0.01, -0.01)$ 을 단위분산 백색 가우스 입력으로 들뜨게 하고, 출력에 분산 $0.01$ 의 측정 잡음을 얹었다. 이때 $J_{\min} = 0.01$, $\mathrm{tr}(R) = 8$ 이다. 60000 샘플을 돌리고 뒤쪽 절반의 평균 $e^2$ 로 $M$ 을 쟀다.

$\mu$	작은 $\mu$ 근사 $\mu N/2$	가우스 보정식	실측 $M$
0.005	0.020	0.020	0.018
0.01	0.040	0.042	0.039
0.05	0.20	0.27	0.26
0.1	0.40	0.80	0.85
0.2	0.80	발산 경계	수백만 배로 폭주
0.25	—	—	726 샘플째 발산

작은 $\mu$ 에서는 근사가 잘 맞지만 0.05부터 어긋난다. 오른쪽에서 두 번째 열은 백색 가우스 입력에서 알려진 보정식

$$M = \frac{\mu N\sigma_x^2/2}{1 - \mu (N+2)\sigma_x^2/2}$$

이고, 실측과 잘 맞는다. 분모가 0이 되는 $\mu = 2/\big((N+2)\sigma_x^2\big) = 0.2$ 가 평균제곱 안정 한계다. 평균 수렴 조건 $\mu < 2/\lambda_{\max} = 2$ 는 열 배나 느슨해서 실전에선 아무 의미가 없다 — 평균이 수렴해도 분산이 터진다. 실무 국룰이 ”$\mu < 2/\mathrm{tr}(R)$ 보다 한참 작게”인 이유다.²

수렴 시간도 확인했다. 가중치 오차 $\lVert\mathbf w - \mathbf h\rVert^2 < 10^{-3}$ 까지 $\mu=0.01$ 은 324 샘플, $\mu=0.005$ 는 679 샘플로, 시정수 $1/(\mu\lambda)$ 대로 $\mu$ 에 반비례했다.

5. 유색 입력과 NLMS

같은 실험에서 입력을 상관계수 $\rho = 0.9$ 의 1차 자기회귀 신호(분산은 1로 유지)로 바꿨다. 이 입력의 자기상관 행렬은 고유값 퍼짐 상한이 $\big((1+\rho)/(1-\rho)\big)^2 = 361$ 이다. $\mu = 0.01$ 에서 수렴 시간이 324 → 4756 샘플로 약 15배 늘었다. 오조정은 $\mathrm{tr}(R)$ 만 보므로 0.041로 거의 그대로다. 정상상태는 멀쩡한데 거기까지 가는 길만 길어진 것이다.

NLMS(정규화 LMS)는 스텝을 입력 에너지로 나눈다.

$$\mathbf w_{k+1} = \mathbf w_k + \frac{\tilde\mu}{\delta + \lVert\mathbf x_k\rVert^2}\, e_k\,\mathbf x_k,\qquad 0 < \tilde\mu < 2$$

입력 크기가 수시로 바뀌는 음성에서 $\mu$ 를 따로 맞출 필요가 없어지고, 안정 범위가 입력 통계와 무관한 $(0, 2)$ 로 고정된다. 그래서 실제 에코 제거기의 기본형은 거의 NLMS 다. 같은 8탭 문제에서 $\tilde\mu = 0.5$ 는 백색 입력 234 샘플, 오조정 0.41이었다.

하지만 NLMS 도 스케일만 맞출 뿐 방향은 못 고친다. $\rho = 0.9$ 입력에서는 6603 샘플이 걸렸다. 고유값 퍼짐을 진짜로 없애려면 입력을 백색화해야 하고, 그 방법이 $R^{-1}$ 을 재귀적으로 추적하는 재귀 최소제곱(샘플당 $O(N^2)$), 혹은 그 중간인 아핀 사영 알고리즘·주파수 영역 블록 LMS 다.

6. 변형과 쓰임새

• 부호 LMS 류. $e_k$ 나 $\mathbf x_k$ 대신 부호만 쓴다. 곱셈이 비트 연산이 되니 초기 하드웨어 모뎀과 ADPCM 음성 부호화(ITU-T G.726 의 적응 예측기)에 들어갔다. 수렴은 느려진다.
• 누설 LMS. $\mathbf w_{k+1} = (1 - \mu\gamma)\mathbf w_k + \mu e_k\mathbf x_k$. 입력이 일부 방향으로 들뜨지 않을 때 가중치가 그 방향으로 표류하는 걸 막는다. 정확히 능형회귀의 확률적 버전이다.
• FxLMS. 능동 소음 제어에서 스피커 → 오차 마이크 사이의 2차 경로를 거친 기준 신호로 갱신한다. 노이즈 캔슬링 이어폰의 기본 골격이다.
• 채널 등화. 모뎀·무선 수신기가 알려진 훈련 열로 등화기를 맞추고, 이후엔 결정된 심벌로 계속 추적한다(결정 지향 모드).

이론적으로도 대접을 받는다. LMS 는 모형 오차·잡음의 통계를 전혀 가정하지 않는 최악 기준($H^\infty$)에서 최적인 알고리즘이라는 결과가 있다(하시비·사예드·카일라스, 1996). RLS 와 칼만 필터가 가우스 가정 아래 평균적으로 최적이라면, LMS 는 가정이 틀렸을 때 덜 망하는 쪽의 최적이다. 현장에서 오래 살아남은 이유 중 하나다.³

7. 관련 문서

• 재귀 최소제곱 · 확률적 경사하강법 · 칼만 필터 · 디지털 필터
• 위너 필터 · 적응 필터 · 음향 에코 제거 · 능동 소음 제어
• 조건수 · 능형회귀

8. Footnotes

1. 테드 호프는 이후 인텔로 가서 최초의 상용 마이크로프로세서 4004 설계를 이끈 사람 중 하나가 된다. 대학원 때 만든 알고리즘과 회사에서 만든 칩이 지금 같은 이어폰 안에 같이 들어 있다. ↩

2. 평균만 보고 “2/λ_max 까지 괜찮다”고 짜면 시뮬레이션 첫날 NaN 을 본다. 기댓값이 수렴한다는 것과 한 번의 실현이 멀쩡하다는 건 다른 이야기다. 통계 수업에서 졸면 이렇게 된다. ↩

3. 똑똑한 알고리즘은 가정이 맞을 때 빛나고, 우직한 알고리즘은 가정이 틀렸을 때 빛난다. 현장의 가정은 대개 틀려 있다. ↩