MAB는 다중 처리 실험에 대한 모델링으로 볼 수 있습니다.
카지노에 여러 개의 슬롯머신이 있습니다. 슬롯머신들은 각각이 다른 수익율을 낸다고 할 때 어떤 슬롯머신을 선택하는 것이 좋을지에 대한 답을 알려줍니다.
여러 슬롯머신들의 손잡이는 실험에서의
처리를 나타내고, 슬롯머신을 통해 얻은 수익을 처리에 대한 효과로 볼 수 있습니다.
MAB 알고리즘의 핵심 아이디어는 탐색과 활용(Exploration & Exploitation)입니다.
슬롯머신들을 돌려보고(탐색) 수익이 높다고 생각하는 슬롯머신을 돌려봅니다.(활용)
1. Greedy Algorithm
가장 먼저 생각해볼 수 있는 방법은 일정 횟수만큼 슬롯머신을 돌려보고, 돌려본 슬롯머신들 중 가장 수익률이 높은 슬롯머신에 몰빵을 하는 방법입니다.
A, B, C 3개의 슬롯 머신이 있고 각각을 동일한 횟수만큼 총 t번 돌린 결과 수익률은 다음과 같습니다.
- A: +1000
- B: - 500
- C: +500
그리디 알고리즘은 t시점에서 수익률이 좋은 A만 활용하게 되고 나머지 B, C는 활용하지 않게 됩니다. 하지만 이후에 다른 슬롯머신의 수익이 더 발생할 수도 있기 때문에 그다지 좋은 방법이 아닙니다.
위 식은 t 시점에서의 A(슬롯)가 a라는 슬롯일 때의 보상R의 기대값을 나타냅니다. 즉, a슬롯을 골랐을 때 t시점에서의 기대보상을 나타냅니다.
하지만 슬롯머신의 실제 수익률을 알 수 없기 때문에 추정치인 Qt를 사용해 값을 구하게 됩니다.
여기서 1은 Indicator Function으로, Ai=a일 때는 1, Ai가 1이 아닐 때는 0이 되는 함수입니다.(조건문과 같은 역할)
결론적으로 구하고자하는 슬롯은 Qt의 값이 가장 큰(슬롯머신을 통해 얻은 보상이 가장 큰) 슬롯이 됩니다.
argmax를 사용하면 이들 슬롯 중 가장 수익률이 높은 슬롯 At를 구할 수 있습니다.
2. ε - Greedy Algorithm(epsilon - Greedy Algorithm)
MAB의 핵심은 탐색과 활용이라 했습니다. 처음 확인한 알고리즘은 탐색의 비중이 적어 적절한 결론에 도달하지 못했습니다. ε - 그리디 알고리즘은 탐색의 비중을 좀 더 높인 알고리즘입니다.
매 시행을 하기에 앞서 동전을 던집니다.
- 동전이 앞면(H): 랜덤하게 슬롯머신을 돌립니다.
- 동전이 뒷면(T): 현재까지 슬롯머신 중 수익률이 가장 높은 슬롯머신을 돌립니다.
이 때, 동전이 앞면이 나올 확률을 ε이라 합니다.
3. UCB(Upper-Confidence Bound)
ε - 그리디 알고리즘은 ε에 따라 수행할 슬롯을 랜덤하게 선택합니다.
UCB에서는 슬롯머신을 탐색할 때, 슬롯머신이 선택한 횟수에 따라 가중치를 부여해, 좀 더 합리적인 방법으로 슬롯머신을 탐색하는 알고리즘입니다.
UCB는 슬롯을 선택할 때, 그리디 알고리즘에서 식을 추가하여 구합니다.
Nt(a)는 t시점에서 a슬롯이 선택된 횟수를 나타냅니다. a슬롯이 선택된 횟수가 작을수록 값이 커지게 되며 c라는 가중치를 두어, 선택된 횟수가 적을수록 슬롯이 선택될 확률을 높입니다.즉, UCB방식은 탐색을 좀 더 공평하게 하여 확인하지 못한 슬롯을 좀 더 많이 탐색하도록하는 알고리즘입니다.
참고
데이터 과학을 위한 통계학
'DataScience' 카테고리의 다른 글
| [Python] 통계량을 이용해 t 검정, z 검정(t-test, z-test) (0) | 2022.10.02 |
|---|---|
| [ML] 분류모형의 평가지표(confusion matrix, accuracy, precision, sensitivity(recall), specificity, F1-score) (0) | 2022.09.02 |
| [Pandas] UnicodeDecodeError: 'utf-8' codec can't decode byte 0xbb in position 2: invalid start byte (0) | 2022.08.23 |
| 임의순열검정(random permutation test) (0) | 2022.08.23 |
| [ML] 회귀모형의 평가지표, MAE, MSE, RMSE, RSE, R^2 (0) | 2022.08.23 |