Multi Armed Bandit 의 Epsilon Greedy, Tompson Sampling 파이썬으로 구현하기

오늘은 추천 알고리즘을 공부하면 많이 듣게 되는 기초, Multi Armed Bandit (MAB)에 대해서 알아보자. 그 중 Epsilon Greedy와 Tompson Sampling에 대해서 설명해보겠다. 

 

---

0. 기본 지식

exploration

이름 그대로 탐험을 의미한다. 추천할 때 새로운 아이템을 추천하는 등, 학습에 fitting되지 않는 미지의 영역을 새롭게 보여주는 개념으로 이해할 수 있다. 

 

아직 클릭이 적은 아이템이나, 기존 로직에 반영하지 않은 fresh 아이템을 노출하는 것이 여기에 해당한다. 그렇기에 매일 유저에게 비슷한 결의 아이템이 추천되는 것을 방지할 수 있다. 단, 당장의 reward는 낮을 수밖에 없다. 

 

 

 

exploitation 

데이터를 기반으로 해서 추천을 해주는 영역이다. 이미 쌓인 데이터 기반으로 확실한 reward를 보장할 수 있다. 

 

추천에서는 이 exploration과 exploitation의 균형을 잘 잡는 것이 중요하다.

 

MAB

여러개의 arm bandit 중 하나를 선택한다는 의미의 Multi Arm Bandit이다. 카지노 슬롯 머신을 생각하면 쉽다. 추천에서는 여러개의 액션(ex. 추천할 수 있는 아이템) 중 하나에 해당하는 슬롯 레버 Arm을 선택한다고 상상해보자. 

 

 

prior, posterior, likelihood

이전 포스트에서 다룬 적 있으나, 구글에서 글 안에 글 링크를 달면 싫어하는 것 같다. 자세한 건 내 블로그의 다른 글을 참고해주시면 된다. 

오늘 설명할 버전으로 기술하면 아래와 같다. 

• θ
  • 이 arm을 선택할 확률 
• prior: P(θ)
  • beta distribution 
• posterior : P(θ|D)
  • 업데이트된 성공 확률 분포 
• likelihood : P(D|θ)
  • 이 arm의 reward가 1또는 0

 

beta distribution

beta distribution은 다음과 같은 확률분포를 띈다.

참고) beta distribution

 

여기서 MAB에 중요한 개념은 어떻게 beta distribution이 업데이트 되는지다. conjucate prior라고 가정했을 때,

posterior는

P(θ∣D) = k∼Beta(α+k,β+n−k)

 

이 된다. 즉, k가 "성공"일 때 알파값은 α +=k , 베타값은 β -=k 와 같이 업데이트 된다. 

 

 

1. epsilon greedy 

강화학습에서 나오는 개념이다. 지금까지의 가장 reward가 높은 아이템을 exploitation을 하지만, 일정한 비율 입실론(ε)에 대해서는 탐험 exploration을 한다.  

 

파이썬으로 간단하게 예시를 작성해볼 수 있다. 만약 0.3의 확률은 새로운 아이템을 '탐험' 시키고, 그렇지 않으면 reward가 가장 높은 아이템을 추천으로 선택하는 epsilon greedy 함수를 작성해보자. 

 

import numpy as np

# 먼저 유저에게 해당 아이템이 추천됐을 때 기대되는 reward를 얻는다. 
user_action_reward = [0, 0, 0.3 ,0.7, 1.0] #1명의 유저, 5개의 아이템에 대한 reward 


# epsilon greedy function 
def epsilon_greedy(rewards, epsilon = 0.3):
  if np.random.rand() < epsilon:
        # 랜덤하게 eps 확률에는 랜덤하게 데이터가 나간다. 
        choosen_idx = np.random.randint(len(rewards))
  else:
        # Exploit: choose the action with the highest Q-value
        choosen_idx = np.argmax(rewards)
  expected_reward = rewards[choosen_idx]
  return choosen_idx, expected_reward
  
epsilon_greedy(user_action_reward)

 

이론상 10번 중 3번은 가장 높은 1.0에 해당하는 index 4가 아닌 다른 아이템이 return된다. 

 

 

2. Tompson Sampling

epsilon-greedy가 일정한 확률대로 새로운 아이템을 return한다면, tompson sampling은 그 확률을 베이지안 (baysian) 에 기반한다. 그리고이 arm이 성공적인가 아닌가를 1 또는 0  으로 본다. 

 

posterior가 baysian이면 보통 conjucate (prior와 posterior가 유사한 확률분포를 따른다고 가정) prior는 beta distribution을 따른다. 

 

P(θ)가 beta-distribution일 때, baysian을 이용해서 학습한 arm bandit 알고리즘을 tompson sampling이라 할 수 있겠다. (실은 다른 conjucate prior를 사용해도 무방하다. 여기선 "보통" 자주 쓰이는 beta - baysian conjucate를 예시로 설명한다.)

 

베이시안에 따라 posterior는 다음과 같이

• Beta(α + 성공횟수, β + 실패횟수)

로 확률이 업데이트가 된다. 데이터 학습이 진행될수록 distribution의 파라미터인 α 값이 커지면서 탐험(exploration)보다 exploitation의 확률이 더 올라간다. 

 

gpt가 그려준 도식. 뭔가 어설픈데 맞긴함!

 

 

이제 파이썬으로 구현해보자. 이번에도 각 아이템이 추천됐을 때의 reward를 데이터로 삼는다. 

 

먼저 arm을 선택하는 확률이다. 이는 계속 언급했듯이 prior 로 beta distribution 기반이다.

def select_arm(self):
        # 각 arm의 성공확률 θ 
        # P(θ) beta distribution 구하는 방법: np.random.beta(self.alphas[i], self.betas[i])
        samples = [np.random.beta(self.alphas[i], self.betas[i]) for i in range(self.num_arms)]
        return np.argmax(samples)

 

 

다음은 알파와 베타를 업데이트 해야한다. posterior는 해당 값에 성공 여부를 더해주면 된다. 

def update(self, chosen_arm, reward):
        #여기가 baysian. 
        # P(θ|a)는 likelihood. reward가 success threshold보다 큰지 아닌지 binary. 
        # P(θ)는 beta-distribution. 
        # P(a|θ)는 업데이트된 성공 확률 분포. (posterior) 
        if reward[chosen_arm] >= self.success_ths: 
            self.alphas[chosen_arm] += 1
        else:
            self.betas[chosen_arm] += 1

 

 

이제 코드를 합쳐보자. 

import numpy as np

class ThompsonSampler:
    def __init__(self, num_arms, success_ths): #num_arms: 현재 아이템 갯수 
        self.num_arms = num_arms
        self.alphas = np.ones(num_arms)  # successes
        self.betas = np.ones(num_arms)   # failures
        self.success_ths = success_ths

    def select_arm(self):
        # 각 arm의 확률 θ 
        # θ beta distribution 구하는 방법: np.random.beta(self.alphas[i], self.betas[i]) 
        samples = [np.random.beta(self.alphas[i], self.betas[i]) for i in range(self.num_arms)]
        return np.argmax(samples)

    def update(self, chosen_arm, reward):
        #여기가 baysian. 
        # P(θ|a)는 reward가 success threshold보다 큰지 아닌지 binary. 
        # P(θ)는 beta-distribution. 
        # P(a|θ)는 이 arm을 선택할 확률임. 
        if reward[chosen_arm] >= self.success_ths: 
            self.alphas[chosen_arm] += 1
        else:
            self.betas[chosen_arm] += 1

n_arms = 5 # 5개의 아이템으로 간주
success_ths = 0.7 # 추천 성공으로 간주하는 reward의 threshold 
smp = ThompsonSampler(n_arms, success_ths) 

trial = smp.select_arm()
print(f'current selected item idx: {trial}')
smp.update(trial, user_action_reward)
print(f'current alpha, beta distribution: {smp.alphas, smp.betas}')
## current selected item idx: 4
## current alpha, beta distribution: (array([1., 1., 1., 1., 2.]), array([1., 1., 1., 1., 1.]))

 

 

이를 계속해서 시도하면 높은 reward를 가진 arm에 따라 distribution도 수렴하는 것이다.