기초통계 (26) 멀티암드 밴딧 알고리즘

📈 용어정리

• 멀팀암드 밴딧(MAB, multi-armed bandit) : 고객이 선택할 수 있는 손잡이가 여러 개일 가상의 슬롯 머신을 말하며, 각 손잡이는 각기 다른 수익을 가져다 준다. 다중 처리 실험에 비유라고 생각할 수 있다.
• 손잡이 : 실험에서 어떤 하나의 처리를 말한다(예를 들면 '웹 테스트에서 헤드라인A')
• 상금(수익) : 슬롯머신으로 딴 상금에 대한 실험적 비유(예를 들면 '고객들의 링크 클릭 수')

📈 멀티암드 밴딧이 나오게된 계기(A/B테스트의 문제점)

• 해당 알고리즘은 실험설계에 대한 전통적인 통계적 접근 방식보다 명시적인 최적화와 좀 더 빠른 의사결정을 가능하게 하며, 여러 테스트, 특히 웹 테스트를 위해 사용된다.

• 전통적인 A/B검정의 경우 처리방식에 따라 A혹은 B중 어느쪽이 좋은가? 와같은 정해진 질문에 대한 답을 준다. 그리고 답을 얻게되면 실험이 끝나고 결과에 따라서 행동을 한다.

• 이러한 접근 방식에 어려움이 몇가지 있다. 첫째, 결론을 내리기 어려울 수 있다. 실험결과를 통해 효과가 있다는 것을 유추할 수 있지만, 효과가 있더라도 그것을 입증할 만한(전통적인 통계 표준을 만족시킬 만한) 크기의 표본이 없을 수 있다

• 둘째, 우리는 실험이 끝나기 전에 이미 얻은 결과들을 이용하기 시작할 수도 있다.

• 셋째, 마음을 바꿔서 실험이 끝난 후에 추가적으로 들어오는 데이터를 기반으로 다른 것을 시도하고 싶을 수 있다.

• 네번째, 테스트하는데 시간이 오래걸리고 비용도 많이든다, 다섯번째, A안이 좋았다면 B안을 적용하는동안 결국 손해를 보게된 것이다. 마지막, A안이 좋았는데 1주일후 B안이 좋을 수도 있다.

• 유연함이 부족하다는 결론에 도달한다.

• 컴퓨터 파워가 좋아짐에 따라 유연한 방법의 접근이 가능해 졌고, 데이터 과학, 그리고 비즈니스 전반에서는 통계적 유의성보다는 제반 비용과 결과를 최적화 하는데 관심이 있다.

• 이번에 다루는 밴딧 알고리즘을 사용하면 한 번에 여러 가지 처리를 테스트하고 기존의 통계 설계보다 빠르게 결론에 도달할 수 있다.

📈 멀티암드 밴딧알고리즘

• 도박에서 사용되는 슬롯머신을 지칭하는 속어에서 이름을 가져온 알고리즘 이다.

• 둘 이상의 손잡이가 달려 있고 각 손잡이는 다른 속도로 돈을 지불하는 슬롯머신을 상상해 보자. 그것이 이 알고리즘의 정식 이름(팔 여러개 달린 강도, 멀티암드 밴딧)이라고 할 수 있다.

• 우리의 목표는 가능한 많은 돈을 얻는 것이고, 더 구체적으로 말하면 많은 상금이 나오는 손 잡이를 나중에 확인하는 것이 아니라 빨리 확인하는 것이다. 하지만, 어려운 점은 손잡이를 잡아당길때 총 얼마를 지불할지 모른다는 것이다.

• 손잡이가 세개가 있고 모든 손잡이가 같은 상금이라고 가정하자. 다른점은 승리할 확률이다.(50번 시도한 후 다음과 같은 결과를 얻었다)

손잡이 A : 50번 중 10번 승리
손잡이 B : 50번 중 2번 승리
손잡이 C : 50번 중 4번 승리

• 다음과 같이 극단적인 결론을 내릴 수 있을것이다. '손잡이 A가 최고인것으로 보인다. 다른손잡이는 도전하지말고 A만 당기자.' 이것은 초기 시험에서 얻은 정보를 최대한 활용하는 방법이다. A가 정말로 우월하다면, 우리는 그 이익을 초기에 얻게 된다. 하지만 사실 B나 C가 더 좋다면 우리는 이 사실을 발견할 기회조차 놓치게 된다.

• 또 다른 방향의 극단적인 결론을 '모두가 무작위인 것으로 보인다.' 모두가 똑같이 잡아당기자 는 것이다. 이 접근은 A외의 다른것들의 확률을 알 수 있는 최대한의 기회를 제공하지만, 우리는 확률이 낮을 것으로 예상되는 행위를 계속해서 시도해야한다. 이를 얼마나 시도해야하는 것일까???

• 밴딧 알고리즘은 하이브리드 방식을 취하게 된다. 먼저 A가 확률이 가장 높게 나왔으므로 A를 더 자주 잡아당기는 선택을 하지만 B와 C를 당길 기회를 포기하지 않는다. A에서 계속해서 성과를 거두게 되면 그때 B와 C를 당길 기회가 A에게 더 주어져서 A를 더 자주잡아당기고, 만약에 C가 더좋아지고 A가 더 나빠지기 시작하면 처음에 A로가던 많은 기회를 C에게 돌린다. 그중 하나가 A보다 우수하고 이것이 초기 50번의 실험에서 감춰져 있었던 결과였다면, 더 많은 테스트를 통해 이 사실이 밝혀질수 있는 기회가 생기게 된 것이다.

• 웹페이지를 예로 들어보겠다, 만약에 영상 베너를 설치 하였고 이에따라 고객은 클릭하거나 하지않을것이다. 처음에는 여러 제안이 무작위로 균등하게 표시된다. 그러다가 한 제안이 다른 제안보다 좋은 결과를 내기 시작하면 더 자주 표시 될 수 있게 한다.

• 즉, 멀티암드밴딧(MAB)에서 핵심 문제는 탐색과 활용(Exploration and Exploitation)이다. 이 한가지 문제를 잘 푸는것만으로 상당한 수의 비즈니스 문제를 해결할 수 있다.

• 첫번째, 그리디 알고리즘(greedy): 한 번씩 플레이 한 후, 점수좋은 슬롯 머신에 몰빵하는것이다. 처음에 들었던 예시처럼 3대의 슬롯머신이 있을때 한번씩 돌려보고 가장높게 나온 슬롯에 모두 투자하는것이다. 이는 탐색이 충분히 이루어 지지않았다.

• 그렇다면 잡아당기는 비율을 수정하는 알고리즘을 위한 파라미터는 무엇이 되어야 할까?? 잡아당기는 비율은 언제 어떻게 수정할 것인가??

• 두번째, 엡실론-그리디 알고리즘(epsilon-greedy algorithm,e-greedy algorighm) : 동전을 던져서 윗면이 나오면 점수 좋았던 슬롯머신, 뒷면이 나오면 랜덤으로 선택, 앞서 그리디 알고리즘에서 부족했던 탐험을 수정한 전략이다. 일정한 확률로 랜덤으로 슬롯머신을 선택하도록 하는것이다. 윗면이 나와서 점수 좋은 슬롯머신을 선택할 확률 50%와 뒷면이 나와서 슬롯머신의 성능과 상관없이 랜덤으로 고를확률 50%이다. 여기서 동전의 윗면이 나올 50%의 확률이 입실론(epsilon)이라는 하이퍼 파라미터다.

• 세번째, UCB(Upper-Confidence-Bound)
  좋은 수익률을 보이며 최적의 선택이 될 가능성이 있는 슬롯머신을 선택한다.
  두번째 전략은 최적의 슬롯머신을 찾기 위해 랜덤으로 탐험을 한다. 하지만, 탐험을 할때 꼭 랜덤이어야만 할까?? 좀 더 합리적으로 탐험을 할 수 없을까??

• 랜덤이 아닌 슬롯 머신이 최적이 될 수 있을만한 가능성을 수치로 계산 해서 가장 가능성이 있는 슬롯 머신을 선택하면 어떨까? 에서 시작이 되었다.

• 기본 그리디 알고리즘에서 수식이 추가되는데 이 수식이 의미하는것은, 해당 슬롯머신이 최적의 슬롯머신이 될 수도 있는 가능성이다. 가능성 혹은 불확실성이라고 할 수 있다.

• 네번째, 톰슨의 샘플링(Thompson's sampling) : 각 단계마다 표본을 추출(손잡이를 당김)하여 최고의 손잡이를 선택할 확률을 최대화한다. 어느것이 가장 좋은 손잡이인지 모른다(이것이 항상 문제이다). 그러나 연속적인 추출을 통해 얻는 수익을 관찰하면 더 많은 정보를 얻을 수 있따. 톰슨 샘플링은 베이즈 방식을 사용한다. 즉 베타분포를 사용하여 수익의 일부 사전 분포를 가정한다. 각 추출 정보가 누적되면서 정보가 업데이트 되어 다음번에 최고의 손잡이를 선택할 확률이 효과적으로 최적화 될 수 있다.

📈 정리

• 전통적 A/B 검정은 임의표본추출 과정을 기본으로 하기 때문에, 수익이 낮은 것을 너무 많이 시도할 수 있다.
• 이와 대조적으로 MAB는 실험 도중에 얻은 정보를 통합하고 수익이 낮은 것의 빈도를 줄이는 쪽으로 표본 추출 과정을 변경한다.
• 또한 두가지 이상의 처리를 효과적으로 다룰 수 있다.
• 추출확률을 수익이 낮은 처리에서 수익이 높으리라 추정되는 쪽으로 이동시키는 다양한 알고리즘이 있다.