12회 · 최적 검정과 결정 · 노트

4 축차확률비 검정 — Wald (1945)

역사 1943년 컬럼비아 대학의 통계연구단(SRG)에서 해군 대령 Garret L. Schuyler가 W. Allen Wallis에게 물었다. 포탄의 품질 검사에서 표본을 미리 정한 수만큼 다 쏘지 않아도, 처음 몇 발로 결론이 뻔히 보일 때가 많은데 그때 멈추면 안 되는가? Wallis와 Milton Friedman은 이 질문을 Abraham Wald에게 가져갔다. Wald는 몇 달 만에 축차확률비 검정(SPRT)을 만들었다. 같은 오류율을 고정 표본 검정의 절반 정도 관측으로 얻었고, 전쟁이 끝날 때까지 군사 기밀이었다(Wald 1945). 영국의 George Barnard도 같은 시기에 같은 생각에 이르렀다.

4.1 정의와 Wald의 경계

정의 4.1 (축차확률비 검정) $X_1,X_2,\dots$를 하나씩 관측하며 $H_0:f=f_0$ 대 $H_1:f=f_1$을 검정한다. 로그 가능도비의 누적합

$$\Lambda_n=\sum_{i=1}^n\log\frac{f_1(X_i)}{f_0(X_i)}$$

에 대해 상수 $B<0<A$를 정하고, $B<\Lambda_n<A$이면 관측을 계속한다. 처음으로 $\Lambda_N\ge A$가 되면 $H_1$을, $\Lambda_N\le B$가 되면 $H_0$를 택한다. $N$은 멈춘 시각이다.

정리 4.2 (Wald의 경계) SPRT가 확률 1로 멈추면, 실제 오류율 $\alpha'=P_0(\text{$H_1$ 택})$, $\beta'=P_1(\text{$H_0$ 택})$은

$$\alpha'\le e^{-A}(1-\beta'),\qquad\beta'\le e^{B}(1-\alpha')$$

를 만족한다. 따라서 목표 $\alpha,\beta$에 대해 $A=\log\tfrac{1-\beta}\alpha$, $B=\log\tfrac\beta{1-\alpha}$로 두면 $\alpha'\le\tfrac\alpha{1-\beta}$, $\beta'\le\tfrac\beta{1-\alpha}$, 그리고 $\alpha'+\beta'\le\alpha+\beta$이다.

증명 전략 멈춘 경로마다 두 가능도의 비가 $e^A$ 이상(또는 $e^B$ 이하)이다. 이 부등식을 $H_1$을 택하는 경로 전체에 걸쳐 더하면 두 가설 아래의 확률이 비교된다.

1. $R_1$을 $H_1$을 택하는 경로들의 집합이라 하자. 각 경로는 어떤 $n$에서 멈춘 $(x_1,\dots,x_n)$이고, 그 위에서 $\prod_{i\le n}f_1(x_i)\ge e^A\prod_{i\le n}f_0(x_i)$이다.정의 4.1, $\Lambda_n\ge A$

2. $R_1$을 멈춘 시각 $n$으로 나눠 1을 적분하고 $n$에 대해 더한다.

   $$1-\beta'=P_1(R_1)=\sum_n\int_{R_1\cap\{N=n\}}\prod_{i\le n}f_1\ \ge\ e^A\sum_n\int_{R_1\cap\{N=n\}}\prod_{i\le n}f_0=e^A\alpha' .$$

   가산가법성, 1

3. $H_0$을 택하는 경로들의 집합 $R_0$ 위에서는 $\prod f_1\le e^B\prod f_0$이므로 같은 방법으로 $\beta'=P_1(R_0)\le e^BP_0(R_0)=e^B(1-\alpha')$이다.2와 같다, 확률 1로 멈춤

4. $A=\log\tfrac{1-\beta}\alpha$이면 2는 $\alpha'\le\tfrac\alpha{1-\beta}(1-\beta')\le\tfrac\alpha{1-\beta}$이다. $\beta'$도 같다.2 3

5. 두 부등식을 $\alpha'(1-\beta)\le\alpha(1-\beta')$, $\beta'(1-\alpha)\le\beta(1-\alpha')$로 쓰고 더하면 $\alpha'\beta$와 $\alpha\beta'$ 항이 양쪽에서 지워져 $\alpha'+\beta'\le\alpha+\beta$이다.4

조건 확인 사건 $\{N=n\}$은 $(x_1,\dots,x_n)$만으로 정해지므로(멈춘 시각의 정의) 그 위의 확률이 $\prod_{i\le n}f(x_i)$의 $n$차원 적분이다. 사건 $R_1\cap\{N=n\}$ ($n=1,2,\dots$)은 서로소이다. 확률 1로 멈춘다는 가정은 3에서 $P_0(R_0)=1-\alpha'$, $P_1(R_1)=1-\beta'$에 쓰인다.

경계는 “넘침”(멈출 때 $\Lambda_N$이 $A$나 $B$를 조금 넘어선 양)을 무시한 것이어서 보수적이다. 실제 오류율은 목표보다 조금 작다. 경계는 $f_0$과 $f_1$의 모양에 의존하지 않는다. 증명의 1–3이 두 밀도의 비만 썼기 때문이다.

증명 없이 쓰는 사실 (SPRT는 확률 1로 멈추고, 최적이다) $f_0\ne f_1$이면 $\Lambda_n$은 0이 아닌 분산을 갖는 확률보행이므로 띠 $(B,A)$를 벗어나지 못할 확률이 기하급수적으로 줄어든다(연습 4.3). 나아가 Wald와 Wolfowitz(1948)는 오류율이 $(\alpha',\beta')$ 이하인 모든 축차검정 가운데 SPRT가 $E_0N$과 $E_1N$을 동시에 최소화함을 증명했다. 이 과정에서는 증명하지 않는다.

4.2 평균 표본수

보조정리 4.3 (Wald의 등식) $Z_1,Z_2,\dots$가 iid이고 $E|Z_1|<\infty$이며, $N$이 멈춤시각(사건 $\{N\ge i\}$가 $Z_1,\dots,Z_{i-1}$로 정해진다)이고 $EN<\infty$이면 $E\sum_{i=1}^NZ_i=EN\cdot EZ_1$이다.

증명 전략 무작위 개수의 합을 지시함수로 고정된 무한합으로 바꾼다. 멈춤시각이라는 조건이 각 항의 두 인수를 독립으로 만든다.

1. $\sum_{i=1}^NZ_i=\sum_{i=1}^\infty Z_i\,1\{N\ge i\}$이다.지시함수 [T1]

2. $\{N\ge i\}=\{N\le i-1\}^c$은 $Z_1,\dots,Z_{i-1}$로 정해지므로 $Z_i$와 독립이다.멈춤시각의 정의, iid

3. $E\bigl[Z_i1\{N\ge i\}\bigr]=EZ_i\,P(N\ge i)=EZ_1\,P(N\ge i)$이다.2, 2회 정리 2.7

4. 1의 기댓값을 항별로 취하고 3을 넣는다.

   $$E\sum_{i=1}^NZ_i=\sum_{i=1}^\infty EZ_1\,P(N\ge i)=EZ_1\cdot EN .$$

   조건 확인, 2회 정리 1.13

조건 확인 4의 첫 등호는 합과 기댓값의 순서를 바꾼다. $|Z_i|$에 1–3을 그대로 쓰면 $\sum_iE\bigl[|Z_i|1\{N\ge i\}\bigr]=E|Z_1|\,EN<\infty$이므로 Fubini–Tonelli로 바꿀 수 있다 [T6]. $E|Z_1|<\infty$와 $EN<\infty$ 가운데 하나라도 없으면 이 단계가 무너진다.

$Z_i=\log\tfrac{f_1(X_i)}{f_0(X_i)}$에 쓰면 $E\Lambda_N=EN\cdot EZ$이다. 넘침을 무시하고 $\Lambda_N$이 $A$ 또는 $B$와 같다고 보면

$$E_0N\approx\frac{(1-\alpha)B+\alpha A}{E_0Z},\qquad E_1N\approx\frac{\beta B+(1-\beta)A}{E_1Z}$$

이다. $E_0Z=-D(f_0\|f_1)<0$이고 $E_1Z=D(f_1\|f_0)>0$이다(9회 보조정리 1.4). 두 분포가 KL 발산으로 멀수록 빨리 끝난다.

예제 4.4 (불량률 검사) 불량률이 $p_0=0.05$이면 받아들이고 $p_1=0.15$이면 돌려보내는 검사를 $\alpha=0.05$, $\beta=0.10$으로 설계한다. 경계는 $A=\log\tfrac{0.9}{0.05}=2.890$, $B=\log\tfrac{0.1}{0.95}=-2.251$이다. 불량품이면 $\Lambda$에 $\log3=1.099$를 더하고, 양품이면 $\log\tfrac{0.85}{0.95}=-0.111$을 더한다. 4만 번의 시뮬레이션에서 평균 표본수는 $p=0.05$이면 41.9개, $p=0.15$이면 39.1개다(Wald의 근사는 넘침을 무시해 39.3과 33.8). 실제 오류율은 0.035와 0.096이다. 같은 오류율을 고정 표본의 이항 검정으로 얻으려면 77개가 필요하다($K\ge8$이면 기각). SPRT는 절반 남짓으로 같은 일을 한다. 평균 표본수가 가장 큰 것은 두 가설의 중간인 $p=0.1$ 근처다(약 60개, 그림 4.1).

그림 4.1 왼쪽: 불량률 검사의 SPRT 경로 몇 개. 불량품마다 위로 1.10, 양품마다 아래로 0.11 움직이다가 띠(점선)를 벗어나면 멈춘다. 오른쪽: 참 불량률에 따른 평균 표본수(시뮬레이션). 같은 오류율의 고정 표본 검정은 77개(점선)가 필요하다.

연습문제

연습 4.1 (Wald의 등식 ★★) 보조정리 4.3에서 $N$이 멈춤시각이 아니면(다음 관측을 엿보고 멈추면) 결론이 틀릴 수 있음을 $Z_i=\pm1$의 예로 보여라.

풀이

$Z_i=\pm1$ (각 확률 $\tfrac12$)이고 $Z_2=-1$이면 $N=1$, $Z_2=+1$이면 $N=2$로 하자. $\{N\ge2\}=\{Z_2=+1\}$이 $Z_1$만으로 정해지지 않으므로 멈춤시각이 아니다(아직 보지 않은 $Z_2$를 엿보고 멈춘다). $\sum_{i\le N}Z_i$는 $Z_2=-1$이면 $Z_1$, $Z_2=+1$이면 $Z_1+1$이므로 평균이 $\tfrac12$이다. 그런데 $EN\cdot EZ=\tfrac32\cdot0=0$이다.

연습 4.2 (정규 평균의 SPRT ★★) $X_i\iid\N(\mu,1)$, $H_0:\mu=0$ 대 $H_1:\mu=\delta$의 SPRT가 “$\sum_{i\le n}X_i$가 두 직선 $\tfrac B\delta+\tfrac{n\delta}2$와 $\tfrac A\delta+\tfrac{n\delta}2$ 사이에 있으면 계속”임을 보여라.

풀이

$\log\tfrac{f_1(x)}{f_0(x)}=\delta x-\tfrac{\delta^2}2$이므로 $\Lambda_n=\delta S_n-\tfrac{n\delta^2}2$. $B<\Lambda_n<A$는 $\tfrac B\delta+\tfrac{n\delta}2<S_n<\tfrac A\delta+\tfrac{n\delta}2$와 같다. 두 평행선 사이의 띠다.

연습 4.3 (멈출 확률 ★★★) $P(Z_1>0)>0$이면 어떤 $m$과 $q>0$이 있어 연속된 $m$개의 $Z$의 합이 $A-B$를 넘을 확률이 $q$ 이상임을 보이고, 이것으로 $P(N>km)\le(1-q)^k$, 따라서 $EN<\infty$임을 보여라.

풀이

$P(Z>0)>0$이면 $P(Z>\varepsilon)=q_0>0$인 $\varepsilon>0$이 있다. $m>(A-B)/\varepsilon$로 잡으면 연속된 $m$개가 모두 $\varepsilon$보다 클 확률 $q=q_0^m$에서 합이 $A-B$를 넘어 띠를 벗어난다. 서로 겹치지 않는 $k$개의 구간에서 한 번도 그런 일이 없을 확률은 $(1-q)^k$이므로 $P(N>km)\le(1-q)^k$이고, $EN=\sum P(N>j)\le m\sum_k(1-q)^k<\infty$.

연습 4.4 (고정 표본의 크기 ★) 예제 4.4의 고정 표본 검정을 정규근사로 설계하면 $n\approx\bigl(\tfrac{z_\alpha\sqrt{p_0q_0}+z_\beta\sqrt{p_1q_1}}{p_1-p_0}\bigr)^2$임을 보이고 계산하라(8회 연습 3.3).

풀이

$\hat p$의 정규근사로 기각역 $\hat p>p_0+z_\alpha\sqrt{p_0q_0/n}$의 검정력이 $1-\beta$가 되려면 $p_0+z_\alpha\sqrt{p_0q_0/n}=p_1-z_\beta\sqrt{p_1q_1/n}$이다. 풀면 $n=\bigl(\tfrac{1.645\cdot0.218+1.282\cdot0.357}{0.10}\bigr)^2\approx67$. 정확한 이항 계산(77)보다 작다. 불량률이 작아 정규근사가 낙관적이다.

이 절을 PDF로 보기 (12쪽)노트북 4절

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