[머신러닝] Lecture 16 Recommender Systems

https://www.youtube.com/watch?v=GIcuSNAAa4g&list=PLoR5VjrKytrCv-Vxnhp5UyS1UjZsXP0Kj&index=16

우선 reocommender system이 무엇인지 살펴보자. 아래 그림을 보자.
유저들은 관람한 영화에 대한 0~5점의 평점을 매겼고, 그 데이터는 아래와 같다.
총 유저 수는 4이고, 영화 종류 수는 5이다.
그리고 각 유저의 평가한 영화 평점을 기반으로, 각 유저가 아직 보지 않은 영화에 대한 평점을 예측할 수 있다.

• 예를 들어, Alice는 Love at last와 Romnace forever에 높은 평점을 주었지만, Nonstop car caseses와 Swords vs. karate에는 낮은 평점을 주었다. 그리고 다른 유저들의 영화 평점을 살펴 보니, Love at last와 Romance forever 그리고 Cute puppies of love에 높은 평점을 준 유저들은 Nonstop car chases와 Swords vs. karate에는 낮은 평점을 준다는 것을 알 수가 있다.
• 따라서 이러한 유저들의 평점을 가지고 모델을 학습하여, 어떤 유저가 아직 보지않은 영화에 대한 유저의 평점을 예측할 수 있다.
  

그리고 이러한 추천 시스템을 "Content-based recommender system"이라고 한다.
먼저 notation을 정리해보자.

• $n_u$ : # of users. $=4$
• $n_m$ : # of movies. $=5$
• $x^{(i)}$ : movie $i$'s features. $x^{(i)}=\begin{bmatrix}x^{(i)}_0 \\ x^{(i)}_1 \\ x^{(i)}_2\end{bmatrix}$ ($x^{(i)}_0=1$)
• $\theta^{(j)}$ user $j$'s parameter vectors. $\theta^{(j)}=\begin{bmatrix}\theta^{(j)}_0 \\ \theta^{(j)}_1 \\ \theta^{(j)}_2\end{bmatrix}$
• 따라서 아래에서 Alice의 Cute puppies of love 영화에 대한 평점을 예측하려면 아래와 같이 계산할 수 있다.
  • Cute puppies of love의 feature vector : $x^{(3)}=\begin{bmatrix}1 \\ 0.99 \\ 0\end{bmatrix}$
  • Alice의 영화에 대한 parameter vector : $\theta^{(1)}=\begin{bmatrix}0 \\ 5 \\ 0\end{bmatrix}$
  • $(\theta^{(1)})^Tx^{(3)}=0.99 \times 5 = 4.95$
  • 따라서 Alice의 Cute puppies of love에 대한 평점은 4.95점일 것이다.
    

그렇다면 이를 공식으로 작성해보자.

• $r(i,j)=1$ : 유저 $j$가 영화 $i$에 평을 남긴 경우. (평이 없을 경우 $r(i,j)=0$)
• $y^{(i,j)}$ : 유저 $j$가 영화 $i$에 매긴 평점.
• $\theta^{(j)}$ : 유저 $j$의 prameter vector. $\in \mathbb{R}^n$
• $x^{(i)}$ : 영화 $i$의 feature vector. $\in \mathbb{R}^n$
• $(\theta^{(j)})^T(x^{(i)})$ : 유저 $j$의 영화 $i$에 대한 예측 평점.
• $m^{(j)}$ : 유저 $j$가 평을 남긴 영화 수.
• 위 notation을 가지고 linear regression의 optimzie function을 다음과 같이 작성할 수 있다.
  • $\underset{\theta^{(j)}}{min}\frac{1}{2m^{(j)}}\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2m^{(j)}}\sum_{k=1}^n (\theta_k^{(j)})^2$
  • 다만 k-means clustering처럼 $\frac{1}{2m^{(j)}}$에서 $m^{(j)}$는 생략해준다. 따라서 유저 $j$의 파라미터 $\theta^{(j)}$를 학습하기 위한 optimize function은 다음과 같이 나온다.
  • $\underset{\theta^{(j)}}{min}\frac{1}{2}\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{k=1}^n (\theta_k^{(j)})^2$
    

그리고 유저 $j$뿐만 아니라 다른 유저의 파라미터 $\theta^{(1)},\theta^{(2)},...,\theta^{(n_u)}$를 모두 학습하기 위한 optimization function은 아래와 같다.

• $\underset{\theta^{(1)},...,\theta^{(n_u)}}{min}\frac{1}{2}\sum_{j=1}^{n_u} \sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^n (\theta_k^{(j)})^2$
  

그리고 위 cost function을 최소화하기 위해서 linear regression처럼 gradient descent를 적용하면 된다.

• $\theta_k^{j} := \theta_k^{j} - \alpha \sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})x_k^{(i)}$ (for $k=0$)
• $\theta_k^{j} := \theta_k^{j} - \alpha (\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})x_k^{(i)} + \lambda\theta_k^{(j)})$ (for $k=1$)
  
  이처럼 각 영화의 feature 정보(romatinc, action)가 주어지고, 이를 기반으로 평점을 예측하고 추천하는 것을 content-based recommender system이라고 한다. 하지만 모든 영화에 대해서 이러한 feature를 갖고 있기는 쉽지 않다. 따라서 이를 위해 not content-based인 "collaborative filtering" 기술이 필요하다.

영화 평점 데이터 중, 영화의 feature $x^{(i)}$는 주어지지 않고 유저의 parameter vecotr $\theta^{(j)}$만 주어졌다고 해보자.

• $x^{(1)}$의 $x_1$, $x_2$ 값은 모르는 상태로 시작한다.
• 그리고 각 유저의 $x^{(1)}$에 대한 평점과 각 유저의 parameter $\theta^{(1)},\theta^{(2)},\theta^{(3)},\theta^{(4)}$를 가지고 $x^{(1)}$의 값을 예측해보자.
  • $(\theta^{(1)})^Tx^{(1)}\approx 5$
  • $(\theta^{(2)})^Tx^{(1)}\approx 5$
  • $(\theta^{(3)})^Tx^{(1)}\approx 0$
  • $(\theta^{(4)})^Tx^{(1)}\approx 0$
• 예측 결과, 아마도 $x^{(1)}=\begin{bmatrix}1.0 \\ 0\end{bmatrix}$과 같이 나올 것이다.
• 이처럼 유저의 파라미터 $\theta$를 가지고 각 영화의 feature $x$를 구할 수가 있다.
  

optimization 방법도 앞서 봤던 $\theta$를 학습하는 방법과 유사하다. 이전에서는 $x$가 주어지고 $\theta$를 예측해야 했다면, 이번에는 $\theta$가 주어지고 $x$를 예측하면 된다. 따라서 다음과 같이 수식을 정리할 수 있다.

• $\underset{x^{(1)},...,x^{(n_m)}}{min}\frac{1}{2}\sum_{i=1}^{n_m} \sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^n (x_k^{(i)})^2$
  

따라서 Collaborative filtering을 예시와 함께 설명하면 다음과 같다.

• 영화 feature vector $x$ 정보가 있다면 이 정보를 가지고 유저 parameter vector $\theta$를 학습하고,
• 유저 parameter vector $\theta$가 있다면 영화 feature vector $x$를 학습한다.
• 그리고 닭이 먼저냐 달걀이 먼저냐 처럼, 만약 둘 중 아무것도 주어지지 않는다면 아래와 같이 수행한다.
  1. 처음에 $\theta$를 랜덤하게 선택한다. (유저들이 어떤 영화를 좋아하는지 모름.)
  2. 다음으로 $\theta$에 대해서 영화 feature $x$를 예측한다.
  3. 영화 feature $x$를 가지고 유저 parameter $\theta$를 예측한다.
  4. 유저 parameter $\theta$를 가지고 영화 feature $x$를 예측한다.
  5. 영화 feature $x$를 가지고 유저 parameter $\theta$를 예측한다.
  6. 유저 parameter $\theta$를 가지고 영화 feature $x$를 예측한다.
     ...
• 아마 유저가 영화를 보고 평을 남기거나 본인의 선호도를 입력하면, 데이터가 쌓이면서 위 과정이 더 효과적으로 학습될 것이다.
  

그리고 각각의 optimization function을 다음과 같이 하나로 통합할 수 있다.

• $\theta$가 주어지고 $x$를 예측할 때 :
  $\underset{x^{(1)},...,x^{(n_m)}}{min}\frac{1}{2}\sum_{i=1}^{n_m} \sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^n (x_k^{(i)})^2$
• $x$가 주어지고 $\theta$를 예측할 때 :
  $\underset{\theta^{(1)},...,\theta^{(n_u)}}{min}\frac{1}{2}\sum_{j=1}^{n_u} \sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^n (\theta_k^{(j)})^2$
• 그리고 자세히 보니 두 cost function이 동일함을 알 수가 있다. ($((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2$)
• 따라서 두 케이스를 모두 고려한 다음과 같이 cost function을 정리할 수 있다.
  $J(x^{(1)},...,x^{(n_m)},\theta^{(1)},...,\theta^{(n_u)})=\frac{1}{2}\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^n (x_k^{(i)})^2 + \frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^n (\theta_k^{(j)})^2$
  
  $\therefore \underset{x^{(1)},...,x^{(n_m)},\theta^{(1)}, ...,\theta^{(n_u)}}{min} J(x^{(1)},...,x^{(n_m)},\theta^{(1)}, ...,\theta^{(n_u)})$
  (한가지 주의점이 있다면, $x,\theta \in \mathbb{R}^n$이라는 점이다. 기존에는 $\theta_0=1$때문에 1차원이 더 많았지만, $x_0$은 1이라는 보장이 없기 때문에 이 부분을 제외하여 $n$차원이 된다.)
  

따라서 Collaborative filtering alg.을 정리하면 아래와 같다.
1. 영화 feature vector $x$와 유저 parameter vector $\theta$를 랜덤하게 초기화한다.
2. gradient descent alg.을 이용하여 cost function $J(x^{(1)},...,x^{(n_m)},\theta^{(1)},...,\theta^{(n_u)})$을 최소화하는 $x^{(1)},...,x^{(n_m)},\theta^{(1)},...,\theta^{(n_u)}$을 찾는다.
3. 위 과정으로 학습한 parameter $\theta$와 feature $x$를 가지고 평점 $\theta^Tx$를 계산하여 예측한다.

그렇다면 predict하는 과정을 한번에 빠르게 연산할 수 있는 방법을 알아보자.
아래 그림과 같이 유저 $j$의 영화 $i$에 대한 평점 $y^{(i,j)}$를 우측 행렬 $Y$로 표현해보자.

그리고 이 $Y$의 값을 구하는 방법은 다음과 같다.
$y^{(i,j)}=(\theta^{(j)})^Tx^{(i)}$

• 하지만 "Vectorization"을 활용하면 한 번에 $Y$ 행렬을 구할 수가 있다. 그리고 그 과정은 다음과 같다.
• $X=\begin{bmatrix}-(x^{(1)})^T- \\ -(x^{(2)})^T- \\ . \\ . \\ -(x^{(n_m)})^T-\end{bmatrix} \in \mathbb{R}^{n_m \times n}$, $\Theta=\begin{bmatrix}-(\theta^{(1)})^T- \\ -(\theta^{(2)})^T- \\ . \\ . \\ -(\theta^{(n_u)})^T-\end{bmatrix} \in \mathbb{R}^{n_u \times n}$
• $\underbrace{Y}_{n_m \times n_u}=\underbrace{X}_{n_m \times n} \ \underbrace{\Theta^T}_{n\times n_u}$
  

다음으로 영화 간 유사도를 측정하는 방법은 다음과 같다.

• 영화 $i$의 feature vector $x^{(i)}$는 $n$개의 칼럼을 갖는다. ($x_1:romance$, $x_2:action$, ...)
• 그리고 영화 $i$와 영화 $j$ 간의 유사도는 다음과 같은 식으로 계산할 수 있다. $||x^{(i)}-x^{(j)}||$
• 따라서 $||x^{(i)}-x^{(j)}||$ 값이 작다면 영화 $i$와 영화 $j$는 유사한 영화라고 볼 수 있다.
• 만약 영화 $i$와 가장 비슷한 영화 5개를 골라야 한다면 $||x^{(i)}-x^{(j)}||$ 값이 가장 작은 5개의 영화 $j$를 선택하면 된다.
  

그렇다면 유저가 어떤 영화에도 평점을 남기지 않았다면 어떻게 해야 할까? 아래 예시를 보자.

• Eve는 어떤 영화에도 평점을 남기지 않았다.
• 따라서 Eve의 index인 $5$에 대한 user parameter $\theta^{(5)}$를 학습하면 $\theta^{(5)}=\begin{bmatrix}0 \\ 0\end{bmatrix}$와 같이 나올 것이다.
• $\theta^{(5)}=\begin{bmatrix}0 \\ 0\end{bmatrix}$를 가지고 예측을 하면 당연히 결과는 0만 나올 것이다.
• 따라서 이를 해결하기 위해 Mean Noramlization 방법을 적용해야 한다.
  

Mean Normalization에 대한 설명은 아래와 같다.

• 모든 영화에 대해서 평균 평점을 구한다. 영화 $i$의 평균 평점 : $\mu_i$
• 그리고 평점이 있는 기존의 값에 평균 값을 빼준다. $y^{(i,j)}:=y^{(i,j)}-\mu_i$ (if $r(i,j)=1$)
• 그리고 예측 결과에 해당 $\mu$ 값을 더해줌으로써, 값이 0이 되는 것을 방지할 수 있다.
  $y^{(i,j)}=(\theta^{(j)})^Tx^{(i)} + \mu_i$
• 따라서 위에서와 달리 mean normalization을 적용한 eve(5)의 각 영화에 대한 예측값은 2.5로 나올 것이다.
  
  (다만, 왜 굳이 평균값을 그냥 넣어주지 않고 더해주는 식으로 적용하는지 의문이 든다. 그래서 곰곰이 생각해보니, 단순히 $\mu$값을 대입하면 기존 분포의 모양이 망가질 수 있다는 생각이 들었다. 하지만 모든 예측값에 $\mu$를 더해줘도 기존 분포의 모양은 유지될 것이다.)