[A/B Test] 실험의 조기 종료 (Early Stopping)

2022, Apr 30

일반적인 A/B Test (i.e. “Fixed-Horizon Test”, “Fixed-Sample Test”) 에서는 사전에 계산된 샘플 사이즈가 충족되기 전까지 p-value를 계산하는 것이 금지된다. 그 이유는 앞서 살펴본 다중 검정의 문제 때문인데, 샘플 사이즈가 충분하지 않은 상태에서 p-value를 계산하고 이를 바탕으로 결론을 도출할 경우 family-wise type I error가 의도했던 유의 수준 $\alpha$ 를 훨씬 상회하는 문제점이 발생한다. 이를 흔히 p-hacking 이라고 부른다.

한편, 그럼에도 불구하고 진행되고 있는 실험을 조기에 종료하고 싶은 상황은 분명히 존재할 수 있다. 가령, 어떤 실험의 경우 control과 treatment의 차이가 너무 명확해서 실험을 끝까지 진행하는 것이 시간 낭비일 수 있다. 혹은 treatment의 새로운 기능이 user experience에 상당히 안좋은 영향을 미쳐서 실험을 더 이상 진행하는 것에 리스크가 따를 수 있다.

이러한 맥락에서 실험을 끝까지 진행하지 않더라도 family-wise type I error를 유의수준 이하로 컨트롤하면서 통계적으로 타당한 결론을 내릴 수 있는 방법론이 존재한다. 즉, 실험의 “early-stopping”을 지원할 수 있는 특별한 실험 디자인이 있는데, 이를 통계학에서는 “group sequential test (design)“라고 부르며, 관련해서 많은 선행 연구들이 존재한다.

비록 해당 방법론들은 임상 통계학의 도메인에서 연구되었으나, Online A/B Test에도 자연스레 적용될 수 있으며 실제로 이와 관련한 몇가지 포스팅들이 있는 것을 찾아볼 수 있었다. (참고 1, 참고 2)

이러한 맥락에서 group sequential test의 대표적인 방법론들을 소개하고, 해당 방법론들을 사용해서 실험을 조기 종료하는 것이 어떻게 가능한지에 대해 정리해보도록 하겠다.

 

---

1. Group Sequential Tests

일반적인 Fixed Horizon Test를 떠올려보자. 이 경우 실험이 종료된 다음 각 그룹별로 수집된 데이터를 바탕으로 통계분석을 수행하게 된다.

이와는 반대로 “group sequential test”는 실험이 진행되는 과정에서 “일정한 시점” 별로 누적된 데이터에 대해 분석을 수행하는 방법이다. 예를 들어, 일주일 단위로 p-value를 계산한 다음 기존과 동일하게 의사결정을 내리는 것이다. 만약 해당 결과가 유의하다면 실험은 조기에 종료된다.

한편, 저번 포스트의 내용을 바탕으로 할 때 이는 결과적으로 가설 검정을 여러번 수행하는 것이기 때문에 다중 검정의 문제가 발생한다는 것을 직관적으로 알 수 있다. 따라서 이를 해결하기 위한 group sequential test 의 가장 핵심적인 아이디어는, 만약 검정통계량이 정규분포를 따르는 경우 여러 시점별로 false-positive의 확률을 근사적으로 계산하는 것이 가능하다는 내용이다. 이처럼 만약 각 시점별로 false-positive의 확률을 알고 있다면, 앞서 다중 검정을 처리했던 것처럼 유의수준을 보정해서 FWER을 유의수준 이하로 컨트롤 할 수 있을 것이다.

예를 들어 실험이 10일 동안 진행되고 하루를 주기로 총 10번의 중간 분석을 수행할 경우, 각 시점들에서의 false-positive 확률값들을 더한 전체 값이 유의 수준보다 작아질 수 있도록 각 시점마다 사용될 유의수준을 정의할 수 있다.

후술할 모든 방법론들은 모두 이러한 아이디어를 바탕으로 하고 있으며, 이후 구체적인 예시를 통해서 살펴보면 이해가 빠를 것이라고 생각한다.

이와 같은 group sequential test 중에 가장 기초적인 방법은 “Pocock’s Test” 이며, 이를 바탕으로 “O’Brien & Flemming Test” 와 ”alpha-spending function method” 가 제안되었으며 현재 임상 통계 분야에서 널리 활용되고 있다. 이후 자세히 살펴보겠지만, A/B Test의 도메인에서 활용될 수 있는 방법론은 “alpha-spending function method” 라는 방법이다. 앞의 세가지 방법론은 group sequential test의 전체적인 맥락을 이해하는데 도움이 될 것 같아 간략하게 소개를 하고자 한다.

 

(a) Pocock’s Test

가장 기초적인 group sequential test 방법론이며, 개념적으로 다중 검정 보정에서의 “Bonferroni correction“과 유사하다고 생각하면 편하다.

Pocock’s Test에서는 각 중간 분석의 시점 ($1, 2, …, k$) 별로 샘플 사이즈가 일정하게 $m$ 만큼 증가한다고 가정한다. 이 때 시점 $k$ 에서 사용되는 검정통계량은 다음과 같다. 이는 간단하게 말하자면 두 집단의 평균 차이 (two sample t-test의 검정통계량) 를 약간 변형한 것에 불과하다.

$$ \begin{aligned} &Z_k = \frac{1}{\sqrt{2mks^2}} \Big( \sum_{i=1}^{mk}X_{T,i} - \sum_{i=1}^{mk}X_{C,i} \Big) \\[15pt] &\;\;\;\quad s^2: \text{sample variance} \\[5pt] &\quad C, T: \text{control, treatment group} \end{aligned} $$

 

이를 바탕으로 $i (i \leq k)$ 시점까지의 모든 중간 분석에 대해서 계산된 검정 통계량 $Z_i$ 가 일정한 기각역 $C$ 에 포함될 경우 (i.e. $Z_i > C$), treatment가 효과가 있다고 결론을 내리고 실험을 조기 종료하게 된다.

이 때, Pocock’s Test의 가장 큰 특징은 모든 시점에서의 분석에서 동일한 기각역 $C$를 사용한다는 점이다. 구체적으로, 기각역의 값은 다음과 같이 구해진다.

$$ C = P\Big( \{\text{reject }H_0 \text{ at }i=1\} \cup \{\text{reject }H_0 \text{ at }i=2\} \cup \dots \cup \{\text{reject }H_0 \text{ at }i=k\} \Big) $$

 

단, 해당 기각역은 closed-form expression이 존재하지 않으므로 수치해석적인 방법을 사용해서 구하게 된다. 만약 유의수준 $\alpha$가 0.05 일 때, 중간분석의 개수 $k$에 따라 기각역 $C$의 값을 계산한 표는 다음과 같다.

Pocock's Method의 기각역

 

위 표에서 중간 분석의 횟수 $k$가 증가할 수록 대응되는 기각역 $C$의 값이 증가하는 것을 확인할 수 있다. $k = 1$ 인 경우에는 일반적인 fixed horizon test가 되므로, 정규분포에서 유의수준 $0.05$에 대응되는 기각역 $1.96$이 사용되는 것은 당연하다.

이는 직관적으로, 중간 분석의 횟수가 많아질수록 중간분석에서 귀무가설을 기각하는 것이 점점 어려워지도록 만들어 전체적으로는 family-wise type I error가 유의 수준 (0.05) 이하로 유지되도록 맞춰지는 것이라고 이해할 수 있다.

가령, $k = 5$ 의 경우 사용될 기각역은 $2.413$ 이므로 정규분포의 cdf를 바탕으로 이에 대응되는 유의 수준을 계산해보면 $0.0158$ 가 된다. 즉, 계산된 p-value가 $0.0158$ 보다 작아야 귀무가설이 기각되고 treatment의 유의성을 주장할 수 있게 되는 것이다.

 

(b) O’Brien & Flemming’s Test

앞서 살펴본 Pocock’s Test의 단점은 early-stopping이 이뤄지지 않은 경우 최종 분석에서 사용되는 유의수준이 초기 유의 수준인 $\alpha$ 에 비해 너무 작아진다는 점이다. 실제로, $k = 5$ 정도만 되도 유의수준이 0.0158로 굉장히 낮은 것을 앞서 확인할 수 있었다.

이러한 단점을 보완하기 위해 O’Brien & Flemming’s Test는 각 중간 분석과 최종 분석에서 서로 다른 크기의 기각역을 사용하는데, 초기의 중간 분석일수록 더 큰 $C$ 값을 사용하며 중간 분석이 진행될수록 점차 더 작은 $C$ 값을 사용한다는 점이 특징이다.

예를 들어, $K = 5$ 의 경우 중간 분석별로 사용되는 유의 수준은 다음과 같다. 구체적인 계산 과정은 크게 중요하지 않으므로 생략하겠다.

 

위 표에서 최종 분석에서 사용되는 유의수준은 $0.041$로, 초기 유의수준인 $0.05$에 비해 약간 감소한 것을 확인할 수 있다. 그리고 그 이유는 앞 단계의 중간 분석이 수행되는 과정에서 일정량의 유의수준이 “사용” 되어버렸기 때문인데, 중간 분석을 통해서 early-stopping이 가능하도록 설계된 것의 기회 비용이라고 이해하면 된다.

한편, 가장 첫번째의 중간 분석에서 사용되는 유의수준은 고작 $0.00001$로 매우 작은 값임을 확인할 수 있다. 이는 직관적으로 자연스러운데, 실험의 초창기에 수집된 데이터는 질적으로 안정성이 낮을 가능성이 크며 샘플 사이즈가 역시 충분하지 않기에 신뢰할만한 결과라고 판단하기 위해서는 그만큼 더 강한 증거, 즉 더 낮은 유의수준에서 의사 결정을 진행하는 것이 바람직할 것이다.

이러한 측면에서 O’Brien & Flemming’s Test는 앞서 살펴본 Pocock’s Test에 비해 더욱 효율적인 방법론이며, 실제 임상 시험에서는 대부분 O’Brien & Flemming’s Test가 상대적으로 선호된다고 한다.

 

(c) The alpha-spending function method

앞서 살펴본 Pocock’s Test와 O’brien & Flemming Test의 경우, 다음의 중요한 가정 사항들이 있었다.

• 중간 분석의 횟수 $k$가 사전에 정해져야 한다
• 중간 분석의 시점이 거의 동일한 간격으로 이루어져야 한다. (시점마다 샘플 사이즈가 $m$만큼 증가)

그리고 당연하게도, 이러한 가정들은 실제 실험 상황에서 만족되기가 다소 어려울 수 있다.

이를 해결하기 위해, Lan and DeMets (1983) 는 alpha-spending function 이라는 방법을 제안했다. 해당 방법의 핵심 아이디어는 사전에 지정되지 않은 임의의 시점에서 중간 분석을 수행하더라도 family-wise type I error를 유의수준 이하로 컨트롤할 수 있도록 “alpha-spending function” 이란 함수를 활용하는 것이다. 구체적으로, 각 중간 분석 시점까지 얻어진 정보량 (i.e. information fraction) 을 바탕으로 각 중간 분석에서 사용될 유의수준을 분배하는 것이 alpha-spending function의 역할이다.

이러한 맥락에서 연속형 평가 지표의 경우, 특정한 시점에서의 information fraction 은 해당 시점까지 수집된 샘플 사이즈를 사전에 계산된 전체 샘플 사이즈로 나눠준 값에 해당된다. 따라서 시점 $k$에서의 information fraction은 수식적으로 다음과 같이 정의된다.

$$ \begin{aligned} &t_k = \frac{1}{N}\sum_{i=1}^k n_i \;, \quad (k=1, \dots, K) \\[10pt] &\quad n_i:\text{sample size until time }i \\[5pt] &\quad N: \text{total sample size} \end{aligned} $$

 

해당 방법의 가장 큰 장점은 중간 분석의 횟수 $K$ 와 해당 시점에서의 샘플 사이즈 $m$ 을 사전에 지정할 필요가 없다는 점이다. 해당 방법을 적용하기 위해 필요한 것은 오직 전체 샘플 사이즈 $N$과 사용될 alpha-spending function의 종류 뿐이다.

이제 본격적으로 alpha-spending function을 이용한 중간 분석이 어떻게 진행되는지를 살펴보도록 하자.

• $\alpha^*(\cdot)$: 사용될 alpha spending 함수
• $C_k, Z_k, t_k$: 시점 $k$에서의 기각역, 검정통계량, information fraction ($\frac{1}{N}\sum_{i=1}^k n_i$)

과 같이 변수를 정의할 때, 가장 첫 번째 시점에서의 중간 분석에 대한 기각역은 다음과 같이 정해진다.

$$ \begin{aligned} &P_{H_0}\big(|Z_1| \geq C_1 \big) = \alpha^*(t_1) \\[10pt] &\Leftrightarrow \text{ reject }H_0 \text{ if p-value }< \alpha^*(t_1) \end{aligned} $$
alpha-spending function 예시

 

위 식에서, 현재 alpha-spending function에 의해 우변의 $\alpha$ 값이 구체적인 상수값로 구해지므로 (그래프 참고), 표준정규분포의 cdf를 바탕으로 해당 기준을 만족하는 기각역 C_1 을 정의할 수 있다. 따라서 첫번째 중간 분석에서 구해진 검정통계량이 해당 기각역에 포함되면 귀무가설을 기각하고 실험을 조기 종료하게 된다.

마찬가지로, 두번째 시점에서의 중간분석에 대한 기각역은 다음과 같이 구해진다.

$$ \begin{aligned} & P_{H_0}\Big( \{ |Z_1|<C_1\} \text{ and } \{ |Z_2|\geq C_2 \} \Big) = \alpha^*(t_2) - \alpha^*(t_1) \\[10pt] & \Leftrightarrow \text{ reject }H_0 \text{ if p-value }< \alpha^*(t_2) - \alpha^*(t_1) \end{aligned} $$

 

이는 단순히 두번째 시점의 information fraction 값을 alpha-spending function에 대입한 다음, 이를 전 시점까지의 값들로 빼준 것이다. 위의 예시를 바탕으로 할 때, 첫번째 중간 분석과 두번째 중간 분석에서 “소비된” 유의수준의 합은 총 $0.01$이며, 두번째 중간 분석에서 소비된 유의수준은 $0.009$ 이다.

</span>

 

위와 같은 절차를 반복할 경우, $k$ 번째 중간 분석에서 사용되는 (소비되는) 유의수준은 다음과 같다.

$$ \begin{aligned} & P_{H_0}\Big( \cap_{i=1}^{k-1} \big(\{ |Z_i|<C_i\} \big) \text{ and } \{ |Z_k|\geq C_k \} \Big) = \alpha^*(t_k) - \alpha^*(t_{k-1}) \\[10pt] & \Leftrightarrow \text{ reject }H_0 \text{ if p-value }< \alpha^*(t_k) - \alpha^*(t_{k-1}) \end{aligned} $$

 

복잡해보이지만, 결국 주어진 유의수준 $\alpha$를 다음과 같이 나누어서 각각의 중간 분석에서 사용하겠다는 것에 불과하다.

$$ P_1 + P_2 + \dots + P_k = \alpha $$

 

이제 alpha-spending function 방법의 개괄적인 아이디어는 전부 파악했다. 다음으로는 어떤 alpha-spending function들이 있는지를 살펴볼 차례이다. 이와 관련해서 여태까지 많은 alpha-spending function들이 연구되어 왔는데, 여기서는 그 중에서 대표적인 몇가지를 소개하도록 하겠다.

 

(1) Pocock’s Test와 근사적으로 같아지는 alpha-spending function

 

$$ \alpha^*(t_k) = 4 \Big( 1 - \Phi\big(\frac{\Phi^{-1}(1 - \alpha/4)}{\sqrt{t_k}} \big) \Big) $$

 

(2) O’Brien & Flemming’s Test와 근사적으로 같아지는 alpha-spending function

 

$$ \alpha^*(t_k) = \alpha \; \text{ln} (1 + (e - 1)t_k) $$

 

(3) The Rho-family (Kim and DeMets 1987)

 

$$ \alpha^* (t_k) = \alpha t_k^\rho $$  

 

• 그래프를 통해 확인할 수 있듯이, $\rho$의 값이 커질수록 초기 중간 분석에서 더 많은 유의수준을 사용하게 된다.

 

(4) The Gamma-family (Hwang, Shih, Decani 1990)

 

$$ \begin{aligned} \alpha^*(\gamma, t_k) = \begin{cases} \alpha\Big( \frac{1-exp(-\gamma t_k)}{1 - exp(-\gamma)} \Big), & \mbox{for } \gamma \neq 0 \\[10pt] \alpha t_k, & \mbox{for }\gamma =0 \end{cases} \end{aligned} $$

 

 

• rho-family와 유사하게 큰 $\gamma$ 값을 사용할수록 초기 중간 분석에서 더 많은 유의수준을 사용하게 된다.

구체적인 예시로, 총 다섯번의 중간 분석이 허용된 실험에서 rho-family function을 이용할 경우 각 중간 분석에 대한 유의수준은 다음과 같이 구해진다.

 

---

Reference

• https://bytepawn.com/early-stopping-in-ab-testing.html
• https://www.aarondefazio.com/tangentially/?p=83
• STUART J. POCOCK, Group sequential methods in the design and analysis of clinical trials, Biometrika, Volume 64, Issue 2, August 1977, Pages 191–199, https://doi.org/10.1093/biomet/64.2.191
• O’Brien PC, Fleming TR. A multiple testing procedure for clinical trials. Biometrics. 1979 Sep;35(3):549-56. PMID: 497341.
• K. K. Gordon Lan, & DeMets, D. L. (1983). Discrete Sequential Boundaries for Clinical Trials. Biometrika, 70(3), 659–663. https://doi.org/10.2307/2336502