Bandit 알고리즘과 추천시스템

요즈음 상품 추천 알고리즘에 대해 고민을 많이 하면서, 리서칭하다 보면 MAB 접근법 등 Bandit 이라는 개념이 많이 등장한다.

이번 글에서는 Bandit 알고리즘이란 무엇이며, 추천시스템과는 어떻게 연결되는지를 살펴보고자 한다.

그리고 MAB 문제를 해결하는 여러 알고리즘에 대해 정리해볼 것이다.

​

우선 수확(Exploitation)과 탐험(Exploration)이라는 개념에 대해 고찰해보자.

우리가 어떤 레스토랑에서 밥을 먹을지 고민을 하고 있다고 가정해보자.

우리는 하나의 레스토랑에서 밥을 먹을 수 밖에 없고, 비용을 지불해야하니 가장 맛있는 레스토랑에서 식사를 하고 싶다.

수확이란 가장 효용이 높은 곳에서 집중적으로 보상을 받는 행동을 의미하고,

탐험은 지금껏 해보지 않은 경험이라 새로운 시도를 하는 행동을 의미한다.

탐험은 비용이 발생할 수 밖에 없으니 어떤 환경에서 최대의 효용이 돌아오는 행동을 하기 위해서는 수학과 탐험 사이의 적절한 균형이 필요하다.

즉 최소한의 탐험으로 가장 효용이 높은 곳에서 수확하는 것이 베스트이다.

​

지금껏 살펴본 지도 학습과 비지도 학습 모델과는 달리 강화학습이 이와 유사하다.

지도/비지도 학습은 환경에 변화가 없는 정적인 학습이지만,

강화학습은 주체(Agent)가 현재 상황(Environment) 중 가장 최대의 보상(Reward)을 얻는 행동을 선택하도록 학습한다.

​

Bandit 알고리즘은 슬롯 머신에서 부터 유래하였다. 우리가 카지노에 가면 모든 슬롯 머신을 다 해보기엔 한계가 있다.

하지만 배팅하여 어떤 머신에서 가장 좋은 결과를 얻을 수 있는지는 알고 싶다. 이러한 문제를 푸는 것이 Bandit 알고리즘의 시작이다.

​

추천 알고리즘도 역시 마찬가지이다.

이커머스 상품 추천 모델이라 생각하면, 고객은 비용을 지불하면서 무언가를 살 것이고, 그 중에서 최대 보상이 되는 선택을 하고 싶을 것이다.

추천시스템은 여러모로 불확실성을 지니고 있다.

예를 들어 상품과 유저가 새롭게 유입되고, 이에 따른 Cold start문제가 발생한다. 유저의 선호가 변화한다는 점도 마찬가지이다.

이에 따라 추천 시스템도 빠르게 변화하고 적응해야한다.

앞서 살펴본 이용과 탐험의 개념을 적용해보면, 유저의 Profile등을 통해 파악한 선호를 기반으로 상품을 추천할 수도 있고,

아니면 아예 유저가 좋아할 만한 것을 모델링하는 추천도 있다. 이는 탐험을 통해 고객의 피드백을 받고자 하는 부분이다.

​

* Greedy Algorithm

우리는 여러 슬롯 머신(Multi-armed bandit)을 두고 어떤 곳에서 최상의 보상을 받을 수 있을까 고민하게 된다.

이 때 최상의 보상을 부여하는 머신을 찾는 알고리즘으로 가장 쉽게 생각해볼 수 있는 것은 Greedy Algorithm이다.

그냥 모든 슬롯 머신을 다 테스트해보고, 가장 최선을 고르는 것이다. 하지만 이는 충분한 탐험이 이루어지지 않았다는 단점이 있다.

​

* 입실론-그리디 알고리즘

가장 먼저 제기된 알고리즘은 엡실론 - 그리디(greeedy) 알고리즘이다.

앞선 Greedy 알고리즘보다는 좀 더 직관적인데, 이제껏 탐험해본 것들 중에서 가장 최선의 슬롯머신에 대해 투자하고,

입실론만큼의 확률로 남은 슬롯머신 중 하나를 탐험해보는 것이다. 입실론이 앞서 살펴본 탐험-수확 간의 조정 비율이다.

이 알고리즘의 단점은, 만약 최대의 보상을 얻는 머신을 찾았다고 하더라도 탐험을 계속해야하는 것이고,

탐험 과정에서도 입실론 확률만큼 무작위로 선정하기 때문에 충분히 탐험하지 못한다는 문제가 있다.

출처 : http://blog.yhat.com/posts/the-beer-bandit.html

​

* UCB (Upper Confidence Bound) Algorithm

이 알고리즘은 지금껏 탐험을 통해 알려진 보상들이 얼마나 많은 탐험을 통해 산출되었는지에 대한 정보를 이용한다.

$\combi{A}_t\ \doteq \ \arg \max _a^{ }\left[\combi{Q}_t\left(a\right)\ +\ c\sqrt{\frac{\log \ t}{\combi{N}_t\left(a\right)}}\right]$At​ ≐ argmaxa[Qt​(a) + c√log tNt​(a)​]​

* t : 특정 시점에서 슬롯머신들을 선택한 횟수의 합

* Qt(a)는 t시점까지의 슬롯머신 a의 누적 보상

* c는 탐색을 결정하는 하이퍼 파라미터로서, 클수록 탐색을 많이 한다

* Nt(a)는 t시점 이전까지 해당 슬롯머신을 선택한 횟수

​

누적보상 값인 Qt(a)의 오른쪽 파라미터가 지금껏 경험에 따른 슬롯머신 A의 보상에 대한 conficence upper bound이다.

가장 처음에는 관측 결과가 좋은 슬롯머신을 고르게 되나, 시간이 지나 경험이 쌓이게 되면 경험했던 슬롯 머신들 중 가장 좋았던 결과를 선택하게 되는 것이다.

​

* Thompson Sampling

가장 최근의 알고리즘이며, GA에서도 해당 알고리즘이 사용되고 있다고 한다. 주로 웹의 배너/광고에 대한 예측을 위해 사용된다.

앞서 살펴본 UCB 알고리즘이 값을 추정한대로 수행하도록 하는 반면 예측값(Expected value)의 사후 분포를 계산하여 샘플링한 뒤 선택한다.

즉 값을 직접 추정하는 것이 아니라 값의 분포를 추정하고 그 중 일부만 샘플링하여 결정하는 것이다.

​

베타 분포란 알파와 베타 두 파라미터로 분포 모양을 조정하는 것이다.

클릭은 0 또는 1로 나뉘기 때문에(베르누이 분포) 베타 분포를 이용하게 되었다고 한다.

베타분포에서 각 광고의 클릭 횟수/미클릭 횟수를 input하여 확률 밀도 함수를 그린 뒤,

그 밀도 함수에서 일부 값들을 샘플링하여 뽑힌 것 중 가장 보상이 큰 광고를 선택하게 된다.

이후 실제 보상이 어떻게 이루어졌는지 확인하고 다시 데이터로 input하여 위 과정을 반복한다.

출처 : https://towardsdatascience.com/thompson-sampling-fc28817eacb8

만약 세 가지의 밴딩 머신이 있다고 한다면, 처음엔 서로 선택하기 어려운 분포를 보이지만,

위 그림과 같이 여러 Trial을 통해 실제 분포와 맞춰나가게 되는 것이다.

초기에는 샘플링에 따라 랜덤 선택을 하기 때문에, 실제 좋지 않은 분포를 키울 수 있지만,

지속적으로 선택하다 보면 최대 보상을 찾을 수 있는 것이다.

​

이 알고리즘은 확률적 알고리즘이라 UCB보다 좋은 성능을 보인다고 한다.

출처 : https://www.youtube.com/watch?v=PNHenYiyIYc

​

​

---

참고자료

https://towardsdatascience.com/beyond-a-b-testing-multi-armed-bandit-experiments-1493f709f804

 

Beyond A/B Testing: Multi-armed Bandit Experiments

An implementation of Google Analytics’ stochastic k-armed bandit test with Thompson sampling and Monte Carlo simulation

towardsdatascience.com