갈아먹는 추천 알고리즘 [3] Matrix Factorization

지난 글

갈아먹는 추천 알고리즘 [1] 추천 알고리즘의 종류

갈아먹는 추천 알고리즘 [2] Collaborative Filtering

들어가며

지난 글에서 Collaborative Filtering에 대하여 자세히 알아보았습니다.

세부적인 알고리즘으로는 Neighborhood model과 Latent Factor model을 소개하였습니다.

그리고 Implicit Dataset이 주어질 경우, Latent Factor model 가운데 Matrix Factorization이 적합하다고 마쳤습니다.

이번 글에서는 Matrix Factorization에 초점을 맞추어서

어떻게 평점 행렬을 사용자와 아이템 행렬로 쪼갤 수 있는지 알아보고자 합니다.

그리고 우리의 원래 목적인 사용자와 아이템의 Latent Factor 행렬을 어떻게 학습시킬 수 있는지 설명해보겠습니다.

Basic Concept

평점 행렬을 사용자와 아이템 Latent Factor 행렬로 분해

R은 사용자가 아이템에 남긴 평점을 행렬로 나타낸 것입니다.

R의 크기는 사용자 수(Nu) x 아이템의 수(Ni)가 됩니다.

Nf는 Matrix Factorization 학습 시에 정하는 임의의 차원 수입니다.

개발자가 조정 가능하며 보통 50에서 200 사이로 설정합니다.

X와 Y는 사용자와 아이템의 Latent Factor 행렬을 나타내며, 우리가 학습시키고자 하는 대상입니다.

이 행렬들의 값은 아주 작은 랜덤한 값들로 초기화됩니다. (R에 있는 값을 쪼개어 생성하는 것이 아닙니다!)

xu 와 yi는 각각 특정 사용자와 특정 아이템의 특징 벡터를 나타냅니다.

여기서 벡터는 1차원 어레이를 뜻하며, xu와 yi는 각각 Nf x 1 크기의 열 벡터 (column vector)로 볼 수 있습니다.

앞으로 xu를 특정 사용자의 Latent Vector, yi를 특정 아이템의 Latent Vector라고 하겠습니다.

분해된 행렬을 다시 곱하여 예측 평점 행렬을 계산

X 행렬의 전치 행렬 (Transpose)를 구하면 Nu x Nf 크기의 행렬이 됩니다.

이를 Y 행렬과 곱해주어 Nu x Ni 크기의 평점 예측 행렬을 구합니다.

예측된 하나의 평점 행렬의 각각의 값들은 다음과 같은 곱셈을 통해서 계산됩니다.

예측 평점 수식

해석해보면 특정 사용자의 Latent Vector와 특정 아이템의 Latent Vector를 곱하여 평점을 계산함을 알 수 있습니다.

Latent Factor Matrix가 적절하게 학습이 되었다면 예측된 R'은 R과 유사한 결과를 낼 것이라 예상할 수 있습니다.

Loss Function

이제 우리는 X와 Y를 학습시키기 위한 Loss Fucntion을 구할 수 있습니다.

바로 X와 Y를 곱하여 얻은 예측 평점 행렬의 오차가 최대한 작아지도록 수식을 구성하면 됩니다.

Loss Function

수식의 앞 부분은 예측된 평점과 실제 평점 간의 차이를 나타냅니다.

그리고 뒷 부분에 람다 표기가 붙은 부분은 모델이 오버 피팅 하지 않도록 정규화 시켜주는 역할을 수행합니다.

즉, 전체 모델에서 파라미터가 미치는 영향력을 감소시켜 줌으로써 모델의 일반화를 돕습니다.

람다의 크기는 데이터 셋마다 달라질 수 있으므로, 여러 실험을 통해 조절해 나가는 것이 바람직합니다.

Optimization

Loss Function도 구했으니 이제 이를 최소화하도록 X와 Y를 학습시킬 일만 남았습니다.

그러한 최적화를 수행하는 알고리즘으로 Gradient Descent와 Alternating Least Squares 알고리즘이 있습니다.

Gradient Descent를 적용하는 방식은 간단합니다. (아마 딥 러닝을 공부해보신 분들은 익숙하실 것 같습니다.)

loss를 미분하고, 여기에 learning rate를 곱한 다음 X와 Y 행렬의 값들을 업데이트 해주는 방식입니다.

개념적으로는 금방 와닿지만 막상 계산은 상당히 복잡하여 여기서는 다루지 않도록 하겠습니다. 

궁금하신 분들은 Andrew ng 교수님의 다음 강의를 참고하시면 좋을 듯 합니다. [1]

Gradient Update 수식

하지만 여기서 우리가 학습시켜야 하는 것은 X와 Y 행렬 두 개이고, 이 둘은 곱셉으로 묶여있습니다. (xuT x yi)

이 둘을 동시에 최적화 시키는 문제는 Non-convex problem으로 NP에 속합니다. 

(NP, Non-convex는 별도로  자세히 다룰 예정입니다.)

Gradient Descent로 이를 최적화 시키는 것은 너무 느리고 많은 반복이 필요하다는 단점이 있습니다. [2]

Alternatin Least Squares 는 이러한 문제를 멋지게 해결합니다.

X와 Y 둘 중 하나를 고정시키고 다른 하나를 최적화 시킵니다. 

그리고 이 과정을 번갈아가며 반복하여 짧은 시간 내에 최적의 X와 Y를 찾아냅니다.

이어지는 글에서는 ALS 알고리즘을 하나하나 뜯어보도록 하겠습니다.

궁금하신 점이 있거나 사실과 다른 내용이 있을 경우 댓글, 혹은 이메일을 남겨주세요.

감사합니다 :)

Reference

[1] Andrew ng, AI all in one 16-5, https://www.youtube.com/watch?v=9siFuMMHNIA

[2] Standford CME 323, http://stanford.edu/~rezab/classes/cme323/S15/notes/lec14.pdf