Recommender System

Utility Matrix

$R$: utility matrix

Users \ Items	Avatar	LOTR	Matrix	Pirates
Alice	5		2
Bob		4		3
Carol	1		5
David				2

• $R=|U| \times |I|$

• $U$: set of users

• $I$: set of items

problem

• $R$ is sparse

• cold start problem

  • 새로운 item들에 대한 rating이 없음

  • 새로운 user들에 대한 기록이 없음

Recommender Systems

1. Content Based

• 사용자가 이전에 높은 평가를 준 아이템과 유사한 아이템을 추천

• 아이템 간 유사성을 계산하기 위해 아이템의 특성(feature)을 활용

• 텍스트 기반의 데이터를 다룰 경우, 문서에서 중요한 단어를 추출해야 하며, 이를 위해 TF-IDF 사용

TF-IDF

$\text{TF-IDF}=w_{id}=TF_{id} \times IDF_i$, 값이 클수록 해당 단어의 중요도가 높은 것

• TF(Term Frequency)

  • 특정 단어가 문서 내에서 얼마나 자주 등장하는지를 나타냄

  • $TF_{id}=\frac{f_{id}}{max_k f_{kd}}$, $f_{id}$: document $d$에 있는 term $i$의 빈도수

• IDF(Inverse Document Frequency)

  • 특정 단어가 전체 문서에서 얼마나 드물게 나타나는지를 나타냄

  • 한 documnet에서만 나타나는 word가 중요하다는 것

  • inverse 하는 이유는 모든 document에서 발현되면 중요도를 줄이기 위함

  • $IDF_i=log(\frac{N}{n_i})$, term $i$가 총 document 개수 $N$의 $n_i$에서의 빈도수

e.g. Document A=[b a b c a a], B=[a b c], C=[a d e f], D=[a d e g]

A: {a:3, b:2, c:1} -> 각 item이 document A에서 나타난 개수

• $TF_{aA}=\frac{a=3}{max(a=3, b= 2, c=1)}=\frac{3}{3}=1$

• $TF_{bA}=\frac{b=2}{max(a=3,b=2,c=1)}=\frac{2}{3}$

A, B, C, D: {a: 4, b: 2, c: 2, d: 2, e: 2, f: 1, g: 1} -> 각 item이 나타난 document의 개

• $IDF_a=log(\frac{N=4}{a=4})=log(\frac{4}{4})=0$

• $IDF_g=log(\frac{N=4}{g=1})=log(\frac{4}{1})=log4$

Heuristic

$R_{xi}=cos(x,i)=\frac{x^Ti}{||x|| \ ||i||}$

• $x$: user profile, 사용자의 이전 활동으로부터 생성된 프로필 (e.g. 관심사, 과거 평점)

• $i$: item profile, 아이템의 특성을 나타내는 프로필 (e.g. 키워드, 장르, 카테고리)

특징

• 장점

  • 다른 사용자의 데이터 필요 없음

  • 새롭고 인기 없는 아이템 추천 가능

• 단점

  • 적절한 특징(feature)를 찾기 어려움

  • 사용자의 컨텐츠 프로필을 벗어난 항목을 추천하지 않

2. Collaborative Filtering

• 나와 비슷한 선호도를 가진 user를 기반으로 추천

• user-user collaborative filtering

• item-item collaborative filtering

user-user collaborative filtering

나와 유사한 user가 rating한 것을 기반으로 rating

• centered cosine similarity(=pearson correlation coefficient: 선형 관계 데이터만 설명 가능)

  1. normalize as rating - mean of row rating

  2. cosine similarity

  $r_{xi}=\frac{\sum_{y \in N}S_{xy}r_{yi}}{\sum_{y \in N}S_{xy}}$

  • $x, y$: user

  • $S_{xy}=sim(x,y)$

e.g. N=2일때, user1의 item5에 대한 rate을 예측하여라

users \ items	item1	item2	item3	item4	item5
user1	1	5	3	3	?
user2	1	4			4
user3	4	4	3		5
user4	1	4			5

1. 각 user 별 평균 계산

• $\overline{user1}=\frac{1+5+3+3}{4}=3$

• $\overline{user2}=\frac{1+4+4}{3}=3$

• $\overline{user3}=\frac{4+4+3+5}{4}=4$

• $\overline{user4}=\frac{1+4+5}{3}=3.3$

1. null 값이 아닌 경우 평균을 빼주고 null 값인 경우 0으로 정규화

	item1	item2	item3	item4	item5
user1	-2	2	0	0	0
user2	-2	1	0	0	1
user3	0	0	-1	0	1
user4	-2.3	0.7	0	0	1.7

1. cosine similarity 계산(소숫점 둘째자리 반올림)

• $sim(user1, user2)=\frac{-2\times-2+2\times1+0\times0+0\times0+0\times1}{\sqrt{(-2)^2+2^2+0^2+0^2+0^2}\sqrt{(-2)^2+1^2+0^2+0^2+1^2}}=0.87$

• $sim(user1, user3)=0$

• $sim(user1, user4)=0.72$

1. rate 계산

• user1과 가장 유사한 2명의 user는 user2(sim=0.87)과 user4(sim=0.72)

• $item5(user1)=\frac{0.87 \times 4 + 0.72 \times 5}{0.87+0.72}=4.45$

item-item collaborative filtering

• 예측하고자 하는 item과 유사한 item에 대해 user가 rating한 것을 기반으로 rating

• user-user와 계산 방식 동일(user x item을 item x user로 바꿔 계산)

• user-user 보다 더 나은 성능을 보임(user는 다양한 취향이 고려되어야하는 반면 item은 단순함)

baseline predictor collaborative filtering

• $r_{xi}=b_{xi}+\frac{\sum_{j \in N(i:x)}S_{ij}r_{xj}}{\sum_{j \in N(i:x)}S_{ij}}$

  • $b_{xi}=\mu+b_x+b_i$: user

  • $S_{ij}=sim(i,j)$

  • $N(i:x)$: user $x$가 item $i$와 유사하게 rating한 item의 집합

  • $b_x$: user $x$의 rating 편차

  • $b_i$: item $i$의 rating 편차

example

• $\mu=3.7, b_i=0.5, b_x=-0.2$

• $b_{xi}=3.7+0.5+(-0.2)=4.0$

3. Latent Factor Models

• $R$을 $P(items\times factors)$와 $Q(factors\times users)$로 decomposition

• $R_{xi} = Q_i \cdot P_x$

  • $Q_i$: $Q$의 row $i$

  • $P_i$: $P^T$의 col $x$

만약, item1에 대한 user5의 rate을 예측한다면 → $R_{5,1}=[0.1, -0.4, 0.2]\cdot[-2,0.3,2.4]=3.4$

Stochastic Gradient Descent

concept

• gradient descent: $f(x)$ 값이 최소가 되는 $x$를 찾는 과정

  1. graidnet($\triangledown f(x)$) 계산

  2. $x'=x-\eta \triangledown f(x), \ \eta: \text{learning rate}$

  3. $x=x'$

  4. until convergence: $|x'-x|<\epsilon \ or \ \text{set number of iterations}$

• stochastic gradient descent

  • gradient descent는 전체 학습 데이터셋을 이용해 에폭 한번 당 gradient를 업데이트(비효율적)

  • stochastic gradient descent는 batch size로 학습 데이터 안에 subset 데이터를 만들고 이를 이용해 gradient를 업데이트(효율적)

loss

• $J(P,Q)=min_{P,Q} \ \sum_{(x,i)\in R}(r_{xi}-q_ip_x)^2+[\lambda_1 \sum_x ||p_x||^2 + \lambda_2 \sum_i ||q_i||^2]$

• $J(P,Q,b)=min_{P,Q,b} \ \sum_{(x,i)\in R}(R_{xi}-\hat{R}_{xi})^2+\lambda[\sum_x ||p_x||^2_2 + \sum_i ||q_i||^2_2 + \sum_x ||b_x||^2_2 + \sum_i ||b_i||^2_2]$

  • $\hat{R}_{xi}=\mu+b_x+b_i+q_ip_x$

Correlation

e.g. study times과 exam score 사이의 상관관계

student	study times	exam score
A	10	75
B	8	60
C	12	85
D	6	55
E	7	90

• Pearson Correlation: 선형 관계 측정, 이상치에 민감(크기 정보 활용하기 때문)

  1. calculate mean of data

     • study times: $\frac{10+8+12+6+7}{5}=8.6$

     • exam score: $\frac{75+60+85+55+90}{5}=73$

  2. substract

     student	study times	exam score
     A	1.4	2
     B	-0.6	-13
     C	3.4	12
     D	-2.6	-18
     E	-1.6	17

  3. cosine similarity

     • $r=\frac{1.4\times 2+(-0.6)\times(-13)+3.4\times12+(-2.6)\times(-18)+(-1.6)\times17}{\sqrt{1.4^2+(-0.6)^2+3.4^2+(-2.6)^2+(-1.6)^2}\sqrt{2^2+(-13)^2+12^2+(-18)^2+17^2}}$

     • $r=0.4$

• Spearman’s Rank Correlation: 단조 관계 측정, 이상치에 덜 민감(순위 정보 활용하기 때문)

  1. rank data

     student	Rank(study times)	Rank(exam score)
     A	2	3
     B	3	4
     C	1	2
     D	5	5
     E	4	1

  2. calculate

     • $D_i=\text{Rank of study times}_i-\text{Rank of exam score}_i$

       student	$D_i$
       A	-1
       B	-1
       C	-1
       D	0
       E	3

  3. calculate

     • $\rho=1-\frac{6 \sum_i (D_i)^2}{n(n^2-1)}=1-\frac{6[(-1)^2+(-1)^2+(-1)^2+0^2+3^2]}{5(5^2-1)}$

     • $\rho=1-0.6=0.4$