모델 기반 CF와 SVD를 응용한 MF(Matrix Factorization)

 

 

Model-based Collaborative Filtering(MBCF)

NBCF(Neighborhood-based CF)의 한계

Sparsity(희소성) 문제

데이터가 충분하지 않으면 추천 성능이 떨어져서 유사도 계산이 부정확한 문제가 있다.

데이터가 부족하거나 또는 아예 없는 유저, 아이템의 경우는 추천이 불가능하다.

 

Scalability(확장성) 문제

유저와 아이템이 늘어날수록 유사도 계산이 늘어난다.

유저, 아이템이 많아야 정확한 예측을 하지만, 반대로 시간이 오래 걸린다.

 

 

MBCF(Model-based CF)의 특징

항목 간 유사성을 단순 비교하는 것에서 벗어나 데이터에 내재한 패턴을 이용해 추천하는 CF 기법이다.

파라미터를 이용하는 Parametric Machine Learning을 사용한다.

데이터 정보가 파라미터의 형태로 모델에 압축되어 저장된다.

데이터의 패턴을 나타내는 모델의 파라미터를 최적화하여 업데이트한다.

데이터에 숨겨진 유저-아이템 관계의 잠재적인 특성과 패턴을 찾아서 모델의 파라미터에 반영하는 것이다.

 

NBCF와의 차이

NBCF는 유저, 아이템 벡터를 데이터를 통해 계산된 형태로 저장하므로 Memory-Based CF로 불리기도 한다.

그러나 MBCF(Model-Based CF)는 유저, 아이템 벡터를 모두 학습을 통해 변하는 파라미터로 저장한다.

현업에서는 Matrix Factorization 기법을 가장 많이 사용한다.

 

 

MBCF의 장점

모델의 학습과 서빙

유저-아이템 데이터는 학습에만 사용되고 학습된 모델은 압축된 파라미터의 형태로 저장된다.

이미 학습된 모델로 추천하기 때문에 서빙 속도가 빠르다는 장점이 있다.

 

Sparsity와 Scalability 문제 개선

NBCF에 비해 sparse한 데이터에서도 좋은 성능을 보인다.

사용자, 아이템의 개수가 많이 늘어나도 좋은 추천 성능을 보인다.

 

Overfitting 방지

NBCF의 경우 특정 주변 이웃에 의해 크게 영향을 받을 수 있지만, MBCF는 전체 데이터의 패턴을 학습하므로 상대적으로 좋은 일반화 성능을 보인다.

 

Limited Coverage 극복

NBCF의 경우 공통의 유저와 아이템을 많이 공유해야만 유사도 값이 정확해지는 단점이 있다.

MBCF는 전체 데이터의 패턴을 학습하므로 NBCF에서 유사도 값이 정확하지 않아 이웃의 효과를 보기 어려운 문제가 발생하지 않는다.

 

 

Latent Factor Model

 

Latent Factor = Embedding

 

유저와 아이템 관계를 잠재적 요인으로 표현할 수 있다고 보는 모델이며, 다양하고 복잡한 유저와 아이템의 특성을 몇 개의 벡터로 compact하게 표현한다.

유저-아이템 행렬을 저차원의 행렬로 분해하는 방식으로 가공하며, 각 차원의 의미는 모델 학습을 통해 생성되며 표면적으로는 알 수 없다.

같은 벡터 공간에서 유저와 아이템 벡터가 놓일 경우 유저와 아이템의 유사한 정도를 확인할 수 있다.

유저 벡터와 아이템 벡터가 같은 벡터 공간에서 유사하게 놓인다면 해당 유저에게 해당 아이템이 추천될 확률이 높음을 유추할 수 있다.

 

 

Singular Value Decomposition(SVD)

 

Rating Matrix $R$에 대해 유저와 아이템의 잠재 요인을 포함할 수 있는 행렬로 분해한다.

• 유저 잠재 요인 행렬
• 잠재 요인 대각행렬
• 아이템 잠재 요인 행렬

선형대수학에서 차원 축소 기법 중 하나로 분류되며, 주성분분석(PCA)도 차원 축소 기법 중 하나이다.

 

 

SVD의 원리

Full SVD

[출처] https://commons.wikimedia.org/wiki/File:Singular_value_decomposition_visualisation.svg, Cmglee

 

$R = U \mathit{\Sigma} V^T$

 

• $U$: 유저와 Latent Factor의 관계
  • $m \times m$ 직교행렬(orthogonal matrix)
  • $RR^T$를 고유값 분해해서 얻은 직교행렬
  • $RR^T$의 eigenvector
  • $U$의 열벡터는 $R$의 left singular vector
• $V$: 아이템과 Latent Factor의 관계
  • $n \times n$ 직교행렬(orthogonal matrix)
  • $R^TR$를 고유값 분해해서 얻은 직교행렬
  • $R^TR$의 eigenvector
  • $V$의 열벡터는 $R$의 right singular vector
• $\mathit{\Sigma}$: Latent Factor의 중요도를 나타낸다.
  • $RR^T$를 고유값 분해해서 얻은 직사각 대각행렬(diagonal matrix)
  • 대각 원소들은 $R$의 singular value(특이치)

 

 

Truncated SVD

[출처] https://commons.wikimedia.org/wiki/File:Reduced_Singular_Value_Decompositions.svg, Mercurysheet

 

$R \approx \widehat{U} \mathit{\Sigma}_k \widehat{V^T} = \widehat{R}$

대표적으로 사용될 $k$개의 특이치만 사용하며, 몇 개의 특이치만을 가지고도 유용한 정보를 유지한다.

유저와 아이템의 상호작용 행렬을 세 개의 행렬로 분해해서 다시 곱할 때 최대한 원래 행렬로 복원될 수 있도록 하는 것이다.

이때 행렬을 분해하는 과정에서 분해된 행렬에는 가장 중요한 정보로 요약된다.

각각의 k개의 Latent Factor의 의미는 유추할 수 있을 뿐 정확히 무엇을 의미하는지는 알 수 없다.

 

 

SVD의 한계

SVD에서는 행렬 값에서 null을 허용하지 않는데, 이는 추천 시스템에서 새로운 아이템에 관해 추천을 해야하는 것에서 어려움이 있다.

Sparsity가 높은 데이터의 경우 결측치가 매우 많은데, 실제 데이터는 대부분 Sparse Matrix이다.

그래서 결측된 entry를 모두 채우는 imputation을 통해 dense matrix를 만들어서 SVD를 수행하는 방법이 있다.

그러나 Imputation은 데이터 양을 상당히 증가시키므로 computation 비용이 높아진다.

즉, 정확하지 않은 Imputation은 데이터를 왜곡시키고 예측 성능을 떨어뜨릴 수 있다.

또한 행렬의 entry가 매우 적을 때 SVD를 적용하면 과적합되기 쉽다.

 

 

Matrix Factorization(MF)

MF의 원리와 특징

[출처] https://commons.wikimedia.org/wiki/File:Matrix_factorization.png, Xianteng

 

유저-아이템 행렬을 저차원의 유저와 아이템의 latent factor 행렬의 곱으로 분해하는 방법이다.

SVD의 개념과 유사하지만, MF는 관측된 선호도(평점)만 모델링에 활용하고 관측되지 않은 선호도를 예측하는 일반적인 모델을 만든다.

Rating Matrix를 $P$와 $Q$로 분해하여 $R$과 최대한 유사하게 $\widehat{R}$을 추론한다.

 

$$ R \approx P \times Q^{T} = \widehat{R} $$

 

$R$과 $\widehat{R}$이 최대한 유사하도록 유저 행렬인 $P$와 아이템 행렬인 $Q$를 학습하는 것이다.

 

$$ P \rightarrow |U| \times k\\ Q \rightarrow |I| \times k $$

 

실제 rating과 예측 rating 사이의 차이를 줄이는 Objective Function을 정의하고 $P$와 $Q$ 등 파라미터의 최적화 문제를 푸는 것이다.

실제 rating: $r_{u, i}$

예측 rating: $\widehat{r_{u, i}} = p_{u}^{T} q_{i} $

 

$$ \underset{P, Q}{\min} \underset{\text{observed} r_{u,i}}{\sum} (r_{u,i} - p_{u}^{T} q_{i})^2 $$

 

 

MF의 Objective Function

 

$$ \underset{P, Q}{\min} \underset{\text{observed} r_{u,i}}{\sum} (r_{u,i} - p_{u}^{T} q_{i})^2 + \lambda(\|p_u\|_2^2 + \|q_i\|_2^2) $$

 

$r_{u, i}$: 학습 데이터에 있는 유저 u의 아이템 i에 대한 실제 rating

$p_i$: 유저의 latent vector

$q_i$: 아이템의 latent vector

$p_i$와 $q_i$ 모두 최적화 문제를 통해 업데이트되는 파라미터이다.

$\lambda$(상수)배 된 penalty term은 L2-정규화(regularization)를 의미한다.

행렬 분해를 위해 결측 entry를 채워 넣는 SVD와는 다르게 실제 관측된 데이터만을 사용하여 모델을 학습한다.

 

 

MF 손실함수에서의 정규화

Weight(가중치)를 손실함수에 넣어주면 weight가 너무 커지지 않도록 제한을 해서 overfitting을 방지한다.

Regularization Term에 곱해지는 $\lambda$의 크기에 따라 영향도가 달라진다.

$\lambda$가 너무 크면 weight가 제대로 변하지 않아서 underfitting이 일어난다.

Weight의 절댓값의 합을 사용하면 L1 정규화, 제곱의 합을 사용하면 L2 정규화이다.

 

 

MF 모델에서의 SGD(Stochastic Gradient Descent)

 

Loss: $L = \sum (r_{u,i} - p_{u}^{T} q_{i})^2 + \lambda(\|p_u\|_2^2 + \|q_i\|_2^2)$

Error: $e_{u, i} = r_{u,i} - p_{u}^{T} q_{i}$

Gradient: $\frac{\partial L}{\partial p_{u}} = \frac{\partial (r_{u,i} - p_{u}^{T} q_{i})^2}{\partial p_u} + \frac{\partial \lambda \|p_u\|_2^2}{\partial p_u} = -2(r_{u,i} - p_{u}^{T} q_{i})q_i + 2\lambda p_u = -2(e_{u,i}q_i - \lambda p_u)$

Gradient의 반대방향으로 $p_u$, $q_i$를 업데이트한다.

 

$$ \begin{aligned} p_u &\leftarrow p_u + \eta \cdot (e_{u,i}q_i - \lambda p_u)\\ q_u &\leftarrow q_u + \eta \cdot (e_{u,i}p_u - \lambda q_i) \end{aligned} $$

 

※ Day 34(22.03.10)의 오피스 아워에서 나온 설명에 의하면, Funk-SVD에 의거하여 $p_u$, $q_i$를 꼭 동시에 업데이트하지 않고 순차적으로 업데이트하는 방식으로 구현해도 된다고 한다. 어차피 딥러닝을 통해 파라미터를 업데이트하는 것은 근사치를 구해 나가면 되므로 엄밀하게 파라미터를 업데이트 하는 것은 어려운 일이다.

 

 

MF의 성능 향상을 위한 테크닉

Adding Biases

어떤 유저는 모든 아이템에 대하여 평점을 짜게 줄 수도 있고, 아이템도 편향이 생길 수 있다.

전체 평균($\mu$), 유저와 아이템 각각의 bias($b_u, b_i$)를 추가하여 예측 성능을 높일 수 있다.

$$ \underset{P, Q}{\min} \underset{\text{observed} r_{u,i}}{\sum} (r_{u,i} - \mu - b_u - b_i - p_{u}^{T} q_{i})^2 + \lambda(\|p_u\|_2^2 + \|q_i\|_2^2 + b_u^2 + b_i^2) $$

error: $e_{u, i} = r_{u,i} - \mu - b_u - b_i - p_{u}^{T} q_{i}$

$$ \begin{aligned} b_u &\leftarrow b_u + \eta \cdot (e_{u,i} - \lambda b_u)\\ b_i &\leftarrow b_i + \eta \cdot (e_{u,i} - \lambda b_i)\\ p_u &\leftarrow p_u + \eta \cdot (e_{u,i}q_i - \lambda p_u)\\ q_u &\leftarrow q_u + \eta \cdot (e_{u,i}p_u - \lambda q_i) \end{aligned} $$

 

Adding Confidence Level

모든 평점이 동일한 신뢰도를 갖지 않으므로 $r_{u,i}$에 대한 신뢰도를 의미하는 $c_{u, i}$를 추가한다.

때로는 특정 데이터를 모델이 더 많이 반영하기를 원하고, 또 다른 데이터는 모델이 적게 반영하기를 원하는 아이디어에서 출발한 것이다.

대규모 광고 집행처럼 특정 아이템이 많이 노출되어 클릭되는 경우, 유저의 아이템에 대한 평점이 정확하지 않은 경우(Implicit Feedback) 등에서 신뢰도를 사용할 수 있다.

$$ \underset{P, Q}{\min} \underset{\text{observed} r_{u,i}}{\sum} c_{u,i}(r_{u,i} - \mu - b_u - b_i - p_{u}^{T} q_{i})^2 + \lambda(\|p_u\|_2^2 + \|q_i\|_2^2 + b_u^2 + b_i^2) $$

 

 

Adding Temporal Dynamics

시간에 따라 변하는 유저, 아이템의 특성을 반영하고 싶은 아이디어에서 출발한 것이다.

예를 들어, 어떤 아이템은 시간이 지남에 따라 인기도가 떨어지기도 하고, 유저가 시간이 흐르면서 평점을 내리는 기준이 엄격해질 수 있다.

 

학습 파라미터가 시간을 반영하도록 모델을 설계한다.

$$ \widehat{r_{u, i}} = \mu + b_u(t) + b_i(t) + p_{u}^{T} q_{i} $$

예) $b_u(t) = b_u + \alpha_u \cdot sign(t - t_u) \cdot |t - t_u|^{\beta}$

 

 

 

MF for Implicit Feedback

Alternative Least Square(ALS)

 

유저와 아이템 데이터 차원이 계속 늘어나는 단점을 보완하는 아이디어에서 나온 것이다.

유저 행렬 $P$와 아이템 행렬 $Q$를 번갈아가면서 업데이트하는 것이다.

두 행렬 중 하나를 상수로 놓고 나머지 행렬을 업데이트 하는 방식이다.

$p_u$, $q_i$ 가운데 하나를 상수로 고정하고 다른 하나로 least-square method를 사용하는 것이며, 이때 목적함수가 quadratic form이 되어 convex하므로 least square 문제 해결이 가능하다. (Convex하다는 것은 결국 극값이 존재함을 의미하므로 극솟값을 찾을 수 있음을 알 수 있다.)

대용량 데이터를 병렬 처리하여 ALS는 SGD보다 더 빠른 속도로 학습하게 되며, sparse한 데이터에 대해 SGD보다 더 robust하게 학습할 수 있다.

 

 

ALS의 objective function

$$ \underset{P, Q}{\min} \underset{\text{observed} r_{u,i}}{\sum} (r_{u,i} - p_{u}^{T} q_{i})^2 + \lambda(\|p_u\|_2^2 + \|q_i\|_2^2) $$

$$ \begin{aligned} p_u &= (Q^TQ + \lambda I)^{-1} Q^T r_u\\ q_i &=(P^TP + \lambda I)^{-1} P^T r_i \end{aligned} $$

 

각 파라미터 $p_u$, $q_i$로 objective function을 미분했을 때의 값이 0과 같다는 등식을 이용해서 각 파라미터 $p_u$, $q_i$에 관해 식을 정리하면 위와 같은 식을 얻을 수 있다.

 

 

Preference

유저 u가 아이템 i를 선호하는지 여부를 binary로 표현한다.

MF에서의 $p_u$, $q_i$의 내적은 preference $f_{u,i}$를 예측하게 된다.

$$ f_{u,i}= \begin{cases} 1, & r_{u,i} > 0 \\ 0, & r_{u,i} = 0 \end{cases} $$

 

 

Confidence

유저 u가 아이템 i를 선호하는 정도를 나타내는 increasing function이다.

$\alpha$는 positive feedback과 negative feedback 간의 상대적인 중요도를 조정하는 하이퍼 파리미터이다.

 

$$ c_{u,i} = 1 + \alpha \cdot r_{u,i} $$

 

 

Implicit Feedback을 고려한 목적 함수

 

$$ \underset{P, Q}{\min} \underset{\text{observed} r_{u,i}}{\sum} c_{u,i}(f_{u,i} - p_{u}^{T} q_{i})^2 + \lambda(\|p_u\|_2^2 + \|q_i\|_2^2) $$

 

$p_u$, $q_i$의 내적은 preference $f_{u,i}$를 예측하게 된다.

예측값과 실제값의 차이를 전체 목적함수에 얼마나 반영할지를 confidence $c_{u, i}$를 통해 조정할 수 있다.

rating($r_{u,i}$)이 높을 경우 confidence $c_{u,i}$가 높기 때문에 해당 데이터에 관해 예측이 좀 더 정확해지도록 모델이 학습된다.

rating($r_{u,i}$)이 낮을 경우에는 confidence $c_{u,i}$가 낮기 때문에 해당 데이터에 관해 예측이 좀 덜 정확해지도록 모델이 학습된다.

 

$$ \begin{aligned} p_u &= (Q^T C^u Q + \lambda I)^{-1} Q^T C^u f_u\\ q_i &=(P^T C^i P + \lambda I)^{-1} P^T C^i f_i \end{aligned} $$

 

 

다음은 MF의 여러 테크닉을 사용했을 때 각 테크닉마다 파라미터 수에 따른 RMSE의 결과를 그래프로 나타낸 것이다.

어떠한 테크닉도 사용하지 않은 것보다는 bias 추가, implicit feedback 고려, 시간에 따른 학습 파라미터 값 반영 등 테크닉을 사용하는 것이 성느잉 좋은 것을 확인할 수 있으며, 마찬가지로 대개 파라미터 수가 증가할수록 성능이 좋아짐을 확인할 수 있다.

 

[출처] https://datajobs.com/data-science-repo/Recommender-Systems-%5bNetflix%5d.pdf, Matrix Factorization Techniques for Recommender Systems

 

2022년 3월 7일(월)부터 11일(금)까지 네이버 부스트캠프(boostcamp) AI Tech 강의를 들으면서 개인적으로 중요하다고 생각되거나 짚고 넘어가야 할 핵심 내용들만 간단하게 메모한 내용입니다. 틀리거나 설명이 부족한 내용이 있을 수 있으며, 이는 학습을 진행하면서 꾸준히 내용을 수정하거나 추가해 나갈 예정입니다.