Matrix Factorization 설명 및 논분 리뷰
20 Dec 2019 | Machine_Learning Recommendation System Matrix Factorization Latent Factor Collaborative Filtering목차
- 1. Introduction
- 2. MF Methods and A Basic MF Model
- 3. Learning Algorithms and Adding Biases
- 4. Additional Input Sources and Temporal Dynamics
- 5. Inputs with varying confidence levels
본 글은 2009년에 발표된 Matrix Factorization Techniques for Recommender Systems 논문을 리뷰하고 간단히 요약 정리한 글이다. 논문 원본은 이곳에서 다운 받을 수 있다.
1. Introduction
컨텐츠 기반 필터링은 각 사용자나 아이템에 대해 프로필을 만들고, 그 특성을 구체화하는 방식으로 이루어진다. 반면 위 방식의 대안이라고 할 수 있는 협업 필터링은 어떤 명시적(Explicit) 프로필을 만들지 않고, 이전 구매 기록이나 제품 평가 기록 등 과거 사용자 행동에만 의존해서 시스템을 구성한다. 이 방식은 유저-아이템 간의 상관관계를 찾아내는 것이 주 목적이라고 할 수 있다.
협업 필터링은 Domain-free 즉, 특별히 이 분야에 대한 지식이 필요하지 않다는 장점을 가진다. 반면 새로운 사용자와 아이템을 다루기에 부적합하다는 Cold Start Problem이라는 한계를 갖고 있다.
협업 필터링은 근접 이웃 방법과 잠재 요인 방법로 나뉜다. 후자의 경우 평점 패턴에서 20~100가지의 factor(요인)을 추론하는 것을 목적으로 한다.
2. MF Methods and A Basic MF Model
잠재 요인 협업 필터링을 구현하는 가장 좋은 방법 중 하나는 Matrix Factorization이다.
기본적으로 이 방법은 평점 패턴으로부터 추론한 요인 벡터들을 통해 사용자와 아이템의 특성을 잡아낸다. 이 때 사용자와 아이템 사이의 강한 관련성이 있다면 추천이 시행된다. 이 방법은 확장성, 높은 정확도, 유연성이라는 장점을 가진다.
추천 시스템은 여러 종류의 Input Data를 활용할 수 있다. 물론 가장 좋은 것은 양질의 명시적 피드백(Explicit Feedback)이 될 것인데, 이는 영화 평점이나 좋아요/싫어요와 같은 아이템에 대한 사용자의 선호 결과를 의미한다. 일반적으로 이러한 피드백은 그리 많이 이루어지지 않기 때문에, 이를 행렬로 정리하면 희소(Sparse) 행렬이 될 수 밖에 없다.
만약 이러한 명시적 피드백 조차 활용할 수 없을 때는, 추천 시스템은 암시적 피드백(Implicit Feedback)을 이용하여 사용자의 선호를 파악하게 된다. 이는 구매내역이나 검색기록, 검색 패턴, 커서의 움직임 등을 의미하며 이를 통해 사용자의 선호를 파악하는 것이 목표라고 할 수 있겠다.
Matrix Factorization(이하 MF 또는 행렬 분해) 모델은 사용자와 아이템 모두를 차원 f의 결합 잠재요인 공간에 매핑하는데, 사용자-아이템 상호작용은 이 공간에서 내적으로 모델링 된다.
아이템 i는 $ q_i $로, 사용자 u는 $ p_u $라는 벡터로 표현된다. 이 둘의 내적은 사용자-아이템 사이의 상호작용을 반영하며 이는 곧 아이템에 대한 사용자의 전반적인 관심을 표현한다고 볼 수 있다. 식은 아래와 같다.
\[\hat{r_{ui}} = q^{T}_i p_u\]이 모델은 사실 SVD(Singular Vector Decomposition)과 매우 유사한데, 추천 시스템에서는 결측값의 존재로 이 SVD를 직접적으로 사용하는 것은 불가능하다. 결측값을 채워 넣는 것 역시 효율적이지 못하고 데이터의 왜곡 가능성 때문에 고려하기 힘들다.
따라서 오직 관측된 평점만을 직접적으로 모델링하는 방법이 제시되었으며, 이 때 과적합을 방지하기 위해 규제 항이 포함되었다. 요인 벡터 $ q_i, p_u $를 학습하기 위해 시스템은 관측된 평점 세트를 바탕으로 아래 식을 최소화하는 것을 목적으로 한다.
\[\min_{q, p} \sum_{(u, i) \in K} ( r_{ui} - q^T_i p_u )^2 + \lambda (\Vert{q_i}\Vert^2 + \Vert{p_u}\Vert^2)\]이 때, K는 $ r_{ui} $가 측정된(known) 값일 때의 (u, i) 세트를 의미한다. 결과적으로 이 모델은 알려지지 않은 평점을 예측하는 것이 목적이기 때문에 과적합을 방지해야 하고, 이를 위해 규제항이 필요하고 $ \lambda $가 이 규제의 정도를 제어한다. $ \lambda $는 주로 Cross-Validation에 의해 결정된다.
3. Learning Algorithms and Adding Biases
이전 장에서 본 식을 최소화하기 위한 방법으로는 2가지가 제시된다.
3.1. Stochastic Gradient Descent
각각의 훈련 세트에 대해 본 알고리즘은 $ r_{ui} $를 예측하고 다음과 같은 예측 오차를 산출한다.
\(e_{ui} = r_{ui} - q^T_i p_u\)
이후 $ q_i $와 $ p_u $를 아래와 같이 업데이트 한다.
\(q_i := q_i + \gamma (e_{ui} p_u - \lambda q_i)\)
\(p_u := p_u + \gamma (e_{ui} q_i - \lambda p_u)\)
확률적 경사하강법은 구현이 쉽고 빠르다는 장점을 지닌다.
3.2. Alternating Least Squares
$ q_i $와 $ p_u $가 둘다 미지의 값이기 때문에 앞서 최소화하려고 했던 식은 convex하지 못하다. 그러나 만약 둘 중 하나를 고정(fixed)할 수 있다면, 이 최적화 문제는 quadratic하게 바뀌어 해를 구할 수 있게 된다. 따라서 ALS는 $ q_i $를 고정했다가 다음 번에는 $ p_u $를 고정하는 방식으로 작동한다. $ p_u $가 고정되어 있다면 본 알고리즘은 최소제곱법으로 $ q_i $를 다시 계산한다. 이러한 방법으로 목적 함수(2장에서 본 최소화 시켜야 할 식)를 최소화할 수 있는 것이다.
3.1장에서 본 SGD가 일반적으로 편리한 방법이긴 하지만 아래의 2가지 경우에는 이 ALS가 효과를 발휘하기도 한다.
- 시스템이 병렬화를 지원하는 경우
- 시스템이 암시적 데이터에 집중되어 있는 경우
3.3. Adding Biases
$ \hat{r_{ui}} = q^{T}_i p_u $ 식은 여러 평점 결과를 만들어 내는 사용자와 아이템 간의 상호관계를 파악하는 것이 목적이다. 그런데 사실 많은 경우에 이 상호작용 외에 사용자나 아이템 자체의 특성이 이러한 평점 결과에 영향을 미친다. 이것을 우리는 biases 또는 intercepts라고 부른다. 이를 앞서 보았던 방정식과 목적 함수에 적용해보면 아래와 같다.
\[\hat{r_{ui}} = \mu + b_i + b_u + q^{T}_i p_u\] \[\min_{p, q, b} \sum_{(u, i) \in K} ( r_{ui} - \mu - b_i - b_u - q^T_i p_u )^2 + \lambda (\Vert{q_i}\Vert^2 + \Vert{p_u}\Vert^2 + b^2_u + b^2_i)\]4. Additional Input Sources and Temporal Dynamics
종종 시스템은 Cold Start 문제에 직면하게 되는데, 평점 데이터에 기반한 추천 시스템을 만드는 상황에서는 사용자들이 평점 결과를 거의 남기지 않는 상황이 이 문제에 해당한다고 볼 수 있다. 이럴 때에는 사용자에 대한 추가적인 정보 소스들을 모두 통합할 필요가 있다. 즉, 행동 정보(Behavior Information)들이 필요하다는 것이다. 예를 들어 소매업자는 고객의 구매 기록이나 검색 기록 등을 활용할 수 있을 것이다.
단순화하기 위해 Boolean 암시적 피드백이 있는 경우를 생각해보자. $ N(u) $는 사용자 $u$가 암시적 선호를 표현한 아이템의 집합을 의미한다. 시스템은 이를 통해 사용자의 프로필을 만들어 낸다. $ N(u) $에 속한 아이템에 대한 선호를 표현한 사용자는 아래 벡터와 같이 표현된다.
\[\sum_{i \in N(u)} x_i\]이 식을 정규화하는 것이 일반적으로 더 좋은 결과를 가져오기에, 정규화를 하겠다.
\[|N(u)|^{-0.5} \sum_{i \in N(u)} x_i\]또 중요한 정보는 인구학적 정보와 같은 사용자 속성(User Attributes)이다. 유사하게 표현하면 아래와 같다.
\[\sum_{a \in A(u)} y_a\]모든 Signal Source를 통합하여 개선된(Enhanced) 사용자 표현식은 아래와 같다.
\[\hat{r_{ui}} = \mu + b_i + b_u + q^T_i [p_u + |N(u)|^{-0.5} \sum_{i \in N(u)} x_i + \sum_{a \in A(u)} y_a]\]지금까지의 모델은 사실 정적(static)인 모델이었다. 즉, 시간의 변화를 반영하지 못한다는 뜻이다. 그러나 현실에서는 제품에 대한 인식, 인기는 새로운 선택지가 늘어남에 따라 시시각각 변하기 마련이다. 또한 고객들의 성향도 진화하여 그들의 취향은 때때로 변화한다. 따라서 추천 시스템은 시간에 따라 변하는 사용자-아이템 상호작용의 동적(dynamic)인 성질을 반영하는 Temporal Effect에 대해 설명할 수 있어야 한다.
총 3개의 항이 변화한다.
$ b_i(t) $: 아이템의 인기는 시간에 따라 변한다.
$ b_u(t) $: 사용자의 성향도 시간에 따라 변한다. (baseline rating)
$ p_u(t) $: 시간이 흐름에 따라 아이템에 대한 사용자의 선호는 변화할 수 있다.
단 (설정에 따라) 아이템의 성격은 (이미 만들어졌기에) 변하지 않으므로 아이템은 시간에 관한 함수로 구성되지 않는다. 최종적으로 정리하면 아래와 같은 식이 만들어진다.
\[\hat{r_{ui}}(t) = \mu + b_i(t) + b_u(t) + q^T_i p_u(t)\]5. Inputs with varying confidence levels
모든 관측값이 같은 신뢰도(confidence)를 가지는 것은 아니다. 예를 들어 어떤 적대적 사용자는 별 이유 없이 낮은 평점을 제공할 수도 있는 것이다. 따라서 추천 시스템을 더욱 공고히 하기 위해서는, 예측된 선호도에 신뢰도를 붙여야(attach) 한다. 이 신뢰도는 action의 빈도를 설명하는 실수 값인데, 예를 들어 특정 사용자가 특정 show를 얼마나 오래, 자주 보았는가와 같은 값이 신뢰도가 될 수 있다. 이러한 특성을 목적 함수에 반영하면 아래와 같이 될 것이다.
\[\min_{p, q, b} \sum_{(u, i) \in K} c_{ui}( r_{ui} - \mu - b_i - b_u - q^T_i p_u )^2 + \lambda (\Vert{q_i}\Vert^2 + \Vert{p_u}\Vert^2 + b^2_u + b^2_i)\]