#5 행렬 인수분해(Matrix Factorization)

[이전 글]#4 추천 시스템 - 협업 필터링(Collaborative Filtering) 기초

 

---

1. 행렬 인수 분해(Matrix Factorization)

 행렬 인수 분해는 간단한 임베딩 모델이다. $m$은 User(or query)의 수이고, $n$은 Item의 수인 피드백 매트릭스 $A \in R^{m \times n}$가 주어질 때 모델은 row $i$는 User $i$ 임베딩인 User 임베딩 매트릭스 $U \in R^{m \times d}$와, row $j$는 Item $j$ 임베딩인 Item 임베딩 매트릭스 $V \in R^{n \times d}$를 학습한다.

$UV^T$의 내적(Dot Product)이 피드백 매트릭스 A의 근삿값이 되도록 임베딩을 학습한다. $U.V^T$에서 $(i, j)$는 User $i$와 Item $j$ 임베딩의 내적(Dot Product) $\langle U_i, V_j \rangle$이다. 이는 $A_{i, j}$에 가까워지기를 원하는 값이다.

 

---

2. 목적 함수의 선택(목적함수:모델에 대하여 일반적으로 사용하는 용어, 최댓값·최솟값을 구하는 함수)

제곱 거리(Squared distance)는 직관적인 목적 함수 중 하나다. 이는 관찰된 모든 항목의 제곱 오차 합계를 최소화한다.

$\min_{U \in R^{m \times d}, V \in R^{n \times d}} \sum_{(i,j)\in obs}(A_{ij} - \langle U_i, V_j \rangle)^2$

 

이 목적 함수에서는 관찰 된 쌍 $(i, j)$, 즉 피드백 매트릭스의 0이 아닌 값에 대해서만 합산한다. 그러나 하나의 값을 합산하는 것은 좋은 생각이 아니다. 모든 것의 행렬은 손실이 최소화되고 효과적인 추천 사항을 만들 수 없고, 일반화를 잘 수행하지 못 한다.

 관찰되지 않은 값을 0으로 처리하고 행렬의 모든 항목에 대한 합계를 계산할 수 있다. 이는 $A$와 근삿값 $UV^T$ 사이의 제곱된 Frobenius 거리를 최소화하는 것에 해당한다.

 

$\min_{U \in R^{m \times d}, V \in R^{n \times d}}||A-UV^T||^2_F$

 행렬의 SVD (Singular Value Decomposition)를 통해 이차 문제를 해결할 수 있다. 그러나 실제 활용에서는 매트릭스 A가 매우 희박(sparse)할 수 있기 때문에 SVD도 훌륭한 솔루션이 아니다. 예를 들어 특정 사용자가 본 모든 비디오와 YouTube의 모든 비디오를 비교한다고 생각해보라. 솔루션 $UV^T$(입력 행렬의 모델 근삿값에 해당하는)는 0에 가까워 일반화 성능이 저하될 수 있다.

 

반대로 가중 행렬 인수 분해는 목표를 다음 두 가지 합계로 분해한다. 관찰된 항목에 대한 합계와, 관찰되지 않은 항목에 대한 합계(0으로 처리)이다.

$\min_{U \in R^{m \times d}, V \in R^{n \times d}} \sum_{(i,j)\in obs}(A_{ij} - \langle U_i, V_j \rangle)^2+ w_0 \sum_{(i,j)\notin obs}(\langle U_i, V_j \rangle)^2$

여기서 $w_0$는 두 항에 가중치를 부여하여 목표가 서로 지배되지 않도록하는 하이퍼 파라미터다. 이 하이퍼 파라미터를 조정하는 것은 매우 중요하다.

 

참고) 실제 활용에서는 관찰된 쌍에 신중하게 가중치를 부여해야한다. 예를 들어, 자주 사용하는 Item(예 : 매우 인기 있는 YouTube 비디오) 또는 자주 사용하는 Query (예 : 헤비 유저)가 목적 함수를 지배할 수 있다. Item 빈도를 설명하기 위해 가중 훈련 예제를 통해 이 효과를 수정할 수 있다. 즉, 목적 함수를 다음과 같이 대체할 수 있다.

$\sum_{(i,j)\in obs}w_{i,j}(A_{ij} - \langle U_i, V_j \rangle)^2+ w_0 \sum_{(i,j)\notin obs}(\langle U_i, V_j \rangle)^2$

여기서 $w_{i,j }$는 Query $i$ 및 Item $j$의 빈도 함수이다.

---

3. 목적 함수의 최소화

 목적 함수를 최소화하는 일반적인 알고리즘에는 두 가지가 있다. 첫 번째는 확률적 경사 하강법(Stochastic gradient descent - SGD)으로 Loss Function을 최소화하는 일반적인 방법입니다. 두 번째 WALS(Weighted Alternating Least Squares)는 특정 목표에 특화되어 있다.

 

목표는 두 행렬 $U$와 $V$에서 각각 이차 형식이다. (그러나 문제는 공동으로 볼록하지 않습니다.) WALS는 임베딩을 무작위로 초기화 한 다음, V를 해결하기 위해 U를 수정하고, U를 해결하기 위해 V를 수정하는 것을 번갈아하며 작동합니다.

 

 각 단계는 정확하게 해결될 수 있으며(선형 시스템의 솔루션을 통해), 분배될 수 있다. 이 기술은 각 단계가 Loss를 줄이도록 보장되므로 수렴이 보장된다.

---

4. SGD vs. WALS

 SGD와 WALS는 각각 장·단점이 있다.

 - SGD의 장·단점

장점1 : 매우 유연하여 다른 Loss function을 사용할 수 있다.

장점2 :병렬화 할 수 있다.

단점1 : 느리다 - 빠르게 수렴하지 않는다.

단점2 : 관찰되지 않은 항목을 다루기가 더 어렵다(Negative Sampling 또는 Gravity를 사용해야 함).

 

 - WALS의 장·단점

장점1 : 병렬화 할 수 있다.

장점2 : SGD보다 빠르게 수렴한다.

장점3 : 관찰되지 않은 항목을 보다 쉽게 처리할 수 있다.

단점1 : Loss Squares에만 의존한다.

---

[출처] 구글 머신러닝 추천 시스템 https://developers.google.com/machine-learning/recommendation

---

공감과 댓글, 그리고 공유는 큰 힘이 됩니다 : )