这篇文章跟大家分享一下Machine Learning的学习笔记: 20-推荐系统(Recommender Systems)。
为什么学习推荐系统
- 推荐系统是机器学习中的一个重要的应用。如果你考虑网站像亚马逊，或网飞公司或易趣，或iTunes Genius，有很多的网站或系统试图推荐新产品给用户。如，亚马逊推荐新书给你，网飞公司试图推荐新电影给你，等等。这些推荐系统，根据浏览你过去买过什么书，或过去评价过什么电影来判断。这些系统会带来很大一部分收入，比如为亚马逊和像网飞这样的公司。因此，对推荐系统性能的改善，将对这些企业的有实质性和直接的影响。
- 通过推荐系统，我们将领略一小部分特征学习的思想。对机器学习来说，特征是很重要的，你所选择的特征，将对你学习算法的性能有很大的影响。因此，在机器学习中有一种大思想，它针对一些问题(可能并不是所有的问题)，有些现有的算法可以为你自动学习一套好的特征。
问题形式化
我们从一个例子开始定义推荐系统的问题。
假使我们是一个电影供应商，我们有 5 部电影和 4 个用户，我们要求用户为电影打分。
前三部电影是爱情片，后两部则是动作片，我们可以看出Alice和Bob似乎更倾向与爱情片， 而 Carol 和 Dave 似乎更倾向与动作片。并且没有一个用户给所有的电影都打过分。我们希望构建一个算法来预测他们每个人可能会给他们没看过的电影打多少分，并以此作为推荐的依据。
下面引入一些标记：
- \(n_u\)代表用户的数量
- \(n_m\)代表电影的数量
- \(r(i,j)\) 如果用户\(j\)给电影\(i\)评过分则\(r(i,j)=1\)
- \(y^{(i,j)}\)代表用户\(j\)给电影\(i\)的评分
- \(m_j\)代表用户\(j\)评过分的电影的总数
基于内容的推荐系统
在我们的例子中，我们可以假设每部电影都有两个特征，如\(x_1\)代表电影的浪漫程度，\(x_2\)代表电影的动作程度。
则每部电影都有一个特征向量，如\(x^{(1)}\)是第一部电影的特征向量为[0.9 0]。
下面我们要基于这些特征来构建一个推荐系统算法。 假设我们采用线性回归模型，我们可以针对每一个用户都训练一个线性回归模型，如\(\theta^{(1)}\)是第一个用户的模型的参数。 于是我们有：
- \(\theta^{(j)}\)：用户\(j\)的参数向量
- \(x^{(i)}\)：电影\(i\)的特征向量
- 对于用户\(j\)和电影\(i\)，我们的预测评分为\((\theta^{(j)})^Tx^{(i)}\)
代价函数
$$
J(\theta^{(j)})=\frac{1}{2}\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2+\frac{\lambda}{2}\sum_{k=1}^n(\theta_k^{(j)})^2
$$
其中\(i:r(i,j)=1\)表示我们只计算那些用户\(j\)评过分的电影。在一般的线性回归模型中，误差项和正则项应该都是乘以\(\frac{1}{2m}\)，在这里我们将m去掉。并且我们不对方差项\(\theta_0\)进行正则化处理。
上面的代价函数只是针对一个用户的，为了学习所有用户，我们将所有用户的代价函数求和：
$$
J(\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
$$
梯度下降求解公式
如果我们要用梯度下降法来求解最优解，我们计算代价函数的偏导数后得到梯度下降的更新公式如下：
for \(k=0\):
$$
\theta_k^{(j)}:=\theta_k^{(j)}-\alpha\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_k^{(i)}
$$
for \(k \neq 0\):
$$
\theta_k^{(j)}:=\theta_k^{(j)}-\alpha(\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_k^{(i)} + \lambda\theta_k^{(j)})
$$
协同过滤
在之前的基于内容的推荐系统中，对于每一部电影，我们都掌握了可用的特征，使用这些特征训练出了每一个用户的参数。相反地，如果我们拥有用户的参数，我们可以学习得出电影的特征。
但是如果我们既没有用户的参数，也没有电影的特征，这两种方法都不可行了。协同过滤算法可以同时学习这两者。我们的优化目标便改为同时针对\(x\)和\(\theta\)进行。
$$
J(x^{(1)},…,x^{(n_m)},\theta^{(1)},…,\theta^{(n_u)}) = \frac{1}{2}\sum_{j=1}^{n_u}\sum_{(i,j):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^{(i)})^2+\frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^n(\theta_k^{(j)})^2
$$
对代价函数求偏导数的结果如下：
$$
x_k^{(i)}:=x_k^{(i)}-\alpha(\sum_{j:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})\theta_k^{(i)} + \lambda x_k^{(j)})
$$
$$
\theta_k^{(j)}:=\theta_k^{(j)}-\alpha(\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})x_k^{(i)} + \lambda\theta_k^{(j)})
$$
协同过滤算法使用步骤如下：
- 初始\(x^{(1)},…,x^{(n_m),\theta^{(1)},…,\theta^{(n_u)}\)为一些小的随机值
- 使用梯度下降算法最小化代价函数
- 在训练完算法后，我们预测\((\theta^{(j)})^Tx^{(i)}\)为用户\(j\)给电影\(i\)的评分
向量化：低秩矩阵分解
这里将会讲到有关协同过滤算法的向量化实现，以及说说有关该算法你可以做的其他事情，例如：
- 当给出一件产品时，你能否找到与之相关的其它产品。
- 一位用户最近看上一件产品，有没有其它相关的产品，你可以推荐给他。
向量化
我们有关于五部电影的数据集，我将要做的是，将这些用户的电影评分，进行分组并存到一个矩阵中。
我们有五部电影，以及四位用户，那么 这个矩阵Y就是一个5行4列的矩阵，它将这些电影的用户评分数据都存在矩阵里：
使用协同过滤算法，我们就可以找到特征向量X，以及参数\(\Theta\)。从而，推导出预测的评分\(X\Theta^T\)
找到相似产品
当用户在看某部电影 的时候，如果你想找5部与电影非常相似的电影，为了能给用户推荐5部新电影，你需要做的是找出电影\(j\)与我们要找的电影\(i\)的距离最小，这样你就能给你的用户推荐几部不同的电影了。
均值归一化
让我们来看下面的用户评分数据：
如果我们新增一个用户 Eve，并且 Eve 没有为任何电影评分，那么我们以什么为依据为Eve推荐电影呢？
我们首先需要对结果 矩阵进行均值归一化处理，将每一个用户对某一部电影的评分减去所有用户对该电影评分的平均值：
然后我们利用这个新的Y矩阵来训练算法。 如果我们要用新训练出的算法来预测评分，则需要将平均值重新加回去，预测\((\theta^{(j)})^Tx^{(i)}+\mu_i\)，对于Eve，我们的新模型会认为她给每部电影的评分都是该电影的平均分。
