MAB기반 추천시스템 : Collaborative Filtering Bandits - (1)

전통적인 CF 기반 추천 방식은 유저와 아이템 셋이 고정되어있다.

하지만 일반적인 추천 시스템에서는 유저와 아이템 풀이 점점 확장된다.

서비스에서는 신규 유저가 인입되기도 하고, 기존 유저가 이탈하기도 하며, 아이템 셋도 변한다.

또한 가장 중요한 것은 유저의 선호가 지속적으로 변한다는 것이다.

이에 따라 논문은 Contextual Bandit을 CF알고리즘의 특성을 녹여 재구성한 알고리즘을 제안했다.

Collaborative filtering bandits

SIGIR, 2016 : https://arxiv.org/pdf/1502.03473.pdf

논문에서는 Bandit이 지속적으로 변하는 유저의 선호를 맞춘 추천을 해주기 적합한 알고리즘이라고 소개한다.

하지만 이 알고리즘은 비슷한 아이템이나 유저 간 선호가 유사하다는 CF 알고리즘적인 특성은 지니지 못한다.

따라서 이 두 알고리즘을 섞어 비슷한 유저가 좋아한 아이템은 비슷한 선호로 추정하면서,

유저의 다이나믹한 변동을 담아낼 수 있는 알고리즘 개발을 필요로 하게 되었다.

과거 연구들은 실시간 클러스터링 알고리즘이나, 네트워크형 데이터구조를 도입하는 등의 시도를 해왔다고 한다.

​

논문은 Stochastic multi-armed bandit 알고리즘 중 하나인 UCB (Upper Confidence Bandit)과

전통적인 추천 알고리즘인 Collaborative Filtering을 섞은 Collaborative Filtering Bandit을 모델로 소개한다.

이제 모델 로직을 좀 더 살펴보자.

​

---

Basic mathematical expression

​

유저의 행동 유사성은 특정 feature벡터 x에 따라 클러스터링 형태로 코딩된다고 가정해보자.

x →{U1​(x), U2​(x), ..., Um(x)​(x) }​

U는 n명의 유저를 담는 pool(혹은 set)이라 정의하면, 유저는 m(x) 개 클러스터만큼 묶일 수 있다.

이 때 한 데 묶인 유저들은 유사한 선호를 가졌다. 이 선호에 따른 클러스터링은 아이템에 따라 다를 수 있다.

위 식에서 볼 수 있듯이, 특정 feature 벡터 x가 값이 변함에 따라 같은 그룹 내에 속할 유저들을 정하고, 그 수에 따른 클러스터링 갯수도 정하게 된다.

즉 유저 set 클러스터링 수와 유저 set에 속할 유저들은 featuer벡터 x가 결정한다.

​

이 정의를 수식적으로 풀면 아래와 같다.

유저 i와 i'가 같은 클러스터 내에 있다면, 동일한 feature vector로 추론한 선호는 동일할 것이다.

반면 다른 클러스터에 있다면 두 벡터 곱간 차이는 발생할 것이다.

​

벡터 Ui는 유저 i의 (평균) 행동을 의미한다.

따라서 context vector x에 대해 유저 i가 반응함으로써 주는 보상(payoff) 가치는 아래와 같이 정의될 수 있다.

Ei(x)는 noise라고 생각하면 된다. 왜냐하면 위에서 Ui는 시간에 따라 변화하지 않는 변수라고 가정했기 때문이다.

각 round를 t로(전체 T개 라운드) 정의한다면, Total payoff는 아래와 같이 정의할 수 있다.

유저의 보상은 클릭 혹은 미클릭 형태로 돌아오며, 이는 binary feedback이다.

우리는 전체 모델의 성과 측정을 CTR지표로 확인할 수 있다.

우리는 알고리즘이 예측하는 값과 실제 보상 값 간의 차이를 줄여나가고 싶다.

이 간차를 'regret'이라고 부를 때, regret은 아래와 같이 정의가 가능하다.

(=실제 Optimal - 추천한 결과)

우리의 알고리즘의 목적은 누적(cumulative) regret값을 줄이는 것이다.

---

Clustering

​

논문의 CF적 알고리즘 특성인 '클러스터링' 방법에 대해서 알아보자.

유사한 유저를 묶는 유저 cluster과, 유사한 아이템을 묶는 아이템 cluster 이렇게 두 개가 있을 것이다.

이 두 클러스터를 'two-sided' cluster, 즉 양면 클러스터라고 부른다.

이 양면 클러스터는 아래와 같은 특성을 지닌다.

​

"만약 아이템 x1로 인해 구분된 유사한 선호 그룹의 유저 셋이 x2로 그룹된 유저 셋과 동일하다면,

아이템 x1과 x2는 동일한 아이템 클러스터에 속할 것이다"

​

즉 아이템 1과 아이템 2 각각 추론된 선호하는 유저 셋이 동일하다면,

아이템 1과 2는 유사한 아이템일 것이라는 의미이다.

조금 생각해보면 당연한 것인데, 정의를 내리는 식으로 어렵게 풀이되었다.

​

---

다음 글에서는 모델의 Pseudocode를 소개하고, 로직을 설명할 것이다.