[Day38] Bandit for Recommendation 10-2 : MAB 알고리즘 심화 : Thompson Samling, LinUCB

Thompson Sampling

각 action에 대해 reward를 계산할 때 확률 분포를 사용한다. 주어진 k개의 action각각이 베타 분포를 따른다고 가정하고 확률분포를 업데이트한다.

 

베타 분포

두 개의 양의 변수 $\alpha$와 $\beta$로 표현할 수 있는 확률분포이며 0~1사이의 값을 갖는다. 

 

$$Beta(x\mid \alpha, \beta) = \frac{1}{B(\alpha, \beta)}x^{\alpha-1}(1-x)^{\beta-1}$$

B($\alpha, \beta$)는 $\alpha$와 $\beta$에 의해 정해지는 베타함수

 

$\alpha$와 $\beta$값에 따라 확률분포의 모양과 sampling되는 값이 달라진다.

 

예시

각각의 아이템 별 추정치를 계산할 때 어떻게 베타분포를 사용하는지 예시를 들어보자

 

배너	click($\alpha$)	non-click($\beta$)	표본 평균
배너1	3	10	$\frac{3}{3+10}$
배너2	2	4	$\frac{2}{2+4}$
배너3	1	9	$\frac{1}{1+9}$

현재 사용자에게 광고배너를 추천해야 한다. 세 배너 중 어떤 배너를 노출했을 때 가장 많은 클릭을 얻을 수 있을지를 알아낸다. 즉, 가장 많은 클릭=CTR을 이끌어 낼 배너를 선택해줄 policy를 세워야 한다.

 

action의 추정치를 구하기 위해서는 베타 분포가 필요하다. 베타 분포는 $\alpha$와 $\beta$의 값이 필요하다

• $\alpha$
  배너를 보고 클릭한 횟수
• $\beta$
  배너를 보고 클릭하지 않은 횟수

위의 데이터로 각각의 배너에 대해서 베타 분포를 정의할 수 있다.

 

베타 분포에 샘플링했을 때 수렴하게 되는 표본 평균은 $\frac{\alpha}{\alpha + \beta}$로 $\alpha + \beta$가 전체 노출 수를 의미하고 그 중에 얼마나 클릭 되었는지 $\alpha$로 표현된다. 결국 표본 평균은 각 배너의 CTR이 된다.

배너를 클릭할 확률 ~ $Beta(\alpha +1 , \beta + 1)$

배너를 클릭할 확률 자체가 베타 분포를 따르기 때문에 베타 분포에서 샘플링한 값이 최종적으로는 그 배너를 클릭할 확률을 따라간다. 

그리디 알고리즘같은 경우는 여기에서 가장 표본평균이 높은 배너2를 계속 노출하게 될 것이지만 Thompson sampling은 베타 분포를 이용하는 것이다.

 

• Step 1
  아무런 데이터가 없는 최초의 사전 확률 분포
• Step 2
  어느 정도의 기간 동안은 random하게 노출시킨다. 관측값을 수집해서 베타분포를 적절한 수준까지 업데이트 한다. banner1은 노출 후에 클릭되었기 때문에 $\alpha$값이 1 더해져서 업데이트 되고, banner2는 클릭 되지 않았기 때문에 $\beta$값이 1 더해진다. 노출되지 않으면 변화가 되지 않는다.
  
  step2를 어느정도 반복해서 베타분포를 업데이트 한다.
• Step 3
  이제는 더 이상 random하게 노출하지 않고 Thompsom sampling에 policy를 사용한다. 각각의 배너가 가진 베타 분포에서 임의로 sampling한다. 즉 그래프에서 x값은 임의로 정해진 것이다. 그 값 중에 가장 큰 값(argmax)을 내보낸 분포가 banner3의 베타 분포여서 배너3을 노출시킨다. 
  
  업데이트도 계속해서 한다.
• Step 4
  Step 3를 반복하면 true distribution에 가까워지게 된다. 점점 reward가 좋은 분포는 오른쪽으로 이동한다. 수많은 노출을 거치면 베타분포의 파라미터가 어느정도 많이 업데이트되어서 뾰족하게 수렴한다. 더이상 sampling을 해도 평균 CTR이 많이 낮은 banner1이 banner3보다 높게 sampling될 확률은 거의 없다. 계속해서 banner3만 노출될 것이다.

결국 이렇게 분포가 업데이트되는 과정을 따라 자연스럽게 exploration과 exploitation의 trade-off가 적절히 이루어지고, 가장 reward가 높은 아이템이 노출되는 쪽으로 수렴하게 된다.

Require: α, β prior parameters of a Beta distribution # 베타 분포 initialize
Si = 0, Fi = 0, ∀i. {Success and failure counters}
for t = 1, . . . , T do # 매 time step 마다
    for i = 1, . . . , K do # k개의 action에 대해서
        Draw θi according to Beta(Si + α, Fi + β). # 베타 분포를 각각 sampling
    end for
    Draw arm ˆı = arg maxi θi and observe reward r # sampling 된 θi중 가장 큰 sampling값을 가진 action 선택
    if r = 1 then # 클릭이 일어났다면
        Sˆı = Sˆı + 1 # α 를 1 더해서 업데이트
    else # 클릭이 일어나지 않았다면
		Fˆı = Fˆı + 1 # β를 1 더해서 업데이트
	end if
end for

# 출처 : An Empirical Evaluation of Thompson Sampling

 

LinUCB

Contextual Bandit

• Context
  유저나 아이템이 가지고 있는 다른 부가,특성 정보
• Context-free Bandit
  context를 고려하지 않음
  ex) greedy, UCB 알고리즘
  동일한 action에 대해서 유저의 context정보에 관계없이 항상 동일한 reward를 가진다고 가정
  ex) 슬롯 머신은 누가 당긴다고 해도 reward가 다르지 않다.
• Contextual Bandit
  user의 context 정보에 따라서 동일한 action을 수행했어도 다른 reward를 가질 수 있다고 가정
  ex) 동일한 스포츠 기사를 봐도 나이나 성별에 따라 클릭 성향이 달라짐
  개인화 추천과도 연관이 있다.

LinUCB with Disjoint Linear Models

action을 선택하기 위한 policy는 밑의 수식을 따른다

$$A_t\doteq  \underset{a}{\operatorname{\arg\max}}\left[ x_{t,a}^T\theta_a^* + \alpha\sqrt{x_{t,a}^TA_a^{-1}x_{t,a}}\right], \quad \text{where} A_a=D_a^TD_a+I_d$$

• $x_{t,a}$
  d-차원 context vector
  유저와 context에 대한 feature
  선택되는 action에 대한 정보도 있다
  ex)성별, 연령, 노출되는 시간적 정보, 공간적 정보
• $\theta^*_a$
  action별로 가지는 파라미터
  d-차원의 학습 파라미터이다. 계속 업데이트하며 모델이 정교해진다.
• $D_a$
  각 action별로 이미 관측된 학습 데이터가 담긴 data matrix
  현재 time step을 기준으로 총 m개의 action data가 수집되었다면 m x d로 이루어진 행렬이 될 것이다. 
• $x_{t,a}^T\theta_a^*$
  expected reward
  주어진 context 상황에서 action a 를 선택했을 때 얻게되는 reward
• $\alpha\sqrt{x_{t,a}^TA_a^{-1}x_{t,a}}$
  action a에 대한 exploration을 추가해준다.
  시간이 지남에 따라 학습데이터가 많아지면 exploration term은 점점 작아진다. 그러면 expected reward에 수렴하며 expected reward가 가장 높은 action을 선택하는 쪽으로 exploitation이 진행된다.

 

예시

3명의 user가 있고, 유저마다 각각 다른 context vector(4차원)를 가진다. 각 context vector가 male, female, young, old로 이루어져있다고 하면 첫번째 유저의 context vector $x_t=[1,0,0,1]^T$가 될 것이다. 유저들이 어떤 아이템을 선택하느냐가 MAB문제에서 추천이 되는 방식이다. 각각의 액션 $\theta_1^*$,,, 에 대해서 파라미터를 학습해야 한다. 

 

맨 위의 스파게티를 선택하는 action에 해당하는 데이터는 총 2명(유저2,3)에게 수집되었기 때문에 스파게티에 대한 데이터 행렬이 $D_1= [[0,1,1,0],[0,1,0,1]]$와 같이 업데이트 될 것이다.

 

최종적으로 context vector와 같은 차원의 action에 대한 학습 파라미터가 $\theta_1^*=[0.0,0.7,0.2,0.1]^T$와 같이 업데이트 되게 될 것이다. $\theta_1^*$에서 두 번째 차원인 female에 대해서 가장 높은 weight를 가진다. 즉 스파게티는 female이 선호하는 action이라는 것이다.

 

이렇게 각각의 유저의 context vector에 따라 어떤 아이템이 더 높은 reward를 줄 지, 즉 어떤 아이템이 CTR이 높을지를 예측하게 된다. 

 

A Contextual-Bandit Approach to Personalized News Article Recommendation

1: 매번 time step 마다

9: $p_{t,a}$값을 구하고

11: argmax를 취해서 $p_{t,a}$값중 가장 큰 값에 해당하는 action이 선택해서 노출하고 그로 인해 얻게 되는 reward $r_t$를 가지고 

12,13: $A_{a_t}$, $b_{a_t}$를 업데이트 한다.  $A_{a_t}$, $b_{a_t}$는 우리가 학습해야할 $\theta$를 업데이트하는데 사용된다.

 

Contextual Bandit 예시 : Naver AiRs

NaverDEVIEW 2020 [뭐볼까? : 네이버AiRS인공지능콘텐츠추천의진화]

bandit의 action 하나하나가 아이템이 된다. 실제 추천 시스템에서는 아이템이 너무 많은 경우에는 각 아이템 별로 bandit의 파라미터가 학습되기 어렵다.

그래서 먼저 인기도 기반 필터링을 통해서 탐색해야하는 후보아이템 리스트를 수천개로 줄인 다음에 수천개의 아이템에 대해서만 contextual bandit 알고리즘을 사용해서 최종적으로 유저의 취향에 맞는 추천을 제공했다.