[K-Data x 러닝스푼즈] 4-3. Multi-Armed Bandit (MAB)의 여러가지 방법

2022.02.17 - [머신러닝 | 딥러닝/추천시스템] - [K-Data x 러닝스푼즈] 4-3. Multi-Armed Bandit (MAB)

[K-Data x 러닝스푼즈] 4-3. Multi-Armed Bandit (MAB)

저번 포스팅에서 MAB의 기본적인 원리에 대해 공부해보았습니다!

이번 글에서는 MAB의 4가지 방법에 대해 소개해보려고 합니다!!

 

1. Simple Average Method (greedy algorithm) --기본적인 방법

2. epsilon-greedy algorithm --베이스라인으로 많이 사용

3. UCB (Upper Confidence Bound)

4. Thompson Sampling

---

① Simple Average Method (greedy algorithm)

 

: 가장 쉬운 방법 : 다 당겨보고 평균 값을 사용

표본 평균을 사용함!

 

* 문제 : 처음에 선택되는 action과 reward에 policy가 크게 영향을 받음! exploration(탐험)이 부족하다..

---

② epsilon-greedy algorithm

 

exploration(탐험)이 부족한 greedy algorithm의 policy를 수정한 전략

 

- 일정한 확률에 의해 랜덤으로 슬롯머신을 선택하도록 함

: 동전을 던져 앞면이 나오면 greedy(제일 높은거), 뒷면이 나오면 랜덤 선택(아무거나 선택). epsilon=0.1/0.2

- epsion-greedy는 심플하면서도 강력한 알고리즘 -> 이거보다 못하면 그 MAB 알고리즘은 잘못짠 것

- 보통 실무에서도 MAB를 처음 시작할 때 epsion-greedy와 많이 비교를 함!

---

③ UCB (Upper Confidence Bound)

 

epsilon-greedy algorithm보다 더 발전한 방법인 UCB

---

④ Thompson Sampling

 

: 주어진 k개의 action에 해당하는 확률분포를 구하는 문제

-> 앞의 세가지 방법에서 확률분포를 가정하지 않음. 단 이 action을 골랐을 때 reward를 주냐 주지않냐..! 이정도(?)

 

action a에 해당하는 reward 추정치가 확률분포를 따른다고 가정! => 베타분포

 

<베타분포>

:두개의 양의 변수로 표현할 수 있는 확률분포이며 0과 1사이의 값을 갖는다

분포를 결정하는 파라미터 알파, 베타

 

* Thompson Sampling 예시

• 사용자에게 보여줄 수 있는 광고 배너가 있다고 가정
• 베타 분포에 필요한 데이터는 2가지 

=> 배너를 보고 클릭한 횟수(α)

=> 배너를 보고 클릭하지 않은 횟수(β)

 

• 배너를 클릭할 확률(Reward를 얻을 확률) :

0이 되버릴 수도 있으니까 smoothing

 

Step1) 데이터가 없는 초기상태

* 추천할 아이템이 3개가 있다고 가정

banner1 ~Beta(1,1)

banner2 ~Beta(1,1)

banner3 ~Beta(1,1)

-> 최초의 사전확률 분포

Step2) 랜덤하게 100회 정도 노출

노출 후 클릭 -&gt; 앞에 &alpha;+1 / 노출 후 클릭x -&gt; 뒤에 &beta;+1

Step3) 베타 분포(확률분포)에서 샘플링하여 노출

banner3를 노출했을 때 클릭이 이루어지지 않았다면 그에 맞춰 베타 분포 업데이트!

banner1 ~ Beta(3,2)

banner2 ~ Beta(2,3)

banner3 ~ Beta(2,3) -> 노출 후 클릭x

=> 실시간 업데이트(계산도 간단!)

 

베타분포 업데이트 후 다시 샘플링!

=> 가장 높은 확률이 샘플링된 banner1 노출

베타분포 업데이트

banner1 ~ Beta(3,3) -> 노출 후 클릭x

banner2 ~ Beta(2,3)

banner3 ~ Beta(3,2)

 

베타분포 업데이트 후 다시 샘플링

=> 가장 높은 확률이 샘플링된 banner1 노출

베타분포 업데이트

banner1 ~ Beta(4,3) -> 노출 후 클릭

banner2 ~ Beta(2,3)

banner3 ~ Beta(3,2)

 

베타분포 업데이트 후 다시 샘플링!

=> 가장 높은 확률이 샘플링된 banner3 노출

베타분포 업데이트

banner1 ~ Beta(4,3) 

banner2 ~ Beta(2,3)

banner3 ~ Beta(4,2)-> 노출 후 클릭

 

베타분포 업데이트 후 다시 샘플링!

=> 가장 높은 확률이 샘플링된 banner3 노출

베타분포 업데이트

banner1 ~ Beta(4,3) 

banner2 ~ Beta(2,3)

banner3 ~ Beta(5,2)-> 노출 후 클릭

 

베타분포 업데이트 후 다시 샘플링!

오른쪽으로 치우쳐져있는게 더 확률이 높음 / 기대값이 낮은 애는 덜 exploration(탐험), but 샘플링이므로 확률이 존재하긴 하니까..!

=> 가장 높은 확률이 샘플링된 banner3 노출

 

Step4) 수많은 노출을 거친 후 CTR이 가장 높은 배너를 선택(?)

banner1 ~ Beta(33,100)

banner2 ~ Beta(100, 223)

banner3 ~ Beta(435, 611)

베타분포가 뾰족하게 수렴

=> 실험 결과 banner3이 가장 reward(CTR)이 높다!

---

MAB를 추천에 활용하는 방법

 

그렇다면 MAB 알고리즘을 추천에 어떻게 활용할까?

 

• 우리가 추천하는 개별 아이템(=슬롯머신 하나라고 생각)은 개별 action에 해당함
• 유저에게 아이템을 추천하는 방식이 MAB알고리즘의 policy
• 아이템을 추천했을 때 사용자의 클릭/구매 여부를 reward로 측정

* 단, 기본적인 MAB 알고리즘만 사용할 경우 개인화 추천은 어려움

 

개인 유저에 대해서 모든 아이템을 구하는 것은 불가능하므로..!

(개인별로 구축하기에는 데이터가 부족)

=> 클러스터링을 통해 비슷한 유저끼리 미리 그룹핑을 한뒤에

클러스터 별로 인기있는 아이템 후보 리스트를 생성한다!

 

이 이후에 해당 유저의 그룹에서 MAB를 통한 추천을 진행!

---

끝!