협업 필터링(KNN, SGD, ALS)

정의

• 사용자의 구매 패턴이나 평점을 이용해 다른 사람들의 구매 패턴, 평점을 통해 추천하는 방법

• 추가적인 사용자의 개인정보나 아이템의 정보 없이도 추천할 수 있는 것이 장점

• 종류
  1. 최근접 이웃기반(KNN)
  2. 잠재요인기반(Latent Factor Collaborative Filtering)

이웃기반의 협업 필터링(Neighborhood Based Method)

• 정의
  • Neighborhood based Collaborative Filtering은 메모리 기반 알고리즘으로 협업 필터링을 위해 개발된 초기 알고리즘

• 알고리즘
  1. User-based collaborative filtering
     • 사용자의 구매 패턴(평점)과 유사한 사용자를 찾아서 추천 리스트 생성
  2. Item-based collaborative filtering
     • 특정 사용자가 준 점수 간의 유사한 상품을 찾아서 추천 리스트 생성

       

       출처: 공대인들이 직접쓰는 컴퓨터공부방

  • K-Nearest Neighbors
    • 가장 근접한 K개의 이웃을 통해 예측하는 방법

  

  https://www.researchgate.net/figure/Example-on-KNN-classifier_fig1_331424423

  • 데이터(Explicit Feedback Data)
    • 유저가 자신의 선호도를 직접 표현한 데이터 예시
    • KNN기반 협업필터링의 Target - ??로 표현된 평점 예측

    	Item1	Item2	Item3	Item4	Item5	Item6
    User1	7	6	7	4	5	4
    User2	6	7	??	4	3	4
    User3	??	3	3	1	1	??
    User4	1	2	2	3	3	4
    User5	1	??	1	2	3	3

User-based collaborative filtering

• User3과 유사한 사용자 찾기 예시

	Item1	Item2	Item3	Item4	Item5	Item6	평균	Cosine(i, User3)	Pearson(i, User3)
User1	7	6	7	4	5	4	5.5	0.956	0.894
User2	6	7	??	4	3	4	4.8	0.981	0.939
User3	??	3	3	1	1	??	2.0	1.0	1.0
User4	1	2	2	3	3	4	2.5	0.789	-1.0
User5	1	??	1	2	3	3	2.0	0.645	-0.817

• User기반(row) Similarity 예시 (User1, User3) - 있는 정보로만 유사도 계산!
  • $Cosine(x,y)=\frac{\sum{x_iy_i}}{\sqrt{\sum{x_i^2}}\cdot \sqrt{\sum{y_i^2}}} =\frac{18+21+4+5}{\sqrt{36+49+16+25}\sqrt{9+9+1+1}}=0.956$
  • $Pearson(x,y)=\frac{\sum{(x_i-\bar{x})(y_i-\bar{y})}}{\sum(x_i-\bar{x})^2 \cdot \sum(y_i-\bar{y})^2} = \frac{(6-5.5)(3-2.0) + (7-5.5)(3-2.0) + (4-5.5)(1-2.0) + (5-5.5)(1-2.0)}{\sqrt{\{(6-5.5)^2+ (7-5.5)^2 + (4-5.5)^2 + (5-5.5)^2\}}\sqrt{\{(3-2.0)^2+(3-2.0)^2+(1-2.0)^2+(1-2.0)^2\}}}=0.894$

• 예를 들어, User3과 유사한 사용자 2명을 찾으면 User1과 User2가 선택되고 유사도 기반 가중평균은 다음과 같음

  $\hat{r_{31}} = \frac{r_{11}\cdot Person_{13} + r_{21}\cdot Person_{23}}{Person_{13} + Pearson_{23}} = \frac{7 \cdot 0.894 + 6\cdot 0.939}{0.894 + 0.939} \approx 6.49$

  $\hat{r_{36}} = \frac{r_{16}\cdot Person_{13} + r_{26}\cdot Person_{23}}{Person_{13} + Pearson_{23}} = \frac{4 \cdot 0.894 + 4\cdot 0.939}{0.894 + 0.939} = 4$

→ 그런데, User의 경향(편향)이 존재

User1, User2는 평균적으로 높은 평점을, User3~User5는 평균적으로 낮은 평점을 주는 경향

따라서, 진짜 Item1에 대한 평가가 높은 건지, 아니면 User의 성향에 따른 편향이 생긴건지 의문이 들며 이를 제거해줘야 함

• Bias를 제거한 가중평균으로 User3의 평점을 예측하기
  • User1, User2와 User3, User4, User5는 평균 평점의 차이가 크게 존재하기 때문에 조정 필요
  • 고객의 경향성 등의 bias 제거를 위해 (User의 Item 평점 - 해당 User의 Item 평균 평점)의 유사도 가중 평균을 취함으로써 해결

    $\hat{r_{31}} = \bar{r_3} + \frac{(r_{11}-\bar{r_1})\cdot Person_{13} + (r_{21}-\bar{r_2}) \cdot Person_{23}}{Person_{13} + Pearson_{23}} = 2 + \frac{(7-5.5) \cdot 0.894 + (6-4.8)\cdot 0.939}{0.894 + 0.939} \approx 3.35$

    $\hat{r_{36}} = \bar{r_3} + \frac{(r_{16}-\bar{r_1})\cdot Person_{13} + (r_{26}-\bar{r_2}) \cdot Person_{23}}{Person_{13} + Pearson_{23}} = 2+\frac{(4-5.5) \cdot 0.894 + (4-4.8)\cdot 0.939}{0.894 + 0.939} \approx 0.86$

Item-based collaborative filtering

• User-based collaborative filtering과 반대로 Column(Item)끼리의 유사도를 계산해 활용하는 방식

• Item을 기준으로 User들이 비슷한 평점을 내린 유사한 Item을 찾는 것이 목적

	Item1	Item2	Item3	Item4	Item5	Item6	평균
User1	7	6	7	4	5	4	5.5
User2	6	7	??	4	3	4	4.8
User3	??	3	3	1	1	??	2.0
User4	1	2	2	3	3	4	2.5
User5	1	??	1	2	3	3	2.0
Cosine(Item1, j)	1	0.735	0.912	-0.848	-0.813	-0.990
Cosine(Item6, j)	-0.990	-0.622	-0.912	0.829	0.730	1

• Item1은 Item2, Item3과 유사하므로 User3의 Item1에 대한 평가를 Item2, Item3 기반으로 추정

  $\hat{r_{31}} = \frac{(3)\cdot 0.735 + (3)\cdot 0.912}{0.735+0.912} = 3$ 또는 $\hat{r_{31}} = 3.75 +\frac{(3-4.5)\cdot 0.735 + (3-3.25)\cdot 0.912}{0.735+0.912} \approx 2.94$

최근접 이웃 기반 방법의 장단점

• 장점
  • 간단하고 직관적인 접근 방식 때문에 구현 및 디버그가 쉬움
  • 특정 Item을 추천하는 이유를 정당화하기 쉽고 Item 기반 방법의 해석 가능성이 두드러짐
  • 추천 리스트에 새로운 Item과 User가 추가되어도 상대적으로 안정적

• 단점
  • User 기반 방법의 시간, 속도, 메모리가 많이 필요 (일반적으로 # of Users > # of Items)
  • 희소성(sparsity) 때문에 제한된 범위가 있음
    • John의 Top-K에만 관심이 있는 상황
    • John과 비슷한 이웃 중 아무도 해리포터를 평가하지 않으면, John의 해리포터에 대한 등급 예측을 제공할 수 없음

잠재요인기반의 협업 필터링(Latent Factor Collaborative Filtering)

• Neighborhood vs Latent Factor
  • 이웃 기반 - Item Space와 User Space 내 벡터 간 유사도를 통해 추천
  • 잠재요인 기반 - Item Space와 User Space 각각에 대한 Latent Space를 만들어 두 matrix의 곱을 통해 추천 진행

  

• 정의
  • Rating Matrix에서 빈 공간을 채우기 위해 사용자와 상품을 잘 표현하는 차원(Latent Factor)을 찾는 방법
  • 행렬 분해 알고리즘을 통해 User - Item 상호작용 행렬을 2개의 저 차원($n\times m$) 직사각형 행렬(User Matrix & Item Matrix)의 곱으로 분해하여 작동
  • 즉, Rating Matrix = User Latent matrix x Item Latent matrix

  

• Matrix Factorization의 원리
  • 사용자의 잠재 요인과 아이템의 잠재요인의 내적으로 평점 매트릭스를 계산

    $R \approx UV^T$

  • 이때, 사용하는 방법으로 Observed Only MF, Weighted MF, SVD 등이 있지만, 여기서는 SGD, ALS 방식을 다룸

1. SGD(Stochastic Gradient Descent)
   • 정의
     • 고유값 분해(Eigen Value Decomposition)와 같은 행렬을 대각화하는 방법
     • Rating Matrix $R$과 User letent matrix $U$와 Item latent matrix $V$내적의 차이를 최소화하는 $U,V$를 찾음
     • Gradient Descent를 통해 $U,V$를 업데이트

     $$Minimize~J=\frac{1}{2}||R-UV^T||_2\\subject~to:~No~constraints~on~U~and~V\\ S=\{(i,j):r_{ij}~is~observed\}$$

     • 위 식은 다음과 같이 구체화하여 포현할 수 있다.

     $$Minimize~J=\frac{1}{2}\sum_{(i,j)\in S}{e_{ij}^2}=\frac{1}{2}\sum_{(i,j)\in S}{(r_{ij}-\sum_{s=1}^{k}{u_{is}\cdot v_{js}})^2}\\ subject~to:~No~constraints~on~U~and~V$$

     • Gradient Descent에 의해 $J$를 $U,V$의 각 원소로 편미분한 값은 다음과 같다.

     $$\begin{align} \frac{\partial J}{\partial u_{iq}} &= \sum_{j:(i,j)\in S}{(r_{ij}-\sum_{s=1}^{k}{u_{is}\cdot v_{js}})\cdot (-v_{jq})}\\ &=\sum_{j:(i,j)\in S}{(e_{ij})(-v_{jq})}~~\forall i\in \{1,...,m\}, q\in \{1,...,k\} \end{align}$$

     $$\begin{align} \frac{\partial J}{\partial v_{jq}} &= \sum_{i:(i,j)\in S}{(r_{ij}-\sum_{s=1}^{k}{u_{is}\cdot v_{js}})\cdot (-u_{iq})}\\ &=\sum_{i:(i,j)\in S}{(e_{ij})(-u_{iq})}~~\forall j\in \{1,...,m\}, q\in \{1,...,k\} \end{align}$$

     • Weight가 폭발적으로 증가하는 Gradient Exploding 방지를 위해 규제항을 추가하면 다음과 같다.

     $$\begin{align} Minimize~J&=\frac{1}{2}\sum_{(i,j)\in S}{e_{ij}^2}+\frac{\lambda}{2}\sum_{i=1}^{m}\sum_{s=1}^{k}{u^2_{is}}+\frac{\lambda}{2}\sum_{j=1}^{n}\sum_{s=1}^{k}{v^2_{js}}\\ &=\frac{1}{2}\sum_{(i,j)\in S}{(r_{ij}-\sum_{s=1}^{k}{u_{is}\cdot v_{js}})^2}+\frac{\lambda}{2}\sum_{j=1}^{n}\sum_{s=1}^{k}{v^2_{js}}+\frac{\lambda}{2}\sum_{j=1}^{n}\sum_{s=1}^{k}{v^2_{js}} \end{align}$$

     • 이에 따라 규제항이 추가된 후 Gradient Descent에 의해 $J$를 $U,V$의 각 원소로 편미분한 값은 다음과 같다.

     $$\begin{align} \frac{\partial J}{\partial u_{iq}} &= \sum_{j:(i,j)\in S}{(r_{ij}-\sum_{s=1}^{k}{u_{is}\cdot v_{js}})\cdot (-v_{jq})}+\lambda u_{iq}\\ &=\sum_{j:(i,j)\in S}{(e_{ij})(-v_{jq})}+\lambda u_{iq},~~\forall j\in \{1,...,m\}, q\in \{1,...,k\} \end{align}$$

     $$\begin{align} \frac{\partial J}{\partial v_{jq}} &= \sum_{i:(i,j)\in S}{(r_{ij}-\sum_{s=1}^{k}{u_{is}\cdot v_{js}})\cdot (-u_{iq})}+\lambda v_{jq}\\ &=\sum_{i:(i,j)\in S}{(e_{ij})(-u_{iq})}+\lambda v_{jq},~~\forall j\in \{1,...,m\}, q\in \{1,...,k\} \end{align}$$

     • 이후 해당 편미분 값을 이용해 한 번의 에폭으로 각 Latent Matrix의 원소를 업데이트 한다. ($\alpha$: learning rate)

       $$u_{iq}\Leftarrow u_{iq}+\alpha(\sum_{j:(i,j)\in S}{e_{ij}\cdot v_{jq}}-\lambda u_{iq})\\ v_{jq}\Leftarrow v_{jq}+\alpha(\sum_{i:(i,j)\in S}{e_{ij}\cdot u_{iq}}-\lambda v_{jq})$$

     • 예시
       • Explicit Feedback 형태의 User 4명에 대한 3개의 Item 평점 Matrix가 다음과 같이 주어졌다고 하자.

       	Item1	Item2	Item3
       User1	??	3	2
       User2	5	1	2
       User3	4	2	1
       User4	2	??	4

       1. User Latent와 Item Latent의 값을 임의로 초기화 ($U$의 column size = $V$의 column size는 사용자 임의 지정 - ALS 논문에서는 20을 주로 사용)

          $$U_{(1)}=\begin{pmatrix} 0.5756 & 1.4534 \\ -0.199 & -1.218 \\ 2.7297 & 0.48 \\ -0.039 & -2.506 \end{pmatrix},~~ V^T_{(1)}=\begin{pmatrix} 0.3668 & -1.1078 & 1.4593 \\ -0.3392 & 0.8972 & 0.4528 \\ \end{pmatrix} \\ U_{(1)}V^T_{(1)}=\begin{pmatrix} -0.2819 & 0.6663 & 1.4981 \\ 0.3403 & -0.8728 & -0.8421 \\ 0.8384 & -2.5933 & 4.2008 \\ 0.8354 & -2.2043 & -1.1928 \end{pmatrix}$$

       2. Gradient Descent 진행 - $r_{12}(=3)$ 예시 ($\alpha=0.05,\lambda=0.01$)

          $$\frac{\partial J}{\partial u_{iq}} =\sum_{j:(i,j)\in S}{(e_{ij})(-v_{jq})}+\lambda u_{iq},~~\forall j\in \{1,...,m\}, q\in \{1,...,k\} \\ \frac{\partial J}{\partial v_{jq}} =\sum_{i:(i,j)\in S}{(e_{ij})(-u_{iq})}+\lambda v_{jq},~~\forall j\in \{1,...,m\}, q\in \{1,...,k\}$$

          $e_{12}=3-0.6663=2.3337$

          $\frac{\partial J}{\partial \bold{u}_1}|_{j=2}=-2.3337\cdot (-1.1078, 0.8972) +0.01\cdot (0.5756,1.4534)$

          $\frac{\partial J}{\partial \bold{v}_2}|_{i=1}=-2.3337\cdot (0.5756,1.4534) + 0.01\cdot (-1.1078, 0.8972)$

          $$\bold{u}_{1}\Leftarrow \bold{u}_{1}-0.05\frac{\partial J}{\partial \bold{u}_1}\\ \bold{v}_{2}\Leftarrow \bold{v}_{2}-0.05\frac{\partial J}{\partial \bold{v}_2}$$

          $$U_{(2)}=\begin{pmatrix} 0.446 & 1.5574 \\ -0.199 & -1.218 \\ 2.7297 & 0.48 \\ -0.039 & -2.506 \end{pmatrix},~~ V^T_{(2)}=\begin{pmatrix} 0.3668 & -1.0401 & 1.4593 \\ -0.3392 & 1.0663 & 0.4528 \\ \end{pmatrix} \\ U_{(2)}V^T_{(2)}=\begin{pmatrix} -0.3647 & 1.1967 & 1.3560 \\ 0.3403 & -0.8728 & -0.8421 \\ 0.8384 & -2.5933 & 4.2008 \\ 0.8354 & -2.2043 & -1.1928 \end{pmatrix}$$

          3. 모든 평점에 대해 반복 (Epoch:1)
             • ??를 제외한 모든 평점에 대해서 진행

   

   • 10-epoch 결과

     $$UV^T=\begin{pmatrix} 2.7458 & 2.4147 & 0.3873 \\ 4.2476 & 0.5806 & 2.8256 \\ 3.9181 & 2.3825 & 1.3030 \\ 2.4323 & -1.9994 & 3.2637 \end{pmatrix}$$

     • User1의 경우 Item1에 대한 예측 평점은 2.7458이므로 추천
     • User4의 경우 Item2에 대한 예측 평점은 -1.9994로 추천하지 않음
     • User Latent Matrix, Item Latent Matrix 자체를 분석 등으로 활용 가능
     • SGD의 장점(딥러닝의 장점)
       • 유연한 모델로, 다른 Loss Function을 사용 가능
       • 병렬처리가 가능함
     • SGD의 단점
       • 수렴까지 속도가 매우 느림

2. ALS(Alternating Least Squares) (참고1, 참고2)
   • 정의
     • SGD가 두 개의 행렬(User Latent Matrix, Item Latent matrix)을 동시에 최적화하는 방법이라면, ALS는 두 행렬 중 하나를 고정시키고 다른 하나의 행렬을 순차적으로 반복하면서 최적화하는 방법
     • 기존의 최적화 문제가 Convex 형태로 바뀌기 때문에 수렴된 행렬을 찾을 수 있음

• 알고리즘
  1. 초기 Item, User 행렬을 초기화
  2. Item 행렬을 고정하고 User 행렬을 최적화
  3. User 행렬을 고정하고 Item 행렬을 최적화
  4. 2번, 3번 과정을 반복

• 요약
  • Matrix Factorization은 아래와 같은 Cost Function을 최소화 하도록 두 행렬 $U$와 $V$를 찾는 것

    $$J = ||R -UV^T||_2 +\lambda(||U||_2 +||V||_2)$$

    여기서, 앞 부분은 원래의 평점행렬과 근사치 사이의 MSE, 뒷 부분은 규제항

    만약, 하나의 행렬을 고정시킨다면, 해당 최적화 문제는 기존 선형회귀 문제($||y-X\beta||_2$)와 동일하게 됨 ($\hat{\beta}=(X^TX)^{-1}X^Ty$)

    즉, cost functioon은 아래와 같이 두 개로 나눌 수 있다.

    $$J(u_i)=||R_i. - \bold{u}_i V^T||+\lambda||\bold{u}_i||_2, ~~~\forall \bold{u}_i\\ J(v_j)=||R_.j - U\bold{v}_j ||+\lambda||\bold{v}_j||_2, ~~~\forall \bold{v}_j$$

    여기서, $\bold{u}_i$와 $\bold{v}_j$에 해당하는 solution은 다음과 같다.

    $$\bold{u}_i=(V^TV+\lambda I)^{-1}V^T R_i.\\ \bold{v}_j=(U^TU+\lambda I)^{-1}U^T R_.j$$

• 예시 - 위와 동일한 예제를 ALS로
  • STEP1. User Latent와 Item Latent의 값을 임의로 초기화 ($U$의 column size = $V$의 column size는 사용자 임의 지정 - ALS 논문에서는 20을 주로 사용)

    $$U_{(1)}=\begin{pmatrix} 0.5756 & 1.4534 \\ -0.199 & -1.218 \\ 2.7297 & 0.48 \\ -0.039 & -2.506 \end{pmatrix},~~ V^T_{(1)}=\begin{pmatrix} 0.3668 & -1.1078 & 1.4593 \\ -0.3392 & 0.8972 & 0.4528 \\ \end{pmatrix} \\ U_{(1)}V^T_{(1)}=\begin{pmatrix} -0.2819 & 0.6663 & 1.4981 \\ 0.3403 & -0.8728 & -0.8421 \\ 0.8384 & -2.5933 & 4.2008 \\ 0.8354 & -2.2043 & -1.1928 \end{pmatrix}$$

  • STEP2. Item Matrix를 고정하고, User Matrix를 최적화
    • $\bold{u}_i=(V^TV+\lambda I)^{-1}V^T R_i$
    • 모든 row에 대해서 진행
      • $\bold{u}_1=(V^TV+\lambda I)^{-1}V^T R_1.=[0.3151, 3.2962]$
      • $\bold{u}_2=(V^TV+\lambda I)^{-1}V^T R_2.=[***, ***]$
      • $\bold{u}_3=(V^TV+\lambda I)^{-1}V^T R_3.=[***, ***]$
      • $\bold{u}_4=(V^TV+\lambda I)^{-1}V^T R_4.=[***, ***]$

  • STEP3. User Matrix를 고정하고 Item Matrix를 최적화
    • $\bold{v}_j=(U^TU+\lambda I)^{-1}U^T R_.j$
    • 모든 row에 대해서 진행
      • $\bold{v}_1=(U^TU+\lambda I)^{-1}U^T R_.1$
      • $\bold{v}_2=(U^TU+\lambda I)^{-1}U^T R_.2$

  • STEP2-STEP3 반복