수학

MATH / 고급 8번

집중부등식: 표본 하나가 기댓값에서 얼마나 벗어나는가

마르코프·체비쇼프에서 체르노프 방법으로 올라가 서브가우시안·서브지수와 오를리츠 노름을 세우고, 회프딩·베른슈타인·맥디아미드와 합집합 경계를 증명합니다. 각 부등식이 요구하는 문항 수를 정규 근사와 나란히 계산해 그 근사가 무너지는 자리를 가립니다.

PALDYN Team62 MIN READ

모델을 학습하는 팀이 체크포인트 스무 개를 사내 평가 세트 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 추정량의 분산을 그때그때 직접 계산했습니다. 이 글은 그 계산을 일반적인 도구로 바꿉니다. 독립인 표본 여럿에서 계산한 값이 그 기댓값에서 tt 이상 벗어날 확률을 tt 의 함수로 위에서 누르는 부등식을 통틀어 집중부등식이라 부르고, 세 질문은 모두 이 부등식 몇 개로 답이 납니다.

마르코프와 체비쇼프

마르코프 부등식

출발점은 한 줄짜리 부등식입니다. X≥0X \ge 0 이고 t>0t > 0 이면

P(X≥t)≤E[X]tP(X \ge t) \le \frac{\mathbb{E}[X]}{t}

입니다. 이것이 마르코프 부등식이고, 증명은 지시함수 하나로 끝납니다. X≥tX \ge t 인 자리에서는 X≥t⋅1X \ge t \cdot 1 이고 나머지 자리에서는 X≥0=t⋅0X \ge 0 = t \cdot 0 이므로 언제나 X≥t⋅1{X≥t}X \ge t \cdot \mathbf{1}\{X \ge t\} 입니다. 양변의 기댓값을 잡으면 E[X]≥t P(X≥t)\mathbb{E}[X] \ge t \, P(X \ge t) 가 남습니다.

평균 하나만 아는 값에서 얻을 수 있는 것은 정확히 이만큼입니다. XX 가 확률 E[X]/t\mathbb{E}[X]/t 로 tt, 나머지 확률로 0인 분포를 생각하면 등호가 서기 때문입니다. 공정한 동전을 100번 던져 앞면 수 SS 가 70 이상일 확률을 마르코프로 누르면 50/70=0.71450/70 = 0.714 입니다. 실제 확률은 3.9×10−53.9 \times 10^{-5} 이니 쓸모가 없어 보이지만, 이 부등식은 그 자체로 쓰는 도구가 아니라 다른 부등식을 만드는 재료입니다. XX 자리에 XX 의 함수를 넣을 때마다 새 부등식이 하나씩 나오고, 이 글의 나머지가 전부 그 넣기입니다.

체비쇼프 부등식

첫 번째 넣기는 편차의 제곱입니다. 평균이 μ\mu, 분산이 σ2\sigma^2 인 XX 에 대해 (X−μ)2≥0(X - \mu)^2 \ge 0 에 마르코프를 쓰면

P(∣X−μ∣≥t)=P((X−μ)2≥t2)≤σ2t2P(\lvert X - \mu \rvert \ge t) = P\big((X - \mu)^2 \ge t^2\big) \le \frac{\sigma^2}{t^2}

입니다. 이것이 체비쇼프 부등식이고, 중급 21번 분산과 표준오차가 대수의 법칙을 분포 가정 없이 끌어낼 때 쓴 도구입니다. 표본평균 Xˉ\bar X 의 분산은 σ2/n\sigma^2/n 이므로

P(∣Xˉ−μ∣≥ε)≤σ2nε2P(\lvert \bar X - \mu \rvert \ge \varepsilon) \le \frac{\sigma^2}{n \varepsilon^2}

이고, 오른쪽을 실패 확률 δ\delta 이하로 만드는 표본 수는 n≥σ2/(δε2)n \ge \sigma^2 / (\delta \varepsilon^2) 입니다. 「표본 nn 개면 오차 ε\varepsilon 를 확률 1−δ1 - \delta 로 보장한다」는 문장이 처음으로 식이 됐습니다. 이 꼴의 보장을 (ε,δ)(\varepsilon, \delta) 보장이라 부르고, 이 글은 같은 ε\varepsilon 와 δ\delta 에 대해 부등식마다 다른 nn 을 계산해 견줍니다.

첫째 질문에 바로 대 봅니다. 정답 여부는 0 아니면 1이라 분산이 p(1−p)≤1/4p(1 - p) \le 1/4 입니다. ε=0.02\varepsilon = 0.02, δ=0.05\delta = 0.05 이면 n≥0.25/(0.05×0.0004)=12,500n \ge 0.25/(0.05 \times 0.0004) = 12{,}500 입니다. 정규 근사의 2,401보다 다섯 배 넘게 큽니다. 동전 예에서는 P(S−50≥20)≤25/400=0.0625P(S - 50 \ge 20) \le 25/400 = 0.0625 로, 마르코프의 0.714보다 열 배 낫지만 실제 값과는 여전히 천 배 넘게 떨어져 있습니다.

다항 꼬리

체비쇼프가 느슨한 이유는 분산 말고는 아무것도 쓰지 않기 때문이고, 분산만으로는 이보다 나을 수 없습니다. XX 가 ±t\pm t 를 각각 확률 σ2/(2t2)\sigma^2/(2t^2) 로, 0을 나머지 확률로 갖는 분포를 생각하면 분산이 정확히 σ2\sigma^2 이고 P(∣X∣≥t)=σ2/t2P(\lvert X \rvert \ge t) = \sigma^2/t^2 로 등호가 섭니다. 분산이 같은 분포 가운데 이런 것이 있는 한, 분산만 쓰는 부등식은 꼬리를 t−2t^{-2} 보다 빨리 줄일 수 없습니다.

값을 치르는 것은 δ\delta 쪽입니다. 체비쇼프의 필요 표본 수는 1/δ1/\delta 에 비례합니다. 실패 확률을 5%에서 100만분의 1로 줄이면 표본이 5만 배 필요합니다. 다음 절의 지수 꼬리에서는 같은 일이 log⁡(1/δ)\log(1/\delta) 에 비례해 일어나 표본이 네 배쯤만 늘어납니다. 체크포인트를 스무 개, 천 개 고르는 장면에서는 δ\delta 를 그 수만큼 나눠 써야 하므로 이 차이가 곧 「할 수 있는 실험」과 「할 수 없는 실험」의 차이가 됩니다.

넣는 함수를 더 높은 적률로 바꾸면 P(∣X−μ∣≥t)≤E∣X−μ∣q/tqP(\lvert X - \mu \rvert \ge t) \le \mathbb{E}\lvert X - \mu \rvert^q / t^q 가 되어 꼬리가 t−qt^{-q} 로 줄어듭니다. qq 를 끝없이 올리는 대신 모든 적률을 한꺼번에 담은 함수를 넣는 것이 다음 절입니다.

체르노프 방법

적률생성함수

확률변수 XX 에 대해

M(λ)=E[eλX],Λ(λ)=log⁡M(λ)M(\lambda) = \mathbb{E}[e^{\lambda X}], \qquad \Lambda(\lambda) = \log M(\lambda)

로 두고, 앞의 것을 적률생성함수, 뒤의 것을 누적생성함수라 부릅니다. eλX=∑qλqXq/q!e^{\lambda X} = \sum_q \lambda^q X^q / q! 이므로 적률생성함수는 모든 적률을 계수로 품은 급수이고, 로그를 씌운 누적생성함수는 원점에서 Λ(0)=0\Lambda(0) = 0, Λ′(0)=E[X]\Lambda'(0) = \mathbb{E}[X], Λ′′(0)=Var(X)\Lambda''(0) = \mathrm{Var}(X) 입니다. 원점 근처의 모양은 평균과 분산이 정하고, 원점에서 멀어질수록 높은 적률이 모양을 정합니다.

이 함수가 집중부등식의 주인공인 이유는 독립인 합에서 곱으로 갈라지기 때문입니다. X1,…,XnX_1, \dots, X_n 이 독립이면 eλ∑Xi=∏eλXie^{\lambda \sum X_i} = \prod e^{\lambda X_i} 의 기댓값이 기댓값의 곱이 되므로

ΛX1+⋯+Xn(λ)=∑i=1nΛXi(λ)\Lambda_{X_1 + \cdots + X_n}(\lambda) = \sum_{i=1}^{n} \Lambda_{X_i}(\lambda)

입니다. 분산이 독립 합에서 더해진다는 중급 21번의 가법성을, 누적생성함수는 모든 차수에서 한꺼번에 해냅니다.

체르노프 경계

두 번째 넣기는 지수함수입니다. 아무 λ>0\lambda > 0 에서 x↦eλxx \mapsto e^{\lambda x} 는 증가함수이므로 X≥tX \ge t 와 eλX≥eλte^{\lambda X} \ge e^{\lambda t} 는 같은 사건이고, 마르코프를 쓰면

P(X≥t)=P(eλX≥eλt)≤e−λtM(λ)=exp⁡(−(λt−Λ(λ)))P(X \ge t) = P(e^{\lambda X} \ge e^{\lambda t}) \le e^{-\lambda t} M(\lambda) = \exp\big(-(\lambda t - \Lambda(\lambda))\big)

입니다. 이 부등식은 모든 λ>0\lambda > 0 에서 성립하므로 가장 좋은 λ\lambda 를 고를 수 있습니다.

P(X≥t)≤exp⁡(−sup⁡λ>0(λt−Λ(λ)))P(X \ge t) \le \exp\Big(-\sup_{\lambda > 0} \big(\lambda t - \Lambda(\lambda)\big)\Big)

이렇게 지수 적률에 마르코프를 쓰고 λ\lambda 에 대해 최적화하는 절차를 체르노프 방법이라 부릅니다. 지수 안의 sup⁡λ(λt−Λ(λ))\sup_\lambda (\lambda t - \Lambda(\lambda)) 는 누적생성함수의 르장드르 변환이고 Λ∗(t)\Lambda^*(t) 로 적습니다.

독립 합에 쓰면 체르노프 방법의 힘이 드러납니다. XiX_i 가 독립이고 같은 분포이며 평균이 μ\mu 이면, 합의 누적생성함수가 nΛn\Lambda 이므로

P(Xˉ−μ≥ε)≤exp⁡(−nΛc∗(ε))P(\bar X - \mu \ge \varepsilon) \le \exp\big(-n \Lambda_c^*(\varepsilon)\big)

입니다. 여기서 Λc\Lambda_c 는 중심화한 X−μX - \mu 의 누적생성함수입니다. 표본 수 nn 이 지수 안으로 들어갔습니다. 실패 확률 δ\delta 를 맞추는 데 필요한 nn 이 log⁡(1/δ)/Λc∗(ε)\log(1/\delta)/\Lambda_c^*(\varepsilon) 이 되어, 체비쇼프의 1/δ1/\delta 가 log⁡(1/δ)\log(1/\delta) 로 바뀝니다. 지수 Λ∗\Lambda^* 는 더 줄일 수 없는 값이라는 것이 크라메르 정리이고, 그래서 체르노프 방법이 잃는 것은 지수 앞의 다항식 크기의 인수뿐입니다.

베르누이의 KL 꼴

정답 여부처럼 Xi∼Bernoulli(p)X_i \sim \mathrm{Bernoulli}(p) 인 경우를 끝까지 계산합니다. 합 SS 의 적률생성함수는 (1−p+peλ)n(1 - p + pe^\lambda)^n 이고, q>pq > p 에 대해 P(S≥nq)P(S \ge nq) 를 누르는 지수 −λnq+nlog⁡(1−p+peλ)-\lambda nq + n\log(1 - p + pe^\lambda) 를 λ\lambda 로 미분해 0으로 두면

eλ=q(1−p)p(1−q)e^{\lambda} = \frac{q(1 - p)}{p(1 - q)}

입니다. q>pq > p 라 이 값이 1보다 커서 λ>0\lambda > 0 이고, 넣으면 1−p+peλ=(1−p)/(1−q)1 - p + pe^\lambda = (1 - p)/(1 - q) 이므로 지수가

−n[qlog⁡qp+(1−q)log⁡1−q1−p]=−n KL(q ∥ p)-n\left[ q \log\frac{q}{p} + (1 - q)\log\frac{1 - q}{1 - p} \right] = -n\,\mathrm{KL}(q \,\Vert\, p)

로 정리됩니다. 베르누이 표본평균이 qq 이상으로 나올 확률은 e−nKL(q∥p)e^{-n \mathrm{KL}(q \Vert p)} 이하이고, 지수에 선 것이 두 베르누이 분포 사이의 KL 발산입니다. 관측된 비율과 참 비율이 정보량으로 얼마나 다른지가 꼬리의 속도를 정한다는 뜻입니다. 이 KL을 KL(q∥p)≥2(q−p)2\mathrm{KL}(q \Vert p) \ge 2(q - p)^2 로 누르면 지수가 −2n(q−p)2-2n(q - p)^2 이 되고, 이것이 4절의 회프딩 부등식과 같은 꼴입니다.

가로축 t 035, 세로축 로그 눈금 확률 110⁻¹⁰. 마르코프 선은 0.6 근처에서 거의 평평하고, 체비쇼프 선은 t⁻² 로 천천히 내려가 t = 35 에서 0.02 이다. 회프딩 꼴 e^(−2t²/100) 와 KL 꼴은 포물선처럼 꺾여 내려가 t = 30 근처에서 10⁻⁸ 아래로 가고, 실제 이항분포 꼬리의 점들이 그 바로 아래를 같은 기울기로 따라간다

동전 100번에서 앞면이 70번 이상 나올 확률로 넷을 나란히 놓으면 차이가 보입니다. 실제 값은 3.93×10−53.93 \times 10^{-5} 이고, 마르코프는 0.714, 체비쇼프는 0.0625, 회프딩 꼴은 e−8=3.35×10−4e^{-8} = 3.35 \times 10^{-4}, KL 꼴은 2.67×10−42.67 \times 10^{-4} 입니다. 앞의 둘은 그림에서 거의 눕고, 체르노프 방법의 두 꼴은 실제 꼬리와 같은 기울기로 내려갑니다. 남은 일곱 배쯤의 간격이 지수 앞의 다항식 인수이고, tt 가 커져도 로그 축에서 벌어지지 않습니다.

서브가우시안과 서브지수

서브가우시안

체르노프 방법이 모든 분포마다 르장드르 변환을 따로 계산하게 두면 일이 끝나지 않습니다. 그래서 누적생성함수를 간단한 함수로 위에서 누르고, 그 누름만 가지고 꼬리를 계산합니다. 가장 흔한 누름은 포물선입니다. 평균이 0인 XX 가 모든 실수 λ\lambda 에서

Λ(λ)=log⁡E[eλX]≤λ2σ22\Lambda(\lambda) = \log \mathbb{E}[e^{\lambda X}] \le \frac{\lambda^2 \sigma^2}{2}

를 만족하면 XX 를 서브가우시안이라 부르고, 이때의 σ2\sigma^2 를 분산 프록시라 부릅니다. 평균이 00, 분산이 σ2\sigma^2 인 정규분포의 누적생성함수가 정확히 λ2σ2/2\lambda^2 \sigma^2/2 이므로, 서브가우시안은 「적률생성함수가 분산 σ2\sigma^2 인 정규분포보다 크지 않다」는 말입니다. 원점에서 두 번 미분해 보면 분산은 분산 프록시를 넘을 수 없지만, 둘이 같을 필요는 없습니다.

정의에 체르노프 방법을 쓰면 sup⁡λ(λt−λ2σ2/2)=t2/(2σ2)\sup_\lambda (\lambda t - \lambda^2 \sigma^2 / 2) = t^2/(2\sigma^2) 이므로 P(X≥t)≤e−t2/(2σ2)P(X \ge t) \le e^{-t^2/(2\sigma^2)} 입니다. 독립인 서브가우시안을 더하면 누적생성함수가 더해지니 분산 프록시도 더해지고, 평균 Xˉ\bar X 는 분산 프록시 σ2/n\sigma^2/n 인 서브가우시안이 됩니다. 꼬리 계산이 분산 프록시 하나의 산수로 줄어든 셈입니다.

같은 성질을 다르게 적은 정의가 셋 더 있고, 넷은 서로를 절대 상수배 안에서 함의합니다. 상수 K1,…,K4K_1, \dots, K_4 는 서로 상수배 차이입니다.

  1. 꼬리: 모든 tt 에서 P(∣X∣≥t)≤2exp⁡(−t2/K12)P(\lvert X \rvert \ge t) \le 2\exp(-t^2/K_1^2)
  2. 적률: 모든 q≥1q \ge 1 에서 (E∣X∣q)1/q≤K2q(\mathbb{E}\lvert X \rvert^q)^{1/q} \le K_2 \sqrt{q}
  3. 제곱의 지수 적률: Eexp⁡(X2/K32)≤2\mathbb{E}\exp(X^2/K_3^2) \le 2
  4. 적률생성함수(평균 0일 때): EeλX≤exp⁡(K42λ2)\mathbb{E}e^{\lambda X} \le \exp(K_4^2 \lambda^2)

적률이 q\sqrt{q} 보다 빨리 자라지 않는다는 2번이 qq 가 클 때 q/e\sqrt{q/e} 로 자라는 정규분포의 적률을 흉내 낸 것이고, 1번과 4번 사이를 오가는 것이 체르노프 방법과 그 거꾸로입니다.

오를리츠 노름

3번 정의는 「얼마나 서브가우시안인가」를 숫자 하나로 만듭니다.

∥X∥ψ2=inf⁡{s>0:Eexp⁡(X2/s2)≤2}\lVert X \rVert_{\psi_2} = \inf\{ s > 0 : \mathbb{E}\exp(X^2/s^2) \le 2 \}

를 오를리츠 노름이라 부르고, 아래 첨자 ψ2\psi_2 는 이 정의가 볼록함수 ψ2(x)=ex2−1\psi_2(x) = e^{x^2} - 1 로 만든 것임을 가리킵니다. 확률변수를 볼록함수에 넣은 기댓값으로 크기를 재는 것은 LpL^p 노름이 xpx^p 로 하는 일과 같고, 볼록성 덕분에 삼각부등식이 서서 진짜 노름이 됩니다. 서브가우시안은 이 노름이 유한한 확률변수이고, 노름이 작을수록 꼬리가 가볍습니다.

몇 개를 직접 계산해 봅니다. 라데마허 변수 ±1\pm 1 은 X2=1X^2 = 1 이라 e1/s2≤2e^{1/s^2} \le 2 에서 s=1/log⁡2=1.201s = 1/\sqrt{\log 2} = 1.201 입니다. 표준정규 ZZ 는 EeZ2/s2=(1−2/s2)−1/2\mathbb{E}e^{Z^2/s^2} = (1 - 2/s^2)^{-1/2} 를 2 이하로 두면 s2≥8/3s^2 \ge 8/3, 곧 ∥Z∥ψ2=1.633\lVert Z \rVert_{\psi_2} = 1.633 입니다. 분산이 둘 다 1인데 노름이 다른 것은 정규분포의 꼬리가 라데마허보다 무겁기 때문입니다. 라데마허는 1을 넘는 값이 아예 없습니다.

같은 틀에서 ψ1(x)=ex−1\psi_1(x) = e^{x} - 1 로 바꾸면 ∥X∥ψ1=inf⁡{s:Eexp⁡(∣X∣/s)≤2}\lVert X \rVert_{\psi_1} = \inf\{ s : \mathbb{E}\exp(\lvert X \rvert / s) \le 2 \} 가 됩니다. 평균 1인 지수분포는 EeX/s=1/(1−1/s)\mathbb{E}e^{X/s} = 1/(1 - 1/s) 라 ∥X∥ψ1=2\lVert X \rVert_{\psi_1} = 2 이고, Z2Z^2 은 (1−2/s)−1/2≤2(1 - 2/s)^{-1/2} \le 2 에서 8/38/3 입니다. 마지막 값이 ∥Z∥ψ22\lVert Z \rVert_{\psi_2}^2 과 같은 것은 우연이 아닙니다. 정의를 풀면 언제나 ∥X2∥ψ1=∥X∥ψ22\lVert X^2 \rVert_{\psi_1} = \lVert X \rVert_{\psi_2}^2 이고, 더 일반적으로 ∥XY∥ψ1≤∥X∥ψ2∥Y∥ψ2\lVert XY \rVert_{\psi_1} \le \lVert X \rVert_{\psi_2} \lVert Y \rVert_{\psi_2} 입니다. 서브가우시안 둘을 곱하면 다음 소절의 서브지수가 됩니다.

서브지수

모든 꼬리가 포물선 아래에 들어가지는 않습니다. Z2−1Z^2 - 1 의 적률생성함수는 e−λ(1−2λ)−1/2e^{-\lambda}(1 - 2\lambda)^{-1/2} 이라 λ≥1/2\lambda \ge 1/2 에서 무한대가 됩니다. 어떤 포물선도 이것을 모든 λ\lambda 에서 누를 수 없습니다. 대신 원점 근처에서는 누를 수 있습니다. 평균이 0인 XX 가

Λ(λ)≤λ2ν22for all ∣λ∣<1/b\Lambda(\lambda) \le \frac{\lambda^2 \nu^2}{2} \qquad \text{for all } \lvert \lambda \rvert < 1/b

를 만족하면 매개변수 (ν,b)(\nu, b) 의 서브지수라 부릅니다. Z2−1Z^2 - 1 은 ∣λ∣≤1/4\lvert \lambda \rvert \le 1/4 에서 e−λ(1−2λ)−1/2≤e2λ2e^{-\lambda}(1 - 2\lambda)^{-1/2} \le e^{2\lambda^2} 이 성립해 (ν,b)=(2,4)(\nu, b) = (2, 4) 인 서브지수입니다.

체르노프 방법을 쓰면 λ\lambda 를 1/b1/b 아래에서만 고를 수 있어 꼬리가 두 국면으로 갈립니다.

P(X≥t)≤{exp⁡ ⁣(−t22ν2)0≤t≤ν2/bexp⁡ ⁣(−t2b)t>ν2/bP(X \ge t) \le \begin{cases} \exp\!\left(-\dfrac{t^2}{2\nu^2}\right) & 0 \le t \le \nu^2/b \\ \exp\!\left(-\dfrac{t}{2b}\right) & t > \nu^2/b \end{cases}

작게 벗어날 때는 정규분포처럼, 크게 벗어날 때는 지수분포처럼 줄어듭니다. 최적의 λ=t/ν2\lambda = t/\nu^2 가 허용 범위 1/b1/b 를 넘는 순간 경계에 멈춰야 해서 생기는 꺾임입니다. 존슨–린덴스트라우스 보조정리의 원래 증명이 다루는 사영된 길이의 제곱 ∥Rx∥2\lVert Rx \rVert^2 이 바로 서브지수입니다. 중급 66번 랜덤 사영과 존슨–린덴스트라우스 보조정리의 지수에 ε2−ε3\varepsilon^2 - \varepsilon^3 처럼 ε\varepsilon 의 높은 차수가 섞여 들어온 것이 이 두 국면의 흔적입니다.

네 겹으로 겹친 상자. 가장 바깥이 「분산이 유한」으로 꼬리 t⁻², 체비쇼프만 쓸 수 있고 예는 자유도 3 인 t분포이다. 그 안이 「서브지수」로 ψ₁ 노름과 꼬리 e^(−t/K), 예는 지수분포·χ²·서브가우시안의 곱이고 베른슈타인이 붙는다. 그 안이 「서브가우시안」으로 ψ₂ 노름과 꼬리 e^(−t²/K²), 예는 정규분포와 유계 변수의 평균이다. 가장 안쪽이 「유계」로 분산 프록시 (b−a)²/4, 예는 정답 여부 0/1 과 라데마허이다

그림의 위계가 이 글의 지도입니다. 바깥으로 갈수록 가정이 약해지고 꼬리가 무거워지며 쓸 수 있는 부등식이 줄어듭니다. 정답 여부, 보상 점수, 잘라 낸 손실처럼 평가에서 다루는 값은 대부분 가장 안쪽의 유계 변수라 모든 도구를 다 쓸 수 있습니다. 그런데 4절에서 보듯, 안쪽에 있다고 해서 가장 안쪽의 도구가 가장 좋은 것은 아닙니다.

최댓값의 기대 상계

서브가우시안 정의가 바로 값을 내는 자리가 하나 있습니다. 평균이 0이고 분산 프록시가 σ2\sigma^2 인 서브가우시안 X1,…,XKX_1, \dots, X_K 에 대해, 서로 독립이든 아니든

E[max⁡k≤KXk]≤2σ2log⁡K\mathbb{E}\Big[\max_{k \le K} X_k\Big] \le \sqrt{2 \sigma^2 \log K}

입니다. 증명은 세 걸음입니다. 아무 λ>0\lambda > 0 에서 젠센 부등식으로 eλE[max⁡Xk]≤E[eλmax⁡Xk]e^{\lambda \mathbb{E}[\max X_k]} \le \mathbb{E}[e^{\lambda \max X_k}] 이고, 최댓값의 지수는 지수들의 최댓값이니 합으로 누르면 E[max⁡keλXk]≤∑kE[eλXk]≤Keλ2σ2/2\mathbb{E}[\max_k e^{\lambda X_k}] \le \sum_k \mathbb{E}[e^{\lambda X_k}] \le K e^{\lambda^2 \sigma^2 / 2} 입니다. 로그를 잡고 λ\lambda 로 나누면 E[max⁡Xk]≤log⁡K/λ+λσ2/2\mathbb{E}[\max X_k] \le \log K / \lambda + \lambda \sigma^2 / 2 이고, 오른쪽을 최소로 하는 λ=2log⁡K/σ\lambda = \sqrt{2 \log K}/\sigma 를 넣으면 끝입니다.

합으로 누른 둘째 걸음에서 독립을 쓰지 않았다는 점이 중요합니다. 같은 문항으로 채점해 서로 강하게 얽힌 점수 스무 개에도 이 상계가 그대로 섭니다. 대가는 KK 가 로그로만 들어온다는 것입니다. 독립인 표준정규 스무 개의 최댓값은 평균이 1.867이고 상계는 2log⁡20=2.448\sqrt{2 \log 20} = 2.448 이라, 독립일 때도 상계가 크게 헐겁지 않습니다. KK 가 커지면 둘의 비는 1로 갑니다. 셋째 질문의 절반이 이 부등식으로 풀립니다.

회프딩과 베른슈타인

회프딩 보조정리

유계 변수가 서브가우시안이라는 것, 그리고 그 분산 프록시가 얼마인지를 정하는 것이 이 절의 첫 일입니다. X∈[a,b]X \in [a, b] 이고 평균이 μ\mu 이면 모든 실수 λ\lambda 에서

Λ(λ)=log⁡E[eλ(X−μ)]≤λ2(b−a)28\Lambda(\lambda) = \log \mathbb{E}\big[e^{\lambda (X - \mu)}\big] \le \frac{\lambda^2 (b - a)^2}{8}

입니다. 이것을 회프딩 보조정리라 부르고, 분산 프록시가 (b−a)2/4(b - a)^2/4 라는 말입니다.

증명은 누적생성함수를 두 번 미분하는 것으로 끝납니다. 평균을 빼도 범위의 폭은 그대로이므로 μ=0\mu = 0 이라 둡니다. λ\lambda 를 하나 고정하고, 원래 분포의 밀도에 eλx/M(λ)e^{\lambda x}/M(\lambda) 를 곱한 새 분포를 만듭니다. 큰 값 쪽으로 무게를 옮긴 이 분포를 기울인 분포라 부르고, 그 기댓값을 Eλ\mathbb{E}_\lambda 로 적습니다. 직접 미분하면

Λ′(λ)=E[XeλX]E[eλX]=Eλ[X],Λ′′(λ)=Eλ[X2]−(Eλ[X])2\Lambda'(\lambda) = \frac{\mathbb{E}[X e^{\lambda X}]}{\mathbb{E}[e^{\lambda X}]} = \mathbb{E}_\lambda[X], \qquad \Lambda''(\lambda) = \mathbb{E}_\lambda[X^2] - \big(\mathbb{E}_\lambda[X]\big)^2

입니다. 누적생성함수의 2계 도함수는 기울인 분포에서 잰 분산입니다. 기울여도 XX 의 값은 여전히 [a,b][a, b] 안에 있고, [a,b][a, b] 안의 확률변수는 어떤 분포든 분산이 (b−a)2/4(b - a)^2/4 이하입니다. 분산은 평균 대신 아무 상수 mm 을 빼서 잰 제곱 평균보다 작거나 같은데, m=(a+b)/2m = (a + b)/2 로 두면 ∣X−m∣≤(b−a)/2\lvert X - m \rvert \le (b - a)/2 이기 때문입니다. 그래서 모든 λ\lambda 에서 Λ′′(λ)≤(b−a)2/4\Lambda''(\lambda) \le (b - a)^2/4 이고, Λ(0)=0\Lambda(0) = 0, Λ′(0)=0\Lambda'(0) = 0 에서 시작하는 테일러 전개의 라그랑주 나머지로

Λ(λ)=λ22Λ′′(ξ)≤λ2(b−a)28\Lambda(\lambda) = \frac{\lambda^2}{2} \Lambda''(\xi) \le \frac{\lambda^2 (b - a)^2}{8}

이 나옵니다. ξ\xi 는 0과 λ\lambda 사이의 어떤 점입니다.

가로축 λ 가 −2 에서 2, 세로축 0~0.55. 보라 점선 포물선 λ²/8 바로 아래를 p = 0.5 의 파란 실선 Λ(λ) 가 거의 붙어 따라가고, p = 0.05 의 초록 실선은 원점 근처에서 훨씬 납작하고 λ = 2 에서도 0.18 이다. 붉은 점선인 p = 0.05 의 베른슈타인 상계는 초록 선을 원점 근처에서 바싹 따라가다가 |λ| 가 커지면 위로 휘어 오른다

그림은 중심화한 베르누이의 누적생성함수입니다. p=0.5p = 0.5 이면 분산이 1/41/4 로 범위가 허락하는 최댓값이라 포물선 λ2/8\lambda^2/8 에 거의 붙습니다. p=0.05p = 0.05 이면 원점의 곡률, 곧 분산이 0.04750.0475 라 곡선이 훨씬 납작합니다. 회프딩 보조정리는 두 경우를 똑같이 λ2/8\lambda^2/8 로 셉니다. 범위만 보고 분산을 보지 않기 때문입니다. 이 낭비가 첫머리의 백 배 차이의 정체이고, 붉은 점선이 아래에서 그것을 메웁니다.

회프딩 부등식

보조정리를 체르노프 방법에 넣으면 됩니다. Xi∈[ai,bi]X_i \in [a_i, b_i] 가 독립이고 S=∑i(Xi−EXi)S = \sum_i (X_i - \mathbb{E}X_i), D=∑i(bi−ai)2D = \sum_i (b_i - a_i)^2 이라 하면, 누적생성함수가 더해지므로 모든 λ>0\lambda > 0 에서

P(S≥t)≤exp⁡ ⁣(−λt+λ2D8)P(S \ge t) \le \exp\!\left(-\lambda t + \frac{\lambda^2 D}{8}\right)

이고, 지수를 최소로 하는 λ=4t/D\lambda = 4t/D 를 넣으면 −4t2/D+2t2/D-4t^2/D + 2t^2/D 가 남아

P(S≥t)≤exp⁡ ⁣(−2t2∑i(bi−ai)2)P(S \ge t) \le \exp\!\left(-\frac{2t^2}{\sum_i (b_i - a_i)^2}\right)

를 얻습니다. 이것이 회프딩 부등식입니다. 아래 꼬리도 같고, 양쪽을 합치면 오른쪽에 2가 붙습니다. [0,1][0, 1] 에 있는 값 nn 개의 평균으로 쓰면

P(∣Xˉ−μ∣≥ε)≤2e−2nε2,n≥log⁡(2/δ)2ε2P(\lvert \bar X - \mu \rvert \ge \varepsilon) \le 2e^{-2n\varepsilon^2}, \qquad n \ge \frac{\log(2/\delta)}{2\varepsilon^2}

입니다. 첫째 질문에 대면 log⁡40/(2×0.0004)=4,611\log 40 / (2 \times 0.0004) = 4{,}611 문항입니다. 분포 가정 없이, 어떤 정답률에서도 성립하는 보장입니다. 체비쇼프의 12,500보다 세 배 가까이 작고, 정규 근사의 2,401보다 두 배 큽니다.

고급 5번 조건부 기댓값은 사영이다, 그리고 마팅게일의 아주마–회프딩 부등식은 증분이 ∣Dk∣≤ck\lvert D_k \rvert \le c_k 일 때 exp⁡(−t2/(2∑ck2))\exp(-t^2 / (2\sum c_k^2)) 를 주었습니다. 증분이 [−c,c][-c, c] 처럼 0을 가운데 둔 구간에 있으면 폭이 2c2c 라 두 식이 정확히 같습니다. [0,1][0, 1] 값에서 모르는 평균을 뺀 것처럼 구간이 어디에 놓일지 모르면, 절댓값으로 묶을 때 c=1c = 1 을 써야 해서 지수가 t2/(2n)t^2/(2n) 이 되고, 폭으로 묶는 회프딩은 2t2/n2t^2/n 이라 네 배 날카롭습니다. 그 글이 미뤄 둔 「(b−a)2/8(b - a)^2/8 판」이 이것입니다.

베른슈타인 부등식

분산을 쓰려면 누적생성함수를 원점의 곡률로 누르면 됩니다. Y=X−μY = X - \mu 가 ∣Y∣≤b\lvert Y \rvert \le b 이고 분산이 σ2\sigma^2 이면 q≥2q \ge 2 에서 E∣Y∣q≤σ2bq−2\mathbb{E}\lvert Y \rvert^q \le \sigma^2 b^{q-2} 이고, q!≥2⋅3q−2q! \ge 2 \cdot 3^{q-2} 입니다. 평균이 0이라 1차 항이 사라지므로 급수를 항별로 누르면

E[eλY]≤1+λ2σ22∑q≥2(∣λ∣b3)q−2=1+λ2σ2/21−∣λ∣b/3\mathbb{E}[e^{\lambda Y}] \le 1 + \frac{\lambda^2 \sigma^2}{2} \sum_{q \ge 2} \left(\frac{\lvert \lambda \rvert b}{3}\right)^{q-2} = 1 + \frac{\lambda^2 \sigma^2 / 2}{1 - \lvert \lambda \rvert b/3}

입니다. 1+x≤ex1 + x \le e^x 로 지수에 올리면 ∣λ∣<3/b\lvert \lambda \rvert < 3/b 에서 Λ(λ)≤λ2σ2/21−∣λ∣b/3\Lambda(\lambda) \le \frac{\lambda^2 \sigma^2/2}{1 - \lvert \lambda \rvert b/3} 입니다. 분모가 1에 가까운 원점 근처에서는 곡률이 분산 σ2\sigma^2 그대로이고, λ\lambda 가 커지면 위로 휩니다. 앞 그림의 붉은 점선이 이것입니다. 유계 변수가 분산 프록시 ν2≈σ2\nu^2 \approx \sigma^2 인 서브지수라는 말이기도 합니다.

나머지는 앞과 같은 산수입니다. nn 개를 더하면 분산이 V=nσ2V = n\sigma^2 로 더해지고, λ=t/(V+bt/3)\lambda = t/(V + bt/3) 를 넣으면 1−λb/3=V/(V+bt/3)1 - \lambda b/3 = V/(V + bt/3) 라 지수가 깔끔하게 정리됩니다.

P(S≥t)≤exp⁡ ⁣(−t22(V+bt/3)),P(Xˉ−μ≥ε)≤exp⁡ ⁣(−nε22σ2+2bε/3)P(S \ge t) \le \exp\!\left(-\frac{t^2}{2(V + bt/3)}\right), \qquad P(\bar X - \mu \ge \varepsilon) \le \exp\!\left(-\frac{n\varepsilon^2}{2\sigma^2 + 2b\varepsilon/3}\right)

이것이 베른슈타인 부등식입니다. 고급 6번 스케치와 행렬 집중부등식이 행렬로 올려 쓴 그 부등식의 스칼라 판이고, 거기서 「증명은 고급 8번에서」라고 미뤄 둔 계산이 위의 다섯 줄입니다. 분모의 두 항이 서브지수의 두 국면입니다. 벗어나는 크기 ε\varepsilon 가 3σ2/b3\sigma^2/b 보다 작으면 2σ22\sigma^2 이 이겨 정규분포처럼, 크면 2bε/32b\varepsilon/3 이 이겨 지수분포처럼 줄어듭니다. 양쪽 꼬리를 합친 필요 표본 수는

n≥(2σ2+2bε/3)log⁡(2/δ)ε2n \ge \frac{(2\sigma^2 + 2b\varepsilon/3)\log(2/\delta)}{\varepsilon^2}

입니다.

분산의 값

둘째 질문에 넣어 봅니다. 유해 응답 비율 p=0.005p = 0.005, 오차 ε=0.005\varepsilon = 0.005, δ=0.05\delta = 0.05 입니다. 분산은 σ2=0.004975\sigma^2 = 0.004975 이고 b=1b = 1 이므로 분모가 0.00995+0.00333=0.013280.00995 + 0.00333 = 0.01328, 필요 표본 수는 0.01328×3.689/0.000025=1,9610.01328 \times 3.689 / 0.000025 = 1{,}961 입니다. 같은 ε\varepsilon 와 δ\delta 에서 회프딩은 log⁡40/(2×0.000025)=73,778\log 40 / (2 \times 0.000025) = 73{,}778 이라 37.6배 차이가 납니다. 분산만 쓰는 체비쇼프도 0.004975/(0.05×0.000025)=3,9800.004975/(0.05 \times 0.000025) = 3{,}980 으로 회프딩보다 열여덟 배 낫습니다. 꼬리를 다룰 줄 아는 회프딩이 다항 꼬리밖에 못 다루는 체비쇼프에게 지는 것은 회프딩이 분산을 1/41/4 로 셈해 버리기 때문입니다.

서브가우시안의 틀 안에서는 이것을 고칠 수 없습니다. 베르누이(0.005)(0.005) 에서 정의를 만족하는 가장 작은 분산 프록시는 sup⁡λ2Λ(λ)/λ2\sup_\lambda 2\Lambda(\lambda)/\lambda^2 를 계산하면 (1−2p)/(2log⁡((1−p)/p))=0.0935(1 - 2p)/(2\log((1 - p)/p)) = 0.0935 로, 실제 분산의 19배입니다. 원점 근처의 곡률은 작지만 λ\lambda 가 크면 드문 1이 무게를 얻어 누적생성함수가 포물선을 밀어 올리기 때문입니다. 분산을 살리려면 원점 근처에서만 포물선으로 누르는 서브지수의 틀, 곧 베른슈타인이 필요합니다. 비율이 1/2에 가까우면 분산이 범위의 최댓값과 같아 둘이 비슷하고(p=0.5p = 0.5 에서 베른슈타인 4,734, 회프딩 4,611), 드문 사건을 셀수록 베른슈타인이 이깁니다. 안전성 평가, 오류율, 거부율처럼 0에 붙은 비율을 재는 일은 거의 언제나 이 쪽입니다.

맥디아미드와 합집합 경계

유계 차분 조건

지금까지는 평균만 다뤘습니다. 평가에서 쓰는 값 가운데는 평균이 아닌 것이 많습니다. 스무 개 체크포인트의 최고 점수가 그렇고, 양성 n+n_+ 개와 음성 n−n_- 개를 쌍으로 비교해 올바르게 순위를 매긴 쌍의 비율을 세는 AUROC도 그렇습니다. 이런 값을 독립인 표본 X1,…,XnX_1, \dots, X_n 의 함수 ff 로 보고, 한 표본만 바꿨을 때 값이 얼마나 움직일 수 있는지를 봅니다. 모든 ii 와 모든 x1,…,xn,xi′x_1, \dots, x_n, x_i' 에서

∣f(x1,…,xi,…,xn)−f(x1,…,xi′,…,xn)∣≤ci\lvert f(x_1, \dots, x_i, \dots, x_n) - f(x_1, \dots, x_i', \dots, x_n) \rvert \le c_i

가 성립하면 ff 가 유계 차분 조건을 만족한다고 말합니다. 표본 하나가 결과를 쥐고 흔들 수 없다는 조건입니다.

예를 셋 봅니다. [0,1][0, 1] 값의 평균은 ci=1/nc_i = 1/n 입니다. 같은 문항 nn 개로 채점한 체크포인트 KK 개의 최고 점수도 문항 하나를 바꾸면 각 점수가 1/n1/n 이하로 움직이고, 최댓값은 각 값이 움직인 폭보다 더 움직이지 않으므로 ci=1/nc_i = 1/n 입니다. 체크포인트끼리는 같은 문항을 공유해 서로 얽혀 있지만 그것은 아무 문제가 되지 않습니다. 독립이어야 하는 것은 문항이지 체크포인트가 아닙니다. AUROC는 양성 하나가 음성 n−n_- 개와의 쌍에만 관여하므로 ci=n−/(n+n−)=1/n+c_i = n_-/(n_+ n_-) = 1/n_+, 음성 하나는 1/n−1/n_- 입니다.

맥디아미드 부등식

유계 차분 조건이 서면

P(f(X)−Ef(X)≥t)≤exp⁡ ⁣(−2t2∑ici2)P\big(f(X) - \mathbb{E}f(X) \ge t\big) \le \exp\!\left(-\frac{2t^2}{\sum_i c_i^2}\right)

입니다. 이것이 맥디아미드 부등식이고, 평균이라는 특정한 함수에 대한 회프딩 부등식을 유계 차분인 모든 함수로 넓힌 것입니다.

증명의 줄기는 고급 5번의 마팅게일입니다. 표본을 하나씩 드러내며 조건부 기댓값을 잡은 Zk=E[f(X)∣X1,…,Xk]Z_k = \mathbb{E}[f(X) \mid X_1, \dots, X_k] 를 둡 마팅게일이라 부르고, Z0=Ef(X)Z_0 = \mathbb{E}f(X) 에서 출발해 Zn=f(X)Z_n = f(X) 에 닿습니다. 구하려는 편차 f−Eff - \mathbb{E}f 가 증분 Dk=Zk−Zk−1D_k = Z_k - Z_{k-1} 의 합으로 쪼개진 셈입니다. 표본이 독립이므로 앞의 k−1k - 1 개를 고정했을 때 ZkZ_k 는 xkx_k 만의 함수 gk(xk)=E[f(x1,…,xk,Xk+1,…,Xn)]g_k(x_k) = \mathbb{E}[f(x_1, \dots, x_k, X_{k+1}, \dots, X_n)] 이고, 기댓값 안에서 kk 번째 자리만 바뀌므로 gkg_k 가 움직이는 폭은 ckc_k 이하입니다. 곧 DkD_k 는 과거가 정하는 폭 ckc_k 짜리 구간 안에 있고 조건부 평균이 0입니다. 회프딩 보조정리를 조건부로 쓰면 E[eλDk∣X1,…,Xk−1]≤eλ2ck2/8\mathbb{E}[e^{\lambda D_k} \mid X_1, \dots, X_{k-1}] \le e^{\lambda^2 c_k^2/8} 이고, 고급 5번의 아주마–회프딩 증명처럼 걸음마다 꺼내 곱하면 E[eλ(f−Ef)]≤eλ2∑ck2/8\mathbb{E}[e^{\lambda(f - \mathbb{E}f)}] \le e^{\lambda^2 \sum c_k^2/8} 이 남습니다. 마지막은 회프딩 부등식과 똑같은 최적화입니다.

셋째 질문의 나머지 절반에 대 봅니다. 최고 점수는 ci=1/2000c_i = 1/2000 이라 ∑ci2=1/2000\sum c_i^2 = 1/2000 이고, 양쪽 꼬리 δ=0.05\delta = 0.05 에서 t=log⁡40/(2×2000)=0.0304t = \sqrt{\log 40 / (2 \times 2000)} = 0.0304 입니다. 문항 2,000개를 새로 뽑아 다시 채점해도 최고 점수는 그 기댓값에서 3.04%p 넘게 벗어날 확률이 5% 이하라는 보장입니다. 스무 개 점수가 모두 참값 70%인 경우를 이십만 번 흉내 내면 최고 점수의 표준편차는 0.53%p이고, 3.04%p를 넘게 벗어난 비율은 1.5×10−51.5 \times 10^{-5} 입니다. 맥디아미드는 최댓값이 점수 하나보다도 좁게 모인다는 사실까지는 쓰지 못해 넉넉하지만, 체크포인트 사이의 얽힘을 하나도 몰라도 된다는 것이 값입니다. AUROC에서는 n+=n−=1,000n_+ = n_- = 1{,}000 이면 ∑ci2=0.002\sum c_i^2 = 0.002 라 같은 δ\delta 에서 t=0.0607t = 0.0607 입니다.

합집합 경계

체크포인트 스무 개의 점수가 모두 참값 근처에 있을 확률은 어떻게 셀까요. 사건 A1,…,AKA_1, \dots, A_K 에 대해

P(⋃k=1KAk)≤∑k=1KP(Ak)P\Big(\bigcup_{k=1}^{K} A_k\Big) \le \sum_{k=1}^{K} P(A_k)

를 합집합 경계라 부릅니다. 겹치는 부분을 여러 번 세는 것을 허락하고 합으로 누르는 것이라, 사건들이 서로 어떻게 얽혀 있는지 몰라도 됩니다. AkA_k 를 「kk 번째 체크포인트의 점수가 참값에서 ε\varepsilon 이상 벗어난다」로 두고 각각에 회프딩을 쓰면

P(max⁡k≤K∣p^k−pk∣≥ε)≤2Ke−2nε2,n≥log⁡(2K/δ)2ε2P\Big(\max_{k \le K} \lvert \hat p_k - p_k \rvert \ge \varepsilon\Big) \le 2K e^{-2n\varepsilon^2}, \qquad n \ge \frac{\log(2K/\delta)}{2\varepsilon^2}

입니다. δ\delta 를 KK 개로 나눠 쓰는 대가가 로그 하나로 들어온다는 것이 체르노프 방법의 지수 꼬리 덕분입니다. ε=0.02\varepsilon = 0.02, δ=0.05\delta = 0.05 이면 K=1K = 1 에서 4,611문항, K=20K = 20 에서 8,356문항, K=1,000K = 1{,}000 에서 13,246문항입니다. 거꾸로 문항을 2,000개로 고정하면 스무 개 전부를 동시에 보장하는 폭은 log⁡800/4000=4.09\sqrt{\log 800 / 4000} = 4.09%p이고, 천 개면 5.15%p입니다. 체비쇼프로 같은 일을 하면 KK 가 δ\delta 의 자리에 곱해져 표본이 KK 배로 늘어납니다.

존슨–린덴스트라우스 보조정리의 마지막 걸음이 이것입니다. 점 쌍 n2/2n^2/2 개마다 서브지수 꼬리를 쓰고 합집합 경계로 묶으면 필요한 차원이 log⁡n\log n 에 비례하게 됩니다. 쌍의 수가 지수 꼬리와 만나 로그로 바뀐 것입니다.

최고 점수의 치우침

이제 72.1%를 읽을 수 있습니다. 문항 2,000개에서 정답률의 편차 p^k−pk\hat p_k - p_k 는 회프딩 보조정리로 분산 프록시 1/(4n)1/(4n) 인 서브가우시안이고, 최댓값의 기대 상계가 독립을 요구하지 않으므로

E[max⁡k≤20(p^k−pk)]≤2log⁡204n=log⁡204000=0.0274\mathbb{E}\Big[\max_{k \le 20} (\hat p_k - p_k)\Big] \le \sqrt{\frac{2 \log 20}{4n}} = \sqrt{\frac{\log 20}{4000}} = 0.0274

입니다. 골라 낸 체크포인트 k∗k^* 의 p^k∗−pk∗\hat p_{k^*} - p_{k^*} 는 이 최댓값을 넘을 수 없으므로, 최고 점수는 평균적으로 그 체크포인트의 참값보다 2.74%p까지 부풀어 있을 수 있습니다. 여러 후보 가운데 측정값이 가장 좋은 것을 고르면 고른 행위 자체가 측정값을 위로 끌어올린다는 이 현상을 승자의 저주라 부릅니다.

가로축 정답률 67~76%. 보라 히스토그램은 체크포인트 하나의 점수로 70 을 가운데 둔 종 모양이고, 파란 히스토그램은 20 개 가운데 최고 점수로 71 에서 74 사이에 좁게 몰려 있다. 흰 점선이 참값 70.0, 초록 점선이 최고 점수의 평균 71.9, 붉은 점선이 상계 72.7 에 서 있다

그림은 스무 개가 모두 참값 70%인, 곧 아무것도 나아지지 않은 경우를 이십만 번 흉내 낸 것입니다. 최고 점수의 평균은 71.9%로 참값보다 1.91%p 높고, 상계 72.7%가 그 위에 섭니다. 팀이 고른 72.1%는 이 분포의 한가운데에 있습니다. 「70%보다 2%p 낫다」는 문장은 스무 개를 채점하고 최고를 골랐다는 사실만으로 설명되고, 실제로 나아졌다는 증거가 되지 못합니다. 처방은 고른 체크포인트를 고르는 데 쓰지 않은 새 문항으로 다시 채점하는 것입니다. 그 채점은 후보가 하나라 K=1K = 1 의 보장이 다시 섭니다.

후보가 스무 개가 아니라 연속적인 하이퍼파라미터나 신경망 가중치 전체라면 KK 가 무한해 합집합 경계가 그대로는 쓸모없어집니다. 무한한 후보를 유한한 대표로 덮어 log⁡K\log K 자리에 복잡도를 놓는 것이 다음 글의 일입니다.

필요 표본 수

네 공식

지금까지의 결과를 양쪽 꼬리, 같은 ε\varepsilon 와 δ\delta 로 나란히 적습니다.

방법 필요 표본 수 nn 쓰는 정보
정규 근사 zδ/22 σ2/ε2z_{\delta/2}^2\, \sigma^2 / \varepsilon^2 분산, 그리고 nn 이 충분히 크다는 가정
체비쇼프 σ2/(δε2)\sigma^2 / (\delta \varepsilon^2) 분산
회프딩 log⁡(2/δ)/(2ε2)\log(2/\delta) / (2\varepsilon^2) 범위
베른슈타인 (2σ2+2ε/3)log⁡(2/δ)/ε2(2\sigma^2 + 2\varepsilon/3)\log(2/\delta)/\varepsilon^2 범위와 분산

정규 근사의 zδ/2z_{\delta/2} 는 표준정규분포의 위쪽 δ/2\delta/2 분위수로, δ=0.05\delta = 0.05 에서 1.96입니다. 아래 셋은 표본 수가 얼마든 성립하는 보장이고, 정규 근사만 n→∞n \to \infty 의 극한에서 온 어림입니다. 첫머리 두 질문에 넣으면 이렇습니다. 「정확」은 이항분포의 확률을 직접 더해, 그 nn 부터는 실패 확률이 계속 δ\delta 이하로 머무는 가장 작은 nn 입니다.

정규 근사 체비쇼프 회프딩 베른슈타인 정확
정답률 ±2%p, pp 모름 2,401 12,500 4,611 4,734 2,424
유해 응답 ±0.5%p, p=0.005p = 0.005 765 3,980 73,778 1,961 800

첫 줄은 pp 를 모르므로 분산을 최댓값 1/41/4 로 두었습니다. 이 줄에서는 회프딩과 베른슈타인이 거의 같고 정확값의 두 배 안쪽입니다. 둘째 줄에서 두 사람의 계산이 갈린 이유가 보입니다. 765는 정규 근사이고 73,778은 분산을 버린 회프딩입니다. 보장으로 말할 수 있는 가장 작은 수는 베른슈타인의 1,961이고, 실제로 필요한 것은 800입니다.

가로축 참 비율 p 0.1%50% 로그 눈금, 세로축 필요한 문항 수 100300,000 로그 눈금. 회프딩은 73,778 에서 수평선이고, 체비쇼프는 800 에서 200,000 까지 비스듬히 오르며, 베른슈타인은 787 에서 74,269 까지 그 아래로 오른다. 흰 점선 정규 근사와 초록 점 정확값은 거의 겹쳐 오르지만 왼쪽 끝 0.1~0.2% 에서는 점이 점선 위로 떨어져 있다. p = 0.5% 에 세로 점선이 있다

그림이 ε=0.005\varepsilon = 0.005, δ=0.05\delta = 0.05 에서 pp 를 0.1%부터 50%까지 바꾼 것입니다. 회프딩은 pp 를 보지 않으니 수평선이고, 분산을 쓰는 셋은 pp 가 작아질수록 내려갑니다. 베른슈타인은 그림 전체에서 정확값의 1.9~4.7배 안에 머뭅니다. 보장을 원하면서 비율이 작은 일을 재면 베른슈타인을 쓰라는 결론이 이 그림입니다.

정규 근사의 붕괴

그림에서 정규 근사는 정확값에 놀랍도록 가깝습니다. 그래도 그것을 보장으로 쓰면 안 되는 자리가 셋 있습니다.

첫째, 기대 개수가 작을 때입니다. 그림의 왼쪽 끝 p=0.13%p = 0.13\% 에서 정규 근사는 199문항이라 하는데 정확값은 318입니다. 199문항에서 유해 응답의 기대 개수는 0.26개라, 0 아니면 1인 개수를 연속인 종 모양으로 어림하는 것 자체가 성립하지 않습니다. 중급 74번이 정답률 95% 근처에서 본 실패와 같은 원인이 반대쪽 끝에서 일어난 것입니다.

둘째, δ\delta 가 작을 때입니다. 유해 응답 예에서 δ\delta 만 줄여 가며, 정규 근사가 준 nn 에서 실제 실패 확률을 정확히 세었습니다.

목표 δ\delta 정규 근사의 nn 실제 실패 확률 목표 대비
0.05 765 4.10×10−24.10 \times 10^{-2} 0.82배
0.0025 1,819 2.64×10−32.64 \times 10^{-3} 1.06배
10−410^{-4} 3,013 2.03×10−42.03 \times 10^{-4} 2.03배
10−610^{-6} 4,762 8.04×10−68.04 \times 10^{-6} 8.04배

목표가 엄할수록 약속이 크게 어긋납니다. 0에 붙은 비율의 표본평균은 오른쪽 꼬리가 길게 늘어진 비대칭 분포인데, 정규 근사는 좌우 대칭인 꼬리를 가정합니다. 한가운데에서는 그 차이가 작지만 꼬리 끝으로 갈수록 커집니다. 2행의 0.0025가 체크포인트 스무 개에 5%를 나눠 준 값이고, 수천 개의 범주나 시점에 같은 일을 하면 3행과 4행의 영역에 들어갑니다. 합집합 경계로 δ\delta 를 잘게 나누는 순간 정규 근사는 믿을 수 없는 도구가 됩니다.

셋째, pp 를 모를 때입니다. 위의 계산은 참값 p=0.005p = 0.005 를 알고 했습니다. 실제로는 pp 를 모르고 관측된 p^\hat p 로 표준오차를 계산하는데, 그렇게 그린 정규 근사 구간 p^±1.96p^(1−p^)/n\hat p \pm 1.96\sqrt{\hat p(1 - \hat p)/n} 이 765문항에서 참값을 품을 확률을 정확히 세면 0.889입니다. 0개가 나와 구간이 점 [0,0][0, 0] 으로 줄어드는 경우가 2.2%나 되고, 적게 나온 경우 구간이 지나치게 좁아지기 때문입니다.

판정을 한 줄로 줄이면 이렇습니다. 기대 개수 np(1−p)np(1 - p) 가 수십을 넘고, δ\delta 가 1% 근처 이상이며, 표준오차에 참값 대신 관측값을 넣는 것이 큰 차이를 내지 않을 때 정규 근사는 정확값에 가까운 좋은 어림입니다. 셋 가운데 하나라도 어긋나면 베른슈타인의 nn 을 쓰고, 그 값은 정확값보다 몇 배 크지만 언제나 참입니다. 베른슈타인 분모의 두 항을 견주는 것도 같은 판정을 다른 말로 한 것입니다. 2ε/32\varepsilon/3 항이 2σ22\sigma^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 np
from math import lgamma, log, exp, sqrt, ceil

def 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, 20
q = 0.5 + t / n
kl = 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.05
v, z = p * (1 - p), 1.959964
need = {"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 800

m = ceil(need["normal"]); k = np.arange(m + 1); ph = k / m
half = 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.7
best = (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.0274
tm = sqrt(log(2 / 0.05) / (2 * nq))                 # 맥디아미드 폭
print(round(tm, 4), (np.abs(best - best.mean()) >= tm).mean())
# 0.0304 1.5e-05

①의 다섯 수가 꼬리 그림의 t=20t = 20 세로줄이고, ②가 필요 표본 수 표의 둘째 줄입니다. 정규 근사의 765문항에서 참값을 아는 경우의 실패 확률은 0.041로 약속을 지키지만, 관측값을 넣어 그린 구간의 포함 확률은 0.889로 떨어집니다. ③의 마지막 열이 「목표 대비」이고, ④가 승자의 저주와 맥디아미드 폭입니다. ④에서 상계 0.0274는 분산 프록시를 범위로 정한 1/(4n)1/(4n) 으로 계산한 값이라, 정답률 70%의 실제 표준편차 0.21/2000=0.0102\sqrt{0.21/2000} = 0.0102 를 넣으면 0.0102×2log⁡20=0.02510.0102 \times \sqrt{2 \log 20} = 0.0251 로 조금 줄어듭니다. 실제 0.0191과의 남은 간격은 최댓값의 기대 상계가 독립을 쓰지 않은 대가입니다.

연습

  1. 참 정답률이 p=0.8p = 0.8 인 모델을 400문항으로 채점합니다. P(∣p^−0.8∣≥0.05)P(\lvert \hat p - 0.8 \rvert \ge 0.05) 를 체비쇼프, 회프딩(양쪽), 베른슈타인(양쪽, b=1b = 1)으로 각각 누르고 어느 것이 가장 날카로운지 말하세요.
    체비쇼프는 0.16/(400×0.0025)=0.160.16/(400 \times 0.0025) = 0.16, 회프딩은 2e−2⋅400⋅0.0025=2e−2=0.2712e^{-2 \cdot 400 \cdot 0.0025} = 2e^{-2} = 0.271, 베른슈타인은 2exp⁡(−1/(0.32+0.0333))=2e−2.83=0.1182\exp(-1/(0.32 + 0.0333)) = 2e^{-2.83} = 0.118 입니다. 베른슈타인이 가장 날카롭고, 이 크기에서는 체비쇼프도 회프딩보다 낫습니다. 분산 0.16이 범위가 허락하는 0.25보다 작아서입니다. 이항분포로 직접 세면 0.0147입니다.
  2. 회프딩으로 정답률을 ε=0.01\varepsilon = 0.01, δ=0.01\delta = 0.01 로 보장하는 문항 수를 구하세요. 같은 문항으로 체크포인트 50개를 동시에 보장하려면 몇 문항이 되나요.
    log⁡(200)/(2×0.0001)=26,492\log(200)/(2 \times 0.0001) = 26{,}492 문항입니다. 50개면 δ\delta 를 50으로 나눠 log⁡(10,000)/0.0002=46,052\log(10{,}000)/0.0002 = 46{,}052 문항입니다. 후보가 50배인데 문항은 1.74배만 늘어납니다.
  3. ±2\pm 2 를 반반으로 갖는 XX 의 ∥X∥ψ2\lVert X \rVert_{\psi_2} 와, 평균 0, 분산 4인 정규분포 YY 의 ∥Y∥ψ2\lVert Y \rVert_{\psi_2} 와 ∥Y2∥ψ1\lVert Y^2 \rVert_{\psi_1} 을 구하세요.
    X2=4X^2 = 4 라 e4/s2≤2e^{4/s^2} \le 2 에서 s=2/log⁡2=2.402s = 2/\sqrt{\log 2} = 2.402 입니다. Y=2ZY = 2Z 이고 노름은 상수배를 그대로 따르므로 28/3=3.2662\sqrt{8/3} = 3.266 입니다. EeY2/s=(1−8/s)−1/2≤2\mathbb{E}e^{Y^2/s} = (1 - 8/s)^{-1/2} \le 2 에서 s=32/3=10.667s = 32/3 = 10.667 이고, 이것이 3.26623.266^2 과 같습니다.
  4. 문항 5,000개로 체크포인트 100개를 채점했습니다. 편차 p^k−pk\hat p_k - p_k 의 분산 프록시를 회프딩 보조정리로 정할 때, 최고 점수가 그 체크포인트의 참값보다 평균적으로 얼마까지 부풀 수 있나요.
    분산 프록시가 1/(4⋅5000)1/(4 \cdot 5000) 이라 2log⁡100/20000=4.605/10000=0.0215\sqrt{2 \log 100 / 20000} = \sqrt{4.605/10000} = 0.0215, 곧 2.15%p입니다. 체크포인트끼리 얽혀 있어도 그대로입니다.
  5. 양성 500개, 음성 2,000개로 AUROC를 잽니다. 유계 차분 상수를 적고, 맥디아미드로 양쪽 δ=0.05\delta = 0.05 에서 AUROC가 기댓값에서 벗어날 수 있는 폭 tt 를 구하세요.
    양성 하나는 c=1/500c = 1/500, 음성 하나는 c=1/2000c = 1/2000 입니다. ∑ci2=500/5002+2000/20002=0.002+0.0005=0.0025\sum c_i^2 = 500/500^2 + 2000/2000^2 = 0.002 + 0.0005 = 0.0025 이고, 2e−2t2/0.0025=0.052e^{-2t^2/0.0025} = 0.05 에서 t=0.0025log⁡40/2=0.0679t = \sqrt{0.0025 \log 40 / 2} = 0.0679 입니다. 적은 쪽 클래스가 폭을 거의 다 정합니다.
  6. 오류율 p=0.02p = 0.02 를 ε=0.01\varepsilon = 0.01, δ=0.05\delta = 0.05 로 재려 합니다. 회프딩, 베른슈타인, 정규 근사의 필요 문항 수를 구하고 정규 근사의 기대 오류 개수를 적으세요.
    회프딩 log⁡40/0.0002=18,444\log 40 / 0.0002 = 18{,}444, 베른슈타인 (0.0392+0.00667)×3.689/0.0001=1,692(0.0392 + 0.00667) \times 3.689 / 0.0001 = 1{,}692, 정규 근사 1.962×0.0196/0.0001=7531.96^2 \times 0.0196 / 0.0001 = 753 입니다. 753문항의 기대 오류 개수는 15.1개라 정규 근사가 크게 빗나가지 않는 자리이고, 보장이 필요하면 베른슈타인의 1,692를 씁니다.

집중부등식은 「표본 nn 개면 오차 ε\varepsilon 를 확률 1−δ1 - \delta 로」라는 문장을 만드는 기계였습니다. 마르코프에 무엇을 넣느냐가 전부였고, 지수함수를 넣는 체르노프 방법이 1/δ1/\delta 를 log⁡(1/δ)\log(1/\delta) 로 바꿨습니다. 회프딩은 범위만으로, 베른슈타인은 분산까지 써서 그 지수를 정했고, 맥디아미드는 평균이 아닌 함수로, 합집합 경계는 여러 사건으로 넓혔습니다. 첫머리의 평가표로 돌아가면, 2,000문항의 72.1%는 스무 개 가운데 고른 숫자라 나아졌다는 증거가 못 되고, 유해 응답 비율은 정규 근사의 765도 회프딩의 73,778도 아닌 베른슈타인의 1,961이 보장의 숫자였습니다. 같은 도구로 LSH의 충돌 확률 보장, 밴딧 UCB가 팔마다 붙이는 신뢰폭 2log⁡t/na\sqrt{2\log t / n_a}(고급 A14 단원), 그리고 「표본 nn 개면 오차 ε\varepsilon 를 확률 1−δ1 - \delta 로 보장한다」는 모든 알고리즘 정리가 증명됩니다. 남은 구멍은 후보가 무한할 때입니다. 합집합 경계의 log⁡K\log K 가 무한대가 되는 자리를 어떻게 메우는지, 그리고 그렇게 얻은 고전적 일반화 경계가 큰 신경망 앞에서 왜 공허해지는지는 다음 글 「고급 9번 · 일반화 경계: 고전 이론이 공허해지는 자리와 PAC-Bayes」가 다룹니다.


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

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