Recommender System

机器学习

---

Key Problems:

1. How to collect data.
2. Extrapolate unknown rating from the known ones.
3. Evaluating extrapolation methods.

3 Approaches to recommender systems:

1. Content-based
2. Collaborative
3. Latent factor based

---

Content-based Recommender System

Recommend items to customer $x$ similar item highly rated by $x$.

TF-IDF

$$TF_{ij} = \frac{f_{ij}}{\max_k f_{kj}}$$
where $f_{ij} =$ frequency of term (feature) $i$ in doc (item) $j$.
$$IDF_i = \log(\frac N n_i)$$
where $N$ is the number of docs, $n_i$ is the num of docs that mention term $i$.
TF-IDF score: $w_{ij} = TF_{ij} \times IDF_i$. Doc profiles = set of words with highest TF-IDF scores.

Pros:

• No cold-start
• Able to provide explanations

Cons:

• Finding apropriate features are hard (images, movies)
• How to build a user profile for new users?

---

Collaborative Filtering

User-user collaborative filtering: Find set $N$ of users whos ratings are similar to user $x$, and estimate user $x$'s ratings based on users in $N$.

Item-item collaborative filtering:

1. For item $i$, find other similar items.
2. Estimate ratings for item $i$ based on similar items:
   $$r_{xi} = \frac {\sum_{j \in N(i; x)} S_{ij} \times r_{xj}} {\sum_{j \in N(i; x)} S_{ij} }$$
   where $S_{ij}$ is similarity, $r_{xj}$ is rating on $j$, $N(i; x)$ is similar items rated by user $x$.

In practice, estimate $r_{xi}$ as the weighted average:

$$r_{xi} = b_{xi} + \frac {\sum_{j \in N(i; x)} S_{ij} \times (r_{xj} - b_{xj})} {\sum_{j \in N(i; x)} S_{ij} }$$
where $b_{xj} = \mu + b_x + b_j$, $\mu$ is overall movie rating, $b_x = \mu_x - \mu$, $b_j = \mu_j - \mu$.

Pros:

• No feature selection needed

Cons:

• Cold start
• User / Rating matrix sparsity
• Tends to recommend popular items

---

Practical Tips

1. Compare predictions with known ratings:
   
   • Root mean square error: $\frac 1 {|R|} \sqrt{\sum_{(i, x) \in R} (\hat{r}_{xi} - r_{xi})^2}$
   • % of those in top 10
2. In pratice, we care only about high ratings (recommender).
3. Finding $k$ most similar is expensive: LSH.

---

Interpolation Weights

$$r_{xi} = b_{xi} + \sum_{j \in N(i; x)} W_{ij} \times (r_{xj} - b_{xj})$$

Learn $W_{ij}$ that minimizes SSE $\sum_{(i, x) \in R} (\hat{r}_{xi} - r_{xi})^2$ on training data. Minimize

$$J(W) = \sum_x \left( \left[ b_{xi} + \sum_{j \in N(i; x)} w_{ij} (r_{xj} - b_{xj}) \right] - r_{xi} \right)^2$$
by gradient descent. The gradient is
$$\frac{\partial J(W)}{\partial W_{ij}} = 2 \sum_{x,i} \left( \left[ b_{xi} + \sum_{k \in N(i; x)} w_{ik} (r_{xk} - b_{xk}) \right] - r_{xi} \right) (r_{xj} - b{xj})$$

---

Latent Factor Models

$R$ is rating matrix, where $R_{ix}$ represents $x$'s rating for item $i$. SVD ($A = U \Sigma V^T$) on $R$: $R = Q P^T$, where $Q = U$, $P^T = \Sigma V^T$, and $r_{xi} = q_i \centerdot p_x$.

SVD isn’t defined when entries are missing! Use specialized methods to find $P$, $Q$

$$\min_{P,Q} \sum_{(i,x) \in R} (r_{xi} - q_i \centerdot p_x)^2$$
Introducing regularization:
$$\min_{P,Q} \sum_{(i,x) \in R} (r_{xi} - q_i \centerdot p_x)^2 + \left[ \lambda_1 \sum_x \| p_x \|^2 + \lambda_2 \sum_i \| q_i \|^2 \right]$$