수학

MATH / 고급 10번

이중 하강과 양성 과적합: 보간해도 일반화되는 이유

최소노름 보간 해의 폐형을 세우고 등방 가우스 특징에서 위험을 정확히 계산해, 보간 문턱에서 위험이 치솟고 그 너머에서 다시 내려가는 이유를 최소 특잇값과 마르첸코–파스투르로 보입니다. 잡음을 외워도 해가 없는 공분산 스펙트럼 조건과 경사하강의 암묵적 편향까지 다룹니다.

PALDYN Team65 MIN READ

이미지 분류 모델을 고르는 팀이 있습니다. 같은 구조의 합성곱 신경망을 폭만 바꿔 열몇 개 학습하고, 폭을 가로축에 시험 오차를 세로축에 찍었습니다. 학습 레이블 일부에는 일부러 잡음을 섞어 두었습니다. 교과서대로라면 곡선은 한 번 내려갔다가 올라가는 U자여야 하고, 실제로 작은 폭에서는 그렇게 갑니다. 그런데 학습 오차가 막 0에 닿는 폭 근처에서 시험 오차가 봉우리처럼 솟더니, 폭을 더 키우자 다시 내려가 U자의 바닥보다 낮은 곳까지 갑니다. 그 큰 모델들은 잡음 섞인 레이블까지 하나도 틀리지 않고 외웠는데도 그렇습니다. Belkin 등이 2019년에 이 모양을 이중 하강이라 이름 붙였고, 같은 해 Nakkiran 등은 ResNet과 트랜스포머에서 모델 크기를 키울 때와 학습을 오래 할 때 모두 이 봉우리가 서고, 레이블 잡음이 많을수록 봉우리가 높아진다고 보고했습니다.

지난 글에서 무작위 레이블까지 외우는 모델 앞에서 균등수렴 경계가 공허해지는 것을 보았고, PAC-Bayes와 평탄성이 그 빈자리를 부분적으로 메웠습니다. 경계는 「위험이 이보다 크지 않다」만 말합니다. 이 글은 방향을 바꿔, 경계가 아니라 위험 그 자체를 정확히 계산할 수 있는 가장 단순한 모형, 선형 회귀로 내려갑니다. 리뷰에서 나올 질문은 넷입니다. 첫째, 왜 하필 학습 오차가 0에 닿는 자리에서 위험이 치솟는가. 둘째, 잡음까지 외운 모델의 위험이 왜 그 너머에서 다시 내려가는가. 셋째, 잡음을 외우는 것이 아예 해가 없는 경우는 언제인가. 넷째, 학습 오차가 0인 해가 무수히 많은데 옵티마이저는 그중 무엇을 고르는가. 넷 다 손으로 끝까지 계산되는 답이 있고, 셋째 질문에는 란초스와 랜덤 행렬에서 세운 마르첸코–파스투르 분포가 계산 도구로 그대로 들어옵니다.

최소노름 보간

보간 해의 집합

표본 nn 개를 행으로 쌓은 설계 행렬 X∈Rn×pX \in \mathbb{R}^{n \times p} 와 정답 y∈Rny \in \mathbb{R}^n 이 있습니다. 열의 수 pp 가 특징의 수, 곧 선형 모형의 파라미터 수입니다. 학습 오차 1n∥Xw−y∥2\tfrac{1}{n}\lVert Xw - y \rVert^2 를 0으로 만드는 ww, 곧 모든 학습 표본을 정확히 지나는 ww 를 찾는 것을 보간이라 부릅니다. 보간이 가능하려면 방정식 Xw=yXw = y 가 풀려야 하고, XX 의 행이 일차독립이면, 곧 계수가 nn 이면 언제나 풀립니다. 그러려면 p≥np \ge n 이어야 합니다. 그래서 특징 수가 표본 수보다 많은 쪽을 과매개변수 영역, 적은 쪽을 과소매개변수 영역이라 부르고, 둘을 가르는 경계 p=np = n 이 보간이 처음 가능해지는 자리, 보간 문턱입니다. 첫머리의 봉우리가 서던 자리가 이 문턱의 신경망 판입니다.

p>np > n 이면 해가 하나가 아닙니다. 해 하나 w0w_0 에 Xz=0Xz = 0 인 zz 를 더해도 여전히 해이므로, 해 전체는 w0+ker⁡Xw_0 + \ker X 라는 평행이동된 부분공간입니다. ker⁡X\ker X 의 차원은 p−np - n 이라, 파라미터가 표본보다 천 개 많으면 학습 오차가 0인 해가 천 차원짜리 평면을 이룹니다. 학습 오차는 이 평면 위의 모든 점을 똑같이 0으로 평가하므로 학습 데이터만으로는 어느 점을 고를지 정할 수 없습니다. 손실 지형에서 과매개변수 신경망의 최소점이 고립된 점이 아니라 평평하게 이어진 골짜기를 이룬다고 했던 것의 가장 단순한 모양이 이 평면입니다. 어느 점을 고르느냐가 시험 위험을 정하고, 그 선택은 손실이 아니라 다른 무언가가 합니다.

가장 자연스러운 선택은 길이가 가장 짧은 해입니다. Xw=yXw = y 를 만족하는 ww 가운데 ∥w∥\lVert w \rVert 가 최소인 것을 최소노름 해라 부르고, 그 폐형은

w∗=X⊤(XX⊤)−1yw^* = X^\top (X X^\top)^{-1} y

입니다. 증명은 두 줄입니다. 먼저 Xw∗=XX⊤(XX⊤)−1y=yXw^* = XX^\top(XX^\top)^{-1}y = y 이니 해입니다. 다음으로 다른 해는 w=w∗+zw = w^* + z, Xz=0Xz = 0 꼴인데, w∗⊤z=y⊤(XX⊤)−1Xz=0w^{*\top} z = y^\top (XX^\top)^{-1} X z = 0 이므로 피타고라스 정리로

∥w∥2=∥w∗∥2+∥z∥2≥∥w∗∥2\lVert w \rVert^2 = \lVert w^* \rVert^2 + \lVert z \rVert^2 \ge \lVert w^* \rVert^2

이고 등호는 z=0z = 0 일 때뿐입니다. w∗w^* 는 X⊤X^\top 에 무언가를 곱한 꼴이라 XX 의 행들이 펼치는 공간, 곧 행공간에 들어 있고, 행공간은 ker⁡X\ker X 의 직교여공간입니다. 해 평면을 가로지르는 방향이 전부 ker⁡X\ker X 에 있으니, 행공간 안의 해는 원점에서 해 평면에 내린 수선의 발입니다.

가로축 w₁, 세로축 w₂ 의 좌표평면. 해 집합 w₁ + 2w₂ = 5 가 파란 직선으로 그어져 있고, 원점을 지나는 보라 점선이 행공간 span{x} 다. 반지름 √5 인 초록 원이 직선에 (1, 2) 에서 닿고 그 자리에 직각 표시가 있다. 직선 위의 다른 해 (3, 1) 은 반지름 √10 인 점선 원 위에 있다

그림은 표본 하나, 특징 둘인 가장 작은 경우입니다. x=(1,2)x = (1, 2), y=5y = 5 이면 해 집합은 직선 w1+2w2=5w_1 + 2w_2 = 5 이고, 최소노름 해는 w∗=x⋅5/∥x∥2=(1,2)w^* = x \cdot 5 / \lVert x \rVert^2 = (1, 2), 길이는 5≈2.24\sqrt{5} \approx 2.24 입니다. 같은 직선 위의 (3,1)(3, 1) 도 학습 오차가 0이지만 길이는 10≈3.16\sqrt{10} \approx 3.16 입니다. 원점을 중심으로 원을 키워 가다 직선에 처음 닿는 점이 최소노름 해이고, 그 점에서 원과 직선은 직각으로 만납니다.

의사역행렬

p<np < n 에서는 XX⊤XX^\top 가 역행렬을 갖지 않으니 위의 폐형이 듣지 않고, 대신 최소제곱 해 (X⊤X)−1X⊤y(X^\top X)^{-1} X^\top y 가 하나로 정해집니다. 두 경우를 한 식으로 묶는 것이 특잇값 분해입니다. 계수가 rr 인 XX 를 X=UΣV⊤X = U \Sigma V^\top, 곧 X=∑i≤rsiuivi⊤X = \sum_{i \le r} s_i u_i v_i^\top 로 쓰면 학습 오차는

∥Xw−y∥2=∑i≤r(si vi⊤w−ui⊤y)2+∥y−∑i≤r(ui⊤y) ui∥2\lVert Xw - y \rVert^2 = \sum_{i \le r} \big(s_i\, v_i^\top w - u_i^\top y\big)^2 + \Big\lVert y - \sum_{i \le r} (u_i^\top y)\, u_i \Big\rVert^2

입니다. 둘째 항은 ww 와 무관하고, 첫째 항은 vi⊤w=ui⊤y/siv_i^\top w = u_i^\top y / s_i 일 때 0이 됩니다. ww 의 나머지 성분, 곧 vr+1,…,vpv_{r+1}, \dots, v_p 방향의 좌표는 오차에 아무 영향이 없으니 노름을 줄이려면 0으로 둡니다. 그렇게 고른

X+y=∑i≤rui⊤ysi vi,X+=VΣ+U⊤X^+ y = \sum_{i \le r} \frac{u_i^\top y}{s_i}\, v_i, \qquad X^+ = V \Sigma^+ U^\top

을 최소제곱 해 가운데 노름이 가장 작은 것이라 정의하고, 행렬 X+X^+ 를 무어–펜로즈 의사역행렬이라 부릅니다. 여기서 Σ+\Sigma^+ 는 0이 아닌 특잇값만 역수로 바꾼 대각 행렬입니다. p<np < n 이고 계수가 pp 이면 이것이 보통의 최소제곱 해와 같고, p>np > n 이고 계수가 nn 이면 위의 최소노름 보간 해와 같습니다. 이 글의 추정량은 처음부터 끝까지 β^=X+y\hat\beta = X^+ y 하나이고, 특징 수가 문턱을 건너는 순간 그 뜻이 「잔차를 가장 작게」에서 「잔차 0 가운데 가장 짧게」로 바뀔 뿐입니다.

이 식에서 첫째 질문의 실마리가 벌써 보입니다. 해의 각 성분은 ui⊤yu_i^\top y 를 특잇값 sis_i 로 나눈 것입니다. 작은 특잇값이 하나라도 있으면 그 방향으로 yy 의 잡음이 1/si1/s_i 배로 부풀어 해에 들어옵니다. 아래에서 보듯 설계 행렬의 가장 작은 특잇값은 정확히 p=np = n 에서 0으로 내려갑니다.

릿지의 극한

릿지 회귀는 오차에 λ∥w∥2\lambda \lVert w \rVert^2 를 더해 최소화하는 방법이고, 해는 wλ=(X⊤X+λI)−1X⊤yw_\lambda = (X^\top X + \lambda I)^{-1} X^\top y 입니다. 같은 특잇값 분해로 쓰면

wλ=∑i≤rsisi2+λ (ui⊤y) viw_\lambda = \sum_{i \le r} \frac{s_i}{s_i^2 + \lambda}\,(u_i^\top y)\, v_i

이고, λ→0\lambda \to 0 에서 각 계수 si/(si2+λ)s_i/(s_i^2 + \lambda) 가 1/si1/s_i 로 가므로 wλ→X+yw_\lambda \to X^+ y 입니다. 최소노름 보간 해는 정규화를 0으로 줄여 간 릿지의 극한이고, 그래서 논문들은 이것을 릿지 없는 회귀라고도 부릅니다. 릿지는 작은 특잇값 방향의 증폭 1/si1/s_i 를 si/λs_i/\lambda 로 눌러 놓는 장치이고, 릿지 없는 회귀는 그 장치를 뗀 것입니다. 그러니 보간 해의 위험이 어떻게 되는지는 정규화 없이 작은 특잇값을 그대로 받아들이면 무슨 일이 생기는지를 묻는 것과 같습니다.

정확한 위험

편향과 분산

위험을 정확히 계산할 수 있는 모형을 세웁니다. 입력 x∈Rpx \in \mathbb{R}^p 는 표준정규 N(0,Ip)N(0, I_p) 를 따르고 정답은 y=x⊤β+εy = x^\top \beta + \varepsilon, 잡음 ε\varepsilon 은 평균 0, 분산 σ2\sigma^2 이며 xx 와 독립입니다. 표본 nn 개로 β^=X+y\hat\beta = X^+ y 를 만들고, 새 입력에서 참 신호와의 기대 제곱 오차

R(β^)=Ex[(x⊤β^−x⊤β)2]=∥β^−β∥2R(\hat\beta) = \mathbb{E}_x\big[(x^\top \hat\beta - x^\top \beta)^2\big] = \lVert \hat\beta - \beta \rVert^2

를 위험이라 부릅니다. 마지막 등호는 E[xx⊤]=I\mathbb{E}[xx^\top] = I 이기 때문입니다. 새 표본의 잡음 σ2\sigma^2 은 어떤 추정량도 줄일 수 없으니 빼고 셉니다. 아무것도 배우지 않은 β^=0\hat\beta = 0 의 위험이 ∥β∥2\lVert \beta \rVert^2 라는 것이 이 글 내내 쓸 기준선입니다.

y=Xβ+εy = X\beta + \varepsilon 을 넣으면 β^=X+Xβ+X+ε\hat\beta = X^+ X \beta + X^+ \varepsilon 이고, P=X+XP = X^+ X 는 행공간으로의 직교사영입니다. 그러므로

β^−β=−(I−P)β+X+ε\hat\beta - \beta = -(I - P)\beta + X^+ \varepsilon

이고, 잡음에 대해 평균을 내면 교차항이 사라져

EεR=∥(I−P)β∥2⏟B+σ2 tr(X+X+⊤)⏟V\mathbb{E}_\varepsilon R = \underbrace{\lVert (I - P)\beta \rVert^2}_{B} + \underbrace{\sigma^2\, \mathrm{tr}\big(X^+ X^{+\top}\big)}_{V}

입니다. 편향과 분산에서 본 분해를 이 모형에 맞춰 적은 것입니다. 여기서 편향 BB 는 잡음이 없어도 남는 오차로, 참 신호 β\beta 가운데 행공간 밖에 놓여 데이터가 한 번도 비추지 못한 부분입니다. 분산 VV 는 학습 레이블의 잡음이 해에 새어 든 부분입니다. 앞 절의 특잇값 식에서 tr(X+X+⊤)=∑i1/si2\mathrm{tr}(X^+X^{+\top}) = \sum_i 1/s_i^2 이므로, 표본 공분산 S=X⊤X/nS = X^\top X / n 의 0이 아닌 고윳값 λi=si2/n\lambda_i = s_i^2/n 으로 쓰면

V=σ2n∑λi≠01λiV = \frac{\sigma^2}{n} \sum_{\lambda_i \ne 0} \frac{1}{\lambda_i}

입니다. 분산은 표본 공분산 고윳값의 역수 평균입니다. 고전적인 이야기에서 둘의 균형은 정성적인 그림으로 남지만, 이 모형에서는 둘 다 nn 과 pp 의 식으로 끝까지 나옵니다.

과소매개변수 영역

p<np < n 이면 XX 의 계수가 확률 1로 pp 라 P=IP = I, 편향은 0입니다. 남은 것은 V=σ2 tr (X⊤X)−1V = \sigma^2\, \mathrm{tr}\,(X^\top X)^{-1} 의 기댓값이고, 보조정리 하나로 정확히 나옵니다. XX 의 성분이 독립 표준정규이고 n>p+1n > p + 1 이면

E[(X⊤X)−1]=1n−p−1Ip\mathbb{E}\big[(X^\top X)^{-1}\big] = \frac{1}{n - p - 1} I_p

입니다.

증명은 대각 성분 하나로 충분합니다. 표준정규 행렬은 열 순서를 바꿔도 분포가 같으므로 대각 성분의 기댓값은 모두 같고, 직교행렬 QQ 를 곱한 XQXQ 도 분포가 같으므로 E[(X⊤X)−1]=Q⊤E[(X⊤X)−1]Q\mathbb{E}[(X^\top X)^{-1}] = Q^\top \mathbb{E}[(X^\top X)^{-1}] Q 가 모든 QQ 에서 성립해 기댓값은 단위행렬의 상수배입니다. 첫 열을 x1x_1, 나머지 p−1p - 1 열을 X2X_2 로 가르면 블록 행렬의 역에 대한 슈어 보수 공식으로

[(X⊤X)−1]11=1x1⊤x1−x1⊤X2(X2⊤X2)−1X2⊤x1=1∥(I−P2) x1∥2\big[(X^\top X)^{-1}\big]_{11} = \frac{1}{x_1^\top x_1 - x_1^\top X_2 (X_2^\top X_2)^{-1} X_2^\top x_1} = \frac{1}{\lVert (I - P_2)\, x_1 \rVert^2}

입니다. P2P_2 는 X2X_2 의 열공간으로의 사영이라 I−P2I - P_2 는 계수 n−p+1n - p + 1 인 사영이고, x1x_1 은 X2X_2 와 독립인 표준정규 벡터입니다. 표준정규 벡터를 kk 차원 부분공간에 사영한 길이의 제곱은 자유도 kk 인 카이제곱 분포 χk2\chi^2_k 를 따르므로 분모는 χn−p+12\chi^2_{n-p+1} 입니다. 카이제곱 밀도 uk/2−1e−u/2/(2k/2Γ(k/2))u^{k/2-1} e^{-u/2} / (2^{k/2}\Gamma(k/2)) 에 1/u1/u 를 곱해 적분하면

E[1χk2]=2k/2−1 Γ(k/2−1)2k/2 Γ(k/2)=12(k/2−1)=1k−2\mathbb{E}\Big[\frac{1}{\chi^2_k}\Big] = \frac{2^{k/2-1}\,\Gamma(k/2 - 1)}{2^{k/2}\,\Gamma(k/2)} = \frac{1}{2(k/2 - 1)} = \frac{1}{k - 2}

이고, k=n−p+1k = n - p + 1 을 넣으면 1/(n−p−1)1/(n - p - 1) 입니다. □\square

그래서 과소매개변수 영역의 위험은 유한한 nn 에서 정확히

ER=σ2pn−p−1  ⟶  σ2γ1−γ,γ=pn\mathbb{E} R = \sigma^2 \frac{p}{n - p - 1} \;\longrightarrow\; \sigma^2 \frac{\gamma}{1 - \gamma}, \qquad \gamma = \frac{p}{n}

입니다. 화살표는 γ\gamma 를 고정하고 n,pn, p 를 함께 키운 극한입니다. 같은 극한을 마르첸코–파스투르 분포로 계산할 수도 있습니다. 위의 VV 식에서 고윳값 역수의 평균은 경험적 스펙트럼 분포 위의 적분 ∫λ−1ρMP(λ) dλ\int \lambda^{-1} \rho_{\mathrm{MP}}(\lambda)\, d\lambda 로 가고, 지지구간 [a,b][a, b] 에서

∫ab(b−λ)(λ−a)λ2 dλ=π(a+b2ab−1)\int_a^b \frac{\sqrt{(b - \lambda)(\lambda - a)}}{\lambda^2}\, d\lambda = \pi\Big(\frac{a + b}{2\sqrt{ab}} - 1\Big)

라는 표준 적분을 씁니다. a,b=(1∓γ)2a, b = (1 \mp \sqrt{\gamma})^2 이면 a+b=2(1+γ)a + b = 2(1 + \gamma), ab=1−γ\sqrt{ab} = 1 - \gamma 라 적분이 2πγ/(1−γ)2\pi\gamma/(1 - \gamma) 이고, 밀도의 분모 2πγ2\pi\gamma 로 나누면 ∫λ−1dρMP=1/(1−γ)\int \lambda^{-1} d\rho_{\mathrm{MP}} = 1/(1 - \gamma) 입니다. 고윳값이 pp 개이므로 V=σ2(p/n)⋅1/(1−γ)=σ2γ/(1−γ)V = \sigma^2 (p/n) \cdot 1/(1 - \gamma) = \sigma^2 \gamma/(1 - \gamma) 로 같은 답입니다. 유한한 nn 에서 정확한 카이제곱 계산과 극한에서의 스펙트럼 계산이 한 점에서 만납니다.

과매개변수 영역

p>np > n 이면 행공간은 pp 차원 안의 nn 차원 부분공간이고, 편향이 살아납니다. XQXQ 가 XX 와 분포가 같다는 회전 불변성 때문에 행공간은 pp 차원 안에서 고르게 무작위로 놓인 nn 차원 부분공간이고, 그 사영의 기댓값 E[P]\mathbb{E}[P] 는 단위행렬의 상수배입니다. 대각합이 tr P=n\mathrm{tr}\,P = n 이므로 E[P]=(n/p)I\mathbb{E}[P] = (n/p) I 이고,

EB=β⊤(I−EP) β=∥β∥2(1−np)\mathbb{E} B = \beta^\top (I - \mathbb{E}P)\, \beta = \lVert \beta \rVert^2 \Big(1 - \frac{n}{p}\Big)

입니다. 분산은 V=σ2 tr (XX⊤)−1V = \sigma^2\, \mathrm{tr}\,(XX^\top)^{-1} 인데, XX⊤XX^\top 는 X⊤X^\top 의 열 pp 개, 곧 Rn\mathbb{R}^n 의 표준정규 벡터 pp 개로 만든 n×nn \times n 행렬이라 보조정리를 nn 과 pp 의 자리를 바꿔 쓰면 E tr(XX⊤)−1=n/(p−n−1)\mathbb{E}\,\mathrm{tr}(XX^\top)^{-1} = n/(p - n - 1) 입니다. 합치면 ∥β∥2=r2\lVert \beta \rVert^2 = r^2 로 적어

ER=r2(1−np)+σ2np−n−1  ⟶  r2(1−1γ)+σ2γ−1\mathbb{E} R = r^2\Big(1 - \frac{n}{p}\Big) + \sigma^2 \frac{n}{p - n - 1} \;\longrightarrow\; r^2\Big(1 - \frac{1}{\gamma}\Big) + \frac{\sigma^2}{\gamma - 1}

입니다. 이 영역에서 마르첸코–파스투르 분포는 0에 질량 1−1/γ1 - 1/\gamma 를 두고 나머지를 [(γ−1)2,(γ+1)2][(\sqrt\gamma - 1)^2, (\sqrt\gamma + 1)^2] 에 펼칩니다. 같은 표준 적분에서 ab=γ−1\sqrt{ab} = \gamma - 1 로 바뀌어 0이 아닌 부분의 ∫λ−1dρ=1/(γ(γ−1))\int \lambda^{-1} d\rho = 1/(\gamma(\gamma - 1)) 이고, p/n=γp/n = \gamma 를 곱하면 분산 배수 1/(γ−1)1/(\gamma - 1) 이 다시 나옵니다.

n=100n = 100, r2=1r^2 = 1, σ2=0.25\sigma^2 = 0.25 에서 β\beta 의 방향과 XX, 잡음을 400번씩 새로 뽑아 의사역행렬로 푼 위험의 평균을 정확한 식과 대 보았습니다.

pp 50 90 110 200 400
정확한 식 0.255 2.500 2.869 0.753 0.834
시뮬레이션 0.257 2.396 2.794 0.750 0.833

문턱에서 먼 곳은 셋째 자리까지 맞습니다. 문턱 가까운 90과 110에서 시뮬레이션이 식보다 조금 낮은 것은 이 위험의 분포가 오른쪽으로 꼬리가 아주 길어, 드물게 나오는 큰 값이 400번 안에 덜 잡히기 때문입니다. 실제로 p=n±1p = n \pm 1 에서는 기댓값 자체가 무한대입니다. 이 모형에서 과매개변수 쪽의 위험이 가장 낮은 자리도 계산됩니다. 극한식을 γ\gamma 로 미분해 0으로 두면 r2/γ2=σ2/(γ−1)2r^2/\gamma^2 = \sigma^2/(\gamma - 1)^2, 곧 γ∗=r/(r−σ)\gamma^* = r/(r - \sigma) 이고, 여기서는 γ∗=2\gamma^* = 2 에서 위험 0.5+0.25=0.750.5 + 0.25 = 0.75 입니다. 표의 p=200p = 200 이 그 자리입니다.

이중 하강

최소 특잇값

첫째 질문에 답할 차례입니다. 분산 V=(σ2/n)∑1/λiV = (\sigma^2/n)\sum 1/\lambda_i 는 표본 공분산의 0이 아닌 고윳값 가운데 작은 것들이 정합니다. 마르첸코–파스투르 분포에서 0이 아닌 고윳값의 아래 끝은 γ<1\gamma < 1 이든 γ>1\gamma > 1 이든 똑같이

λmin⁡≈(1−γ)2,smin⁡(X)≈∣n−p∣\lambda_{\min} \approx (1 - \sqrt{\gamma})^2, \qquad s_{\min}(X) \approx \lvert \sqrt{n} - \sqrt{p} \rvert

이고, 둘 다 p=np = n 에서 0이 됩니다. 그림 왼쪽이 이 아래 끝이고 점은 n=400n = 400 행렬로 잰 실제 최소 고윳값입니다. 그런데 극한의 분산 배수 γ/(1−γ)\gamma/(1 - \gamma) 가 발산하는 것은 최소 고윳값 하나 때문이 아닙니다. γ\gamma 를 1이 아닌 값에 고정하면 최소 고윳값 한 개의 몫은 σ2/(n(1−γ)2)\sigma^2/(n(1 - \sqrt\gamma)^2) 이라 nn 이 커지면 사라집니다. 발산은 집단으로 일어납니다. 아래 끝이 0으로 내려오면서 그 근처의 밀도가 쌓이고, γ=1\gamma = 1 에서는 마르첸코–파스투르 밀도가 0 근처에서 1/(πλ)1/(\pi\sqrt{\lambda}) 처럼 행동해 ∫λ−1dρ\int \lambda^{-1} d\rho 가 무한대가 됩니다. 문턱에서는 작은 고윳값이 하나가 아니라 덩어리로 0에 붙는다는 것이 정확한 그림입니다. 유한한 행렬에서 정확히 p=np = n 이면 최소 고윳값은 1/n21/n^2 정도까지 내려가, 그 하나의 몫만으로도 분산이 nn 에 비례해 커집니다.

두 칸 그림. 왼쪽은 가로축 γ = p/n (0~4), 세로축 최소 고윳값으로, 곡선 (1 − √γ)² 이 1 에서 내려와 γ = 1 의 붉은 점선에서 0 에 닿은 뒤 다시 올라 γ = 4 에서 1 이 된다. n = 400 행렬로 잰 점들이 곡선 위에 있다. 오른쪽은 분산 배수 V/σ² 로, 왼쪽 가지 γ/(1 − γ) 와 오른쪽 가지 1/(γ − 1) 이 γ = 1 에서 위로 발산하고 점들이 두 가지를 따라간다

직관은 이렇습니다. p=np = n 이면 XX 는 정사각 행렬이라 보간 해가 X−1yX^{-1}y 하나뿐이고, 고를 여지가 전혀 없습니다. 잡음 섞인 yy 를 정확히 지나도록 강제당한 해는 거의 특이한 행렬의 역을 통과하며 잡음을 크게 부풀립니다. 과소매개변수 쪽에서는 잡음의 일부가 잔차로 남아 해에 들어가지 않고, 과매개변수 쪽에서는 해가 잡음을 여러 방향에 나눠 담을 여유가 있습니다. 문턱은 그 두 여유가 동시에 사라지는 자리입니다. 그림 오른쪽의 분산 배수 γ/(1−γ)\gamma/(1 - \gamma) 와 1/(γ−1)1/(\gamma - 1) 이 양쪽에서 문턱을 향해 발산하는 것이 그 모습이고, γ=0.9\gamma = 0.9 와 1.11.1 에서 잰 배수가 9.19와 10.34로 이론값 9와 10에 붙습니다.

특징 p개 모형

앞 절의 모형은 특징 수 pp 를 바꿀 때마다 문제 자체가 바뀝니다. 참 신호도 pp 차원이기 때문입니다. 첫머리의 장면처럼 문제는 그대로 두고 모델의 크기만 바꾸려면, 참 신호는 큰 차원 dd 에 고정해 두고 모델이 그중 앞 pp 개 특징만 쓰게 하면 됩니다. 입력 x∈Rdx \in \mathbb{R}^d 는 N(0,Id)N(0, I_d), 정답은 y=x⊤β+εy = x^\top \beta + \varepsilon 이고, 모델은 처음 pp 좌표 xSx_S 만 보고 β^S=XS+y\hat\beta_S = X_S^+ y 를 만듭니다. 이 모형을 이 글에서는 특징 p개 모형이라 부릅니다. Hastie·Montanari·Rosset·Tibshirani가 2019년에 정리한 「잘못 지정된 모형」의 한 판입니다.

이 모형의 위험은 앞 절의 결과로 바로 나옵니다. 모델이 보지 못하는 부분 xSc⊤βScx_{S^c}^\top \beta_{S^c} 는 xSx_S 와 독립인 정규 확률변수라, 모델 쪽에서 보면 잡음과 구별되지 않습니다. 그래서 문제는 참 신호 βS\beta_S, 잡음 분산이

σeff2=σ2+∥βSc∥2\sigma_{\mathrm{eff}}^2 = \sigma^2 + \lVert \beta_{S^c} \rVert^2

인 앞 절의 모형과 똑같습니다. 이 σeff2\sigma_{\mathrm{eff}}^2 를 유효 잡음이라 부릅니다. 위험에는 모델이 원리적으로 못 잡는 ∥βSc∥2\lVert \beta_{S^c} \rVert^2 가 더해집니다. 앞 pp 개 특징의 신호 에너지를 s(p)=∥βS∥2s(p) = \lVert \beta_S \rVert^2, 전체를 ∥β∥2=1\lVert \beta \rVert^2 = 1 로 두면

ER(p)={(1−s(p))+σeff2pn−p−1p<n−1(1−s(p))+s(p)(1−np)+σeff2np−n−1p>n+1\mathbb{E}R(p) = \begin{cases} \big(1 - s(p)\big) + \sigma_{\mathrm{eff}}^2 \dfrac{p}{n - p - 1} & p < n - 1 \\[2ex] \big(1 - s(p)\big) + s(p)\Big(1 - \dfrac{n}{p}\Big) + \sigma_{\mathrm{eff}}^2 \dfrac{n}{p - n - 1} & p > n + 1 \end{cases}

입니다. 과매개변수 쪽의 편향 계산은 βS\beta_S 의 방향과 무관했으므로, 신호가 앞 특징에 몰려 있어도 이 식은 정확합니다.

n=100n = 100, d=400d = 400, σ2=0.1\sigma^2 = 0.1 로 두고 신호를 βj2∝1/j\beta_j^2 \propto 1/j, 곧 앞 특징일수록 신호가 큰 꼴로 심었습니다. 아래 그림의 곡선이 위의 식이고 점은 300번 뽑아 평균한 시뮬레이션입니다.

가로축 특징 수 p (0400), 세로축 시험 위험 R (02). 파란 곡선이 p = 21 에서 0.592 로 첫 골을 이룬 뒤 p = 100 의 붉은 점선(보간 문턱)을 향해 위로 솟고, 문턱 너머에서 위에서 내려와 p = 243 에서 0.743 의 둘째 골을 지나 p = 400 에서 0.783 이 된다. 흰 점이 곡선을 따라가고, R = 1 에 '아무것도 안 배운 예측' 점선이 있다

곡선은 첫머리의 그림과 같은 모양입니다. 과소매개변수 쪽에서는 특징을 늘릴수록 못 잡는 신호 1−s(p)1 - s(p) 가 줄고 분산 배수 p/(n−p−1)p/(n - p - 1) 이 늘어, p=21p = 21 에서 위험 0.592로 바닥을 찍는 고전적인 U자가 섭니다. 문턱으로 다가가며 분산 배수가 발산해 위험이 치솟고, 문턱을 넘으면 다시 내려와 p=243p = 243 에서 0.743으로 둘째 골을 이룹니다. 시뮬레이션은 p=21p = 21 에서 0.589, p=243p = 243 에서 0.744로 식과 맞습니다.

이 계산은 랜덤 특징 모형, 곧 입력을 무작위 가중치와 ReLU에 통과시킨 특징을 쓰는 모형에서도 같은 모양으로 나온다는 것이 Mei와 Montanari의 결과입니다. 그쪽은 비선형 특징의 공분산을 다루는 도구가 더 들어 여기서 다루지 않지만, 위험이 문턱에서 발산하고 그 너머에서 내려온다는 구조, 그리고 그 원인이 특징 행렬의 작은 특잇값이라는 진단은 같습니다.

두 번째 하강

둘째 질문입니다. 문턱 너머에서 위험이 다시 내려가는 것은 분산 σeff2 n/(p−n−1)\sigma_{\mathrm{eff}}^2\, n/(p - n - 1) 이 pp 와 함께 줄기 때문입니다. XX⊤=∑jcjcj⊤XX^\top = \sum_j c_j c_j^\top 는 Rn\mathbb{R}^n 의 무작위 벡터 pp 개를 쌓은 것이라, 특징이 늘수록 이 합이 p⋅Inp \cdot I_n 에 가까워지고 최소 고윳값 (γ−1)2(\sqrt{\gamma} - 1)^2 이 커집니다. 해 쪽에서 보면 잡음 ε\varepsilon 을 보간하는 데 드는 노름 ∥X+ε∥2≈σ2n/(p−n)\lVert X^+ \varepsilon \rVert^2 \approx \sigma^2 n/(p - n) 이 줄어듭니다. 잡음을 외우는 것은 변함없지만, 외운 잡음이 pp 차원에 얇게 흩어져 새 입력 하나에서는 거의 드러나지 않습니다.

그런데 그림의 둘째 골 0.743은 첫째 골 0.592보다 높습니다. p=d=400p = d = 400 까지 가도 0.783입니다. 이유는 편향의 식 s(p)(1−n/p)s(p)(1 - n/p) 에 있습니다. 행공간이 pp 차원 안의 고른 무작위 nn 차원이라 신호의 n/pn/p 만 비추고, 특징을 늘릴수록 그 몫이 줄어듭니다. 잡음을 희석하는 바로 그 여분의 차원이 신호도 똑같이 희석합니다. 공분산이 등방, 곧 모든 방향의 분산이 같으면 여분의 차원은 잡음과 신호를 가리지 않는다는 뜻입니다. 등방 공분산에서는 잡음이 있는 한 최적의 릿지 세기가 언제나 0보다 커서, 잘 조율한 릿지가 최소노름 보간을 이긴다는 것이 Hastie 등의 결과이기도 합니다.

첫머리의 장면에서 둘째 골이 첫째 골보다 낮았던 것은 그래서 이 등방 모형만으로는 설명되지 않습니다. 필요한 것은 여분의 차원이 잡음은 받아 주되 신호는 빼앗지 않는 구조이고, 그것을 정하는 것이 공분산의 스펙트럼입니다.

양성 과적합

유효 차원

학습 레이블의 잡음까지 완벽히 보간하면서도 표본이 늘면 위험이 최선의 값으로 가는 현상을 양성 과적합이라 부릅니다. 잡음을 외우는 것이 해롭지 않다는 뜻에서 「양성」이고, Bartlett·Long·Lugosi·Tsigler가 2020년에 선형 회귀에서 그 필요충분조건을 공분산의 스펙트럼으로 적었습니다. 이제 입력의 공분산을 Σ\Sigma, 고윳값을 λ1≥λ2≥⋯\lambda_1 \ge \lambda_2 \ge \cdots 로 두고, 앞 kk 개를 뺀 나머지 꼬리에 대해 두 수를 정의합니다.

rk(Σ)=∑i>kλiλk+1,Rk(Σ)=(∑i>kλi)2∑i>kλi2r_k(\Sigma) = \frac{\sum_{i > k} \lambda_i}{\lambda_{k+1}}, \qquad R_k(\Sigma) = \frac{\big(\sum_{i > k} \lambda_i\big)^2}{\sum_{i > k} \lambda_i^2}

둘을 묶어 유효 차원이라 부릅니다. 꼬리의 분산이 몇 개의 방향에 고르게 퍼져 있는 것과 맞먹는지를 재는 수이고, 꼬리 고윳값이 모두 같으면 둘 다 정확히 꼬리의 차원과 같습니다. rkr_k 는 꼬리 전체를 꼬리의 맨 위 고윳값으로 나눠 맨 위 방향이 얼마나 튀는지를, RkR_k 는 제곱합으로 나눠 꼬리 전체의 고르기를 봅니다. 둘 사이에는 rk≤Rk≤rk2r_k \le R_k \le r_k^2 가 늘 성립합니다. ∑i>kλi2≤λk+1∑i>kλi\sum_{i>k} \lambda_i^2 \le \lambda_{k+1} \sum_{i>k} \lambda_i 이니 Rk≥rkR_k \ge r_k 이고, ∑i>kλi2≥λk+12\sum_{i>k} \lambda_i^2 \ge \lambda_{k+1}^2 이니 Rk≤rk2R_k \le r_k^2 입니다. 그리고 어떤 상수 bb 에 대해 rk≥bnr_k \ge bn 이 처음 성립하는 kk 를 k∗k^* 로 둡니다. k∗k^* 는 스펙트럼을 「표본 수에 비해 큰 스파이크」와 「표본 수보다 넓게 퍼진 꼬리」로 가르는 자리입니다.

Bartlett 등의 정리는 이렇습니다. 입력이 준가우스이고 잡음 분산이 σ2\sigma^2 일 때, 높은 확률로 최소노름 보간 해의 위험은

R(β^)  ≲  ∥β∥2∥Σ∥max⁡{r0n,r0n}+σ2(k∗n+nRk∗)R(\hat\beta) \;\lesssim\; \lVert \beta \rVert^2 \lVert \Sigma \rVert \max\Big\{\sqrt{\frac{r_0}{n}}, \frac{r_0}{n}\Big\} + \sigma^2\Big(\frac{k^*}{n} + \frac{n}{R_{k^*}}\Big)

으로 위에서 눌리고, 분산 항 σ2(k∗/n+n/Rk∗)\sigma^2(k^*/n + n/R_{k^*}) 은 상수배 안에서 아래로도 눌립니다. 그러므로 nn 마다 공분산 Σn\Sigma_n 을 바꿔 가는 수열에서 보간이 양성일 필요충분조건은

r0(Σn)n→0,kn∗n→0,nRkn∗(Σn)→0\frac{r_0(\Sigma_n)}{n} \to 0, \qquad \frac{k_n^*}{n} \to 0, \qquad \frac{n}{R_{k_n^*}(\Sigma_n)} \to 0

입니다. 첫째는 전체 분산이 표본 수에 비해 너무 퍼져 있지 않아 신호가 희석되지 않을 것, 둘째는 스파이크가 표본 수보다 훨씬 적을 것, 셋째는 꼬리가 표본 수보다 훨씬 넓게 퍼져 있을 것입니다. 증명은 행렬 집중부등식으로 꼬리의 그람 행렬 XtailXtail⊤X_{\mathrm{tail}} X_{\mathrm{tail}}^\top 이 rk∗≥bnr_{k^*} \ge bn 덕분에 단위행렬의 상수배에 가깝다는 것을 보이는 데서 시작해 꽤 깁니다. 이 글에서는 끝까지 따라가지 않고, 다음 절에서 그 핵심 단계를 하나의 구체적인 스펙트럼으로 계산해 보입니다.

앞 절의 등방 모형이 왜 양성이 될 수 없었는지도 이 조건으로 바로 읽힙니다. Σ=Ip\Sigma = I_p 이면 r0=pr_0 = p 이고 과매개변수 영역에서는 p>np > n 이니 첫째 조건이 깨집니다. 편향 1−n/p1 - n/p 가 정확히 그 깨짐의 값입니다.

스파이크와 긴 꼬리

스펙트럼을 가장 단순하게 나눕니다. 고윳값 1인 방향이 kk 개 있고 신호 β\beta 는 그 안에만 삽니다. 나머지는 고윳값 τ=c/m\tau = c/m 인 방향 mm 개로, 꼬리 분산의 합이 cc 로 고정되어 있습니다. 앞쪽을 스파이크, 뒤쪽을 꼬리라 부릅니다. 꼬리가 평평하니 rk=Rk=mr_k = R_k = m 입니다. 이제 꼬리 차원 mm 이 nn 보다 훨씬 크다고 둡니다.

가로축 고윳값 순번 i, 세로축 고윳값 λᵢ, 둘 다 로그 눈금. 순번 1~10 에서 λ = 1 인 스파이크가 서고, 10 에서 수직으로 떨어져 순번 50,000 까지 λ = 0.0004 의 평평한 꼬리가 이어지며 꼬리 아래가 옅게 칠해져 있다. n = 200 에 붉은 점선. 오른쪽 상자 셋이 스파이크는 신호가 사는 곳이자 꼬리가 릿지 노릇을 하는 곳, 꼬리 합 c = 20 이 편향 (c/(n+c))² 을 정하고, r₁₀ = R₁₀ = m 이 꼬리 분산 σ²(n−k)/m 을 정한다고 적는다

핵심 관찰은 꼬리의 그람 행렬입니다. XtXt⊤X_t X_t^\top 의 대각 성분은 τ\tau 곱하기 표준정규 제곱 mm 개의 합이라 cc 근처에 몰리고, 비대각 성분은 크기가 c/mc/\sqrt{m} 정도라 m≫nm \gg n 이면 무시됩니다. 곧 XtXt⊤≈cInX_t X_t^\top \approx cI_n 입니다. 그러면 최소노름 해의 스파이크 부분은

β^s=Xs⊤(XsXs⊤+cI)−1y=(Xs⊤Xs+cI)−1Xs⊤y\hat\beta_s = X_s^\top (X_s X_s^\top + cI)^{-1} y = (X_s^\top X_s + cI)^{-1} X_s^\top y

로, 정확히 정규화 세기 cc 인 릿지 회귀입니다. 등호는 X⊤(XX⊤+cI)−1=(X⊤X+cI)−1X⊤X^\top(XX^\top + cI)^{-1} = (X^\top X + cI)^{-1}X^\top 라는 항등식 그대로입니다. 꼬리는 아무도 시키지 않은 릿지 정규화를 스파이크에 걸어 주는 셈이고, 그것이 첫째 효과입니다. Xs⊤Xs≈nIkX_s^\top X_s \approx nI_k 이니 편향은 (c/(n+c))2∥β∥2\big(c/(n + c)\big)^2 \lVert \beta \rVert^2, 스파이크 쪽 분산은 σ2k n/(n+c)2\sigma^2 k\, n/(n + c)^2 입니다.

둘째 효과는 꼬리가 잡음을 받아 주는 방식입니다. 꼬리 성분 β^t=Xt⊤G−1ε\hat\beta_t = X_t^\top G^{-1}\varepsilon (G=XX⊤G = XX^\top) 의 위험 기여는

τ ∥β^t∥2=τ ε⊤G−1XtXt⊤G−1ε  ≈  τ c σ2 tr G−2\tau\, \lVert \hat\beta_t \rVert^2 = \tau\, \varepsilon^\top G^{-1} X_t X_t^\top G^{-1} \varepsilon \;\approx\; \tau\, c\, \sigma^2\, \mathrm{tr}\, G^{-2}

입니다. GG 는 고윳값 n+cn + c 근처가 kk 개, cc 근처가 n−kn - k 개이니 tr G−2≈(n−k)/c2\mathrm{tr}\,G^{-2} \approx (n - k)/c^2 이고, 꼬리 분산은 σ2(n−k)/m\sigma^2 (n - k)/m 입니다. 꼬리는 잡음을 외우되 그 외운 것을 고윳값이 아주 작은 방향 mm 개에 나눠 담아, 새 입력에서는 1/m1/m 만큼만 드러나게 합니다. 합치면

R≈(cn+c)2∥β∥2+σ2(kn(n+c)2+n−km)R \approx \Big(\frac{c}{n + c}\Big)^2 \lVert \beta \rVert^2 + \sigma^2\Big(\frac{kn}{(n + c)^2} + \frac{n - k}{m}\Big)

이고, 둘째 괄호의 꼴이 정리의 k∗/n+n/Rk∗k^*/n + n/R_{k^*} 와 같습니다.

n=200n = 200, k=10k = 10, ∥β∥=1\lVert \beta \rVert = 1, 그리고 잡음 분산을 신호와 같은 σ2=1\sigma^2 = 1 로 크게 잡아 20번씩 시뮬레이션했습니다. 꼬리 합은 c=20c = 20 입니다.

꼬리 차원 mm 400 2,000 10,000 50,000
편향 0.005 0.008 0.010 0.009
분산 1.061 0.151 0.060 0.039
위험 1.066 0.160 0.070 0.048

m=50,000m = 50{,}000 에서 위험은 0.048입니다. 아무것도 안 배운 예측의 1에 견주면 스무 분의 일이고, 신호가 어느 열 방향에 사는지 미리 알고 그 열 개로만 최소제곱을 푼 경우의 σ2k/(n−k−1)=10/189=0.053\sigma^2 k/(n - k - 1) = 10/189 = 0.053 과 같은 수준입니다. 잡음 분산 1짜리 레이블 200개를 하나도 틀리지 않고 외웠는데도 그렇습니다. 반대로 m=400m = 400 은 꼬리가 표본 수의 두 배밖에 안 되어 XtXt⊤X_t X_t^\top 가 단위행렬과 거리가 멀고, 분산이 1을 넘어 보간이 해롭습니다. 위의 근사식은 이 경우 0.525를 주는데 실제는 1.066이라, 근사가 m≫nm \gg n 에서만 맞는다는 것도 함께 보입니다. 같은 m=50,000m = 50{,}000 에서 cc 를 200으로 키우면 편향이 (200/400)2=0.25(200/400)^2 = 0.25 로 커집니다. 꼬리가 너무 무거우면 릿지가 너무 세져 신호까지 깎습니다. 첫째 조건 r0/n→0r_0/n \to 0 이 막는 것이 이것입니다.

스펙트럼 감쇠

무한 차원 공분산에서 고윳값이 어떻게 줄어들어야 양성인지도 정리가 답합니다. λi=i−αln⁡−β(i+1)\lambda_i = i^{-\alpha} \ln^{-\beta}(i + 1) 꼴에서 보간이 양성인 것은 α=1\alpha = 1, β>1\beta > 1 일 때뿐입니다. α<1\alpha < 1 이면 고윳값의 합이 무한대라 입력의 분산부터 유한하지 않고, α>1\alpha > 1 이면 꼬리가 너무 빨리 줄어 RkR_k 가 kk 와 같은 정도에 머물러 n/Rk∗n/R_{k^*} 가 0으로 가지 않습니다. 합은 유한하되 겨우 유한한, 1/(iln⁡2i)1/(i \ln^2 i) 처럼 아슬아슬하게 줄어드는 스펙트럼만 꼬리가 충분히 넓습니다.

조건이 이렇게 좁다는 것이 정직한 결론입니다. 양성 과적합은 「보간은 언제나 괜찮다」가 아니라, 신호를 싣는 소수의 큰 방향과 잡음을 받아 줄 아주 많은 작은 방향이 함께 있을 때의 이야기입니다. 이 사이의 넓은 회색 지대, 곧 위험이 0으로는 안 가지만 발산하지도 않는 보간을 Mallinar 등은 온건한 과적합이라 부르고, 커널 회귀와 신경망의 많은 경우가 여기에 든다고 보고했습니다. 스펙트럼의 꼬리가 몇 제곱으로 줄어드느냐는 멱법칙과 스케일링 곡선에서 본 데이터 스케일링 지수를 정하는 바로 그 양이기도 해서, 같은 계산이 고급 트랙 뒤쪽의 스케일링 법칙 이론에서 다시 쓰입니다.

암묵적 편향

행공간의 경사하강

넷째 질문입니다. 지금까지 추정량은 처음부터 최소노름 해였습니다. 그런데 신경망을 학습하는 사람은 최소노름 해를 고르라고 지시한 적이 없고, 손실을 경사하강으로 줄였을 뿐입니다. 선형 회귀에서 그 둘이 같다는 것이 다음 사실입니다. 손실 L(w)=12∥Xw−y∥2L(w) = \tfrac{1}{2}\lVert Xw - y \rVert^2 의 기울기는 X⊤(Xw−y)X^\top(Xw - y) 이고, 이것은 언제나 행공간 안의 벡터입니다. 그러므로 경사하강 wt+1=wt−ηX⊤(Xwt−y)w_{t+1} = w_t - \eta X^\top(Xw_t - y) 은 w0w_0 에서 행공간 방향으로만 움직이고, wt−w0w_t - w_0 은 늘 행공간에 있습니다.

특잇값 좌표로 쓰면 수렴까지 보입니다. ai(t)=vi⊤wta_i(t) = v_i^\top w_t 로 두면 i≤ri \le r 에 대해

ai(t+1)=(1−ηsi2) ai(t)+η si ui⊤ya_i(t + 1) = (1 - \eta s_i^2)\, a_i(t) + \eta\, s_i\, u_i^\top y

이고, 0<η<2/smax⁡20 < \eta < 2/s_{\max}^2 이면 ∣1−ηsi2∣<1\lvert 1 - \eta s_i^2 \rvert < 1 이라 ai(t)→ui⊤y/sia_i(t) \to u_i^\top y / s_i 입니다. i>ri > r 인 좌표, 곧 ker⁡X\ker X 방향은 기울기가 0이라 처음 값 그대로입니다. 합치면

w∞=X+y+(I−P) w0w_\infty = X^+ y + (I - P)\, w_0

입니다. w0=0w_0 = 0 에서 시작하면 정확히 최소노름 해이고, 일반적으로는 해 평면 위에서 w0w_0 에 가장 가까운 점, 곧 w0w_0 을 해 평면에 사영한 점입니다. 손실은 해 평면의 모든 점에 같은 값을 주는데 알고리즘이 그중 하나를 골랐으니, 그 선택의 규칙을 암묵적 편향이라 부릅니다. 명시적인 정규화 항 없이 알고리즘의 동역학이 거는 선호라는 뜻입니다.

가로축 w₁, 세로축 w₂ 의 좌표평면에 해 집합 w₁ + 2w₂ = 5 가 파란 직선으로, 행공간이 보라 점선으로 그어져 있다. 원점에서 출발한 초록 화살표가 행공간을 따라 (1, 2) 로 가고 반복점이 점으로 찍혀 있다. w₀ = (3, −1) 에서 출발한 붉은 화살표는 행공간과 평행하게 움직여 (3.8, 0.6) 에서 직선에 닿는다

그림은 처음의 예 x=(1,2)x = (1, 2), y=5y = 5 입니다. 기울기는 언제나 xx 방향이라 원점에서 출발하면 행공간을 따라 (1,2)(1, 2) 에 닿고, w0=(3,−1)w_0 = (3, -1) 에서 출발하면 xx 와 평행하게 움직여 (3,−1)+(1,2)⋅(5−1)/5=(3.8,0.6)(3, -1) + (1, 2)\cdot(5 - 1)/5 = (3.8, 0.6) 에 닿습니다. 둘 다 학습 오차가 0이지만 둘째 해의 길이는 3.85로 최소노름 해의 2.24보다 깁니다. 초기화의 크기가 곧 해의 크기를 정한다는 뜻이라, 작은 초기화가 일반화에 유리하다는 경험칙의 가장 단순한 판입니다. 확률적 경사하강도 표본 하나의 기울기가 xix_i 방향이라 같은 행공간에 머물고 같은 해로 갑니다. 그래디언트 잡음이 어디로 흔드느냐는 비선형 모델에서는 중요하지만, 선형 최소제곱에서는 도착점을 바꾸지 못합니다.

조기 종료와 릿지

끝까지 돌리지 않고 tt 걸음에서 멈추면 어떻게 될까요. w0=0w_0 = 0 에서 위의 점화식을 풀면

ai(t)=[1−(1−ηsi2)t]ui⊤ysia_i(t) = \Big[1 - (1 - \eta s_i^2)^t\Big] \frac{u_i^\top y}{s_i}

이고, 릿지 해는 같은 자리에 si2/(si2+λ)s_i^2/(s_i^2 + \lambda) 가 곱해진 꼴이었습니다. 두 괄호를 필터 계수라 부릅니다. 각 특잇값 방향을 얼마나 받아들일지 정하는 0과 1 사이의 수입니다. q=ηtsi2q = \eta t s_i^2 로 두면 조기 종료의 필터는 대략 1−e−q1 - e^{-q}, 릿지에서 λ=1/(ηt)\lambda = 1/(\eta t) 로 두면 q/(1+q)q/(1 + q) 입니다. q=0.1q = 0.1 에서 0.095와 0.091, q=1q = 1 에서 0.632와 0.5, q=10q = 10 에서 0.99995와 0.909입니다. 큰 특잇값 방향은 둘 다 거의 다 받아들이고, 작은 특잇값 방향은 둘 다 qq 에 비례해 눌러 둡니다.

그러니 걸음 수 tt 는 정규화 세기 1/(ηt)1/(\eta t) 와 같은 노릇을 합니다. 오래 돌릴수록 작은 특잇값 방향이 열리고, 끝까지 돌리면 릿지 없는 회귀, 곧 보간 해가 됩니다. 첫머리에서 Nakkiran 등이 보고한 「학습 기간에 따른 이중 하강」이 이 그림으로 읽힙니다. 학습이 진행되며 유효 정규화가 약해지는 것은 모델을 키우는 것과 같은 축 위의 움직임이고, 작은 특잇값 방향이 열리며 잡음이 들어오는 시점에 시험 위험이 솟습니다.

거울 하강

경사하강이 고르는 것이 유클리드 노름인 것은 걸음을 유클리드 거리로 쟀기 때문입니다. 거리를 바꾸면 고르는 해도 바뀝니다. 강볼록 함수 ψ\psi 를 잡아 ∇ψ(wt+1)=∇ψ(wt)−η∇L(wt)\nabla\psi(w_{t+1}) = \nabla\psi(w_t) - \eta \nabla L(w_t) 로 걷는 방법을 거울 하강이라 부르고, ψ\psi 가 정하는 거리를

Dψ(w,w0)=ψ(w)−ψ(w0)−∇ψ(w0)⊤(w−w0)D_\psi(w, w_0) = \psi(w) - \psi(w_0) - \nabla\psi(w_0)^\top (w - w_0)

로 적어 브레그먼 발산이라 부릅니다. ψ=12∥w∥2\psi = \tfrac{1}{2}\lVert w \rVert^2 이면 거울 하강은 경사하강이고 브레그먼 발산은 12∥w−w0∥2\tfrac{1}{2}\lVert w - w_0 \rVert^2 입니다.

거울 하강의 암묵적 편향도 앞 절과 같은 논법으로 나옵니다. 기울기가 늘 행공간에 있으므로 ∇ψ(wt)−∇ψ(w0)\nabla\psi(w_t) - \nabla\psi(w_0) 이 늘 행공간에 있습니다. 반복이 보간 해 w∞w_\infty 로 수렴한다면 ∇ψ(w∞)−∇ψ(w0)=X⊤μ\nabla\psi(w_\infty) - \nabla\psi(w_0) = X^\top \mu 인 μ\mu 가 있고, 이것은 「Xw=yXw = y 아래에서 Dψ(w,w0)D_\psi(w, w_0) 최소화」의 라그랑주 조건 그 자체입니다. 목적함수가 볼록이고 제약이 선형이니 이 조건이 최적성의 충분조건이라, 거울 하강은 해 평면 위에서 브레그먼 발산이 가장 작은 점을 고릅니다.

이 틀은 선형 모델 밖으로 이어집니다. 파라미터를 w=u⊙u−v⊙vw = u \odot u - v \odot v 로 다시 쓴 대각 선형 신경망을 작은 초기화에서 경사하강으로 학습하면, 동역학이 특정 ψ\psi 의 거울 하강과 같아지고 초기화가 작을수록 ℓ1\ell_1 노름 최소 해에 가까워진다는 것이 Woodworth 등의 결과입니다. 같은 해 평면에서 성긴 해를 고른다는 뜻이고, 파라미터화만 바꿨는데 암묵적 편향의 기하가 바뀝니다. 분리 가능한 데이터에서 로지스틱 손실을 경사하강으로 줄이면 가중치의 크기는 끝없이 자라지만 방향은 최대 마진 해로 수렴한다는 Soudry 등의 결과도 같은 계열입니다. 손실이 해를 정하지 못하는 과매개변수 영역에서는 옵티마이저와 파라미터화가 정규화 항 노릇을 하고, 그 정규화 항이 무엇인지 적어 내는 것이 이 분야의 계산입니다.

다시 이중 하강으로

코드로 확인하기

이 글의 네 주장을 한 번에 확인합니다. 최소노름 해가 릿지의 극한이자 0에서 출발한 경사하강의 도착점인지, 특징 p개 모형의 정확한 위험 식이 시뮬레이션과 맞는지, 문턱에서 최소 고윳값이 0으로 가는지와 마르첸코–파스투르 적분이 분산 배수를 주는지, 스파이크와 긴 꼬리에서 보간이 해롭지 않은지입니다.

import numpy as np

rng = np.random.default_rng(0)

# 1) 최소노름 보간: 의사역행렬 = 릿지의 극한 = 0에서 출발한 경사하강
n, p = 30, 80
X = rng.standard_normal((n, p)); y = rng.standard_normal(n)
w_pinv = np.linalg.pinv(X) @ y
w_ridge = np.linalg.solve(X.T @ X + 1e-8 * np.eye(p), X.T @ y)
w = np.zeros(p); eta = 1 / np.linalg.norm(X, 2) ** 2
for _ in range(20000):
    w -= eta * X.T @ (X @ w - y)
print(np.abs(X @ w_pinv - y).max() < 1e-10,
      round(np.abs(w_ridge - w_pinv).max(), 6), round(np.abs(w - w_pinv).max(), 6))

# 2) 특징 p개 모형: 정확한 위험 공식과 시뮬레이션
n, d, sig2 = 100, 400, 0.1
b2 = 1 / np.arange(1, d + 1); b2 /= b2.sum(); beta = np.sqrt(b2)   # β_j² ∝ 1/j, ‖β‖² = 1
s = np.cumsum(b2)                                                  # s(p) = 앞 p개 특징의 신호 에너지

def risk(p):
    sp, e = s[p - 1], sig2 + 1 - s[p - 1]                          # e = 유효 잡음 분산
    if p < n - 1: return (1 - sp) + e * p / (n - p - 1)
    return (1 - sp) + sp * (1 - n / p) + e * n / (p - n - 1)

ps = [21, 60, 90, 120, 243, 400]
acc = {q: [] for q in ps}
for _ in range(300):
    Xf = rng.standard_normal((n, d)); yf = Xf @ beta + np.sqrt(sig2) * rng.standard_normal(n)
    for q in ps:
        bh = np.linalg.lstsq(Xf[:, :q], yf, rcond=None)[0]
        acc[q].append(np.sum((bh - beta[:q]) ** 2) + 1 - s[q - 1])
for q in ps:
    print(q, round(risk(q), 3), round(np.mean(acc[q]), 3))

# 3) 보간 문턱: 0이 아닌 최소 고윳값과 마르첸코–파스투르의 아래 끝
n = 400
for g in [0.25, 0.9, 1.0, 1.1, 4.0]:
    Z = rng.standard_normal((n, int(g * n)))
    ev = np.linalg.eigvalsh(Z @ Z.T / n if g > 1 else Z.T @ Z / n)
    print(g, round(ev[0], 4), round((1 - np.sqrt(g)) ** 2, 4))

for g in [0.5, 4.0]:                                               # 마르첸코–파스투르로 분산 배수 계산
    a, b = (1 - np.sqrt(g)) ** 2, (1 + np.sqrt(g)) ** 2
    t = np.linspace(a, b, 400001); t = (t[1:] + t[:-1]) / 2
    rho = np.sqrt((b - t) * (t - a)) / (2 * np.pi * g * t)          # 0이 아닌 부분의 밀도
    V = g * np.sum(rho / t) * (b - a) / 400000                     # (p/n) × ∫ ρ(λ)/λ dλ
    print(g, round(V, 4), round(g / (1 - g) if g < 1 else 1 / (g - 1), 4))

# 4) 양성 과적합: 스파이크 10개(고윳값 1) + 고윳값 c/m 인 꼬리 m개, 잡음 분산 1
n, k, sig2 = 200, 10, 1.0
for m, c in [(400, 20.0), (50000, 20.0), (50000, 2.0), (50000, 200.0)]:
    lam = np.r_[np.ones(k), np.full(m, c / m)]
    out = []
    for _ in range(20):
        X = rng.standard_normal((n, k + m)) * np.sqrt(lam)
        beta = np.zeros(k + m); beta[:k] = rng.standard_normal(k); beta /= np.linalg.norm(beta)
        y = X @ beta + np.sqrt(sig2) * rng.standard_normal(n)
        bh = X.T @ np.linalg.solve(X @ X.T, y)                     # 최소노름 보간 해
        out.append(np.sum(lam * (bh - beta) ** 2))
    approx = (c / (n + c)) ** 2 + sig2 * (k * n / (n + c) ** 2 + (n - k) / m)
    print(m, c, round(np.mean(out), 3), round(approx, 3))
True 0.0 0.0
21 0.592 0.592
60 0.884 0.883
90 3.49 3.409
120 1.807 1.756
243 0.743 0.753
400 0.783 0.789
0.25 0.2493 0.25
0.9 0.0028 0.0026
1.0 0.0 0.0
1.1 0.0028 0.0024
4.0 1.0126 1.0
0.5 1.0 1.0
4.0 0.3333 0.3333
400 20.0 1.013 0.525
50000 20.0 0.05 0.053
50000 2.0 0.045 0.053
50000 200.0 0.281 0.266

첫 줄은 세 해가 같다는 확인입니다. 의사역행렬 해가 학습 표본을 정확히 지나고, λ=10−8\lambda = 10^{-8} 의 릿지 해와 2만 걸음의 경사하강이 여섯째 자리까지 같은 점에 있습니다. 다음 여섯 줄이 특징 p개 모형입니다. 첫째 골 p=21p = 21 과 둘째 골 p=243p = 243 에서 식과 시뮬레이션이 맞고, 문턱 근처 p=90p = 90, 120120 에서 시뮬레이션이 조금 낮은 것은 앞에서 말한 긴 꼬리 때문입니다. 그 아래 다섯 줄에서 최소 고윳값이 γ=1\gamma = 1 에서 0으로 내려가고 양쪽에서 (1−γ)2(1 - \sqrt\gamma)^2 을 따르며, 그다음 두 줄에서 마르첸코–파스투르 밀도를 수치로 적분한 분산 배수가 γ/(1−γ)=1\gamma/(1 - \gamma) = 1 과 1/(γ−1)=0.3331/(\gamma - 1) = 0.333 을 정확히 줍니다. 마지막 넷이 양성 과적합입니다. 꼬리 50,000개에서는 잡음 분산 1을 보간하고도 위험이 0.05 안팎이고, 근사식이 그것을 맞힙니다. 꼬리 400개에서는 위험이 1을 넘고 근사식은 빗나갑니다. 위의 표와 숫자가 조금 다른 것은 다른 난수로 20번씩 뽑았기 때문입니다.

연습

  1. 표본 하나 x=(2,1,2)x = (2, 1, 2), y=6y = 6 에 대해 최소노름 보간 해와 그 노름을 구하고, 다른 보간 해 (3,0,0)(3, 0, 0) 의 노름과 견주세요.
    w∗=x y/∥x∥2=(2,1,2)⋅6/9=(4/3,2/3,4/3)w^* = x\, y / \lVert x \rVert^2 = (2, 1, 2) \cdot 6/9 = (4/3, 2/3, 4/3) 이고 노름은 16/9+4/9+16/9=2\sqrt{16/9 + 4/9 + 16/9} = 2 입니다. (3,0,0)(3, 0, 0) 은 2⋅3=62 \cdot 3 = 6 이라 해이지만 노름이 3입니다. 차이를 피타고라스로 보면 9=4+59 = 4 + 5, 곧 (3,0,0)−w∗(3, 0, 0) - w^* 의 길이 제곱이 5이고 이것은 xx 와 직교합니다.
  2. 등방 정규 모형에서 n=50n = 50, ∥β∥2=1\lVert \beta \rVert^2 = 1, σ2=1\sigma^2 = 1 일 때 p=20p = 20 과 p=80p = 80 의 정확한 기대 위험을 구하고, 같은 γ\gamma 에서의 극한값과 견주세요.
    p=20p = 20 은 분산만 남아 20/(50−20−1)=20/29=0.69020/(50 - 20 - 1) = 20/29 = 0.690, 극한은 γ=0.4\gamma = 0.4 에서 0.4/0.6=0.6670.4/0.6 = 0.667 입니다. p=80p = 80 은 (1−50/80)+50/(80−50−1)=0.375+1.724=2.099(1 - 50/80) + 50/(80 - 50 - 1) = 0.375 + 1.724 = 2.099, 극한은 γ=1.6\gamma = 1.6 에서 0.375+1/0.6=2.0420.375 + 1/0.6 = 2.042 입니다. 유한한 nn 의 값이 극한보다 조금 큰 것은 분모의 −1-1 때문입니다.
  3. 같은 모형에서 ∥β∥2=1\lVert \beta \rVert^2 = 1, σ2=0.09\sigma^2 = 0.09 일 때 과매개변수 영역의 극한 위험을 가장 작게 하는 γ\gamma 와 그때의 위험을 구하세요.
    r=1r = 1, σ=0.3\sigma = 0.3 이라 γ∗=r/(r−σ)=1/0.7=1.4286\gamma^* = r/(r - \sigma) = 1/0.7 = 1.4286 입니다. 위험은 (1−0.7)+0.09/0.4286=0.3+0.21=0.51(1 - 0.7) + 0.09/0.4286 = 0.3 + 0.21 = 0.51 입니다. 일반적으로 1−1/γ∗=σ/r1 - 1/\gamma^* = \sigma/r 라 최소 위험은 rσ+σ(r−σ)=σ(2r−σ)r\sigma + \sigma(r - \sigma) = \sigma(2r - \sigma) 이고, 0.3×1.7=0.510.3 \times 1.7 = 0.51 과 맞습니다.
  4. 고윳값이 4 하나와 1 여덟 개인 공분산에서 r0,R0,r1,R1r_0, R_0, r_1, R_1 을 구하고, 두 유효 차원 사이의 부등식이 성립하는지 확인하세요.
    합이 4+8=124 + 8 = 12, 제곱합이 16+8=2416 + 8 = 24 라 r0=12/4=3r_0 = 12/4 = 3, R0=144/24=6R_0 = 144/24 = 6 이고 3≤6≤93 \le 6 \le 9 입니다. 4를 빼면 꼬리가 1 여덟 개로 평평해 r1=8/1=8r_1 = 8/1 = 8, R1=64/8=8R_1 = 64/8 = 8 이고 8≤8≤648 \le 8 \le 64 입니다. 평평한 꼬리에서 두 유효 차원이 꼬리의 차원과 같아지는 경우입니다.
  5. 1번의 표본에서 경사하강을 w0=(1,1,1)w_0 = (1, 1, 1) 에서 시작하면 어느 해로 수렴하나요. 그 해의 노름은 최소노름 해보다 큰가요.
    기울기가 늘 xx 방향이라 w∞=w0+x (y−x⊤w0)/∥x∥2=(1,1,1)+(2,1,2)⋅(6−5)/9=(11/9,10/9,11/9)w_\infty = w_0 + x\,(y - x^\top w_0)/\lVert x \rVert^2 = (1, 1, 1) + (2, 1, 2)\cdot(6 - 5)/9 = (11/9, 10/9, 11/9) 입니다. 노름 제곱은 (121+100+121)/81=342/81=4.22(121 + 100 + 121)/81 = 342/81 = 4.22 라 노름 2.05로, 최소노름 해의 2보다 큽니다.
  6. 스파이크와 긴 꼬리 모형에서 n=100n = 100, k=5k = 5, c=10c = 10, m=20,000m = 20{,}000, σ2=1\sigma^2 = 1, ∥β∥=1\lVert \beta \rVert = 1 일 때 근사식으로 편향, 스파이크 분산, 꼬리 분산을 각각 구하세요.
    편향은 (10/110)2=0.0083(10/110)^2 = 0.0083, 스파이크 분산은 5×100/1102=500/12100=0.04135 \times 100/110^2 = 500/12100 = 0.0413, 꼬리 분산은 (100−5)/20000=0.0048(100 - 5)/20000 = 0.0048 이라 합이 0.054입니다. 잡음 분산 1을 보간하면서 아무것도 안 배운 예측의 위험 1보다 스무 배 가까이 낮습니다.

첫머리의 곡선으로 돌아갑니다. 학습 오차가 0에 닿는 자리에서 시험 오차가 솟은 것은 그 자리에서 보간 해를 고를 여지가 사라지고, 특징 행렬의 작은 특잇값들이 덩어리로 0에 붙어 레이블 잡음을 부풀리기 때문이었습니다. 등방 모형에서 그 증폭 배수는 정확히 γ/(1−γ)\gamma/(1 - \gamma) 와 1/(γ−1)1/(\gamma - 1) 이었습니다. 그 너머에서 다시 내려간 것은 여분의 차원이 외운 잡음을 얇게 흩기 때문이고, 둘째 골이 첫째 골보다 낮아지려면 여분의 차원이 신호를 빼앗지 않아야 했습니다. 그 조건이 신호를 싣는 소수의 스파이크와 잡음을 받는 넓은 꼬리, 곧 유효 차원 rk,Rkr_k, R_k 로 적힌 양성 과적합의 조건입니다. 그리고 그 많은 보간 해 가운데 무엇이 나오는지는 손실이 아니라 옵티마이저와 초기화와 파라미터화가 정했습니다. 레이블 잡음을 늘리면 봉우리가 높아진다는 관찰도 이제 식으로 읽힙니다. 봉우리의 높이는 잡음 분산에 증폭 배수를 곱한 것이었습니다.

이것으로 「확률 부등식과 일반화」 단원 A3를 닫습니다. 집중부등식은 표본 하나가 기댓값에서 얼마나 벗어나는지를, 일반화 경계는 그 벗어남을 가설 집합 전체에 대해 묶는 법과 그것이 공허해지는 자리를 보였고, 이 글은 경계 대신 위험을 정확히 계산해 그 공허한 자리에서 실제로 무슨 일이 일어나는지를 보였습니다. 다음 글 고급 11번 · 「볼록해석: 하위기울기, 강볼록성, 매끄러움의 쌍대」는 A4 「볼록해석과 최적화 이론」 단원을 엽니다. 이 글에서 라그랑주 조건 한 줄로 넘어간 거울 하강의 최적성과 브레그먼 발산이 거기서 제 자리를 찾습니다.


읽어주셔서 감사합니다. 😊

LATEST

수학의 최신 글

수학2026.11.17

다양체 위의 최적화: 직교 제약과 Muon의 직교화가 하는 일

차트·접공간·리만 계량·측지선·후퇴로 다양체를 세우고, 스티펠·그라스만·양정치 행렬·확률 단체의 접공간과 사영을 계산한 뒤, 리만 그래디언트가 유클리드 그래디언트의 접공간 사영임을 증명하고 극분해 후퇴와 뉴턴–슐츠 반복의 수렴 조건을 다룹니다.

고급46 MIN
수학2026.11.17

프리컨디셔닝의 이론: Adam에서 K-FAC·Shampoo·Muon까지 한 줄로

갱신 −ηP⁻¹∇를 노름의 최급강하로 읽고 헤세·가우스–뉴턴·피셔·경험적 피셔의 관계를 정리한 뒤, 준뉴턴과 3차 정규화, K-FAC의 크로네커 인수분해와 그 독립 가정, Shampoo의 −1/4 지수, Muon의 스펙트럴 노름 유도를 차례로 세워 이들이 어디서 일치하는지 보입니다.

고급41 MIN
수학2026.11.17

확률적 근사와 SGD의 연속 극한: 수렴한다는 말의 정확한 뜻

로빈스–먼로 조건과 마팅게일 잡음으로 SGD의 수렴을 정확히 정의하고, 볼록·강볼록·PL·비볼록에서의 수렴률과 오라클 하한을 계산한 뒤, SGD를 확률미분방정식으로 읽어 학습률/배치가 온도가 되는 관점과 안정성의 가장자리를 다룹니다.

고급48 MIN