추천 시스템

Multi-Armed Bandits

망나 2019. 11. 7. 14:53

강화 학습 알고리즘 중 하나인 Multi-Armed Bandits에 대해서 알아보도록 하겠습니다.

 

Multi-Armed Bandits

Multi-Armed Bandits은 카지노에서 어떤 슬롯머신에 투자를 해야 이익을 최대화할 수 있을지에 대한 문제를 풀기 위해 만들어진 알고리즘으로 알려져 있습니다. 쉽게 말하면 Multi-Armed Bandits은 사용자가 어느 슬롯머신의 손잡이를 당겨야 가장 높은 수익을 올릴 수 있을지를 결정할 수 있는 알고리즘입니다.

 

Multi-Armed Bandits에서 가장 중요한 개념은 탐색과 활용(Exploration and Exploitation)입니다. 탐색과 활용의 균형있는 조절이 필요한 추천 시스템에도 Multi-Armed Bandits 알고리즘은 많이 활용되고 있습니다. 탐색과 활용이 정확히 무엇을 뜻하는지에 대해서 알아보도록 하겠습니다.

 

Exploration과 Exploitation 사이에는 Trade-off가 존재합니다. 쉽게 인터넷 광고 배너를 예로 들어보겠습니다. Exploration은 말 그대로 더 많은 정보를 수집하기 위해 불확실성이 높은 광고 콘텐츠를 보여주며 사용자들의 성향을 탐색한다고 이해할 수 있습니다. Exploitation은 사용자들이 많이 소비할 것 같은 광고 콘텐츠를 추천으로 제공합니다. 따라서 Exploitation 기반의 추천 시스템을 사용한다면 인기 콘텐츠 위주로만 추천이 되어 새로운 콘텐츠나 독특한 콘텐츠를 추천하기가 어렵다는 한계가 있기 때문에 Exploration을 활용하여 인기가 없을지 모르는 불확실성이 높은 신규 콘텐츠들도 추천해줌으로써 사용자들의 피드백과 같은 다양한 정보 수집하여 전체적인 추천 시스템의 성능을 향상시킬 수 있습니다.

 

인터넷 광고 배너의 클릭률은 곧바로 수익률로 이어지기 때문에 현실적으로 풀어야할 아주 중요한 문제라고 할 수 있습니다.

 

직관적으로 설명하자면, Exploration은 안가본 새로운 식당을 다니며 맛집을 찾는 방법이고, Exploitation은 이미 검증된 인기 있는 맛집을 찾아간다고 생각할 수 있습니다.

 

Multi-Armed Bandits은 Exploration과 Exploitation을 조절하여 장기적으로 봤을때 최종 Reward를 최대화하기 위한 알고리즘입니다. 그렇다면 다양한 Multi-Armed Bandits 알고리즘에 대해서 하나씩 알아보도록 하겠습니다.

 

Multi-Armed Bandits 문제의 용어를 정리하면 아래와 같습니다.

 

- 행동(action): MAB에서 할 수 있는 하나의 선택 (예, A/B 테스트에서 선택할 수 있는 A안, B안)

- 보상(reward): 한 번의 행동에 따른 수치화된 결과 (에, 고객에서 선택된 안을 보여줬을 때 고객의 구매액)

- 가치(value): 행동에 대한 기대 보상, 또는 행동에 따르는 보상의 평균

 

MAB에서 모든 행동은 순서대로 발생한다고 가정합니다. 그 순서에 따라서 시점 \(t\)의 행동을 \(A_{t}\)라 하고, 그 행동에 따른 보상은 \(R_{t}\)로 표기합니다. 또한, 행동 \(a\)의 가치는 \(q_{*}(a)\)이며 시점 \(t\)에 추정된 가치는 \(Q_{t}(a)\)로 표기합니다.

 

 

 

1.  ε-greedy

 

greedy 알고리즘은 간단하게 모든 슬롯머신을 한 번씩 플레이 한 후 가장 reward가 높았던 슬롯머신을 골라서 올인하는 방법입니다.

greedy 알고리즘

해당 방법은 Exploration(탐험)이 충분히 고려되지 않았다는 단점이 존재합니다. 이를 보완하기 위해서 사용하는 알고리즘이 ε-greedy(epsilon-greedy)로 (1-ε) 확률로 greedy한 action을 선택(Exploitation)하고 ε 확률로 random한 action을 선택(Exploration)함으로써 Exploration과 Exploitation을 적절히 활용하는 알고리즘입니다.

 

ε-greedy from [http://blog.yhat.com/posts/the-beer-bandit.html]

 

   * 1-ε 확률로 지금까지 경험적으로 reward가 가장 좋은 action 선택.

   * ε 확률로 랜덤한 action 선택.

 

직관적이고 쉬운 알고리즘이지만 단점이 존재합니다. 먼저, 많은 시도 끝에 최적의 action을 알게 되더라도 지속적으로 ε의 확률로 랜덤한 Exploration을 해야하므로 최적 결과값과 멀어질 수 있습니다. 또한, ε의확률로 최적이 아닌 랜덤한  action을 선택하기 때문에 전체 action들 중에서 어쨌든 충분한 관측이 부족하여 정보를 얻지 못하는 경우가 생길 수 있습니다.

 

Reinforcement Learning - Richard Sutton

 

 

2. UCB(Upper Confidence Bound)

 

위에서 알아본 ε-greedy 알고리즘은 항상 경험적 평균값을 기준으로 reward가 좋은 action을 고르고 의 확률로 나머지 action을 무작위로 선택하게 되지만, 실제로 매 시간마다 action에서 얻는 보상은 변하지 않는 값이 아닌 특정 분포에서 얻게되는 랜덤 변수 이기 때문에 지금 순간에 경험적 평균값이 크다고해서 정말로 해당 action이 최적의 선택이라고 할 수는 없습니다. 이러한 문제점은 관측 횟수가 적을수록 더욱 큰 차이를 발생시킬 수 있습니다.

 

UCB 알고리즘은 이러한 문제를 해결하기 위해서 경험적 평균값이 높은 action을 선택하는 대신, 시간 t마다 과거의 관측결과와 몇 가지 확률들을 고려하여 최적이 될 수 있을만한 가능성을 수치로 계산하여 action을 선택하게 됩니다.

 

UCB 알고리즘

위의 식에서 보면 \(t\)는 현재 시간이고 \(N_{t}(a)\)는 현재 시간에서 action a가 선택된 횟수를 의마합니다. 이 값은 action의 실제 보상에 대한 confidence의 upper bound로 Chernoff-Hoeffding bound를 통해 얻어지는 값 입니다. 처음에는 관측 결과가 좋은 action을 고르되, 관측 결과가 적은 action을들 고를 확률이 더 높을 수 있지만, 시이 충분히 지나고 나면 경험적 결과가 더 큰 가중치를 얻게 되고, 그 결과로 시간이 지난 후에는 경험적으로 가장 좋은 action들을 선택 할 수 있게 됩니다.

 

Reinforcement Learning - Richard Sutton

 

 

3. Thompson Sampling

 

톰슨 샘플링은 구글 Analytics에서도 활용할 만큼 좋은 성능을 보여주고 있는 알고리즘입니다.

 

톰슨 샘플링은 가치를 직접 추정하는 대신 가치의 분포를 추청하고 행동을 선택할 때는 이 분포로부터 가치를 무작위 추출해서 가장 가치가 높은 행동을 선택하게 됩니다. 이후 받은 보상으로부터 베이즈 정리를 활용하여 가치의 분포를 업데이트 하는 방식으로 동작합니다.

 

\(t\)시점의 context \(x_{t}\)상에서 관측한 \((a_{t}, r_{t})\)와 \(r_{t}\)가 따르는 분포의 파라미터 \(\theta \)로 likelihood function Pr[\(r_{t} | a_{t}, x_{t}, \theta\)]를 정의하면 다음을 \(max\)로 하는 \(\theta\)값을 찾는 Multi-Armed Bandits 문제가 됩니다.

 

\(\max_{\theta}Pr[\theta|D] = \prod Pr[r_{t}|a_{t}, x_{t}, \theta]Pr[\theta]\)

 

여기서 \(D = {(x; a; r)}\)으로 post observations이고 매 \(t\)시점마다 action을 했을 때의 reward는 다음과 같이 예측할 수 있습니다.

 

\(E[r|a] = \int E[r|a, \theta]Pr[\theta|D]d\theta\)

 

이를 최대화하는 action을 \(a^{*}\)라고 할 때 다음과 같이 정리할 수 있습니다.

 

\(\int I[E(r|a^{*}, x, \theta) = \max_{a}E(r|a, x, \theta)]Pr(\theta|D)d\theta\)

 

위 수식을 통해서 매 시간 \(t\)에서 전체 파라미터에 대해 구한 예측 reward를 최대화하는 action을 선택하는 것이 톰슨 샘플링의 목적입니다. 

 

톰슨 샘플링은 확률적 알고리즘이고 늦게 들어오는 피드백을 수용할 수 있다는 장점이 있습니다. 또한 논문에서 톰슨 샘플링이 UCB보다 좋은 성능을 보인다고 주장하고 있습니다.

 

 

REFERENCE

- Reinforcement Learning: An Introduction

- NC Soft 블로그

- 멀티 암드 밴딧(Multi-Armed Bandits)

- Multi-armed Bandit

- A/B 테스팅과 '여러 팔 강도' 문제

'추천 시스템' 카테고리의 다른 글

추천 알고리즘 - SVD (Singular Value Decomposition)  (0) 2019.11.12
LaTeX 활용해서 논문쓰장  (6) 2018.09.18
Collaborative Filtering  (0) 2018.09.15