2019년을 돌아보는 글
이 글의 주 소스 링크를 먼저 밝힙니다. 원작자에게 먼저 허락을 구하고 글을 작성했습니다.
https://www.kaggle.com/ruslankl/how-to-deal-with-multi-armed-bandit-problem
마케팅이든 아니면 의학적인 실험에서든 사용자에게 어떤 게 가장 좋은 것 인지 확인하는 방법은 무엇일까요?
바로 Multi Armed Bandit Algorithm입니다. 특히 Thompson Sampling이라는 기법과 같이 사용된다면 굉장히 효과적으로 가장 좋은 선택이 무엇인지 알아낼 수 있습니다.(실제로 추천 알고리즘의 Cold Start 문제 등에 효과적으로 적용되고 있는 알고리즘 중 하나입니다.)
마케팅 캠페인을 한다고 합시다. 마케팅 캠페인에서는 보통 CTR(Click Through Rate)을 이용해서 광고가 효과적인지 판단하곤 합니다.(물론 마케팅 회사마다 케이스 바이 케이스이긴 합니다만, 일단 CTR이라고 가정하고 넘어가 봅시다)
이야기가 나온김에 Regret도 같이 설명하자면, Regret은 가능한 CTR중 최고의 CTR과 지금 있는 CTR을 빼준 값입니다. 광고 A의 CTR이 0.1이고 B가 0.3이라고 할 때, A를 보여줬을 때 Regret은 $0.3 - 0.1 = 0.2$가 됩니다.
이제 광고에 대한 여러 안들이 있고, 어떤 광고가 가장 효과적인지 확인하려고 합니다. 하지만 광고에 대해서 어떤 사전 정보도 없다면 어떨까요?, 어떻게 여러 대안중에 효과적인 광고를 골라낼 수 있을까요? 이럴 때는 보통 사용하는 방법이 A/B test입니다. A/B 테스트는 말 그대로 A안과 B안을 노출시켜서(노출 비율은 정할 수 있다) 두 집단의 각각 다른 효과를 확인하기 위해서 사용되는 방법입니다. (wiki 설명 : A/B 테스트는 변수 A에 비해 대상이 변수 B에 대해 보이는 응답을 테스트하고, 두 변수 중 어떤 것이 더 효과적인지를 판단함으로써 단일 변수에 대한 두 가지 버전을 비교하는 방법이다, https://ko.wikipedia.org/wiki/A/B_%ED%85%8C%EC%8A%A4%ED%8A%B8)
‘아 그럼 A/B 테스트 하고 좋은 거 그냥 뽑으면 되겠네!’라고 생각할 수 있겠지만, 회사에서 이 테스팅을 진행한다고 생각해 봅시다. 주의할 점이 있습니다. A안을 기존에 하던 광고라고 하고 B를 실험하는 광고라고 해봅시다. A안 광고를 통해서는 꾸준히 매출을 기록하고 있고, B안은 아직 확실하지 않습니다. B가 아마 효과적이라고 하는데 아직 의심스럽습니다. 만약 테스팅을 하는데 B의 효과가 너무 떨어진다면 어떨까요?
이런 상황이 가능하지 않을까요? 그래서 MAB에서 중요한 것은, Exploration
과 Exploitaion
입니다. 한국어로 쉽게 말하면, 탐색하기와 뽑아먹기 입니다. 쉽게 탐색과 이용이라고 하겠습니다.
결국 A/B테스트이든, MAB이든 중요한 것은, 이 비율을 적절하게 맞춰서 탐색을 간결하게 하고 최대한 효과적으로 이용할 수 있는 대안을 선정하는 것입니다.
MAB, 즉 Multi Armed Bandit 알고리즘은 여러 대안들(슬롯머신의 Arm에서 이름을 따왔습니다)을 자동으로 실험하고 최적의 광고를 탐색과 이용사이에서 균형을 잡으면서 빠르게 찾는데 좋은 알고리즘입니다. Multi Armed Bandit 알고리즘들은 몇 가지 종류가 있습니다만 거의 모든 알고리즘은 위에서 소개한 Regret을 줄이는 것을 목표로 하고 있습니다.
주요 알고리즘들은 다음과 같습니다.
이 알고리즘들을 가지고 실험을 하기 전에 CTR을 사전에 설정해 둘 필요가 있습니다. 설정해둔 CTR로 광고가 주어졌을 때 클릭에 대한 시뮬레이션을 진행할 수 있습니다.
먼저 CTR을 비현실적이지만 0.45와 0.65로 설정하겠습니다.
1 | ACTUAL_CTR = [.45, .65] |
Random Selection은 말그대로 탐색을 하지 않고 동전 튕기기를 이용해서 앞면이면 광고0, 뒷면이면 광고1을 보여주는 알고리즘입니다. 정말 간단합니다!
1 | n=1000 |
1 | Ad #0 has been shown 48.4 % of the time. |
CTR이야 0.65, 0.45를 잘 찾아간다지만, 중요한 것은 Regret입니다. Regret함수를 보면 함수값이 거의 100대에 육박하는 것을 볼 수 있습니다. 좀 더 좋은 알고리즘을 통해서 Regret을 낮출 필요가 있겠습니다. 마케팅 예산이 무한대라면 그냥 마구잡이로 보여주고 CTR을 측정해서, 높은 CTR을 보이는 광고안을 선정하면 그만입니다. 하지만 일개 사원인 우리들은 예산을 최대한 아껴서 좋은 효율적인 광고를 통해 매출을 극대화 해야하는 사람들입니다. 그렇다면 좀 더 좋은 알고리즘을 살펴보겠습니다.
Epsilon Greedy 알고리즘은 Random Selection에서 한 단계 업그레이드 된 모델입니다.
이 알고리즘은 탐색과 이용의 비율을 어느정도 조정한다는 것이 큰 특징입니다.
로직은 다음과 같습니다.
1 | e = 0.05 |
1 | regret = 0 |
1 | Ad #0 has been shown 6.2 % of the time. |
Random Selection model보다는 훨씬 괜찮은 결과가 나왔습니다. 간단한데 결과는 훨씬 좋아지네요. 하지만 탐색시의 winning variant는 최적의 variant가 아닐 수 있습니다. 사실 suboptimal variant로 탐색 한 것입니다. 이것은 regret을 올리고 보상을 감소시킬 수 밖에 없습니다. 큰 수의 법칙에 따르면, 초기 시도를 많이 할수록, winning variant를 찾을 가능성이 커집니다. 하지만 마케팅에서는 큰 수의 법칙에 결코 따를 수가 없을 겁니다. 우리는 일개 사원…
이 알고리즘의 좋은 점은 어떤 비율을 설정할 수 있다는 것입니다. 각기 다른 epsilon값을 선택함으로써 얼마나 자주 winning ad를 보여줄 수 있는지 조정할 수 있는 것입니다.
좀 더 좋은 알고리즘을 살펴볼까요?
50% Exploration
50% Exploitation
Thompson Sampling의 탐색 부분은 Epsilon-greedy알고리즘보다 복잡합니다. 이 알고리즘은 단순히 epsilon을 정하는 것이 아니라, Beta distribution을 이용하기 때문입니다. 왜냐하면 광고를 클릭하는 것은 베르누의 과정에 속하기 때문입니다.(클릭했다, 안했다는 1,0으로 표현 가능합니다) 하지만 톰슨 샘플링은 일반적으로 어떤 분포, 어떤 파라미터에서든지 샘플링이 가능하다. 이게 가장 큰 장점 중 하나라고 생각합니다.
참고로 Beta 분포는 alpha와 beta 파라미터로 분포의 모양을 조절한다.(prior 조정 가능)
로직은 다음과 같습니다.
1 | regret = 0 |
1 | x = np.arange (0, 1, 0.01) |
1 | Ad #0 has been shown 4.2 % of the time. |
지금까지 본 regret중 가장 낮은 regret을 확인할 수 있습니다.
이 알고리즘은 지속적으로 탐색합니다. 자연스럽게 Beta distribution을 이용해 가장 가치가 높은 샘플을 가져와서 이용할 수 있습니다. Beta distribution Ad#1은 더 높고 좁은 분포를 갖고 있습니다. 이것은 샘플된 값들이 항상 Ad#0보다 높을 것이라는 것을 의미합니다. 결국 Ad#1이 우리가 원하는 광고임을 빠르게 파악할 수 있습니다.
알고리즘은 가장 높은 UCB가 나오는 variant를 선택합니다. UCB를 통해 가장 높은 보상이 나올 것이라고 생각되는 variant를 고르는 것입니다.
$$UCB = \bar x_i + \sqrt{\frac{2 \cdot \log{t}}{n}}$$
이 수식을 따르며 뒤에 term에 따라 UCB의 파생 알고리즘들이 등장하게 됩니다.
$\bar x_i$ CTR이 i번째 단계일 때,
$t$ - 모든 variant에 대해 impression을 다 더한 숫자이다.
$n$ - 선택된 variant에 대해 impression을 다 더한 숫자이다.
로직은 직관적입니다.
1 | regret = 0 |
1 | Ad #0 has been shown 19.2 % of the time. |
결과는 다음과 같습니다. Regret이 생각보다 높네요, UCB알고리즘도 현업에서 자주 사용하는 알고리즘입니다만, 이 알고리즘은 가장 기본적인 알고리즘이기 때문에 그런 것 같습니다.
이제 살펴봤던 모든 알고리즘의 성능을 비교해 볼 시간입니다. 기대가 되네요, 나온 결과를 시각화를 해서 살펴 보겠습니다.
1000번의 시도에 어떤 광고를 얼마나 노출시켰는 지에 대한 막대그래프입니다. Random Selection은 CTR이 낮은 광고를 너무 많이 노출 시켰네요, 그 다음은 UCB1, Epsilon Greedy, Thompson Sampling 순 입니다. Thompson Sampling이 가장 좋네요! 하지만 놀라운 것은 Epsilon Greedy입니다. 정말 간단한 알고리즘인데 성능이 좋군요. 다음 자료는 Regret에 대한 것입니다. 시도가 늘어날 수록, Random Selection이나 UCB는 쭉 쭉 증가하는 것이 보입니다. 하지만 Thomspon Sampling은 굉장히 안정적으로 Regret이 유지되네요. 마지막은 1000번의 시도에서 총 몇번의 클릭을 받았는가에 대한 시각화 자료입니다. 클릭이 많다면 더 효과적으로 실험을 하면서 광고를 했다고 할 수 있겠네요. 역시 Thompson Sampling이 가장 많은 클릭 수를 얻었습니다. 그 다음은 Epsilon Greedy, UCB1, Random Selection 순 입니다.물론 Regret이 낮다고 가장 높은 보상이 있는 것은 아닙니다. 이 실험에서는 우연히 Thompson Sampling이 Regret도 낮고, 높은 보상을 얻었습니다. 알고리즘은 적절한 광고를(right ads) 보여줄 뿐 이고, 유저가 클릭하는 것은 보장하지 않습니다.
일반적으로 Thompson Sampling이 좋은 결과를 보여줍니다. 하지만 다른 알고리즘을 보면서 어떻게, 그리고 언제 그 알고리즘이 유용할지 생각해봐야 합니다. 어떤 문제를 풀 지는 각 개인 마다 다르기 때문에, 여러 알고리즘들 중에서 문제에 적합한 것을 선택할 수 있어야 합니다. 어떤 사전 정보를 갖고 있고, 알고리즘 적용 후에 어떤 정보를 알고싶은지를 명확하게 설정하는 것이 더 중요하다고 할 수 있겠습니다.
일단 블로그부터 제대로 구축하자!
라는 계획으로 hexo 블로그를 만들었고, 여러 테마들을 돌려보면서 괜찮은 것들을 살펴봤습니다. 한 한달정도 블로그랑 씨름하다보니 어느정도 구축이 되었고, 배운 내용들을 글로 정리하기 시작했습니다.
사실 올해에는 취업 생각이 없었습니다. 데이터 이론이나 알고리즘 등 준비해야 할 것도 많다고 생각했고, 개인 프로젝트도 더 필요하다고 느꼈습니다. 하지만 3월에 상반기 대기업 취업 공고가 나니까 마음이 급해지기 시작했죠. ‘내가 공부는 정말 많이 했지만 내가 진짜 제대로 알고 있는걸까?’, ‘이 상태로 취업은 가능할까?’, ‘공부를 이렇게 하는게 맞나?’ 이런 고민들이었습니다.
이런 고민들로 3월부터 6월 동안 취업준비를 급하게 시작했습니다. 결국 데이터 관련 일은 데이터를 직접 만져봐야 얻는 게 있다는 결론을 내렸기 때문입니다. 이력서도 많이 쓰고 면접도 많이 봤습니다. 첫 면접부터 마지막 면접까지 하나하나 기억이 다 나네요, 쓰라렸지만 좋은 경험을 많이 했다고 생각합니다. 사실 상반기 회고를 하면서 면접에 관해서 글이 길어졌는데, 너무 무거운 내용들이 많아서 일단 나중에 정리해서 업로드 할 생각입니다. 이번 글은 조금 가벼운 느낌으로!
그래서 상반기 회고를 다시 하자면 저는 도서관에서 거의 살았었습니다. 아침 일찍 나가서 저녁 늦게 까지 책을 쌓아놓고 노트북 두들기면서 한 자리에만 있었습니다. 그때 공부를 하면서 느낀 건 공부를 오래하고 싶더라도 체력이 부족하면 불가능 하다는 것이었습니다. 운동도 시작했고, 식단 조절도 해보면서 건강을 챙겼습니다. 우연히 운동 좋아하는 후배들을 알게 되면서 좋은 습관들을 쌓게 된 것 같네요.
취업 준비도 준비지만 또 다른 좋은 습관을 들이려고 노력한 것은 글쓰는 습관이었습니다. 배운 내용을 혼자 공부해서 갖고 있는 것보다, 글을 쓰고 공유하고, 얘기하는 것이 저에게 훨씬 더 큰 가치를 가져다 줄 수 있겠구나 하는 생각이 들었습니다. 부족하지만 이론을 정리한 걸 글로 작성하고, 알고리즘 문제 푼 것들도 어떤 생각의 흐름으로 풀었는지 기록했습니다. 이외로 면접 준비하면서 이걸 다시 보게 되니까 정리하는데 도움이 많이 되는 것 같았습니다. 특히 이론에 관해서 글을 쓸때는 완벽하게 알지 못하면 글을 쓰지 못하기 때문에, 어디가 부족한지 스스로 알 수 있게 되어서 더 좋은 것 같습니다.
그 외에 상반기에 했던 것들은 다 취업 준비가 대부분이었던 것 같네요.
회고를 해보니 너무 정신없이 살았던 것 같습니다. 정리 안되고 정신없는 거 별로 안 좋아하는데 상반기를 정리해보니 제 자신이 정리 안하고 살았었네요. 하반기에는 계획을 제대로 세워서 하나씩 클리어 하는 재미로 살아봐야겠습니다.
상반기 회고를 두 번 해보니 얻어지는 것이 있었습니다. 사실 취업준비를 하면서 많이 지쳤었거든요, 데이터 얘기만 들어도 싫고, 개발이나 알고리즘, 코드만 봐도 어지럽고 도망치고 싶었습니다. 하지만 취업도 했고, 상반기를 냉철하게, 처절하게 다시 들여다보고 나니, 다시 시작할 힘이 나는 느낌입니다. 바닥에 다시 내려왔고, 어디부터 공부를 해야할지 이제 감이 잡히는 느낌입니다.
글또 3기를 하면서 가끔은 넋두리 같은, 오늘 같은 이야기를 하게 될 것 같고, 캐글 대회에 참여하고 잘 되거나, 안되었던 것들을 정리할 계획입니다. 또 일하면서 필요한 부분을 공부하면서, 예를들어 AWS(사실 GCP를 더 공부하고 싶었는데 ㅠㅠ 회사는 AWS를 쓰는군요…)나 Apache Spark, NoSQL(MongoDB) 등을 정리한 내용을 공유할 것 같습니다.
하반기에 계획했었던 일 중 하나가 글또 3기 들어가는 것이였는데요, 벌써 체크 하나하게 되어서 너무 기쁩니다. 최소 12개의 글을 쓰게 될텐데 그 과정이 의외로 도전적일 것 같아 재밌을 것 같네요. 도전적인 자세로 하반기를 살아봐야겠습니다. 내일은 월요일, 도전이 생각보다 꽤 빨리 시작되는 느낌입니다.