MAB를 이해하기 위해 필요한 베타분포(Beta Dist.), 이항분포(Binomial Dist.), 베이지안 추정(Bayesian Estimation), 톰슨 샘플링(Tompson Sampling)과 관련된 내용을 정리하였습니다.
1 A/B 테스트 자동화의 필요성
특정 캠페인을 진행하면서, 어떤 캠페인의 배너가 더 잘 구매 전환을 유도하는지를 알기 위해 가장 간단하게 시행할 수 있는 A/B 테스트 방법은 배너별 노출 비율을 수동으로 설정하는 것입니다. 동일한 기간에 A 배너와 B 배너의 노출 비율을 50:50으로 고정하여 데이터를 수집하고 평균 분석 등의 통계적 방법론을 적용하는 것이죠. 만일 테스트 종료 후 A 배너가 B배너 보다 더 효과적으로 구매 전환을 유도하는 것으로 결론이 났다고 가정해 봅시다. 기업의 의사결정자 입장에서는 A 배너가 B 배너에 비해서 더 나은 결과를 보인다는 것을 통계적으로 확인하였으니 A 배너를 계속 노출하자는 의사결정을 하게 되겠죠.
그런데 그러한 결론을 유도하기 위한 데이터 수집기간 동안 B 배너는 어쨌든 계속 노출될수밖에 없습니다. 결과론적으로 보면 A 배너가 더 좋은 결과를 가져다주는 것을 알 수 있음에도 불구하고 말이죠. 다시말해, B 배너 노출에 따른 손실이 발생하게 된 것으로 볼 수도 있습니다.. A 배너를 더 많이 노출 했으면 더 높은 수익을 얻을 수 있었을 텐데 말이죠. 만일 A 배너와 B 배너의 노출 비율을 상황에 적합하게 실시간으로 조정할 수만 있다면 배너 노출 테스트하는 기간 동안의 기회비용을 줄일 수 있지 않을까요? 이제 MAB에 대해서 알아봅시다.
2 MAB 문제
MAB(Multi-armed Bandits)란 이름에서 알 수 있듯이 도박꾼이 카지노의 여러 슬롯머신의 레버(arm)을 당겨서 최대의 이익을 달성하려는 모습에서 비롯되었습니다. 도박꾼이 최대 이익을 달성하려면 알려지지 않은 분포를 가진 여러 슬롯머신의 arm을 당겨서 데이터 패턴을 얻어내야 합니다. 그러나 주어진 자원은 한정적이기 때문에 모든 arm을 무한번 당길 수는 없습니다. 다시말해 탐색(exploration)과 선택(exploitation)의 trade-off 문제를 잘 해결할 수 있어야 한다는 것이죠. 이것이 MAB 문제 해결 전략의 핵심이라고 할 수 있습니다.
2.1 분포의 필요성
우리는 서비스를 진행하면서 어떤 배너에 대해 노출수와 구매 건수(목표 conversion이 구매전환 일 경우) 얻을 수 있습니다. 또한 단순한 사칙연산을 통해서 구매 전환율(구매 건수/노출수)을 얻어 낼 수 있죠. 그런데 그렇게 해서 얻어낸 구매 전환율이 실제 모수를 대표한다고 확신할 수 있을까요? 저희가 얻은 데이터는 표본에 불과하기 때문에, 단순한 표본 통계량으로는 이것이 모수를 대표한다고 단정지어 말할 수 없겠습니다. 그렇다면 얻어진 구매 전환율이 어느정도의 신뢰도 혹은 확신도로 실제 모수를 반영하고 있는지를 ‘정량적’ 지표로 나타낼 수 없을까요? 베타분포(beta)와 이항분포(binomial)를 통해서 표본 데이터에 기반한 모수의 신뢰도를 지속적으로 업데이트 할 수 있습니다.
결론부터 말하자면 사전확률분포와 데이터 발생 분포를 각각 베타분포, 이항분포로 가정하면, 사후확률분포도 베타분포임을 도출할 수 있습니다(베타분포는 이항분포의 켤레사전확률분포). 베타분포는 2개의 모수 \(\alpha, \beta\)를 통해 분포의 모양을 비교적 자유롭게 바꿀 수 있으며, 확률변수가 0~1사이의 실수값이므로, ‘구매 전환율’의 신뢰도를 나타내기의 안성맞춤인 분포이죠.
2.2 사전 분포: 베타분포(beta distribution)
베타분포는 \(RV = \theta(\in [0,1])\)을 가지는 분포를 말합니다. 여기서 \(\theta\)는 0~1사이의 실수값을 가지므로, 확률로 해석할 여지가 있습니다. \(\theta\)를 구매 전환율로 볼때, 표본 데이터를 통해 도출한 전환율이 실제 모수임을 어느 정도의 확신 혹은 신뢰할 수 있는지를 이끌어 낼 수 있습니다.
2.3 데이터 분포(가능도 분포): 이항분포(binomial distibution)
이항분포는 독립적인 베르누이 시행을 \(n\)번 시행했을 때의 성공 횟수 \(k\) 에 대한 분포를 나타냅니다. 이항분포의 PDF는 다음과 같습니다.
이항분포에 왜 조합(combination)이 있을까요? 독립적인 동전 던지기 시행을 5번 했을 때, 2번 성공(=앞면이 나옴) 했을 때를 가정해봅시다. 첫번째, 세번째에서 동전의 앞면이 나왔을 때와 두번째 다섯번째에서 동전이 앞면이 나오는 경우는 모두 같은 확률을 나타냅니다. 다시말해, 5개 중 2개를 순서와 상관없이 뽑는 경우를 모두 고려해야하며, 각각의 사건은 서로 배반사건(disjoint, 동시에 발생할 수 없음)입니다.
2.4 사후 분포: 베타분포(beta distribution)
사후 분포는 사전 분포인 베타분포 \(P(\theta)\)와 데이터 분포인 이항분포 \(P(k)\)의 조건부 결합 확률 밀도 함수(joint probability density function)으로로 나타낼 수 있습니다. 결합 확률 밀도 함수에 대한 자세한 내용은 이곳을 참조해 주세요. 아래 식의 결론은 가능도 분포가 이항분포이고 사전확률분포가 베타분포이면 사후 확률분포도 베타분포라는 결론을 나타냅니다.
\[\begin{aligned} P(\theta|X=k) &= \cfrac{P(X=k|\theta)P(\theta)}{P(X=k)} \\\\ &=\cfrac{P(X=k|\theta)P(\theta)}{\int_{0}^{1} P(X=k|\theta)P(\theta)d\theta} \\\\ &= \cfrac{P(X=k|\theta)P(\theta)}{\int_{0}^{1} P(X=k|\theta)P(\theta)d\theta} \\\\ &= \cfrac{\dbinom{n}{k} \theta^k(1-\theta)^{(n-k)}{\cfrac{\theta^{\alpha-1}\theta^{\beta-1}}{B(\alpha, \beta)}}}{\int P(k|\theta)P(\theta)d\theta} \\\\ &= \cfrac{\dbinom{n}{k}{\cfrac{\theta^{(\alpha+k)-1}\theta^{(\beta+n-k)-1}}{B(\alpha, \beta)}}}{\int_{0}^{1} P(X=k|\theta)P(\theta)d\theta} \\\\ &= \cfrac{\dbinom{n}{k}{\cfrac{\theta^{(\alpha+k)-1}\theta^{(\beta+n-k)-1}}{B(\alpha, \beta)}}}{\int_{0}^{1}\dbinom{n}{k}\theta^{k}(1-\theta)^{n-k} \cfrac {\theta^{\alpha-1}\theta^{\beta-1}} {B(\alpha, \beta)} } \\\\ &= \cfrac{\dbinom{n}{k}{\cfrac{\theta^{(\alpha+k)-1}\theta^{(\beta+n-k)-1}}{B(\alpha, \beta)}}}{\dbinom{n}{k} \cfrac{1}{B(\alpha, \beta)}\int_{0}^{1}\theta^{k}(1-\theta)^{n-k} \theta^{\alpha-1}\theta^{\beta-1}} \\\\ &= \cfrac{\dbinom{n}{k}{\cfrac{\theta^{(\alpha+k)-1}\theta^{(\beta+n-k)-1}}{B(\alpha, \beta)}}}{\dbinom{n}{k} \cfrac{1}{B(\alpha, \beta)}\int_{0}^{1}\theta^{\alpha+k-1}(1-\theta)^{\beta+n-k-1}} \\\\ &= \cfrac{\dbinom{n}{k}{\cfrac{\theta^{(\alpha+k)-1}\theta^{(\beta+n-k)-1}}{B(\alpha, \beta)}}}{\dbinom{n}{k} \cfrac{B(\alpha+k, \beta+n-k)}{B(\alpha, \beta)}} \\\\ &= \cfrac{1}{B(\alpha+k, \space \beta+n-k)} \space \theta^{(\alpha+k)-1}(1-\theta)^{(\beta+n-k)-1} \\\\ &= Beta(\alpha+k, \space \beta+(n-k)) \end{aligned}\]참고로 \(P(X=k)\)는 결합확률분포의 관점에서는 marginal probability이므로, 전확률의 법칙에 따라 아래와 같이 쓸수 있습니다.
\[\begin{aligned} P(k) &= \int P(X=k, \theta)d\theta \\ &= \int P(X=k|\theta)P(\theta)d\theta \end{aligned}\]2.5 켤레 사전 확률 분포(conjugate prior distribution)
켤레 분포란, 모수는 다르지만, 사전 분포와 사후 분포의 형태를 같게 하는 사전 분포를 뜻합니다.
사전분포와 데이터 분포를 각각 베타분포, 이항분포로 가정했을 때, 사후분포는 베타분포이므로 사전분포는 켤레 사전 확률 분포라고 할 수 있습니다.
3 배너 선택 전략: 톰슨 샘플링(Thompson Sampling)
톰슨 샘플링이란, 도출된 베타 분포에서 확률변수의 observaion을 샘플링하는 기법을 말합니다. 배너 \(A\)의 conversion 횟수, expression 횟수를 알고 있으면, \(\alpha_{A}\)와 \(\beta_{A}\)를 다음과 같이 정의할 수 있고 이 두가지 모수만 있으면 각 배너의 베타분포를 그릴 수 있습니다.
\(\alpha_{A} =\) 배너 \(A\)의 conversion 횟수
\(\beta_{A} =\) 배너 \(A\)의 expression 횟수 \(-\) 배너 \(A\)의 conversion 횟수
쉽게 와 닿지 않으니 예시를 들어서 설명해보겠습니다. 배너 A는 expression 13회, conversion 4회. 배너 B는 expression 11회, conversion 5회라면 각 배너의 베타 분포는 아래와 같이 나타납니다.
여기서 노출시킬 배너를 선택할 수 있는 가장 쉬운 방법은 배너 A와 배너 B의 conversion rate의 기댓값을 뽑아서 기댓값이 높은 배너를 노출 시키는 전략을 취하면 될 것 같습니다. 현재 예시에서 배너 A의 conversion rate 기댓값은 0.307, 배너 B의 conversion rate 기댓값은 0.454입니다. 따라서 우리는 배너 B만 계속 노출시키면 되겠군요(0.307<0.454).
그러나 한번만 더 생각 해봅시다. conversion rate의 기댓값이 높은 배너만 계속해서 노출시키는 것이 좋은 판단인지에 대해서 말이죠. 배너 B가 배너 A에 비해 초기 어느 시점에서는 기댓값이 높을 수는 있습니다. 그러나 이러한 현상이 ‘우연히’ 발생 했을 수도 있지 않을까요? 우연히 배너 B를 선호하는 고객이 데이터 수집기간 초기 어느 시점에 잔뜩 유입돼서 배너 B에 편향된 결과를 만들 수도 있었지 않을까요? 우리는 배너 A에 대한 충분한 탐색(exploration)을 하지 못했습니다.
아래의 Algorithm 3.1이 greedy 방식의 sampling을 나타냅니다. 우리는 Algorithm 3.2 방식의 톰슨 샘플링을 적용해 보겠습니다. 톰슨 샘플링이란 단순히 기대값이 높은 arm을 선택하는 것이 아니라 베타 분포에서 랜덤 샘플링을 통해 적절한 탐색(exploration)을 진행하고, 새로 관찰된 데이터를 기반으로 베타 분포를 업데이트 하는 방식을 통해 각 arm에 대한 모수를 추정해 나가는 기법을 말합니다. 톰슨 샘플링 기법을 활용하면 탐색(exploration)과 선택(exploitation)을 적절하게 수행해 나갈 수 있습니다.
계속 예시를 들어보죠. 톰슨 샘플링 결과 배너 A에서는 0.337, 배너 B에서는 0.271가 샘플링 되었습니다. 배너 A의 conversion rate 기댓값은 더 낫지만, 현재 시점에서는 샘플링 된 conversion rate가 더 큰 배너 A를 노출 시키는 전략(exploration)을 취하면 되겠습니다.
결과적으로 N개의 배너 당 2개의 값(conversion 횟수, expression 횟수)만 계속 저장 및 업데이트하면, 베타 분포와 톰슨 샘플링 알고리즘을 통해 적절한 exploration과 exploitation을 진행하여 최적의 배너를 통계 기반으로 찾아갈 수 있겠습니다.
4 베이지안 확률값의 비교: 각 배너간 \(\theta\)의 차이가 통계적으로 유의미할까?(추후 업데이트)
- 각 배너간 구매전환율이 실질적으로 차이가 있는지를 베이지안 확률로 도출할 수 있음
- p-value에 의한 가설 검정(빈도주의 방식)은 여러가지 문제점은 안고 있음
- 베이지안 방법으로 A/B 테스트를 해보자는 것이 요지
- https://brunch.co.kr/@gimmesilver/152324