1. A/B 테스트의 확장판 MAB
MAB(Multi-Armed Bandit)는 A/B 테스트의 탐색(Exploration)과 활용(Exploitation)의 문제를 체계화한 것이다.
A/B 테스트의 문제점
“알고리즘 A, B, C 중 어떤게 가장 좋은 성과를 얻을 수 있을까?”
A/B 테스트란 여러 알고리즘 중에서 가장 좋은 성과를 내는 알고리즘을 선택하는 것이다. 그러나 A/B 테스트에는 탐색-수확 딜레마 (The Exploration-Exploitation Dilemma) 문제가 존재한다.
- 탐색(Exploration)의 문제 : 테스트를 할수록 기회비용이 발생
- Ex) 직관적으로 기존의 A 알고리즘의 매출이 더 높을 것이라 예상했지만, 새로운 B 알고리즘을 적용했을 때 매출을 분석하기 위해 일주일 간 A/B 테스트를 시행하여 예상대로 B 알고리즘이 A 알고리즘 대비 매출이 더 낮은 것을 확인할 수 있었다.
- 즉, 직관대로 테스트를 하지 않았다면 매출 손실(기회비용)은 없었을 것이다.
- 활용(Exploitation)의 문제 : 테스트를 짧게하면 신뢰성을 보장할 수 없음
- Ex) 일주일간의 A,B 테스트를 통해 B 알고리즘이 단기적으로는 매출이 더 낮지만, 장기적인 신뢰성을 보장할 수는 없다.
- 즉, 테스트 기간은 기회비용과 신뢰성을 고려하여 최소한의 비즈니스 사이클을 포함하도록 한다.
위와 같이 테스트에는 Exploration-Exploitation Tradeoff 가 존재한다. 탐색 (Exploration)은 가장 나은 대안을 찾기 위해 테스트하는 과정을 의미하고, 활용 (Exploitation)은 테스트를 중단하고 결정된 대안을 선택하는 것을 의미한다. 테스트를 많이 하면 많이 하는대로 기회비용 문제가 발생하고, 안하면 안하는대로 신뢰성의 문제가 발생한다. 이러한 문제를 체계화한 것이 MAB(Multi-Armed Bandit)이다.
2. MAB(Multi-Armed Bandit)란?
MAB(Multi-Armed Bandit)란 슬롯머신의 속어 “One Armed Bandit”에서 “Multi”를 붙여 여러 대의 슬롯 머신을 비유한 표현이다.
카지노에서는 슬롯머신 마다 당첨되는 비율이 모두 다르게 설정한다고 한다. 따라서, 고객 입장에서 가장 높은 당첨 확률을 가진 슬롯머신을 선택하기 위해서는 A/B 테스트의 Exploration- Exploitation Tradeoff 논리가 적용된다.
어느 슬롯머신의 당첨 확률이 가장 좋은지 확인하기 위해 탐색(Exploration)의 관점으로 모든 슬롯머신을 여러 번 당겨보면 기회비용의 문제가 발생하고, 활용(Exploitation)의 관점으로 모든 슬롯머신을 한 두 번만 당겨 가장 수익률이 높은 머신을 선택하면 신뢰성을 보장할 수 없다.
즉, MAB 알고리즘이란 탐색과 활용을 최적화하여, 매번 수익률이 가장 높을 것으로 예측되는 슬롯머신을 선택해 수익률을 극대화한다.
3. MAB 용어
- 행동(Action) : MAB에서 선택된 대안 (Ex. A/B 테스트에서 A 알고리즘, B 알고리즘)
- 보상(Reward) : 한 번의 행동에 따른 수치화된 결과 (Ex. 클릭, 구매)
- 가치(Value) : 행동으로 인한 기대 보상
MAB에서는 모든 행동이 순서대로 발생한다 가정한다. 그 순서에 따라 시점 $t$의 행동을 $A_{t}$라 하고, 행동에 따른 보상은 $R_{t}$로 표기한다. 또한, 행동 $a$의 가치는 $q∗(a)$, 시점 $t$에 추정된 가치는 $Q_{t}(a)$라 쓴다.
4. MAB 알고리즘
Greedy
한 번씩 해보고, 가장 수익률이 높은 슬롯머신 선택
- 모든 슬롯머신을 한 번씩 플레이한 후, 수익률이 가장 높은 슬롯머신에 모두 투자
- 하지만, 충분한 탐색(Exploration)이 이루어지지 않음
- 수식
$$
A_t = argmax_a Q_t(a)
$$
Epsilon-Greedy
10번중 8번은 가장 수익률이 높은 슬롯머신 선택, 나머지 2번은 무작위로 선택
- Greedy 알고리즘에서 탐색을 촉진하기 위해 보완된 알고리즘
- $1-\epsilon$의 확률로는 Greedy 알고리즘 (활용)
- $\epsilon$(Epsilon)의 확률로는 랜덤하게 선택 (탐색)
- 파라미터 $\epsilon$가 Exploration- Exploitation Tradeoff를 조절
- 단점
- 과도한 탐색 : 어느정도 시간이 지나 최적의 슬롯머신을 찾더라도, 계속해서 $\epsilon$만큼의 탐색을 하여 최적 값과 멀어지는 문제가 발생
- 부족한 탐색 : $\epsilon$의 확률로 sub-optimal한 나머지 슬롯머신들을 무작위로 뽑기 때문에, 전체 슬롯머신 중에서 탐색하지 못하거나, 혹은 탐색을 덜하여 정보를 얻지 못한 슬롯머신이 있을 수 있음
UCB (Upper Confidence Bound)
탐색과 활용을 적절히 선택
위 알고리즘들은 탐색했던 슬롯머신으로부터 얼마나 많은 보상을 받았는 지에만 초점을 맞추어, 그들이 처음에 경험한 보상이 얼마 없던 슬롯머신들의 정보를 저장하지 않음
UCB는 지금까지 알려진 보상뿐만 아니라, 그 보상이 얼마나 많은 탐색을 통해 알려진 결과인지(즉, 얼마나 확실한지[Uncertainty Weight])도 함께 따져서, 덜 확실한 쪽에 더 많은 탐색을 수행
추정된 가치 $Q_t(a)$에서 일종의 신뢰 구간을 구하여, 신뢰 구간 위쪽의 슬롯머신을 선택
수식
$$
A_t = argmax_a [ Q_t(a) + c\sqrt{\frac{\ln t}{N_t(a)}}]
$$- $t$ : 모든 슬롯머신을 선택한 횟수의 합 (시점)
- $Q_t(a)$ : $t$ 시점까지 슬롯머신 $a$의 누적 보상 (Reward)
- $c$ : 신뢰 구간의 폭을 제어하는 파라미터로 탐색의 정도를 결정 ($c$ $\propto$ 탐색)
- $N_t(a)$ : $t$ 시점 전까지 해당 슬롯머신을 선택했던 횟수 (충분히 탐색되지 않은 슬롯머신에 가중치를 줌)
- $c\sqrt{\frac{\ln t}{N_t(a)}}$ : 선택한 슬롯머신이 최적의 슬롯머신이 될 가능성을 의미 (신뢰 구간)
- 일반적으로 신뢰구간을 구하는 식 $\mu + c\sqrt{\sigma^2 / n}$에서 $\mu$ 대신 $Q_t(a)$, $\sigma^2$ 대신 $\ln t$를 사용한 것만 다름을 알 수 있음
- 즉, 수식의 첫 번째 항 $Q_t(a)$은 활용에 중점을 두고, 두 번째 항 $c\sqrt{\frac{\ln t}{N_t(a)}}$은 탐색에 중점을 두기 때문에 UCB 알고리즘은 활용과 탐색을 적절히 고려함
장점
- 랜덤으로 탐색하지 않고, 최적이 될 수 있을 만한 슬롯머신을 선택할 가능성을 수치로 계산한 뒤, 이 수치를 바탕으로 선택을 결정하기 때문에 어떻게 행동하는지 알 수 있음
- 설정해야 할 자유 (Free) 파라미터가 없음
- 세상이 어떻게 행동할지에 대한 명확한 감각을 갖지 않아도 UCB를 사용 가능
단점
- 매 라운드마다 수치 값을 갱신해야 함
- UCB를 계산하기 위해 Empirical Mean이 필수적이기 때문에 반드시 처음에 모든 슬롯머신들을 한 번 이상 탐색해야 하는 문제점이 있음
톰슨 샘플링 (TS, Thompson Sampling)
보상에 분포가 있음
값을 직접 추정하여 예측한 그대로 행동하는 결정론적인(deterministic) UCB 알고리즘과 달리 기댓값의 사후 분포를 계산한 뒤 샘플링한 값을 기준으로 슬롯머신을 선택
이 선택한 슬롯머신을 통해 얻은 보상을 바탕으로 베이지안 정리를 이용해 분포를 갱신
사전 지식
표현식 p(A)
- 표현식 p(A)는 사건 A가 참일 확률을 의미
- 확률 값은 0~1의 값을 가짐 (0 ≤ p(A) ≤ 1)
확률 질량 함수 (PMF, probability mass function)
- p(x)는 사건 x가 일어날 확률
- p()는 확률 질량 함수 또는 pmf이며, 모든 사건의 확률의 합은 1이 됨
베르누이 분포 (bernoulli distribution)
베르누이 분포는 1이 나올 확률을 의미하는 $\theta$라는 모수를 가지며, 0이 나올 확률은 $1−\theta$ 이다. (변수와 모수는 세미콜론(;)기호로 분리)
$$
\begin{split}\text{Bern}(x;\theta) = \begin{cases} \theta & \text{if }x=1, \1-\theta & \text{if }x=0\end{cases}\end{split}
$$
베타 분포 (beta distribution)
베타 분포는 두 개의 양수 변수로 표현할 수 있는 확률 분포이며, $\alpha$ 와 $\beta$ 파라미터로 분포의 모양을 조절
베타 분포는 [0, 1] 구간을 지원
베타 분포의 확률 밀도 함수
$$
\text{Beta}(x;\alpha,\beta) = \frac{x^{\alpha-1} (1-x)^{\beta-1}}{B(\alpha,\beta)}
$$
알고리즘 수도 코드
확률 분포에서 샘플링한 후 argmax로 배너를 선택하고 결과를 관찰한 뒤에 그 결과를 확률 분포에 반영
베르누이 밴딧에서의 톰슨 샘플링 알고리즘
베타 분포에서 각 광고의 S (클릭 횟수), F (클릭하지 않은 횟수)를 바탕으로 확률 밀도 함수를 그림 (Draw)
이 확률 밀도 함수에서 값들을 샘플링한 뒤, 뽑힌 값들 중 가장 큰 값의 광고를 선택 (argmax)
이후에 CTR이 어떻게 바뀌었는지 탐색하고 클릭 성공 (S)과 클릭 실패 (F)를 기록하여 다시 톰슨 샘플링 반복
출처 : An Empirical Evaluation of Thompson Sampling
장점
- 확률적 알고리즘 (확률적으로 움직임)
- 한 번에 하나의 슬롯머신만 플레이하는 싱글플레이 문제에서, N개의 슬롯머신을 플레이할 수 있는 멀티플레이 문제로의 확장이 용이함
- 액션을 최대화하는 문제를 만족하는 M개의 액션을 순서대로 고르는 방법 (MP-TS, Multiplay Thompson Sampling)
- N - 1 개의 슬롯머신은 경험적인 결과가 가장 좋은 슬롯머신을 고르고, 마지막 N번째 슬롯머신만 Thompson Sampling으로 푸는 방법 (IMP-TS, Improved MP-TS)
- 실제로는 두 번째 방법이 Asymptotic Bound를 유지하면서 성능이 조금 더 좋음
- 나중에 들어오는 피드백 데이터도 수용할 수 있음 (회원가입 / 결제 데이터 등등)
단점
- 시간의 흐름에 따라 $\alpha + \beta$ 값이 계속해서 증가하므로 Algorithm 1의 모델 파라미터 $\theta$에 대한 추정을 하기 점점 어려움
- 위 문제를 해결하기 위한 방법으로 Discounted Thompson Sampling을 사용
톰슨 샘플링 예시 (출처 : MAB (Multi-Armed Bandits)
웹에서 노출되는 3개의 배너의 클릭 확률을 구한다.
TS는 배너를 클릭할 확률을 베타 분포로 표현하기 위해 두 가지의 숫자가 필요
- 배너를 보고 클릭한 횟수
- 배너를 보고 클릭하지 않는 횟수
- Ex) Beta(배너를 보고 클릭한 횟수 + 1, 배너를 보고 클릭하지 않는 횟수 + 1)
두 번의 배너 노출 결과 다음과 같은 CTR을 가짐
- 배너1 : 1번의 클릭 / 2번의 노출 = 50%
- 배너2 : 0번의 클릭 / 2번의 노출 = 0%
- 배너3 : 1번의 클릭 / 1번의 노출 = 100%
greedy 알고리즘 : 경험상 가장 성능이 좋은 배너1을 선택
e-greedy 알고리즘 : 확률적으로 경험상 가장 성능이 좋은 배너1을 선택하거나 무작위로 탐색을 하기 위해 다른 배너2,3을 선택할 수 있음
톰슨 샘플링 알고리즘 : 확률 밀도 함수가 수렴하기 전까지는 샘플링이 수행되고 나면, 다른 배너들이 선택될 가능성이 있음 (샘플된 값에서 가장 큰 값을 선택)
- 하지만, 여러번의 수행을 거쳐 확률 밀도 함수가 수렴하게되면 샘플링 값을 통해 어떤 배너가 가장 좋은지 명확하게 분포에서 표현됨
- 결국, 베이지안 추론을 통해 배너3이 가장 우수하다는 것을 알 수 있음
UCB vs 톰슨 샘플링
아래 그림은 톰슨 샘플링의 논문에 있는 그림으로, UCB보다 톰슨 샘플링이 좋은 성능을 보임
Regret은 최선의 선택에 비해 잘못된 선택을 함으로써 얼마나 손해를 입었는 지를 수치화한 값
출처 : An Empirical Evaluation of Thompson Sampling
References
'추천 시스템 > Study' 카테고리의 다른 글
| A/B 테스트 (0) | 2022.02.14 |
|---|---|
| 연관 분석 (Association Analysis) (0) | 2022.02.10 |
댓글