Paper Information
- Title : Matrix Factorization Techniques for Recommender Systems
- Authors : Yehuda Koren et al.
- Journal : IEEE Computer
- URL : 논문 링크
-
- 추천 시스템 (Recommender System)
-
제품에 대한 사용자의 관심 패턴을 분석해서 사용자 취향(taste)에 맞는 개인화된 추천(personalized recommendations)을 제공한다.
Recommender System Strategies
추천 시스템은 2가지 전략을 바탕으로 작동한다.
- Content Filtering
- Collaborative Filtering
1. Content Filtering
각 사용자 및 제품의 특성을 특징짓기(characterize) 위한 프로필(profile)을 생성한다.
예: 영화 프로필 - 장르, 특정 배우, 박스 오피스 흥행 기록 등
유저 프로필 - 인구 통계학적 정보(성별, 나이 등), 설문조사 기록 등
이러한 프로필은 사용자와 제품을 연결할 수 있지만, 추가적인 외부정보를 수집해야 한다.
2. Collaborative Filtering
프로필에 생성할 필요 없이 과거 사용자의 행동(예: 과거 상호작용 또는 제품의 등급)에만 의존한다.
협업 필터링(Collaborative Filtering)은 사용자 간의 관계와 제품 간의 상호 의존성을 분석하여 새로운 사용자-아이템 연결 관계를 식별한다.
협업 필터링은 도메인의 영향을 적게 받으며 일반적으로 콘텐츠 기반 방법보다 더 정확하다.
하지만, 협업 필터링 방법은 새로운 사용자나 아이템에 대해서 해결 할 수 없는 cold start 문제에 고통받는다.
협업 필터링 방법의 두 가지 주요 분야로는 neighborhood methods와 latent factor models가 있다.
1) Neighborhood Methods
Neighborhood Methods은 아이템 또는 사용자 간의 관계를 계산하는 것에 집중한다.
아이템 중심 방법은 “neighboring” 아이템의 등급을 기반으로 아이템에 대한 사용자의 선호도를 계산한다.
제품의 이웃들은 같은 사용자가 평가할 때 비슷한 평가를 받는 경향이 있는 다른 제품이다.
2) Latent Factor Models
반면, Latent Factor Models은 평가 패턴에서 추론된 요인에 대해 아이템과 사용자를 모두 특성화하여 평가를 설명하려는 대안적인 접근 방법이다.
사용자에 대해서, 각 요인들은 얼마나 사용자가 해당 영화 요인에서 높은 점수를 받은 영화를 좋아하는 지를 측정한다.
이 모델의 경우 영화의 평균 평점과 비교하여 영화에 대한 사용자의 예측 평점은 위 그림에서 영화와 사용자 위치의 내적과 동일하다.
Matrix Factorization Methods
Latent factor models의 가장 성공적인 구현 중 일부는 matrix factorization을 기반으로 한다.
Matrix factorization은 아이템 등급 패턴에서 추론된 factor의 벡터로 아이템과 사용자를 특성화(characterizes)한다.
아이템과 사용자 factors 간의 높은 관련성(correspondence)은 추천으로 직결된다.
Matrix Factorization 방법의 장점
- 우수한 확장성(scalability)
- 높은 예측 정확도(predictive accuracy)
- 실제 상황에서 유연함(flexibility)
추천 시스템에서 input data의 종류
- 1) Explicit feedback
-
Explicit feedback은 아이템에서 사용자의 관심에 대한 명시적인 입력(explicit input)이 포함된다. 그렇기 때문에 보통 explicit feedback은 sparse matrix이다.
Matrix Factorization의 강점 중 하나는 추가적인 정보의 통합이 가능하다는 것이다. Explicit feedback이 존재하지 않는 경우에, 추천 시스템은 사용자의 선호도(preferences)를 implicit feedback을 통해서 추론한다.
- 2) Implicit feedback
-
Implicit feedback은 구매 내역, 방문 기록, 검색 패턴 및 마우스 움직임 등 사용자의 행동(behavior)을 간접적으로 의견을 반영한다.
Implicit feedback은 보통 사건의 발생여부로 나타내며, 따라서 일반적으로 dense matrix로 표현된다.
A Basic Matrix Factorization Model
Matrix factorization은 사용자와 아이템을 차원 $f$의 공동 잠재 요인 공간(joint latent factor space)에 매핑하여 사용자-아이템 상호작용(interaction)이 해당 공간의 내적 공간(내적)으로 모델링되도록 한다.
각 아이템 $i$는 벡터 $q_i \in \mathbb{R}^f$와 관련되고, 각 사용자 $u$는 벡터 $p_u \in \mathbb{R}^f$와 관련된다.
주어진 아이템 $i$에 대해서, $q_i$의 요소들은 아이템이 긍정이든 부정이든 그러한 factor를 소유하는 정도를 측정한다.
주어진 사용자 $u$에 대해서, $p_u$의 요소들은 긍정 및 부정으로 아이템에 대한 사용자의 관심의 정도를 측정한다.
\[\hat{r_{ui}} = q_i^T p_{u\cdot}\]여기서, 주요 challenge는 각 아이템과 사용자를 factor vector $q_i, p_u \in \mathbb{R}^f$에 매핑하는 것이다.
이러한 모델들은 latent semantic factors을 식별하기 위한 singular value decomposition (SVD)와 밀접한 관련이 있다. SVD를 협업 필터링 도메인에 적용하기 위해서는 사용자-아이템 등급 행렬이 필요한데, 종종 sparseness로 인하여 어려움이 발생한다.
- 기존의 SVD는 불완전한 행렬에 적용할 수 없음.
- 적은 양의 관측 데이터만 활용할 경우 과적합의 위험이 존재함.
Factor vector ($p_u$와 $q_i$)를 학습하기 위해서, 알려진 ratings의 집합에서 regularized squared error을 최소화한다:
\[\min_{q*, p*} \sum_{(u,i) \in \kappa} (r_{ui} - q_i^Tp_u)^2 + \lambda(||q_i||^2 + ||p_u||^2)\]$\kappa$는 $r_{ui}$이 알려진 $(u, i)$ 쌍의 집합니다. 시스템은 과거의 관측 등급에 대해서 학습되며, 목표는 과거 등급을 일반화하여 알려지지 않은 등급을 예측하는 것이다.
Learning Algorithm
식 2를 최소화하는 두 가지 접근 방법으로는 stochastic gradient descent와 alternating least squares (ALS)가 있다.
Stochastic gradient descent
알고리즘은 training set의 모든 등급에서 반복하며, 주어진 각 훈션 세트에 대해서 $r_{ui}$를 예측하고 관련 예측 오차를 계산한다.
$e_{ui} =^{def} r_{ui} - q_i^Tp_{u\cdot}$
그런 다음, 기울기(gradient)의 반대방향으로 $\gamma$에 비례하는 만큼 파라미터를 수정한다:
- $q_i \leftarrow q_i + \gamma \cdot (e_{ui} \cdot p_u - \lambda \cdot q_i)$
- $p_u \leftarrow p_u + \gamma \cdot (e_{ui} \cdot q_i - \lambda \cdot p_u)$
Alternating least squares
$q_i$와 $p_u$가 모두 unknown이기 때문에, 식 2는 convex 하지 않다. 하지만, 만약 unknowns 중에서 하나를 고정하면, 최적화 문제는 quadratic이 되고 optimally 하게 풀 수 있다.
Convex
두 점 $x_1$과 $x_2$를 잇는 선분은 다음과 같이 정의된다:
$x = \theta x_1 + (1 - \theta) x_2$ with $0 \leq \theta \leq 1$
어떤 집합(set)이 주어져 있다고 가정하고, 이 집합의 원소인 두 점 $x_1$과 $x_2$를 잇는 선분이 이 집합에 다시 포함될 때 우리는 이 집합을 convex set이라고 부른다. 다시 말하면 집합 $C$가 convex가 될 조건은 다음과 같다.
$x_1, x_2 \in C, 0 \leq \theta \leq 1 \Rightarrow \theta x_1 + (1 - \theta) x_2 \in C$
그리고 Convex function은 다음과 같이 정의된다:
$f: R^n \rightarrow R$ is convex if dom f is a convex set and $f(\theta x + (1 - \theta) y) \leq \theta f(x) + (1 - \theta) y$ for all $x, y \in$ dom f, $0 \leq \theta \leq 1$
ALS 기법은 $q_i$와 $p_u$를 번갈아가며 고정한다. $p_u$가 고정될 때, $q_i$을 least-squared 문제로 다시 계산하고 반대의 경우도 동일하다. 이렇게 하면 식 2는 수렴할 때 까지 감소가 보장된다.
일반적으로, ALS보다 SGD가 더 쉽고 빠르지만, 다음의 두 경우에는 ALS 방법이 선호된다.
- 시스템이 병렬화(parallelization)를 사용할 수 있는 경우.
- 시스템이 암묵적(implicit) 데이터를 중심으로 하는 경우.
Adding Biases
식 1은 다른 등급을 생성하는 아이템과 사용자 간의 상호 작용을 찾으려고 시도한다. 하지만, 등급 값에서 관찰된 변동(variation)의 대부분은 상호 작용과는 무관한 biases 또는 intercepts에 의한 것이다.
예: 일부 사용자는 다른 사용자보다 더 높은 평점을 주는 경향이 있으며, 특저 아이템은 다른 아이템보다 더 높은 점수를 받는 경향(tendencies)이 있다.
등급 $r_{ui}$와 관련된 bias의 1차 approximation은 다음과 같다:
\[b_{ui} = \mu + b_i + b_u\]등급 $r_{ui}$에 관련된 편향(bias)는 $b_{ui}$로 표기되며, 사용자와 아이템 효과로 여겨진다. 전체 등급 평균은 $\mu$로 표기되며, 파라미터 $b_u$와 $b_i$는 각각 사용자 $u$와 아이템 $i$의 관측된 편차를 나타낸다.
bias는 식 1을 다음과 같이 확장한다:
\[\hat{r_{ui}} = \mu + b_i + b_u + q_i^T p_u\]관측된 등급은 global average(전체 평균), 아이템 편향, 사용자 편향 및 사용자-아이템 상호 작용의 4가지로 나뉜다. 각 요소는 그것과 관련된 신호의 부분만 설명할 수 있다. 시스템은 제곱 오차 함수(squared error function)을 최소화 함으로써 학습한다:
\[\min_{p\cdot, q\cdot, b\cdot} \sum_{(u,i) \in \kappa} (r_{ui} - \mu - b_i - b_i - p_u^Tq_i)^2 + \lambda (||p_u||^2 + ||q_i||^2 + b_u^2 + b_i^2)\]Additional Input Sources
많은 사용자들이 적은 양의 등급을 제공한다는 점에서 종종 시스템은 cold start 문제를 겪는다. 이러한 점은 그들의 취향(taste)에 도달하는 것을 어렵게 만든다.
이 문제를 완화하기 위한 방법으로는 사용자와 관련된 추가적인 정보를 통합하는 것이다. 추천 시스템은 사용자의 선호도(preference)에 대한 통찰(insight)을 얻기 위해 암묵적 피드백(implicit feedback을 사용할 수 있다.)
$N(u)$는 사용자 $u$가 암묵적 피드백을 표현한 아이템의 집합을 나타낸다. 이러한 방식으로 시스템은 암묵적으로 선호하는 아이템을 통해서 사용자를 프로파일링한다. 여기서, 아이템 $i$가 $x_i \in \mathbb{R}^f$와 관련이 있는 아이템 요인(factor)의 집합이 필요하다.
따라서, $N(u)$에서 아이템에 대한 선호를 보였던 사용자는 벡터로 특징화(characterized)된다.
$\sum_{i \in N(u)} x_i$
정규화된 형태는 다음과 같다:
$\mid N(u)\mid^{-0.5} \sum_{i \in N(u)} x_i$
사용할 수 있는 다른 정보로는 사용자 속성(attributes)가 있다. 예를 들어, 사용자 $u$가 성별, 연령, 우편 번호, 소득 수준 등을 설명할 수 있는 속성 $A(u)$ 집합에 해당하는 boolean 속성이다. distinct factor vector $y_a \in \mathbb{R}^f$는 사용자 관련 속성 집합을 통해서 사용자를 설명하는 각 속성에 해당한다:
$\sum_{a \in A(u)} y_a$
Matrix factorization 모델은 향상된 사용자 표현(representation)과 함께 모든 신호들을 통합해야 한다:
\[\hat{r}_{ui} = \mu + b_i + b_u + q_i^T [p_u + |N(u)|^{-0.5} \sum_{i \in N(u)} x_i + \sum_{a \in A(u)} y_a]\]일반적으로 데이터의 부족이 극심한 사용자의 경우를 예제를 들었지만, 아이템의 경우에도 적용 가능하다.
Temporal Dynamics
이전까지 소개한 모델들은 정적(static)이다. 실제 상황에서는, 아이템에 대한 인식(perception)과 인기(popularity)은 끊임없이 변화하며 사용자의 취향(taste)도 변화한다. 따라서, 시스템은 사용자-아이템 상호 작용의 동적이고 time-drifting 특성을 반영하는 시간적(temporal) 효과를 고려해야 한다.
-
item biases $b_i(t)$
아이템의 인기(popularity)는 시간이 경과함에 따라 변화한다. 그러므로, 아이템 bias $b_i$는 시간의 함수로 취급되어야 한다.
-
user biases $b_u(t)$
시간적 효과는 사용자가 시간에 따라 기준 등급을 변경할 수 있게 한다. 예를 들어, 평균적인 형화에 4점을 평가하던 사용자가 이제는 3점을 평가할지도 모른다. 따라서 매개변수 $b_u$는 시간의 함수이다.
-
user preferences $p_u(t)$
Temporal dynamic은 사용자의 선호도와 사용자와 아이템 간의 상호작용에도 영향을 미친다. 사용자는 시간이 지남에 따라 선호도가 변화한다. 따라서, user facotrs ($p_u$)또한 시간의 함수로 표현되어야 한다.
반면에, 사람과는 다르게 아이템의 특징(characteristics) $q_i$은 정적(static)이다.
time-varying 매개변수의 정확한 매개변수화(parameterizations)은 식 4를 시간 $t$에서의 등급에 대한 동적 예측 규칙으로 대체한다:
\[\hat{r_{ui}} (t) = \mu + b_i(t) + b_u(t) + q_i^T p_u (t)\]Inputs with Varying Confidence Levels
많은 설정에서, 관측된 모든 등급이 동일한 가중치(weight)나 신뢰도(confidence)를 갖지는 않는다. 그렇기 때문에, 시스템은 특정 아이템의 등급을 기울이려는(tilt) 적대적인(adversarial) 사용자에 직면할 수 있다.
또 다른 예로는 사용자의 행동을 해석하는 암묵적 피드백을 중심으로 구축된 시스템은 사용자의 정확한 선호도의 수준을 정량화하기 어렵다. 이런 경우에는, 선호도가 추정된 신뢰도의 점수를 붙이는 것이 중요하다. 신뢰도는 동작 빈도를 설명하는 수치에서 비롯될 수 있다.
Matrix Factorization은 다양한 신뢰 수준을 쉽게 수용할 수 있으므로 의미없는 관측치에 더 작은 가중치를 부여할 수 있다. 관측된 $r_{ui}$의 신뢰도가 $c_{ui}$로 표기되면, 모델은 다음과 같은 비용 함수(식 5)를 개선한다:
\[\min_{p\cdot, q\cdot, b\cdot} \sum_{(u,i) \in \kappa} c_{ui} (r_{ui} - \mu - b_u - b_i - p_u^T q_i)^2 \lambda ( ||p_u||^2 + ||q_i||^2 + b_u^2 + b_i^2)\]Netflix Prize Competition
2006년, Netfilx는 추천 시스템을 개선하기 위한 공모전을 진행하였다. 약 50만 명의 익명의 고객과 1만 7000여 편의 영화에 대한 평점 1억개 이상의 훈련 세트를 공개했으며, 각 평점은 1~5의 수치로 표현된다. 오차는 RMSE(root-mean-squared error)을 사용했다.
저자들이 제안한 방몀은 100개 이상의 다른 predictor sets로 구성되며, 대부분은 본 논문에서 설명한 방법의 일부분을 변형을 가한 factorization model이다.
넷플릭스 사용자-영화 행렬을 인수분해하면 영화 선호도를 예측하기 위한 가장 설명력이 높은 차원을 발견할 수 있다. 그림 3은 인수분해에서의 처음 두 가지 요인을 보여준다.
인수 분해를 위해서 다양한 구현과 매개변수화를 시도했는데, 그림 4는 다양한 모델과 매개변수의 수와 다양한 구현이 RMSE에 어떠한 영향을 미치는지를 보여준다.
각 모형의 정확도는 파라미터의 수가 증가할수록 향상되며, 이는 factor model의 차원성을 증가시키는 것과 같다.
또한 복잡한 모델이 더 정확함을 알 수 있다. 특히, 시간적 효과가 성능에 가장 중요함을 알 수 있다.