MAB기반 추천시스템 : Stochastic Bandits, CFB

Exploitation and Exploration in a Performance based Contextual Advertising System
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.297.8373&rep=rep1&type=pdf

 

Introduction

온라인 광고 시장은 굉장히 역동적이다. 실시간으로 어떤 광고를 송출해야할지 결정해야하기 때문이다.

광고는 광고주가 인벤토리에 따라 일정 클릭 수만큼 광고비를 지불한다. (CPC 방식이라고 부른다) * CPC : cost-per-click

이 때 한정된 인벤토리 내 최대의 성과를 낼 수 있는 광고를 선택해야만 한다.

기존에 집행해본 경험이 있는 광고와, 그렇지 않은 신규 광고 사이에서 어떤 광고를 보내야할지 결정한다.

여기서 Bandit 문제가 접목된다. 전자는 Exploitation, 후자는 Exploration이다.

​

오늘 리뷰할 논문은 온라인 광고에서의 EE(Exploitation vs Exploration) 전략을 취하는 알고리즘을 소개한다.

광고에서는 DA(Display Ads), 검색광고와 contextual 광고, 세 가지 타입이 있다.

논문은 그 중에서도 Contextual ad에 중점을 두고 있다.

​

앞서 살펴보았듯이 광고가 CPC 방식일 경우 광고 플랫폼은 수익을 최대화하기 위해 매번 인기있는 광고만을 걸게 된다.

논문에서는 이를 'Matthew effect'라고 하는데, 빈익빈 부익부처럼 기존에 걸어본적 있는 광고만이 계속 게재된다는 것이다.

하지만 광고 시장은 역동적이기 때문에 새로운 광고 컨텐츠가 지속적으로 유입된다.

이 상황에서 이러한 문제를 풀지 않을 경우 아래와 같은 문제들이 발생한다.

- 동일한 유저에게 같은 광고를 지속적으로 보여준다. 유저 경험이 좋지 않을 뿐더러 장기적으로 광고 클릭율을 떨어뜨린다.

- 단기간에 동일한 광고를 과대하게 노출할 경우 이 광고주는 짧은 시간내 예산을 사용하게 되는 반면,

덜 노출된 광고주의 경우 노출량 확보까지 오랫동안 기다려야하기 때문에 기획된 예산을 다 사용하지 못하게 되어 경제적 효용성을 떨어뜨린다.

​

이러한 이슈들을 해결하기 위해서는 적절히 탐색(exploration)하고, 적절히 수확(exploitation)할 줄 알아야한다.

EE 밸런스를 맞추는 알고리즘 중 가장 유명한 것은 단연 𝜀-greedy 알고리즘인데, 이 알고리즘은 optimal한 𝜀를 미리 정하기가 어렵다.

이 알고리즘의 대안으로 고안된 것이 𝜀-decreasing알고리즘인데, 초기에는 𝜀만큼 탐색하다가, 점점 𝜀값을 떨어뜨리는 것이다.

하지만 앞서 살펴보았듯이 새로운 광고가 지속적으로 유입되기 때문에, 우리는 장기적으로도 탐색을 어느정도 해야한다.

따라서 논문은 𝜀-greedy알고리즘을 보강하여 새로운 알고리즘을 제안한다.

---

Algorithm in short explanation

논문의 알고리즘은 간단하게 두 가지로 구성되어 있다.

1. 𝜀-greedy 알고리즘에서 한 단계 더 확장하여 𝜀값을 유동적으로 업데이트한다.

매 회차(iteration)마다 유한한 후보(candidates) 리스트 중에서 새로운 𝜀를 적절히 선정하기 위해 샘플링 과정을 추가한다.

2. 𝜀-greedy알고리즘에서 랜덤 탐색( 𝜀만큼 exploration하는) 전략을 좀 더 보강하였다.

역동적인 광고 시장의 특성을 반영하여 노출량에 관한 신뢰구간(confidence) metric 도입하였다.

어떤 광고를 더 탐색해야할지에 대해 이 metric을 사용하여 결정하게 된다. (UCB기반 MAB알고리즘과 유사하다.)

신뢰 구간이 어느 수준 이상으로 도달할 경우, 더 이상 탐색대상이 아닌 수확대상으로 분류하게 된다.

​

Related works

논문은 기본적으로 MAB 알고리즘을 기반으로 하고 있다. 그 중에서도 UCB알고리즘에 영감을 받았다고 한다.

UCB알고리즘은 굉장히 결정적(determinitstic)인 알고리즘인데, 이 알고리즘에 랜덤성(randomness)를 부여하는 방식으로 수정했다.

---

Click Feedback Model (CFB)

광고의 과거 최대 실적을 바탕으로 미래의 CTR을 예측하는 CFB모델을 소개해보고자 한다.

이 모델은 '노출(impression)'과 '클릭(click)', 두 이벤트를 중점으로 다룬다.

CFB모델은 특정 페이지를 중심으로 모든 광고들의 노출량과 클릭수를 집계(aggregation)한다.

이렇게 단일 광고가 아닌, 광고가 게재된 페이지 중심으로 이벤트를 합산하는 이유는 이렇게 연산한 CTR의 분산이 더 적기 때문에(노출량과 클릭수 모두 단일 광고보다 많기 때문에) 더 신뢰할 수 있는 수준의 CTR 예측치를 만들 수 있기 때문이다.

예를 들어 100,000번 노출되었는데 100번 클릭된 광고 A와 10번 노출로 1번 클릭된 광고 B 가 있을 때, A와 B간의 우위 비교가 어렵다.

페이지 단위로 합산하더라도 노출량과 클릭수가 많을 수록 더 CTR의 신뢰도가 올라가는데,

이처럼 feedback 기반 접근(CTR기반 접근 모델, CFB)을 하게 되면 앞서 언급한 Matthew effect를 피할 수 없게 된다.

CTR이 높은 광고만이 살아남을 것이고, 그 외 광고들은 소외된다.

​

이 단점을 보완하기 위해 결정론적(deterministic)이 아닌, 확률론적인(stochastic) 방법론을 제시한다.

CFB 모델은 모델 스코어에 따라 광고들을 랭킹하고, top 랭크에 있는 광고는 우수한 광고라고 정의한다.

하지만 낮은 랭크에 있는 광고도 선택할 수 있도록 기회를 주는 것이 확률론적인 방법론이 반영된 부분이다.

이 확률론적인 방법은 앞서 소개한 두 가지 알고리즘이다.

1. Exponentiated Gradient로 최적의 𝜀값을 학습

2. 랜덤 탐색 중에서도 적은 노출량의 광고에 좀 더 탐색 기회를 제공

---

1. 𝜀-greedy algorithm with EG(Exponentiated Gradient) Update

𝜀-greedy알고리즘은 우선 CFB모델 스코어에 따라 광고를 리스트업하고,

가장 좋은 rank에 있는 광고를 exploit, 그렇지 않은 광고 리스트 중 하나를 𝜀확률로 고르게 된다.

하지만 𝜀를 결정하는 것이 매우 어렵다. 어떻게 현명하게 𝜀를 고를 수 있을까?

𝜀를 임의로 결정하는 것보다 EG(Exponentiated Gradient)알고리즘에 따라 업데이트하는 방식을 고려해보자.

​

우선 𝜀가 한정된(finite) 후보군을 지니고 있다고 가정해야한다. 그 갯수를 임의의 T로 정한다.

𝜀와 함께 𝜀를 선정할 확률 P라는 변수를 도입한다. 초기에는 이 값이 1/T로 셋팅된다.

w는 𝜀의 성능(performance)를 평가하는 변수이다.

기본적으로 𝜀를 통해 클릭을 얻게 되면 w 값을 증가하는 방식이다.

p는 w값을 표준화하여 계산하는 방식이다.

​

부가적인 factor들이 도입되는데,

𝛽 와 𝜏는 w를 통해 p값을 계산하기 위해 사용되는 smoothing factor이다.

𝜅는 w의 regularization factor이다.

pseudo code로 알고리즘을 살펴보자.

input으로는 CFB 스코어에 따라 rank가 매겨진 a1부터 an까지의 광고 리스트가 들어오게 된다.

모델은 𝜀의 베르누이 분포에서 sampling을 통해 z값을 추출하고,

z값이 0일 경우* 탐색을 하게 되는데, 낮은 rank 리스트(L)에서 랜덤하게 광고 a를 추출하게 된다.

z값이 0이 아닐 경우* 높은 rank리스트(H)에서 랜덤하게 광고 a를 추출하게 되고, L혹은 H가 빈 리스트가 될때까지 반복한다.

* 이 부분이 조금 잘못된 것 같은데, 사실 z = 1일 때 탐색하는 것이 𝜀-greedy 알고리즘의 원리이다. 𝜀확률만큼 탐색하기 때문이다.

* 논문에서 if else 구문을 반대로 작성한 것 같다.

​

2. Confidence-based Exploration

두 번째 알고리즘은 앞서 살펴본 UCB에서 영감을 받은 신뢰도 기반 탐색 광고 선정 방식이다.

낮은 신뢰도를 지닌 광고를 좀 더 탐색할 수 있는 기회를 주는데, 이 때 사용되는 metric은 단순하게 노출량 기반 metric이다.

이 알고리즘은 𝜀값을 적절하게 선택하도록 결정하는데, 앞서 정의한 factor들을 업데이트하는 프로세스를 담고 있다.

우선 특정 𝜀값이 선택될 확률인 p를 초기화한다. 𝜀의 갯수가 T라고 했을 때, 가능한 경우의 수인 1/T를 초기값으로 정한다.

𝜀에 대한 성능을 트래킹하는 T개의 weight w는 모두 1로 셋팅된다.

p1부터 pT에서 sample d를 랜덤하게 고르고, 𝜀d로 알고리즘 1번을 수행한다.

유저로부터 feedback(클릭)을 받고 w와 p를 업데이트하는데, 그 업데이트 과정에 Exponential Gradient가 사용된다.

​

​

정리하면 전체적인 알고리즘 수행 순서는 아래와 같다.

1. 광고 리스트 {a1, ..., an} 을 CFB스코어(CTR)에 따라 rank를 매긴다.

2. 일정 수익을 보장하기 위해 성능이 좋은 광고 r개를 미리 예약해두고, 그 외 q개의 탐색 광고 개수를 정하여 모델에게 전해준다.

3. rank결과 목록을 모델로 input하면 모델은 알고리즘에 따라 𝜀를 정한다.

4. T개의 𝜀 후보군에 각각 매핑된 p확률 리스트에서 샘플링을 통해 𝜀를 정한다.

5. 𝜀의 베르누이 분포에서 샘플링하여 그 값에 따라 탐색과 수확을 하여 예비 광고 리스트를 소진한다.

6. 유저로부터 feedback(클릭)을 받아 알고리즘에 사용되는 factor들을 업데이트한다. (w, p)

이를 pseudo code로 정리하면 아래와 같다.

---

Review

이쯤되면 궁금한 점이 두 가지가 생긴다.

1) 일정 수익을 보장하는 성능이 좋은 광고 개와 그렇지 않은 광고 q개는 어떤 기준으로 정하는 것이며

2) 𝜀의 후보군은 어떻게 정할까?

​

1)에 대한 응답은 이렇다. 우선 CFB모델의 결과에 따라 가장 좋은 성과를 내는 광고는 수확 대상으로 빼둔다.

그 외 광고들을 한 데 섞어 CFB모델 스코어의 신뢰도를 계산한다.

이 때 신뢰도는 각 광고의 노출량(impression)에 비례하도록 설계되어있다.

탐색 대상 광고 리스트들은 CFB모델 스코어의 신뢰도에 따라 낮은 신뢰도를 지닌 광고일수록 더 선택되도록 구성된다.

만약 노출량이 일정 수준 이상으로 도달하게 되면 해당 광고는 탐색이 아닌 수확 대상에 포함된다.

​

2)에 대한 답은 논문에서 찾을 수 없는 것 같다.

실험 결과를 담은 섹션을 보니 경험에 의해서 정하는 factor가 많은 것 같았는데(r, q 등) 그에 대한 설명이 조금 부족해서 아쉬웠다.

​

논문 내용을 다시 정리해보자면, 온라인 광고 마켓팅 시장에서 적절한 광고 선정을 할 수 있는 알고리즘에 bandit을 적용해본 논문이었다.

탐색과 수확 사이의 밸런스를 정하는 데에 있어 두 가지 알고리즘을 도입했고,

첫째는 𝜀-greedy알고리즘에 따라 𝜀확률만큼 탐색하는 것인데, Optimal 𝜀를 찾기 위해 Exponential Gradient방법을 사용한다.

둘째는 신뢰도(Confidence) 방식으로 탐색함에 있어 랜덤성을 추가하는 것인데, 신뢰도가 낮은(여기서는 노출량이 낮은) 광고에 대해 더 탐색할 기회를 제공해준다.

첫번째 알고리즘은 𝜀-greedy알고리즘의 가장 중요한 파라미터인 𝜀값을 Optimal하게 찾아나가는 학습 방법을 소개한 것이고,

두번째 알고리즘은 𝜀-greedy알고리즘의 탐색은 단순히 랜덤하게 뽑는 것인데, 이를 개선하여 노출량이 적은 광고를 더 탐색할 기회를 제공했다.

​

이 논문은 역동적으로 변하는 광고 마켓팅 시장을 위해 개발된 알고리즘을 담고 있다.

광고가 지속적으로 유입되고 인기 있는 광고만이 계속해서 추천되는 필터 버블을 막기 위해 제안되었다.

조금 오래된 논문이다 보니 유저의 선호에 따른 추천이라기 보다는, 가장 단순한 𝜀-greedy bandit 알고리즘을 좀 더 개선하는 방향을 제시하였다.

이전에 살펴본 COFIBA모델과는 달리 context나 유저의 선호에 대한 정보를 사용하진 않는다.

단순히 클릭/미클릭의 feedback 요인만 있고, 이에 따라 알고리즘의 파라미터를 어떻게 optimal하게 찾아나갈지에 대해 고민하고 있다.