재귀 최소제곱

1. 개요

재귀 최소제곱 Recursive Least Squares (RLS)
푸는 것	데이터가 하나씩 들어오는 선형 최소제곱의 온라인 갱신
핵심 도구	셔먼-모리슨 공식 (랭크-1 역행렬 갱신)
계산량	샘플당 O(n²), 메모리 O(n²)
조절 손잡이	망각 인자 λ, 초기 공분산 P0 = δ−1I
친척	칼만 필터 (상수 상태판) · LMS (기울기 근사판)

데이터가 한 줄 들어올 때마다 정규방정식을 처음부터 다시 푸는 건 현생 낭비다. 어제의 답에 오늘의 오차만 더하면 된다.

재귀 최소제곱(recursive least squares, RLS)은 선형 모형 $y_k = \mathbf x_k^{\mathsf T}\boldsymbol\theta + v_k$ 의 최소자승 추정치 $\hat{\boldsymbol\theta}$ 를, 새 관측 $(\mathbf x_k, y_k)$ 가 들어올 때마다 이전 추정치에 예측 오차 × 이득을 더하는 방식으로 갱신하는 알고리즘이다. 정규방정식 행렬에 랭크-1 항이 더해질 뿐이라는 점을 셔먼-모리슨 공식으로 이용해, 매 샘플 $O(n^3)$ 대신 $O(n^2)$ 으로 배치 최소제곱과 같은 답을 낸다.

여기에 오래된 데이터를 지수적으로 잊는 망각 인자 $\lambda$ 를 넣으면, 천천히 변하는 파라미터를 실시간으로 따라가는 추정기가 된다. 적응 필터·에코 제거·온라인 시스템 식별·자기 동조 제어기의 표준 부품이다. 현대적 형태는 플래킷(Plackett, 1950)의 정리로 거슬러 올라가며, 사실상 칼만 필터의 가장 단순한 특수형이다.

2. 유도

망각 인자 $0<\lambda\le1$ 을 넣은 가중 비용

$$J_k(\boldsymbol\theta) = \sum_{i=1}^{k} \lambda^{k-i}\,\bigl(y_i - \mathbf x_i^{\mathsf T}\boldsymbol\theta\bigr)^2$$

을 최소화하는 해는 $R_k \hat{\boldsymbol\theta}_k = \mathbf r_k$, 여기서 $R_k = \lambda R_{k-1} + \mathbf x_k\mathbf x_k^{\mathsf T}$, $\mathbf r_k = \lambda\mathbf r_{k-1} + \mathbf x_k y_k$ 이다. $P_k = R_k^{-1}$ 로 두고 셔먼-모리슨을 적용하면 역행렬을 다시 구할 필요 없이

$$\mathbf g_k = \frac{P_{k-1}\mathbf x_k}{\lambda + \mathbf x_k^{\mathsf T} P_{k-1}\mathbf x_k},$$ $$\hat{\boldsymbol\theta}_k = \hat{\boldsymbol\theta}_{k-1} + \mathbf g_k\bigl(y_k - \mathbf x_k^{\mathsf T}\hat{\boldsymbol\theta}_{k-1}\bigr),$$ $$P_k = \frac{1}{\lambda}\bigl(P_{k-1} - \mathbf g_k \mathbf x_k^{\mathsf T} P_{k-1}\bigr)$$

의 세 줄이 나온다. 괄호 안 $e_k = y_k - \mathbf x_k^{\mathsf T}\hat{\boldsymbol\theta}_{k-1}$ 은 선험 예측 오차(새 데이터를 보기 전 추정치로 예측한 오차)이고, 이득 $\mathbf g_k$ 는 “지금 불확실한 방향일수록 크게 고친다”는 뜻을 담는다. 분모가 스칼라라 나눗셈 한 번이면 되고, 행렬-벡터 곱과 외적만 남아 샘플당 $O(n^2)$ 이다.

2.1. 초기화는 숨은 정규화다

$R_0$ 이 없으므로 보통 $P_0 = \delta^{-1} I$ ($\delta$ 작음), $\hat{\boldsymbol\theta}_0 = \mathbf 0$ 으로 시작한다. 이것은 아무 의미 없는 시작값이 아니라, 비용에 $\lambda^k\delta\lVert\boldsymbol\theta\rVert^2$ 를 더한 것과 정확히 같다. 즉 RLS 는 처음부터 능형회귀를 하고 있고, 그 벌점이 $\lambda^k$ 로 사라져 갈 뿐이다.

검산. 3차원 파라미터, 잡음 표준편차 0.1, $\lambda=1$ 로 처음 20개 샘플만 넣은 뒤 배치 최소제곱 해와의 최대 차이를 쟀다.

$\delta$	20 샘플 후 배치 LS 와의 차이
$10^{-6}$	$6\times10^{-8}$
$10^{-2}$	$6\times10^{-4}$
$1$	$0.056$
$100$	$0.82$

$\delta$ 를 크게(= $P_0$ 를 작게) 잡으면 “처음엔 0 이 정답일 것”이라는 사전 믿음이 강해져 초반 추정이 0 쪽으로 끌린다. 500 샘플을 다 넣으면 $\delta=10^{-6}$ 에서 배치 해와의 차이는 $2\times10^{-9}$ 까지 줄었다. 반대로 $\delta$ 를 극단적으로 작게 잡으면 첫 몇 스텝의 $P$ 가 거대해 반올림 오차가 커지니, “데이터 규모 대비 아주 약한 사전”을 고르는 게 요령이다.

3. 망각 인자와 추적

$\lambda<1$ 이면 $i$ 스텝 전 데이터의 가중치가 $\lambda^{i}$ 라, 유효 기억 길이는 대략 $1/(1-\lambda)$ 샘플이다. 파라미터가 시점 250 에서 갑자기 바뀌는 문제(잡음 0.1)로 추적 성능을 쟀다. “회복”은 추정 오차 노름이 0.05 아래로 10 샘플 연속 유지된 첫 시점이다.

$\lambda$	기억 길이	점프 후 회복	정상상태 오차 (샘플 400~500 평균)
1	∞	못 함	0.99
0.99	100	250 샘플 안에 못 함	0.23
0.95	20	81 샘플	0.028
0.9	10	37 샘플	0.040

$\lambda=1$ 은 과거 250 개와 새 데이터를 똑같이 믿어 영원히 두 파라미터의 중간쯤에 머문다. $\lambda$ 를 줄이면 빨리 따라가지만 적은 샘플로 추정하는 셈이라 정상상태 잡음이 커진다($\lambda=0.9$ 가 $0.95$ 보다 오차가 크다). 추적 속도와 잡음 민감도의 교환이고, 최적 $\lambda$ 는 파라미터가 변하는 속도와 잡음 크기의 비가 정한다.

4. 칼만 필터와의 관계

상태가 변하지 않는 계 $\boldsymbol\theta_k = \boldsymbol\theta_{k-1}$ (과정 잡음 $Q=0$)에 관측 $y_k = \mathbf x_k^{\mathsf T}\boldsymbol\theta_k + v_k$ 를 붙인 칼만 필터를 쓰면, 관측 잡음 분산을 1로 둔 경우 갱신식이 $\lambda=1$ 인 RLS 와 한 글자도 안 다르다. $P_k$ 는 추정 오차 공분산(을 잡음 분산으로 나눈 것)이다.

$\lambda<1$ 은 매 스텝 $P$ 를 $1/\lambda$ 배 부풀리는 것이니, 칼만 필터 쪽에서 보면 과정 잡음을 넣거나 앙상블 칼만 필터의 공분산 팽창을 거는 것과 같은 정신이다. 차이는 RLS 가 “파라미터가 어떻게 변하는지” 모형을 갖지 않고 그냥 잊는다는 것뿐이다. 변화의 모형(랜덤워크 분산 등)을 알면 칼만 필터가 더 낫고, 모르면 $\lambda$ 하나로 버티는 RLS 가 다루기 쉽다.

5. 수치적 함정

5.1. 대칭성 붕괴

위 $P_k$ 갱신은 대칭 행렬에서 대칭 행렬을 빼는 식이지만 부동소수점에서는 대칭이 조금씩 깨지고, 그 오차가 $1/\lambda$ 로 매 스텝 증폭된다. 실제로 위 추적 실험을 $\lambda=0.9$, $\delta=10^{-6}$ 으로 그대로 돌리면 $P$ 의 최소 고유값이 $-3\times10^{12}$ 까지 내려가 양정치성을 잃고 추정치가 발산했다(정상상태 오차 13). 매 스텝 $P \leftarrow (P+P^{\mathsf T})/2$ 로 대칭화 한 줄만 넣자 같은 조건에서 정상상태 오차 0.040 으로 멀쩡해졌다.

진지한 구현은 더 나아가 다음을 쓴다.

• 제곱근형·QR-RLS. $P$ 대신 그 촐레스키 인자나 데이터 행렬의 QR 분해 인자를 기븐스 회전으로 갱신한다. 조건수가 제곱되는 것을 피하고 양정치성이 구조적으로 보장된다.
• 격자형·고속 횡단 필터. 입력이 시계열의 지연 벡터 $(u_k, u_{k-1}, \dots)$ 이면 시프트 구조를 이용해 $O(n)$ 으로 줄일 수 있다. 대신 수치적으로 더 예민하다.

5.2. 와인드업

$\lambda<1$ 인데 입력이 어떤 방향으로 여기되지 않으면(예: 입력이 한동안 상수), 그 방향으로는 새 정보가 없는데 $P$ 는 매 스텝 $1/\lambda$ 배 커진다. 검산하면 2차원에서 입력이 한 축에만 있을 때 $\lambda=0.95$ 로 200 스텝 뒤 다른 축의 $P$ 성분이 $0.95^{-200}\approx2.9\times10^4$ 로 정확히 불어났다. 이 상태에서 여기가 돌아오면 이득이 거대해 추정치가 크게 튄다. 공분산 상한 클램프, 여기된 방향만 잊는 방향성 망각, $P$ 의 대각합을 일정하게 유지하는 정규화 등이 처방이다.¹

6. LMS 와의 비교

적응 필터에서 RLS 의 라이벌은 LMS 필터다. LMS 는 $\hat{\boldsymbol\theta}_k = \hat{\boldsymbol\theta}_{k-1} + \mu\,\mathbf x_k e_k$ — RLS 의 $P_{k-1}$ 자리에 스칼라 $\mu$ 를 넣은 확률적 경사하강이다. 샘플당 $O(n)$ 이라 싸지만, 입력 자기상관 행렬의 고유값이 퍼져 있으면(유색 입력) 수렴이 그 조건수만큼 느려진다. RLS 는 $P$ 가 입력 상관을 미리 “백색화”해 주므로 수렴 속도가 입력 통계와 거의 무관하고 대략 $2n$ 샘플이면 자리를 잡는다. 탭 수 수천의 음향 에코 제거기는 LMS 계열(NLMS 등)을, 파라미터 몇 개짜리 플랜트 식별·배터리 상태 추정은 RLS 를 쓰는 게 대체적인 분업이다.²

7. 관련 문서

• 최소자승법 · 셔먼-모리슨 공식 · 능형회귀 · 총최소제곱
• 칼만 필터 · 앙상블 칼만 필터 · 시스템 식별 · 디지털 필터
• QR 분해 · 촐레스키 분해 · 조건수
• LMS 필터 · 적응 필터 · 적응 제어

8. Footnotes

1. 제어 쪽 사람들은 적분기 와인드업과 이름이 같아서 처음엔 헷갈려 한다. 둘 다 “아무 일도 안 일어나는 동안 뭔가가 몰래 쌓인다”는 점에서 같은 병이다. ↩

2. 같은 문제를 두고 RLS 는 $O(n^2)$ 으로 똑똑하게, LMS 는 $O(n)$ 으로 우직하게 푼다. 탭이 4096개면 우직함이 이긴다. 현생의 메모리와 전력은 유한하다. ↩