관리 메뉴

갈아먹는 머신러닝

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

갈아먹는 추천 알고리즘

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

형준킴 염창동형준킴 2019. 3. 21. 02:26

지난 글

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

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


들어가며


지난 글에서 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


9 Comments
  • 프로필사진 ㅎㅈ 2019.09.08 01:03 안녕하세요! 글 정말 잘 읽었습니다. ALS 궁금해서 찾아보던 중에 읽고 많은 도움을 받았어요 그런데 마지막 부분에서 조금 이해가 안 가는 부분이 있어서 질문 드립니다. (9)부분에서 "YCuYT와 YTCuY는 결국 계산하면 1x1 크기의 스칼라 값이므로 이 둘은 같습니다." 라고 써있는데, YCuYT가 계산결과 Nf*Nf크기가 나올 것 같고, transpose취하는 순간 크기가 다른 Cu를 중간에 끼울수도 없게될 것 같은데 두 행렬을 같다고 할 수 있는 이유가 무엇일까요...?
  • 프로필사진 형준킴 염창동형준킴 2019.10.30 11:12 신고 안녕하세요! 답변이 늦어서 죄송합니다. 결론부터 말씀드리면 최대한 논문에 기재된 수식을 그대로 재현하는 과정에서 오류가 있었던 것 같습니다. 굳이 YTCuY로 변환 하지 않더라도 계산이 가능하지만, 이를 논문에 나온 수식에 맞추려는 의도였는데 실수가 있었네요. 좋은 지적 감사드립니다!
  • 프로필사진 ㅎㅎ 2019.10.29 19:32 하단부 Y, Y의 transpose 하는 부분의 연산에서 Y 정의가 잘못되어서 아래 수식에 오류가 있는 듯 합니다. 물론 최종 Xu vector에 결과는 맞지만 과정속에 오류가 있는 것 같네요.
  • 프로필사진 형준킴 염창동형준킴 2019.10.30 11:13 신고 좋은 지적 감사드립니다. 논문에 기재된 수식 그대로 재현해보려던 과정에서 실수가 있었던 것 같습니다. 감사합니다!
  • 프로필사진 궁금 2020.01.28 17:40 수식의 어느 부분이 잘못된 지 알 수 있을까요? 고쳐진건지는 모르겠는데 봤을때는 아무 이상 없어보여서 ㅠ
  • 프로필사진 질문 2019.11.04 16:02 sparse 한 정도에 따라 ALS 알고리즘 반복횟수를 조절하라고 하셨는데, 데이터가 sparse 할수록 반복횟수를 늘려야한다는 뜻인가요?
  • 프로필사진 형준킴 염창동형준킴 2019.11.04 16:05 신고 논문을 보면 반복 횟수 같은 부분은 경험적으로 해보면서 최적의 결과를 찾습니다! als 경우엔 사실 학습에 많은 시간이 소요되지 않으므로 직접 다양한 환경에서 실험해보는 것이 좋을 것 같네요 ㅎㅎ
  • 프로필사진 질문 2020.02.04 12:11 식5에서 식6으로 갈 때 xu로 묶어주기 위해 람다xu가 시그마 안에 들어갔는데 그럼 시그마가 돌아가는 횟수만큼 람다xu를 i로 나누어주어야 하지 않나요?? 아니면 괄호를 한번 더 써야하는게 아닌가요!?
  • 프로필사진 형준킴 염창동형준킴 2020.02.04 16:26 신고 표기에 약간 혼선이 있었던 것 같습니다. 애초에 로스 펑션의 미분 값에서 람다 xu는 시그마 안에 포함되지 않습니다. (5)번 식의 좌변에서는 시그마 뒤에 곱셈으로 묶인 식들만 시그마에 포함되며 그 위에 람다 xu는 시그마에 포함되지 않습니다. 시그마 안의 xu를 밖으로 빼주게 되면 전체 식은 xu(시그마 ...) + 람다 xu 형태가 되며 이는 다시 xu(시그마 ... + 람다I) 형태가 됩니다.

    충분한 답변이 되었는지 모르겠네요 ㅎㅎ 혹시 더 의아하신 부분이 있다면 말씀해주세요
댓글쓰기 폼