Collaborative Filtering - 2 (Model based CF, Matrix Factorization, Bayesian Personalized Ranking)

이웃 기반 CF 에서 벗어나 Model 기반 CF 에 들어선다. 

 

다루고자하는 내용은 다음과 같다. 

추천시스템에서 가장 중요한 '모델' Matrix Factorization을 이해하기 위해 간단 로드맵을 거친다. 

 

 

Sparsitiy: 결국에 Neighboorhood CF 는 데이터가 적으면 유사도 계산이 부정확하다는 큰 한계가 있다.  

또한 유저와 아이템 개수가 늘어나면 계산량이 늘어난다. 

 

Scalability: K-NN 으로 최소화 한다고 해도, 이전에 글에서 제기한 의문 같이 '유사도' 계산에서 bottle neck이 걸릴 수 있는 것이다. 

다만 역설적으로 정확한 예측을 하기위해서는 데이터가 많아야한다.

 

 

모든 분야에서 그렇듯이, 단순 유사성에서 벗어나 내재된 패턴을 이용하면 보다 정확한 결과를 얻곤 한다. 

딥러닝보다는 간단해도 주어진 모델을 이용해서 parameter를 학습한다. 

parameter는 데이터의 패턴을 담고, 최적화 과정에서 업데이트 된다. 

 

MBCF (model based CF) VS NBCF(neighborhood based CF)

 

 

이웃 기반 CF는 데이터를 통해 계산 된 형태를 메모리로 저장하여 Memory-based CF 라고 부른다. 

그러나, 현업에서는 Matrix Factorization 을 가장 많이 사용 

 

기존에 보이던 문제들을 단번에 완화한다. 

학습 모델을 추론만 하면 되니 서빙 속도가 빠르고, Sparse한 데이터에서도 (99.5% $\downarrow$) 상대적으로 좋은 성능을 보인다. 

 

Overfitting을 오히려 방지하고, 유사한 인물 혹은 '유사도 계산방식' 에 의지하지 않아도 된다.  

 

---

지금까지 다룬 데이터는 Explicit Feedback 이다. 

하지만, 실제로는 Explicit Feedback보다 Implicit Feedback이 훨씬 더 자동으로 많이 생성된다. 

해당 Implicit Feedback에서 Insight를 뽑아내는 것이 중요한 능력으로 보인다. 

또한, Implicit Feedback을 학습하도록 하는 모델링 기법도 아주 중요한 고려요인이다.

 

 

Explicit은 빈칸에 예측 rating으로 채워 넣는다. 

Implicit은 빈칸에 정확한 rating이 아닌 어떠한 선호도 값으로 채워넣을 수 있다. (O,X는 예시)

 

요새는 딥러닝의 등장으로 Latent Factor 보다는 Embedding 이라 더 자주 표현 

대부분 친숙한 내용이나 그 외에 저차원으로 나타낼 수 있다는 점이 흥미롭다. 

 

 

2차원으로 표현한 간단한 예시: 가까운 아이템들 추천 

실제로는 각 차원의 의미가 무엇인지 Explicit하게 알 수 없다. 

 

---

SVD 개념

https://www.youtube.com/watch?v=cq5qlYtnLoY 

 

SVD 에 대한 이해 

 

$A = U\Sigma V^T$ 

$A$ 라는 행렬은 다음과 같이 $U, V^T$로 분해 가능 

 

$A   : m\times n \, \mathbf{matrix}$

$U   : m\times m \,\, \mathbf{orthogonal}\, \mathbf{matrix}$ 

$\Sigma: m\times n \,\, \mathbf{diagonal}\, \mathbf{matrix}$ 

$V   : n\times n \,\, \mathbf{orthogonal}\, \mathbf{matrix} $ 

 

 

※Orthogonoal Matrix 

$UU^T = U^TU = I, \,\, U^{-1} = U^T$

 

※Diagonal Matrix 

대각 행렬 : 행렬은 선형 변환이다. 이 중, diagonal matrix 는 벡터의 크기를 조정한다. 

scaling factor를 0으로 하면 차원을 축소하는 것도 가능하다. 

 

SVD 의 기하학적 의미 

직교하는 벡터 집합(행렬)에 대하여, 선형 변환 후에 그 크기는 변하지만, 여전히 직교할 수 있게 만드는 그 직교 벡터 집합은 무엇이고, 변형 후의 결과는 무엇인가? 

다음과 같은 (초록색) 3개의 벡터를 diagonal matrix 를 곱해 (파란색) 2차원으로 축소한다고 가정하자. 이때 diagonal matrix 의 scaling factor 중 하나가 0이다. 그래서 벡터 하나가 없어진 것이다. 

계산과정에서 eigen value, eigen decomposition에 대한 배경 지식이 필요하다. 

해당 내용은 다음의 글을 살펴보자. 

 

 

간단하게 설명하자면 User Item의 정보를 Users, Items 그리고 그 사이에 User 와 item의 차원을 맞춰주며 중요도에 따라 weight를 곱해주는 행렬로 분해한다. 

 

그 후, 중요도에 따라 k의 factor만 선정하여 $\hat{R}$ 을 복원한다. 

해당 과정은 몇가지 문제를 가지고 있다. 

 

정리하자면 결측치를 채우는 과정이 문제를 발생시킨다. 이에 따라 Matrix Factorization이 등장했다. 

---

Matrix Factorization (here after, MF)

 

모델링을 위해 SVD 는 관측 되지 않은 entry를 모두 채워야 했으나, MF 는 채우지 않고 관측치만 활용한다. 

이에 따라 Rating Matrix 를 User, Item 두개의 matrix 로 분해한후, 실제 R 과 유사한 R hat을 추론한다. 

 

(여기서 생기는 궁금점 예측 평점이 왜 P 와 Q의 내적일까? $\rightarrow$ 유저와 특정 아이템의 곱이 평점이 되도록 유도하는 것이 당연. 이 과정을 통해 유저는 유저의 특징을 담고, 아이템은 아이템의 특징을 담을 수 있다.)

 

P와 Q안에 있는 각각의 유저 벡터와 아이템 벡터들은 모두 학습 가능한 파라미터이다. 

해당 학습 파라미터를 구하기 위하여 최적화 문제를 푼다. 

mean squared error 로 예측치와 GT 의 차이를 최소화한다. 

뒤 부분은 각각 파라미터가 overfitting되지 않도록 regularization term이다. 

(|| ||: norm, 2nd norm raised to the 2nd power)

이를 통해 $p_u, q_i$ 가 너무 많이 커지지 않도록, 즉 학습 데이터에 과적합되지 않도록 방지한다. 

 

 

---

※ 정규화 

 

---

학습 방법

MF 기법에 여러 테크닉 추가하여 성능 향상 시킨 논문

https://soobarkbar.tistory.com/105

Matrix Factorization Techniques for Recommender Systems

다음과 같은 페이지에 논문 리뷰도 있다. 

 

유저별로 편향이 다르다. (후한 점수, 낮은 점수)

이에 따라 전체 평균과 유저/아이템 별 bias 추가하여 예측 성능 향상 

 

추가 된 파라미터 $\mu, b_u, b_i$ 중 $\mu$는 학습 파라미터는 아니다. 학습 되는 편향 $b_u b_i$ 는 regularization term 에 추가되어 있다. 

 

SGD 사용하여 파라미터를 똑같이 업데이트 한다. bias 두 term 이 추가되었다. 

 

때로는 데이터의 신뢰도 및 특정 이유로 모델이 각각 다른 중요도를 반영하면 좋은 경우가 있다. 

데이터에 따라 $c_{u,i}$ 값을 다르게 줘서 모델 파라미터에 다르게 반영되도록 한다. 

 

MF 모델에 '시간' 을 반영하는 경우 

학습 파라미터가 시간을 반영하도록 $b_u, b_i, p_u^T q_i$ 파라미터에 t라는 변수를 추가하여 시간이 지날 수록 증가 혹은 감소하도록 선형 수식을 세울 수 있다. 

 

간단한 수식 모델링에서도 해당 내용들이 반영되었었지만, 학습 모델에 반영을 한 경우로 새로운 시도라고 할 수 있다. 

 

MF for implicit feedback

Implicit feedback 데이터셋을 위해서 MF 를 모델링하고 어떤 학습 기법을 사용해야하는지 제시한 논문 

상단의 MF 논문과 동일한 저자 

 

 

MF 학습시 가장 많이 사용하는 기법 

유저 아이템 차원이 늘어날 수록 학습 속도가 계속 느려진다. ALS 는 기존 방법보다 학습 속도가 빠르다. 

한번에 P, Q 를 동시에 업데이트 하지 않고, 번갈아가며 업데이트. 

한 쪽의 파라미터를 고정하고 나면 다른 하나에 대해서 least square 로 determistic 하게 풀어낼 수 있다. 

 

SGD와 비교하면 Sparse 한 경우 학습이 더 잘된다. (유저 수 대비 채워져 있는 정도가 더 적은 경우)

대용량 데이터를 병렬로 처리 가능 (대용량 데이터 병렬이 어떤 의미인지는 설명되지 않음)

따로 두 논문을 읽어봐야할 듯 해보인다. 

ALS 목적 함수는 다음과 같다. MF 와 동일한 수식이나 p, q 를 번갈아가며 상수로 고정하다보니 목적함수의 변수가 1개가 되어 determistic 하게 한번에 구할 수 있다. (어떠한 수식 한번으로 구할 수 있다. - 한번의 행렬 연산)

반복 업데이트 과정을 통해 $p_u, q_i$ 의 값을 구한다.

 

 

explicit feedback에서는 유저와 아이템 벡터의 내적값으로 바로 rating 을 예측했으나 

implicit feedback에서는 유저와 아이템 벡터의 내적값이 단지 preference 값을 예측하고, 실제 값과 예측 값의 차이를 전체 목적 함수의 어느정도 반영할지는 confidence를 통해서 조정된다. 

새로운 목적함수는 SGD , ALS 로 파라미터 업데이트를 통해 문제 해결 가능 

ALS 가 더 효율적

미분 관련 글

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ythansome&logNo=221195095825 

---

https://yeomko.tistory.com/4

 

해당 글에 ALS가 유도 되어있다. 

중간 중간 못 쫓아간 부분들을 포함하여 아래에 정리한다. 웬만한 분들은 가독성이 뛰어난 위 글을 읽는 것을 추천드린다. 

 

구현 과정을 살펴보자. 

위 글과의 통일성을 위해 상단의 $f_{u,i}$ 가 $p_{u,i}$ 로 대체, $p_{i}, q_{i}$ 는 $x_u, y_i$ 로 대체하여 식 전개한다. 

합성함수의 미분과 $L_{2} norm$ 미분 

 

$L_{2} norm$ 미분 

시그마는 분배법칙 적용 가능 

$x^T_u y_i$ 의 결과값은 scalar 이므로 $y_i^T x_u $  의 값과 동일 

 

$x_u$ 로 묶기 

$\Sigma y_i , \Sigma y^T_i$ 는 다음 같이 정리 가능 

$C$ 는 weight (confidence) 행렬이므로 diagonal matrix이다. 

 

우변도 동일하게 정리해준다. $Y$가 $Y^T$ 된 이유는 $p(u)$에 곱해주기 위해 차원을 맞추느라 그런 것으로 보인다. 

우리가 원하는 것은 $x_u$ 만 남기는 것이므로 양변에 역행렬을 곱해준다.

위와 동일한 방법으로 $y_i$ 도 업데이트 가능하다. 

 

간단한 편미분인데 이해가 오래걸렸다. 수학과 더 친해져야 할 것 같다.. 

---

Explicit, Implicit 방법론의 ALS 를 사용한 변형 

 

유도과정은 

https://yeomko.tistory.com/4

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

갈아먹는 저자님의 글을 확인하자. 

---

Implicit Feedback을 고려한 

Bayesian Personalized Ranking (Hereafter, BPR)

implicit feedback 데이터를 활용해 MF 를 학습할 수 있는 새로운 관점 제시 논문 

 

Personalized Ranking 이란 아이템 리스트를 순서대로 제공하는 경우 

다음과 같은 데이터를 사용한다.

학습 데이터(선호도 데이터) 생성 방법 

ex) $U_1$ 은 $i_2, i_3$을 $i_1, i_4$보다 선호함 

 

ex) $U_1$ 은 $i_2, i_3$을 $i_1, i_4$보다 선호함  

데이터는 $D_s$ 학습 데이터에 포함이 된다. 

(>: likelihood)

데이터에서 모델 파라미터를 학습시키는 방법은 두가지이다. 

MLE와 MAP 이다. 

MAP 는 말 그대로 사후 확률이 최대가 되는 파라미터 단 한개! 를 학습하는 것이다. 

그러다보니 분포 자체를 학습하는 MLE 보다 빠르다. 

사후 확률은 직접 구할 수 없다. 그러다 보니 가능도를 이용한다. 

personalized 정보를 모두 이용해서 likelihood 를 찾아야한다. 

확률은 0~1 사이기에 sigmoid function 사용

$\hat{x_{uij}}$ 는 $\hat{r}_{ui}$ - $\hat{r}_{uj}$ 즉, 아이템 i 에 대한 예측 rating - j에 대한 예측 rating 

이 값을 sigmoid 통과시키면 아이템 i를 j보다 좋아할 확률을 얻게 된다. 

 

주로 prior 를 구할 때, 사람들의 데이터가 정규분포를 따른다는 가정을 차용한다. 이는 오랜기간동안 다양한 실험을 통해 입증된 결과임으로 편하게 사용해도된다. 

공분산 행렬 $\sigma_{\theta} = \lambda_{theta} I$

$I$: 단위행렬 $\lambda$: 정규화 

 

 

$D_s$ 유저 선호데이터 ($i, j$) 관측된 아이템 i, 관측 안 된 아이템 j

계속해서 i,j 를 하나씩 샘플링해서 사용하니 비대칭 해소, 랜덤이니 반복 등장하지 않아 성능이 우수 

 

 

BPR 요약