[논문 리뷰] A Contextual-Bandit Approach to Personalized News Article Recommendation

Recommender System

이번 포스팅은 야후의 개인화 뉴스추천에 대한 내용이다. 해당 논문은 contextual bandit에 대해 다루고 있으며, bandit 계열 추천에서는 거의 바이블 같은 논문이다. 이번 포스팅에서는 contextual bandit 알고리즘이 개인화 추천을 구현하는 아이디어에 대해 집중적으로 살펴보도록 하겠다.

1. Introduction

논문은 웹(모바일) 컨텍스트에서의 개인화 추천 문제를 다룬다. 이는 구체적으로 ‘유저 방문 시점’에 ‘가장 적절한 아이템’을 추천해주는 내용이다. 하지만 웹(모바일)이라는 특성 상 특히 뉴스 같은 경우, 아이템(뉴스 기사)풀과 유저의 선호가 dynamic하게 변하는 성질이 있다. bandit 기반 추천은 유저에게 아이템을 추천한 후, 피드백(리워드)을 받아 추천 퀄리티를 점차 높여가는 방식으로, 이런 dynamic 성질에 잘 대응할 수 있다. 그 중 contextual bandit은 개인화 추천이 가능하므로 유저 선호 변화를 보다 면밀히 모델링 할 수 있는 특징이 있다.

2. Formulation & Related work

이제 본격적으로 $k-$armed contextual bandit 문제에 대해 살펴보겠다. 먼저 $k-$armed bandit(multi armed bandit)에 대한 이해가 필요한데, 해당 내용은 이전 포스팅을 참고 바란다. $k-$armed contextual bandit은 $k-$armed bandit의 일반화 버전이다. 여기에서는 두 문제가 어떤 차이가 있는지만 가볍게 살펴보도록 하겠다.

2.1 A Multi-armed Bandit Formulation

$K-$armed bandit

• 모든 arm에 대한 셋 $\mathcal{A_{t}}$는 모든 trial $t$에 대해 불변이다.
• 유저 피처 $user feature_{t}$는 모든 trial $t$에 대해 동일하다.

$k-$armed bandit은 위 두 조건을 따른다. 예를 들어 뉴스기사 추천 문제를 생각해 보자. 첫 번째 조건은 추천 대상이되는 뉴스기사 셋 $\mathcal{A_{t}}$가 고정임을 의미한다. 즉 trial이 반복 됨에 따라 새로운 기사가 추가되거나, 기존 기사가 제외되거나 하지 않는다. 두 번째 조건은 유저 피처가 모든 trial에 대해 동일하다는 것인데, 이는 곧 유저피처를 고려하지 않는다는 의미기도 하다. 따라서 $k-$armed bandit은 개인화 추천이 불가능하며 이를 가리켜 context-free bandit이라고도 한다. 이에는 $\epsilon-$greedy, UCB, bernoulli TS 등이 있다. 아직 trial이 무엇인지는 3장에서 context와 함께 구체적으로 설명하도록 하겠다.

$K-$armed contextual bandit

• 모든 arm에 대한 셋 $\mathcal{A_{t}}$는 trial $t$에 대해 가변이다.
• 유저 피처 $user feature_{t}$는 trial $t$에 따라 달라진다.

이어 $k-$armed contextual bandit 조건이다. 이는 $k-$armed bandit을 일반화한 것임을 알 수 있다. 먼저 추천 대상이 되는 뉴스기사 셋은 가변이다. 이는 실제로 뉴스기사의 dynamic 성질을 고려했을 때 현실적인 조건이기도 하다. 또한 위와 달리 유저피처를 고려하므로, 개인화 추천이 가능하며 이러한 특징을 가리켜 contextual bandit이라고도 한다.

정리하자면 두 문제의 차이는 ‘추천 대상셋 변화 여부’와 ‘유저 피처(context) 고려 여부’에 있다. 3장에서는 이 두 조건을 바탕으로 논문에서 제시하는 contextual bandit과, arm 추천 전략인 LinUCB 알고리즘에 대해 살펴보겠다.

3. Algorithm

모든 bandit 계열 알고리즘은 reward를 정의하는 것부터 시작한다. 따라서 이번 챕터에서는 contextual bandit이 reward를 어떻게 정의하고 모델링하는지 살펴볼 것이다. 나아가 reward의 기댓값을 추정하는 방법과 이를 바탕으로 LinUCB가 arm을 추천하는 방법에 대해 차례로 살펴보겠다. LinUCB는 reward 모델링시 arm 간의 파라미터 공유 여부에 따라 disjoint와 hybrid 계열로 나뉜다. disjoint는 개별 arm 별로 학습하는 반면, hybrid는 이 외에도 모든 arm이 공유하는 파라미터가 존재한다. 여기선 컨셉을 이해하는 것이 목적이므로 disjoint 계열만 자세히 보도록 하겠다.

3.1 LinUCB with Disjoint Linear Models

Reward(payoff) Modeling

앞서 contextual bandit이 context-free bandit과 달리 ‘개인화 추천’이 가능한 이유는 유저피처를 고려하기 때문이라 하였다. 이제 두 문제의 reward 모델을 비교해보며 이것이 무슨 말인지 살펴보자. 그 전에 먼저 reward를 정의해야 한다. 흔히 bandit 기반 추천시스템에서 reward는 item 클릭 여부(binary) 또는, item 스코어(continuous) 등으로 정의된다. 논문에서는 이를 아래와 같이 F1영역 기사의 클릭 여부로 정의하였다.

\[\begin{align*} \text{reward} \ \ r= \begin{cases} 1 & \text{clicked} \\ 0 & \text{otherwise} \end{cases} \end{align*}\]

context-free 계열의 알고리즘들은 reward 모델링에 주로 bernoulli 분포를 사용한다. 만약 내가 단순히 기사별 클릭률에 따른 추천만 한다면, 아래와 같은 bernoulli 분포로도 충분할 것이다.

\[\begin{align*} f(r) = p^r(1-p)^{1-r}, \ \ \ r=1 \ or \ 0 \end{align*}\]

하지만 ‘개인화’ 관점에선 어떨까? 예를 들어 성별이나 기사의 카테고리에 따른 유저 맞춤형 추천이 필요하다면, 조금 더 확장성 있고 정교한 모델이 필요할 것이다. 따라서 논문에서는 reward 모델을 다음과 같은 linear regression으로 정의하였다. regression 모델은 다양한 피처를 표현 수 있으므로, 개인화 요소를 표현하는데 보다 적합하기 때문이다.

\[\begin{align*} r_{t,a} = x^{T}_{t,a}\theta_{a}&+\epsilon_{a}, \ \ \epsilon_{a} \sim N(0, \sigma^2) \\ \therefore \ \ r_{t,a} \ &\sim N(x^{T}_{t,a}\theta_{a}, \ \sigma^2) \end{align*}\] \[\begin{align*} & \bullet \ r_{t,a}, \ \epsilon_{a} &(1\times 1 ) \ \text{dimension} \\ & \bullet \ x_{t,a} & (d\times 1) \ \text{dimension} \\ & \bullet \ \theta_{a} & (d\times 1) \ \text{dimension} \\ \end{align*} \\\]

이때 context란, 위 $x_{t,a}$ 벡터로 reward $r_{t,a}$를 예측하기 위한 피처벡터를 의미한다. 예를 들어 유저 성별과, 기사의 카테고리 정보를 context로 사용한다고 하자. 이때 성별은 남성, 기사의 카테고리는 스포츠로 가정했을 때, $x_{t,a}$는 아래와 같이 표현해 볼 수 있다.

\[\begin{align*} x_{t,a} &= \text{concat}(user feature_{t}, \ item feature) \\ &= \text{concat([male, female], [Sports, Health, Politics])} \\ &= [1,0,1,0,0] \end{align*} \\\]

여기서 잠깐 노테이션 $t,a$에 대해 살펴보자. 먼저 $a \in \mathcal{A_{t}}$는 각 기사를 가리키며, $t$는 앞서 trial이라 하였다. 특이한 점은 개인화 추천에 유저 노테이션이 따로 없다는 것이다. 그렇다면 $t$가 그 역할을 하는 것일까? 결론부터 말하자면 그렇다.

잠시 웹(모바일) 컨텍스트 관점에서 이야기를 해보자면, 웹(모바일)에서 trial $t$는 곧 ‘유저 방문’을 의미한다. 따라서 $t$에 어떤 유저가 방문하냐에 따라 $user feature_{t}$가 달라지기 때문에 $x_{t,a}$의 내용도 달라지게 된다. 여기선 단순히 성별을 예로 들었지만, 개별 유저 또는 특정 유저 그룹(ex. 연령대, 타겟그룹) 등 목적에 따라 다양한 유저 컨텍스트를 정의할 수 있다.

정리하자면 contextual bandit의 핵심은 reward 모델을 regression으로 정의해 유저 피처를 표현함으로써, 개인화 추천이 가능하도록 한 것이다. 위는 이해를 돕기 위한 단순 예시일 뿐, 논문에서는 다소 복잡한 엔지니어링을 사용해 user feature와 item feature의 차원을 모두 통일하였다. 이 부분은 별도의 포스팅을 통해 실험 세팅과 함께 보충해 보도록 하겠다.

E(reward) 추정

앞서 reward(클릭 여부) 분포를 linear regression으로 모델링 했음을 살펴봤다. 궁극적으로 우리가 해야할 일은, 각 유저(그룹) 별로 기사에 대한 클릭률을 계산해 적절한 기사를 추천해주는 것이다. 이때 클릭률은 다음과 같이 계산되며 이것이 곧 CTR이다.

\[\begin{align*} E(r_{t,a}|x_{t,a}) = x^{T}_{t,a}\theta_{a} \end{align*}\]

이제 우리가 해야할 일은 regression의 파라미터 $\theta$를 추정하는 것으로, 논문에서는 베이지안 방법을 사용한다. 아래는 $\theta$의 사후분포로, 사후분포가 정규분포일 때 베이지안 추정치는 평균과 동일하다.

\[\hat{\theta}_{a} | r_{t,a}, x_{t,a} \sim N(A^{-1}_{a}x_{t,a}r_{t,a}, \ A^{-1}_{a}), \ \ \ where \ \ A_{a}=x_{t,a}x_{t,a}^{T}+ kI, \ \ k>0\]

사후분포는 사전분포와 라이클리후드의 곱으로 다음과 같이 구할 수 있다. 여기서 $\theta$의 사전분포는 정규분포로 가정하였다.

\[\begin {align*} p(\theta|r,x) &\propto \ p(\theta)\ p(r|x,\theta) , \ \ \ \theta \sim N(0, \tau^2I) \\ & \propto \text{exp}[-\frac{1}{2} \theta^T \frac{1}{\tau^2} \theta] \text{exp}[-\frac{1}{2} (r-x^T\theta)^T \frac{1}{\sigma^2}(r-x^T\theta) ] \\ &= \text{exp}[-\frac{1}{2\sigma^2} (r-x^T\theta)^T(r-x^T\theta) -\frac{1}{2\tau^2} \rVert \theta \rVert_{2}^{2} \ ] \ \ \ \ \ \cdots \ (*) \\ & \propto \text{exp}[- ( (r-x^T\theta)^T(r-x^T\theta) + \frac{\sigma^2}{\tau^2}\theta^T\theta ) ] \\ & = \text{exp}[-(r^2 - rx^T\theta - \theta^Txr + \theta^Txx^T\theta + \frac{\sigma^2}{\tau^2}\theta^T\theta )] \\ & = \text{exp}[-(\theta^T(xx^T+\frac{\sigma^2}{\tau^2}I)\theta + r^2 - rx^T\theta - \theta^Txr )] \\ & \propto \text{exp}[-(\theta^TA\theta + rx^TA^{-1}xr - rx^TA^{-1}A \theta - \theta^TxA^{-1}Ar )], \ \ \ \ \ A := xx^T+\frac{\sigma^2}{\tau^2}I \\ & = \text{exp}[-(\theta-A^{-1}xr)^TA(\theta-A^{-1}xr)] \\ \end {align*}\] \[\begin{align*} \therefore \ \ \ p(\theta|r,x) \ \ & \sim N(A^{-1}xr, \ A^{-1}), \ \ \ \hat{\theta}_{MAP} = A^{-1}xr \end{align*}\]

추가적으로 논문에서는 ridge regression을 사용했다고 한다. ridge가 objective function에 l2 regularization텀을 추가 한 것임을 고려해 볼 때, 위 베이지안 추정치는 아래와 같이 ridge 추정치와 동치임을 알 수 있다. (*)을 다시 보자.

\[\begin{align*} \hat{\theta}_{MAP} &= \operatorname*{argmax}_{\theta} \ \ (*) \\ &= \operatorname*{argmax}_{\theta} \ \ \text{exp}[-\frac{1}{2\sigma^2} (r-x^T\theta)^T(r-x^T\theta) -\frac{1}{2\tau^2} \rVert \theta \rVert_{2}^{2} \ ] \\ &= \operatorname*{argmin}_{\theta} \ \ \frac{1}{\sigma^2} (r-x^T\theta)^T(r-x^T\theta) +\frac{1}{\tau^2} \rVert \theta \rVert_{2}^{2} \\ &= \operatorname*{argmin}_{\theta} \ \ (r-x^T\theta)^T(r-x^T\theta) +\frac{\sigma^2}{\tau^2} \rVert \theta \rVert_{2}^{2} \\ &= \hat{\theta}_{Ridge} \end{align*}\]

Confidence Interval

지금까지 reward를 모델링한 후, CTR을 구하기 위해 $\theta$를 추정했다. 이제 이를 바탕으로 기사를 선택하는 알고리즘인 LinUCB 에 대해 살펴볼 차례다. UCB 계열의 알고리즘은 불확실성이 큰 arm을 선택하는 전략으로, 불확실성의 척도로서 신뢰구간을 사용한다. 아래는 모평균 $\mu$에 대한 신뢰구간 예시다.

\[\hat{\mu}- \alpha \sqrt{var(\hat{\mu})} \ \ \leqq \ \ \mu \ \ \leqq \ \ \hat{\mu}+\alpha \sqrt{var(\hat{\mu})}\]

이때 UCB 계열의 알고리즘은 신뢰 구간의 upper bound만 고려하며 이 값이 가장 큰 arm을 선택한다. 위에서 $\theta$의 사후분포를 유도했으므로 E(reward)에 대한 신뢰구간도 아래와 같이 구할 수 있다.

\[\begin{align*} x^{T}_{t,a}\theta_{a} \ \ &\leqq \ \ x^{T}_{t,a} \hat{\theta_{a}} + \alpha \sqrt{var(x^{T}_{t,a} \hat{\theta_{a}} )} \\ &\leqq \ \ x^{T}_{t,a} \hat{\theta_{a}} + \alpha \sqrt{x^{T}_{t,a} A^{-1}_{a}x_{t,a}} \end{align*}\]

LinUCB Algorithm

이제 수도코드를 살펴보며 LinUCB 알고리즘을 정리해보자. 지금까지 $\text{(1)}$ reward 모델을 정의했고 $\text{(2)}$ E(reward)를 구하기 위해 모델의 파라미터를 추정했다. 특히 이 경우 reward를 클릭 여부라는 binary 케이스로 정의했기 때문에 E(reward)가 곧 CTR이 됨을 알 수 있었다. 또한 $\text{(3)}$ LinUCB 알고리즘은 신뢰구간을 바탕으로 arm(여기서는 기사)을 선택하므로, E(reward)의 신뢰구간까지 구하였다.

위 수도코드 Line 3~10을 보면 각 arm에 대해 $\text{(2),(3)}$을 반복한 후, Line 11에서 신뢰구간이 가장 큰 arm을 추천한다. 나머지는 초기화 및 업데이트 부분이다.

• Line 8: E(reward)를 구하기 위해 $\theta$를 추정한다. (이때 $b = xr$) $ \ \ \ \cdots \ \ \text{(2)}$
• Line 9: E(reward)의 신뢰구간을 구한다. $ \ \ \cdots \ \ \text{(3)}$
• Line 11: 신뢰구간이 가장 큰 arm을 추천한 후 reward를 얻는다.

4. Summary

이번 포스팅에서는 contextual bandit 알고리즘인 LinUCB에 대해 자세히 살펴봤다. 다음 포스팅에서는 논문 데이터셋 소개와 실험세팅 및 결과에 대해 이야기해보겠다.

Reference

https://towardsdatascience.com/the-bayesian-paradigm-ridge-regression-418af128ae8c https://statisticaloddsandends.wordpress.com/2018/12/29/bayesian-interpretation-of-ridge-regression