[Recommender System] - 추천시스템과 MAB (Multi-Armed Bandits)

 

 

 

1. Multi-Armed Bandit

 

 

어떤 슬롯머신을 당길지를 최적화하는 MAB

 

 

MAB에서 가장 중요한 개념은 Exploration & Exploitation이다. 여러 개의 슬롯머신 중, 어떤 슬롯머신을 당겨야 이득을 최대화할 수 있는지를 파악하는 것을 탐색/획득으로 알아내기 때문이다. 그래서 탐색과 활용이 조화롭게 필요한 추천시스템에서 많이 활용되는 방식이다. 이미 수 년 전부터 추천시스템에서는 대세로 자리잡았다. A/B 테스트의 완벽한 상위호환이라고 볼 수 있기 때문이다. (모델 단위가 아닌 아이템 단위의 MAB는 모델의 대체재이기도 하다.)

 

MAB의 구성 원리는 앞서 말한 것 처럼 두 가지, 탐색과 활용이다. 그 중 추천시스템에서의 Exploration은 Diversity를 올려줄 수 있는 방법 중 하나이다. Cold-start 문제를 겪을 것이 예상되는 신규 아이템이나 사용자 피드백이 적은 아이템의 경우, 바로 이 Exploration 과정을 통해 사용자의 피드백을 수집할 수 있다. 반대로 Exploitation은 추천시스템의 랭킹 모델처럼, 이미 데이터를 통해 학습이 되어있거나 잠재적인 확률이 높은 콘텐츠를 위주로 추천을 제공한다. 따라서 Exploration과 Exploitation을 적절하게 활용하면, 장기적으로는 최종적인 추천시스템의 Metric이 개선될 수 있다.

 

일반적으로 MAB에서 사용되는 용어들은 다음과 같다. 

 

 

 

 

---

 

2. e(epsilon)-greedy

 

 

이제 MAB의 메커니즘을 이해해보자. 가장 기본적인 방법으로는 greedy하게 모든 슬롯머신(추천시스템에서는 A/B/C...)을 한 번씩 사용해본 뒤 가장 보상이 높았던 슬롯머신에 올인하는 방법을 생각해볼 수 있다. 그리고 이것을 단순한 greedy 전략이라고 한다. 아래와 같은 간단한 수식으로 표현할 수 있다.

 

 

 

 

그러나 이 방법은 Exploration에 대한 고려가 덜 되어있다고 할 수 있다. 특정 기간동안 일어난 행위와 보상을 greedy하게 한 번만 고려했기 때문이다. 그래서 조금 더 나은 epsilon-greedy 라는 방법을 통해, 확률적으로 greedy한 행동과 random한 행동을 조화롭게 선택한다. greedy한 행동을 선택(Exploitation)하는 것은 1-엡실론의 확률, 그리고 random한 행동은 앱실론만큼의 확률로 선택(Exploration)한다. 즉 1-앱실론의 확률로는 Best Case를 선택하는 것이고, 엡실론 확률로는 Diversity를 고려하여 선택한다고 볼 수 있다.

 

하지만 이 방법 역시 단점을 가지고 있는데, 앱실론의 값에 따라 전체 케이스들 중에서 충분한 관측이 부족할 수가 있다는 것이다. 또한 최적의 케이스를 찾아도 지속적으로 앱실론 만큼의 비율을 랜덤으로 사용해야하기 때문에 최적화의 관점에서는 아쉬운 결과를 낼 수 있다. 랜덤보다는 좋은 것을 찾아야 한다.

 

---

 

 

3. UCB(Upper Confidence Bound)

 

 

e-greedy 알고리즘은 다소 휴리스틱한 기준으로 보상과 행동을 선택하는 방법이다. 하지만 실제 추천시스템은 매 시간마다 최적의 선택이 바뀔 수 있다. 가령, 비 오는날의 배달 추천은 파전이나 국물 종류가 최적이 될 것이고, 조두순이 출소한 날 유튜브의 추천은 참교육 영상이 최적의 추천이 될 수 있기 때문이다. 이 문제점은 관측 횟수가 적을수록, 즉 추천시스템의 업데이트가 느려질수록 더 심해진다.

 

UCB는 이러한 문제를 해결하기 위한 방법으로, 매 시간 t마다 과거의 관측 결과와 몇 가지 확률들을 종합하여 최적이 될 수 있는 가능성을 수치로 계산하여 다음 행동을 선택하게 된다.

 

 

 

 

위 식에서 N_t(a)는 현재 시간까지 Case a가 선택된 횟수를 의미한다. 그리고 t는 모든 슬롯머신들이 선택된 횟수의 합이다. 따라서 파라미터 c는 탐색의 정도, 즉 Diversity에 대한 파라미터라고 볼 수 있다. argmax 내의 오른쪽 항의 역할은 탐색의 정도를 나타내는 것이고, c가 크면 결국 탐색을 많이 하기 때문이다. e-greedy는 단순히 일정 비율을 랜덤으로 노출시키는 것이었던 반면, UCB는 상대적으로 노출 기회가 없었던 아이템에게 어느정도의 노출 기회를 제공하게 된다.

 

하지만 UCB 역시 라운드마다 계속해서 파라미터를 갱신해야 하며, 이는 모든 아이템에 대한 reward를 알아야 한다는 단점을 의미한다. 결과적으로 e-greedy와 기본적인 알고리즘 뼈대(확실한 보상과 우연성 사이의 줄다리기)는 같다고 볼 수 있다.

 

 

---

 

 

4. Thompson Sampling

 

 

톰슨 샘플링은 Case에 대한 기대 보상, 즉 가치를 직접 추정하는 대신에 가치의 분포(베타 분포를 사용)를 추정한다. 확률적으로 Case에 대한 기대 보상을 PDF로 만든 것이라고 할 수 있다. 그리고 이를 통해, 다음 Case를 선택(추천시스템에서는 Item Exposure)할때는 이 분포로부터 가치를 무작위로 추출하여 이 중 가장 높은 하나를 선택하게 된다. 그리고 그 보상으로부터 가치의 분포를 업데이트하는 작업을 반복적으로 수행한다.

 

Thompson Sampling은 크게는 강화학습의 한 줄기로 볼 수 있는 MAB 개념을 토대로 하고, 여기에 Bayesian 개념까지 들어가기 때문에, 처음에는 진입장벽이 높게 느껴지는 개념일 수 있으나 실제로는 아주 간단한 알고리즘이다. 간단하게 요약하면 베타 분포를 사용하는 pdf를 만들고, 이를 토대로 샘플링하여 얻은 RF(Relevance Feedback)를 활용해 두 개의 파라미터를 업데이트 해준다는 것.

 

이제 이 샘플링 기법에 베타 분포가 사용되는 원리를 직관적으로 짚고 넘어간 후에, Thompson Sampling 기반의 MAB가 동작하는 방법을 코드로 간단히 살펴보도록 하겠다.

 

 

 

1) Beta Distribution

 

MAB를 통해 하려는 것이 전환율, 즉 CTR(Click-Through Rate)을 높이기 위한 것이라고 가정해보자. greedy한 방법으로 서비스되는 MAB는 통계적으로 보았을 때, 이는 단순히 '표본'만을 가지고 노출될 아이템을 결정하는 것이다. 어떤 아이템이 몇 번 노출되었고, 몇 번 클릭되었는지에 대한 표본이 바로 그것이다. 하지만 단순한 표본만으로는 모집단을 표현할 수 없다. 그래서 이를 조금 더 '통계적'으로 올바른 방향으로 생각하기 위한 시도가 바로 CTR의 분포를 베이지안 관점에서 보는 것이다. 그리고 이는 베타분포라는 사전 분포를 가정하게 된다. 여기에서 의문이 생길 것이다. 왜? 베타분포를 사전 분포로 가정하는가?

 

이는 MAB가 풀고자 하는 문제(CTR: impression, click)가 이항 분포를 띠고 있기 때문이다. 결국 CTR이라는 것은 아이템이 클릭이 되느냐 안 되느냐를 가지고 노는 것이고, 이는 필연적으로 0~1 사이의 확률값으로 표현하게 된다. 따라서 베타분포를 사후확률로 가정한 뒤에 사전분포를 베타분포, 데이터분포를 이항분포인 경우에 사후확률이 베타분포가 된다는 것을 증명하면 되는 것이다. 이 증명에 관한 내용은 링크에 잘 설명되어 있으니 이곳을 참고하자. 이제 우리는 데이터와 문제의 특성을 이용하여, 모집단의 분포를 베이지안 과정으로 추론할 수 있게 된 것이다.

 

 

 

2) Thompson Sampling Process

 

이 내용을 톰슨 샘플링에 써먹는 방법은 아주 간단하다. 베타 분포를 B(a,b) 라고 할 때, 만약 CTR이 해결해야 할 문제라고 한다면 B(아이템의 클릭 수 + 1, 아이템의 노출 수 - 아이템의 클릭 수 + 1)가 우리가 추정해야 할 베타 분포가 된다.

 

다음을 우리가 가진 초기 추천시스템에서 가지고 있는 데이터라고 해보자.

 

- Item 1의 로그 데이터 : 100회 노출, 10번 클릭

- Item 2의 로그 데이터 : 100회 노출, 20번 클릭

- Item 3의 로그 데이터 : 100회 노출, 40번 클릭

 

그리고 이 3개의 아이템을 베타 분포로 표현하면 다음과 같다.

# This code is from the link below
# https://github.com/chris-chris/bandits-baseline/blob/master/beta.py

from scipy.stats import beta
import matplotlib.pyplot as plt
import numpy as np

fig, ax = plt.subplots(1, 1)
x = np.linspace(0, 1, 100)

# item logs
item1 = [10, 100]  # CTR 20%
item2 = [20, 100]  # CTR 20%
item3 = [40, 100]  # CTR 40%

ax.plot(x, beta.pdf(x, item1[0]+1, item1[1]-item1[0]+1), 'r')
ax.plot(x, beta.pdf(x, item2[0]+1, item2[1]-item2[0]+1), 'g')
ax.plot(x, beta.pdf(x, item3[0]+1, item3[1]-item3[0]+1), 'b')

 

여기에서 greedy한 방법으로 MAB를 한다면, 시스템이 노출할 아이템은 3번 아이템이 된다. 하지만 그렇게 판단하는 기준은 단순한 CTR이 되는 것이고, 단순한 CTR을 수집하려면 일정 이상의 트래픽을 반드시 랜덤하게 노출해야만 한다. 그리고 이는 사용자 경험의 손실로 이어진다 (논문에서는 일반적으로 'regret' 으로 표현한다)

 

하지만 우리는 데이터의 모집단 분포를 알고있다고 가정하기 때문에, 다음에 노출할 아이템은 모집단에서 확률적으로 추출할 수 있다. 그래서 위 3개의 분포에서 각각 한 개 씩을 샘플링하여, 샘플링 값이 가장 높은 아이템을 노출하면 된다. 물론 이 과정에서, 아직 분포가 안정적으로 수렴하지 않았기 때문에 실제 CTR이 낮은 아이템이 몇 번 선택될 수 있지만, TS 기반의 MAB는 특정 트래픽을 고정으로 exploration으로 사용하지 않기 때문에 regret의 관점에서 본다면 베이지안 기반의 TS MAB가 트래픽이 늘어날수록 훨씬 효과적이라는 것을 추측해볼 수 있다.

 

Distribution의 Sharpness 변화를 관찰하기 위해, 이 과정을 몇 개의 Step으로 나눠서 실행해보자. 아래의 코드블럭에서 range를 늘려가며 여러 번 수행하면 된다.

 

(단, 아래의 시뮬레이션 코드는 유저가 impression에 반응하여 click 하는 것이 아니라, 산술적인 CTR로 연산되기 때문에 제자리에서 뾰족해지는 분포가 생성될 것이다. 실제 추천시스템에서는 콘텐츠가 좋은 item의 분포가 점점 오른쪽으로 옮겨갈 것이다)

 

for i in range(1000):
    # 베타 분포 기반 샘플링 : 가장 샘플링 값이 큰 item 선택
    item1_rvs = beta.rvs(item_list[0][0]+1, item_list[0][1]-item_list[0][0]+1, size=1)
    item2_rvs = beta.rvs(item_list[1][0]+1, item_list[1][1]-item_list[1][0]+1, size=1)
    item3_rvs = beta.rvs(item_list[2][0]+1, item_list[2][1]-item_list[2][0]+1, size=1)
    rvs_list = [item1_rvs, item2_rvs, item3_rvs]
    max_result_item_index = rvs_list.index(max(rvs_list))

    # 현재까지의 CTR을 확률로 하여 조회 여부를 시뮬레이션
    exposure_item = item_list[max_result_item_index]
    prob_by_ctr = exposure_item[0] / exposure_item[1]
    is_click = random.choices(
        population = [True, False],
        weights = [prob_by_ctr, 1-prob_by_ctr]
    )
    
    # 시뮬레이션 결과에 따라 item status 업데이트
    if is_click[0]:  # click count ++
        item_list[max_result_item_index][0] += 1
    item_list[max_result_item_index][1] += 1  # impression(exposure) count ++
    
print(item_list)

fig, ax = plt.subplots(1, 1)
x = np.linspace(0, 1, 100)

ax.plot(x, beta.pdf(x, item1[0]+1, item1[1]-item1[0]+1), 'r')
ax.plot(x, beta.pdf(x, item2[0]+1, item2[1]-item2[0]+1), 'g')
ax.plot(x, beta.pdf(x, item3[0]+1, item3[1]-item3[0]+1), 'b')

1000번을 수행한 결과

실험 결과를 보면, 수행 횟수가 늘어날수록 자연스럽게 CTR이 낮은 아이템의 트래픽이 감소한다. 그리고 이 과정이 반복되면 item 1은 노출 기회를 얻지 못하게 된다. 하지만 실제 추천시스템에서는 User Context의 영향이 굉장히 중요하기 때문에(Context에 따라 기대 CTR이 달라질 수 있다는 것), item 1이 노출 기회를 아예 얻지 못하는 것은 바람직하지 않다. 따라서 실제 추천시스템에서는 몇 가지 룰을 추가하여 디자인하는 것이 좋겠다.

 

---

 

3) Regret in MAB

 

MAB에는 Loss 대신, Regret 이라는 개념이 있다. 이름에서 짐작할 수 있듯이 ideal한 Reward에 대비하여, 실제 Reward가 얼마나 유실되었는지를 정량적으로 계산하는 지표이다. 일반적인 loss와 같은 역할이지만, ML에서는 최적화의 용도로 사용되는 데 반해 MAB에서는 단순 성능 측정용으로 사용된다(사실 loss의 개념보다는 시뮬레이션의 개념에 더 가깝다고 볼 수 있다). Regret은 아래와 같은 기본적인 formula 형식만 갖추고 있고, 구현이나 사용법이 제각각이라고 한다. (그럼에도 표준 지표 정도는 있는 것 같으니, 링크를 참고하자)

 

이 개념에 대해 약간의 부연설명을 하자면 다음과 같다. MAB problem은 CTR prediction으로 가정하겠다.

 

- ideal reward는 시점 t에서 가장 CTR이 높은 아이템의 CTR로 설정할 수 있음
- expected reward는 시점 t-1 에서 계산된 아이템마다의 기대 CTR이라고 할 수 있음

- 아래와 같은 수도코드로 표현

# pseudocode
regret_in_t = 0
for expected_reward_in_t-1 in arms:
    regret_ratio = ideal_reward_in_t - expected_reward_in_t-1
    regret_in_t += regret_ratio * (arm's expected play count in t, or real play count in t)
normalized_regret_in_t = regret_in_t / (whole play count)

 

 

 

references

- Book : [bandit algorithms for website optimization]

 

- Paper & Materials

[A Batched Multi-Armed Bandit Approach to News Headline Testing]
https://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf

https://arxiv.org/pdf/1209.3353.pdf

https://www.cs.umd.edu/~slivkins/CMSC858G-fall16/Lecture 5.pdf

- Blogs
https://medium.com/analytics-vidhya/multi-armed-bandit-analysis-of-thompson-sampling-algorithm-6375271f40d1
https://www.youtube.com/watch?v=RK3-aNWveMs
https://seing.tistory.com/65
http://sanghyukchun.github.io/96/
https://sumniya.tistory.com/9
https://brunch.co.kr/@chris-song/66
https://velog.io/@gwkoo/%EB%B2%A0%EC%9D%B4%EC%A7%80%EC%95%88-%EC%B6%94%EC%A0%95