MAB(Multi Armed Bandit)를 활용한 추천

오늘은 MAB 알고리즘을 추천 시스템에 활용해 보는 방법에 대해 알아보겠습니다.

 

1. MAB란?

2. MAB 알고리즘 종류

  2-1. epsilon greedy algorithm

  2-2. UCB (Upper Confidence Bound)

  2-3. Thompson Sampling

3. MAB를 이용한 추천 시스템

 

 

 

1. MAB란?

 

 

 

 

MAB는 강화학습으로 분류되지는 않지만 해당 원리를 활용한 알고리즘으로 위의 그림과 같이 각 슬롯머신에서 얻을 수 있는 Reward의 확률이 모두 다른 여러 개의 슬롯머신을 의미합니다.

 

MAB는 수익을 최대화하기 위해서 arm을 어떤 policy에 의해 당겨야 하는지를 결정하는 알고리즘입니다.

 

MAB는 강화학습의 핵심 아이디어인 Exploitation(이용)과 Exploration(탐색)을 활용합니다.

 

Exploitation은 현재에서 사용자가 많이 소비할 것 같은 콘텐츠를 예측하여 추천하는 것이고

 

Exploration은 더 많은 정보를 얻기 위해 사용자가 많이 소비할 것 같지 않는 불확실성이 높은 콘텐츠를 추천하는 것입니다.

 

예를 들어, 광고를 노출시킬 때 사용자들이 클릭할 것 같은 광고를 노출시키는 것이 Exploitation, 사용자가 아직 보지 않았지만 관심 있을 수 있는 광고를 노출시키는 것이 Exploration이라고 할 수 있습니다.

 

Exploration이 너무 적을 경우, 정보가 부족한 상태에서 Exploitation하면 최종적으로 높은 Reward를 보장할 수 없고

 

Exploration이 너무 많을 경우, 비용을 과하게 낭비하게 되어 최종적으로 높은 Reward를 얻을 수 없습니다.

 

즉, Exploitation과 Exploration 사이에는 Trade-off가 존재하므로 수익을 최대화하기 위해서, 현재의 단기적인 이익을 극대화하는 Exploitation과 더 많은 정보를 수집하는 Exploration을 적절하게 조절할 필요가 있습니다.

 

MAB는 알고리즘이 간단하고 이해하기 쉬우며 실제 비즈니스 어플리케이션에 매우 유용하여 추천 시스템에도 활용됩니다.

 

 

 

2. MAB 알고리즘 종류

 

2-1. epsilon greedy algorithm

 

epsilon greedy algorithm이란 일정한 확률에 의해 랜덤으로 슬롯머신을 선택하도록 하는 것입니다.

 

greedy algorithm은 Reward가 가장 높은 arm을 선택하는 방식인데, 이 방식은 Exploration이 적어지게 되므로 일정한 확률로 Reward가 높은 arm이 아닌 랜덤으로 arm을 선택하는 방식입니다.

 

이때 말하는 확률이 epsilon ( \( \epsilon  \) ) 입니다.

 

epsilon greedy algorithm을 표현하면 다음과 같습니다.

 

 

 

 

1-\( \epsilon  \)의 확률로 Reward가 가장 높은 arm을 선택하고 \( \epsilon  \)의 확률로는 랜덤으로 arm을 선택하는 policy입니다.

 

\( Q_t(a)  \)는 현재까지 관측된 개별 머신의 Reward 평균값을 뜻하고 수식은 다음과 같습니다.

 

 

 

 

이 알고리즘은 심플하면서도 강력한 알고리즘이기 때문에 MAB의 가장 기본 알고리즘으로 여겨지는 알고리즘입니다.

 

 

 

2-2. UCB (Upper Confidence Bound)

 

UCB는 reward의 Upper Confidence Bound를 계산하여 Uncertainty Weight로 활용하는 알고리즘입니다. 

 

t 시점에서 UCB를 기반으로 arm을 선택하는 기준은 다음과 같습니다.

 

 

 

 

빨간색으로 박스 친 부분이 해당 action이 최적의 action이 될 수도 있는 가능성인 Uncertainty Weight을 나타낸 것입니다.

 

\( N_t(a)  \)는 action a를 선택했던 횟수를 뜻하고 c는 Exploration을 조정하는 파라미터를 뜻합니다.

 

이 항이 의미하는 것은 t시점에서 해당 action을 적게 선택했다면 다른 action에 비해 항의 값이 커지기 때문에 해당 action이 뽑힐 가능성을 높여주게 됩니다. 

 

따라서, UCB는 현재 해당 action이 최적의 action일 수도 있는 불확실성을 고려해서 최적의 action을 선택하는 알고리즘입니다.

 

 

 

2-3. Thompson Sampling

 

Thompson Sampling은 과거에 관측된 데이터를 이용하여 Reward 분포를 추정한 뒤, 해당 분포를 통해 가장 높은 Reward를 줄 arm을 높은 확률로 선택해 주는 알고리즘입니다.

 

Thompson Sampling에서는 action a에 해당하는 reward 추정치 \( Q_t(a)  \)가 베타 분포를 따른다고 가정합니다.

 

베타 분포는 두 개의 양의 변수로 표현할 수 있는 확률 분포이며 0과 1 사이의 값을 가집니다.

 

 

 

 

이제 예시를 통해 Thompson Sampling이 진행되는 과정에 대해 알아보겠습니다.

 

사용자에게 보여지는 광고 배너가 3개 있고 베타 분포에서 \( \alpha  \)는 배너를 보고 클릭한 횟수, \( \beta  \)는 배너를 보고 클릭하지 않은 횟수를 뜻한다고 가정합니다.

 

이때 배너를 클릭할 확률은 \( Beta(\alpha + 1, \beta + 1)  \)이라고 표현할 수 있습니다.

 

1을 더해주는 이유는 0이 되지 않도록 하는 역할이고 꼭 1이 아니어도 됩니다.

 

 

 

Step1은 데이터가 없는 초기 상태를 뜻하고 모든 배너의 \( \alpha  \), \( \beta  \)는 0입니다.

 

 

 

 

다음 단계는 배너를 랜덤하게 노출시키는 것입니다.

 

랜덤하게 노출시키는 이유는 랜덤하게 여러 번 노출시키지 않으면 초기값에 의존하는 정도가 커질 수 있기 때문입니다.

 

Step2 과정을 여러 번 반복하여 데이터를 쌓은 후 다음 단계로 넘어갑니다.

 

 

 

 

Step3에서는 베타 분포에서 샘플링하여 배너를 노출시킵니다.

 

위의 그림에서 처럼 베타 분포에 따라 배너 별로 Thompson Sampling을 한 결과값에 따라 확률이 높은 배너를 노출시킵니다.

 

Step2와 마찬가지로 이 과정을 여러 번 반복합니다.

 

 

 

 

마지막 Stpe인 Step4에서는 수많은 노출을 거친 후에 Thompson Sampling한 결과값이 가장 높은 배너를 최종적으로 선택합니다.

 

 

Thompson Sampling은 확률적 알고리즘이기 때문에 policy를 통해 선택할 action이 확률분포에 의존하게 됩니다.

 

 

여러 MAB 알고리즘 중 Thompson Sampling이 가장 우수한 성능을 가진 것으로 알려져 있습니다.

 

 

 

3. MAB를 이용한 추천 시스템

 

MAB를 이용한 추천 시스템에서는 실제 서비스의 지표인 클릭/구매를 모델의 Reward로 가정합니다.

 

해당 Reward를 최대화하는 방향으로 모델이 학습되고 추천을 수행하게 됩니다.

 

MAB 알고리즘의 policy가 유저에게 아이템을 추천하는 방식이라고 할 수 있습니다.

 

MAB는 무거운 추천 모델을 사용하지 않고 간단한 Bandit 기법을 적용하여도 CTR, CVR과 같은 온라인 지표가 좋아질 수 있다는 장점이 있습니다.

 

 

MAB의 Thompson Sampling을 이용하여 유저에게 아이템을 추천하는 방식에 대해 알아보겠습니다.

 

개인 유저에 대해 모든 아이템의 Bandit을 구하는 것은 불가능하기 때문에 클러스터링을 통해 비슷한 유저끼리 그룹핑한 뒤에 해당 그룹 내에서 Bandit을 구축합니다.

 

이때 필요한 Bandit의 개수는 유저 클러스터 개수 X 후보 아이템 개수입니다.

 

그림을 통해 알아보겠습니다.

 

 

 

 

유저가 들어오면 유저의 클러스터를 할당해줍니다.

 

클러스터 별로 생성된 후보 아이템 리스트에서 Thomson Sampling을 진행해서 아이템을 추천해 줍니다.

 

 

 

오늘은 MAB의 여러 알고리즘에 대해 알아보고 이 중 가장 성능이 뛰어난 Thompson Sampling을 이용한 추천 시스템에 대해서 알아보았습니다.

 

사실, 기본적인 MAB 알고리즘만 사용할 경우에는 개인화 추천이 어렵다는 단점이 존재한다고 합니다.

 

이를 보완하는 알고리즘으로 Contextual MAB가 존재하는데 이에 대해서도 공부하고 포스팅하도록 하겠습니다.

 

 

 

 

Reference

 

러닝 스푼즈의 "비즈니스 Case와 딥러닝을 활용한 추천시스템 구현" 강의

NC의 커뮤니케이션과 AI #7 사용자에게 소식을 골라주는 PAIGE: 

https://blog.ncsoft.com/%ec%bb%a4%eb%ae%a4%eb%8b%88%ec%bc%80%ec%9d%b4%ec%85%98%ea%b3%bc-ai-7-%ec%82%ac%ec%9a%a9%ec%9e%90%ec%97%90%ea%b2%8c-%ec%86%8c%ec%8b%9d%ec%9d%84-%ea%b3%a8%eb%9d%bc%ec%a3%bc%eb%8a%94-paige/