갈아먹는 추천 알고리즘 [4] Alternating Least Squares

지난 글

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

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

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

들어가며

지난 글에서 Matrix Factorization와 Latent Factor의 개념을 살펴보았습니다.

그리고 이를 학습시키기 위한 Loss function까지 알아보았습니다.

이 Loss Function을 최소화하는 사용자와 아이템의 Latent Factor Matrix를 찾아내는 것이 우리의 목표였습니다.

이를 학습시키기 위한 방법으로 Gradient Descent와 Alaternating Least Squares(이하 ALS)를 소개하였으며,

ALS가 더 적합한 방법이라고 알아보았습니다.

이번 글에서는 ALS를 스텝 바이 스텝으로 분석해보도록 하겠습니다.

단, 이 글에서 소개하는 ALS 알고리즘은 Colloaborative Filtering For Implicit Datasets[1] 논문을 기반으로 합니다.

세부적인 수식은 논문 별로 조금씩 다를 수 있음을 미리 언급합니다.

Basic Concept

이름에서 짐작할 수 있듯이 ALS는 사용자와 아이템의 Latent Factor를 한번 씩 번갈아가며 학습시킵니다.

두 행렬을 한꺼번에 최적화시키는 것은 어렵기 때문에 둘 중 하나를 고정시킵니다.

아이템의 행렬을 상수로 놓고 사용자의 행렬을 학습시키고,

사용자 행렬을 상수로 놓고 아이템 행렬을 학습시키는 방식입니다.

이 과정을 계속 반복하면서 최적의 사용자와 아이템 Latent Factor를 학습시킵니다.

구체적인 수식으로 넘어가 보도록 하겠습니다.

Loss Function

잠시 Loss fuction으로 돌아가보겠습니다.

아래 수식을 살펴보면 앞서 보았던 Loss Function과 조금 다른 것을 볼 수 있습니다.

Loss Function (하단의 사용한 표기 참조)

기존의 Loss Function에서는 단순히 원래 rating 에서 예측된 rating을 빼준 값의 제곱을 사용하였습니다.

하지만 새로운 Loss Function 에서는 rui 대신에 cui와 pui가 새롭게 추가된 것을 볼 수 있습니다.

이는 평점 예측을 선호도를 나타내는 p와 그 예측값의 신뢰도를 나타내는 c로 나누어 준 것입니다.

먼저 선호를 나타내는 p 입니다.

Implicit Dataset에서의 평점은 선호와 비선호를 구분하지 않습니다. (아리까리 하면 [이전 글]을 참고하세요)

때문에 평점 데이터가 존재할 경우 선호함을 나타내는 1, 반대의 경우 0으로 바꾸어줍니다.

다음으로 해당 데이터의 신뢰도를 나타내는 c입니다.

앞서서 우리는 평점이 남아있지 않은 데이터는 모두 0으로 바꾸어주었습니다.

여기에는 실제 선호하지만, 평점이 남아있지 않은 데이터들도 포함되어 있습니다.

즉, 데이터의 신뢰도가 낮은 것으로 볼 수 있습니다.

이 논문에서는 이 신뢰도 변수를 도입하여 평점이 남아있지 않은 데이터에 대한 예측 값도

전체 Loss Function에 영향을 주도록 만들었습니다.

이는 평점이 남아있지 않은 데이터는 모두 학습에서 제외한 Explicit Dataset과 대조적입니다.

또한 이러한 데이터는 낮은 c값을 갖게하여, loss에 포함하되 영향력이 작게끔 조절하였습니다.

사용자가 높은 평점을 주어 명확하게 선호임을 파악할 수 있는 경우엔 영향력이 높아지게끔 합니다.

여기서 '어차피 가중치가 낮으면, 평점이 0인 데이터는 있으나 마나한거 아닌가?' 라는 의문이 들 수 있습니다.

하지만 Implicit Dataset을 보면 평점이 남는 아이템보다 0으로 남아있는 데이터가 훨씬 더 많습니다.

쇼핑몰 클릭 로그의 사례를 떠올려 보겠습니다.

우리가 미칫듯이 클릭을 하며 아이쇼핑을 하더라도 클릭하게 되는 상품은 전체 중 아주아주 일부분입니다.

그 외의 상품들은 클릭 횟수가 0인 채로 남아있을 것입니다.

이러한 행렬 데이터를 Sparse Matrix라고 합니다.

실제 값보다 0이 더 많은 Sparse Matrix

기존에 Explicit Dataset을 다루었던 기법들은 이렇게 0으로 남은 데이터들은 버리고 학습을 진행하였습니다.

하지만 앞서 제시되었던 신뢰도 지수 c를 통해서 0으로 남아있는 방대한 아이템들에 대한 예측 값도 

Latent Factor 학습에 포함시킬 수 있게 되었습니다.

또한 가중치가 낮다 하더라도 그 수가 평점이 남은 아이템들이 비해 

월등히 많기 때문에 학습에 유의미한 영향을 미치게 됩니다.

이제 새롭게 얻은 Loss Function을 최적화 시키는 ALS에 대해서 알아보도록 하겠습니다.

Alternating Least Squares (ALS)

ALS는 먼저 사용자 혹은 아이템의 Latent Factor 행렬을 아주 작은 랜덤 값으로 초기화합니다.

그 다음 둘 중 하나를 상수처럼 고정시켜 Loss Function을 Convex Function으로 만듭니다.

그리고 이를 미분한 다음, 미분 값을 0으로 만드는 사용자 혹은 아이템의 Latent Factor 행렬을 계산합니다.

이 과정을 사용자 한번, 아이템 한번 반복하면서 최적의 X, Y를 찾아내는 것입니다.

먼저 아이템의 Latent Factor 행렬을 고정하고 사용자의 Latent Factor를 최적화시키는 과정을 살펴보겠습니다.

아이템 행렬을 고정된 상수로 놓고 Loss Fuction을 미분하면 다음과 같습니다.

이 값이 0이 되게끔 하는 Xu를 찾기 위해서 미분한 식을 전개하면 다음과 같습니다.

(행렬의 미분이 다소 까다롭습니다. 문돌이인지라 이 부분을 이해하는데 많이 고생했습니다 ㅠㅠ)

이를 다시 전개한 다음 좌변 우변을 나누어 정리해주면 다음과 같습니다. 

여기서 xTuyi를 계산하면 1x1 크기인 스칼라 값이 나옵니다.

즉, xTuyi의 전치 행렬(Transpose)를 구해도 동일한 스칼라 값이 나오게 됩니다.

여기서 다시 Cui 역시 스칼라 값이기 때문에 뒤에 오는 yTixu와 순서를 바꾸어도 결과값은 동일합니다.

여기서 xu를 밖으로 빼주고 항을 정리하면 다음과 같은 형태가 나옵니다. 

여기서 I는 단위 행렬 (Identity Matrix)를 말합니다.

여기서 좌변의 시즈마를 먼저 정리해보도록 하겠습니다.

모든 아이템 개수만큼 벡터와 스칼라 곱을 수행하는 이 식은 하나의 행렬 곱으로 나타낼 수 있습니다.

먼저 원본 Y 행렬과 그 전치 행렬을 곱해보았습니다.

그 결과 시그마 안의 식 중 yiyT 부분에 해당하는 식을 얻어낼 수 있습니다.

하지만 여기에는 신뢰도 변수 cui가 빠져있습니다.

각 i에 맞는 신뢰도를 곱해주기 위해서는 Cui를 diagonal matrix로 만든 다음, 그 사이에 곱해주면 됩니다.

이렇게 구한 식으로 (6)의 식을 정리해보겠습니다.

(6) 식의 우변 역시 비슷한 방식으로 정리하면 다음과 같은 결과를 얻을 수 있습니다.

이제 좌변에 Xu만 남기기 위해서 양변에  같은 역행렬을 곱해주면 다음과 같은 식이 나옵니다.

YCuYT와 YTCuY는 결국 계산하면 1x1 크기의 스칼라 값이므로 이 둘은 같습니다.

드디어 우리는 Loss의 미분 값을 0으로 만드는 Xu 행렬을 찾아낸 것입니다!

이제 X를 위 식을 통해 계산한 다음 업데이트 해줍니다. 

다음으로 사용자 행렬 X를 고정시키고, 아이템에 대하여 같은 작업을 반복하면 같은 형태의 수식을 얻을 수 있습니다.

이를 통해 Y 행렬을 계산하여 업데이트 해줍니다.

이 과정을 반복함으로써 최적의 X와 Y를 찾아내는 것이 ALS 알고리즘의 핵심입니다.

논문이나 실제 구현체[2]를 참고하여 보면 보통 이 반복하는 횟수를 10회에서 15회 정도로 설정합니다.

하지만 데이터의 양이나 Sparse 정도에 따라서 조절해나가는 것이 바람직합니다. 

사용한 표기

궁금하신 점이나 사실과 다른 부분이 있다면 댓글 혹은 이메일로 남겨주세요 :)

감사합니다.

Reference

[1] Y. Hu et al, Collaborative Filtering for Implicit Feedback Datasets

[2] Benfred, implicit, https://github.com/benfred/implicit