광고 알고리즘 최적화시도
초기 스타트업에 있다 보면 이것저것 혼자 해야할일이 많다. 최근에는 광고 시스템을 CLAUDE 와 함께 구축했는데 광고 서빙알고리즘을 도입해야했다. 기존에는 어떤 상품(소재)가 잘 탈지 모르기 때문에 "라운드 로빈"[^1] 방식으로 최대한 각 광고가 균등한 기회를 가지고 유저에게 노출될 수 있도록 알고리즘을 구성했다.
라운드로빈 방식의 장점은 기간이 같은 프레임안에서의 모든 광고가 균일하게 노출될 수 있다는 점이다. 단점으로는 광고로서 매력이 없는 소재가 계속해서 균일한 노출 시간을 차지하게 된다는 것이다. 본질적으로 광고란 "특정 그룹에게 노출될 시간을 특정 소재가 점유하는 것" 인데, 라운드로빈 방식은 특정 그룹에게 매력적이지 않을수도 있는데 해당 시간을 점유하게 된다. 그렇다면 어떤 알고리즘이 좋을까? 생각하다가 최근에 지인분인 쿠킴님이 적으신 MAB 알고리즘 시리즈 가 생각났다.
여기서 MAB(Multi-Armed Bandit Machine) 의 탐색과 활용에 관한 설명이 나오면서 톰슨 샘플링이라는 개념이 등장한다. 이 알고리즘을 이용하면 준-실시간으로 매력적인 광고를 서빙할 수 있다는 생각이 들어 적용해보아야겠다는 생각이 들었다. 일단, 구현하기에 앞서 왜 이 통계학적인 개념이 매력적인 광고를 서빙할 확률이 높은지 이해해 보자.
베이지안 추론(Bayesian Inference)
요즘 AI 로 확률과 통계가 조금 일반인에게 익숙해졌으므로 들어본 분들이 있을거라고 생각됩니다. 베이지안은 기존의 빈도주의 확률과는 다르게 "확률 자체도 불확실하니, 확률도 분포[^2]로 해석해야 된다" 라는 입장입니다.
예를 들면, 기존의 빈도주의에서는 아래와 같은 결과를 보면 53% 의 확률이네 라고 예상합니다.
동전을 100번 던져서 앞면이 53번 나왔다면, "이 동전의 앞면이 나올 확률은 0.53 입니다
하지만 베이지안식으로 접근해보면 아래와 같이 해석됩니다.
"이 동전의 앞면이 나올 확률이 정확히 무엇인지는 아무도 모른다.
하지만 우리가 가진 데이터(100번 던져서 53번 나옴)를 바탕으로 볼 때
가장 가능성이 높은 값은 0.53 부근이고, 0.51이나 0.55일 가능성도 꽤 있으며, 0.9일 가능성은 거의 없다"
즉, 베이지안 접근법에는 "어떠한 결과가 나올 확률이 정확하지 않을 수 있다" 가 근간이므로 분포로 나타나게 됩니다. 위에 사진을 보면 알수 있듯이 50% 부근에 밀도가 다른 부분에 비해 높음을 알수 있습니다.
사전지식과 사전 분포
따라서 베이지안 접근법에는 어느정도의 사전 지식(Prior Knowledge) 가 근간에 있음을 알 수 있습니다. 이러한 사전 지식을 분포로 나타낸것을 사전 분포(Prior Distribution) 라고 합니다.
그렇다면 광고의 CTR 을 예측하는 통계적 모델을 구성한다면 어떻게 사전지식을 구성해야할까요? 기존의 빈도주의적 접근에서는 클릭/클릭안함이 0/0 이므로 아직 정의 불가라고 할 수 있습니다. 베이지안식 사고에서는 나이브하게 "어떤 확률일지는 모르지만 0 ~ 100% 사이값일거야, 극단적인 값보다는 중간값으로 둬보자" 혹은 "이미 알고있는 우리 시스템의 평균 CTR" 이라고 추정하고 분포를 그려볼수 있습니다.
이렇게 0 ~ 100% 까지의 범위가 확실하고, 광고의 클릭이 성공/실패를 가를 수 있을때 쉽게 사용할수 있는 분포가 베타 분포(Beta Distribution) 입니다. 이해를 더 쉽게하기 위해 베타 분포에 관한 설명을 더 해보도록 하겠습니다. 베타분포는 인자값으로 알파(성공), 베타(실패) 값을 받습니다.
Beta(A, B)
만약 초기에 광고를 서빙하지 않은 상태라 성공과 실패 두개의 값이 없다면 어떻게 해야할까요? 위에서 이야기했듯 사전지식이 필요하기 때문에 Beta(알파 + 1, 베타 + 1) 로 값을 세팅합니다.
이렇게 세팅하는 이유는 위와 같이 세팅하고 그래프를 그리게 되면 모든 구간에서 균일하게 됩니다. 즉, 아무런 정보를 알지 못한다고 이야기하는 것과 마찬가지죠.
그렇다면 광고를 수행하다보니 Beta(2, 98) 이 되면 그래프가 어떻게 변할까요. 그래프의 확률 밀도가 0.1 ~ 0.2 부근에 집중되어 있음을 확인할 수 있습니다. 아직 0.2 일 확률이 그다지 높은 것은 아니지요. 그렇다면 시횡 횟수를 늘려 Beta(200, 9800) 이면 그래프가 어떨까요?
0.2 부근으로 엄청 뾰족하게 되어있음을 확인할 수 있습니다. 즉, 상대적으로 다른 구간에 비해 CTR 이 2%일 확률이 높은 것이죠. 즉, 시행횟수가 많아질수록 점점 특정 확률구간으로 집중되는 것을 확인할 수 있습니다.
Samples from Beta(2, 98):
['0.0053', '0.0291', '0.0198', '0.0173', '0.0327', '0.0108', '0.0362', '0.0092', '0.0153', '0.0065']
Samples from Beta(200, 9800):
['0.0179', '0.0187', '0.0196', '0.0209', '0.0204', '0.0198', '0.0187', '0.0221', '0.0186', '0.0186']
확인을 위해 해당 분포에서 랜덤으로 값을 뽑아보면 (2, 98) 인 경우에는 0.00~0.03 까지도 값이 벌어지는 반면에 (200, 9800) 의 경우에는 0.01~0.02 정도임을 알수 있습니다.
그래프로 그려보면 확실하게 보이는 것을 확인할 수 있습니다. 즉, 샘플링을 계속 해보면 CTR = 2% 부근으로 갈 확률이 상대적으로 높은 것이죠. 그렇다면 이러한 방법을 통해서 어떻게 광고시스템의 알고리즘을 조금 더 강화해볼 수 있을까요?
톰슨 샘플링
톰슨 샘플링은 이러한 분포를 이용해서 높은 값을 뽑아내는 방법입니다. 예를 들어 아래와 같은 상황이라고 가정해보겠습니다.
광고 A => Beta(2, 98)
광고 B => Beta(1, 9)
광고 C => Beta(300, 9700)
위와 같은 상황에서 샘플링을 했을때 가장 값이 높은 광고를 뽑는다고 해봅시다. 10번 뽑았더니 아래와 같은 결과가 나왔습니다.
10 Sampled CTRs from Ad A: Beta(2, 98):
['0.0094', '0.0257', '0.0509', '0.0149', '0.0400', '0.0062', '0.0177', '0.0187', '0.0124', '0.0133']
10 Sampled CTRs from Ad B: Beta(1, 9):
['0.0204', '0.0481', '0.0264', '0.3570', '0.2477', '0.1423', '0.2239', '0.3158', '0.0995', '0.1214']
10 Sampled CTRs from Ad C: Beta(300, 9700):
['0.0317', '0.0311', '0.0302', '0.0334', '0.0301', '0.0302', '0.0300', '0.0302', '0.0306', '0.0319']
결과를 보면 Beta(1, 9) 일때 유독 값의 범위가 넓고, 시행에서 높은 값을 자주얻었음을 확인할 수 있습니다. 이러한 이유는 무엇일까요? 아직 시행횟수가 높지 않기 때문에 뾰족하지 않고 무딘 언덕을 가졌기 때문입니다.
10 Sampled CTRs from Ad A: Beta(2, 98):
['0.0091', '0.0118', '0.0091', '0.0105', '0.0104', '0.0098', '0.0098', '0.0105', '0.0099', '0.0084']
10 Sampled CTRs from Ad B: Beta(1, 9):
['0.0207', '0.0193', '0.0214', '0.0178', '0.0204', '0.0189', '0.0193', '0.0208', '0.0223', '0.0209']
10 Sampled CTRs from Ad C: Beta(300, 9700):
['0.0304', '0.0280', '0.0292', '0.0275', '0.0304', '0.0297', '0.0307', '0.0321', '0.0287', '0.0313']
이렇게 시행을 반복했더니 아래와 같이 알파와 베타가 변했다고 해봅시다. 이제는 높은 확률로 C 광고가 높은값을 얻고 있음을 알수 있습니다. 즉, 시행횟수가 낮을때는 탐색(Exploration) 이 큰 영역을 가지고 있기 때문에 가끔 혹은 대부분의 경우 이길수도 있지만, 시행횟수가 높아질수록 기존의 높은 값을 활용(Exploitation) 하는 경향성이 강해지는 것이죠. 즉, 분포를 이용하기 때문에 자연스럽게 이렇게 탐색과 활용이 적용되게 됩니다.
적용
많은 부분을 비용 및 관리적인 부분때문에 스케일 있도록 적용하지는 못했지만 일단 실험을 위해 50:50 으로 라운드로빈과 톰슨샘플링을 이용한 광고를 유저들에게 서빙했습니다. 50:50 의 과정에서는 hash function 과 modular 를 이용해 각 유저가 두개의 버킷중 하나에 들어가도록 구현하였습니다.
아직 많은 데이터가 들어가지 않았지만 상당히 기존대비 데이터가 개선되었음을 알수 있습니다. (기존이 형편없었을수도..)
마치며
실무적인 부분보다 조금 더 이론적인 부분에 집중해서 글을 작성해보았습니다. 이론적인 부분에 대해서 저 같은 수포자들에게 조금 더 좋은 설명이 있으면 좋겠다 싶어서 조금 더 집중해서 작성해보았습니다. 운영하다보니 쿠킴님 블로그에서 언급하신 문제들이 조금씩 보이는데 해결하고 나서 또 위키에 정리해보도록 하겠습니다.
[^1]: "차례로 돌아가며 라는 뜻으로" 4개의 팀이 있을 때 A–B, A–C, A–D, B–C, B–D, C–D처럼 모든 팀이 서로 한 번씩 맞붙는 형식의 경기 방식이 라운드 로빈의 전형적인 예시이다. [^2]:
어떤 변수가 특정한 여러 값들이나 일정한 구간 사이에서 퍼져 있는 모양을 분포(distribution)라고 부를 수 있다면, 확률분포는 어떤 확률변수가 그 확률함수에 의거하여 퍼져 있는 모양이라고 말할 수 있다.
