2회 · 기댓값·부등식·대수의 법칙 · 노트

8 Beautiful insights — 같은 도구, 오늘의 문제

8.1 지수적 집중: Chernoff와 Hoeffding

Chebyshev 한계는 $1/n$으로 준다. 실제 꼬리 확률은 지수적으로 준다. Bernoulli가 “확실성을 10배 높이는 데 5,708번이면 된다”고 쓴 것이 그 흔적이다. 따름정리 5.2의 Chernoff 한계를 이항분포에 쓰면 이 지수적 감소를 증명할 수 있다.

정리 8.1 (이항분포의 Chernoff 한계) $K\sim\mathrm b(n,p)$, $\hat p=K/n$, $p<a<1$이면

$$P(\hat p\ge a)\le e^{-n\,D(a\|p)},\qquad D(a\|p)=a\log\frac ap+(1-a)\log\frac{1-a}{1-p} .$$

증명 $t>0$에 대해 따름정리 5.2와 예제 3.2로

$$P(K\ge na)\le e^{-tna}(q+pe^t)^n=\exp\bigl(-n\,[ta-\log(q+pe^t)]\bigr) .$$

대괄호를 $t$에 대해 최대로 한다. 미분해 0으로 놓으면 $a=\tfrac{pe^t}{q+pe^t}$, 곧 $e^t=\tfrac{aq}{(1-a)p}$이고, $a>p$이므로 $t>0$이다. 이 값을 넣으면 $q+pe^t=\tfrac q{1-a}$이므로

$$ta-\log(q+pe^t)=a\log\frac{aq}{(1-a)p}-\log\frac q{1-a}=a\log\frac ap+(1-a)\log\frac{1-a}{q}=D(a\|p) .$$

$D(a\|p)$는 Bernoulli($a$)와 Bernoulli($p$) 사이의 Kullback–Leibler 발산이다(8.2절). 꼬리 확률의 지수가 정보 이론의 양으로 나온다. 이 지수를 다루기 쉬운 이차식으로 누르면 다음을 얻는다.

정리 8.2 (Hoeffding 부등식 (Bernoulli 시행)) $\varepsilon>0$이면

$$P\bigl(|\hat p-p|\ge\varepsilon\bigr)\le2\,e^{-2n\varepsilon^2} .$$

증명 $g(\varepsilon)=D(p+\varepsilon\|p)-2\varepsilon^2$ ($0\le\varepsilon<q$)이 음이 아님을 보이면 정리 8.1로 $P(\hat p\ge p+\varepsilon)\le e^{-2n\varepsilon^2}$이다. 직접 미분하면 $g(0)=0$, $g'(0)=0$이고

$$g''(\varepsilon)=\frac1{(p+\varepsilon)(q-\varepsilon)}-4\ \ge\ 0,$$

$a(1-a)\le\tfrac14$이기 때문이다. $g'$은 증가하고 $g'(0)=0$이므로 $g'\ge0$, 따라서 $g$는 증가하고 $g\ge g(0)=0$이다. 왼쪽 꼬리는 $\hat p$ 대신 $1-\hat p$에 같은 논증을 쓰고, 두 꼬리를 Boole 부등식으로 더한다.

Bernoulli의 질문에 쓰면 $2e^{-2n\varepsilon^2}\le\tfrac1{1001}$, 곧

$$n\ \ge\ \frac{\log(2\cdot1001)}{2\varepsilon^2}=\frac{\log2002}{0.0008}\approx9{,}503 .$$

Chebyshev의 600,600보다 60배 작다. 정리 8.1를 그대로 쓰면 9,121이다. 결정적인 차이는 $\delta=\tfrac1{1001}$이 $\log\tfrac1\delta$로 들어간다는 것이다. Chebyshev에서는 $\tfrac1\delta$로 들어갔다. 확실성을 10배 높이는 비용이 Chebyshev로는 시행 수의 10배이지만, Hoeffding으로는 $\tfrac{\log10}{2\varepsilon^2}\approx2{,}878$번을 더하는 것이다. 정확한 계산에서는 약 2,600번이고, Bernoulli의 공식은 5,708번이었다. 그의 어림은 상수가 두 배쯤 컸을 뿐 모양은 옳았다. 일반적인 Hoeffding 부등식(1963)은 $[0,1]$ 안의 값을 갖는 임의의 독립 확률변수의 평균에 대해 같은 한계를 준다.

그림 8.1 $p=0.6$, $\varepsilon=0.02$에서 $P(|\hat p_n-p|\ge\varepsilon)$의 정확한 값(파랑)과 세 한계. Chebyshev는 $1/n$로, Chernoff·Hoeffding은 지수적으로 준다. 세로축은 로그 눈금이다.

학습 이론의 첫 정리 분류기 $h$의 시험 오류율 $R(h)$를 $n$개의 독립 표본에서 잰 오류율 $\hat R(h)$로 추정한다. $h$가 정해져 있으면 오류 지시변수들의 평균이므로 Hoeffding으로 $P(|\hat R(h)-R(h)|\ge\varepsilon)\le2e^{-2n\varepsilon^2}$이다. 그런데 학습은 $|H|$개의 후보 가운데 $\hat R$이 가장 작은 것을 고른다. 그러면 하나가 아니라 모든 후보가 동시에 맞아야 하고, Boole 부등식(1회 정리 4.3)으로

$$P\bigl(\text{어떤 }h\in H\text{에서 }|\hat R(h)-R(h)|\ge\varepsilon\bigr)\le2|H|e^{-2n\varepsilon^2} .$$

오른쪽이 $\delta$ 이하가 되는 $n\ge\tfrac{\log(2|H|/\delta)}{2\varepsilon^2}$이 PAC 학습의 표본 크기다. 후보가 100만 개여도 $\log|H|\approx14$만큼 늘 뿐이다. Bernoulli의 질문에 Boole 부등식 하나를 더한 것이 일반화 이론의 출발점이다.

8.2 Jensen과 정보

정리 8.3 (Gibbs 부등식) $p=(p_1,\dots,p_m)$과 $q=(q_1,\dots,q_m)$이 확률질량함수이고 $p_i>0$이면 $q_i>0$이라 하자. 그러면

$$D(p\|q)=\sum_ip_i\log\frac{p_i}{q_i}\ \ge\ 0$$

이고, 등호는 $p=q$일 때뿐이다.

증명 $X$가 값 $\tfrac{q_i}{p_i}$를 확률 $p_i$로 갖는다고 하자($p_i>0$인 $i$만). $\log$는 오목이므로 Jensen으로

$$-D(p\|q)=E\log X\le\log EX=\log\sum_{i:p_i>0}q_i\le\log1=0 .$$

$\log$는 순오목이므로 등호는 $X$가 상수일 때, 곧 $q_i/p_i$가 일정해 $q=p$일 때뿐이다.

이것이 기계학습의 교차 엔트로피 손실이 작동하는 이유다. 참 분포 $p$와 모형 $q$의 교차 엔트로피는 $-\sum p_i\log q_i=H(p)+D(p\|q)$이고, $H(p)=-\sum p_i\log p_i$는 모형과 상관없으므로, 교차 엔트로피를 줄이는 것은 $D(p\|q)$를 줄이는 것이다. Gibbs 부등식으로 최솟값은 $q=p$에서 얻는다. 9회에서 최대가능도 추정이 바로 이 원리임을 본다.

변분 추론과 VAE의 ELBO도 Jensen 한 줄이다. 관측 $x$와 숨은 변수 $z$의 모형 $p(x,z)$와 아무 분포 $r(z)$에 대해

$$\log p(x)=\log\sum_zr(z)\frac{p(x,z)}{r(z)}\ \ge\ \sum_zr(z)\log\frac{p(x,z)}{r(z)}\qquad(\log\text{가 오목}).$$

계산할 수 없는 왼쪽 대신 오른쪽을 키운다. 10회의 EM 알고리즘도 같은 부등식에서 나온다.

8.3 기댓값으로서의 손실, 그리고 Kelly

모형을 훈련할 때 줄이는 “훈련 손실” $\tfrac1n\sum_i\ell(\theta;x_i)$는 손실의 표본평균이고, 우리가 정말 줄이고 싶은 것은 그 기댓값 $E\,\ell(\theta;X)$다. 정해진 $\theta$에서 둘을 잇는 것이 대수의 법칙이고, 고른 $\theta$에서 둘을 잇는 것이 앞의 학습 이론이다. 미니배치 확률적 경사하강법은 기울기의 기댓값을 작은 표본평균으로 추정하고, 그 오차가 배치 크기의 $1/\sqrt b$로 준다는 것을 이용한다.

Daniel Bernoulli의 로그 효용은 1956년 Bell 연구소의 John Kelly에게서 다시 태어났다. 이길 확률이 $p>\tfrac12$인 같은 배당의 내기를 되풀이할 때 가진 돈의 비율 $f$를 건다면, $n$판 뒤의 돈은 $W_n=W_0\prod_i(1\pm f)$이고

$$\frac1n\log\frac{W_n}{W_0}=\frac1n\sum_{i=1}^n\log(1+fR_i)\ \xrightarrow{P}\ G(f)=p\log(1+f)+q\log(1-f)$$

이다($R_i=\pm1$, 대수의 법칙). 장기 성장률 $G$를 최대로 하는 비율은 $f^*=p-q$이다(연습 8.3). 기댓값 $EW_n$을 최대로 하려면 전부를 걸어야 하지만($f=1$), 그러면 한 번만 져도 파산한다. 기댓값을 최대로 하는 것과 거의 확실하게 잘 되는 것은 다르다. St. Petersburg 역설과 같은 교훈이다.

연습문제

연습 8.1 (Hoeffding의 여론조사 ★) 연습 6.1의 여론조사($\pm3\%$포인트, 틀릴 확률 5%)에 필요한 $n$을 Hoeffding 부등식으로 구하고, Chebyshev(5,556명)·정규근사(1,068명)와 비교하라.

풀이

$2e^{-2n(0.03)^2}\le0.05$에서 $n\ge\tfrac{\log40}{2\cdot0.0009}\approx2{,}050$명. Chebyshev의 5,556명보다 훨씬 작고 정규근사의 1,068명의 두 배쯤이다. Hoeffding은 정규근사처럼 “$n$이 크면”이라는 근사 없이 모든 $n$에서 참이다.

연습 8.2 (두 주사위의 KL ★) 공평한 주사위 $p$와, Weldon의 자료에서 추정한 주사위 $q$(면 1–4에 $\tfrac{1-\hat p}4$, 면 5·6에 $\tfrac{\hat p}2$, $\hat p=0.33769$, 예제 2.11) 사이의 $D(p\|q)$와 $D(q\|p)$를 구하라. 대칭인가?

풀이

노트북의 계산으로 $D(p\|q)\approx4.24\times10^{-5}$, $D(q\|p)\approx4.25\times10^{-5}$이다. 거의 같지만 같지 않다. KL 발산은 일반적으로 대칭이 아니다. 아주 작은 값이라는 것은 주사위 한 번으로는 두 분포를 거의 구별할 수 없다는 뜻이다. Weldon의 주사위 $315{,}672$개 굴림에서는 $nD(q\|p)\approx13.4$가 되어 구별할 수 있다. 가능도비로는 $e^{13.4}\approx7\times10^5$배다(9회).

연습 8.3 (Kelly 비율 ★★) $G(f)=p\log(1+f)+q\log(1-f)$를 최대로 하는 $f^*=p-q$를 구하고, $p=0.6$일 때 $G(f^*)$를 계산하라. $f=2f^*$이면 $G$는 어떻게 되나?

풀이

$G'(f)=\tfrac p{1+f}-\tfrac q{1-f}=0$에서 $p(1-f)=q(1+f)$, $f^*=p-q$. $G''<0$이므로 최대다. $p=0.6$이면 $f^*=0.2$, $G(f^*)=0.6\log1.2+0.4\log0.8\approx0.0201$. 판마다 약 2%씩 복리로 자라 약 34판에 돈이 두 배가 된다. $f=0.4$이면 $G\approx-0.0024<0$이다. 판마다 유리한 내기인데도 너무 많이 걸면 돈은 확률 1에 가깝게 0으로 간다.

연습 8.4 (후보가 많을 때 ★) $|H|=10^6$개의 분류기 가운데 하나를 고를 때, 모든 후보의 오류율을 동시에 $\pm0.02$ 안으로 99% 확신하려면 $n$이 얼마면 되나? $|H|=1$일 때와 비교하라.

풀이

$n\ge\tfrac{\log(2\cdot10^6/0.01)}{2(0.02)^2}\approx23{,}892$. $|H|=1$이면 $\tfrac{\log200}{0.0008}\approx6{,}623$. 후보가 100만 배 늘어도 표본은 3.6배만 늘어난다.

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

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