엠에이비, 멀리암드밴딧이라고 부릅니다.
“팔 여러 개 달린 산적” “Multi Armed Bandit”은 슬롯머신의 별명입니다.
이름처럼 “어떤 슬롯 머신의 팔을 당겨야 돈을 딸 수 있는가?” 와 같은 문제를 풀기위한 방법입니다.
이 알고리즘은 강화학습의 일종으로 봐주기도 하는데 엄밀히 말하면 강화학습에 넣지는 않습니다.
하지만 상당히 간단하고 쓸만하고 강화학습의 개념을 익히기 좋기 때문에 강화학습을 설명할 때 가장 먼저 설명하는 것이기도 합니다.
이 문제의 전제 조건이 있는데 한 번에 하나의 슬롯머신의 팔을 당길 수 있다는 것입니다.
그래서 동시에 모든 슬롯머신의 팔을 당겨서 그리고 여러번 당겨서 어떤 슬롯머신이 돈을 딸 학률이 높은지 알아낼 수 없습니다.
그래서 한 번에 하나씩만 선택해서 돈을 최대한 많이 따는 것이 이 문제의 푸는 목적입니다.
복잡한 공식은 여기에 안 적겠습니다. 구글에서 찾아보시면 수식과 코드가 다 있습니다. :D
첫번째 방법. Greedy 욕심쟁이
모든 슬롯머신에 순차적으로 한 번씩 팔을 내려봅니다. 그래서 돈을 못땄다면 다시 한 번씩 다 팔을 내려봅니다.
몇번을 수행한 후에 딴 돈이 가장 많은 슬롯머신에게 계속해서 몰빵합니다.
이게 Greedy 방식입니다.
단순하고 조금 무식한 방법입니다.
두번째 방법. epsilon
Greedy 방법을 사용하되 무작정 사용하지 않고 랜덤으로 팔을 당길 확률을 정해놓습니다.
만약 50%의 확률로 랜덤을 고르겠다고 하면 한 번은 지금까지 가장 돈을 많이 딴 슬롯머신을 당기고 한 번은 랜덤으로 아무것이나 고르는 방법입니다.
그나마 다른 것들에게 기회를 준다는 것 때문에 낫습니다.
epsilon이라는 이름은 랜덤으로 고를 확률값을 epsilon이라고 이름을 붙여서 부르기 때문입니다.
세번째 방법. UCB(Upper-Confidence-Bound)
위의 epsilon에서 약간의 공식을 주어서 랜덤 찬스가 왔을 때
무조건 랜덤으로 어떤 슬롯머신을 팔을 다기지 않고
덜 뽑혔던 슬롯머신에 가중치를 두어서 더 뽑아서 팔을 내려줍니다.
네번째 방법. Tompson sampling
톰슨 샘플링은 설명을 하면 조금 복잡해지는데 확률 분포 중 하나인 베타분포를 이용해서 확률이 가장 높은 것을 선택하는 것입니다.
베타분포 함수에 선택된 횟수와 돈을 딴 횟수를 입력하면 베타분포를 각각 구할 수 있고 그 베타분포를 확률 분포로 이용해서 값을 구하면 선택할 것을 찾을 수 있습니다.
저장된 데이터를 이용할 수 있는 장점이 있고 UCB 보다 성능이 조금 더 좋아서 온라인 추천 시스템에서 많이 이용되고 있습니다.
A/B 테스트와 MAB의 관계
A/B 테스트는 통계학의 실험계획법 중 하나 인데 2개 또는 2개 이상의 그룹을 동일한 수(최대한 비슷한 수) 만큼 각각 분할해서 한쪽에만 다른 처리를 해서 두 그룹의 차이를 보는 방법입니다
온라인에서는 흔히 버킷테스트라고 하는 방법입니다.
예를 들어 광고배너가 있는데 원래 배너는 테두리가 하얀색인데 테두리를 빨간색으로 바꿨을 때 사람들이 어떤 것을 클릭을 더 많이 하는지 알아 보고 싶을 때 같은 경우에 합니다.
A/B 테스트가 오랫동안 사용한 방법이기 때문에 잘 알려져 있지만 문제는 두 그룹을 방해받지 않게 불한하는 방법이 상당히 어렵고 두 그룹의 차이를 알아보는 방법이 데이터의 양상과 원래 데이터의 특성에 따라 여러가지 통계적인 방법을 써야하는 데 실수로 잘못된 방법으로 확인을 했다고 하더라도 그 실수를 알아내기 어렵다는 문제가 있습니다.
A/B 테스트를 하는 것은 많이 어렵지 않지만 A/B테스트의 결과를 해석하는 것은 매우 숙련된 통계학자가 필요하고 시간도 많이 걸립니다.
그래서 A/B 테스트를 하지 않고 각각 반응을 그대로 볼 수 있는 어떤 환경이 있다면 그 환경에서는 각각 매번의 결과에 따라서 결과가 좋은 것에 점수를 더 줘서 그것을 선택하게 만드는 방법을 쓰자는 것입니다.
그래서 MAB는 온라인 시스템의 추천시스템이나 평가에 굉장히 적합합니다.
광고시스템과 MAB
한 번에 5개의 제품을 동시에 보여지는 광고 이미지가 있다고 가정합니다.
사용자 별, 또는 사용자 그룹별로 어떤 제품에 더 관심을 가지는 지를 보고 클릭을 많이 하는 제품을 MAB에 의해서 더 많이 노출한다고 하겠습니다.
흔히 쓰는 방법이지만 이게 문제가 좀 있습니다.
- 선택할 제품이 매우 많은 경우에는 못합니다. 아마도 제품의 카테고리가 있고 그것들 중에 가장 잘 팔리는가 하는 전략을 취할 수 있지만 상식적으로 좋은 방법은 아닐 것입니다.
- 선호도는 계절성 효과, 요일 효과, 캠페인에 피로도에 따라 달라집니다. 슬롯머신 처럼 확률이 안변한다는 가정을 두기가 좀 어렵습니다. 변동이 너무 많습니다.
- 또 가중치를 변경하는 것 때문에 생기는 문제가 파생적으로 생기는데
- 쿠키로 인해 신규 및 재이용자의 분포에 영향을 미칩니다.
- 변화에 대한 적응이 느리기 때문에 인해 관성때문에 결과가 왜곡될 수 있습니다.
아주 단순한 경우에만 사용이 가능하며 복잡한 시스템으은 오히려 결과를 왜곡할 수 있습니다.
저렇게 선택한 것이 여전히 가장 좋은 방법 또는 그리 좋은 선택이 아닐 수도 있겠지만 그 자체를 확실하게 확인 못합니다. 이건 다른 알고리즘도 동일한 문제이긴 합니다만.
