Recommend system

andrew ng lecture note recommend 를 공부하며 번역하여서 올립니다

각 영화에 대해서 평점이 5점까지 줄수 있다고 가정한다

Movie	Alice(1)	Bob(2)	Carol(3)	Dave(4)
Love at star	5	5	0	0
Romance Forevere	5	?	?	0
Cute love	?	4	0	?
Nonstop Car	0	0	5	4
Sword	0	0	5	?

Notation

• $n_u$ : 총 유저의 명(수)

• $n_m$ : 총 영화의 갯수

• $r(i,j)$ : $j$라는 유저가 영화 $i$에 평점을 줬으면 1

• $y^{(i,j)}$ : $r(i,j) = 1$이라는 조건 하에 user $j$가 movie $i$에게 준 평점 점수

우리는 주어진 데이터를 가지고 missing value를 predict해야 한다

1. Content_based algorithm

content_based는 content가 어떤 특정한 잠재 feature가 있을거라고 생각하고 그 feature vector를 적용하는 것이다.
예를 들어 영화를 추천하는 거라면 영화에는 각 장르가 존재한다. 영화의 로맨스 장르 정도, 액션 정도를 가중치 개념으로 주어서 각 영화의 latent feature vector를 지정해준다

여기에서는 romance를 $x_1$, action $x_2$의 feature vector를 만들어준다 extra(constant) feature도 넣어준다

Movie	Alice(1)	Bob(2)	Carol(3)	Dave(4)	$x_0$(constant)	$x_1$(romance)	$x_2$(action)
Love at star	5	5	0	0	1	0.9	0
Romance Forevere	5	?	?	0	1	1.0	0.1
Cute love	?	4	0	?	1	0.99	0
Nonstop Car	0	0	5	4	1	0.1	1.0
Sword	0	0	5	?	1	0	0.9

각각의 영화는 $\begin{bmatrix}
Love.. & Romance.. & Cute.. & Nonstop.. & Sword.. \\
\end{bmatrix} =\begin{bmatrix}
x^1 & x^2 & x^3 & x^4 & x^5 \\
\end{bmatrix}$

각각의 영화 $x^i$은 feature vector를 가지고 있다
에를 들어 영화 Love at star $x^1 = \begin{bmatrix}
1 \\
0.9\\
0
\end{bmatrix}$ 의 feature vector를 가지고 있다

content_based 방식에서는 각각의 content feature vector에 따른 user parameter vector를 learning시켜야한다
각각의 user마다 각각의 평점은 linear regression방식으로 나타난다

만약 Alice의 parameter vector($\theta^1$)이 $\theta^1 = \begin{bmatrix}
0 \\
5\\
0
\end{bmatrix}$ 이라고 한다면 Alice가 Cute love 영화에 평점을 줄 점수는 $(\theta^{(1)})^T x^{(3)}$ inner product를 해주면 4.95 평점을 줄거라는 예측이 나온다

$\theta$를 learning 해보자

Notation

• n : feature의 dimension(constant를 제외한것) 여기서는 2(romance, action)이다

• $m^j$ : $j$ user가 평점을 준 영화의 갯수

$j$ user가 평점을 준 영화에 한해서 $j$ user의 영화에 준 예측 평점과 실제 평점의 차를 최소화 해야한다

$$min_{\theta^{(j)}} \frac{1}{2 m^{(j)}} \sum_{i:r(i,j)=1} \left(\left(\theta^{(j)}\right) ^T x^{(i)} - y^{(i,j)}\right)^2 + \frac{\lambda}{2 m^{(j)}}\sum_{k=1}^n \left( \theta_k^{(j)}\right)^2$$

최적화 하는데 $m^{(j)}$는 필요 없으므로 없애주어도 된다

$$min_{\theta^{(j)}} \frac{1}{2} \sum_{i:r(i,j)=1} \left(\left(\theta^{(j)}\right) ^T x^{(i)} - y^{(i,j)}\right)^2 + \frac{\lambda}{2}\sum_{k=1}^n \left( \theta_k^{(j)}\right)^2$$

이거를 모든 user에게 적용시켜야 한다. 우리의 objective function이 된다

$$J(\theta^1, \ldots, \theta^{n_u}) =\underset{\theta^{(1)}, \cdots, \theta^{(n_u)}}{\operatorname{min}}\frac{1}{2} \sum_{j=1}^{n_u}\sum_{i:r(i,j)=1} \left(\left(\theta^{(j)}\right) ^T x^{(i)} - y^{(i,j)}\right)^2 + \frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^n \left( \theta_k^{(j)}\right)^2$$

$\theta$에 대해서 미분을 해준다

$\theta_k^{(j)} : \theta_k^{(j)} - \alpha\sum_{i:r(i,j)=1} \left(\left(\theta^{(j)}\right) ^T x^{(i)} - y^{(i,j)}\right)x_k^{(i)}$ $(for \text{ } k= 0)$

$\theta_k^{(j)} : \theta_k^{(j)} - \alpha \left(\sum_{i:r(i,j)=1} \left(\left(\theta^{(j)}\right) ^T x^{(i)} - y^{(i,j)}\right)x_k^{(i)} + \lambda \theta_k^{(j)} \right)$ $(for \text{ } k\neq 0)$

k가 0인것과 K가 0이 아닌것의 뜻은 feature의 constant term을 하느냐 안하느냐 이다

우리의 Obejctive function의 최종식은

$${\partial^2\over\partial\theta_k^{(j)}}J(\theta^1, \ldots, \theta^{n_u})=\left(\sum_{i:r(i,j)=1} \left(\left(\theta^{(j)}\right) ^T x^{(i)} - y^{(i,j)}\right)x_k^{(i)} + \lambda \theta_k^{(j)} \right)$$

content_based는 각 content에 대한 feature를 알아야 한다는 단점이 있다. 다음에 알아볼 방법은 이거를 보완해준 Colloaborative filtering방법이다

2. Collaborative filtering

1. content_based 방식에서는 content feature를 알고 있는 상태였다. 하지만 현실에서는 불가능하다
2. 또한 Feature의 갯수를 조금더 많이 알기를 원한다

user의 영화 취향 벡터 $\theta$와 각 영화의 장르 feature 벡터 $x$를 서로 교차적으로 learning

Notation

• $n_m$ : 영화의 갯수

• $n_u$ : user의 수

1. $\theta$를 랜덤적으로 Initialize한다

   $\theta$를 가지고 $x$를 update시킨다

   $$\underset{x^{(1)}, \cdots, x^{(n_m)}}{\operatorname{min}} {1\over2} \sum_{j=1}^{n_m}\sum_{i:r(i,j)=1} \left(\left(\theta^{(j)}\right) ^T x^{(i)} - y^{(i,j)}\right)^2 + \frac{\lambda}{2}\sum_{j=1}^{n_m}\sum_{k=1}^n \left( x_k^{(j)}\right)^2$$

2. update된 $x$를 가지고 $\theta$를 Update시킨다

   $$\underset{\theta^{(1)}, \cdots, \theta^{(n_u)}}{\operatorname{min}} {1\over2} \sum_{j=1}^{n_u}\sum_{i:r(i,j)=1} \left(\left(\theta^{(j)}\right) ^T x^{(i)} - y^{(i,j)}\right)^2 + \frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^n \left( \theta_k^{(j)}\right)^2$$

Minimizing $\theta^{(1)}, \cdots, \theta^{(n_u)}$ and $x^{(1)}, \cdots, x^{(n_m)}$ simultaneously $$J(x^{(1)}, \cdots, x^{(n_m)},\theta^{(1)}, \cdots, \theta^{(n_u)}) ={1\over2} \sum_{(i,j):r(i,j)=1} \left(\left(\theta^{(j)}\right) ^T x^{(i)} - y^{(i,j)}\right)^2 + \frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^n \left( \theta_k^{(j)}\right)^2 + \frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^n \left( x_k^{(i)}\right)^2$$ $$\underset{x^{(1)}, \cdots, x^{(n_m)},\theta^{(1)}, \cdots, \theta^{(n_u)}}{\operatorname{min}}J\left(x^{(1)}, \cdots, x^{(n_m)},\theta^{(1)}, \cdots, \theta^{(n_u)}\right)$$

content_based와 다른점은 costant Term을 넣어주지 않는다는 것이다

cost function J를 최대한 줄여주는 벡터를 찾는다

3. Low rank matrix Factorization $$Y = \begin{bmatrix} 5 & 5 & 0 &0\\ 5 & ? & ? &0\\ ? & 4 & 0 &?\\ 0 & 0 & 5 &4\\ 0 & 0 & 5 &0\\ \end{bmatrix}$$

5개의 영화와 4명의 user matrix이다

predicted rating은 다음과 같이 나타낼수 있다

$$X = \begin{bmatrix} --- \left(x^{(1)}\right)^T ---\\ --- \left(x^{(2)}\right)^T ---\\ \vdots\\ --- \left(x^{(n_m)}\right)^T ---\\ \end{bmatrix}$$ $$\Theta = \begin{bmatrix} --- \left(\theta^{(1)}\right)^T ---\\ --- \left(\theta^{(2)}\right)^T ---\\ \vdots\\ --- \left(\theta^{(n_u)}\right)^T ---\\ \end{bmatrix}$$

predicted rating matrix = $\Theta^T \cdot X$

Notation

• $r_{i,j}$ : $i$ 유저가 $j$ 영화에게준 실제 평점

• $e_{i,j}$ : $i$ 유저가 $j$ 영화에게준 실제 평점과 예측 평점의 차이

• $p_{i,k}$ : $i$ 유저의 latent feature vector

• $q_{k,j}$ : $j$ 영화의 latent feature vector

• $\beta$ : Regularization Term

• $\alpha$ : Learning rate

• $P$ : 유저들의 Latent Matrix / shape : $\left( \text{유저 명수 (X) Latent 갯수}\right)$

• $Q$ : 영화들의 Latent Matrix / shape : $\left( \text{ Latent 갯수 (X) 영화 갯수 }\right)$

$$e_{i,j}^2 = \left( r_{i,j} -\sum_{k=1}^K p_{i,k} q_{k,j} \right)^2 + {\beta \over 2} \sum_{k=1}^K \left(\lVert P \rVert^2 + \lVert Q \rVert^2\right)$$ $$p_{i,k}^{'} = p_{i,k} + \alpha {\partial \over \partial p_{i,k}}e_{i,j}^2 = p_{i,k} + \alpha \left( 2 e_{i,j}q_{k,j} - \beta p_{i,k}\right)$$ $$q_{k,j}^{'} = q_{k,j} + \alpha {\partial \over \partial q_{k,j}}e_{i,j}^2 = q_{k,j} + \alpha \left( 2 e_{i,j}p_{i,k} - \beta q_{k,j}\right)$$

$p_{i,k}^{‘}$, $q_{k,j}^{‘}$ 각각 벡터이다