0. Multi-Armed Bandits(멀티암드 밴딧) 의 역사
카지노의 고객들은 특정 슬롯머신의 수익률이 좋다는 사실을 경험적으로 알게된다.
또, 한번 대박이 터진 슬롯머신은 한동안 수익률이 좋지 않다는 사실을 알게된다.
어느날, 카지노에 방문한 수학자가 “이 슬롯머신에 어떻게 투자를 하면 최적의 수익을 얻을 수 있을까?” 라는 생각을 하게 된다.
💡 멀티 암드 밴딧은 카지노에서 슬롯머신 투자를 최적화하기 위해 만들어진 알고리즘이다.
정리하자면, N개의 슬롯머신이 있다. 각각의 슬롯머신은 수익률이 다르다.
당장, 고객은 각 슬롯머신의 수익률을 알지 못한다.
여기서 내 돈을 어느 슬롯머신에 걸고 슬롯머신의 암(손잡이)을 내려야 돈을 가장 많이 벌 수 있을까?
여기서 슬롯머신이 밴딧(Bandit)이고, 슬롯머신의 손잡이가 암(arm)이다.
카지노에는 여러 개의 슬롯머신이 있기 때문에, 이 문제의 이름은 Multi-Armed Bandits가 된다.
MAB는 그 역사에 걸맞게, 상당히 Profitable한 알고리즘이다.
실제 비즈니스 어플리케이션에서 상당한 성과를 거두고 있으며, 눈에 띄게 성능을 개선시켜준다.
탐색과 활용(Exploration and Exploitation)
MAB는 강화학습의 핵심 아이디어 중 하나인 탐색과 활용을 다루고 있다. 하지만 강화학습으로 분류되진 않는다.
멀티암드밴딧(이하 MAB)에서 핵심 문제는 탐색과 활용이다. 이 문제를 잘 풀어내는 것만으로도 상당수의 비즈니스 문제를 해결할 수 있다.
보상을 최대화하는 알고리즘 4가지를 아래에서 예시를 들어 설명해보고자 한다. 예를들어, 오늘 카지노에 방문했다고 가정하자.
3개의 슬롯머신을 동시에 플레이한다. 이제 돈을 벌기 위한 전략을 수립한다.
전략 1. greedy
: 한 번씩 플레이 한 후, 점수 좋은 슬롯머신에 몰빵
한 번씩 플레이 후, 돈을 가장 많이 딴 슬롯머신에 모두 투자한다.
- 슬롯머신 1(Arm 1) : 1000원
- 슬롯머신 2(Arm 2) : 0원
- 슬롯머신 3(Arm 3) : 500원
→ “슬롯머신 1에 전부 투자하자!”
❗문제점 : 한 번 씩만 테스트 했다는 점. 즉 탐험(Exploration)이 충분히 이루어지지 않았다. 이 전략은 좋지 않다!
전략 2. 입실론 그리디 e-greedy
: 동전을 던져서 앞면이 나오면 점수 좋았던 슬롯머신, 뒷면이 나오면 랜덤으로 선택
탐험이 부족했던 전략1 을 수정한 전략이다.
일정한 확률로, 랜덤하게 슬롯머신을 선택하도록 한다.
동전의 앞면이 나올 확률은 50% 이다. 50%의 확률로 greedy알고리즘으로 경험상 성능이 좋았던 슬롯머신을 선택하고,
50%의 확률로 동전의 뒷면이 나오면 슬롯머신의 성능과 상관없이 랜덤으로 슬롯머신을 고른다.
이 알고리즘을 입실론 그리디(e-greedy)알고리즘이라고 한다.
여기서 동전의 앞면이 나올 50%의 확률이 입실론이라는 하이퍼파라미터이다.
이런 약간의 변칙을 사용함으로써, greedy 방식(녹색 그래프)에 비해 더 나은 결과가 나온다.
전략 3. UCB(Upper-Confidence-Bound)
: 좋은 수익률을 보이며, 최적의 선택이 될 가능성이 있는 슬롯머신을 선택한다.
전략2 는 최적의 슬롯머신을 찾기 위해 랜덤으로 탐험을 한다. e-greedy알고리즘이 지난 전략중에선 최고의 성능을 보일 것이다.
하지만, 탐험을 할 때 꼭 랜덤이어야만 할까? 좀 더 합리적으로 탐험을 할 수 없을까?
우리의 목표는, 슬롯머신에서 숨겨진 로또를 찾는것이다.
이를 위해서 탐험을 해야한다. 슬롯머신일 최적이 될 수 있을만한 가능성을 수치로 계산해서 가장 가능성이 있는 슬롯머신을 선택하면 어떨까?
가능성에 투자해보자! (아직 좋은 성과를 내진 못했지만, 왠지 더 시도해보면 잘 할 수 있을 것 같아)
UCD 알고리즘에서 다음 action을 선택하는 알고리즘의 수식은 다음과 같다.
greedy 알고리즘의 수식과 비교
빨간 네모 점선의 수식이, 해당 슬롯머신이 최적의 슬롯머신이 될 수도 있는 가능성(불확실성)이다.
- c : 탐험의 정도를 조절할 수 있는 하이퍼파라미터
- N : 슬롯머신을 선택한 횟수
- t : 모든 슬롯머신을 선택한 횟수의 합
멀티암드밴딧 문제에서는 UCB알고리즘을 베이스로한 알고리즘이 가장 각광받고 있다.
전략 4. 톰슨의 샘플링(Thompson's sampling)
- 베이지언 방식 사용
- 베타분포(사전 정보)를 사용하여 수익의 일부 사전 분포를 가정한다.
각 단계마다 표본을 추출(손잡이를 당김)하여 최고의 손잡이를 선택할 확률을 최대화한다.
어느것이 가장 좋은 손잡이인지 모른다(이것이 항상 문제이다).
그러나 연속적인 추출을 통해 얻는 수익을 관찰하면 더 많은 정보를 얻을 수 있다.
톰슨 샘플링은 베이즈 방식을 사용한다. 즉 베타분포를 사용하여 수익의 일부 사전 분포를 가정한다.
각 추출 정보가 누적되면서 정보가 업데이트 되어 다음번에 최고의 손잡이를 선택할 확률이 효과적으로 최적화 될 수 있다.
정리하자면
- MAB는 A/B테스트의 진화된 버전이라고 볼 수 있다.
- 비즈니스 문제를 다룰 때, 두가지 차이점을 아는 것보다 중요한 것은 “가장 좋은 것을 아는것”이다.
- 과거> A/B테스트 : 가격 A와 가격 B의 차이가 통계적으로 유의한가?
- 현재> 가능한 여러 가격 중에서 가장 좋은 가격은 얼마일까?
- 전통적인 통계적 실험 설계에서 벗어나, 질문이 다음과 같이 변하고 있다.
- A/B 테스트의 문제점
- 시간과 비용이 많이 소요된다. (전통적 A/B 테스트는 임의표집 과정을 기본으로 하기 때문에 수익이 낮은 것을 너무 많이 시도한다.)
- A/B 테스트를 할 대 A안이 훨씬 좋았다면, 테스트 기간 동안엔 B안으로 인해 결국 손해를 보게 된다.
- A/B테스트를 할 때는 A안이 좋았는데 일주일이 지나니 B안 반응률이 더 좋아졌다
- A/B 테스트와 달리 MAB는 실험 도중에 얻은 정보를 통합하고 수익이 낮은 것의 빈도를 줄이는 쪽으로 표본 추출과정을 변경한다.
- 전통적인 통계적 접근 방식보다 명시적인 최적화와 좀 더 빠른 의사 결정이 목표
- 특히 웹 테스트를 위해 자주 사용된다.
- 두 가지 이상의 처리를 효과적으로 다룰 수 있다.
- MAB는 실험설계에서 전통적인 통계적 접근방식이 아닌, 최적화&빠른 의사결정을 위해 사용한다.
- 웹 테스트 적용 예시
- 여러 개의 손잡이 대신에 제안/헤드라인/색상을 테스트 할 수 있다.
- 고객은 클릭/ 클릭안함의 결정을 한다.
- 처음에는 무작위로 균등하지만, 하나가 좋은 결과를 내기 시작하면 더 자주 표시될 수 있도록 한다.
- 카카오 뉴스 추천 알고리즘 적용 예시
실시간 이용자 반응형 뉴스 추천 서비스를 내세운 루빅스는 초기에 **'멀티암드밴딧(Multi Armed Bandit, MAB)' 알고리즘**을 썼다. 이전 방식처럼 로그인한 사용자가 클릭한 뉴스들을 바탕으로 비슷한 뉴스를 추천해주는 내용 기반 필터링이나 비슷한 성별, 연령대 별로 선호하는 뉴스를 노출시키는 협업 기반 필터링의 한계를 보완하기 위해 고안한 것이 이 알고리즘이다.
이 알고리즘에서 고려한 것은 크게 세 가지 요인이었다고 카카오는 공개했다.
- 시간이 흐를수록 뉴스를 볼 가능성이 줄어든다.
- 어떤 위치에 게시되느냐에 따라 클릭확률이 크게 달라진다.
- 한번 본 뉴스는 다시는 보지 않을 가능성이 많다.
이런 요인에 따라 최신 뉴스일수록 클릭할 확률을 높이기 위해 가중치를 줬다.
또 한번 클릭된 뉴스에 대해서는 가중치를 떨어뜨리는 등 방식을 써서 클릭할 확률이 높은 뉴스를 예측하는 한편, 이용자들 마다 다른 선호도를 반영해 뉴스를 모바일앱에 배치하는 작업을 진행토록 했다.
이런 노력은 그대로 뉴스 이용자 수 증가로 이어졌다. 2015년 11월 다음앱 뉴스 주간 이용자수가 1천910만명이었던 것에서 1년 뒤인 2016년 11월에는 2천710만명으로 42% 가량 늘어나는 효과를 거뒀다.
논문에서 루빅스 개발 TF팀이 강조한 **멀티암드밴딧 알고리즘**은 슬롯머신을 '외팔이 강도(One-Armed Bandit)'라는 속어로 부르던 것에서 착안한 것이다. 멀티암드밴딧 알고리즘은 레버가 여러개 달린 슬롯머신 혹은 한 줄로 늘어선 여러 개 외팔이 슬롯머신을 뜻한다.
여러 대 혹은 레버가 여러 개 달린 한 대의 슬롯머신으로 수차례 테스트를 거쳐 제한된 시간 내에 가장 많은 보상을 따내는 과정이 초기 루빅스 알고리즘에 녹아들어갔다.
어떤 슬롯머신이 돈을 딸 확률이 높은지를 알기 위한 탐색 횟수를 줄이면서도 수익을 극대화하는 전략을 뉴스에 적용해 본 것이다.
다시 말하면 여러 대 혹은 레버가 여러 개 달린 한 대의 슬롯머신을 최소한으로 돌려본 뒤 가장 많이 돈을 딸 수 있는 슬롯머신 혹은 레버를 찾아내는 식이다.
슬롯머신을 개별 뉴스로 보면 슬롯머신의 승률은 뉴스가 클릭될 확률(CTR)을 말한다. 가장 클릭률이 높은 방식으로 뉴스를 보여주는 알고리즘이 다음앱 뉴스 화면에 적용됐다.
TF팀은 다른 정보성 콘텐츠와 달리 최신 기사가 선호되고, 한번 클릭한 기사는 다시 클릭할 확률이 떨어진다는 등 특성을 추가로 반영해 뉴스 맞춤형 멀티암드밴딧 알고리즘을 고안했다.
카카오정책지원팀 관계자에 따르면 현재 카카오의 뉴스추천 알고리즘에는 자체적으로 수정해 적용한 멀티밴드암 알고리즘 외에도 여러 알고리즘이 조합돼 적용되고 있는 추세다.