[논문 리뷰] Matrix Factorization techniques for Recommender Systems

이번 논문은 추천 시스템에서 정말 중요한 개념 중 하나인 Matrix Factorization에 대해서 소개하고, 그 성능을 증가시키기 위한 여러 가지 기법에 대해 기술한 논문이다. 개인적으로 추천 시스템의 기초가 되는 논문이라고 생각되어서 선정하게 되었고, 규제화(regularization)부터 시작해서 시간적 요소를 반영하는 것까지 생각한 것들이 흥미롭게 읽은 논문이다.

 

 

 

 

출처:https://wikidocs.net/132773

 

 

 

 

당시에 진행하던 Netflix Prize 대회는 넷플릭스의 영화를 사용자에게 얼마나 더 잘 추천하는지를 겨루는 대회였다. 해당 대회에서 Matrix Factorization 기법을 사용한 추천의 성능이 이웃기반 추천 시스템보다 우월했다. 따라서 저자는 Matrix Factorization 기법에 다른 테크닉을 추가하여 성능을 더 끌어올리려고 했었다.

 

 

 

 

 

 

RECOMMENDER SYSTEM STRATEGIES

 

출처: https://www.researchgate.net/figure/Content-based-filtering-vs-Collaborative-filtering-Source_fig5_323726564

 

 

 

 

 

당시 기준으로 보자면, 추천시스템은 크게 2가지 전략으로 구분될 수 있었다. 하나는 content filtering 방식이고, 다른 하나는 collaborative filtering 방식이다. 먼저, content-based 방식은 유저 또는 아이템 각각에 대한 프로필을 만들고 유사한 것들끼리 매칭 시켜주게 된다. 예를 들어, 영화에 대한 아이템 프로필에는 장르, 배우, 박스오피스 인기도 등의 정보가 포함될 수 있고, 유저 프로필에는 기본적인 인구통계학적 정보(성별, 나이, 이름 등) 또는 설문지를 통해서 얻어낸 성향 정보들이 저장된다.

 

 

 

 

하지만 프로필 정보를 만드는 것은 말처럼 쉽지만은 않다. 실제로 얻어내기 힘든 정보들이 있을 수도 있어서 프로필을 제대로 생성하지 못하는 경우가 꽤 많이 있다고 한다. 그럼에도 content-based filtering 방식으로 성공을 한 사례는 음악 추천을 해주는 pandora의 Music genome Project가 있다. 

 

 

 

 

Collaborative Filtering 방식은 유저와 아이템 사이의 상호작용 정보를 사용하여 그 사이의 관계를 포착하려고 한다. CF방식의 큰 매력은 해당 도메인에 대한 지식이 없어도 된다는 것이다. 프로필 정보처럼 장르, 배우와 같은 추가 정보가 필요한 것이 아니라 오직 상호작용 정보만 있으면 된다. 하지만, 초기 유저와 같이 상호작용 정보가 하나도 없거나 적은 경우에는 추천 성능이 현저하게 떨어지는 cold start problem이 있다.

 

 

 

 

추천시스템의 분류

 

 

 

 

다시 CF는 이웃기반(neighborhood method) 방법인지, 잠재 요소 (latent factor) 방법인지에 따라 2가지로 분류할 수 있다. 이웃 기반 방법은 아이템과 아이템 또는 유저와 유저 사이의 관계를 파악하려고 한다. 먼저 아이템과 아이템 사이의 관계를 파악하는 이웃 기반 협업 필터링(IBCF)은 같은 유저가 아이템에 매긴 평점 정보를 사용하여 선호도를 파악하는 방법이다. 예를 들어, "라이언 일병 구하기"와 같은 영화의 이웃에는 스필버그의 영화나 톰 행크스가 등장하는 영화가 등장할 것이다.

 

 

 

 

반대로 유저와 유저사이의 관계를 파악하는 협업 필터링(UBCF)은 유저가 아이템들에 내린 평점들과 유사하게 평점을 내린 다른 유저들을 찾는다. 그리고 가장 유사한 유저를 찾으면 해당 유저가 재미있게 본 영화를 추천하게 되는 것이다. 이렇게 유저들끼리 서로서로 협업하여 추천을 해주는 것이 이웃 기반 협업 필터링이다.

 

 

 

 

Word Embedding

 

 

 

 

잠재 요소를 사용하는 모델들은 각 유저와 각 아이템을 20개~100개의 잠재 요소를 갖는 벡터로 동일한 벡터 공간에 매핑시킨다. 현대에 와서는 이 과정을 "임베딩 한다"라고 자주 표현하며 이 동일한 임베딩 공간상에서 유사한 벡터는 선호도가 매칭이 잘 된다고 볼 수 있다. 주의할 것은 어떤 벡터 공간에 매핑했을 때, 각 축이 의미하는 것은 유추만 할 수 있을 뿐 우리가 정확하게 알 수는 없다. 논문에서는 임베딩 된 벡터들을 다음과 같이 표현될 것이라고 도식화하였다.

 

 

 

 

출처: Matrix Factorization Techniques for recommender system 본문

 

 

 

 

잠재 요소를 사용하는 모델에서 어떤 사용자가 특정 아이템에 내릴 평점을 예측하고 싶을 때는, 유저 벡터와 아이템 벡터를 내적 하면 된다. 그렇게 되면 위의 그림에서 Gus는 Dumb and Dumber를 좋아할 것이고, The Color Purple 영화를 싫어한다고 예측할 것이다.

 

 

 

 

 

 

 MATRIX FACTORIZATION METHOD

출처: https://velog.io/@amin/220718%EC%9B%94

 

 

추천 시스템은 2가지 데이터 타입을 사용한다. 하나는 Explicit feedback으로 유저가 영화에 매긴 평점 또는 좋아요/싫어요 정보들이 여기에 해당한다. 유저가 "명시적으로" 어떤 영화가 좋다! 싫다! 를 표현한 것이기 때문에 가장 효과적으로 학습할 수 있는 정확한 데이터가 된다.

 

 

 

 

다른 하나는 Implicit feedback 데이터이다. 사실 생각해보면 explicit feedback은 그 개수가 정말 적을 수밖에 없다. 모든 유저들이 어떤 영화를 보고나서 평점이나 후기를 남기는 비율이 적듯이 그런 데이터도 적을 수 밖에 없다. 반면, implicit feedback 은 유저가 어떤 상품을 살펴보았는지, 그 영화를 몇 번 보았는지 등의 간접적으로 유저의 선호도를 알 수 있는 정보들을 포괄하여 말한다.

 

 

 

 

 

 

A BASIC MATRIX FACTORIZATION MODEL

 

출처: Naver Boostcamp AI Tech - Collaborative Filtering 강의 자료

 

 

 

 

앞서 말했듯이, MF모델들은 아이템과 유저 정보를 $f$ 차원을 갖는 벡터 공간에 매핑시킨다. 여기서 매핑된 각 아이템은 $q_i \in \mathbb{R}^f$ 로 표현하며, 각 유저는 $p_u \in \mathbb{R}^f$로 표현한다. 결과적으로 $q_i$와 $p_u$의 원소들은 각 차원에 얼마나 더 연관이 되어있는지를 말한다. 이 아이템 벡터와 유저 벡터를 사용해 평점 예측을 할 때는 내적을 사용하게 되며 아래와 같다.

 

 

 

 

$$ \hat{r}_{ui} = q_i^T p_u $$

 

 

 

이제 문제는 "어떻게 각 유저와 아이템들을 벡터 공간에 매핑시키는가?"이다. 모델은 singular vector decomposition(SVD)의 정보 추출 기법에서 아이디어를 가져왔다. SVD를 협업 필터링에 적용하게 되면, 유저-아이템 평점 행렬을 사용하는데 문제는 SVD가 불완전한 행렬(비어있는 값이 있는 행렬)에 대해서는 정의되지 않았다는 것이다. 게다가, 값이 있는 부분만 사용하게 되면 과적합이 될 가능성이 매우 높아진다.

 

 

그래서 나온 첫 번째 방법은 비어있는 값을 채워 넣는 것이다. 하지만, 채워넣는 것도 양이 너무 많기에 높은 계산량을 요구하였고 부정확한 결과를 초래할 수 있었다. 두 번째 등장한 방법은 잠재 벡터를 학습시키는데, 오직 평점 정보가 존재하는 데이터만 사용하고, 과적합을 피하기 위한 규제화를 하는 것이다. 학습할 때는 예측한 평점과 실제 평점 간의 제곱 오차를 사용하도록 하였다.

 

 

 

 

$$ \underset{q^*, p^*}{\min} \sum_{(u, i) \in \mathcal{K}} (r_{ui} - q_i^T \cdot p_u) ^ 2 + \lambda(\| q_i \|^2 + \|p_u\|^2) $$

 

• $\mathcal{K}$ : 관측된 평점 정보가 있는 $u, i$ 쌍
• $\lambda$ : 규제화(regularization)의 정도를 조절

 

 

학습이 될 때, 학습 데이터셋에 오버피팅이 되는 것을 막고자 L2-norm 정규화 방법을 사용하였다. 이때, 람다를 도입하여 규제화의 정도를 조절할 수 있도록 만들었다. 따라서 보지 않은 유저 아이템 쌍에 대해서도 평점 정보를 잘 예측할 수 있도록 하였다.

 

 

 

 

 

 

LEARNING ALGORITHMS

 

stochastic gradient descent

 

먼저, 딥러닝 학습방법에서 잘 사용되고 있는 SGD를 적용시켜서 모델을 학습시킬 수 있다. Simon Funk가 평점 데이터를 사용해 SGD를 적용한 계산을 도입했고, 이는 모든 평점 데이터를 사용하여 경사 하강법을 계산하는 것이다. 실제값과 예측값과의 오차 $e_{ui}$ 를 계산한 뒤, 각 파라미터의 업데이트에 사용하는 것이다.

 

 

 

 

$$ e_{ui} = r_{ui} - q_i^T \cdot p_u $$

 

 

$$ q_i \leftarrow q_i + \gamma \cdot (e_{ui} p_u - \lambda q_i) $$

$$ p_u \leftarrow p_u + \gamma \cdot (e_{ui} q_i - \lambda p_u) $$

 

 

 

 

 

alternating least squares

 

$q_i$와 $p_u$는 알지 못하기 때문에 사실 위에서 등장한 목적함수가 convex 한지는 알 수 없다. 하지만 만약 이 2개의 변수 중에서 하나를 고정한다면 2차 함수 꼴이 되어 미분을 통해 문제를 풀 수 있게 된다. ALS 방법은 업데이트를 할 때, 2개의 변수를 번갈아가면서 업데이트한다. 예를 들어 $q_i$를 업데이트할 때는 $p_u$를 상수화 시키고, $p_u$를 업데이트 할 때는 $q_i$를 상수화 시키는 것이다.

 

 

 

 

SGD가 ALS보다 쉽고 빠름에도 ALS를 사용했을 때 좋을 때는 다음  2가지 조건을 만족하는 경우이다. 먼저 병렬 연산을 사용할 수 있는 경우와, 데이터가 implicit feedback에 집중되어 있는 경우이다. implicit feedback을 사용할 경우, 데이터가 그래도 sparse 하지 않다. 그렇기에 SGD를 학습시킬 때 사용하는 데이터의 양도 매우 많아져 계산 복잡도가 높아 실용적이지 못하다. 반면에 ALS는 해를 수식을 통해 한 번에 계산할 수 있기 때문에 문제를 쉽게 다룰 수 있다.

 

 

 

 

 

 

ADDING BIASES

 

대부분의 유저들과 아이템들에는 편향(bias)이 존재한다. 예를 들어 1~5점까지의 평점을 매길 수 있다고 할 때, 주로 높은 평점을 주는 유저는 4점이 그렇게 높은 점수가 아닐 수 있어도, 주로 낮은 평점을 주는 유저가 4점을 준 것은 매우 높게 점수를 주었다고 할 수 있다. 이에 따라 아이템들도 다른 것들에 비해 훨씬 높게 평가된 것들이 존재할 수 있게 된다.

 

 

 

 

저자들은 이 문제를 해결하기 위해 2개의 bias term을 추가하여 모델에 같이 학습시키게 만들었다. bias는 각 유저와 각 아이템에 대해 다르게 존재하는 값이기 때문에 유저마다 그리고 아이템마다 생성해 주어야 한다.

 

 

 

 

$$ b_{ui} = \mu + b_i + b_u $$

 

• $\mu$ : 전체 평점 평균
• $b_i$ : 아이템에 대한 bias
• $b_u$ : 유저에 대한 bias

 

 

방금 정의한 bias를 평점 예측 식에 추가하게 되면 $\hat{r}_{ui} = b_{ui} + q_i^T \cdot p_u$ 로 나타난다. 각 bias term을 학습하기 위한 오차 제곱합 목적 함수 식을 표현한 것은 아래와 같다.

 

 

 

 

$$ \underset{q^*, p^*, b^*}{\min} \sum_{(u, i) \in \mathcal{K}} (r_{ui} - \mu - b_u - b_i - q_i^T \cdot p_u) ^ 2 + \lambda(\| q_i \|^2 + \|p_u\|^2 + b_u^2 + b_i^2) $$

 

 

 

 

 

 

ADDITIONAL INPUT SOURCES

 

cold start 문제를 다루려면 explicit feedback 외의 정보들을 많이 활용해야 한다. 추가적인 정보로는 implicit feedback 데이터가 될 수 있다. 예를 들어, 판매자의 경우 고객이 어떤 상품들을 구매했고, 어떤 페이지를 조회했는지 기록을 사용하면 고객들의 성향을 살필 수 있는 것이다.

 

 

 

 

단순화를 위해서 Boolean 값을 갖는 implicit feedback 정보를 사용한다고 해보자. $N(u)$가 implicit feedback을 통해 알아낸 $u$가 선호할 만한 아이템들의 집합이라면, 그의 성향을 다음과 같이 정규화를 포함한 수식으로 표현할 수 있다.

 

 

 

 

$$ \vert N(u) \vert ^{-0.5} \sum_{i \in N(u)} x_i, \quad x_i \in \mathbb{R}^f $$

 

 

 

 

cold start에 대비하여 또 사용할 수 있는 것은 유저 정보이다. 마찬가지로 boolean형의 유저 정보 $A(u)$가 있다고 했을 때, 각 열은 성별, 나이, 수입능력 등이 된다. 각각의 열 정보들은 벡터로 표현되기 때문에 위와 비슷한 수식이 형성된다.

 

 

 

 

$$ \sum_{a \in A(u)} y_a, \quad y_a \in \mathbb{R}^f $$

 

 

 

 

위의 2가지 추가 정보를 사용하여 MF의 평점 예측 수식을 업데이트하면 아래와 같다.

 

 

 

 

$$ \hat{r}_{ui} = \mu + b_i + b_u + q_i^T[p_u + \vert N(u) \vert ^{-0.5} \sum_{i \in N(u)} x_i + \sum_{a \in A(u)} y_a ] $$

 

 

 

 

 

 

TEMPORAL DYNAMICS

 

지금까지 소개한 모델은 시간에 따라 변화하지 않는 정적인 모델이었다. 하지만, 실제로는 시간이 지남에 따라 유저의 선호도는 변화하고 아이템의 정보도 변화한다. 평점 예측 수식을 시간의 흐름에 따라 변화할 수 있는 수식으로 분해할 수 있게 된다면 시간에 따른 유저의 선호도나 상품의 변화를 같이 녹일 수 있을 것이다.

 

 

 

 

구체적으로 저자들은 3개의 시간에 따라 변화하는 term을 두었고, 구체적으로는 아이템에 대한 편향 $b_i(t)$, 유저에 대한 편향 $b_u(t)$, 유저의 선호도에 대한 값 $p_u(t)$이 있다. 이 3가지 term을 평점 예측 수식에 더한다면 아래와 같아질 것이다.

 

 

 

 

$$ \hat{r}_{ui} = \mu + b_i(t) + b_u(t) + q_i^T \cdot p_u(t) $$

 

• $b_i(t)$ : 아이템의 인기도는 시간이 지남에 따라 변화한다
• $b_u(t)$ : 유저의 평균 평점 정도가 시간이 지남에 따라 높아지거나 낮아질 수 있는 정보를 반영
• $p_u(t)$ : 시간에 따라 변화하는 유저의 선호도

 

 

 

 

 

 

INPUTS WITH VARYING CONFIDENCE LEVEL

 

평점을 예측할 때, 관측된 (유저, 아이템) 쌍인 $\mathcal{K}$를 사용했었다. 여기서 관측된 평점 정보들을 사용할 때, 모든 평점들이 똑같이 취급되어서는 안 된다는 것이 이번 파트의 주제이다. 예로 특정 상품에 대한 광고를 많이 하게 되면, 해당 상품의 평점이 좋거나 높아질 수 있을 수 있기 때문이다.

 

 

 

 

implicit feedback에서는 유저와 아이템이 상호작용한 횟수를 이용해서 학습을 했었다. 문제는 정확한 유저의 성향을 파악하는 것은 힘들다는 것이다. implicit feedback으로 알 수 있는 것은 "아마도 이것을 더 좋아함" 또는 "아마도 이것을 싫어할 것임"의 정보뿐이다. 따라서 여기에 confidence를 곱하여 어느 정도의 확신이 있는지를 가중치를 주는 것이다. 저자는 더 많이 상호작용 할수록 유저가 해당 아이템을 더 선호할 것이라 생각하였고, 이것을 가중치이자 confidence 값으로 사용하였다.

 

 

 

 

$$ \underset{q^*, p^*, b^*}{\min} \sum_{(u, i) \in \mathcal{K}} c_{ui}(r_{ui} - \mu - b_u - b_i - q_i^T \cdot p_u) ^ 2 + \lambda(\| q_i \|^2 + \|p_u\|^2 + b_u^2 + b_i^2) $$

 

 

 

 

 

 

NETFLIX PRIZE COMPETITION

 

저자들은 2007년도에 넷플릭스 추천 대회에 참여해서 수상을 했으며, 방대한 양의 데이터 덕분에 의미 있는 발견들을 여럿 할 수 있었다고 밝혔다. 그중 하나로 먼저, 벡터 공간에 표현한 아이템들을 표현했을 때의 모습을 보여주었다.

 

 

 

 

출처: MATRIX FACTORIZAION TECHNIQUES FOR RECOMMENDER SYSTEM

 

 

 

영화에 대해서 잘 아는 사람들은 위의 그림을 바로 눈치를 챘을 수 있겠지만, factor 1에 가까울수록 저속하고 코메디요소와 호러, 남성향에 가까운 영화들이 존재하였고 factor2에 가까울 수록 드라마, 여성향에 가까운 영화들이 많이 늘어져 있었다.

 

 

 

 

그런데 위의 그림에서 붙어 있다고 해서 비슷한 영화가 매핑된 것은 아니었다. 예시로 Annie Hall과 Citizen Kane은 서로 붙어있는데 장르가 서로 크게 다른 영화이다. 그 이유는 위의 그림에서는 100개에 달하는 차원에서 첫 2가지 차원에 대해서만 2차원적으로 본 그림이기 때문이다.

 

 

 

 

출처: MATRIX FACTORIZAION TECHNIQUES FOR RECOMMENDER SYSTEM

 

 

 

 

위 그림은 앞에서 소개한 MF의 다양한 기법들을 적용했을 때와 각 잠재 요소의 수 변화량에 따른 RMSE 결괏값 차이를 보여준다. 각 모델에 대한 성능은 잠재 요소의 수가 많을수록 RMSE 오차가 줄어 성능이 증가하는 경향을 보여주었다. 시간에 따른 성향의 차이('temporal effect') 정보를 더한 모델이 훨씬 더 좋은 성능을 보여줌을 확인할 수도 있다.