마르코프·체비쇼프에서 체르노프 방법으로 올라가 서브가우시안·서브지수와 오를리츠 노름을 세우고, 회프딩·베른슈타인·맥디아미드와 합집합 경계를 증명합니다. 각 부등식이 요구하는 문항 수를 정규 근사와 나란히 계산해 그 근사가 무너지는 자리를 가립니다.
PALDYN Team//62 MIN READ
08MATH
고급
집중부등식 · 체르노프 방법
모델을 학습하는 팀이 체크포인트 스무 개를 사내 평가 세트 2,000문항으로 채점합니다. 점수는 68.4%에서 72.1% 사이에 흩어져 있고, 팀은 72.1%짜리를 골라 「기존 모델 70%보다 2%p 낫다」고 적습니다. 같은 주에 안전성 평가도 돌립니다. 출시 기준은 유해 응답 비율 1% 미만이고, 지난 측정은 0.5% 근처였습니다. 이번에는 그 비율을 ±0.5%p 안으로 재고 싶은데, 문항을 몇 개 모아야 하는지를 두고 두 사람의 계산이 백 배 가까이 갈립니다. 한 사람은 정규 근사로 765개라 하고, 다른 사람은 회프딩 부등식으로 73,778개라 합니다.
리뷰에서 질문이 셋 나옵니다. 첫째, 정답률을 ±2%p 안으로 확률 95%로 맞히려면 몇 문항이 필요한가요. 중급 74번 추정량과 표준오차의 정규 근사 구간을 거꾸로 풀면 2,401문항인데, 그것은 근사이지 보장이 아닙니다. 둘째, 765와 73,778 가운데 어느 쪽이 맞나요. 셋째, 스무 개 가운데 최고를 고른 72.1%는 얼마나 부풀어 있고, 그 최고 점수 자체는 문항을 다시 뽑으면 얼마나 흔들리나요. 지난 글에서는 Hutchinson 추정량의 분산을 그때그때 직접 계산했습니다. 이 글은 그 계산을 일반적인 도구로 바꿉니다. 독립인 표본 여럿에서 계산한 값이 그 기댓값에서 t 이상 벗어날 확률을 t 의 함수로 위에서 누르는 부등식을 통틀어 집중부등식이라 부르고, 세 질문은 모두 이 부등식 몇 개로 답이 납니다.
마르코프와 체비쇼프
마르코프 부등식
출발점은 한 줄짜리 부등식입니다. X≥0 이고 t>0 이면
P(X≥t)≤tE[X]
입니다. 이것이 마르코프 부등식이고, 증명은 지시함수 하나로 끝납니다. X≥t 인 자리에서는 X≥t⋅1 이고 나머지 자리에서는 X≥0=t⋅0 이므로 언제나 X≥t⋅1{X≥t} 입니다. 양변의 기댓값을 잡으면 E[X]≥tP(X≥t) 가 남습니다.
평균 하나만 아는 값에서 얻을 수 있는 것은 정확히 이만큼입니다. X 가 확률 E[X]/t 로 t, 나머지 확률로 0인 분포를 생각하면 등호가 서기 때문입니다. 공정한 동전을 100번 던져 앞면 수 S 가 70 이상일 확률을 마르코프로 누르면 50/70=0.714 입니다. 실제 확률은 3.9×10−5 이니 쓸모가 없어 보이지만, 이 부등식은 그 자체로 쓰는 도구가 아니라 다른 부등식을 만드는 재료입니다. X 자리에 X 의 함수를 넣을 때마다 새 부등식이 하나씩 나오고, 이 글의 나머지가 전부 그 넣기입니다.
체비쇼프 부등식
첫 번째 넣기는 편차의 제곱입니다. 평균이 μ, 분산이 σ2 인 X 에 대해 (X−μ)2≥0 에 마르코프를 쓰면
P(∣X−μ∣≥t)=P((X−μ)2≥t2)≤t2σ2
입니다. 이것이 체비쇼프 부등식이고, 중급 21번 분산과 표준오차가 대수의 법칙을 분포 가정 없이 끌어낼 때 쓴 도구입니다. 표본평균 Xˉ 의 분산은 σ2/n 이므로
P(∣Xˉ−μ∣≥ε)≤nε2σ2
이고, 오른쪽을 실패 확률 δ 이하로 만드는 표본 수는 n≥σ2/(δε2) 입니다. 「표본 n 개면 오차 ε 를 확률 1−δ 로 보장한다」는 문장이 처음으로 식이 됐습니다. 이 꼴의 보장을 (ε,δ) 보장이라 부르고, 이 글은 같은 ε 와 δ 에 대해 부등식마다 다른 n 을 계산해 견줍니다.
첫째 질문에 바로 대 봅니다. 정답 여부는 0 아니면 1이라 분산이 p(1−p)≤1/4 입니다. ε=0.02, δ=0.05 이면 n≥0.25/(0.05×0.0004)=12,500 입니다. 정규 근사의 2,401보다 다섯 배 넘게 큽니다. 동전 예에서는 P(S−50≥20)≤25/400=0.0625 로, 마르코프의 0.714보다 열 배 낫지만 실제 값과는 여전히 천 배 넘게 떨어져 있습니다.
다항 꼬리
체비쇼프가 느슨한 이유는 분산 말고는 아무것도 쓰지 않기 때문이고, 분산만으로는 이보다 나을 수 없습니다. X 가 ±t 를 각각 확률 σ2/(2t2) 로, 0을 나머지 확률로 갖는 분포를 생각하면 분산이 정확히 σ2 이고 P(∣X∣≥t)=σ2/t2 로 등호가 섭니다. 분산이 같은 분포 가운데 이런 것이 있는 한, 분산만 쓰는 부등식은 꼬리를 t−2 보다 빨리 줄일 수 없습니다.
값을 치르는 것은 δ 쪽입니다. 체비쇼프의 필요 표본 수는 1/δ 에 비례합니다. 실패 확률을 5%에서 100만분의 1로 줄이면 표본이 5만 배 필요합니다. 다음 절의 지수 꼬리에서는 같은 일이 log(1/δ) 에 비례해 일어나 표본이 네 배쯤만 늘어납니다. 체크포인트를 스무 개, 천 개 고르는 장면에서는 δ 를 그 수만큼 나눠 써야 하므로 이 차이가 곧 「할 수 있는 실험」과 「할 수 없는 실험」의 차이가 됩니다.
넣는 함수를 더 높은 적률로 바꾸면 P(∣X−μ∣≥t)≤E∣X−μ∣q/tq 가 되어 꼬리가 t−q 로 줄어듭니다. q 를 끝없이 올리는 대신 모든 적률을 한꺼번에 담은 함수를 넣는 것이 다음 절입니다.
체르노프 방법
적률생성함수
확률변수 X 에 대해
M(λ)=E[eλX],Λ(λ)=logM(λ)
로 두고, 앞의 것을 적률생성함수, 뒤의 것을 누적생성함수라 부릅니다. eλX=∑qλqXq/q! 이므로 적률생성함수는 모든 적률을 계수로 품은 급수이고, 로그를 씌운 누적생성함수는 원점에서 Λ(0)=0, Λ′(0)=E[X], Λ′′(0)=Var(X) 입니다. 원점 근처의 모양은 평균과 분산이 정하고, 원점에서 멀어질수록 높은 적률이 모양을 정합니다.
이 함수가 집중부등식의 주인공인 이유는 독립인 합에서 곱으로 갈라지기 때문입니다. X1,…,Xn 이 독립이면 eλ∑Xi=∏eλXi 의 기댓값이 기댓값의 곱이 되므로
ΛX1+⋯+Xn(λ)=∑i=1nΛXi(λ)
입니다. 분산이 독립 합에서 더해진다는 중급 21번의 가법성을, 누적생성함수는 모든 차수에서 한꺼번에 해냅니다.
체르노프 경계
두 번째 넣기는 지수함수입니다. 아무 λ>0 에서 x↦eλx 는 증가함수이므로 X≥t 와 eλX≥eλt 는 같은 사건이고, 마르코프를 쓰면
P(X≥t)=P(eλX≥eλt)≤e−λtM(λ)=exp(−(λt−Λ(λ)))
입니다. 이 부등식은 모든 λ>0 에서 성립하므로 가장 좋은 λ 를 고를 수 있습니다.
P(X≥t)≤exp(−supλ>0(λt−Λ(λ)))
이렇게 지수 적률에 마르코프를 쓰고 λ 에 대해 최적화하는 절차를 체르노프 방법이라 부릅니다. 지수 안의 supλ(λt−Λ(λ)) 는 누적생성함수의 르장드르 변환이고 Λ∗(t) 로 적습니다.
독립 합에 쓰면 체르노프 방법의 힘이 드러납니다. Xi 가 독립이고 같은 분포이며 평균이 μ 이면, 합의 누적생성함수가 nΛ 이므로
P(Xˉ−μ≥ε)≤exp(−nΛc∗(ε))
입니다. 여기서 Λc 는 중심화한 X−μ 의 누적생성함수입니다. 표본 수 n 이 지수 안으로 들어갔습니다. 실패 확률 δ 를 맞추는 데 필요한 n 이 log(1/δ)/Λc∗(ε) 이 되어, 체비쇼프의 1/δ 가 log(1/δ) 로 바뀝니다. 지수 Λ∗ 는 더 줄일 수 없는 값이라는 것이 크라메르 정리이고, 그래서 체르노프 방법이 잃는 것은 지수 앞의 다항식 크기의 인수뿐입니다.
베르누이의 KL 꼴
정답 여부처럼 Xi∼Bernoulli(p) 인 경우를 끝까지 계산합니다. 합 S 의 적률생성함수는 (1−p+peλ)n 이고, q>p 에 대해 P(S≥nq) 를 누르는 지수 −λnq+nlog(1−p+peλ) 를 λ 로 미분해 0으로 두면
eλ=p(1−q)q(1−p)
입니다. q>p 라 이 값이 1보다 커서 λ>0 이고, 넣으면 1−p+peλ=(1−p)/(1−q) 이므로 지수가
−n[qlogpq+(1−q)log1−p1−q]=−nKL(q∥p)
로 정리됩니다. 베르누이 표본평균이 q 이상으로 나올 확률은 e−nKL(q∥p) 이하이고, 지수에 선 것이 두 베르누이 분포 사이의 KL 발산입니다. 관측된 비율과 참 비율이 정보량으로 얼마나 다른지가 꼬리의 속도를 정한다는 뜻입니다. 이 KL을 KL(q∥p)≥2(q−p)2 로 누르면 지수가 −2n(q−p)2 이 되고, 이것이 4절의 회프딩 부등식과 같은 꼴입니다.
동전 100번에서 앞면이 70번 이상 나올 확률로 넷을 나란히 놓으면 차이가 보입니다. 실제 값은 3.93×10−5 이고, 마르코프는 0.714, 체비쇼프는 0.0625, 회프딩 꼴은 e−8=3.35×10−4, KL 꼴은 2.67×10−4 입니다. 앞의 둘은 그림에서 거의 눕고, 체르노프 방법의 두 꼴은 실제 꼬리와 같은 기울기로 내려갑니다. 남은 일곱 배쯤의 간격이 지수 앞의 다항식 인수이고, t 가 커져도 로그 축에서 벌어지지 않습니다.
서브가우시안과 서브지수
서브가우시안
체르노프 방법이 모든 분포마다 르장드르 변환을 따로 계산하게 두면 일이 끝나지 않습니다. 그래서 누적생성함수를 간단한 함수로 위에서 누르고, 그 누름만 가지고 꼬리를 계산합니다. 가장 흔한 누름은 포물선입니다. 평균이 0인 X 가 모든 실수 λ 에서
Λ(λ)=logE[eλX]≤2λ2σ2
를 만족하면 X 를 서브가우시안이라 부르고, 이때의 σ2 를 분산 프록시라 부릅니다. 평균이 0, 분산이 σ2 인 정규분포의 누적생성함수가 정확히 λ2σ2/2 이므로, 서브가우시안은 「적률생성함수가 분산 σ2 인 정규분포보다 크지 않다」는 말입니다. 원점에서 두 번 미분해 보면 분산은 분산 프록시를 넘을 수 없지만, 둘이 같을 필요는 없습니다.
정의에 체르노프 방법을 쓰면 supλ(λt−λ2σ2/2)=t2/(2σ2) 이므로 P(X≥t)≤e−t2/(2σ2) 입니다. 독립인 서브가우시안을 더하면 누적생성함수가 더해지니 분산 프록시도 더해지고, 평균 Xˉ 는 분산 프록시 σ2/n 인 서브가우시안이 됩니다. 꼬리 계산이 분산 프록시 하나의 산수로 줄어든 셈입니다.
같은 성질을 다르게 적은 정의가 셋 더 있고, 넷은 서로를 절대 상수배 안에서 함의합니다. 상수 K1,…,K4 는 서로 상수배 차이입니다.
꼬리: 모든 t 에서 P(∣X∣≥t)≤2exp(−t2/K12)
적률: 모든 q≥1 에서 (E∣X∣q)1/q≤K2q
제곱의 지수 적률: Eexp(X2/K32)≤2
적률생성함수(평균 0일 때): EeλX≤exp(K42λ2)
적률이 q 보다 빨리 자라지 않는다는 2번이 q 가 클 때 q/e 로 자라는 정규분포의 적률을 흉내 낸 것이고, 1번과 4번 사이를 오가는 것이 체르노프 방법과 그 거꾸로입니다.
오를리츠 노름
3번 정의는 「얼마나 서브가우시안인가」를 숫자 하나로 만듭니다.
∥X∥ψ2=inf{s>0:Eexp(X2/s2)≤2}
를 오를리츠 노름이라 부르고, 아래 첨자 ψ2 는 이 정의가 볼록함수 ψ2(x)=ex2−1 로 만든 것임을 가리킵니다. 확률변수를 볼록함수에 넣은 기댓값으로 크기를 재는 것은 Lp 노름이 xp 로 하는 일과 같고, 볼록성 덕분에 삼각부등식이 서서 진짜 노름이 됩니다. 서브가우시안은 이 노름이 유한한 확률변수이고, 노름이 작을수록 꼬리가 가볍습니다.
몇 개를 직접 계산해 봅니다. 라데마허 변수 ±1 은 X2=1 이라 e1/s2≤2 에서 s=1/log2=1.201 입니다. 표준정규 Z 는 EeZ2/s2=(1−2/s2)−1/2 를 2 이하로 두면 s2≥8/3, 곧 ∥Z∥ψ2=1.633 입니다. 분산이 둘 다 1인데 노름이 다른 것은 정규분포의 꼬리가 라데마허보다 무겁기 때문입니다. 라데마허는 1을 넘는 값이 아예 없습니다.
같은 틀에서 ψ1(x)=ex−1 로 바꾸면 ∥X∥ψ1=inf{s:Eexp(∣X∣/s)≤2} 가 됩니다. 평균 1인 지수분포는 EeX/s=1/(1−1/s) 라 ∥X∥ψ1=2 이고, Z2 은 (1−2/s)−1/2≤2 에서 8/3 입니다. 마지막 값이 ∥Z∥ψ22 과 같은 것은 우연이 아닙니다. 정의를 풀면 언제나 ∥X2∥ψ1=∥X∥ψ22 이고, 더 일반적으로 ∥XY∥ψ1≤∥X∥ψ2∥Y∥ψ2 입니다. 서브가우시안 둘을 곱하면 다음 소절의 서브지수가 됩니다.
서브지수
모든 꼬리가 포물선 아래에 들어가지는 않습니다. Z2−1 의 적률생성함수는 e−λ(1−2λ)−1/2 이라 λ≥1/2 에서 무한대가 됩니다. 어떤 포물선도 이것을 모든 λ 에서 누를 수 없습니다. 대신 원점 근처에서는 누를 수 있습니다. 평균이 0인 X 가
Λ(λ)≤2λ2ν2for all ∣λ∣<1/b
를 만족하면 매개변수 (ν,b) 의 서브지수라 부릅니다. Z2−1 은 ∣λ∣≤1/4 에서 e−λ(1−2λ)−1/2≤e2λ2 이 성립해 (ν,b)=(2,4) 인 서브지수입니다.
체르노프 방법을 쓰면 λ 를 1/b 아래에서만 고를 수 있어 꼬리가 두 국면으로 갈립니다.
P(X≥t)≤⎩⎨⎧exp(−2ν2t2)exp(−2bt)0≤t≤ν2/bt>ν2/b
작게 벗어날 때는 정규분포처럼, 크게 벗어날 때는 지수분포처럼 줄어듭니다. 최적의 λ=t/ν2 가 허용 범위 1/b 를 넘는 순간 경계에 멈춰야 해서 생기는 꺾임입니다. 존슨–린덴스트라우스 보조정리의 원래 증명이 다루는 사영된 길이의 제곱 ∥Rx∥2 이 바로 서브지수입니다. 중급 66번 랜덤 사영과 존슨–린덴스트라우스 보조정리의 지수에 ε2−ε3 처럼 ε 의 높은 차수가 섞여 들어온 것이 이 두 국면의 흔적입니다.
그림의 위계가 이 글의 지도입니다. 바깥으로 갈수록 가정이 약해지고 꼬리가 무거워지며 쓸 수 있는 부등식이 줄어듭니다. 정답 여부, 보상 점수, 잘라 낸 손실처럼 평가에서 다루는 값은 대부분 가장 안쪽의 유계 변수라 모든 도구를 다 쓸 수 있습니다. 그런데 4절에서 보듯, 안쪽에 있다고 해서 가장 안쪽의 도구가 가장 좋은 것은 아닙니다.
최댓값의 기대 상계
서브가우시안 정의가 바로 값을 내는 자리가 하나 있습니다. 평균이 0이고 분산 프록시가 σ2 인 서브가우시안 X1,…,XK 에 대해, 서로 독립이든 아니든
E[maxk≤KXk]≤2σ2logK
입니다. 증명은 세 걸음입니다. 아무 λ>0 에서 젠센 부등식으로 eλE[maxXk]≤E[eλmaxXk] 이고, 최댓값의 지수는 지수들의 최댓값이니 합으로 누르면 E[maxkeλXk]≤∑kE[eλXk]≤Keλ2σ2/2 입니다. 로그를 잡고 λ 로 나누면 E[maxXk]≤logK/λ+λσ2/2 이고, 오른쪽을 최소로 하는 λ=2logK/σ 를 넣으면 끝입니다.
합으로 누른 둘째 걸음에서 독립을 쓰지 않았다는 점이 중요합니다. 같은 문항으로 채점해 서로 강하게 얽힌 점수 스무 개에도 이 상계가 그대로 섭니다. 대가는 K 가 로그로만 들어온다는 것입니다. 독립인 표준정규 스무 개의 최댓값은 평균이 1.867이고 상계는 2log20=2.448 이라, 독립일 때도 상계가 크게 헐겁지 않습니다. K 가 커지면 둘의 비는 1로 갑니다. 셋째 질문의 절반이 이 부등식으로 풀립니다.
회프딩과 베른슈타인
회프딩 보조정리
유계 변수가 서브가우시안이라는 것, 그리고 그 분산 프록시가 얼마인지를 정하는 것이 이 절의 첫 일입니다. X∈[a,b] 이고 평균이 μ 이면 모든 실수 λ 에서
Λ(λ)=logE[eλ(X−μ)]≤8λ2(b−a)2
입니다. 이것을 회프딩 보조정리라 부르고, 분산 프록시가 (b−a)2/4 라는 말입니다.
증명은 누적생성함수를 두 번 미분하는 것으로 끝납니다. 평균을 빼도 범위의 폭은 그대로이므로 μ=0 이라 둡니다. λ 를 하나 고정하고, 원래 분포의 밀도에 eλx/M(λ) 를 곱한 새 분포를 만듭니다. 큰 값 쪽으로 무게를 옮긴 이 분포를 기울인 분포라 부르고, 그 기댓값을 Eλ 로 적습니다. 직접 미분하면
입니다. 누적생성함수의 2계 도함수는 기울인 분포에서 잰 분산입니다. 기울여도 X 의 값은 여전히 [a,b] 안에 있고, [a,b] 안의 확률변수는 어떤 분포든 분산이 (b−a)2/4 이하입니다. 분산은 평균 대신 아무 상수 m 을 빼서 잰 제곱 평균보다 작거나 같은데, m=(a+b)/2 로 두면 ∣X−m∣≤(b−a)/2 이기 때문입니다. 그래서 모든 λ 에서 Λ′′(λ)≤(b−a)2/4 이고, Λ(0)=0, Λ′(0)=0 에서 시작하는 테일러 전개의 라그랑주 나머지로
Λ(λ)=2λ2Λ′′(ξ)≤8λ2(b−a)2
이 나옵니다. ξ 는 0과 λ 사이의 어떤 점입니다.
그림은 중심화한 베르누이의 누적생성함수입니다. p=0.5 이면 분산이 1/4 로 범위가 허락하는 최댓값이라 포물선 λ2/8 에 거의 붙습니다. p=0.05 이면 원점의 곡률, 곧 분산이 0.0475 라 곡선이 훨씬 납작합니다. 회프딩 보조정리는 두 경우를 똑같이 λ2/8 로 셉니다. 범위만 보고 분산을 보지 않기 때문입니다. 이 낭비가 첫머리의 백 배 차이의 정체이고, 붉은 점선이 아래에서 그것을 메웁니다.
회프딩 부등식
보조정리를 체르노프 방법에 넣으면 됩니다. Xi∈[ai,bi] 가 독립이고 S=∑i(Xi−EXi), D=∑i(bi−ai)2 이라 하면, 누적생성함수가 더해지므로 모든 λ>0 에서
P(S≥t)≤exp(−λt+8λ2D)
이고, 지수를 최소로 하는 λ=4t/D 를 넣으면 −4t2/D+2t2/D 가 남아
P(S≥t)≤exp(−∑i(bi−ai)22t2)
를 얻습니다. 이것이 회프딩 부등식입니다. 아래 꼬리도 같고, 양쪽을 합치면 오른쪽에 2가 붙습니다. [0,1] 에 있는 값 n 개의 평균으로 쓰면
P(∣Xˉ−μ∣≥ε)≤2e−2nε2,n≥2ε2log(2/δ)
입니다. 첫째 질문에 대면 log40/(2×0.0004)=4,611 문항입니다. 분포 가정 없이, 어떤 정답률에서도 성립하는 보장입니다. 체비쇼프의 12,500보다 세 배 가까이 작고, 정규 근사의 2,401보다 두 배 큽니다.
고급 5번 조건부 기댓값은 사영이다, 그리고 마팅게일의 아주마–회프딩 부등식은 증분이 ∣Dk∣≤ck 일 때 exp(−t2/(2∑ck2)) 를 주었습니다. 증분이 [−c,c] 처럼 0을 가운데 둔 구간에 있으면 폭이 2c 라 두 식이 정확히 같습니다. [0,1] 값에서 모르는 평균을 뺀 것처럼 구간이 어디에 놓일지 모르면, 절댓값으로 묶을 때 c=1 을 써야 해서 지수가 t2/(2n) 이 되고, 폭으로 묶는 회프딩은 2t2/n 이라 네 배 날카롭습니다. 그 글이 미뤄 둔 「(b−a)2/8 판」이 이것입니다.
베른슈타인 부등식
분산을 쓰려면 누적생성함수를 원점의 곡률로 누르면 됩니다. Y=X−μ 가 ∣Y∣≤b 이고 분산이 σ2 이면 q≥2 에서 E∣Y∣q≤σ2bq−2 이고, q!≥2⋅3q−2 입니다. 평균이 0이라 1차 항이 사라지므로 급수를 항별로 누르면
E[eλY]≤1+2λ2σ2∑q≥2(3∣λ∣b)q−2=1+1−∣λ∣b/3λ2σ2/2
입니다. 1+x≤ex 로 지수에 올리면 ∣λ∣<3/b 에서 Λ(λ)≤1−∣λ∣b/3λ2σ2/2 입니다. 분모가 1에 가까운 원점 근처에서는 곡률이 분산 σ2 그대로이고, λ 가 커지면 위로 휩니다. 앞 그림의 붉은 점선이 이것입니다. 유계 변수가 분산 프록시 ν2≈σ2 인 서브지수라는 말이기도 합니다.
나머지는 앞과 같은 산수입니다. n 개를 더하면 분산이 V=nσ2 로 더해지고, λ=t/(V+bt/3) 를 넣으면 1−λb/3=V/(V+bt/3) 라 지수가 깔끔하게 정리됩니다.
이것이 베른슈타인 부등식입니다. 고급 6번 스케치와 행렬 집중부등식이 행렬로 올려 쓴 그 부등식의 스칼라 판이고, 거기서 「증명은 고급 8번에서」라고 미뤄 둔 계산이 위의 다섯 줄입니다. 분모의 두 항이 서브지수의 두 국면입니다. 벗어나는 크기 ε 가 3σ2/b 보다 작으면 2σ2 이 이겨 정규분포처럼, 크면 2bε/3 이 이겨 지수분포처럼 줄어듭니다. 양쪽 꼬리를 합친 필요 표본 수는
n≥ε2(2σ2+2bε/3)log(2/δ)
입니다.
분산의 값
둘째 질문에 넣어 봅니다. 유해 응답 비율 p=0.005, 오차 ε=0.005, δ=0.05 입니다. 분산은 σ2=0.004975 이고 b=1 이므로 분모가 0.00995+0.00333=0.01328, 필요 표본 수는 0.01328×3.689/0.000025=1,961 입니다. 같은 ε 와 δ 에서 회프딩은 log40/(2×0.000025)=73,778 이라 37.6배 차이가 납니다. 분산만 쓰는 체비쇼프도 0.004975/(0.05×0.000025)=3,980 으로 회프딩보다 열여덟 배 낫습니다. 꼬리를 다룰 줄 아는 회프딩이 다항 꼬리밖에 못 다루는 체비쇼프에게 지는 것은 회프딩이 분산을 1/4 로 셈해 버리기 때문입니다.
서브가우시안의 틀 안에서는 이것을 고칠 수 없습니다. 베르누이(0.005) 에서 정의를 만족하는 가장 작은 분산 프록시는 supλ2Λ(λ)/λ2 를 계산하면 (1−2p)/(2log((1−p)/p))=0.0935 로, 실제 분산의 19배입니다. 원점 근처의 곡률은 작지만 λ 가 크면 드문 1이 무게를 얻어 누적생성함수가 포물선을 밀어 올리기 때문입니다. 분산을 살리려면 원점 근처에서만 포물선으로 누르는 서브지수의 틀, 곧 베른슈타인이 필요합니다. 비율이 1/2에 가까우면 분산이 범위의 최댓값과 같아 둘이 비슷하고(p=0.5 에서 베른슈타인 4,734, 회프딩 4,611), 드문 사건을 셀수록 베른슈타인이 이깁니다. 안전성 평가, 오류율, 거부율처럼 0에 붙은 비율을 재는 일은 거의 언제나 이 쪽입니다.
맥디아미드와 합집합 경계
유계 차분 조건
지금까지는 평균만 다뤘습니다. 평가에서 쓰는 값 가운데는 평균이 아닌 것이 많습니다. 스무 개 체크포인트의 최고 점수가 그렇고, 양성 n+ 개와 음성 n− 개를 쌍으로 비교해 올바르게 순위를 매긴 쌍의 비율을 세는 AUROC도 그렇습니다. 이런 값을 독립인 표본 X1,…,Xn 의 함수 f 로 보고, 한 표본만 바꿨을 때 값이 얼마나 움직일 수 있는지를 봅니다. 모든 i 와 모든 x1,…,xn,xi′ 에서
∣f(x1,…,xi,…,xn)−f(x1,…,xi′,…,xn)∣≤ci
가 성립하면 f 가 유계 차분 조건을 만족한다고 말합니다. 표본 하나가 결과를 쥐고 흔들 수 없다는 조건입니다.
예를 셋 봅니다. [0,1] 값의 평균은 ci=1/n 입니다. 같은 문항 n 개로 채점한 체크포인트 K 개의 최고 점수도 문항 하나를 바꾸면 각 점수가 1/n 이하로 움직이고, 최댓값은 각 값이 움직인 폭보다 더 움직이지 않으므로 ci=1/n 입니다. 체크포인트끼리는 같은 문항을 공유해 서로 얽혀 있지만 그것은 아무 문제가 되지 않습니다. 독립이어야 하는 것은 문항이지 체크포인트가 아닙니다. AUROC는 양성 하나가 음성 n− 개와의 쌍에만 관여하므로 ci=n−/(n+n−)=1/n+, 음성 하나는 1/n− 입니다.
맥디아미드 부등식
유계 차분 조건이 서면
P(f(X)−Ef(X)≥t)≤exp(−∑ici22t2)
입니다. 이것이 맥디아미드 부등식이고, 평균이라는 특정한 함수에 대한 회프딩 부등식을 유계 차분인 모든 함수로 넓힌 것입니다.
증명의 줄기는 고급 5번의 마팅게일입니다. 표본을 하나씩 드러내며 조건부 기댓값을 잡은 Zk=E[f(X)∣X1,…,Xk] 를 둡 마팅게일이라 부르고, Z0=Ef(X) 에서 출발해 Zn=f(X) 에 닿습니다. 구하려는 편차 f−Ef 가 증분 Dk=Zk−Zk−1 의 합으로 쪼개진 셈입니다. 표본이 독립이므로 앞의 k−1 개를 고정했을 때 Zk 는 xk 만의 함수 gk(xk)=E[f(x1,…,xk,Xk+1,…,Xn)] 이고, 기댓값 안에서 k 번째 자리만 바뀌므로 gk 가 움직이는 폭은 ck 이하입니다. 곧 Dk 는 과거가 정하는 폭 ck 짜리 구간 안에 있고 조건부 평균이 0입니다. 회프딩 보조정리를 조건부로 쓰면 E[eλDk∣X1,…,Xk−1]≤eλ2ck2/8 이고, 고급 5번의 아주마–회프딩 증명처럼 걸음마다 꺼내 곱하면 E[eλ(f−Ef)]≤eλ2∑ck2/8 이 남습니다. 마지막은 회프딩 부등식과 똑같은 최적화입니다.
셋째 질문의 나머지 절반에 대 봅니다. 최고 점수는 ci=1/2000 이라 ∑ci2=1/2000 이고, 양쪽 꼬리 δ=0.05 에서 t=log40/(2×2000)=0.0304 입니다. 문항 2,000개를 새로 뽑아 다시 채점해도 최고 점수는 그 기댓값에서 3.04%p 넘게 벗어날 확률이 5% 이하라는 보장입니다. 스무 개 점수가 모두 참값 70%인 경우를 이십만 번 흉내 내면 최고 점수의 표준편차는 0.53%p이고, 3.04%p를 넘게 벗어난 비율은 1.5×10−5 입니다. 맥디아미드는 최댓값이 점수 하나보다도 좁게 모인다는 사실까지는 쓰지 못해 넉넉하지만, 체크포인트 사이의 얽힘을 하나도 몰라도 된다는 것이 값입니다. AUROC에서는 n+=n−=1,000 이면 ∑ci2=0.002 라 같은 δ 에서 t=0.0607 입니다.
합집합 경계
체크포인트 스무 개의 점수가 모두 참값 근처에 있을 확률은 어떻게 셀까요. 사건 A1,…,AK 에 대해
P(⋃k=1KAk)≤∑k=1KP(Ak)
를 합집합 경계라 부릅니다. 겹치는 부분을 여러 번 세는 것을 허락하고 합으로 누르는 것이라, 사건들이 서로 어떻게 얽혀 있는지 몰라도 됩니다. Ak 를 「k 번째 체크포인트의 점수가 참값에서 ε 이상 벗어난다」로 두고 각각에 회프딩을 쓰면
P(maxk≤K∣p^k−pk∣≥ε)≤2Ke−2nε2,n≥2ε2log(2K/δ)
입니다. δ 를 K 개로 나눠 쓰는 대가가 로그 하나로 들어온다는 것이 체르노프 방법의 지수 꼬리 덕분입니다. ε=0.02, δ=0.05 이면 K=1 에서 4,611문항, K=20 에서 8,356문항, K=1,000 에서 13,246문항입니다. 거꾸로 문항을 2,000개로 고정하면 스무 개 전부를 동시에 보장하는 폭은 log800/4000=4.09%p이고, 천 개면 5.15%p입니다. 체비쇼프로 같은 일을 하면 K 가 δ 의 자리에 곱해져 표본이 K 배로 늘어납니다.
존슨–린덴스트라우스 보조정리의 마지막 걸음이 이것입니다. 점 쌍 n2/2 개마다 서브지수 꼬리를 쓰고 합집합 경계로 묶으면 필요한 차원이 logn 에 비례하게 됩니다. 쌍의 수가 지수 꼬리와 만나 로그로 바뀐 것입니다.
최고 점수의 치우침
이제 72.1%를 읽을 수 있습니다. 문항 2,000개에서 정답률의 편차 p^k−pk 는 회프딩 보조정리로 분산 프록시 1/(4n) 인 서브가우시안이고, 최댓값의 기대 상계가 독립을 요구하지 않으므로
입니다. 골라 낸 체크포인트 k∗ 의 p^k∗−pk∗ 는 이 최댓값을 넘을 수 없으므로, 최고 점수는 평균적으로 그 체크포인트의 참값보다 2.74%p까지 부풀어 있을 수 있습니다. 여러 후보 가운데 측정값이 가장 좋은 것을 고르면 고른 행위 자체가 측정값을 위로 끌어올린다는 이 현상을 승자의 저주라 부릅니다.
그림은 스무 개가 모두 참값 70%인, 곧 아무것도 나아지지 않은 경우를 이십만 번 흉내 낸 것입니다. 최고 점수의 평균은 71.9%로 참값보다 1.91%p 높고, 상계 72.7%가 그 위에 섭니다. 팀이 고른 72.1%는 이 분포의 한가운데에 있습니다. 「70%보다 2%p 낫다」는 문장은 스무 개를 채점하고 최고를 골랐다는 사실만으로 설명되고, 실제로 나아졌다는 증거가 되지 못합니다. 처방은 고른 체크포인트를 고르는 데 쓰지 않은 새 문항으로 다시 채점하는 것입니다. 그 채점은 후보가 하나라 K=1 의 보장이 다시 섭니다.
후보가 스무 개가 아니라 연속적인 하이퍼파라미터나 신경망 가중치 전체라면 K 가 무한해 합집합 경계가 그대로는 쓸모없어집니다. 무한한 후보를 유한한 대표로 덮어 logK 자리에 복잡도를 놓는 것이 다음 글의 일입니다.
필요 표본 수
네 공식
지금까지의 결과를 양쪽 꼬리, 같은 ε 와 δ 로 나란히 적습니다.
방법
필요 표본 수 n
쓰는 정보
정규 근사
zδ/22σ2/ε2
분산, 그리고 n 이 충분히 크다는 가정
체비쇼프
σ2/(δε2)
분산
회프딩
log(2/δ)/(2ε2)
범위
베른슈타인
(2σ2+2ε/3)log(2/δ)/ε2
범위와 분산
정규 근사의 zδ/2 는 표준정규분포의 위쪽 δ/2 분위수로, δ=0.05 에서 1.96입니다. 아래 셋은 표본 수가 얼마든 성립하는 보장이고, 정규 근사만 n→∞ 의 극한에서 온 어림입니다. 첫머리 두 질문에 넣으면 이렇습니다. 「정확」은 이항분포의 확률을 직접 더해, 그 n 부터는 실패 확률이 계속 δ 이하로 머무는 가장 작은 n 입니다.
정규 근사
체비쇼프
회프딩
베른슈타인
정확
정답률 ±2%p, p 모름
2,401
12,500
4,611
4,734
2,424
유해 응답 ±0.5%p, p=0.005
765
3,980
73,778
1,961
800
첫 줄은 p 를 모르므로 분산을 최댓값 1/4 로 두었습니다. 이 줄에서는 회프딩과 베른슈타인이 거의 같고 정확값의 두 배 안쪽입니다. 둘째 줄에서 두 사람의 계산이 갈린 이유가 보입니다. 765는 정규 근사이고 73,778은 분산을 버린 회프딩입니다. 보장으로 말할 수 있는 가장 작은 수는 베른슈타인의 1,961이고, 실제로 필요한 것은 800입니다.
그림이 ε=0.005, δ=0.05 에서 p 를 0.1%부터 50%까지 바꾼 것입니다. 회프딩은 p 를 보지 않으니 수평선이고, 분산을 쓰는 셋은 p 가 작아질수록 내려갑니다. 베른슈타인은 그림 전체에서 정확값의 1.9~4.7배 안에 머뭅니다. 보장을 원하면서 비율이 작은 일을 재면 베른슈타인을 쓰라는 결론이 이 그림입니다.
정규 근사의 붕괴
그림에서 정규 근사는 정확값에 놀랍도록 가깝습니다. 그래도 그것을 보장으로 쓰면 안 되는 자리가 셋 있습니다.
첫째, 기대 개수가 작을 때입니다. 그림의 왼쪽 끝 p=0.13% 에서 정규 근사는 199문항이라 하는데 정확값은 318입니다. 199문항에서 유해 응답의 기대 개수는 0.26개라, 0 아니면 1인 개수를 연속인 종 모양으로 어림하는 것 자체가 성립하지 않습니다. 중급 74번이 정답률 95% 근처에서 본 실패와 같은 원인이 반대쪽 끝에서 일어난 것입니다.
둘째, δ 가 작을 때입니다. 유해 응답 예에서 δ 만 줄여 가며, 정규 근사가 준 n 에서 실제 실패 확률을 정확히 세었습니다.
목표 δ
정규 근사의 n
실제 실패 확률
목표 대비
0.05
765
4.10×10−2
0.82배
0.0025
1,819
2.64×10−3
1.06배
10−4
3,013
2.03×10−4
2.03배
10−6
4,762
8.04×10−6
8.04배
목표가 엄할수록 약속이 크게 어긋납니다. 0에 붙은 비율의 표본평균은 오른쪽 꼬리가 길게 늘어진 비대칭 분포인데, 정규 근사는 좌우 대칭인 꼬리를 가정합니다. 한가운데에서는 그 차이가 작지만 꼬리 끝으로 갈수록 커집니다. 2행의 0.0025가 체크포인트 스무 개에 5%를 나눠 준 값이고, 수천 개의 범주나 시점에 같은 일을 하면 3행과 4행의 영역에 들어갑니다. 합집합 경계로 δ 를 잘게 나누는 순간 정규 근사는 믿을 수 없는 도구가 됩니다.
셋째, p 를 모를 때입니다. 위의 계산은 참값 p=0.005 를 알고 했습니다. 실제로는 p 를 모르고 관측된 p^ 로 표준오차를 계산하는데, 그렇게 그린 정규 근사 구간 p^±1.96p^(1−p^)/n 이 765문항에서 참값을 품을 확률을 정확히 세면 0.889입니다. 0개가 나와 구간이 점 [0,0] 으로 줄어드는 경우가 2.2%나 되고, 적게 나온 경우 구간이 지나치게 좁아지기 때문입니다.
판정을 한 줄로 줄이면 이렇습니다. 기대 개수 np(1−p) 가 수십을 넘고, δ 가 1% 근처 이상이며, 표준오차에 참값 대신 관측값을 넣는 것이 큰 차이를 내지 않을 때 정규 근사는 정확값에 가까운 좋은 어림입니다. 셋 가운데 하나라도 어긋나면 베른슈타인의 n 을 쓰고, 그 값은 정확값보다 몇 배 크지만 언제나 참입니다. 베른슈타인 분모의 두 항을 견주는 것도 같은 판정을 다른 말로 한 것입니다. 2ε/3 항이 2σ2 항에 견줄 만해지면 꼬리가 정규분포의 국면을 벗어나고 있다는 신호입니다. 유해 응답 예는 그 비가 0.33이라 이미 경계에 서 있었습니다.
다시 평가표로
세 질문
첫째 질문, 정답률 ±2%p를 95%로 보장하려면 4,611문항입니다. 회프딩 부등식이 어떤 정답률에서나 이것을 보장하고, 정규 근사의 2,401은 정답률 50% 근처에서 정확값 2,424에 가까운 좋은 어림이지만 보장은 아닙니다. 둘째 질문, 유해 응답 비율 ±0.5%p는 보장으로 1,961문항, 실제로는 800문항이면 됩니다. 정규 근사의 765는 기대 개수가 3.8개인 자리라 경계에 걸쳐 있고, 회프딩의 73,778은 틀리지는 않았지만 분산을 버려 37.6배를 더 씁니다. 셋째 질문, 72.1%는 아무것도 나아지지 않았어도 스무 개 가운데 최고를 골랐다는 사실만으로 평균 1.9%p, 많게는 2.7%p 부풀어 있을 수 있고, 최고 점수 자체는 맥디아미드로 기댓값 ±3.04%p 안에 머뭅니다. 「2%p 낫다」를 주장하려면 새 문항으로 다시 재야 합니다.
코드로 확인하기
본문의 숫자를 한 번에 다시 계산합니다. 이항분포의 확률은 로그 감마 함수로 직접 셉니다.
import numpy as npfrom math import lgamma, log, exp, sqrt, ceildef pmf(n, p): # 이항분포 Bin(n, p) 의 확률 전부 k = np.arange(n + 1) lg = np.vectorize(lgamma) return np.exp(lg(n + 1) - lg(k + 1) - lg(n - k + 1) + k * log(p) + (n - k) * log(1 - p))def fail(n, p, eps): # P(|p̂ − p| > eps) 를 정확히 k = np.arange(n + 1) return pmf(n, p)[np.abs(k / n - p) > eps + 1e-12].sum()# ① 동전 100번, 앞면이 70번 이상n, t = 100, 20q = 0.5 + t / nkl = q * log(q / 0.5) + (1 - q) * log((1 - q) / 0.5)print(f"{pmf(n, .5)[50 + t:].sum():.2e} {50/(50+t):.3f} {25/t**2:.4f} " f"{exp(-2*t*t/n):.2e} {exp(-n*kl):.2e}") # 실제, 마르코프, 체비쇼프, 회프딩, KL# 3.93e-05 0.714 0.0625 3.35e-04 2.67e-04# ② 유해 응답률 p = 0.5% 를 ±0.5%p 안으로, 실패 확률 δ = 5%p, eps, d = 0.005, 0.005, 0.05v, z = p * (1 - p), 1.959964need = {"normal": z*z*v/eps**2, "cheb": v/(d*eps**2), "bern": (2*v + 2*eps/3) * log(2/d) / eps**2, "hoeff": log(2/d) / (2*eps**2)}print({k: ceil(x) for k, x in need.items()})# {'normal': 765, 'cheb': 3980, 'bern': 1961, 'hoeff': 73778}bad = [m for m in range(1, 4000) if fail(m, p, eps) > d]print("exact", bad[-1] + 1) # 이 n 부터는 계속 δ 이하# exact 800m = ceil(need["normal"]); k = np.arange(m + 1); ph = k / mhalf = z * np.sqrt(ph * (1 - ph) / m) # 플러그인 정규 근사 구간의 반폭print(round(fail(m, p, eps), 3), round(pmf(m, p)[np.abs(ph - p) <= half].sum(), 3))# 0.041 0.889# ③ δ 를 줄이면 정규 근사의 n 에서 실제 실패 확률은for d in [0.05, 0.0025, 1e-4, 1e-6]: zz = {0.05: 1.959964, 0.0025: 3.023341, 1e-4: 3.890592, 1e-6: 4.891638}[d] m = ceil(zz * zz * v / eps**2) print(d, m, f"{fail(m, p, eps):.2e}", round(fail(m, p, eps) / d, 2))# 0.05 765 4.10e-02 0.82# 0.0025 1819 2.64e-03 1.06# 0.0001 3013 2.03e-04 2.03# 1e-06 4762 8.04e-06 8.04# ④ 체크포인트 20개가 모두 70%, 문항 2,000개rng = np.random.default_rng(0)nq, K, p = 2000, 20, 0.7best = (rng.binomial(nq, p, size=(200_000, K)) / nq).max(axis=1)print(round(best.mean() - p, 4), round(sqrt(log(K) / (2 * nq)), 4)) # 실제 치우침, 상계# 0.0191 0.0274tm = sqrt(log(2 / 0.05) / (2 * nq)) # 맥디아미드 폭print(round(tm, 4), (np.abs(best - best.mean()) >= tm).mean())# 0.0304 1.5e-05
①의 다섯 수가 꼬리 그림의 t=20 세로줄이고, ②가 필요 표본 수 표의 둘째 줄입니다. 정규 근사의 765문항에서 참값을 아는 경우의 실패 확률은 0.041로 약속을 지키지만, 관측값을 넣어 그린 구간의 포함 확률은 0.889로 떨어집니다. ③의 마지막 열이 「목표 대비」이고, ④가 승자의 저주와 맥디아미드 폭입니다. ④에서 상계 0.0274는 분산 프록시를 범위로 정한 1/(4n) 으로 계산한 값이라, 정답률 70%의 실제 표준편차 0.21/2000=0.0102 를 넣으면 0.0102×2log20=0.0251 로 조금 줄어듭니다. 실제 0.0191과의 남은 간격은 최댓값의 기대 상계가 독립을 쓰지 않은 대가입니다.
연습
참 정답률이 p=0.8 인 모델을 400문항으로 채점합니다. P(∣p^−0.8∣≥0.05) 를 체비쇼프, 회프딩(양쪽), 베른슈타인(양쪽, b=1)으로 각각 누르고 어느 것이 가장 날카로운지 말하세요.
체비쇼프는 0.16/(400×0.0025)=0.16, 회프딩은 2e−2⋅400⋅0.0025=2e−2=0.271, 베른슈타인은 2exp(−1/(0.32+0.0333))=2e−2.83=0.118 입니다. 베른슈타인이 가장 날카롭고, 이 크기에서는 체비쇼프도 회프딩보다 낫습니다. 분산 0.16이 범위가 허락하는 0.25보다 작아서입니다. 이항분포로 직접 세면 0.0147입니다.
회프딩으로 정답률을 ε=0.01, δ=0.01 로 보장하는 문항 수를 구하세요. 같은 문항으로 체크포인트 50개를 동시에 보장하려면 몇 문항이 되나요.
log(200)/(2×0.0001)=26,492 문항입니다. 50개면 δ 를 50으로 나눠 log(10,000)/0.0002=46,052 문항입니다. 후보가 50배인데 문항은 1.74배만 늘어납니다.
±2 를 반반으로 갖는 X 의 ∥X∥ψ2 와, 평균 0, 분산 4인 정규분포 Y 의 ∥Y∥ψ2 와 ∥Y2∥ψ1 을 구하세요.
X2=4 라 e4/s2≤2 에서 s=2/log2=2.402 입니다. Y=2Z 이고 노름은 상수배를 그대로 따르므로 28/3=3.266 입니다. EeY2/s=(1−8/s)−1/2≤2 에서 s=32/3=10.667 이고, 이것이 3.2662 과 같습니다.
문항 5,000개로 체크포인트 100개를 채점했습니다. 편차 p^k−pk 의 분산 프록시를 회프딩 보조정리로 정할 때, 최고 점수가 그 체크포인트의 참값보다 평균적으로 얼마까지 부풀 수 있나요.
분산 프록시가 1/(4⋅5000) 이라 2log100/20000=4.605/10000=0.0215, 곧 2.15%p입니다. 체크포인트끼리 얽혀 있어도 그대로입니다.
양성 500개, 음성 2,000개로 AUROC를 잽니다. 유계 차분 상수를 적고, 맥디아미드로 양쪽 δ=0.05 에서 AUROC가 기댓값에서 벗어날 수 있는 폭 t 를 구하세요.
양성 하나는 c=1/500, 음성 하나는 c=1/2000 입니다. ∑ci2=500/5002+2000/20002=0.002+0.0005=0.0025 이고, 2e−2t2/0.0025=0.05 에서 t=0.0025log40/2=0.0679 입니다. 적은 쪽 클래스가 폭을 거의 다 정합니다.
오류율 p=0.02 를 ε=0.01, δ=0.05 로 재려 합니다. 회프딩, 베른슈타인, 정규 근사의 필요 문항 수를 구하고 정규 근사의 기대 오류 개수를 적으세요.
회프딩 log40/0.0002=18,444, 베른슈타인 (0.0392+0.00667)×3.689/0.0001=1,692, 정규 근사 1.962×0.0196/0.0001=753 입니다. 753문항의 기대 오류 개수는 15.1개라 정규 근사가 크게 빗나가지 않는 자리이고, 보장이 필요하면 베른슈타인의 1,692를 씁니다.
집중부등식은 「표본 n 개면 오차 ε 를 확률 1−δ 로」라는 문장을 만드는 기계였습니다. 마르코프에 무엇을 넣느냐가 전부였고, 지수함수를 넣는 체르노프 방법이 1/δ 를 log(1/δ) 로 바꿨습니다. 회프딩은 범위만으로, 베른슈타인은 분산까지 써서 그 지수를 정했고, 맥디아미드는 평균이 아닌 함수로, 합집합 경계는 여러 사건으로 넓혔습니다. 첫머리의 평가표로 돌아가면, 2,000문항의 72.1%는 스무 개 가운데 고른 숫자라 나아졌다는 증거가 못 되고, 유해 응답 비율은 정규 근사의 765도 회프딩의 73,778도 아닌 베른슈타인의 1,961이 보장의 숫자였습니다. 같은 도구로 LSH의 충돌 확률 보장, 밴딧 UCB가 팔마다 붙이는 신뢰폭 2logt/na(고급 A14 단원), 그리고 「표본 n 개면 오차 ε 를 확률 1−δ 로 보장한다」는 모든 알고리즘 정리가 증명됩니다. 남은 구멍은 후보가 무한할 때입니다. 합집합 경계의 logK 가 무한대가 되는 자리를 어떻게 메우는지, 그리고 그렇게 얻은 고전적 일반화 경계가 큰 신경망 앞에서 왜 공허해지는지는 다음 글 「고급 9번 · 일반화 경계: 고전 이론이 공허해지는 자리와 PAC-Bayes」가 다룹니다.
갱신 −ηP⁻¹∇를 노름의 최급강하로 읽고 헤세·가우스–뉴턴·피셔·경험적 피셔의 관계를 정리한 뒤, 준뉴턴과 3차 정규화, K-FAC의 크로네커 인수분해와 그 독립 가정, Shampoo의 −1/4 지수, Muon의 스펙트럴 노름 유도를 차례로 세워 이들이 어디서 일치하는지 보입니다.