13회 · 최소제곱 · 노트

8 오늘의 최소제곱 — 경사하강과 weight decay

신경망의 선형층 nn.Linear에 평균제곱오차를 손실로 붙이면 그것이 최소제곱이다. 다른 것은 푸는 방법뿐이다. 정규방정식이나 QR 대신 경사하강을 쓴다. 이 절은 그 차이가 무엇을 낳는지 본다.

8.1 경사하강의 속도는 조건수가 정한다

정리 8.1 (최소제곱의 경사하강) $L(\bw)=\tfrac1{2n}\|\y-X\bw\|^2$, $A=X\T X/n$이고 $\rank X=p$라 하자. $A$의 고유값을 $0<\mu_{\min}\le\dots\le\mu_{\max}$, $\kappa=\mu_{\max}/\mu_{\min}$이라 하고 학습률 $\eta=1/\mu_{\max}$로 $\bw_{k+1}=\bw_k-\eta\nabla L(\bw_k)$를 되풀이하면

$$\bw_k-\bhat=(I-\eta A)^k(\bw_0-\bhat),\qquad \|\bw_k-\bhat\|\le\Bigl(1-\frac1\kappa\Bigr)^k\|\bw_0-\bhat\| .$$

오차를 $\epsilon$배로 줄이는 데 대략 $\kappa\log(1/\epsilon)$번이 든다.

증명 $\nabla L(\bw)=A\bw-X\T\y/n$이고 정규방정식으로 $X\T\y/n=A\bhat$이므로 $\nabla L(\bw)=A(\bw-\bhat)$이다. 따라서 $\bw_{k+1}-\bhat=(I-\eta A)(\bw_k-\bhat)$. 대칭행렬 $I-\eta A$의 고유값은 $1-\mu_i/\mu_{\max}\in[0,\allowbreak \ 1-1/\kappa]$이므로 그 노름은 $1-1/\kappa$ 이하다. $(1-1/\kappa)^k\le e^{-k/\kappa}$에서 마지막 문장이 나온다.

예제 8.2 (Galton을 경사하강으로) $X=[\one,\ \text{부모 키}]$의 $\kappa$는 $6.8\times10^6$이다(2절). 원점에서 출발해 상대오차 $10^{-3}$에 이르려면 4,721만 번의 반복이 든다. 부모 키에서 평균을 빼면 $\kappa=3.19$이고 19번이면 된다(그림 8.1 왼쪽). 상수 열과 거의 평행한 열이 손실 함수의 등고선을 길쭉한 골짜기로 만들고, 경사하강은 골짜기의 벽 사이를 오가며 바닥을 따라 아주 느리게 내려간다. 입력을 표준화하는 것, 신경망의 배치 정규화(5회 6절의 백색화)는 이 골짜기를 둥글게 만드는 일이다.

8.2 모수가 관측보다 많으면 — 최소노름 해

$p>n$이면 $\rank X<p$이고 정규방정식의 해가 무수히 많다. 그 해들은 모두 자료를 완벽히 맞춘다(잔차 0). 경사하강은 그 가운데 어느 것을 고르나?

정리 8.3 (경사하강은 최소노름 해로 간다) $\bw_0=\bzero$에서 출발해 $0<\eta<2/\mu_{\max}$로 경사하강을 하면 $\bw_k$는 정규방정식의 해 가운데 노름이 가장 작은 것 $\bw^\dagger$로 수렴한다.

증명 

1. 행공간에 머문다. $\nabla L(\bw)=X\T(X\bw-\y)/n\in\col(X\T)$이므로 $\bw_0=\bzero$에서 시작한 $\bw_k$는 모두 $\col(X\T)$에 있다.

2. 행공간의 해는 하나이고 노름이 최소다. 해 하나를 $\bw^*$라 하면 해 전체는 $\bw^*+\mathrm{null}(X)$이다. $\R^p=\col(X\T)\oplus\mathrm{null}(X)$ (직교 분해)로 $\bw^*=\bw^\dagger+\bw_n$이라 쓰면 $X\bw_n=\bzero$이므로 $\bw^\dagger$도 해이고, 행공간에 있는 해는 이것 하나다(두 해의 차는 $\mathrm{null}(X)\cap\col(X\T)=\{\bzero\}$에 있다). 아무 해 $\bw=\bw^\dagger+\bv$ ($\bv\in\mathrm{null}(X)$)에 대해 $\|\bw\|^2=\|\bw^\dagger\|^2+\|\bv\|^2$이다.

3. 수렴. 정리 8.1의 증명처럼 $\bw_{k+1}-\bw^\dagger=(I-\eta A)(\bw_k-\bw^\dagger)$이고 $\bw_k-\bw^\dagger\in\col(X\T)$이다. $A$는 $\col(X\T)$를 자기 자신으로 보내고, 거기서의 고유값은 양수 $\mu_i\le\mu_{\max}$이므로 $I-\eta A$의 고유값 $1-\eta\mu_i$는 절댓값이 1보다 작다. 따라서 $\bw_k\to\bw^\dagger$.

$\bw^\dagger=X^+\y$ ($X^+$는 Moore–Penrose 역행렬)이다. 아무도 노름을 작게 하라고 시키지 않았는데 경사하강이 스스로 그렇게 한다. 이것을 암묵적 정칙화라 부른다. 모수가 자료보다 훨씬 많은 오늘의 신경망이 왜 자료를 외우면서도 새 자료에서 망가지지 않는지 설명하려는 연구가 이 정리에서 출발했다.

8.3 Ridge와 weight decay

정의 8.4 (Ridge 추정량) $\lambda>0$에 대해 $\|\y-X\bb\|^2+\lambda\|\bb\|^2$을 최소로 하는

$$\bhat_\lambda=(X\T X+\lambda I)^{-1}X\T\y$$

를 ridge 추정량이라 한다(Hoerl–Kennard 1970). 상수항은 벌점에서 빼는 것이 보통이어서 설명변수와 반응을 중심화한 뒤에 쓴다.

$X\T X+\lambda I$는 언제나 양정치이므로 $p>n$이어도, 공선성이 심해도 해가 하나로 정해진다. 신경망에서 손실에 $\tfrac\lambda2\|\bw\|^2$을 더하는 것을 weight decay라 부른다. 경사하강 한 걸음이 $\bw\leftarrow(1-\eta\lambda)\bw-\eta\nabla L(\bw)$, 곧 매번 가중치를 조금씩 줄이는 꼴이기 때문이다. 손실이 제곱오차이면 그 고정점이 ridge 해다(연습 8.1).

명제 8.5 (ridge는 방향마다 줄인다) $X=UDV\T$를 특이값 분해($d_1\ge\dots\ge d_p>0$)라 하면

$$\bhat_\lambda=\sum_{j=1}^p\frac{d_j^2}{d_j^2+\lambda}\cdot\frac{\bu_j\T\y}{d_j}\,\bv_j,\qquad \bhat=\sum_{j=1}^p\frac{\bu_j\T\y}{d_j}\,\bv_j .$$

최소제곱 해의 성분을 방향 $\bv_j$마다 $d_j^2/(d_j^2+\lambda)$배로 줄인다. 특이값이 작은 방향, 곧 자료가 정보를 적게 가진 방향을 가장 많이 줄인다.

증명 $X\T X+\lambda I=V(D^2+\lambda I)V\T$, $X\T\y=VDU\T\y$이므로 $\bhat_\lambda=V(D^2+\lambda I)^{-1}DU\T\y$이다. 성분으로 쓰면 위의 식이고, $\lambda=0$이 최소제곱이다.

정리 8.6 (Hoerl–Kennard (1970)) 정의 1.1의 모형에서 $0<\lambda<\sigma^2/\max_j\vartheta_j^2$이면 ($\boldsymbol\vartheta=V\T\bbeta$)

$$E\|\bhat_\lambda-\bbeta\|^2<E\|\bhat-\bbeta\|^2 .$$

치우친 ridge 추정량이 BLUE를 평균제곱오차에서 이기는 $\lambda$가 언제나 있다.

증명 $V$로 돌려도 노름은 같으므로 $\boldsymbol\vartheta=V\T\bbeta$의 좌표에서 계산한다. 최소제곱의 $j$번째 성분 $\hat\vartheta_j=\bu_j\T\y/d_j$는 평균 $\vartheta_j$, 분산 $\sigma^2/d_j^2$이고, ridge의 성분은 $c_j\hat\vartheta_j$, $c_j=d_j^2/(d_j^2+\lambda)$이다. 분산과 치우침의 제곱을 더하면

$$M(\lambda)=E\|\bhat_\lambda-\bbeta\|^2=\sum_{j=1}^p\frac{\sigma^2d_j^2+\lambda^2\vartheta_j^2}{(d_j^2+\lambda)^2},\qquad M'(\lambda)=\sum_{j=1}^p\frac{2d_j^2(\lambda\vartheta_j^2-\sigma^2)}{(d_j^2+\lambda)^3}$$

이다. $0<\lambda<\sigma^2/\max\vartheta_j^2$이면 모든 항이 음수이므로 $M$은 $[0,\lambda]$에서 감소하고, $M(\lambda)<M(0)=E\|\bhat-\bbeta\|^2$이다.

예제 8.7 (공선성 자료의 ridge) 예제 7.5의 표본(중심화)에서 $X$의 두 특이값은 13.56과 0.366이다. $\lambda$를 0, 1, 10으로 올리면 $(\hat\beta_1,\hat\beta_2)$는 $(4.71,\allowbreak -2.87)\to(1.36,\allowbreak 0.47)\to(0.93,\allowbreak 0.82)$로 참값 $(1,1)$ 쪽으로 모인다(그림 8.1 오른쪽). 줄어드는 것은 거의 전부 작은 특이값의 방향 $\bv_2\approx(1,-1)/\sqrt2$, 곧 “두 계수의 차”다. 합의 방향은 거의 건드리지 않는다. 이 설계에서 $\sigma=1$, $\bbeta=(1,1)$이면 최소제곱의 평균제곱오차는 7.47이고 ridge는 $\lambda\approx7$에서 0.010으로, 700배 작다. $\bbeta$가 거의 전부 큰 특이값의 방향에 있어서 작은 방향을 줄이는 대가(치우침)가 거의 없기 때문이다.

가정 주의 최적의 $\lambda$는 모르는 $\bbeta$에 의존한다(연습 3.5의 $c$와 같다). 실무에서는 교차검증으로 고른다. 16회에서 Stein은 정규 평균 세 개 이상을 동시에 추정할 때, $\bbeta$와 무관하게 언제나 최소제곱을 이기는 축소 추정량이 있음을 보인다.

그림 8.1 왼쪽: Galton 자료의 경사하강. 원래의 부모 키($\kappa=6.8\times10^6$, 주황)로는 오차가 거의 줄지 않고, 중심화하면($\kappa=3.19$, 파랑) 100번쯤에 기계 정밀도에 이른다. 점선은 정리 8.1의 상계 $(1-1/\kappa)^k$이다. 오른쪽: 공선성 자료의 ridge 경로. $\lambda$가 커지면 두 계수가 참값 1(회색 점선) 근처로 모이고, 합(빨강 점선)은 $\lambda\approx10$까지 거의 그대로다.

연습문제

연습 8.1 (덧붙인 자료 ★) (a) $\tilde X=\smat{X\\ \sqrt\lambda I_p}$, $\tilde\y=\smat{\y\\ \bzero}$로 최소제곱을 하면 ridge 해가 나옴을 보여라. (b) weight decay를 붙인 경사하강 $\bw\leftarrow(1-\eta\lambda)\bw-\eta X\T(X\bw-\y)$의 고정점이 $\bhat_\lambda$임을 보여라.

풀이

(a) $\tilde X\T\tilde X=X\T X+\lambda I$, $\tilde X\T\tilde\y=X\T\y$이므로 정규방정식이 ridge의 식이다. (b) 고정점에서 $\bw=(1-\eta\lambda)\bw-\eta X\T(X\bw-\y)$이므로 $\lambda\bw=-X\T(X\bw-\y)$, 곧 $(X\T X+\lambda I)\bw=X\T\y$.

연습 8.2 (두 점, 세 모수 ★★) $X=\smat{1&0&1\\0&1&1}$, $\y=(1,1)\T$이다. 정규방정식의 해 전체를 쓰고, 그 가운데 노름이 가장 작은 해가 $(1/3,1/3,2/3)$임을 보여라. 원점에서 출발한 경사하강이 이 해로 가는 것을 정리 8.3으로 설명하라.

풀이

$\rank X=2=n$이므로 정규방정식의 해는 $X\bw=\y$의 해, 곧 $w_1+w_3=1$, $w_2+w_3=1$이다. 해 전체는 $(1-t,1-t,t)$이고 노름의 제곱 $2(1-t)^2+t^2$은 $t=2/3$에서 최소다. 해 $(1/3,\allowbreak 1/3,\allowbreak 2/3)=\tfrac13(1,\allowbreak 0,\allowbreak 1)+\tfrac13(0,\allowbreak 1,\allowbreak 1)$은 $X$의 행공간에 있다. 원점에서 시작한 경사하강은 행공간을 떠나지 않으므로(정리 8.3의 1단계) 그 안의 유일한 해로 간다.

연습 8.3 (조건수와 중심화 ★★) 단순회귀에서 $A=X\T X/n=\smat{1&\bar x\\ \bar x&\overline{x^2}}$이다. $x$를 중심화하면 $A=\diag(1,\ s_x^2)$ ($s_x^2=\tfrac1n\sum(x_i-\bar x)^2$)임을 보이고, 중심화하지 않았을 때 $\bar x^2\gg1$이면 $\kappa\approx(1+\bar x^2+s_x^2)^2/s_x^2$임을 보여라(고유값의 합과 곱을 쓰라). Galton의 $\bar x=68.3$, $s_x^2=3.19$로 $6.8\times10^6$을 확인하라.

풀이

중심화하면 $\bar x=0$이므로 $A=\diag(1,s_x^2)$. 중심화하지 않으면 $A$의 대각합은 $1+\bar x^2+s_x^2$, 행렬식은 $\overline{x^2}-\bar x^2=s_x^2$이다. $\bar x^2\gg1$이면 큰 고유값은 대각합에 가깝고 작은 고유값은 행렬식$/$대각합에 가까우므로 $\kappa\approx(1+\bar x^2+s_x^2)^2/s_x^2$. Galton: $(1+4666+3.19)^2/3.19=6.8\times10^6$. 중심화하면 $\kappa=3.19$.

이 절을 PDF로 보기 (42쪽)노트북 8절

이 회차에서 읽은 절 0개 · 회차 차례