[Recommender System] - MF(Matrix Factorization) 모델과 ALS(Alternating Least Squares)

추천 알고리즘 중에 가장 널리 사용되는 알고리즘은 단연 CF이다. 그중에서도 단일 알고리즘으로써 가장 성능이 높은 것은 단연 Model Based CF인 Matrix Factorization 계열의 알고리즘이다. (CF 기반 모델링에 관한 내용 참고) 이번 포스팅에서는 MF와 ALS에 대해 공부해보고, Implicit feedback 상황에서 ALS를 적용하는 방법을 살펴볼 것이다. 포스팅의 내용은 [추천 엔진을 구축하기 위한 기본서 - Suresh K.Gorakala]와 논문 그리고 이곳을 참고하였다.

---

1. Matrix Factorization

우선 MF 모델은 user-item 의 matrix에서 이미 rating이 부여되어 있는 상황을 가정한다. (당연히 sparse한 matrix를 가정한다)  MF의 목적은, 바꿔 말하면 Matrix Complement 이다. 아직 평가를 내리지 않은 user-item의 빈 공간을 Model-based Learning으로 채워넣는 것을 의미한다.

유저간, 혹은 아이템간 유사도를 이용하는 Memory-based 방법과 달리, MF는 행렬 인수 분해라는 수학적 방법으로 접근한다. 이는 행렬은 두개의 하위 행렬로 분해가 가능하며, 다시 곱해져서 원래 행렬과 동일한 크기의 단일 행렬이 될 수 있다는 성질에 기인한 것이다.

크기 U X M을 가지는 rating matrix R이 있다고 하자. 이 때 R은 각각의 크기가 U X K, M X K인 두 개의 행렬 P와 Q로 분해될 수 있다고 가정해본다. 그리고 다시 P X Q 행렬을 계산하면, 원래의 matrix R와 굉장히 유사하며 크기가 동일한 행렬이 생성된다. 중요한 것은, 행렬이 재생성 되면서 빈공간이 채워진다는 것이다. 이러한 행렬 인수 분해의 원칙은 비평가 항목을 채우기 위함이라는 것을 알 수 있다. 또한 한 가지 알 수 있는 것은, 분해된 행렬 P, Q는 각각 User-latent factor matrix, Item-latent factor matrix라는 각각의 내재적 의미를 나타내는 잠재 행렬도 나타낼 수 있다는 것이다. 이는 사람이 해석하는 잠재의미로도 해석은 가능하지만 기계가 해석하기 위한 행렬, 즉 블랙 박스 모델에 더 가깝다.

---

2. Objective Function

이제 MF를 학습하는 것은 latent feature들을 학습하는 것과 같다는 것을 알게 되었다. Latent 행렬을 각각 P, Q라고 했을 때 이제 MF 모델의 목적함수는 다음과 같다.

이 목적함수를 최소화 하는 것이 P와 Q를 학습하기 위한 것이다. 결국 rating의 y-y^ 제곱을 오차로 활용하는 것이기 때문에, 일반적인 regression에서의 최적화와 마찬가지로 정규화 파라미터를 추가해준다. 

---

3. ALS

교대 최소 제곱법, ALS는 위에서 정의한 목적함수를 최적화하는 기법이다. 일반적인 파라미터 최적화 기법으로 Gradient Descent를 사용하지만, 추천 알고리즘의 computation 환경인 분산처리 플랫폼에서는 GD보다 ALS가 더욱 효과적이라고 알려져 있다. 이는 ALS의 계산 방법 때문인데, GD에서처럼 Loss에 대한 편미분값을 update gradient로 활용하는 것이 아닌, P와 Q 벡터 중 하나를 고정해놓고 교대로 계산하기 때문이다. 이러한 방법은 분산처리 환경에서 더욱 빠른 연산이 가능해진다. 또한 ALS는 GD와 비교해볼때 sparse한 데이터에 robust한 모습을 보인다고 알려져 있다. Spark에서는 MF의 기본 학습법을 ALS에 기반하여 ML library로 제공하는데, Implicit feedback에 최적화된 학습까지 제공한다. (논문)

---

4. ALS with Implicit feedback

특정 도메인을 제외한 대부분의 e-commerce 시스템에서의 user-item 데이터 혹은 event 데이터는 implicit feedback의 형태이다. Implicit feedback의 형태로 수집된 데이터의 문제점은, 사용자의 호불호를 정확하게 파악할 수가 없다는 점이다. 예를 들어 영화추천에 사용되는 explicit data의 경우, 0~5 사이의 사용자의 호불호를 온전하게 계산에 사용할 수 있지만 e-commerce와 같은 조회정보, 구매정보 등과 같은 implicit data만 존재하는 경우에는 추가적인 논의가 필요하다고 할 수 있다. 상품을 구매했다고 반드시 그 상품에 호의적인 평가를 내렸다고 볼 수 없는 예를 생각해보면 알 수 있다. 앞서 설명했던 ALS를 Optimizer로 활용하는 목적함수는, 기본적으로 explicit feedback을 대상 데이터로 한 수식이다. 

그래서 Implicit feedback을 처리하는 접근방법이 제안되었다. 우선 confidence에 대한 개념을 정립하였다. Implicit feedback data에서 user의 item에 대한 점수를 나타내는 r_ui가 있다고 할 때, 이는 해당 아이템을 몇 번 조회하였는지, 혹은 how long stay 등의 측정으로 나타낼 수 있다고 하자. 이때의 선호도, preference 값을 p_ui 라고 정의하자. 먼저 선호와 비 선호를 나타내는 binary로 분류하는 방법을 생각할 수 있다.

하지만 만약 사용자 입장에서 존재의 여부도 몰랐지만 선호하는 아이템이 있다고 가정해본다면, action의 부재로 인해 p를 0으로 분류하는 것은 옳지 않을 것이다. 혹은 실수로 상품 페이지를 들어왔다가, 브라우저 오류 때문에 몇 번을 새로고침 해서 선호도가 올라간 것 처럼 수치가 상승하는 경우도 있을 것이다. 결국, preference 값을 항상 신뢰할 수 없기 때문에 이를 위한 confidence level을 제안하게 된다. 그리고 Implicit feedback을 대상으로 하는 MF의 목적함수는 다음과 같이 정리할 수 있게 된다.

개념은 그렇지만, 결국 생각해보면 explicit feedback의 경우는 명확하고 한정된 rating을 매기는 것이다. 반면, implicit feedback은 논리적 결함이 있을 수는 있지만 rating이 높아질수록 높은 확률로 item을 prefer한다고 생각할 수 있다. 결국 신뢰도 c_ui는 increasing function의 역할을 하는 것이 된다. 다만 이 목적함수에서의 의문점은, training 과정에서의 prediction 값은 real value인 반면, 원래의 real value는 p_ui로 바뀌어 binary 하다는 점이다. 이 경우 실제의 r 값이 크다면 아무리 예측이 정확해져도 cost는 상승하는 것 같은데 말이다. 그래서 (p_ui)^ 에 대한 추가적인 조치를 논문에서는 자세히 언급하지 않았지만, spark로 코딩하여 결과를 내보면 prediction값이 전체적으로 down scale 되어있는 것을 볼 수 있었다. 

논문에서 언급하는 또 한가지는, 목적함수가 이런 방식으로 구성된다면 목적함수에서 사용되는 p_ui, c_ui 등은 학습 전에 결정된 상수이기 때문에 ALS를 적용하기에 좋은 구조가 된다는 것이다. 어찌되었든 메인 아이디어와 주장은 다음과 같다.

1. Raw observation r_ui을 p_ui, c_ui로 활용하여 Implicit feedback 데이터에 적합한 수식으로 목적함수를 변경한다.

2. ALS를 적용하여 학습하면 Linear Time에 학습이 완료된다.

---

5. Spark ML로 구현하기

Spark ML을 사용하여 Scala에서 매우 간단하게 구현이 가능하다. Document에 있는 거의 그대로 사용하면 된다. 다만, 하이퍼 파라미터를 제대로 설정하기 위해서는 본 포스팅에서 언급된 논문을 찾아서 읽어보는 것을 반드시 추천한다.

github 링크