톰슨 샘플링 for Bandits
밴딧 문제를 해결하는 또 하나의 baseline
이번 포스팅에서는 톰슨 샘플링에 대해 소개해드리겠습니다. 멀티암드밴딧(MAB) 보다는 좀 더 어려운 확률이론이 나오니, 먼저 대학교 때 기말고사를 보고 머릿 속에서 지워버린 수학을 다시 살려내보겠습니다. ^^
표현식 p(A)
표현식 p(A) 는 사건 A 가 참일 확률을 의미합니다. 확률의 값은 0 부터 1의 값을 가질 수 있죠.
0 ≤ p(A) ≤ 1
확률 질량 함수(pmf, probability mass function)
p(x)은 사건 x가 일어날 확률입니다. 여기서 p()는 확률 질량 함수 또는 pmf이다. 모든 사건의 확률을 더하면, 총 확률의 합이 1이 되어야 합니다.
0 ≤ p(x) ≤ 1
베르누이 분포 (bernoulli distribution)
광고를 보여줄 때 클릭할 확률로 예시를 들어보겠습니다.
X는 {0, 1} 이항의 확률 변수이고, θ는 광고가 클릭될 확률입니다.
이 X는 베르누이 분포를 갖는다고 말하고, 아래와 같이 써집니다.
베르누이 분포
베타 분포 (beta distribution)
베타 분포는 [0, 1] 구간을 지원합니다. 그리고 아래와 같이 정의합니다. 베타 분포는 두 개의 양수의 변수로 표현할 수 있는 확률 분포입니다. 오늘 배울 톰슨 샘플링을 구현하기 위해 활용할 핵심 개념입니다.
베타 분포
알파와 베타 값에 따른 베타 분포 출처: 위키피디아 베타 함수 (beta function)
해석학에서, 베타 함수는 감마 함수의 비로 나타내어지는 2변수 특수함수입니다.
베타 함수의 정의
감마 함수를 활용한 베타 함수 정의감마 함수 (gamma function)
Factorial 함수는 오로지 자연수만을 정의역으로 가지는 함수입니다. 그 뒤 수학자들이 계승 함수의 정의역을 복소수 체계로 확장해서 새로운 함수를 만든 게 이를 감마 함수라고 부릅니다.
자연수만을 위한 Factorial을 복소수 체계로 확장한 감마 함수
감마 함수저번 포스팅에서는 멀티 암드 밴딧(MAB)을 다루었습니다. MAB에 대한 개념과 e-greedy, UCB(Upper Confidence Bound) 알고리즘을 이해해보았습니다. 밴딧 문제를 해결하는 방법 중에서 많이 활용되고 있는 또 다른 알고리즘인 톰슨 샘플링(Thompson Sampling)에 대해 공부해보겠습니다.
e-greedy, UCB, Thompson Sampling은 모두 베이지안 최적화(Bayesian Optimization) 기법에 속합니다. 예전에 베이지안 추론에서 이야기했던 컨셉이 그대로 들어있습니다. 오늘 다루어볼 톰슨 샘플링 안에는 사전 확률과 사후 확률의 개념이 있습니다.
광고 시스템에서의 톰슨 샘플링 예시
이번에는 슬롯머신의 예시를 사용하지 않고 광고 시스템을 예로 들어보도록 하겠습니다. 실제 인터넷 기업들이 이러한 밴딧 문제를 활용하는 방식대로 설명해보겠습니다.
우리에게는 유저들에게 노출하고 싶은 3개의 배너가 있습니다. 그리고, 우리는 각 배너를 사용자들에게 보여줬을 때, 이 배너를 클릭할 확률을 알고 싶습니다.
배너1
배너2
배너3톰슨 샘플링은 베타 분포를 활용합니다.
톰슨 샘플링은 배너를 클릭할 확률을 베타 분포로 표현을 했습니다.
어떻게 배너를 클릭할 확률을 베타 분포로 표현할 수 있을까요? 우리에게 필요한 숫자는 두가지입니다. 하나는 배너를 보고 클릭한 횟수, 그리고 배너를 보고 클릭하지 않은 횟수입니다.
놀랍게도 이 두가지 숫자만 있으면, 베타 분포를 그릴 수 있습니다.
Beta(배너를 클릭한 횟수 + 1, 배너를 클릭하지 않은 횟수 + 1)
예를 들어서 그려보겠습니다.
Step1: 아무 데이터가 없는 초기 상태
우선, 배너를 클릭한 횟수 = 0, 배너를 클릭하지 않은 횟수 = 0
최초 사전확률Step2: 배너1: 노출후 클릭, 배너2: 노출후 클릭 안함, 배너3: 노출 안함
일단 데이터가 좀 쌓일때까진 랜덤으로 노출해보겠습니다.
banner1: Beta(2, 1)
banner2: Beta(1, 2)
banner3: Beta(1, 1)
3가지 배너 중 배너1과 배너2를 광고로 내보냈습니다.
배너1을 클릭이 되었고,
배너2는 클릭이 안되었습니다.
그리고 배너3은 아직 노출은 안했기에 원래 초기 분포를 유지하고 있습니다.
Step3: 배너1: 노출 후 클릭 안함, 배너2: 노출후 클릭 안함, 배너3: 노출후 클릭함
banner1: Beta(2, 2)
banner2: Beta(1, 3)
banner3: Beta(2, 1)
Step4: 배너1: 노출 후 클릭함, 배너2: 노출후 클릭함, 배너3: 노출후 클릭안함
오 이제 뭔가 분포가 이쁘게 나옵니다. 지금까지는 랜덤으로 노출했습니다. 그리고 각 배너의 반응률을 베타 분포에 반영해서 그래프를 그렸습니다.
banner1: Beta(3, 2)
banner2: Beta(2, 3)
banner3: Beta(2, 2)
이 상태에서 최고의 배너는 무엇인가요? 바로 배너1이죠. 그렇다면, 앞으로는 무조건 배너1만 사용하는 게 답일까요? 아닙니다. 저번 멀티암드밴딧(MAB) 글에서도 소개했듯이, 우리에겐 여전히 탐험이 필요합니다.
멀티암드밴딧에서는 각 배너의 클릭율을 어떻게 계산했을까요?
banner1: 2번 성공 / 3번 시도 = 66%
banner2: 1번 성공 / 3번 시도 = 33%
banner3: 1번 성공 / 2번 시도 = 50%
greedy 알고리즘: 경험상 가장 성능이 좋았던 선택지만을 활용하기 때문에 banner1을 선택합니다.
e-greedy 알고리즘: 확률적으로 경험상 가장 성능이 좋았던 선택지만을 활용하기 때문에 banner1을 선택하거나 랜덤 선택지를 선택합니다.
저번 글을 읽으셨다면 여기까지는 이해하셨을 겁니다. 그렇다면 톰슨 샘플링은 어떻게 선택을 할까요?
이런 3가지 분포가 있을 때 우선 톰슨 샘플링에서는 3개의 분포에서 임의의 점을 샘플링해보겠습니다.
베타 분포에서 샘플링한다.
3개 배너의 베타 분포에서 그래프 하단의 밑 면의 넓이는 모두 1입니다.
특정 x값에 해당하는 분포의 y값이 클 수록 발생할 확률이 높다는 의미입니다.
각 베타 분포의 밑면 안에서 임의의 점을 하나 고른다고 했을 때, 그 점의 x값을 뽑아내는 것을 샘플링이라고 합니다. 아래 그래프에서 보시면, 맨 밑에 각 베타 분포에서 샘플링한 3개 값에 x마크를 찍어두었습니다.
banner1 샘플: [ 0.38695794]
banner2 샘플: [ 0.43873433]
banner3 샘플: [ 0.61692633]
샘플된 값에서 가장 큰 값을 나타낸 선택지를 선택한다.
보시면, 놀랍게도 배너1의 샘플값이 가장 작습니다. 그리고, 파란색 배너3의 샘플값이 가장 높습니다. 이렇게 추출된 샘플값에서 가장 큰 값이 나온 배너를 선택하겠습니다. 바로 배너3이 당첨되었네요.
이렇게 샘플된 값에서 가장 큰 값을 선택하는 것을 argmax() 한다고 하죠.
배너3Step5: 배너1: 노출안함 배너2: 노출안함 배너3: 노출후 클릭
그리고 배너3을 노출했더니 유저가 클릭을 했습니다! 그럼 이제 배너3과 배너1이 동점이 되겠군요-
banner1: Beta(3, 2)
banner2: Beta(2, 3)
banner3: Beta(3, 2)
배너1 배너3 그래프가 겹쳐서, 보라색이 되었네요.
banner1: [ 0.8606323]
banner2: [ 0.07932551]
banner3: [ 0.43033056]
이번에는 샘플된 값을 보니 배너1이 가장 크네요- 이번에는 배너1을 노출하겠습니다.
배너1Step5: 배너1: 노출후 클릭안함 배너2: 노출안함 배너3: 노출안함
배너1을 노출했는데 클릭을 안했습니다.
banner1: Beta(3, 3)
banner2: Beta(2, 3)
banner3: Beta(3, 2)
banner1: [ 0.66165054]
banner2: [ 0.36745788]
banner3: [ 0.28561718]
이번에도 배너1의 샘플값이 가장 크게 나왔습니다. 배너1을 노출합니다.
Step6: 배너1: 노출후 클릭함 배너2: 노출안함 배너3: 노출안함
banner1: Beta(4, 3)
banner2: Beta(2, 3)
banner3: Beta(3, 2)
banner1: [ 0.42296478]
banner2: [ 0.18102569]
banner3: [ 0.78204765]
이번에는 샘플값이 배너3 파란색이 가장 크네요- 배너3를 노출하겠습니다.
배너2Step7: 배너1: 노출안함 배너2: 노출안함 배너3: 노출후 클릭함
배너2를 노출했는데, 클릭했습니다!
banner1: Beta(4, 3)
banner2: Beta(2, 3)
banner3: Beta(4, 2)
banner1: [ 0.42437534]
banner2: [ 0.48749753]
banner3: [ 0.82210968]
이번에도 배너3 샘플값이 가장 큽니다.
Step8: 배너1: 노출안함 배너2: 노출안함 배너3: 노출후 클릭함
배너3를 노출했는데, 이번에도 클릭했습니다!
banner1: Beta(4, 3)
banner2: Beta(2, 3)
banner3: Beta(5, 2)
이렇게 분포에서 샘플값을 뽑은 후 가장 높은 선택지를 선택한 후 그 데이터를 다시 분포 데이터에 반영합니다.
이렇게 베타 분포를 활용해서 선택을 하고, 데이터를 통해 지속적으로 학습을 합니다.
Stepn: 수 많은 실험을 거친 후
banner1: Beta(33, 100)
banner2: Beta(100, 223)
banner3: Beta(435, 611)
수 많은 실험을 거친 후에는 어떤 배너가 가장 반응이 좋은지가 명확하게 분포에서 표현이 됩니다.
결국은 배너3이 가장 우수하다는 것을 베이지안 추론을 통해 알 수 있게 되었습니다.
배너3알고리즘 수도 코드
위에서 스텝바이스텝 설명했듯이, 확률 분포에서 샘플링 한 후 argmax로 배너를 선택하고 그 결과를 관찰(observe)한 후에 결과를 확률 분포에 반영한다.
베르누이 밴딧에서의 톰슨샘플링 알고리즘
위에서 스텝바이스텝 설명했듯이, 베타 분포에서 샘플링 한 후 argmax로 배너를 선택하고 그 결과를 관찰(observe)한 후에 결과를 베타 분포에 반영한다.
UCB vs Thompson Sampling
우리가 배웠던 UCB랑 Thompson Sampling 중에 뭐가 더 좋을까?
출처: https://www.youtube.com/watch?v=PNHenYiyIYcUCB:
- 결정론적 알고리즘 (예측한 그대로 움직인다)
- 매 라운드마다 업데이트를 해줘야 한다
Thompson Sampling:
- 확률적 알고리즘 (확률적으로 움직인다)
- 늦게 들어오는 피드백을 수용할 수 있다. (회원가입 / 결제 데이터 등도)
- 더 나은 경험적 증거를 보인다
톰슨 샘플링 논문을 보면, 톰슨 샘플링이 UCB보다 좋은 성능을 보인다고 합니다. 아래 결과에서 Regret은 최선의 선택에 비해 잘못된 선택을 함으로 얼마나 손해를 입었는 지를 수치화한 것입니다.
나름 쉽게 설명한다고 해봤습니다. 간단한 알고리즘인데, 최고의 추천시스템을 갖고있다고 알려진 넷플릭스에서도 최근에 톰슨 샘플링을 활용 중이라고 합니다. (Netflix Tech Blog)
베타 분포 그래프 그렸던 Python 코드는 여깄습니다~
https://github.com/chris-chris/bandits-baseline/blob/master/beta.py
그래서, Clova AI Research에 오셔서 저랑 같이 강화학습 공부하실 분을 찾습니다.
AI 엔지니어, 데이터 엔지니어, 프론트 백엔드 엔지니어
추천해드릴게요~ 메일 주세요~ :)
chris.ai@navercorp.com
http://recruit.navercorp.com/naver/job/detail/developer/?annoId=20000597&classId&jobId
References:
http://sanghyukchun.github.io/96/
https://www.youtube.com/watch?v=PNHenYiyIYc
블랭핑크 이미지(취향입니다 존중해주시죠)
