탐험과 활용의 균형을 맞추기 위한 알고리즘, 톰슨샘플링

톰슨 샘플링이란?

• 톰슨 샘플링(Thompson Sampling)은 멀티 암드 밴딧 문제(Multi-Armed Bandit Problem)에서 사용되는 확률론적 알고리즘으로, 다양한 선택지(예: 광고, 제품 추천) 중에서 가장 효율적인 선택지를 반복적으로 탐색하는 방법입니다
• 이는 탐험(Exploration)과 활용(Exploitation)의 균형을 잘 맞추기 위한 기법으로, 각 선택지의 성공 확률을 베이지안 방법론을 통해 갱신하면서 최적의 선택을 수행합니다.

Motivation

• 기존의 Greedy 알고리즘이나 Epsilon-Greedy 같은 기법은 선택지 중 성공 가능성이 높은 팔을 우선적으로 탐색하거나 무작위로 탐색하는 방식입니다. 하지만 이 방식은 탐험과 활용 간의 균형을 제대로 맞추지 못하는 단점이 있습니다. 이 문제를 해결하기 위해 톰슨 샘플링이 등장했습니다.
• 톰슨 샘플링은 각 선택지의 성공 확률에 대한 불확실성을 고려하고, 이를 기반으로 확률적으로 선택지를 탐색하면서 점차적으로 성공 확률이 높은 선택지를 집중적으로 활용하게끔 설계되었습니다.

Pros & Cons

Pros

• 탐험과 활용의 균형: 톰슨 샘플링은 성공 확률이 낮은 선택지도 탐험할 기회를 제공하므로, 최적의 선택지를 찾는 과정에서 놓치는 선택지를 줄일 수 있습니다.
• 베이지안 업데이트: 톰슨 샘플링은 베이지안 확률론을 사용하여 각 선택지의 성공 확률을 반복적으로 업데이트하며, 데이터가 추가될수록 더 정확한 예측이 가능합니다.
• 다양한 상황에 유연하게 대응: 선택지의 성공률이 동적으로 변하거나 불확실성이 클 때도 톰슨 샘플링은 유연하게 작동합니다.

Cons

• 계산 복잡도: 각 선택지에 대해 베이지안 업데이트를 수행하기 때문에 연산량이 다소 많아질 수 있습니다. 특히 선택지가 많을수록 계산 복잡도가 증가합니다.
• 초기 데이터 부족 시 성능 저하: 탐험과 활용 간 균형을 잡기 위해서는 어느 정도의 초기 데이터가 필요합니다. 초기 데이터가 부족할 경우, 최적의 선택을 찾는 데 더 많은 시간이 소요될 수 있습니다.

Alternative

• Epsilon-Greedy: 일정 확률(ε)로 무작위 탐험을 하고, 나머지 확률로 현재 가장 성능이 좋은 선택지를 활용하는 방법입니다. 단순하면서도 빠르게 동작하지만, 탐험과 활용의 균형이 명확하게 설정되지 않을 수 있습니다.
• Upper Confidence Bound (UCB): 탐험을 제어하기 위해 각 선택지의 상한선을 계산하고, 상한선이 높은 선택지를 선택하는 방법입니다. 톰슨 샘플링보다 계산 복잡도가 낮으나, 동적인 상황에서 성능이 떨어질 수 있습니다.

Code

• 아래코드에서 톰슨샘플링은 성공확률(베타분포)에 기반해서 가장 높은 확률을 가진 Arm을 선택합니다.
• 자연스럽게 시도횟수만큼 누적보장승은 증가하게 되고 이는 시간이 지남에 따라 알고리즘이 성공 확률이 높은 슬롯머신을 더 자주 선택하게 됨을 의미합니다.

import numpy as np
import matplotlib.pyplot as plt

# 각 슬롯머신(팔)의 실제 성공 확률
true_probs = [0.1, 0.3, 0.5]  # 3개의 슬롯머신
n_arms = len(true_probs)
n_trials = 1000  # 시도 횟수

# 베타 분포의 성공 및 실패 횟수 추적
successes = np.zeros(n_arms)
failures = np.zeros(n_arms)

# 결과 추적
rewards = np.zeros(n_trials)

# 톰슨 샘플링 실행
for t in range(n_trials):
    sampled_theta = [np.random.beta(1 + successes[i], 1 + failures[i]) for i in range(n_arms)]
    chosen_arm = np.argmax(sampled_theta)
    
    # 선택한 팔을 당겼을 때의 보상
    reward = np.random.rand() < true_probs[chosen_arm]
    
    # 성공 또는 실패 기록
    if reward:
        successes[chosen_arm] += 1
    else:
        failures[chosen_arm] += 1
    
    rewards[t] = reward

# 누적 보상 그래프
cumulative_rewards = np.cumsum(rewards)
plt.plot(cumulative_rewards)
plt.xlabel('Trials')
plt.ylabel('Cumulative Reward')
plt.title('Thompson Sampling - Cumulative Reward')
plt.show()

A/B 테스트 관련

• A/B 테스트에서는 일반적으로 두 그룹에 대해 동일한 시간 동안 실험을 진행한 후, 결과를 수집하고 분석하여 승자를 결정합니다. 이 과정에서 주로 T-Test나 Chi-Square Test를 사용하여 두 대안의 성능 차이를 평가합니다
• 이에 반해서 톰슨 샘플링을 이용한 A/B 테스트는 실험 도중에도 성공 가능성이 높은 대안을 더 많이 탐색하도록 설계됩니다. 톰슨 샘플링은 베이지안 방식으로 각 대안(A, B)의 성공 확률을 추정한 후, 확률적으로 더 나은 대안을 선택하는 방식입니다. 즉 A/B 테스트에서 효율적이고 실시간적인 의사 결정을 가능하게 합니다.

예시 코드

• 시간이 지남에 따라 B 그룹이 A 그룹보다 성공률이 훨씬 높다는 것을 톰슨 샘플링 알고리즘이 학습하게 됩니다. 그 이후로는 B 그룹을 훨씬 더 자주 선택하게 되며, B 그룹의 누적 성공률이 빠르게 증가하는 것을 볼 수 있습니다.

import numpy as np  
import matplotlib.pyplot as plt  
  
# A/B 테스트에서 두 그룹의 전환율  
true_conversion_A = 0.3  
true_conversion_B = 0.4  
n_trials = 1000  # 실험 횟수  
  
# 베타 분포를 통한 성공/실패 추적  
successes_A, failures_A = 0, 0  
successes_B, failures_B = 0, 0  
cumulative_rewards_A, cumulative_rewards_B = [], []  
  
# 톰슨 샘플링 기반 A/B 테스트 실행  
for _ in range(n_trials):  
    # A와 B에 대해 베타 분포에서 샘플링  
    theta_A = np.random.beta(1 + successes_A, 1 + failures_A)  
    theta_B = np.random.beta(1 + successes_B, 1 + failures_B)  
      
    # 더 큰 값을 가진 대안을 선택  
    if theta_A > theta_B:  
        # A 선택  
        reward = np.random.rand() < true_conversion_A  
        successes_A += reward  
        failures_A += 1 - reward  
    else:  
        # B 선택  
        reward = np.random.rand() < true_conversion_B  
        successes_B += reward  
        failures_B += 1 - reward  
      
    cumulative_rewards_A.append(successes_A)  
    cumulative_rewards_B.append(successes_B)  
  
# 결과 시각화  
plt.plot(cumulative_rewards_A, label="A Cumulative Rewards")  
plt.plot(cumulative_rewards_B, label="B Cumulative Rewards")  
plt.xlabel('Trials')  
plt.ylabel('Cumulative Successes')  
plt.legend()  
plt.show()