[MF] MATRIX FACTORIZATION TECHNIQUES FOR RECOMMENDER SYSTEMS

논문: MATRIX FACTORIZATION TECHNIQUES FOR RECOMMENDER SYSTEMS

 

위의 논문을 공부한 후, 코딩으로 구현하였다.

 

논문

MF는 implicit feedback, temporal effects, confidence levels을 추가적으로 적용시켜 classic nearest-neighbor 알고리즘보다 더욱 우수하다.

각각에 대해서 어떻게 적용시켰는지 살펴보자

 

RECOMMENDER SYSTEM STRATEGIES

추천 시스템에 대한 대략적인 내용이 들어가 있다.

1. Content Filtering

이 방법은 각 user 또는 item의 특성으로 profile을 만든다. 예를 들어, 영화의 장르, 배우등으로 profile을 만들어서 비슷한 특성을 가지는 item끼리 추천해주는 형식이다.

외부 정보도 추가할 수 있는데, user profile에는 인구 통계학적 정보(성별, 나이..)가 들어갈 수 있고 설문지의 답변이 들어갈 수 있다.

 

장단점

- 도메인에 따라 profile작성이 어려울 수 있다.

- cold start문제에서 collaborative filtering보다 우수하다.

 

 

2. Collaborative Filtering(협업 필터링)

이 모델은 user 간의 관계와 item 간의 상호 의존성(interdependencies)을 분석해 새로운 user-item associdations을 정의한다.

 

장단점

- 도메인이 없다는 뜻이다. 어떤 피드백(rating, 구매 횟수..)등으로 user-item을 연결하기 때문에 도메인에 의존되지 않는다. 

- 일반적으로 content based보다 좋은 성능을 가진다.

- 하지만, cold start라는 문제가 있다. 새로운 item이나 user들에 대한 feedback이 부족하기 때문이다.

 

 

collaborative filtering은 주로 두 개의 영역으로 나뉜다. Neighborhood와 Latent factor model이다.

Neighborhood methods는 item이나 user 간의 관계를 파악해, 가장 가까운 item, user를 살펴 rating을 예측하는 것이다.

Latent factor model은 rating pattern에서 추론된 여러 가지 factor(요소)들로 rating을 예측한다.

예를 들어, 영화를 여성 vs 남성 지향적, serious vs escapist 등으로 특징을 나눠, 각각의 factor에 대해 단계성(점수)을 매긴다.

 

 

 

 

MATRIX FACTORIZATION METHODS

MF(Matrix Factorization)은 items과 users에 대해 rating pattern을 가지고 latent 한 vector를 만든다. 

MF의 장점은 explicit feedback뿐 아니라 implicit feedback(구매 내역, 검색 기록, 검색 패턴..)까지 허용한다. 

explicit feedback으로 이뤄진 matrix는 sparse하다는 문제가 있지만, implicit feedback을 사용한다면 보다 dense 한 matrix로 만들 수 있기 때문에 좋은 결과를 낼 수 있다.

 

 

 

A BASIC MATRIX FACTORIZATION MODEL

MF는 user와 item을 latent factor 공간($f$)에 mapping시켜(내적) 모델링한다.

 

*user, item의 factor vector로 mapping시킬 때 SVD를 많이 사용한다. 하지만 SVD에서 matrix가 불완전할 경우 정의되지 않는다.

 

벡터 q($q_{i} \in R^f$)는 item이 가지는 factor의 정도를 표시하고, p($p_u \in R^f$)는 user가 factor에서 얼마나 관심을 가지고 있는지의 정도로 표현된다.

이 두 벡터를 이용해 $\hat{r}$을 구할 수 있다.

regularized 된 rating은 아래와 같다.

k= (u,i)쌍의 training set

뒤에 정규항을 넣음으로써 overfitting을 방지한다. q벡터나 p벡터에 엄청나게 큰 값들이 존재한다면, norm이 커져버리게 된다. 즉, 위의 식을 최소화 하기 때문에 크게 튀어버리는 숫자들을 잡고, overfitting을 방지할 수 있다.

$\lambda$는 hyperparameter로 정규화의 범위를 제어하며, 대게 cross validation에 의해 결정된다.

 

 

 

LEARNING ALGORITHMS

object function을 최소화하는 방법에는 SGD(Stochastic Gradient Descent)와 ALS(Alternating Least Squares)가 있다.

 

1. SGD(확률적 그래디언트 강하)

SGD는 구현이 쉽고 빠른 시간으로 최적화 할 수 있어 대중화된 방법이다. SGD에 대한 자세한 설명은 생략하고 간단하게 설명하겠다.

SGD

SGD의 일반적인 공식은 위와 같다. W(업데이트) < - 기존 W - 학습률* w미분 값으로 구성된다.

미분 값을 곱해주는 이유는, 함수가 convex 할 때 최솟값에 다가가기 위해서 기울기만큼 step을 밟는다는 이유다.

 

이를 MF에 적용해 보면, error의 값은 다음과 같다. 

$e_{ui} = r_{ui}-q^T_ip_u = r_{ui}-\hat{r}$

 

이후, q와 p를 아래와 같이 업데이트를 하는데, convex하지 않기 때문에 미분하지 않고, 각 parameter에 반대방향으로 비례하는 크기로 step을 밟아간다.
$q_i : = q_i + \gamma (e_{ui}p_u - \lambda q_i)$
$p_u : = p_u + \gamma (e_{ui}q_i - \lambda p_u)$

 

2. ALS

object function이 convex하지 못하다. 그 이유는 q, p에 대한 2차 방정식이기 때문이다. 만약, q를 상수로 두면 p에 대한 convex 2차 함수를 만들 수 있다. 이 개념이 ALS의 토대가 된다.

ALS는 먼저 q를 고정하고 p의 optimal값을 찾는다. 그 후, p를 고정하고 q의 optimal을 찾고 계속해서 번갈아가는 것을 반복한다. 계속 반복하면 p와 q는 어떤 값에 수렴하게 되고 반복을 종료한다.

ALS는 적어도 두 가지 경우에서 유리하다.

1. 시스템이 병렬 처리(parallelization)를 사용할 수 있는 경우: 다른 item facor에 대해 각 $q_{i}$를 독립적으로 계산하고, 다른 user factor에 대해 각 $p_{u}$를 독립적으로 계산한다.

2. 암시적(implicit) 데이터를 중심으로 하는 시스템: sparse하지 않은 데이터를 train data로 사용할 때는, 각 단일 training case를 반복하는 SGD를 사용하면 실용적이지 않다.

 

 

 

ADDING BIASES

식(2)에서 Bias의 영향을 고려해야 한다. rating은 item과 user에 대해 독립적인 bias(편향) 또는 intercept(절편)의 영향을 받기 때문이다. 예를 들어, '민지'는 다른 사람보다 점수를 후하게 주고, '타이타닉'은 점수를 후하게 받는 영화에 속한다면 '민지가 타이타닉'에 매긴 점수는 다른 rating보다 높을 것이다. 이를 보완해야 한다.

 

$\hat{r_{ui}} = \mu + b_i + b_u + q^{T}_{i}p_{u}$

*$\mu$: Global average, $b_{i}$: item bias, $b_{u}$: user bias, $q^{T}_{i}p_{u}$: interaction

보완한 식은 위와 같다.

문제) 영화의 전체 평균은 3.7이고, 타이타닉은 평균적으로 0.5점 더 받는 경향이 있으며, 지혜는 평균적으로 -0.2점 주는 경향이 있을 때 지혜는 타이타닉을 몇 점 줄 것인가?

$\hat{r_{지혜,타이타닉}}= 3.7 + 0.5 -0.2$

 

결론적으로, Biases를 고려하면 object 함수는 아래와 같다.

$\min_{q,p,b}\sum_{(u,i)\in K}(r_{ui}-\mu-b_i-b_u-_i^Tp_u)^2 +\lambda(\parallel q_i \parallel^2 + \parallel p_u \parallel^2+{b_u}^2+{b_i}^2)$

 

biases는 signal을 모두 캡처하는 경향이 있기 때문에, 정확한 모델링이 필요하다.

 

 

 

ADDITIONAL INPUT SOURCES

cold start문제를 보완하기 위해 implicit data를 활용할 수 있다.

 

$N(u)$는 user가 implicit preference를 표현한 item 집합이다. 그 안에는 $x_i$가 존재하며, iterm에 대한 선호도를 나타낸다. user의 implicit preference를 벡터로 표현하면 아래와 같이 표현할 수 있다.

$$\sum_{i\in N(u)}x_i$$

 

이를 normalizing을 시키면 다음의 식이 된다.

$$\mid N(u)\mid^{-0.5} \sum_{i\in N(u)}x_i$$

 

다른 정보로는, user attributes의 속성이 있다. 여를 들어 demographics 같은 연령, 성별, 우편 코드 등이 있다. 이를 $A(u)$에 집합으로 담는다. 위와 동일하게 벡터로 나타내면 다음과 같다.

$$\sum_{a\in A(u)}y_a$$

 

결론적으로, 이 전에 만들어놨던 공식에 implicit preference를 추가해주면 된다.

$$\hat{r_{ui}} = \mu + b_i + b_u + q^{T}_{i}[p_{u} + \mid N(u)\mid^{-0.5} \sum_{i\in N(u)}x_i + \sum_{a\in A(u)}y_a]$$

 

 

 

TEMPORAL DYNAMICS

이때까지의 공식은 시간을 고려하지 않았다. 하지만, user의 성향은 시간에 따라 바뀌기 때문에 시간적인 요인(temporal aspects)도 고려해야 한다. $b_i(t)$(item biases), $b_u(t)$(user biases), $p_u(t)$(user preference)가 시간에 따라 바뀐다.

1. item의 인기는 시간에 따라 달라진다. 이 때문에 item bias인 $b_i$를 시간적으로 다룬다.

2. user의 baseline rating은 시간에 따라 달라진다. 예를 들어, 한 user가 평균적으로 4점의 평점을 줬지만, 현재는 3점을 준다고 하면 이는 분명 baseline이 변한 것이다. 때문에 $b_u$를 고려해야 한다.

3. 1,2번을 고려해보면 users, items에 대한 interaction도 변한다.

 

시간을 고려해 공식을 만들면 아래와 같다.

$$\hat{r_{ui}}(t) = \mu + b_i(t) + b_u(t) + q_i^T P_u(t)$$

 

 

 

INPUTS WITH VARYING CONFIDENCE LEVELS

모든 rating이 동일한 confidence(신뢰도)를 받으면 안 된다.

예를 들어, 엄청 크게 광고를 진행했으면 item rating에 영향을 줄 수 있으며, 한 user가 한 번 구입한 것과, 여러 번 구입한 것은 신뢰도가 확연히 다르다. 따라서 신뢰도를 적용해야 한다.

$$\min_{q,p,b}\sum_{(u,i)\in K}c_{ui}(r_{ui}-\mu-b_i-b_u-q_i^Tp_u)^2 +\lambda(\parallel q_i \parallel^2 + \parallel p_u \parallel^2+{b_u}^2+{b_i}^2)$$