推荐系统(Recommender Systems)
问题定义
本文使用电影评分推荐的例子来解释两种推荐系统的工作原理，电影推荐的问题可以描述为：
已知一些用户对一些电影的评分，预测用户对未评价电影的评分。
| 用户1 | 用户2 | 用户3 | 用户4 | |
|---|---|---|---|---|
| 电影1 | 5 | 5 | 0 | 0 |
| 电影2 | 5 | ? | ? | 1 |
| 电影3 | ? | 4 | 0 | ? |
| 电影4 | 0 | 0 | 4 | 5 |
| 电影5 | 0 | 0 | 4 | ? |
即，已知：
- \(n_u=\) 用户数量；
- \(n_m=\) 电影数量；
- \(r(i,j)=1\) 如果用户\(j\)给电影\(i\)打了分，否则为0；
- \(y^{(i,j)}=\) 用户\(j\)给电影\(i\)打的分数（只有当\(r(i,j)=1\)时才有定义）；
- \(m^{(j)}=\) 用户\(j\)打分了的电影数量；
估计：
- \(\theta^{(j)}=\) 用户\(j\)的参数向量；
- \(x^{(i)}=\) 电影\(i\)的特征向量；
- 对于用户\(j\)，电影\(i\)，预测\((\theta^{(j)})^T(x^{(i)})\)
基于内容的推荐系统
根据已知每个电影的特征\(x^{(i)}\)，学习用户偏好\(\theta^{(1)},…,\theta^{(n_u)}\)，则损失函数为：
$$min_{\theta^{(1)},…,\theta^{(n_u)}}\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$$
梯度下降：
$$\theta_k^{(j)} := \theta_k^{(j)} - \alpha\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x^{(i)}\quad (for\quad k=0 )\ \theta_k^{(j)} := \theta_k^{(j)} - \alpha(\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x^{(i)}+\lambda\theta_k^{(j)}\quad)\quad (for\quad k\neq0 )$$
使用协同过滤的推荐系统
若我们事先知道各用户的偏好参数 \(\theta^{(j)}\)，则可以学习电影的特征：
$$min_{x^{(1)},…,x^{(n_m)}}\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^{(j)})^2$$
那么：
给出\(x^{(1)},…,x^{(n_m)}\)和电影评分，可以估计\(\theta^{(1)},…,\theta^{(n_u)}\)；
给出\(\theta^{(1)},…,\theta^{(n_u)}\)和电影评分，可以估计\(x^{(1)},…,x^{(n_m)}\)。
这似乎是一个“先有鸡还是先有蛋”的问题，其实我们在解决这个问题时，可以先随机生成 \(\theta\)，然后估计\(x\)，接着根据\(x\)再次估计一组新的\(\theta\)，如此循环最后可以收敛到一组足够合理的结果。
$$ Guess\quad\theta \to x\to\theta\to x\to …$$
以上就是协同过滤的思想。但为了提高计算效率，实际上\(x^{(1)},…,x^{(n_m)}\)和\(\theta^{(1)},…,\theta^{(n_u)}\)是同时考虑的，这样可以将损失函数定义为：
$$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^{(j)})^2+\frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^{n}(\theta_k^{(j)})^2$$
协同过滤算法：
- 使用小的随机值初始化\(x^{(1)},…,x^{(n_m)},\theta^{(1)},…,\theta^{(n_u)}\)；
- 使用梯度下降最小化损失函数\(J(x^{(1)},…,x^{(n_m)},\theta^{(1)},…,\theta^{(n_u)})\)；
- 对偏好参数为\(\theta\)的用户和特征值为（学习到的）\(x\)的电影，预测其打分\(\theta^Tx\)
此时不再需要截距项：
\(x^{(i)}\in \mathbb{R}^n\)
\(\theta^{(j)}\in \mathbb{R}^n\)
协同过滤算法的向量化实现即低秩矩阵分解(Low Rank Matrix Factorization)的过程。
Mean Normalization
在使用协同过滤算法时应该将打分矩阵均值正规化。因为对于无法得知偏好的新用户(初始化\(\theta^T=[0,0,…]\))，均值正规化可以避免\(\theta\)和\(x\)的最优解都是零矩阵（最后的结果其实就是把其他已知打分的均值赋给了新用户）。
寻找相关电影
可以根据电影相似性进行推荐：比如对于喜欢电影\(i\)的用户，我们在学习其它电影的特征后将与电影\(i\)最相似的5个电影就是5个最小\(||x^{(i)}-x^{(j)}||\)的电影推荐给这个用户。