Machine Learning-推荐系统(Recommender Systems)

点击量:370

本文覆盖Coursera Machine Learning Week 9的内容。这篇文章看似公式很复杂,但实质上内容还是比较简单的,就是基于最基本的线性回归,其实很容易理解的。

一、问题描述

推荐系统是机器学习在工业界的一个非常重要的应用,虽然它在学术界并不怎么被重视。今天你看到的大部分网站里使用的推荐系统,比如Amazon,淘宝,豆瓣等,它们基本都采用了机器学习技术,今天我们花点时间总结下推荐系统的相关知识。
例子:预测电影评分
假设我们有一些数据,它包含了不同用户对不同电影的评分情况(0-5分),其中?表示该用户没有看过这部电影,这些数据用一个表格表示如下:

Movie Alice(1) Bob(2) Carol(3) Dave(4)
Love at last 5 5 0 0
Romance forever 5 ? ? 0
Cute puppies of love ? 4 0 ?
Nonstop car chases 0 0 5 4
Swards vs. karate 0 0 5 ?

那么我们的问题就变成:需要找到这样一个算法,它能够自动地帮我们把表格中缺失的数值(也就是打问号那一项)算出来,然后根据数值的大小向用户推荐电影。这就是推荐系统的正式表述,这里介绍两种算法:基于内容的推荐(Content Based Recommendations)和协同过滤(Collaborative Filtering)。

二、基于内容的推荐(Content Based Recommendations)

所谓基于内容的推荐意思就是我们已经知道每一部电影大致是什么内容,比如《Love at last》这部电影是爱情片,而《Swards vs. karate》很明显是一部动作片。因此在上一个表格的基础上,我们引入两个特征变量 \(x_{1}\) 和 \(x_{2}\) 分别表示一部电影爱情(romance)和动作(action)的程度(取值范围:0-1.0)。

Movie \(x_{1}\)(romance) \(x_{2}\)(action) Alice(1) Bob(2) Carol(3) Dave(4)
Love at last 0.9 0 5 5 0 0
Romance forever 1.0 0.01 5 ? ? 0
Cute puppies of love 0.99 0 ? 4 0 ?
Nonstop car chases 0.1 1.0 0 0 5 4
Swards vs. karate 0 0.9 0 0 5 ?

为了后面能够准确地描述这个问题,我们定义了如下一些变量:

  • \(n = \) 电影的特征数
  • \(n_{u} = \) 用户数量
  • \(n_{m} = \) 电影数量
  • \(r(i,j) = 1 \) 如果用户评价了该电影
  • \(y^{(i,j)} = \) 用户\(j\)对电影\(i\)的评分(只有当\(r(i,j) = 1\)时才会有值)
  • \(\theta^{(j)}\)用户\(j\)的参数向量(parameter vector)
  • \(x^{(j)}\)电影\(i\)的特征向量(feature vector)
  • \(m^{(j)}\) 用户\(j\)评价过的电影数量

这其实是一个很简单、很基础的线性回归问题,对于电影《Love at last》而言它的特征向量就是:\(x^{(1)}=\begin{bmatrix}
x_{0}\
x_{1}\
x_{2}
\end{bmatrix}=\begin{bmatrix}
1\
0.9\
0
\end{bmatrix}\),而每个用户看过的每一部电影就是一条样本数据,我们通过对这些样本数据的学习得出这个用户对两个特征romance和action的偏爱程度(也就是参数\(\theta\)),这样就能预测该用户对下一部电影的评分了。严谨地,我们有:对于每一个用户\(j\),学习一个参数\(\theta^{(j)} \in \mathbb{R}^{n+1}\),然后预测用户\(j\),对于电影\(i\)的评分\((\theta^{(j)})^{T}x^{(i)}\)。
那么对于用户\(j\)而言,要习得参数\(\theta^{(j)}\),那么他的目标函数就是:

$$\min_{\theta^{(j)}}\frac{1}{2}\sum_{i:r(i,j)=1}((\theta^{(j)})^{T}x^{(i)} – y^{(i,j)})^{2} + \frac{\lambda}{2}\sum_{k=1}^{n}(\theta_{k}^{(j)})^{2}$$

其中,\(i:r(i,j)=1\)表示的意思是只选取\(r(i,j)=1\)时的\(i\),也就是只选取用户\(j\)评价过的电影\(i\)。然而我们的系统内肯定不止一个用户,我们并不想单独的计算每个用户的目标函数(因为单个用户的数据量太小,可能会导致预测不准确),而是想把所有的用户数据当成一个整体来求得目标函数,这样会使得预测的结果更准确。于是,要习得每个用户的参数:\(\theta^{(1)},\theta^{(2)},…,\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)})^{T}x^{(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)})^{T}x^{(i)} – y^{(i,j)})x_{k}^{(i)}
\ (for \ k = 0 ) \\
\theta_{k}^{(j)}:= \theta_{k}^{(j)} – \alpha \left ( \sum_{i:r(i,j)=1}((\theta^{(j)})^{T}x^{(i)} – y^{(i,j)})x_{k}^{(i)} + \lambda\theta_{k}^{(j)} \right )\ (for \ k \neq 0 )
$$

三、协同过滤(Collaborative Filtering)

上一部分我们在知道了电影内容的前提下,预测用户对某一部电影的喜欢程度;而有时候我们并不知道某一部电影的成分是什么,实际上我们可以根据用户的兴趣爱好以及对电影的评分记录来预测某一部电影的主要成分是什么。说白了,基于内容的推荐算法就是给定了每一部的电影特征值\(x^{(1)},…,x^{(n_{m})}\)去求出用户对不同特征的偏爱程度:\(\theta^{(1)},…,\theta^{(n_{u})}\);而另一种算法就是给定了用户对不同特征的偏爱程度:\(\theta^{(1)},…,\theta^{(n_{u})}\)去算出某一部电影的特征值\(x^{(1)},…,x^{(n_{m})}\),这两个恰好是一个相反的计算过程。对于第二种算法他的目标函数是:
给定\(\theta^{(1)},…,\theta^{(n_{u})}\),要习得\(x^{(i)}\),那么它的目标函数为:

$$\min_{x^{(i)}}\frac{1}{2}\sum_{j:r(i,j)=1}((\theta^{(j)})^{T}x^{(i)} – y^{(i,j)})^{2} + \frac{\lambda}{2}\sum_{k=1}^{n}(x_{k}^{(i)})^{2}$$
给定\(\theta^{(1)},…,\theta^{(n_{u})}\),要习得\(x^{(i)},…,x^{(n_{m})}\),那么它最终的目标函数为:

$$\min_{x^{(1)},…,x^{(n_{m})}}\frac{1}{2}\sum_{i=1}^{n_{m}}\sum_{j:r(i,j)=1}((\theta^{(j)})^{T}x^{(i)} – y^{(i,j)})^{2} + \frac{\lambda}{2}\sum_{i=1}^{n_{m}}\sum_{k=1}^{n}(x_{k}^{(i)})^{2}
$$
那所谓的协同过滤算法就是把这两个算法结合起来,交替计算\(x\)和\(\theta\)的值,比如我们随机初始化一个变量\(\theta\),然后计算得到\(x\),再通过\(x\)得到一个更好的\(\theta\)。于是如此往复,\(\theta \rightarrow x \rightarrow \theta \rightarrow x…\)最终得到理想的拟合结果。具体地,
给定\(x^{(1)},…,x^{(n_{m})}\),要习得\(\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)})^{T}x^{(i)} – y^{(i,j)})^{2} + \frac{\lambda}{2}\sum_{j=1}^{n_{u}}\sum_{k=1}^{n}(\theta_{k}^{(j)})^{2}$$

给定\(\theta^{(1)},…,\theta^{(n_{u})}\),要习得\(x^{(1)},…,x^{(n_{m})}\),他的目标函数为:
$$\min_{x^{(1)},…,x^{(n_{m})}}\frac{1}{2}\sum_{i=1}^{n_{m}}\sum_{j:r(i,j)=1}((\theta^{(j)})^{T}x^{(i)} – y^{(i,j)})^{2} + \frac{\lambda}{2}\sum_{i=1}^{n_{m}}\sum_{k=1}^{n}(x_{k}^{(i)})^{2}
$$
然而这种做法效率并不高,因为要不断往复计算\(x\)和\(\theta\),很麻烦。实际上我们可以同时计算\(x\)和\(\theta\)的值,把两个分开求的目标函数整合成一个目标函数:
$$J(x^{(1)},…,x^{(n_{m})},\theta^{(1)},…,\theta^{(n_{u})}) = \ \frac{1}{2}\sum_{(i,j):r(i,j)=1}((\theta^{(j)})^{T}x^{(i)} – y^{(i,j)})^{2} + \frac{\lambda}{2}\sum_{j=1}^{n_{u}}\sum_{k=1}^{n}(\theta_{k}^{(j)})^{2} + \frac{\lambda}{2}\sum_{i=1}^{n_{m}}\sum_{k=1}^{n}(x_{k}^{(i)})^{2}$$
这里要注意的是\(x\)和\(\theta\)都是\(n\)维的:\(x^{(j)} \in \mathbb{R}^{n})、(\theta^{(j)} \in \mathbb{R}^{n} \),也就是说他们并没有截距项\(x_{0}\)和\(\theta_{0}\)。为什么呢?因为这两个参数是需要互相学习得到的,并不是固定已知的,所以不能写死成截距项的值。最终的系统过滤算法如下:
对\(x^{(1)},…,x^{(n_{m})},\theta^{(1)},…,\theta^{(n_{u})}\)随机初始化一些较小的值

使用梯度下降算法最小化代价函数\(J(x^{(1)},…,x^{(n_{m})},\theta^{(1)},…,\theta^{(n_{u})})\),对每一个\(j=1,…,n_{n},i=1,…,n_{m}\),同时计算:
$$
x_{k}^{(i)}:= x_{k}^{(i)} – \alpha \left ( \sum_{j:r(i,j)=1}((\theta^{(j)})^{T}x^{(i)} – y^{(i,j)})\theta_{k}^{(j)} + \lambda x_{k}^{(i)} \right ) \\
\theta_{k}^{(j)}:= \theta_{k}^{(j)} – \alpha \left ( \sum_{i:r(i,j)=1}((\theta^{(j)})^{T}x^{(i)} – y^{(i,j)})x_{k}^{(i)} + \lambda\theta_{k}^{(j)} \right )
$$
因为这里没有截距项,所以不需要考虑\(k=0\)的情况了,所有的参数都进行了正则化。
预测某一个用户对某一部电影的评分:使用该用户的参数\(\theta\)和电影的特征\(x\)计算\(\theta^{T}x\)即是该用户对该电影的评分

四、向量化

  • 低秩矩阵分解(Low Rank Matrix Factorization)
    我们可以把第一个表格里的内容转化成一个矩阵\(Y\)(每一行表示一部电影,每一列表示一个用户):
    $$Y=\begin{bmatrix}
    5 & 5 & 0 & 0\\
    5 & ? & ? & 0\\
    ? & 4 & 0 & ?\\
    0 & 0 & 5 & 4\\
    0 & 0 & 5 & 0
    \end{bmatrix}$$
    把参数(\theta)和特征变量(x)也都表示成向量的形式:
    $$X=\begin{bmatrix}
    —(x^{(1)})^{T}—\\
    —(x^{(2)})^{T}—\\
    …\\
    —(x^{(n_{m})})^{T}—
    \end{bmatrix}$$
    $$
    \Theta=\begin{bmatrix}
    —(\theta^{(1)})^{T}—\\
    —(\theta^{(2)})^{T}—\\
    …\\
    —(\theta^{(n_{u})})^{T}—
    \end{bmatrix}$$
    那么我们有:\(Y=\Theta^{T}X\),这种方法被称为:低秩矩阵分解(Low Rank Matrix Factorization)。

  • 如何找到相似电影
    比如用户刚刚看完了电影\(i\),我们的系统想找一部跟\(i\)类似的电影\(j\)推荐给用户,该如何做呢?
    很简单,对于候选影片中的每一部电影,分别计算他们与电影(i)的特征向量之间的距离:\(\left | x^{(i)} – x^{(j)} \right |\),然后选择距离最小的那个就是我们要找的电影\(j\)。

  • 均值化处理(Mean Normalization)
    现在假设我们的系统新增了一位用户Eve,她从来没有看过任何电影,于是我们有:
    $$Y=\begin{bmatrix}
    5 & 5 & 0 & 0 & ?\\
    5 & ? & ? & 0 & ?\\
    ? & 4 & 0 & ? & ?\\
    0 & 0 & 5 & 4 & ?\\
    0 & 0 & 5 & 0 & ?
    \end{bmatrix}$$
    最右边一列就是eve的数据。根据之前的算法可以算出来Eve的参数\(\theta=\begin{bmatrix}
    0\\
    0
    \end{bmatrix}\),对所有电影的评分都是0,这样就会导致这个算法对新用户而言是毫无意义的,因为系统不能向他推荐任何电影。我们可以通过均值化的方法解决这个问题,具体地,对于每一部电影(每一行)我们计算出所有用户对这部电影的平均分,得到:
    $$\mu=\begin{bmatrix}
    2.5\\
    2.5\\
    2\\
    2.25\\
    1.25
    \end{bmatrix}$$
    然后我们把原矩阵\(Y\)的每一项都减去他对应的平均值,得到:
    $$Y=\begin{bmatrix}
    2.5 & 2.5 & -2.5 & -2.5 & ?\\
    2.5 & ? & ? & -2.5 & ?\\
    ? & 2 & -2 & ? & ?\\
    -2.25 & -2.25 & 2.75 & 1.75 & ?\\
    -1.25 & -1.25 & 3.75 & -1.25 & ?
    \end{bmatrix}$$
    我们把这个矩阵里的值就当成是用户对电影的评分,计算出\(\theta\)和\(x\),然后我们只要在预测评分时加上平均值就能得到真实的评分了。具体地,对于用户\(j\)对电影\(i\)的评分预测,我们有:\((\theta^{(j)})^{T}(x^{(i)})+\mu_{i}\)。这样就能解决新用户对所有电影评分预测都是0的问题了,即如果某个用户没有看过这部电影,那么系统会把所有用户对这部电影的评分的平均值赋值给他。但也许这么做也没必要,因为用户啥电影都没看过,你怎么会知道他喜欢什么类型的电影呢?或许你根本不该向他推荐任何电影。

课后编程作业已经上传至本人github,如有需要可以参考,但请遵守课堂准则,不要抄袭。

发表评论

电子邮件地址不会被公开。 必填项已用*标注