本章主要讲解机器学习中的一个重要应用——推荐系统。
Problem formulation
本节课以预测电影评分为例，介绍了什么是推荐系统。
我们有5部电影和4个用户，要求用户从0-5对电影打分：
注：
？表示用户没有打分的电影，也就是需要我们预测的电影。
前3部电影是爱情片，后2部电影是动作片，可以看出Alice和Bob似乎更倾向于爱情片，而Carol和Dave似乎更倾向于动作片。我们希望构建一个算法来预测所有用户可能会对他们没看过的电影打多少分，并以此作为推荐的依据。
下面引入一些标记：
- \(n_u\) 代表用户数量
- \(n_m\) 代表电影数量
- \(r(i,j)\) 如果用户\(j\)给电影\(i\)评过分则\(r(i,j)=1\)
- \(y^{(i,j)}\) 代表用户\(j\)给电影\(i\)的评分（只有在\(r(i,j)=1\)时才定义）
Content-based recommendations
主要讲解了推荐系统的一种方法——基于内容的推荐系统。
Content-based recommender systems
在我们的电影推荐例子中，我们可以假设每部电影都有两个特征（表示其内容），E.g. \(x_1\)代表电影的浪漫成分，\(x_2\)代表电影的动作成分。
再加上特征\(x_0=1\)，这样每部电影就得到了一个特征向量，E.g. 第一部电影的特征向量为\(x^{(1)} = \begin{bmatrix} 1 \\ 0.9 \\ 0\end{bmatrix}\)。
下面我们基于这些特征构造一个推荐系统算法，假设我们采用线性回归模型，那么可以针对每一个用户\(j\)训练一个参数\(\theta^{(j)} \in \R^3\)。可以预测用户\(j\)对电影\(i\)的评分为\((\theta^{(j)})^Tx^{(i)}\)颗星。
E.g. 假如对于用户1我们得到模型参数\(\theta^{(1)} = \begin{bmatrix} 0 \\ 5 \\ 0 \end{bmatrix}\)，而电影3的特征值为$x^{(3)} =\begin{bmatrix} 1 \ 0.99 \ 0 \end{bmatrix} \(，那么就可以预测出用户1对于电影3的评分为\)(\theta{(1)})Tx^{(3)} = 5 \times 0.99 = 4.95$。
Problem formulation
我们把问题的表述正式化。
- \(n_u\) 代表用户数量
- \(n_m\) 代表电影数量
- \(r(i,j)\) 如果用户\(j\)给电影\(i\)评过分则\(r(i,j)=1\)
- \(y^{(i,j)}\) 代表用户\(j\)给电影\(i\)的评分（只有在\(r(i,j)=1\)时才定义）
- \(m^{(j)}\) 代表用户\(j\)给出评分的电影数量
对于用户\(j\)，电影\(i\)，预测评分：\((\theta^{(j)})^Tx^{(i)}\)，学习参数\(\theta^{(j)}\)的线性回归模型为：
\[\min \limits_{\theta(j)} \frac{1}{2 m^{(j)}} \sum_{i \colon r(i,j)=1} ((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2m^{(j)}} \sum_{k=1}^n (\theta_k^{(j)})^2 \]其中，\(i \colon r(i,j)=1\)表示值计算那些用户\(j\)评过分的电影。
由于\(\frac{1}{m^{(j)}}\)为常数项，不影响优化目标，因此对于用户\(j\)的学习参数\(\theta^{(j)}\)的模型可以简化为：
\[\min \limits_{\theta(j)} \frac{1}{2} \sum_{i \colon r(i,j)=1} ((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2} \sum_{k=1}^n (\theta_k^{(j)})^2 \]对于所有用户的优化目标，只需要把上面单用户的式子再进行求和，为：
\[\min \limits_{\theta(1),\cdots,\theta(n_u)} \frac{1}{2} \sum_{j=1}^{n_u} \sum_{i \colon 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 \]Optimization algorithm
为了求解最优解，我们需要计算梯度下降的更新公式：
注：对于\(k=0\)项，也就是特征值\(x_0\)，我们是不进行正则化的，所以上面的式子需要分成两种情况。
Collaborative filtering
基于内容的推荐算法的局限性在于我们必须要知道了每部电影的内容（特征值），但在某些时候我们是难以获取这些特征值的，因此这节课介绍了另外一种推荐算法——协同过滤算法。
Problem motivation
假如我们没有每一部电影关于内容的特征值，但是我们却有每个用户对于每一类电影的喜爱程度的数据。
E.g. 4个用户对于不同类型电影的喜爱程度如下：
注：\(x_0=0\)，\(x_1=\)对于爱情片的喜爱程度，\(x_2=\)对于动作片的喜爱程度。
Optimization algorithm
那么我们的优化目标就变成了，给定\(\theta^{(1)},\theta^{(2)}, \cdots, \theta^{(n_u)}\)，学习\(x^{(i)}\)：
\[\min \limits_{x(i)} \frac{1}{2} \sum_{j \colon r(i,j)=1} ((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2} \sum_{k=1}^n (x_k^{(j)})^2 \]如果是学习所有电影的内容特征值\(x^{(1)},x^{(2)}, \cdots, x^{(n_m)}\)，那么只需要对所有电影特征进行求和：
\[\min \limits_{x(1),\cdots,x(n_m)} \frac{1}{2} \sum_{j=1}^{n_m} \sum_{j \colon 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 \]简单小结一下，上节课讲解的基于内容的推荐算法，通过电影内容特征值预测用户偏好：
本节课讲解的算法过程，通过用户偏好预测电影内容特征值：
但是假如我们既没有用户参数，也没有电影特征，那么协同过滤算法可以同时学习这两种。首先随机生成一组\(\theta\)，以此来预测\(x\)，然后再用预测出来的\(x\)来优化\(\theta\)，再用新的\(\theta\)来预测\(x\)，这样慢慢迭代下去，最后就能得到一组合理的\(\theta\)和\(x\)。\(\theta \rarr x \rarr \theta \rarr x \rarr \theta \cdots\)，这就是最基础的协同过滤算法。
Collaborative filtering algorithm
之前讲解了如何根据给定的电影内容特征值预测用户偏好，也讲解了如何根据给定的用户偏好预测电影内容特征值，本节课主要讨论协同过滤算法是如何如何把两者结合起来的。
Collaborative filtering optimization objective
Given \(x^{(1)}, \cdots, x^{(n_m)}\), estimate \(\theta^{(1)}, \cdots, \theta^{(n_u)}\):
\[\min \limits_{\theta(1),\cdots,\theta(n_u)} \frac{1}{2} \sum_{j=1}^{n_u} \sum_{i \colon 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 \]Given \(\theta^{(1)}, \cdots, \theta^{(n_u)}\), estimate \(x^{(1)}, \cdots, x^{(n_m)}\):
\[\min \limits_{x(1),\cdots,x(n_m)} \frac{1}{2} \sum_{j=1}^{n_m} \sum_{j \colon 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 \]Minimizing \(x^{(1)}, \cdots, x^{(n_m)}\) and \(\theta^{(1)}, \cdots, \theta^{(n_u)}\) simultaneously:
\[J(x^{(1)}, \cdots, x^{(n_m)},\theta^{(1)}, \cdots, \theta^{(n_u)}) = \frac{1}{2} \sum_{(i,j) \colon 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 \\ \mathop{\rm{min}}_{ x^{(1)}, \cdots, x^{(n_m)} \atop \theta^{(1)}, \cdots, \theta^{(n_u)} } J(x^{(1)}, \cdots, x^{(n_m)},\theta^{(1)}, \cdots, \theta^{(n_u)}) \]把两者结合起来，这样我们就同时实现了对\(\theta\)和\(x\)的最优化求解。
Collaborative filtering algorithm
协同过滤算法的步骤：
-
Initialize \(x^{(1)}, \cdots, x^{(n_m)},\theta^{(1)}, \cdots, \theta^{(n_u)}\) to small random values.
-
Minimize \(J(x^{(1)}, \cdots, x^{(n_m)},\theta^{(1)}, \cdots, \theta^{(n_u)})\) using gradient descent (or an advanced optimization algorithm).
E.g. for every \(j=1,\cdots,n_u,i=1,\cdots,n_m\):
\[x_k^{(i)} := x_k^{(i)} - \alpha \bigg( \sum \limits_{j:r(i,j)=1} (\theta^{(j)})^Tx^{(i)} - y^{(i,j)} \theta_k^j + \lambda x_k^{(i)} \bigg) \\ \theta_k^{(j)} := \theta_k^{(j)} - \alpha \bigg( \sum \limits_{i:r(i,j)=1} (\theta^{(j)})^Tx^{(i)} - y^{(i,j)} x_k^j + \lambda \theta_k^{(j)} \bigg) \] -
For a user with parameters \(\theta\) and a movie with (learned) features \(x\) , predict a star rating of \(\theta^Tx\).
Low rank matrix factorization
主要讲解如何通过向量化的形式实现协同过滤算法，同时也讲解了如何基于学习到的特征进行产品推荐。
Collaborative filtering
对于5部电影4个用户组成的数据集，我们可以采用一个5行4列的矩阵\(Y\)进行表示。
矩阵\(Y\)以及预测评分的对应关系如下：
因此，我们可以同样把电影内容特征值用矩阵表示为\(X = \begin{bmatrix} (x^{(1)})^T \\ (x^{(2)})^T \\ \vdots \\ (x^{(n_m)})^T \end{bmatrix}\)，用户偏好用矩阵表示为\(\Theta = \begin{bmatrix} (\theta^{(1)})^T \\ (\theta^{(2)})^T \\ \vdots \\ (\theta^{(n_u)})^T \end{bmatrix}\)，那么预测得分则表示为\(X\Theta^T\)。
由于预测得分的矩阵在线性代数中是一个低秩矩阵，所以协同过滤算法也称为低秩矩阵分解（Low rank matrix factorization）。
Finding related movies
对于每个产品（电影）\(i\)，都学习到一个特征向量\(x^{(i)} \in \R^n\)，那么我们如何找到和电影\(i\)相关的电影\(j\)呢？
我们只需要计算电影\(i\)的特征向量\(x^{(i)}\)和电影\(j\)的特征向量\(x^{(j)}\)之间的距离\(\| x^{(i)} - x^{(j)}\|\)，如果距离小，则意味着两者比较相似。那么我们就能够以此找到和电影\(i\)相似的电影，推荐给用户即可。
Implementational detail: Mean normalization
本节课主要讲解了在实现协同过滤算法过程中的一个细节——均值归一化。
Users who have not rated any movies
对于一个没有对任何电影进行评分的用户，直接采用协调过滤算法我们会得到用户偏好参数\(\theta = 0\)，那么对于每部电影的评分也会是\(\theta^Tx=0\)，也就是我们没办法对该用户推荐任何电影。
为了避免这种情况，我们可以对数据进行均值归一化处理。
Mean Normalization
对于原始矩阵\(Y\)，我们可以求出每一步电影的平均得分构成的向量\(\mu\)，然后把\(Y\)减去\(\mu\)作为新的数据集\(Y\)。
对于用户\(i\)，电影\(j\)，预测评分为：\((\theta^{(j)})^Tx^{(i)} + \mu_i\)。
这样对于没有给任何电影评分的用户，新模型就会认为他给每部电影的评分都是该电影的平均分。
当然，理论上这种思想还可以应用在没有用户评分的电影上，但是实际上对于没有用户评分的电影，可能我们根本就不应该将其推荐给用户。所以比起没有评分的电影，一般更关心没有评分的用户。