Matrix Factorization _ Part3

이 글은 Nicolas hug씨의

Understanding mtrix factorization 

for recommendation (part 3)

을 한글로 번역한 글입니다.  

오역이나 잘못 설명된 부분을 발견하신 분은 댓글로 알려주시면 감사하겠습니다.

SVD for recommendation

 지난 시간까지 잘 따라왔다면 SVD가 무엇인지, 그리고 SVD가 점수(rating)를 어떤 식으로 모델링 할 수 있는지에 대한 이해가 됐을 거라 생각한다.

그렇다면 이제 가장 중요한 이야기를 할 때다.

 SVD를 추천시스템에 어떻게 적용할지에 대해 이야기해보자.  SVD로 점수를 예측하는 방법이라고도 할 수 있겠다.

 맨 처음에 얘기했던 우리의 sparse matrix R을 다시 떠올려보자

우리의 목표는 여기서 '?'로 표시되어 있는 부분을 채우는 거였다.

잠깐!

그런데 우리는 R의 SVD를 아직 정의하지 않았다. 왜냐면... 계산할 수 없기 때문이다. 

위와 같이 비어있는 행렬을 가지고 SVD를 계산하는 것은 불가능하다. 

 하지만 걱정마라. 우리가 지난 시간에 배웠던 것들을 여기에 적용시킬 수 있다!

 만약 R이 dense matrix였다면 우리는 M과 U를 쉽게 구할 수 있을 것이다. M의 열은 R*R^T의 eigenvectors이고 U의 열은 R^T*R의 eigenvectors다. 그리고 이와 관련된  eigenvalues 는 대각행렬Σ를 만들어 낸다.

그런데 우리 R은 sparse하기 때문에 R*R^T와 R^T*R은 존재하지 않는다. 때문에 이것들의 eigenvector도 없고 R을 MΣU^T 로 factorize할 수도 없다.

 그러나 방법이 없는 것은 아니다. 한 가지 적용해 볼 수 있는 방법은 Heuristic이다. 예를 들어 행이나 열의 평균값으로 빈 요소들을 채워볼 수 있다.

 행렬이 dense해지기만 한다면 우리는 우리가 배운 방법을 그대로 사용해 SVD를 써먹을 수 있다. 

 그래 그렇게 한다 치자. 하지만 이 방법은 편향된(biased) 결과를 낼 가능성이 높다. 

 그래서 우리는 조금 다른 방법인 minimization problem을 이용해 문제를 풀어 나갈 것이다.

The alternative

 사실 dense matrix의 SVD를 계산하는 방법이 R&R^T와 R^T*R의 eigenvectors를 구하는 것만 있는 것은 아니다. 만약 우리가 M의 행들인 p_u와 U^T의 열들인q_i 만 찾을 수 있다면 M과 U를 구할 수 있다.

그리고 모든 user와 item의 p_u와 q_i를 찾는 문제는 optimization problem 문제를 적용해 해결할 수 있다.

위 식을 한마디로 말하자면 "위 수식을 가장 작게 만드는 p_u와 q_i를 찾자"는 뜻이다.  

 In other words: we’re trying to match as well as possible the values 

rui with what they are supposed to be: pu⋅qi.

-> 달리 말하자면 r_(ui)와 p_u*q_i를 매칭시키는? (역자: 해석이 잘 안되네요 나중에 다시 수정하겠습니다.)

I’m abusing notation here and referring to R as both a matrix and a set of ratings.

-> 수식을 던져놓고 R을 행렬, 점수의 집합으로 표현했다. (역자: 무슨 의미로 쓰인 말인지 잘 모르겠습니다.)

만약 위 값을 최소로 만들어주는 p_u와 q_i를 찾는다면 우린 M과 U를 만들어 SVD를 구할 수 있을 것이다. (최솟값은 0일 것이다.)

위의 예제는 dense matrix일 때였고... 이번에도 어김없이 R이 sparse할 경우에 대해서 이야기를 해보자.

Simon Funk 씨는 이에 대한 답으로 다음과 같이 이야기했다.

"그냥 똑같이 optimization problem으로 풀자!"

앞선 예제와의 차이는 sparse하다는 것, 즉 행렬에 빈 값들이 있다는 것 뿐이다. 

여기서 주의할 것은 빈 값이라고 해서 우리가 그 값을 0이라고 생각하지는 않는다는 것이다.

그리고, PCA에서 이야기 했던 M의 열들이 직교(orthogonal)해야 한다는 제약은 잠깐 잊어버리자. 

그 특성이 해석에 도움이 될 수는 있지만 정확한 예상치를 얻는 것에는 도움이 되지 않는다.

Simon Funk씨에게 감사한다... (그는 Netflix prize에서 3등을 했고 그의 알고리즘은 이후에도 인용되고 발전돼왔다.)

The algorithm

 하 지 만... 이 sparse한 녀석의 optimization problem은 ...쉽지 않다. 위 수식의 sum이 최소가 되는 p_u와 q_i를 찾는 것이 힘들 뿐만 아니라

이를 구하기 위한 최선의 방법이랄 것도 딱히 없다.

그래도 우리는 '근사' 할 수 있다! 근사하는 방법은 많다.

여기선 SGD(Stochastic Gradient Descent)를 쓸 것이다.

 

Gradient Descent(GD)는 함수의 최솟값을 찾는 문제에선 매우 고전적인 방법이다. 딥러닝에 관심이 있는 사람은 뉴럴넷을 학습시키는 방법 중 하나로 back-propagation을 사용한다는 것을 알고 있을 것이다. Back-propagation은 GD문제에서 기울기(gradient)를 구하기 위해 쓰는 테크닉이며 이 예제에서도 사용할 것이다. 

SGD는 GD의 수많은 변형 중 하나다. 여기서는 SGD가 어떻게 동작하는 지에 대해서는 자세히 다루지 않을 것이다. 이에 대한 좋은 자료들은 웹상에 정말 많으니까 한번 찾아봐도 좋다. 그래도 기본 개념정도만 이야기하자면 다음과 같다.

만약 어떤 파라미터 ⍬에 대한 함수 f가 있다고 하자. 다음과 같은 모양을 가질 것이다.

SGD는 다음과 같은 절차를 반복하며 f(⍬)가 최소가 되는 ⍬값을 찾아낸다.

1. ⍬를 랜덤하게 초기화한다.

2. 원하는 만큼 반복한다:

         *모든 k 에 대해서 반복:

* af_k / a⍬ 를 계산 ( f_k를 ⍬로 미분한 값)

* 다음과 같이 ⍬를 갱신한다, ⍬ ← ⍬ - ⍺*(af_k / a⍬), ⍺는 learning_rate(임의의 작은 값)

우리 예제에서 ⍬는 p_u와 q_i에 해당한다. (p_*,q_*)로 표현할 것이며 이렇게 표현했을 때 우리가 minimize할 함수는 다음과 같다.

f_(ui)는 다음으로 정의된다.

따라서 SGD를 적용하기 위해서 우린 p_u와 q_i에 대한 f_(ui) 의 미분값을 구해야 한다.

* p_u에 대한 f_(ui)의 미분값은 다음과 같다.

* q_i에 대한 f_(ui)의 미분값은 다음과 같다.

뭔가 많아 보인다고 겁먹지 말자. 고등학생도 풀 수 있을 정도의 미분이다.

자 이제 SGD를 우리 예제에 적용해서 알고리즘을 다시 정의해보겠다.

1. p_u와 q_i를 랜덤하게 초기화시킨다.

2. 원하는 만큼 반복한다:

* 알려진 rating 점수 r_(ui)에 대해서 반복한다:

* f_(ui)의 p_u 그리고 q_i 에 대한 각각의 미분값 계산 (방금 했다)

* 다음과 같이 p_u와  q_i를 갱신, 

p_u ← p_u + ⍺ * q_i(r_(ui) - p_u*q*i)

q_i  ← q_i + ⍺*p_u(r_(ui) - p_u*q_i)

위에서 미분값 앞의 상수 2를 따로 곱하지 않고 그냥 learning rate  ⍺랑 통합시켰다.

자, 이 과정을 통해 p_u와 q_i가 동시에 업데이트 되고있다. 그런데 Funk씨의 오리지널 알고리즘은 조금 다르다. 동시에 하지 않고 하나하나 따로따로 갱신을 해줬다. 이러한 점에서 그의 알고리즘이 좀더 SVD틱하다고 할 수 있다. 이와 관련된 이야기들은 추천시스템에 관한 Aggarwal 씨의 책에 자세히 나와있다.

자 이제 됐다! p_u와 q_i를 구했다면 우린 비어있는 점수들을 다음과 같읕 식을 통해 예측해 볼 수 있다.

r_ui에 모자가 씌워있는 녀석(r hat이라고 부른다)은 예측값이라는 것을 뜻한다. 

Dimensionality reduction

 자, 파이썬 예제로 넘어가기 전에 우리가 생각해봐야 할 것이 하나 더 있다. "p_u와 q_i의 크기는 어떻게 돼야할까?"

우리가 아는 한가지 사실은 Dot product를 이용하기 위해선 p_u와 q_i의 사이즈가 똑같아야 한다는 것이다.

이 문제의 답을 찾기 위해 잠깐 예전에 보았던 PCA와 creepy guys의 예제로 돌아가보자.

으.. 여전히 creepy하다. 무튼 너희도 기억하겠지만 이 creepy guy들은 original face를 다시 reconstruct할 수 있다.

         

근데 우리가 original face들에 대한 좋은 근사치 정도만 원한다면 모든 creepy guy들을 동원할 필요는 없다.

사실 내가 너희에게 거짓말한게 있는데, 위 gif이미지들은 creepy guy 400명이 아닌 200명만 사용해 만든 것들이다.

part1으로 가서400명으로 만든 것들이랑 비교해보면 큰 차이가 없다는 걸 알 수 있을 것이다. 

덭붙이자면 다음 사진들은 첫 번째 original face를 reconstruct하는 과정이다. 왼쪽부터 오른쪽으로 갈수록 creepy guy 40명이 추가된다.

마지막 사진은 정말 굉장히 잘 복원됐다. 그런데 80 creepy guy만 사용한 것도 (세 번째 이미지) 누구인지 인식할 수 있을 정도로 잘 표현하고 있다.

이쯤에서 이러한 것들이 궁금한 분들이 있을 것이다. 왜 첫 번째 인물은 첫 번째 creepy guy랑 닮지 않았을까? 왜 creepy guy들은 original guy들보다 밝기 대비가 클까? 

왜냐하면 PCA는 모든 이미지의 평균을 추출하는 것이기 때문이다. 첫 번째 original image는 첫 번째 creepy guy + average guy이다.

만약 와닿지 않는다면... 우선 넘어가도 괜찮다.  추천하는데 있어서 이것이 중요한건 아니다.

아무튼 내가 하고자 하는 말은 이거다. 우린 잘 예측하기 위해 모든 creepy/typical guy를 쓸 필요는 없다. 

추천시스템에서도 마찬가지다. 우린 모든 typical moive와 typical user를 사용할 필요는 없다.

이 말은, 우리가 유저랑 아이템(무비)를  다음과 같은 식으로 표현한다고 할 때 (SVD 결과) 우린 적은 수의 영화와 유저들만을 가지고도 좋은 예측을 할 수 있다는 뜻이다. 우리 예제에선 p_u와 q_i의 사이즈를 10으로 제한할 것이다. 

즉 10개의 latent factor만 고려한다는 것이다.

이쯤되면 이렇게만 해도 정말 잘 되나? 의심을 하는 것도 이상하지 않다. 하지만 이러한 근사법도 좋은 결과를 낸다는 것을 보증한다.

자세한 사항은 여기 스탠포드 강의노트의 section 5를 참고하자. 저자는 SVD를 통해 missing entries를 채우는 방법을 제시하고 있다. 

자 이제 우린 다음 강의(마지막!)에서 matrix factorization 알고리즘을 구현할 준비가 됐다. 파이썬과 파이썬의 surprise 라이브러리를 이용할 것이다!

굉장히 심플하며 잘 동작한다.

관련 글

• Understanding matrix factorization for recommendation (part4)
• Understanding matrix factorization for recommendation (part2)
• Understanding matrix factorization for recommendation (part1)