A/B 테스트를 보완하는 Multi-Armed Bandit(MAB) 알고리즘

아마 인터넷 비즈니스나 인터넷 광고사업을 하는 사업자라면 노출하는 광고의 효율이나 웹 페이지 변경에 따른 사용자 반응을 파악하기 위하여 몇 가지 후보를 사용자들에게 노출해 측정하고 판단하는 A/B 테스트에 대해서 들어본 적이 있을 것이다. 이 글은 최근 A/B 테스트가 가진 문제점을 해결할 수 있다고 해서 관심을 끌고 있는 Multi-Armed Bandit 알고리즘에 대한 소개이다.

Multi-Armed Bandit (직역하자면 팔 여러 개 달린 도둑놈 정도 되겠다. 이하 글에서는 MAB로 부르겠다) 알고리즘은 간단히 Bandit 알고리즘이라 부르기도 한다. 의미적으로는 Explore/Exploit Dilemma (탐색/획득 문제 또는 딜레마)라고 부르기도 하는데 사실 MAB이라는 말은 슬롯머신을 One-Armed bandit (외팔이 도둑놈, 슬롯머신에 있는 손잡이를 지칭)이라고 부르는 데서 기인한 재미있는 이름이다.

정확한 승률을 알지 못하는 여러 대의 슬롯머신을 가지고 도박을 할 때 가장 많은 돈을 따기 위해서 어떤 전략(알고리즘)을 가지고 게임을 해야 가장 많은 돈을 딸 수 있을 것인가 하는 문제를 빗대어서 잡아당길 수 있는 손잡이를 여러 개 가진 슬롯머신을 MAB이라고 부르게 된 것이다.

사람 사는 인생사처럼 어떤 선택의 기로에 섰을 때 비슷한 고민을 하게 되는 것과 같은 이치라고 할 수 있다. 좀 더 자세히 설명하면 이렇다. 우리가 처음 슬롯머신을 가지고 게임을 시작할 때 각각의 슬롯머신에 대한 승률을 전혀 짐작할 수 없다. 그렇다고 가지고 있는 돈이 무한정 있어서 모든 슬롯머신을 다 해볼 수도 없다. 뿐만 아니라 같은 슬롯머신이라도 승률은 수시로 바뀌기 마련이다. 이렇듯 우리가 살아가면서 무언가를 선택하고 결정할 때마다 부딪히는 바로 그 고민거리와 마찬가지다. 슬롯머신을 한번 잡아당긴다는 것은 주어진 그 결과를 정확히 알 수 없는 어떤 선택지라고 생각하면 이해가 쉽게 될 것이다.

물론 내가 돈과 시간이 무한정으로 있다면 (그럼 도박을 할 이유가 전혀 없겠지만) 주어진 모든 슬롯머신에서 미리 여러 번 게임을 다 해보고 나서 각각의 슬롯머신에 대한 승률을 정확히 파악할 수 있다면야 그 이후에 가장 돈을 가장 많이 딸 수 있는 슬롯머신에서 게임을 하면 될 것이다. 그러다가 승률이 떨어지는가 싶으면 다시 나머지 슬롯머신에서 게임을 해봐서 가장 좋은 승률을 가진 슬롯머신을 다시 선택하고 이를 반복하다 보면 가장 많은 돈을 딸 수 있을 것이다. (인생도 이렇게 여러 번 살아보면 좋으련만)

하지만 현실은 한정된 돈과 시간을 가지고 가장 좋은 승률을 가진 슬롯머신을 선택하면서(정확히 말하면 대략 짐작하면서) 모든 게임을 마쳤을 때 가장 많은 돈을 딸 수 있는 전략(알고리즘)을 찾는 것이다. 이것이 바로 MAB 알고리즘 문제이다.

여기서 탐색과 획득이라는 과정이 반복된다. 각 슬롯머신의 승률을 확인하기 위한 과정을 탐색이라고 할 수 있는데 이때 가장 높은 승률을 가진 슬롯머신을 파악하기 위해서 플레이하는 과정이다. 따라서 승률이 낮은 슬롯머신으로 플레이해보는 것을 피할 수는 없다. 누가 승률이 높은지 알아내야 하니까. 반면 획득은 가장 높은 승률을 가진 것으로 예상되는 슬롯머신을 선택해서 본격적으로 돈을 따는 과정이라 볼 수 있다. 어떤 과정을 치르든 두 과정 모두 비용이 발생하고 게임 할 수 있는 횟수는 점점 줄어들기 때문에 각각의 횟수와 선택을 어떻게 조정하느냐에 따라 전체적으로 최대로 돈을 딸 수 있는 가능성이 달라질 수 있는 것이다.

정보도 얻어야 하고 그래야 가장 좋은 승률을 가진 슬롯머신을 선택할 수 있기 때문에 두 가지 과정이 반드시 필요하며, 나머지 한가지 과정을 완전히 배제해서는 원하는 결과를 얻을 수 없다. 이 때문에 ‘탐색/획득 딜레마’라고도 부르는 것이다.

관련 자료를 찾아보면 이 문제는 1933년까지 거슬러 올라가게 된다. 어떻게 하면 여러 자원을 여러 프로젝트에 효과적으로 배분할 것인지를 모델링할 수 있을 것인가라는 연구에서 시작되었다. 그래서 2차 세계대전 때 연합군 과학자들도 이 문제를 어떻게 하면 잘 풀 수 있을지 연구했지만 너무 풀기 어려운 문제라고 생각되었는지 독일 과학자들도 이 문제를 연구하는 데 시간을 낭비(?)할 수 있도록 이 문제를 독일 쪽에 일부러 흘려 보내자는 제안도 있었다고 한다.

하지만 최근 야후!, 구글과 같은 인터넷 회사에서 이러한 Bandit 알고리즘을 웹 페이지 추천, 광고추천 및 분석 도구에 도입한 사례들이 등장하면서 다시금 주목받게 되었다. 이론적으로 보면 A/B 테스트라는 것을 대체하거나 포용할 수 있는 상위 개념의 테스트 방법을 제안하고 있기 때문에 이미 구글 애널리틱스에는 이 알고리즘을 이용한 테스트 도구를 제공하고 있다. 아마 Bandit 알고리즘이 대중에게 알려지게 된 것은 구글 애널리틱 서비스 제공하면서 그 계기가 마련된 것은 아닌가 짐작된다.

참고 : 다중 슬롯머신 실험

잘 알려지다시피 A/B 테스트는 인터넷이나 앱 서비스를 하는 여러 회사에서 새로운 기능이나 UI/UX에 대한 고객 반응을 파악하거나 더 좋은 최종안을 결정할 때 가장 많이 사용하는 방법이다. 하지만 비교군의 UX/UI 또는 광고 품질에서 큰 차이가 나게 되면 테스트하는 기간 중 일정 비율만큼 더 나쁜 서비스를 실 서비스에 지속적으로 노출할 수밖에 없고 테스트를 통해 사용자 평가를 하려다가 오히려 일부 사용자들에게 더 나쁜 경험을 주게 되어 고객 이탈이라는 최악의 결과를 만들어 낼 수도 있다. 그래서 항상 테스트 규모와 대상을 선정할 때 많은 주의가 필요하다.

이미지 출처 : Visual Website Optimizer

또한, 비교군 중 어떤 것은 서비스 노출 시간이 길어지면 길어질수록 잔존율(retention rate)이 점점 높아지는 경우도 있다. 너무 짧은 테스트 기간의 결과만을 가지고 전체 서비스에 서둘러 적용함으로써 올바른 선택을 하지 못하게 되는 경우도 발생하게 된다. 아마존도 사업 초기에 너무 빠른 의사 결정과 서비스 전환으로 오히려 좋지 않은 결과를 얻었다는 얘기도 들린다.

그래서 오랜 시간(사실상 회사가 서비스를 중단하기 전까지) 서비스를 노출해야 하는 인터넷 서비스에서는 이런 A/B 테스트의 단점을 어느 정도 보완해 줄 수 있는 것이 Bandit 알고리즘을 적용한 서비스 평가/추천 프레임워크이다.

이 분야에 대한 연구는 매우 오랫동안(1930년 이후) 그리고 광범위한 분야에 응용되고 있다. 인생에 있어서 한번 선택한 결과에 대한 평가를 함에 그 비용과 대가가 크듯이 일반적인 산업 분야에서는 비용이 많이 들 수밖에 없는 탐색(Explore) 과정이 인터넷 서비스에서는 상대적으로 비용이 적게 들고 Bandit 알고리즘이 active learning (매번 스스로 최적의 옵션을 선택)이면서 online learning (실시간으로 각 옵션의 결괏값을 가지고 평가)의 성격을 가지는 기계학습의 일종이라서 인터넷 서비스 기업들이 많은 관심을 가지게 된 것이다.

A/B 테스트에 비해서 상대적으로 어려운 수학적 이해가 필요해서인지 국내에서는 이를 활용한 실제 사례는 들어 본 적은 없지만 아마 대형 포털 사업자들은 내부적으로 이미 활용하고 있을 것으로 짐작된다. 반면 해외 사례의 경우에는 논문 중심으로 찾아보면 인터넷 서비스 적용 사례나 검색 엔진, SEO (검색 최적화) 등에 적용한 사례들이 제법 많이 소개되고 있다.

이 글에서는 Bandit 알고리즘에 대한 기본적인 개요 정도를 소개하고 있다보니 실제로 Bandit 문제를 풀기 위해 소개된 다양한 알고리즘들과 수학적인 증명은 자세히 설명하고 있지 않았다. 사실 전공자가 아니면 쉽게 이해하기 쉽지 않다. 따라서 통계에 대한 정확한 이해 없이 어설프게 사용하기보다는 차라리 A/B 테스트를 하는 것이 낫다고 볼 수 있고 함부로 실 서비스에 적용하지 말라는 의견들도 있다.

하지만 앞서 언급했듯이 Bandit 알고리즘은 기존 A/B 테스트의 문제점을 해결하기 위해 인터넷 서비스를 하는 이들이 관심을 가져 볼 만한 방법론이 아닐까 생각된다. 너무 이론적인 것에 매몰되지 않고 필요한 부분을 잘 활용하면 된다고 본다. 물론 본인들의 실 서비스에 적용하고 원하는 효과를 얻기 위해서는 고려해야 할 점 등이 적지 않지만 말이다.

가볍게 시작하고 싶다면 오라일리에서 출간한 ‘Bandit Algorithms for Website Optimization’ 책을 권하고 싶다. 100페이지도 안 되는 분량이고 이해하기 힘든 수식으로 가득 찬 논문과 달리 매우 알기 쉽게 설명하고 있다. 파이썬으로 된 코드들도 이해하기가 매우 쉽다. 참고로 저자는 ‘Machine Learning for Hackers’를 쓴 것으로도 유명한 사람이다. 소스코드 역시 깃허브에 잘 공개되어 있다.