수학

MATH / 고급 9번

일반화 경계: 고전 이론이 공허해지는 자리와 PAC-Bayes

균등수렴의 틀에서 성장함수·VC 차원·Sauer 보조정리와 Rademacher 대칭화를 증명하고, 무작위 라벨을 외우는 신경망 앞에서 그 경계가 왜 1을 넘는지 계산합니다. 이어 도노스커–바라단 변분식으로 PAC-Bayes 정리를 증명하고, KL 항과 평평한 최소점으로 1보다 작은 경계를 직접 얻습니다.

PALDYN Team71 MIN READ

이미지 분류 모델을 만드는 팀이 CIFAR-10 학습 이미지 50,000장으로 파라미터 120만 개짜리 합성곱 신경망을 학습합니다. 학습 정확도는 100%이고 시험 정확도는 90% 근처입니다. 한 사람이 장난삼아 라벨을 전부 무작위로 섞어 같은 신경망을 같은 설정으로 다시 돌립니다. 시간이 조금 더 걸릴 뿐 학습 정확도는 또 100%가 되고, 시험 정확도는 찍는 것과 같은 10%로 떨어집니다. 이 관찰은 Zhang 등이 2017년에 「딥러닝을 이해하려면 일반화를 다시 생각해야 한다」는 제목의 논문으로 보고해 널리 알려진 것입니다.

리뷰에서 질문이 셋 나옵니다. 첫째, 교과서의 일반화 경계에 이 신경망을 넣으면 어떤 숫자가 나오나요. 둘째, 그 숫자가 1을 넘는다면 그 까닭은 무엇이고, 진짜 라벨과 무작위 라벨이 같은 경계를 받는 것은 이론의 어느 자리 때문인가요. 셋째, 진짜 라벨로 학습한 신경망에 대해서만 「시험 오차가 이 값을 넘지 않는다」고 1보다 작은 숫자를 말해 주는 경계가 있나요. 이 글은 셋에 답합니다. 앞의 둘은 균등수렴과 그것을 재는 두 자, VC 차원과 Rademacher 복잡도가 맡고, 마지막은 PAC-Bayes 정리가 맡습니다. 지난 글의 회프딩 부등식·맥디아미드 부등식·합집합 경계를 도구로 그대로 받아 씁니다.

균등수렴

경험위험과 실제위험

입력과 라벨의 짝 z=(x,y)z = (x, y) 가 모르는 분포 D\mathcal{D} 에서 나오고, 표본 S=(z1,…,zn)S = (z_1, \dots, z_n) 은 그 분포에서 독립으로 뽑은 nn 개입니다. 가설 hh 는 입력을 받아 예측을 내는 함수이고, 손실 ℓ(h,z)\ell(h, z) 는 값이 [0,1][0, 1] 안에 있다고 둡니다. 분류라면 틀렸을 때 1, 맞았을 때 0인 0-1 손실입니다. 이때

R(h)=Ez∼D[ℓ(h,z)],R^S(h)=1n∑i=1nℓ(h,zi)R(h) = \mathbb{E}_{z \sim \mathcal{D}}[\ell(h, z)], \qquad \hat{R}_S(h) = \frac{1}{n} \sum_{i=1}^{n} \ell(h, z_i)

의 앞쪽을 실제위험, 뒤쪽을 경험위험이라 부릅니다. 실제위험은 분포 전체에서 평균한 손실이라 시험 오차가 어림하려는 값이고, 경험위험은 표본 위에서 평균한 손실이라 학습 오차입니다. 둘의 차이 R(h)−R^S(h)R(h) - \hat{R}_S(h) 가 일반화 간극이고, 일반화 경계란 이 간극을 표본 크기와 가설의 성질로 위에서 누르는 부등식입니다.

hh 하나를 표본과 상관없이 미리 정해 두면 간극은 지난 글의 회프딩 부등식 그대로입니다. ℓ(h,zi)\ell(h, z_i) 들이 [0,1][0, 1] 안의 독립 확률변수이고 평균이 R(h)R(h) 이므로

Pr⁡[R(h)−R^S(h)>ε]≤e−2nε2\Pr\big[R(h) - \hat{R}_S(h) > \varepsilon\big] \le e^{-2n\varepsilon^2}

입니다. 문제는 학습이 hh 를 미리 정해 두지 않는다는 데 있습니다. 가설 집합 H\mathcal{H} 안에서 경험위험이 가장 작은 것을 고르는 규칙을 경험위험 최소화라 하는데, 이렇게 고른 h^\hat{h} 는 표본을 보고 고른 것이라 ℓ(h^,zi)\ell(\hat{h}, z_i) 들이 더는 독립이 아닙니다. 표본에서 우연히 잘 맞은 가설을 일부러 골랐으니 그 경험위험은 실제위험보다 낮은 쪽으로 치우칩니다.

유한 가설 집합

H\mathcal{H} 가 유한하면 합집합 경계가 이 치우침을 값으로 막습니다. 가설마다 나쁜 사건 {R(h)−R^S(h)>ε}\{R(h) - \hat{R}_S(h) > \varepsilon\} 의 확률이 e−2nε2e^{-2n\varepsilon^2} 이하이니, 그중 하나라도 일어날 확률은 ∣H∣e−2nε2|\mathcal{H}| e^{-2n\varepsilon^2} 이하입니다. 이것을 δ\delta 와 같게 놓고 ε\varepsilon 에 대해 풀면, 확률 1−δ1 - \delta 이상으로 모든 h∈Hh \in \mathcal{H} 에서 동시에

R(h)≤R^S(h)+log⁡∣H∣+log⁡(1/δ)2nR(h) \le \hat{R}_S(h) + \sqrt{\frac{\log|\mathcal{H}| + \log(1/\delta)}{2n}}

입니다. 「동시에」가 핵심입니다. 모든 가설에서 한꺼번에 성립하므로 표본을 보고 고른 h^\hat{h} 에도 성립합니다. 값을 넣어 보면 가설이 백만 개, n=50,000n = 50{,}000, δ=0.05\delta = 0.05 일 때 둘째 항은 0.0130입니다. 백만 개 가운데 하나를 골랐는데도 간극의 상한이 1.3%포인트라는 것은 log⁡∣H∣\log|\mathcal{H}| 가 가설 수를 로그로 줄여 세기 때문입니다.

이 식은 나중에 다시 만납니다. 가설을 몇 비트로 적을 수 있는가를 세는 압축 경계도, PAC-Bayes 정리에 점 하나에 몰린 사후분포를 넣은 것도 결국 이 식으로 돌아옵니다. 그러나 가설 집합은 대개 무한합니다. 문턱값 하나로 가르는 분류기만 해도 문턱의 후보가 실수 전체입니다. ∣H∣=∞|\mathcal{H}| = \infty 를 넣으면 경계가 무한대가 되므로, 무한한 집합의 「실질적인 크기」를 셀 다른 방법이 필요합니다.

최악의 간극

모든 가설에서 동시에 간극이 작다는 것을 식 하나로 적으면

sup⁡h∈H∣R(h)−R^S(h)∣≤ε\sup_{h \in \mathcal{H}} \big|R(h) - \hat{R}_S(h)\big| \le \varepsilon

입니다. nn 이 커질 때 이 상한이 0으로 가는 성질을 균등수렴이라 부릅니다. 가설 하나에서의 수렴이 대수의 법칙이라면 균등수렴은 가설 집합 전체를 한꺼번에 덮는 대수의 법칙이고, 경험위험 최소화가 믿을 만한 이유가 정확히 이것입니다. 균등수렴이 성립하면 R(h^)≤R^S(h^)+ε≤R^S(h∗)+ε≤R(h∗)+2εR(\hat{h}) \le \hat{R}_S(\hat{h}) + \varepsilon \le \hat{R}_S(h^*) + \varepsilon \le R(h^*) + 2\varepsilon 이 되어, 표본으로 고른 가설이 집합 안의 가장 좋은 가설 h∗h^* 와 2ε2\varepsilon 안쪽으로 맞섭니다.

작은 예로 그 모습을 봅니다. 입력 xx 가 [0,1][0, 1] 에서 고르게 나오고, 참 라벨은 x≥0.4x \ge 0.4 이면 1, 아니면 0인데 라벨의 10%가 뒤집혀 있습니다. 가설은 문턱 tt 를 정해 x≥tx \ge t 를 1로 부르는 분류기입니다. 실제위험은 손으로 계산되어 R(t)=0.1+0.8∣t−0.4∣R(t) = 0.1 + 0.8|t - 0.4| 입니다. 문턱이 0.4에서 멀어질수록 잘못 부르는 구간의 길이가 늘고, 그 구간에서는 뒤집히지 않은 90%를 틀리고 뒤집힌 10%를 맞히므로 기울기가 0.8입니다.

문턱 분류기의 실제위험과 경험위험을 문턱 t 에 따라 그린 그림. 실제위험은 t = 0.4 에서 0.1 로 가장 낮은 V자 꺾은선이고, 표본 30개로 센 경험위험은 그 주위를 오르내리는 계단이다. 경험위험 최소화가 고르는 구간 0.3910.431 에서 경험위험은 0.033, 실제위험은 0.100.125 이고, 두 곡선이 가장 멀리 벌어지는 곳은 t = 0.115 근처의 0.128 이다

표본 30개를 뽑았더니 하나가 뒤집혀 있었습니다. 경험위험은 문턱이 두 이웃한 표본 사이를 지날 때만 바뀌는 계단이고, 가장 낮은 계단은 문턱이 0.391과 0.431 사이에 있을 때의 1/30=0.0331/30 = 0.033 입니다. 그 구간에서 실제위험은 0.100에서 0.125이니 고른 가설의 간극은 0.07에서 0.09입니다. 그런데 그림에서 두 곡선이 가장 멀리 벌어진 곳은 고른 자리가 아니라 t=0.115t = 0.115 근처로, 실제위험 0.328과 경험위험 0.200이 0.128만큼 벌어져 있습니다. 균등수렴의 상한은 이 가장 나쁜 자리까지 덮어야 하므로, 고른 가설 하나의 간극보다 늘 큽니다. 이 여분이 고전 이론이 치르는 값이고, 뒤에서 신경망 앞에서 경계가 무너지는 것도 이 여분이 집합 전체의 크기를 따라 자라기 때문입니다.

VC 차원

성장함수

문턱 분류기는 무한히 많지만 표본 nn 개 위에서 보면 다르게 부를 수 있는 방법이 n+1n + 1 가지뿐입니다. 점을 정렬해 두면 문턱이 몇 번째 점과 몇 번째 점 사이에 오는지만이 예측을 바꾸기 때문입니다. 이 관찰을 일반화합니다. 점 x1,…,xnx_1, \dots, x_n 위에서 가설 집합이 만들어 내는 라벨 벡터 (h(x1),…,h(xn))(h(x_1), \dots, h(x_n)) 의 서로 다른 개수를 세고, 그 개수를 점의 배치에 대해 최대로 한 것

ΠH(n)=max⁡x1,…,xn∣{(h(x1),…,h(xn)):h∈H}∣\Pi_{\mathcal{H}}(n) = \max_{x_1, \dots, x_n} \big|\{(h(x_1), \dots, h(x_n)) : h \in \mathcal{H}\}\big|

을 성장함수라 부릅니다. 두 갈래 분류에서는 라벨 벡터가 2n2^n 가지밖에 없으니 언제나 ΠH(n)≤2n\Pi_{\mathcal{H}}(n) \le 2^n 입니다. 성장함수는 무한한 집합을 「표본 위에서 실제로 구별되는 가설의 수」로 바꿔 세는 자이고, 앞 절의 log⁡∣H∣\log|\mathcal{H}| 자리에 log⁡ΠH(n)\log \Pi_{\mathcal{H}}(n) 이 들어갈 수 있다는 것이 다음 절에서 증명할 내용입니다.

산산조각

어떤 점 nn 개에 대해 2n2^n 가지 라벨을 전부 만들어 낼 수 있으면, 가설 집합이 그 점들을 산산조각 낸다고 말합니다. 그리고 산산조각 낼 수 있는 점 집합의 가장 큰 크기를 VC 차원이라 부르고 dVCd_{\mathrm{VC}} 로 적습니다. 정의에서 곧바로 n≤dVCn \le d_{\mathrm{VC}} 이면 ΠH(n)=2n\Pi_{\mathcal{H}}(n) = 2^n 이고 n>dVCn > d_{\mathrm{VC}} 이면 ΠH(n)<2n\Pi_{\mathcal{H}}(n) < 2^n 입니다.

예를 셋 봅니다. 한쪽으로만 부르는 문턱 분류기는 점 하나는 두 가지로 다 부를 수 있지만, 점 둘 x1<x2x_1 < x_2 에 「왼쪽 1, 오른쪽 0」을 줄 수 없어 VC 차원이 1입니다. 구간 [a,b][a, b] 안을 1로 부르는 분류기는 점 둘을 산산조각 내지만 세 점의 「1, 0, 1」은 못 만들어 VC 차원이 2입니다. kk 차원 공간의 반공간 {x:w⊤x+b≥0}\{x : w^\top x + b \ge 0\} 은 VC 차원이 k+1k + 1 입니다. 평면이라면 일반 위치에 놓인 세 점은 어떻게 칠해도 직선 하나로 가를 수 있지만, 네 점은 대각선끼리 같은 색을 칠한 배치를 직선으로 못 가릅니다. 세 예 모두 VC 차원이 조절할 수 있는 숫자의 개수와 맞아떨어지지만 일반적으로는 그렇지 않습니다. sin⁡(ωx)\sin(\omega x) 의 부호로 부르는 분류기는 숫자가 ω\omega 하나뿐인데 VC 차원이 무한합니다. 파라미터 수와 VC 차원이 다른 것이라는 사실을 뒤에서 신경망을 따질 때 다시 씁니다.

Sauer 보조정리

VC 차원이 유한하면 성장함수가 지수에서 다항식으로 꺾입니다. 이것이 Sauer 보조정리입니다. dVC=dd_{\mathrm{VC}} = d 이면 모든 nn 에서

ΠH(n)≤∑i=0d(ni)≤(end)d(n≥d)\Pi_{\mathcal{H}}(n) \le \sum_{i=0}^{d} \binom{n}{i} \le \left(\frac{en}{d}\right)^{d} \quad (n \ge d)

입니다. 첫 부등식의 증명은 n+dn + d 에 대한 귀납법이고, 개요는 이렇습니다. 점 nn 개 위의 라벨 벡터 집합을 AA 라 하고 마지막 점을 떼어 냅니다. 앞의 n−1n - 1 개에서 보이는 라벨 벡터의 집합을 A1A_1, 그 가운데 마지막 점에 0과 1을 둘 다 붙여 AA 에 들어 있는 것의 집합을 A2A_2 라 하면 ∣A∣=∣A1∣+∣A2∣|A| = |A_1| + |A_2| 입니다. A1A_1 은 VC 차원이 여전히 dd 이하이고, A2A_2 는 d−1d - 1 이하입니다. A2A_2 가 어떤 점 집합 TT 를 산산조각 내면 AA 는 TT 에 마지막 점을 더한 것까지 산산조각 내기 때문입니다. 귀납 가정을 두 쪽에 쓰고 파스칼의 항등식 (n−1i)+(n−1i−1)=(ni)\binom{n-1}{i} + \binom{n-1}{i-1} = \binom{n}{i} 로 더하면 끝납니다. 둘째 부등식은 d/n≤1d/n \le 1 을 써서

∑i=0d(ni)≤(nd)d∑i=0n(ni)(dn)i=(nd)d(1+dn)n≤(nd)ded\sum_{i=0}^{d} \binom{n}{i} \le \left(\frac{n}{d}\right)^{d} \sum_{i=0}^{n} \binom{n}{i} \left(\frac{d}{n}\right)^{i} = \left(\frac{n}{d}\right)^{d} \left(1 + \frac{d}{n}\right)^{n} \le \left(\frac{n}{d}\right)^{d} e^{d}

로 얻습니다.

VC 차원이 10 인 가설 집합의 성장함수를 밑이 2 인 로그로 그린 그림. 가로축은 표본 크기 n 이 0 에서 100 까지, 세로축은 비트 수다. 2 의 n 제곱은 기울기 1 인 직선이고, Sauer 상한은 n = 10 까지 그 직선과 겹치다가 꺾여 n = 100 에서 44.1 비트에 머문다. (en/d)^d 상한은 47.6 비트다

숫자로 보면 꺾임이 분명합니다. d=10d = 10 일 때 n=20n = 20 이면 라벨 벡터가 최대 616,666가지로, 가능한 1,048,576가지의 59%입니다. n=100n = 100 이면 약 1.94×10131.94 \times 10^{13} 가지인데 가능한 수는 1.27×10301.27 \times 10^{30} 이라, 비트로 세면 100비트 가운데 44.1비트만 씁니다. 표본이 늘수록 가설 집합이 표본 위에서 낼 수 있는 패턴의 비율이 빠르게 0으로 갑니다. 이 꺾임 덕분에 log⁡ΠH(n)≤dlog⁡(en/d)\log \Pi_{\mathcal{H}}(n) \le d \log(en/d) 가 nn 에 대해 로그로만 자라고, 그것을 nn 으로 나눈 값이 0으로 가 균등수렴이 섭니다. 반대로 VC 차원이 표본 수 이상이면 꺾이기 전의 구간, 곧 ΠH(n)=2n\Pi_{\mathcal{H}}(n) = 2^n 인 구간에 머물러 아무것도 줄지 않습니다.

Rademacher 복잡도

라데마허 평균

성장함수는 0-1 손실처럼 값이 둘뿐인 경우에만 셀 수 있습니다. 손실이 실수값이어도 쓸 수 있고 표본 자체에 맞춰 재는 자가 Rademacher 복잡도입니다. 값이 +1+1 과 −1-1 이 반반인 독립 확률변수 σ1,…,σn\sigma_1, \dots, \sigma_n 을 라데마허 변수라 부릅니다. 함수 집합 F\mathcal{F} (지금은 f(z)=ℓ(h,z)f(z) = \ell(h, z) 꼴의 손실 함수들)와 표본 SS 에 대해

R^S(F)=Eσ[sup⁡f∈F1n∑i=1nσif(zi)],Rn(F)=ES[R^S(F)]\hat{\mathfrak{R}}_S(\mathcal{F}) = \mathbb{E}_{\sigma}\left[\sup_{f \in \mathcal{F}} \frac{1}{n} \sum_{i=1}^{n} \sigma_i f(z_i)\right], \qquad \mathfrak{R}_n(\mathcal{F}) = \mathbb{E}_{S}\big[\hat{\mathfrak{R}}_S(\mathcal{F})\big]

의 앞쪽을 경험 Rademacher 복잡도, 뒤쪽을 그 기댓값이라 부릅니다. 읽는 법은 이렇습니다. 표본마다 동전을 던져 무작위 부호를 붙여 놓고, 함수 집합 안에서 그 부호와 가장 잘 맞는 함수를 골랐을 때의 상관을 잽니다. 잡음에 지나지 않는 부호까지 잘 따라가는 집합일수록 값이 크고, 그만큼 표본에 우연히 맞춰질 여지가 크다는 뜻입니다.

앞 절의 문턱 분류기로 값을 재 봅니다. 점 100개 위에서 문턱을 움직이며 부호와의 상관을 최대로 하는 일을 무작위 부호 20만 벌에 대해 되풀이하면 평균이 0.150입니다. 집합이 아무 부호나 다 따라갈 수 있으면, 곧 표본을 산산조각 내면 값은 최대인 1에 닿습니다. 이 「1」이 장면의 신경망 앞에서 다시 나옵니다.

대칭화

이 절의 주인공인 정리를 씁니다. [0,1][0, 1] 값의 함수 집합 F\mathcal{F} 에 대해, Ef=Ez∼Df(z)\mathbb{E}f = \mathbb{E}_{z \sim \mathcal{D}} f(z) 와 E^Sf=1n∑if(zi)\hat{\mathbb{E}}_S f = \frac{1}{n}\sum_i f(z_i) 로 적으면

ES[sup⁡f∈F(Ef−E^Sf)]≤2 Rn(F)\mathbb{E}_{S}\left[\sup_{f \in \mathcal{F}} \big(\mathbb{E}f - \hat{\mathbb{E}}_S f\big)\right] \le 2\,\mathfrak{R}_n(\mathcal{F})

입니다. 증명에 쓰는 장치가 대칭화이고, 그 재료가 고스트 표본입니다. 고스트 표본은 SS 와 같은 분포에서 독립으로 하나 더 뽑은 표본 S′=(z1′,…,zn′)S' = (z'_1, \dots, z'_n) 으로, 실제로 모으지 않고 증명 안에서만 쓰는 가상의 표본입니다.

대칭화 논법을 세 단계로 그린 그림. 위 줄은 표본 S 의 칸 z1 부터 zn, 아래 줄은 고스트 표본 S′ 의 칸 z′1 부터 z′n 이다. 칸마다 위아래 짝을 바꾸는 양방향 화살표에 σi 가 붙어 있다. 오른쪽에 세 걸음이 차례로 적혀 있다: 실제위험을 고스트 표본의 평균으로 바꾼다, 짝을 바꿔도 분포가 같아 차이마다 부호 σi 를 붙인다, 합의 상한을 둘로 갈라 2 Rademacher 복잡도를 얻는다

첫 걸음입니다. Ef=ES′[E^S′f]\mathbb{E}f = \mathbb{E}_{S'}[\hat{\mathbb{E}}_{S'} f] 이고 E^Sf\hat{\mathbb{E}}_S f 는 S′S' 와 무관하므로

sup⁡f(Ef−E^Sf)=sup⁡fES′[E^S′f−E^Sf]≤ES′[sup⁡f(E^S′f−E^Sf)]\sup_{f} \big(\mathbb{E}f - \hat{\mathbb{E}}_S f\big) = \sup_{f} \mathbb{E}_{S'}\big[\hat{\mathbb{E}}_{S'} f - \hat{\mathbb{E}}_S f\big] \le \mathbb{E}_{S'}\Big[\sup_{f} \big(\hat{\mathbb{E}}_{S'} f - \hat{\mathbb{E}}_S f\big)\Big]

입니다. 부등호는 기댓값의 상한이 상한의 기댓값을 넘지 않는다는 것이고, 어느 ff 하나에서든 ES′[⋅]≤ES′[sup⁡f⋅]\mathbb{E}_{S'}[\cdot] \le \mathbb{E}_{S'}[\sup_f \cdot] 이므로 왼쪽의 상한도 그렇습니다. 양변을 SS 로 평균하면 왼쪽은 증명할 식의 왼쪽이 되고, 오른쪽은 SS 와 S′S' 를 함께 평균한 ES,S′[sup⁡f1n∑i(f(zi′)−f(zi))]\mathbb{E}_{S, S'}[\sup_f \frac{1}{n}\sum_i (f(z'_i) - f(z_i))] 가 됩니다. 실제위험이라는 모르는 값이 사라지고 표본 둘의 차이만 남았습니다.

둘째 걸음이 대칭화입니다. ziz_i 와 zi′z'_i 는 같은 분포에서 독립으로 나왔으므로 둘을 맞바꿔도 (S,S′)(S, S') 의 결합분포가 그대로입니다. 맞바꾸면 f(zi′)−f(zi)f(z'_i) - f(z_i) 의 부호만 뒤집힙니다. 그러니 각 ii 마다 동전을 던져 바꿀지 말지를 정해도 분포가 그대로이고, 이것은 차이마다 라데마허 변수 σi\sigma_i 를 곱하는 것과 같습니다.

ES,S′[sup⁡f1n∑i(f(zi′)−f(zi))]=ES,S′,σ[sup⁡f1n∑iσi(f(zi′)−f(zi))]\mathbb{E}_{S, S'}\Big[\sup_{f} \frac{1}{n}\sum_{i} \big(f(z'_i) - f(z_i)\big)\Big] = \mathbb{E}_{S, S', \sigma}\Big[\sup_{f} \frac{1}{n}\sum_{i} \sigma_i \big(f(z'_i) - f(z_i)\big)\Big]

셋째 걸음입니다. 합의 상한은 상한의 합을 넘지 않으므로 오른쪽은

≤ES′,σ[sup⁡f1n∑iσif(zi′)]+ES,σ[sup⁡f1n∑i(−σi)f(zi)]=2 Rn(F)\le \mathbb{E}_{S', \sigma}\Big[\sup_{f} \frac{1}{n}\sum_{i} \sigma_i f(z'_i)\Big] + \mathbb{E}_{S, \sigma}\Big[\sup_{f} \frac{1}{n}\sum_{i} (-\sigma_i) f(z_i)\Big] = 2\,\mathfrak{R}_n(\mathcal{F})

입니다. 마지막 등호는 −σi-\sigma_i 가 σi\sigma_i 와 같은 분포를 가지고 S′S' 가 SS 와 같은 분포를 가지기 때문입니다. 증명이 끝났습니다.

기댓값 경계를 확률 경계로 바꾸는 것은 지난 글의 맥디아미드 부등식입니다. Φ(S)=sup⁡f(Ef−E^Sf)\Phi(S) = \sup_f(\mathbb{E}f - \hat{\mathbb{E}}_S f) 는 표본 하나를 바꾸면 E^Sf\hat{\mathbb{E}}_S f 가 어느 ff 에서든 1/n1/n 이하로만 움직이므로 상한도 1/n1/n 이하로만 움직입니다. 그러니 확률 1−δ1 - \delta 이상으로 Φ(S)≤EΦ+log⁡(1/δ)/(2n)\Phi(S) \le \mathbb{E}\Phi + \sqrt{\log(1/\delta)/(2n)} 이고, 대칭화와 합치면 모든 f∈Ff \in \mathcal{F} 에서

Ef≤E^Sf+2 Rn(F)+log⁡(1/δ)2n\mathbb{E}f \le \hat{\mathbb{E}}_S f + 2\,\mathfrak{R}_n(\mathcal{F}) + \sqrt{\frac{\log(1/\delta)}{2n}}

입니다. R^S\hat{\mathfrak{R}}_S 도 표본 하나에 1/n1/n 이하로 움직이므로 맥디아미드를 한 번 더 쓰고 δ\delta 를 반씩 나누면, 기댓값 대신 표본에서 계산하는 2R^S(F)+3log⁡(2/δ)/(2n)2\hat{\mathfrak{R}}_S(\mathcal{F}) + 3\sqrt{\log(2/\delta)/(2n)} 로 바꿀 수 있습니다. 이쪽이 장면에서 쓸 형태입니다.

Massart 보조정리

Rademacher 복잡도와 성장함수를 잇는 다리가 Massart 보조정리입니다. Rn\mathbb{R}^n 안의 유한 집합 AA 의 원소가 모두 길이 rr 이하이면

Eσ[max⁡a∈A1n∑i=1nσiai]≤r2log⁡∣A∣n\mathbb{E}_{\sigma}\left[\max_{a \in A} \frac{1}{n}\sum_{i=1}^{n} \sigma_i a_i\right] \le \frac{r\sqrt{2\log|A|}}{n}

입니다. 증명은 지수를 씌우는 지난 글의 방식 그대로입니다. λ>0\lambda > 0 에 대해 젠센 부등식으로 지수를 기댓값 안으로 넣고, 최댓값을 합으로 늘리고, 독립성으로 곱으로 쪼갭니다.

eλE[max⁡a∑iσiai]≤E[eλmax⁡a∑iσiai]≤∑a∈A∏i=1nE[eλσiai]=∑a∈A∏i=1ncosh⁡(λai)≤∑a∈Aeλ2∥a∥2/2≤∣A∣ eλ2r2/2\begin{aligned} e^{\lambda \mathbb{E}[\max_a \sum_i \sigma_i a_i]} &\le \mathbb{E}\big[e^{\lambda \max_a \sum_i \sigma_i a_i}\big] \le \sum_{a \in A} \prod_{i=1}^{n} \mathbb{E}\big[e^{\lambda \sigma_i a_i}\big] \\ &= \sum_{a \in A} \prod_{i=1}^{n} \cosh(\lambda a_i) \le \sum_{a \in A} e^{\lambda^2 \lVert a \rVert^2 / 2} \le |A|\, e^{\lambda^2 r^2 / 2} \end{aligned}

넷째 줄의 cosh⁡x≤ex2/2\cosh x \le e^{x^2/2} 는 두 테일러 급수를 항마다 견주면 나옵니다((2k)!≥2kk!(2k)! \ge 2^k k!). 로그를 취하고 λ\lambda 로 나누면 E[max⁡a∑iσiai]≤log⁡∣A∣/λ+λr2/2\mathbb{E}[\max_a \sum_i \sigma_i a_i] \le \log|A|/\lambda + \lambda r^2/2 이고, 오른쪽을 가장 작게 하는 λ=2log⁡∣A∣/r\lambda = \sqrt{2\log|A|}/r 를 넣으면 r2log⁡∣A∣r\sqrt{2\log|A|} 입니다. 양변을 nn 으로 나누면 끝입니다.

0-1 손실에 쓰면 VC 경계가 나옵니다. 표본 위에서 손실 벡터 (ℓ(h,z1),…,ℓ(h,zn))(\ell(h, z_1), \dots, \ell(h, z_n)) 은 성분이 0 아니면 1이라 길이가 n\sqrt{n} 이하이고, 라벨이 정해져 있으니 서로 다른 손실 벡터의 수는 예측 벡터의 수, 곧 ΠH(n)\Pi_{\mathcal{H}}(n) 이하입니다. 그러므로 R^S≤2log⁡ΠH(n)/n\hat{\mathfrak{R}}_S \le \sqrt{2\log \Pi_{\mathcal{H}}(n)/n} 이고, Sauer를 넣어 대칭화와 맥디아미드에 합치면 확률 1−δ1 - \delta 이상으로 모든 hh 에서

R(h)≤R^S(h)+22dlog⁡(en/d)n+log⁡(1/δ)2nR(h) \le \hat{R}_S(h) + 2\sqrt{\frac{2 d \log(en/d)}{n}} + \sqrt{\frac{\log(1/\delta)}{2n}}

입니다. 이것이 VC 경계의 한 형태입니다. 앞의 문턱 분류기에 Massart를 쓰면 n=100n = 100 에서 2log⁡101/100=0.304\sqrt{2\log 101/100} = 0.304 로, 실측 0.150의 두 배쯤입니다. 상한은 최악의 배치를 덮으려고 그만큼 여유를 둡니다.

마진 경계

함수 값이 실수인 분류기, 예컨대 선형 점수 fw(x)=w⊤xf_w(x) = w^\top x 의 부호로 부르는 분류기에서는 VC 차원 대신 노름으로 복잡도를 잴 수 있습니다. ∥w∥≤B\lVert w \rVert \le B 인 집합과 ∥xi∥≤X\lVert x_i \rVert \le X 인 표본에서 코시–슈바르츠와 젠센으로

R^S=1nEσ[sup⁡∥w∥≤Bw⊤∑iσixi]=BnEσ∥∑iσixi∥≤Bn∑i∥xi∥2≤BXn\hat{\mathfrak{R}}_S = \frac{1}{n}\mathbb{E}_\sigma\Big[\sup_{\lVert w \rVert \le B} w^\top \sum_i \sigma_i x_i\Big] = \frac{B}{n}\mathbb{E}_\sigma\Big\lVert \sum_i \sigma_i x_i \Big\rVert \le \frac{B}{n}\sqrt{\sum_i \lVert x_i \rVert^2} \le \frac{BX}{\sqrt{n}}

입니다. 셋째 단계는 E∥v∥≤E∥v∥2\mathbb{E}\lVert v \rVert \le \sqrt{\mathbb{E}\lVert v \rVert^2} 이고, i≠ji \ne j 인 교차항의 기댓값 E[σiσj]\mathbb{E}[\sigma_i\sigma_j] 가 0이라 제곱 노름의 기댓값이 대각항만 남습니다. 결과에 입력의 차원이 없다는 점이 중요합니다. 차원이 백만이어도 노름이 제한되어 있으면 복잡도는 1/n1/\sqrt{n} 로 줄어듭니다.

이것을 분류 오차로 옮기는 것이 마진입니다. 표본 (x,y)(x, y) 의 마진은 yf(x)y f(x) 로, 부호가 양이면 맞게 부른 것이고 크기는 얼마나 여유 있게 맞았는지입니다. 마진 γ>0\gamma > 0 을 하나 정하고, 마진이 0 이하면 1, γ\gamma 이상이면 0, 그 사이는 직선으로 잇는 램프 손실 ϕγ\phi_\gamma 를 씁니다. 램프 손실은 0-1 손실보다 크거나 같고, 마진이 γ\gamma 보다 작은 표본의 비율 R^γ\hat{R}_\gamma 보다 작거나 같으며, 기울기가 1/γ1/\gamma 이하입니다. 기울기가 LL 이하인 함수를 씌우면 Rademacher 복잡도가 많아야 LL 배가 된다는 탈라그랑의 축약 보조정리를 증명 없이 받아 쓰면(라벨을 곱하는 것은 σiyi\sigma_i y_i 가 σi\sigma_i 와 같은 분포라 복잡도를 바꾸지 않습니다), 확률 1−δ1 - \delta 이상으로

R(w)≤R^γ(w)+2BXγn+log⁡(1/δ)2nR(w) \le \hat{R}_\gamma(w) + \frac{2BX}{\gamma\sqrt{n}} + \sqrt{\frac{\log(1/\delta)}{2n}}

입니다. BX/γ=10BX/\gamma = 10, n=50,000n = 50{,}000 이면 둘째 항은 0.089입니다. 경계에 들어가는 것은 파라미터의 개수가 아니라 「노름에 비해 마진이 얼마나 큰가」입니다. 이 비가 PAC-Bayes에서도 같은 자리에 나타납니다.

공허한 경계

무작위 라벨

이제 장면의 첫 질문에 답합니다. 실제위험은 정의상 1을 넘지 못하므로, 상한이 1 이상인 경계는 참이지만 아무것도 말해 주지 않습니다. 이런 경계를 공허한 경계라 부릅니다. 두 갈래 분류라면 동전 던지기가 0.5를 내므로 0.5를 넘는 경계도 실질적으로 공허합니다.

Rademacher 경계에 무작위 라벨 실험을 넣어 봅니다. 신경망이 학습 이미지 50,000장에 붙인 어떤 라벨이든 외울 수 있다고, 곧 실험이 보여 준 것을 모든 라벨 배정으로 넓혀 받아들인다고 합시다. 그러면 0-1 손실의 함수 집합에서 부호 σ\sigma 가 무엇이든, σi=+1\sigma_i = +1 인 이미지는 틀리고 −1-1 인 이미지는 맞히는 라벨 배정을 신경망이 실현할 수 있습니다. 그 가설에서 1n∑iσiℓi\frac{1}{n}\sum_i \sigma_i \ell_i 는 σi=+1\sigma_i = +1 인 이미지의 비율이고 그 기댓값이 1/21/2 이므로 R^S=1/2\hat{\mathfrak{R}}_S = 1/2 입니다. 경계의 복잡도 항 2R^S2\hat{\mathfrak{R}}_S 가 정확히 1이 되어 학습 오차가 0이어도 상한이 1을 넘습니다.

이 논증에는 진짜 라벨이 한 번도 나오지 않습니다. 균등수렴 경계는 가설 집합과 표본의 입력만 보고, 학습 알고리즘이 그 집합 안에서 어디에 내려앉았는지는 보지 않습니다. 진짜 라벨로 학습한 신경망과 무작위 라벨로 학습한 신경망이 같은 집합에 속하므로 같은 경계를 받고, 무작위 쪽의 시험 오차가 90%이니 그 경계는 90%보다 작을 수 없습니다. 이것이 둘째 질문의 답입니다. 고전 이론이 틀린 것이 아니라, 묻는 대상이 「이 집합의 최악」이라 이 집합에서는 할 말이 없는 것입니다.

파라미터 수

VC 차원으로 계산해도 같습니다. 조각마다 선형인 활성화를 쓰는 신경망의 VC 차원은 파라미터 수 WW 와 층 수 LL 에 대해 대략 WLlog⁡WW L \log W 를 넘지 않고, 그 크기에 가까운 하한도 알려져 있습니다(Bartlett 등, 2019). 장면의 신경망은 W=1.2×106W = 1.2 \times 10^6 이라 dVC≥nd_{\mathrm{VC}} \ge n 은 의심할 것이 없습니다. 그러면 Sauer는 아무것도 줄여 주지 않아 log⁡ΠH(n)=nlog⁡2\log \Pi_{\mathcal{H}}(n) = n\log 2 이고, 복잡도 항은

22log⁡ΠH(n)n=22log⁡2=2.3552\sqrt{\frac{2\log \Pi_{\mathcal{H}}(n)}{n}} = 2\sqrt{2\log 2} = 2.355

입니다. 표본 수와 무관한 상수로, 1의 두 배를 넘습니다.

표본 50,000 개에서 VC 경계의 복잡도 항을 VC 차원에 따라 그린 그림. 가로축은 VC 차원을 로그 눈금으로 10 에서 백만까지, 세로축은 경계 값이다. 곡선은 d = 10 에서 0.12, d = 100 에서 0.34, d = 1,000 에서 0.89 로 오르고 d = 1,357 에서 공허함을 뜻하는 가로선 1 을 지나며, d 가 16,000 남짓을 넘으면 Sauer 상한이 2 의 n 제곱보다 커져 2.355 에서 평평해진다. 장면의 신경망 파라미터 수 120만은 그 평평한 구간에 있다

n=50,000n = 50{,}000 에서 복잡도 항이 1을 넘는 VC 차원은 1,357입니다. 파라미터 수와 VC 차원이 같다고 가장 너그럽게 쳐도, 이 경계가 무언가를 말하려면 파라미터가 1,357개 이하여야 하고 장면의 신경망은 그보다 900배 가까이 큽니다. 경계를 1 아래로 끌어내리려면 표본 수가 VC 차원보다 수십 배 많아야 하는데, 현대의 신경망은 대개 파라미터가 표본보다 많습니다. 파라미터 수에 기대는 경계는 출발부터 공허한 쪽에 서 있습니다.

노름 기반 경계

마진 경계처럼 노름으로 재면 차원이 사라졌으니 신경망에도 같은 방향을 시도할 수 있습니다. Bartlett·Foster·Telgarsky(2017)는 층마다 가중치 행렬의 스펙트럼 노름을 곱한 값에 보정 인자를 붙이고 마진으로 나눈 양으로 신경망의 Rademacher 복잡도를 눌렀습니다. 그들이 보인 것 가운데 이 글의 장면에 닿는 것은, 이 양이 무작위 라벨로 학습한 신경망에서 진짜 라벨일 때보다 훨씬 크게 나온다는 점입니다. 파라미터 수와 달리 노름은 학습이 어디에 내려앉았는지를 보기 때문에 두 신경망을 가를 수 있습니다.

그러나 가르는 것과 1 아래로 내려가는 것은 다른 일입니다. 실제 크기의 신경망에서 이런 노름 기반 경계를 숫자로 계산하면 1을 크게 넘는다는 것이 여러 후속 연구의 보고이고, 학습을 오래 할수록 노름의 곱이 커져 경계가 오히려 나빠지기도 합니다. 더 근본적인 한계도 지적되었습니다. Nagarajan과 Kolter(2019)는 학습 알고리즘이 실제로 내놓는 가설들만 모은 집합으로 좁혀도 그 집합 위의 균등수렴 경계가 공허해지는 구성을 만들었습니다. 「최악을 덮는다」는 틀을 유지하는 한 좁히는 데에도 한계가 있다는 뜻입니다. 다음 절은 이 틀에서 벗어나는 길 하나를 봅니다. 가설 집합 전체가 아니라 가설 위의 분포를 묻는 길입니다.

PAC-Bayes 정리

깁스 분류기

PAC-Bayes는 가설 하나 대신 가설 위의 확률분포를 다룹니다. 표본을 보기 전에 고정한 분포 PP 를 사전분포, 표본을 보고 고른 분포 QQ 를 사후분포라 부릅니다. 이름은 베이즈 통계에서 왔지만 베이즈 정리로 계산할 필요가 없습니다. PP 가 표본과 독립이기만 하면 되고 QQ 는 무엇이든 됩니다. 예측할 때마다 QQ 에서 가설을 새로 하나 뽑아 쓰는 분류기를 깁스 분류기라 하고, 그 실제위험과 경험위험은 가설마다의 값을 QQ 로 평균한 것입니다.

R(Q)=Eh∼Q[R(h)],R^S(Q)=Eh∼Q[R^S(h)]R(Q) = \mathbb{E}_{h \sim Q}[R(h)], \qquad \hat{R}_S(Q) = \mathbb{E}_{h \sim Q}[\hat{R}_S(h)]

신경망이라면 학습한 가중치 ww 를 평균으로 하고 성분마다 작은 정규 잡음을 더한 Q=N(w,σ2I)Q = \mathcal{N}(w, \sigma^2 I) 가 전형적인 사후분포이고, 사전분포는 초기화 지점 w0w_0 를 평균으로 둔 P=N(w0,σ2I)P = \mathcal{N}(w_0, \sigma^2 I) 가 전형입니다. 정리가 말하는 것은 R(Q)R(Q) 가 R^S(Q)\hat{R}_S(Q) 에 두 분포 사이의 KL 발산 DKL(Q ∥ P)D_{\mathrm{KL}}(Q \,\|\, P) 를 nn 으로 나눈 만큼의 여유를 더한 값을 넘지 않는다는 것입니다. 「고급 6번 · 라돈–니코딤 도함수」가 정의한 KL입니다.

DKL(Q ∥ P)=EQ[log⁡dQdP]D_{\mathrm{KL}}(Q \,\|\, P) = \mathbb{E}_{Q}\left[\log \frac{dQ}{dP}\right]

여기서 고전 이론과 갈리는 자리가 보입니다. 가설 집합의 크기는 어디에도 없고, 「학습이 사전분포에서 얼마나 멀리 갔는가」만 있습니다. 무작위 라벨을 외우는 가설이 같은 집합 안에 있어도, 진짜 라벨로 학습한 사후분포가 사전분포 근처에 머문다면 그 사후분포의 경계는 작습니다.

도노스커–바라단 변분식

증명의 열쇠는 KL을 쌍대로 적는 등식입니다. 확률측도 PP 와 유계 가측함수 ff 에 대해

log⁡EP[ef]=sup⁡Q≪P(EQ[f]−DKL(Q ∥ P))\log \mathbb{E}_{P}\big[e^{f}\big] = \sup_{Q \ll P} \Big(\mathbb{E}_{Q}[f] - D_{\mathrm{KL}}(Q \,\|\, P)\Big)

이고, 이것을 도노스커–바라단 변분식이라 부릅니다. 왼쪽은 PP 하나로 정해지는 수이고 오른쪽은 모든 QQ 를 훑은 최댓값입니다. 우리가 쓸 것은 「모든 QQ 에서 EQ[f]≤DKL(Q ∥ P)+log⁡EP[ef]\mathbb{E}_Q[f] \le D_{\mathrm{KL}}(Q \,\|\, P) + \log \mathbb{E}_P[e^f]」라는 부등식 쪽입니다. Q≪PQ \ll P 가 아니면 KL이 +∞+\infty 라 부등식은 저절로 성립합니다.

증명합니다. Z=EP[ef]Z = \mathbb{E}_P[e^f] 는 ff 가 유계라 양의 유한한 수이고, dG/dP=ef/ZdG/dP = e^f / Z 로 새 확률측도 GG 를 정의합니다. 이것을 깁스 측도라 부릅니다. ef/Ze^f/Z 가 어디서나 양수이므로 PP 와 GG 는 서로 절대연속이고, Q≪PQ \ll P 이면 Q≪GQ \ll G 입니다. 라돈–니코딤 도함수의 연쇄 법칙 dQ/dP=(dQ/dG)(dG/dP)dQ/dP = (dQ/dG)(dG/dP) 에 로그를 씌워 QQ 로 평균하면

DKL(Q ∥ P)=EQ[log⁡dQdG]+EQ[f]−log⁡Z=DKL(Q ∥ G)+EQ[f]−log⁡ZD_{\mathrm{KL}}(Q \,\|\, P) = \mathbb{E}_Q\left[\log\frac{dQ}{dG}\right] + \mathbb{E}_Q[f] - \log Z = D_{\mathrm{KL}}(Q \,\|\, G) + \mathbb{E}_Q[f] - \log Z

입니다. 옮겨 적으면 EQ[f]−DKL(Q ∥ P)=log⁡Z−DKL(Q ∥ G)\mathbb{E}_Q[f] - D_{\mathrm{KL}}(Q \,\|\, P) = \log Z - D_{\mathrm{KL}}(Q \,\|\, G) 이고, 기브스 부등식으로 DKL(Q ∥ G)≥0D_{\mathrm{KL}}(Q \,\|\, G) \ge 0 이므로 왼쪽은 log⁡Z\log Z 를 넘지 못합니다. 등호는 Q=GQ = G 에서 섭니다. 상한이 실제로 닿으므로 등식이 성립합니다. 증명이 끝났습니다. EQ[f]\mathbb{E}_Q[f] 와 EQ[log⁡(dQ/dG)]\mathbb{E}_Q[\log(dQ/dG)] 를 따로 적어 더한 것은 ff 가 유계라 첫째 기댓값이 유한하기 때문에 허락됩니다.

깁스 측도는 PP 를 ff 가 큰 쪽으로 지수적으로 기울인 분포입니다. 변분식은 「ff 의 평균을 키우되 PP 에서 멀어지는 값을 KL로 치르는」 거래에서 가장 좋은 답이 그 기울인 분포라고 말합니다. 이 거래가 PAC-Bayes 경계의 모양 그대로입니다.

PAC-Bayes 경계

이제 정리를 씁니다. 손실이 [0,1][0, 1] 안에 있고, 사전분포 PP 와 λ>0\lambda > 0, δ∈(0,1)\delta \in (0, 1) 을 표본과 무관하게 정해 둡니다. 그러면 확률 1−δ1 - \delta 이상으로, 모든 사후분포 QQ 에서 동시에

R(Q)≤R^S(Q)+DKL(Q ∥ P)+log⁡(1/δ)λ+λ8nR(Q) \le \hat{R}_S(Q) + \frac{D_{\mathrm{KL}}(Q \,\|\, P) + \log(1/\delta)}{\lambda} + \frac{\lambda}{8n}

입니다. 이것이 PAC-Bayes 정리의 한 형태입니다.

증명은 세 걸음입니다. 첫째, 변분식에 f(h)=λ(R(h)−R^S(h))f(h) = \lambda(R(h) - \hat{R}_S(h)) 를 넣습니다. 이 ff 는 [−λ,λ][-\lambda, \lambda] 안이라 유계이고, QQ 로 평균하면 λ(R(Q)−R^S(Q))\lambda(R(Q) - \hat{R}_S(Q)) 이므로 모든 QQ 에서

λ(R(Q)−R^S(Q))≤DKL(Q ∥ P)+log⁡Eh∼P[eλ(R(h)−R^S(h))]⏟Ψ(S)\lambda\big(R(Q) - \hat{R}_S(Q)\big) \le D_{\mathrm{KL}}(Q \,\|\, P) + \log \underbrace{\mathbb{E}_{h \sim P}\big[e^{\lambda(R(h) - \hat{R}_S(h))}\big]}_{\Psi(S)}

입니다. 표본에 따라 달라지는 것은 오른쪽의 Ψ(S)\Psi(S) 하나이고, 거기에는 QQ 가 없습니다.

둘째, Ψ(S)\Psi(S) 의 기댓값을 누릅니다. 음이 아닌 함수라 적분 순서를 바꿀 수 있고(토넬리 정리), 사전분포가 표본과 무관하므로 바꾼 뒤에도 PP 는 그대로입니다.

ES[Ψ(S)]=Eh∼P[ES[eλ(R(h)−R^S(h))]]≤Eh∼P[eλ2/(8n)]=eλ2/(8n)\mathbb{E}_S[\Psi(S)] = \mathbb{E}_{h \sim P}\Big[\mathbb{E}_S\big[e^{\lambda(R(h) - \hat{R}_S(h))}\big]\Big] \le \mathbb{E}_{h \sim P}\big[e^{\lambda^2/(8n)}\big] = e^{\lambda^2/(8n)}

부등호는 가설을 하나 고정한 뒤의 회프딩 보조정리입니다. R(h)−R^S(h)=1n∑i(R(h)−ℓ(h,zi))R(h) - \hat{R}_S(h) = \frac{1}{n}\sum_i (R(h) - \ell(h, z_i)) 이고 각 항은 평균이 0이고 폭이 1인 구간 안의 독립 변수이므로, 하나마다 E[e(λ/n)(R−ℓi)]≤eλ2/(8n2)\mathbb{E}[e^{(\lambda/n)(R - \ell_i)}] \le e^{\lambda^2/(8n^2)} 이고 nn 개를 곱하면 eλ2/(8n)e^{\lambda^2/(8n)} 입니다. 사전분포가 표본을 보았다면 이 자리에서 가설이 표본에 따라 움직여 회프딩을 쓸 수 없습니다. 사전분포의 독립성이 증명 전체에서 쓰이는 곳은 여기 한 곳입니다.

셋째, 마르코프 부등식으로 Pr⁡[Ψ(S)>eλ2/(8n)/δ]≤δ\Pr[\Psi(S) > e^{\lambda^2/(8n)}/\delta] \le \delta 입니다. 그 나쁜 사건 밖에서는 log⁡Ψ(S)≤λ2/(8n)+log⁡(1/δ)\log\Psi(S) \le \lambda^2/(8n) + \log(1/\delta) 이고, 첫째 걸음의 부등식에 넣어 λ\lambda 로 나누면 정리의 식입니다. 나쁜 사건이 QQ 와 무관한 Ψ(S)\Psi(S) 하나에 관한 것이므로, 그 밖에서는 모든 QQ 에서 한꺼번에 성립합니다. 표본을 보고 사후분포를 골라도 되는 이유가 이것입니다.

λ=8n(DKL+log⁡(1/δ))\lambda = \sqrt{8n(D_{\mathrm{KL}} + \log(1/\delta))} 로 놓으면 오른쪽이 R^S(Q)+(DKL+log⁡(1/δ))/(2n)\hat{R}_S(Q) + \sqrt{(D_{\mathrm{KL}} + \log(1/\delta))/(2n)} 이 됩니다. 다만 이 λ\lambda 는 QQ 에 기대므로 미리 정할 수 없고, 후보 KK 개에 δ/K\delta/K 씩 나눠 합집합 경계를 쓰면 log⁡K\log K 만큼만 더 치르고 가장 좋은 후보를 쓸 수 있습니다. 같은 뼈대에 f(h)=n kl(R^S(h) ∥ R(h))f(h) = n\,\mathrm{kl}(\hat{R}_S(h) \,\|\, R(h)) 를 넣으면 더 날카로운 형태가 나옵니다. 여기서 kl(q ∥ p)=qlog⁡(q/p)+(1−q)log⁡((1−q)/(1−p))\mathrm{kl}(q \,\|\, p) = q\log(q/p) + (1 - q)\log((1 - q)/(1 - p)) 는 동전 두 개의 KL입니다. kl의 볼록성으로 기댓값을 안으로 넣고, 마우러가 보인 ES[en kl(R^S(h)∥R(h))]≤2n\mathbb{E}_S[e^{n\,\mathrm{kl}(\hat{R}_S(h) \| R(h))}] \le 2\sqrt{n} 을 둘째 걸음 자리에 쓰면(이 부등식의 증명은 생략합니다)

kl(R^S(Q) ∥ R(Q))≤DKL(Q ∥ P)+log⁡(2n/δ)n\mathrm{kl}\big(\hat{R}_S(Q) \,\|\, R(Q)\big) \le \frac{D_{\mathrm{KL}}(Q \,\|\, P) + \log(2\sqrt{n}/\delta)}{n}

입니다. R(Q)R(Q) 에 대해 풀면 학습 오차가 작을 때 간극이 제곱근이 아니라 KL을 nn 으로 나눈 크기로 줄어듭니다. 숫자로 경계를 계산할 때는 이쪽을 씁니다.

사전분포의 선택

경계에 들어가는 것이 KL이니 사전분포를 어디에 두느냐가 경계를 좌우합니다. 사후분포 N(w,σ2I)\mathcal{N}(w, \sigma^2 I) 와 사전분포 N(μ,σP2I)\mathcal{N}(\mu, \sigma_P^2 I) 사이의 KL은 파라미터 수를 pp 라 할 때

DKL=12(p σ2+∥w−μ∥2σP2−p+plog⁡σP2σ2)D_{\mathrm{KL}} = \frac{1}{2}\left(\frac{p\,\sigma^2 + \lVert w - \mu \rVert^2}{\sigma_P^2} - p + p\log\frac{\sigma_P^2}{\sigma^2}\right)

이고, σP=σ\sigma_P = \sigma 로 맞추면 ∥w−μ∥2/(2σ2)\lVert w - \mu \rVert^2 / (2\sigma^2) 만 남습니다. 파라미터 수가 직접 들어가는 항은 두 분산을 맞추면 사라지고, 남는 것은 사전분포의 평균에서 학습한 가중치까지의 거리를 잡음의 폭으로 잰 값입니다. 사전분포를 원점에 두면 가중치 자체의 노름을 치르고, 초기화 지점 w0w_0 에 두면 학습이 움직인 거리만 치릅니다. w0w_0 는 무작위로 뽑았지만 표본과 독립이므로 사전분포의 평균으로 써도 됩니다. 학습한 가중치를 사전분포의 평균으로 쓰는 것만 금지됩니다. 그것은 표본을 본 사전분포라 둘째 걸음이 무너집니다.

분산도 미리 정해야 합니다. 후보 σ1,…,σK\sigma_1, \dots, \sigma_K 를 미리 적어 두고 각각에 δ/K\delta/K 를 배정하면 표본을 보고 가장 좋은 것을 골라도 log⁡K\log K 만 더 치릅니다. 더 나아가 표본을 둘로 나눠 앞쪽으로 사전분포를 학습하고 뒤쪽으로 경계를 계산하는 방법도 쓰입니다. 경계에 쓰는 표본 수는 줄지만 사전분포가 사후분포에 훨씬 가까워져 KL이 크게 줄어드는 경우가 많습니다. 어느 쪽이든 원칙은 같습니다. 사전분포는 경계를 재는 표본을 보지 않은 채로 사후분포가 갈 곳을 최대한 가깝게 예측해야 합니다.

평탄성과 압축

평평한 최소점

사후분포의 평균은 학습한 가중치로 정했으니 남은 손잡이는 잡음의 폭 σ\sigma 하나입니다. σ\sigma 를 키우면 KL은 1/σ21/\sigma^2 로 줄지만 깁스 분류기의 경험위험이 오릅니다. 2차까지 펼치면

R^S(Q)=Eε[R^S(w+σε)]≈R^S(w)+σ22 tr ∇2R^S(w)\hat{R}_S(Q) = \mathbb{E}_{\varepsilon}\big[\hat{R}_S(w + \sigma\varepsilon)\big] \approx \hat{R}_S(w) + \frac{\sigma^2}{2}\,\mathrm{tr}\,\nabla^2 \hat{R}_S(w)

입니다(ε∼N(0,I)\varepsilon \sim \mathcal{N}(0, I), 1차 항은 평균이 0이라 사라지고 2차 항의 기댓값이 헤세 행렬의 대각합입니다). 손실 지형이 평평해서 헤세 행렬의 대각합이 작은 최소점, 곧 평평한 최소점에서는 큰 σ\sigma 를 써도 경험위험이 거의 안 오르고, 그만큼 KL이 작아집니다. 날카로운 최소점에서는 작은 σ\sigma 밖에 못 쓰고 KL이 1/σ21/\sigma^2 로 불어납니다. 「중급 44번 · 손실 지형」이 그린 평평한 골짜기와 「중급 49번 · 그래디언트 잡음」이 말한 잡음의 평탄성 선호가 여기서 일반화 경계의 숫자로 번역됩니다.

장난감 크기에서 재 보았습니다. 입력 100차원, 은닉 100개인 tanh 신경망(파라미터 10,100개)을 표본 4,000개에 학습했습니다. 라벨은 한 방향의 부호로 정한 진짜 라벨과 무작위 라벨 두 벌이고, 둘 다 학습 오차 0까지 갔습니다. 시험 오차는 진짜 라벨에서 2.5%, 무작위 라벨에서 51.4%입니다. 학습한 가중치에 성분마다 폭 σ\sigma 의 잡음을 더해 학습 표본에서 다시 잰 오차가 아래 그림입니다.

학습한 tanh 신경망의 가중치에 폭 σ 의 정규 잡음을 더했을 때 학습 표본 위 오차를 σ 에 따라 그린 그림. 가로축 σ 는 0.04 에서 1.0 까지 로그 눈금이다. 진짜 라벨로 학습한 쪽은 σ = 0.08 까지 0.2% 이하에 머물고 0.16 에서 3.8%, 0.32 에서 13.3% 로 오른다. 무작위 라벨로 학습한 쪽은 σ = 0.16 에서 이미 17.9%, 0.32 에서 40.2% 로 동전 던지기 0.5 에 다가간다. 초기화에서 학습한 가중치까지의 거리는 진짜 라벨 16.1, 무작위 라벨 29.7 이다

같은 잡음에 대해 무작위 라벨 쪽이 훨씬 빨리 무너집니다. σ=0.16\sigma = 0.16 에서 진짜 라벨은 3.8%만 틀리는데 무작위 라벨은 17.9%가 틀립니다. 무작위 라벨을 외운 최소점이 더 날카롭다는 뜻입니다. 거리도 다릅니다. 초기화에서 학습한 가중치까지 진짜 라벨은 16.1, 무작위 라벨은 29.7을 움직였습니다. 같은 σ\sigma 에서 KL은 거리의 제곱에 비례하므로 무작위 쪽이 3.4배입니다. 날카로우니 σ\sigma 를 작게 써야 하고, 멀리 갔으니 같은 σ\sigma 에서도 KL이 큽니다. 두 이유가 곱해져 무작위 라벨의 사후분포는 큰 KL을 치르게 되고, 균등수렴 경계가 갈라내지 못한 두 신경망을 PAC-Bayes 경계는 KL 항으로 가릅니다.

이 연결이 평탄성 지향 최적화의 이론적 근거가 되었습니다. Foret 등(2021)의 SAM은 가중치 근처 반지름 ρ\rho 안에서 가장 나쁜 손실 max⁡∥ε∥≤ρL(w+ε)\max_{\lVert \varepsilon \rVert \le \rho} L(w + \varepsilon) 을 줄이도록 학습하는데, 그 동기를 PAC-Bayes 꼴 경계에서 유도했습니다. 다만 평탄성 자체를 경계로 삼을 때는 조심해야 합니다. ReLU 신경망은 한 층을 cc 배, 다음 층을 1/c1/c 배 해도 같은 함수인데, 이 변환이 헤세 행렬의 대각합을 마음대로 바꾸므로(Dinh 등, 2017) 「평평함」은 좌표를 정해야 뜻이 섭니다. PAC-Bayes는 이 문제를 사전분포에 넘깁니다. 같은 함수라도 초기화에서 먼 표현을 고르면 KL이 커지므로, 경계는 평탄성 하나가 아니라 「사전분포에서 본 평탄성」을 잽니다.

비공허 경계

Dziugaite와 Roy(2017)가 이 계산을 실제 신경망에 처음 끝까지 해냈습니다. MNIST를 두 갈래(5 미만과 이상)로 나눈 문제에서 수십만 파라미터의 완전연결 신경망을 SGD로 학습한 뒤, 그 가중치에서 출발해 성분마다 분산이 다른 정규 사후분포를 PAC-Bayes 경계가 작아지도록 다시 최적화했습니다. 사전분포는 초기화 지점에 두었고 분산 후보는 합집합 경계로 처리했으며, 깁스 분류기의 경험위험은 가중치를 여러 번 뽑아 어림하고 그 어림의 오차도 따로 경계에 넣었습니다. 그렇게 얻은 시험 오차의 상한이 0.2 안팎으로, 같은 신경망의 VC 경계가 한참 공허한 자리에서 처음으로 1보다, 그리고 0.5보다 작은 숫자가 나왔습니다. 무작위 라벨로 학습한 신경망에 같은 절차를 쓰면 의미 있는 경계가 나오지 않았습니다.

위의 tanh 신경망에서도 같은 절차를 줄여 돌려 보았습니다. 진짜 라벨 쪽에서 σ=0.2\sigma = 0.2 로 사후분포의 평균을 다시 최적화하니 KL이 579.8, 가중치 500벌로 어림한 깁스 경험위험이 0.120이었고, 어림의 오차와 kl 형태를 거쳐 얻은 상한이 0.420이었습니다. 동전 던지기보다는 낫지만 날카롭지는 않습니다. 표본이 4,000개뿐이라 KL을 nn 으로 나눈 몫이 0.14나 되고, 가중치 500벌의 어림 오차도 0.05쯤을 보탭니다. 표본이 많고 KL이 작아야 경계가 내려갑니다.

압축 경계

PAC-Bayes에 점 하나에 몰린 사후분포를 넣으면 처음의 유한 가설 경계로 돌아갑니다. 가설이 셀 수 있게 많고 사전분포가 가설마다 확률 π(h)\pi(h) 를 주며 QQ 가 가설 하나에 몰려 있으면 DKL(Q ∥ P)=log⁡(1/π(h))D_{\mathrm{KL}}(Q \,\|\, P) = \log(1/\pi(h)) 입니다. 균등한 π=1/∣H∣\pi = 1/|\mathcal{H}| 이면 log⁡∣H∣\log|\mathcal{H}| 가 되어 첫 절의 식과 같은 꼴입니다. 사전분포를 고르지 않게 주면 이것이 오컴의 면도날이 됩니다. 접두어 없는 부호로 가설을 k(h)k(h) 비트에 적을 수 있으면 π(h)=2−k(h)\pi(h) = 2^{-k(h)} 로 확률의 합이 1을 넘지 않게 줄 수 있고, 그러면 확률 1−δ1 - \delta 이상으로

R(h)≤R^S(h)+k(h)log⁡2+log⁡(1/δ)2nR(h) \le \hat{R}_S(h) + \sqrt{\frac{k(h)\log 2 + \log(1/\delta)}{2n}}

입니다. 이것을 압축 경계라 부릅니다. 짧게 적히는 가설일수록 경계가 작습니다. 예컨대 학습한 신경망을 가지치기와 양자화로 줄여 20,000비트에 적을 수 있고 n=50,000n = 50{,}000, δ=0.05\delta = 0.05 이면 둘째 항은 0.372입니다. 120만 개의 파라미터가 아니라 그것을 적는 데 실제로 필요한 비트 수가 경계에 들어갑니다.

신경망은 학습 뒤 크게 압축되어도 성능을 지키는 경우가 많으므로 이 길이 실제로 쓰입니다. Arora 등(2018)은 학습한 신경망이 잡음에 둔감한 방향을 이용해 작은 신경망으로 압축하고 그 압축본에 경계를 매겼고, Zhou 등(2019)은 압축과 PAC-Bayes를 합쳐 ImageNet 규모에서도 공허하지 않은 경계를 보고했습니다. 경계가 말하는 대상이 원래 신경망이 아니라 압축본이라는 점은 함께 적어 두어야 합니다. 「압축해도 성능이 남는다」가 곧 「잡음을 더해도 성능이 남는다」, 곧 평평하다는 말과 같은 뿌리라는 점도 눈여겨볼 만합니다.

알고리즘 안정성

세 번째 길은 가설 집합도 분포도 아니라 학습 알고리즘의 성질을 봅니다. 표본 SS 에서 ii 번째 원소만 새 것으로 바꾼 표본을 S(i)S^{(i)} 라 할 때, 모든 SS, ii, zz 에서 ∣ℓ(A(S),z)−ℓ(A(S(i)),z)∣≤β|\ell(A(S), z) - \ell(A(S^{(i)}), z)| \le \beta 이면 알고리즘 AA 가 균등 안정성 β\beta 를 가진다고 말합니다. 표본 하나를 바꿔도 결과가 크게 안 흔들린다는 뜻입니다. 그러면

∣ES[R(A(S))−R^S(A(S))]∣≤β\Big|\mathbb{E}_S\big[R(A(S)) - \hat{R}_S(A(S))\big]\Big| \le \beta

입니다. 증명은 대칭화와 같은 고스트 논법입니다. 새 원소 zi′z'_i 를 하나 더 뽑으면 A(S)A(S) 가 그것을 못 봤으니 E[R(A(S))]=E[ℓ(A(S),zi′)]\mathbb{E}[R(A(S))] = \mathbb{E}[\ell(A(S), z'_i)] 이고, ziz_i 와 zi′z'_i 를 맞바꿔도 분포가 같으므로 이것은 E[ℓ(A(S(i)),zi)]\mathbb{E}[\ell(A(S^{(i)}), z_i)] 와 같습니다. 한편 E[R^S(A(S))]=1n∑iE[ℓ(A(S),zi)]\mathbb{E}[\hat{R}_S(A(S))] = \frac{1}{n}\sum_i \mathbb{E}[\ell(A(S), z_i)] 이므로 둘의 차이는 1n∑iE[ℓ(A(S(i)),zi)−ℓ(A(S),zi)]\frac{1}{n}\sum_i \mathbb{E}[\ell(A(S^{(i)}), z_i) - \ell(A(S), z_i)] 이고 각 항이 β\beta 이하입니다. 맥디아미드를 쓰면 확률 경계로도 바꿀 수 있습니다(Bousquet와 Elisseeff, 2002).

이 경계에는 가설 집합이 없습니다. 무작위 라벨을 외울 수 있는 집합이어도 알고리즘이 안정하면 됩니다. Hardt·Recht·Singer(2016)는 볼록하고 매끄러운 손실에서 SGD의 안정성이 걸음 크기의 합을 nn 으로 나눈 것에 비례함을 보였습니다. 오래 학습할수록 덜 안정해진다는 이 결과는 조기 종료에 이론적 근거를 줍니다. 볼록하지 않은 신경망에서는 같은 결과가 그대로 서지 않고, 무작위 라벨을 외울 때까지 오래 돌리면 안정성 경계도 커집니다. 세 길은 결국 같은 것을 다른 말로 잽니다. 학습이 표본의 우연에 얼마나 덜 기대는가입니다.

다시 무작위 라벨로

코드로 확인하기

장면의 세 질문을 손에 잡히는 크기에서 한꺼번에 확인합니다. 깁스 경험위험을 정확히 계산할 수 있는 선형 분류기를 씁니다. 입력은 3,000차원인데 라벨을 정하는 신호는 앞 10차원에만 있고 나머지 2,990차원에는 작은 잡음만 있습니다. 표본은 2,000개라 파라미터가 표본보다 많고, 3,000차원 반공간의 VC 차원 3,001이 표본 수를 넘습니다. 진짜 라벨과 무작위 라벨에 같은 경사하강법을 같은 걸음 수만큼 돌립니다.

사후분포는 학습한 방향 w^=w/∥w∥\hat{w} = w/\lVert w \rVert 를 tt 배 한 점을 평균으로 둔 Q=N(tw^,I)Q = \mathcal{N}(t\hat{w}, I), 사전분포는 표본을 보지 않은 P=N(0,I)P = \mathcal{N}(0, I) 입니다. 두 분산이 같으니 KL은 t2/2t^2/2 입니다. QQ 에서 뽑은 vv 에 대해 v⊤xv^\top x 는 평균 tw^⊤xt\hat{w}^\top x, 분산 ∥x∥2\lVert x \rVert^2 인 정규분포이므로, 표본 하나를 틀릴 확률이 정확히

Pr⁡v∼Q[y v⊤x<0]=Φ(−tγ),γ=y w^⊤x∥x∥\Pr_{v \sim Q}\big[y\, v^\top x < 0\big] = \Phi(-t\gamma), \qquad \gamma = \frac{y\,\hat{w}^\top x}{\lVert x \rVert}

입니다. Φ\Phi 는 표준정규 누적분포함수이고 γ\gamma 는 길이로 나눠 정규화한 마진입니다. 마진이 크면 tt 를 조금만 키워도 깁스 오차가 0으로 가고 KL은 t2/2t^2/2 로만 자랍니다. 마진 경계에서 노름 대 마진의 비가 하던 일을 여기서는 tt 가 합니다. tt 는 미리 적어 둔 후보 40개 가운데 고르고 그 값을 합집합 경계로 치릅니다.

import numpy as np
from math import erf

rng = np.random.default_rng(0)
n, d, k = 2000, 3000, 10                            # 표본 2000, 파라미터 3000 > n, 신호는 10차원
u = rng.standard_normal(k); u /= np.linalg.norm(u)
def data(m):                                        # 앞 10차원에 신호, 나머지 2990차원에 작은 잡음
    z = rng.standard_normal((m, k))
    xi = rng.standard_normal((m, d - k)) / np.sqrt((d - k) / k)
    return np.hstack([z, xi]), np.sign(z @ u)
X, y = data(n); Xt, yt = data(5000)
yr = rng.choice([-1.0, 1.0], n)                     # 무작위 라벨

def gd(y, steps=3000, lr=1.0):                      # 로지스틱 손실의 경사하강법, 원점에서 출발
    w = np.zeros(d)
    for _ in range(steps):
        w += lr * X.T @ (y / (1 + np.exp(np.clip(y * (X @ w), -50, 50)))) / n
    return w

Phi = np.vectorize(lambda s: 0.5 * (1 + erf(s / np.sqrt(2))))
def kl(q, p): return q*np.log(q/p) + (1-q)*np.log((1-q)/(1-p)) if q > 0 else -np.log(1-p)
def klinv(q, c):                                    # kl(q||p) <= c 를 만족하는 가장 큰 p
    lo, hi = q, 1 - 1e-12
    for _ in range(100):
        p = (lo + hi) / 2
        lo, hi = (p, hi) if kl(q, p) <= c else (lo, p)
    return hi

print(round(2 * np.sqrt(2 * np.log(2)), 3))         # d_VC = d+1 > n 일 때 VC 경계의 복잡도 항
# 2.355

delta, K = 0.05, 40
ts = 2 ** (np.arange(K) / 2)                        # 미리 적어 둔 후보 40개 (합집합 경계)
for name, yy in (("진짜", y), ("무작위", yr)):
    w = gd(yy)
    g = yy * (X @ w) / np.linalg.norm(w) / np.linalg.norm(X, axis=1)    # 정규화한 마진
    gt = yt * (Xt @ w) / np.linalg.norm(w) / np.linalg.norm(Xt, axis=1)
    best = min((klinv(Phi(-t * g).mean(), (t*t/2 + np.log(2*np.sqrt(n)*K/delta)) / n),
                t, Phi(-t * g).mean(), t*t/2, Phi(-t * gt).mean()) for t in ts)
    B, t, q, KL, qt = best
    print(name, np.mean(np.sign(X @ w) != yy), np.mean(np.sign(Xt @ w) != yt), round(np.median(g), 4))
    print('  t=%.2f KL=%.0f 깁스 학습 %.4f 경계 %.4f 깁스 시험 %.4f' % (t, KL, q, B, qt))
# 진짜 0.0 0.012 0.1276
#   t=16.00 KL=128 깁스 학습 0.0741 경계 0.2097 깁스 시험 0.0980
# 무작위 0.0015 0.4904 0.0133
#   t=2.83 KL=4 깁스 학습 0.4834 경계 0.5449 깁스 시험 0.4998

첫 줄이 첫째 질문의 답입니다. VC 차원이 표본 수를 넘으니 복잡도 항이 2.355이고, 이 숫자는 진짜 라벨인지 무작위 라벨인지를 묻지 않습니다. 둘째 줄과 넷째 줄이 둘째 질문을 보여 줍니다. 같은 분류기 집합, 같은 알고리즘이 진짜 라벨에서는 학습 오차 0과 시험 오차 1.2%를, 무작위 라벨에서는 2,000개 가운데 세 개를 빼고 다 외워 학습 오차 0.15%와 시험 오차 49.0%를 냅니다. 균등수렴 경계는 이 둘에 같은 값을 주어야 하므로 49.0% 아래로 내려갈 수 없습니다.

셋째 질문의 답이 그 아래 줄들입니다. 두 분류기는 같은 집합에 있지만 정규화한 마진의 중앙값이 0.1276과 0.0133으로 열 배 가까이 다릅니다. 진짜 라벨 쪽은 t=16t = 16 까지 키워 KL 128을 치르고 깁스 학습 오차를 0.0741로 누를 수 있어, 경계가 0.2097입니다. 시험 표본에서 잰 깁스 오차 0.0980은 그 아래에 있습니다. 무작위 라벨 쪽은 마진이 작아 tt 를 키우면 KL만 늘고 깁스 오차가 안 내려가, 가장 좋은 후보에서도 깁스 학습 오차가 0.4834이고 경계가 0.5449입니다. 동전 던지기보다 나쁘다는 것밖에 말하지 못합니다. 경계가 진짜 라벨에서만 작게 나왔습니다. 고전 이론이 갈라내지 못한 둘을 KL 항이 가른 것입니다.

경계가 말하는 대상이 무작위로 뽑는 깁스 분류기라는 점은 짚어 둡니다. 결정론적 분류기 sign(w^⊤x)\mathrm{sign}(\hat{w}^\top x) 는 QQ 가 평균에 대해 대칭이라 깁스 분류기의 다수결이고, 다수결이 틀린 입력에서는 QQ 의 절반 이상이 틀리므로 그 시험 오차는 2R(Q)≤0.422R(Q) \le 0.42 이하입니다. 실제 시험 오차 1.2%와는 거리가 있습니다. 경계는 참이고 1보다 한참 작지만, 날카로운 예측은 아닙니다. Dziugaite와 Roy의 0.2 안팎도 같은 성격의 숫자입니다. 그 신경망의 실제 시험 오차는 그보다 훨씬 작았습니다.

연습

  1. 가설이 2202^{20} 개인 유한 집합에서 표본 n=10,000n = 10{,}000, δ=0.01\delta = 0.01 일 때 모든 가설에 동시에 성립하는 간극의 상한 (log⁡∣H∣+log⁡(1/δ))/(2n)\sqrt{(\log|\mathcal{H}| + \log(1/\delta))/(2n)} 을 구하세요.
    log⁡∣H∣=20log⁡2=13.863\log|\mathcal{H}| = 20\log 2 = 13.863, log⁡100=4.605\log 100 = 4.605 이라 18.468/20,000=0.000923=0.0304\sqrt{18.468/20{,}000} = \sqrt{0.000923} = 0.0304 입니다. 가설이 백만 개를 넘어도 간극의 상한은 3%포인트쯤입니다.
  2. VC 차원이 3인 가설 집합에서 n=6n = 6 일 때 Sauer 보조정리의 두 상한 ∑i≤3(6i)\sum_{i \le 3}\binom{6}{i} 과 (en/d)d(en/d)^d 를 각각 계산하고 262^6 과 견주세요.
    첫째는 1+6+15+20=421 + 6 + 15 + 20 = 42 로 26=642^6 = 64 보다 작습니다. 둘째는 (2e)3=160.7(2e)^3 = 160.7 로 오히려 64보다 큽니다. (en/d)d(en/d)^d 는 nn 이 dd 의 몇 배쯤일 때는 자명한 상한 2n2^n 보다도 헐거우니, 작은 nn 에서는 합의 꼴을 그대로 씁니다.
  3. 점 두 개 위의 함수 둘 a=(1,0)a = (1, 0), b=(0,1)b = (0, 1) 로 이루어진 집합의 경험 Rademacher 복잡도를 부호 네 가지를 늘어놓아 구하고, Massart 보조정리의 상한과 견주세요.
    max⁡(σ1,σ2)/2\max(\sigma_1, \sigma_2)/2 를 네 경우에 계산하면 (+,+)(+,+), (+,−)(+,-), (−,+)(-,+) 에서 0.5, (−,−)(-,-) 에서 −0.5-0.5 라 평균이 0.25입니다. Massart는 r=1r = 1, ∣A∣=2|A| = 2 로 2log⁡2/2=0.589\sqrt{2\log 2}/2 = 0.589 입니다.
  4. 두 점 {0,1}\{0, 1\} 위의 균등분포 PP 와 f(0)=0f(0) = 0, f(1)=log⁡3f(1) = \log 3 에 대해 도노스커–바라단 변분식의 왼쪽을 계산하고, 깁스 측도 GG 를 구해 EG[f]−DKL(G ∥ P)\mathbb{E}_G[f] - D_{\mathrm{KL}}(G \,\|\, P) 가 같은 값인지 확인하세요.
    왼쪽은 log⁡((1+3)/2)=log⁡2=0.6931\log((1 + 3)/2) = \log 2 = 0.6931 입니다. GG 는 efe^f 에 비례해 G(0)=1/4G(0) = 1/4, G(1)=3/4G(1) = 3/4 입니다. EG[f]=0.75log⁡3=0.8240\mathbb{E}_G[f] = 0.75\log 3 = 0.8240 이고 DKL(G ∥ P)=0.25log⁡0.5+0.75log⁡1.5=0.1308D_{\mathrm{KL}}(G \,\|\, P) = 0.25\log 0.5 + 0.75\log 1.5 = 0.1308 이라 차이가 0.6932, 반올림을 빼면 log⁡2\log 2 와 같습니다.
  5. 사후분포 N(w,0.12I)\mathcal{N}(w, 0.1^2 I) 와 사전분포 N(w0,0.12I)\mathcal{N}(w_0, 0.1^2 I) 에서 ∥w−w0∥=5\lVert w - w_0 \rVert = 5, n=60,000n = 60{,}000, δ=0.05\delta = 0.05 일 때 KL과 간극 항 (DKL+log⁡(1/δ))/(2n)\sqrt{(D_{\mathrm{KL}} + \log(1/\delta))/(2n)} 을 구하세요. 같은 거리에서 잡음 폭을 0.05로 줄여야만 깁스 학습 오차가 유지된다면 간극 항은 어떻게 되나요.
    KL은 25/(2×0.01)=1,25025/(2 \times 0.01) = 1{,}250 이고 간극 항은 1,253.0/120,000=0.102\sqrt{1{,}253.0/120{,}000} = 0.102 입니다. 폭이 절반이면 KL이 네 배인 5,000이 되어 5,003.0/120,000=0.204\sqrt{5{,}003.0/120{,}000} = 0.204 입니다. 날카로운 최소점에서는 폭을 줄여야 하므로 같은 거리를 움직여도 간극 항이 두 배가 됩니다.
  6. 학습한 모델을 5,000비트에 적을 수 있고 n=20,000n = 20{,}000, δ=0.05\delta = 0.05 일 때 압축 경계의 간극 항을 구하세요.
    (5,000×0.6931+2.996)/40,000=3,468.7/40,000=0.294\sqrt{(5{,}000 \times 0.6931 + 2.996)/40{,}000} = \sqrt{3{,}468.7/40{,}000} = 0.294 입니다.

장면으로 돌아갑니다. CIFAR-10 무작위 라벨을 다 외우는 신경망 앞에서 균등수렴 경계는 공허합니다. VC 차원으로 세면 복잡도 항이 2.355, Rademacher 복잡도로 세면 외울 수 있다는 사실 하나로 1이고, 둘 다 진짜 라벨과 무작위 라벨을 가리지 않습니다. 이론이 틀린 것이 아니라 「이 집합의 최악」을 묻는 틀이라 이 집합에서는 할 말이 없었습니다. PAC-Bayes는 묻는 것을 바꿉니다. 학습이 표본과 무관한 사전분포에서 얼마나 멀리 갔고, 그 자리가 잡음을 얼마나 견디는지를 KL 하나로 잽니다. 그 값은 진짜 라벨에서만 작았고, 위의 선형 장난감에서는 0.21, Dziugaite와 Roy의 신경망에서는 0.2 안팎으로 1보다, 그리고 동전 던지기보다 작은 경계가 나왔습니다. 남은 물음이 있습니다. 무작위 라벨까지 0으로 맞추는 보간이 왜 진짜 라벨에서는 해가 되지 않는가, 그리고 파라미터를 늘릴수록 시험 오차가 한 번 올랐다가 다시 내려가는 모양은 어디서 오는가입니다. 이 글은 그 계산을 하지 않았습니다. 다음 글 고급 10번 · 이중 하강과 양성 과적합: 보간해도 일반화되는 이유가 최소노름 보간을 직접 풀어 그 답을 냅니다.


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

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