추천 알고리즘 - Matrix Factorization

✅ 협업필터링의 두 가지 방식  

① Memory-based Approach

추천할 때 마다 Raw 데이터를 활용해서 계산하고 추천에 사용하는 방식

 

• 이전 포스팅에서 다룬 기본적인 협업필터링 알고리즘은 모두 메모리 기반 알고리즘이라고 볼 수 있다. 

• 계산량이 많기 때문에 현실의 빅데이터를 사용한 모델에는 적합하지 않음 

 

② Model-based Approach

raw데이터로 미리 학습한 모델을 만들어두고, 추천할 때는 미리 학습한 모델로 예측하는 방식

 

• 모델 기반 접근은 주기적으로 업데이트할 필요가 있다. 

• Weak Signal 을 파악할 수 있다. 여러 사용자들 사이에서 나타나는 약한 패턴도 파악할 수 있다.

여러 개의 데이터를 동시에 고려해서 공통된 피쳐를 추출할 수 있다. 이를 바탕으로 메모리 기반 모델보다 robust함. 

 

• 모델 학습에 많은 컴퓨팅 자원이 필요하지만 예측 시에는 적은 자원이 들어간다. 

• 모델 기반 알고리즘에는 다양한 방식이 존재하고 Matrix Factorization도 여기에 포함된다.  

 

모델 기반 알고리즘 예시

모델 기반 추천 알고리즘에는 위와 같이 다양한 방식이 존재한다. 

 

 

---

✅ Matrix Factorization 

• 기본적인 CF가 90년대부터 2000년대 초반에 사용된 알고리즘이라면, MF는 2000년 중반부대 활발하게 연구되기 시작한 추천 알고리즘이다. 

 

•User Latent 매트릭스인 P와 Item Latent 매트릭스인 Q의 역행렬을 곱해서 R^을 만들면, 원래 유저-아이템 평점 매트릭스의 근사값을 구할 수 있다는 아이디어에 기반한 방식이다. 

 

 

✔ MF의 장점 

•차원 축소(dimensionality reduction)이 가능하며 이를 통해서 컴퓨팅 자원 절약이 가능함 

•노이즈를 감소시켜서 과적합 가능성을 줄일 수 있다 

• 추천 이유에 대한 약간의 설명력을 부여할 수 있다. 

 예를 들어, 위와 같이 Latent Factor를 2개로 설정해서 차원 축소를 할 경우, 각 사용자들이 액션과 드라마 중에서 어느 쪽을 더 선호하는지를 수치적으로 나타낼 수 있다. 마찬가지로 각 영화에 대해서도 영화의 특성에 따라서 수치로 나타낼 수 있다. 물론 현업에서는 Latent Factor 를 100개 이상 사용하기 때문에 완벽한 설명을 하기에는 한계가 있다. 

 

위의 사용자 요인-아이템 요인 매트릭스를 곱하면 아래와 같은 매트릭스를 생성할 수 있다. 

R^ = P x Q(T)

이 매트릭스를 그림 상에서 나타내면, 어떤 사용자가 어떤 영화를 좋아할 지 보다 직관적으로 파악할 수 있다. 

Latent Factor = 2 일때, 각 영화와 유저들의 위치를 나타내면 위의 그림과 같다. 

 

 

✅ 경사하강법을 통한 업데이트 

P : 사용자 잠재 매트릭스 

Q : 아이템 잠재 매트릭스 

K : Latent Factor의 수 

r^_ij : 사용자 i 의 아이템 j 에대한 예측값 

e_ij : 예측 오차 

 

각 사용자의 아이템에 대한 행렬 계산 식은 위와 같이 나타낼 수 있다. 

 

특히 예측 에러의 제곱을 위와 같이 나타낼 때, 머신러닝의 경사하강법을 사용해서 업데이트 방향을 찾기 위해서 미분을 실시할 수 있다. 

 

p에 대해서 편미분

q에 대해서 편미분

e_ij^{2 를 p에 대해서 편미분 한 값은 위의 첫번째 식이고, q에 대해서 편미분한 값은 두번째 식이다.} 

 

업데이트 된 값 

업데이트된 값인 p′_ik 와 q′_ik 는 위와 같이 나타낼 수 있다. 일반적인 경사하강법의 업데이트 방식과 동일하다. 

여기서 α 는 학습률이고 임의로 정하는 값이다.  

 

위의 식은 한 명의 유저 i 와 아이템 j 에 대한 업데이트 식인데, 매트릭스에 존재하는 모든 i, j 에 대해서 오차가 e가 최소화 될 때 까지 업데이트를 반복한다. 이 과정을 1 iteration으로 본다. 

매트릭스 전체에 대한 업데이트 식 

 

 

Regularization

일반적인 머신러닝과 동일하게 규제 텀을 추가해서 과적합을 방지한다. regularization을 추가한 업데이트 식은 다음과 같다. 

 

P, Q의 최종 업데이트 룰

여기서 β 는 정규화의 크기를 조절하는 값으로 임의로 조정할 수 있다. 

 

 

 

✅ 평가 경향(bias) 고려 

 

CF에서 한 것 처럼 평가 경향을 고려할 수 있다. 이런 방식으로 계산하는 것이 보다 더 정확함 

 

bu_i : 사용자의 bias

bd_j : 아이템의 bias

b : 전체 평균(고정된 상수) 

시그마 부분 : 나머지 부분 

 

bias 값의 업데이트 룰을 미분을 통해서 구하면 아래와 같다. 

 

bias의 최종 업데이트 룰

 

 

 

---

✅  MF 최적화 

 

 α, β, K 파라미터에 대한 튜닝은 차례대로 진행한다. α의 최적값을 찾기 위해서 나머지 두 파라미터를 고정한 상태로 탐색을 한다. β, K도 동일한 방식으로 최적 파라미터를 찾는다. K 까지 완료한 후에 다시 α의 파라미터 수정을 시도한다. 이 과정을 최소 2회 이상 반복해야 최적 파라미터 조합을 찾을 수 있다. 

 

---

✅ SVD ++ (Singular Value Decomposition) 

추천시스템에서는 원래 엄격한 의미의 SVD가 사용되지 않는다. SVD는 결측치의 처리가 어렵기 때문. 

하지만 2008년 Netflix Prize 우승자가 MF를 기반으로 한 알고리즘을 SVD++라고 부르면서 현재까지 관행적으로 사용되고 있다. 

즉, 추천시스템에서는 SVD = MF라고 볼 수 있다. 

 

 

R(u) : 사용자 i가 평가한 모든 아이템

 y_j : j 아이템에 대한 추가적인 latent factor

 

위의 식은 MF 식을 의미한다. 여기에다가 사용자가 해당 리뷰를 평가했는지를 binary 값으로 표시하는 R(u) 부분을 추가한다. 

사용자가 특정 아이템을 몇 점으로 평가했는지도 중요하지만, 사용자가 어떤 아이템을 평가를 했는지 안 했는지 여부도 중요한 정보라고 보고 이를 반영한다. y매트릭스는 Q랑 동일한 차원을 가진다.

 

 R(u)를 추가한 식의 업데이트 rule을 계산하기 위해서 미분을 진행하면 아래와 같다. y 매트릭스가 추가되었기 때문에 이에 대한 계수인 람다가 추가된다. 

 

✅ SVD ++의 응용

  기본적인 SVD++는 하나의 implicit rating 요소를 고려하였다(장바구니 추가) . 하지만 아래 식과 같이 여러 개의 implicit rating 요소를 반영할 수도 있다. 

두 개의 implicit rating 정보를 반영

 위 식에서 N¹(u) 와 N²(u)는 두 개의 서로 다른 implicit rating을 의미한다. 대표적으로는 장바구니 담기 여부, 위시리스트 선정 여부, 아이템 페이지 클릭 여부 등이 있다. 이 경우에 대한 미분 규칙은 다른 방식으로 계산되어야 함. 

 

 

---

◈ Reference

•  "Python을 이용한 개인화 추천시스템", 임일, 청람