在之前的BLOG中,我们学习了一种简单易用的基于内容的推荐系统算法,但上述算法也存在着一些局限性。所以这篇BLOG,就让我们来看一种更全能的推荐系统算法——协同过滤算法(collaborative filtering)吧!

协同过滤

说起协同过滤算法,有一个值得一提的特点,那就是它能实现对特征的学习。也就是说这种算法能够自行学习所要使用的特征。

我们还是通过例子来说明吧。对于我们之前的例子,按照之前的方法,我们需要为每一部电影评估浪漫指数是多少,动作指数是多少。听起来好像轻而易举,但仔细想一下就知道这样做难度很大,也很花费时间和金钱来请人专门进行评估。那么我们怎样才能得到这些特征呢?

让我们转移一下问题,假如我们有某一个数据集,我们并不知道每一部电影特征的值是多少,于是我把所有的问题都打上问号:

PM20.png

现在我们稍稍改变一下这个假设,假设我们采访了每一位用户而且得知了每一位用户是否喜欢爱情电影或动作电影,这样 Alice 就有了对应的参数 θ(1),Bob 的是 θ(2),Carol 的是 θ(3),Dave 的是 θ(4):

PM8.png

假如 Alice 告诉我们她十分喜欢爱情电影,于是 Alice 的特征 x1 对应的值就是5;假设 Alice 告诉我们她非常不喜欢动作电影,于是 x2 就是 0,别忘了我们仍然有在这里等于0 的 x0。于是某种程度上我们就可以着眼于用户,看看任意的用户 j 对应的 θ(j) ,这样就明确地告诉了我们他们对不同题材电影的喜欢程度。如果我们能够从用户那里得到这些 θ 参考值,那么我们理论上就能推测出每部电影的 x1 以及 x2 的值。

我们来看上面例子,假如我们看第一部电影——《爱到最后》, 假设我们不知道这部电影的主要内容但我们知道 Alice 喜欢这部电影, Bob 喜欢这部电影但 Carol 和 Dave 不喜欢它,那么我们能推断出什么呢?我们从之前的每个人的特征向量知道了 Alice 和 Bob 喜欢爱情电影,因为他们都在这里评了 5 分,然而 Carol 和 Dave 不喜欢爱情电影但喜欢动作电影;同时由于我们知道 Alice 和 Bob 喜欢第一部电影而 Carol 和 Dave 不喜欢它,我们就可以推断这可能是一部爱情片而不太可能是动作片。

这个例子在数学上可以某种程度的简化,对于第一部电影,我们不知道他的各种成分的特征向量 x(1),但我们知道每个人对不同类型电影的喜好程度 θ 。通过 Alice 的评分值知道 θ(1)^T * x(1) ≈ 5;也知道 θ(2)^T * x(2) ≈ 5,同样地对于Carol 的评分θ(3)^T * x(3) ≈ 0 ;最后θ(4)^T * x(4) ≈ 0。由此可知 x(1) 应该用 [1 1.0 0.0] 这个向量表示,第一个 1 是 x0 截距项恒等于1,第二项是爱情电影的成分,第三项是动作电影的成分。这样才能得出 Alice Bob Carol 和 Dave 四个人对电影评分的结果。由此及之我们可以继续列举试着弄明白其他电影的合理特征。

让我们将这一学习问题标准化到任意特征 x(i),假设我们的用户告诉了我们的偏好 θ(1) 到 θ(nu) ,而我们想知道 电影 i 的特征向量 x(i) 我们能做的是列出以下的最优化的问题:

PM9.png

所以我们的最小化目标还是最小化我们预测用户的评分和真实评分的平方误差,我们要选择特征 x(i) 使得我们预测的用户 j 对该电影 i 评分的预测值评分值跟我们从用户 j 处实际得到的评分值不会相差太远。和之前一样,我们可以在最后加上一个正则化项来防止特征的数值变得过大。这就是我们如何从一部特定的电影中学习到特征的方法。但我们要做的是学习出所有电影的所有特征,所以我现在要做的是在此加上另外的一个求和,我要对所有的电影的代价函数进行求和然后最小化整个这个目标函数:

PM10.png

如果我们将上式最小化,我们就应该能得到所有电影的一系列合理的特征。接着我们把上一篇BLOG视频讨论的基于内容的推荐算法和我们刚刚讲过的算法合在一起:

PM11.png

上一篇BLOG我们讲的是上面那条式子:如果我们有一系列对电影的评分,我们就根据不同电影的特征 x 来得到用户对不同类型电影的喜好参数向量 θ ;而这篇BLOG中讲的是如果用户愿意为我们提供参数向量 θ ,那么我们就可以为不同的电影估计特征 x 。这有点像鸡和蛋的问题,到底先有鸡还是先有蛋?就是说如果我们能知道 θ 就能学习到 x 如果我们知道 x 也会学出 θ 。

而这样一来我们能做的就是在算法开始时随机出 θ 的值,接着基于我们一开始随机出的 θ 的值,我们计算出最优的 x 值,再针对这个 x 值计算出最优的 θ值……我们可以以此继续迭代,不停重复优化θ x θ x θ……如果我们这样做的话,我们的算法将会收敛到一组合理的电影的特征以及一组对合理的对不同用户参数的估计,这就是基本的协同过滤算法。这实际并不是最后我们将要使用的算法,在下一部分中,我们将改进这个算法让其在计算时更为高效。但是这一部分希望能让你基本了解如何构建一个协同过滤算法的大致思想。

协同过滤算法

我们回顾一些之前谈到几个概念,首先如果我们拿到表示电影的特征值,我们就可以使用这些资料去获得用户喜好相关的参数数据;而如果给你用户的参数数据我们可以使用这些资料去获得电影的特征值:

PM11.png

在这一部分我们将会使用这些概念合并成协同过滤算法 (Collaborative Filtering Algorithm)。我们之前做过的事情其中之一是假如我们有了电影的特征,我们就可以解出上面这个最小化问题以找到参数 θ;然后我们也知道了如果我们拥有参数 θ ,我们同样也可以用该参数去计算出特征 x ,所以我们可以做的就是不停地重复这些计算。或许是随机地初始化这些参数然后解出 θ 解出 x 解出 θ 解出 x……但这看起来不那么高效。

实际上呢存在一个更有效率的算法,让我们不再需要再这样不停地计算 x 和 θ 而是能够将 x 和 θ 同时计算出来,下面就是这种算法:我们所要做的是将这两个优化目标函数给合为一个:

PM12.png

所以我要来定义这个新的优化目标函数 J 它依然是一个代价函数,且是特征 x 和参数 θ 的函数,它其实就是上面那两个优化目标函数的累加和,让我们来看看这个式子到底在做什么。第一个求和运算是所有被用户评分过的电影计算出我们的估计值和真实值之间的平方误差,而后面两项则分别是 x 和 θ 的正则化项。这个式子有一个很有趣的特性,如果我们假设 x 为常数并关于 θ 优化的话,你其实就是在计算下图中的下面那个式子。反过来也一样如果你把 θ 作为常量然后关于 x 求 J 的最小值的话,那就与上面的式子相等:

PM11.png

所以我们的代价函数是一个既关于 x 也关于 θ 的函数,这和前面的算法之间唯一的不同是不需要反复计算关于 θ 最小化然后关于 x 最小化然后再关于 θ 最小化再关于 x 最小化... 在新版本里,我们不需要不断地在 x 和 θ 这两个参数之间不停折腾,我们所要做的是将这两组参数同时化简。

一件值得一提事是当我们以这样的方法学习特征量时之前我们所使用的增加一个特征 x0 恒等于 1 的操作是必须去掉的,所以这些我们将学习的特征量 x 都是 n 维实数,而先前我们所有的特征值 x 是 n+1 维,因为我们包括了截距 x0,现在删除掉 x0 后就只会有 n 维的 x。同样地因为参数 θ 是在同一个维度上所以 θ 也是 n 维的,因为如果没有 x0 那么 θ0 也不再需要。我们将这个前提移除的理由是因为我们现在是在学习所有的特征对吧?所以我们没有必要去将这个等于一的特征值固定死,因为如果算法真的需要一个特征永远为 1 ,它可以选择靠自己去获得 1 这个数值,比如它可以将特征值 x1 设为 1,所以没有必要去将 1 这个特征定死,这样算法有了灵活性去自行学习的途径。

让我们对协同过滤算法进行一下总结。首先我们将会把 x 和 θ 初始为小的随机值,这有点像神经网络训练,我们也是将所有神经网路的参数用小的随机数值来初始化。接下来 我们要用梯度下降或者某些其他的高级优化算法把之前那个长长的代价函数最小化。所以如果我们求导的话就会发现梯度下降法写出来的更新式是这样的:

PM13.png

上面式子的更新减去的是关于特征值 x(i)k 的偏微分乘以系数α,下面这是参数 θ 对于的偏微分以系数α,记得我们还要将所有的参数 θ 和 x 做正则化。最后计算完成后我们会得到一些参数 θ 以及每部电影的特征 x ,我们就可以通过θ^T * x预测用户对未评分电影的评分。这就是协同过滤算法的全部,如果我们使用这个算法,我们可以得到一个可以同时学习几乎所有电影的特征和所有用户参数并作出较为准确预测的强大算法。在下一部分我们将会继续看看如何让优化这个算法。

低秩矩阵分解

在之前的部分我们具体学习了协同过滤算法的实现原理,在这一部分中我们将会学习有关该算法的向量化实现以及有关该算法我们可以做的其他事情。

我们的协同过滤算法一般用来干什么呢?举一个例子其中一个可以做得是当给出一件产品时,我们能否找到与之相关的其它产品?我们不妨再举一个例子,接入一位用户最近看上一件产品,有没有其它相关的产品我们可以推荐给他?好的让我们看看我们能做什么,我们将要做的是实现一种选择的方法,写出协同过滤算法的预测情况。推荐电影就是一个很好的例子。

首先我们有关于五部电影的数据集,我们将要做的是将这些用户的电影评分进行分组并存到一个矩阵中:

PM14.png

看这里我们有五部电影以及四位用户,那么这个矩阵 Y 就是一个5行4列的矩阵,我们将这些电影的用户评分数据都存在矩阵里,包括问号标注出的将这些数据分组到这个矩阵中 当然。矩阵中的这些元素在(i, j)位置的元素其实是我们先前写的 y(i, j) 代表用户 j 对电影 i 给出的评分。由这个矩阵 Y 中所有的评分数据就可以选择用另一种方法写出我们对于所有的预测评分来。具体来说如果我们看到某位用户预测某部电影的评分,下面这个公式就是用户 j 对电影 i 的预测评分:

PM15.png

如果我们有预测评分矩阵——于 θ(j)^Tx(i),我们就可以定义出误差。我们给出预测评分矩阵一个更简化的向量化的方法,具体来说如果我定义这个矩阵 X 和矩阵 Θ :

PM16.png

这就会有点类似我们先前在线性回归里面的矩阵 x(1)^T x(2)^T一直到 x(nm)^T。我会把这些所有有关电影的特征 按行堆叠起成矩阵的每一行来形成左边这个 X 矩阵。然后我们要做的是定义一个 Θ 矩阵,接下来我要做的是将每一位用户的参数向量 θ(j)^T 像右边这样按行堆叠起来组成这个大写Θ矩阵。在这个矩阵里我们有 nu 个参数向量像这样按行堆叠起来。现在我们已经给出了针对 X 矩阵以及 Θ 矩阵的定义,为了能有一个向量化的方法以计算,我们的预测矩阵可以写成 Predict = X * Θ^T。我们接着就可以用梯度下降或者其他算法求出 X 和 Θ 来以得到我们的Predict矩阵。

这就得出了一个向量化的方法以计算这个预测矩阵。顺带一提,我们用的这个协同过滤算法还有另外一个名字——低秩矩阵分解。这是因为这个矩阵Predict = X * Θ^T具有低秩属性,所以我们的预测矩阵Predict = X * Θ^T也被叫做低秩矩阵,我们的算法也被叫做低秩分解。

最后在运行了协同过滤算法后仍有一些存在疑惑的事情,比如对于每一个产品好比每一部电影,我们有特征向量x(i) 那么我们就会项知道我们学习出来的 x(i) 的每一项具体代表什么。如果我们运行这个算法电影的所有特征将会完美地捕获,但到底什么是造成某些用户喜欢某些电影以及是什么造成了这些电影其它不同的电影呢?也许我们可以猜测爱情指数是x1,动作指数是x2……但实际中对这些参数提出一个人类能理解的解释实际上是很困难的,并且在实践中这些特征是很难以可视化的,也很难计算出这些特征到底是什么。通常来说特征学习对于捕获哪些是电影的重要或显著的属性。是很有意义的也正是这样才有了你对某些电影的喜欢或不喜欢。这也是算法的神奇之处,它可以自动捕捉最重要的n个特征进行学习,而我们人类确难以理解这n个特征具体代表什么。

我们再来考虑另一个问题,假如有一位用户正在浏览一些电影,当他们看完电影 i 时,我们应该推荐哪一部类似的电影给他呢?或者说某人最近买了一部电影,我们将如何找到她最有可能在下一次购买的电影并推荐给他呢?换句话说我们怎么找到与电影 i 最接近的一部电影 j ?现在既然我们已经对特征参数向量进行了学习,那么我们就会有一个很方便的方法来度量两部电影之间的相似性。

换一种解释,假如电影i有一个特征向量x(i),我们是否能找到一部不同的电影 j,保证两部电影的特征向量之间的距离 |x(i) - x(j)| 最小?如果我们能找到满足最小距离的 j ,那就很有力地表明电影 i 和电影 j 在某种程度上有相似,至少在某种意义上某些人喜欢电影 i 或许更有可能也对电影 j 感兴趣。这也是我们参数向量化的意义之一。

所以如果当用户在看某部电影 i 的时候,假如我们想找 5部与电影 i 非常相似的电影,我们需要做的是遍历所有电影,计算出它们的特征 x 与电影 i 的距离,接着取最小的五个推送给用户。

通过以上的方法,希望你能知道如何进行一个向量化的计算来对所有的用户和所有的电影进行评分计算,同时希望你也能掌握通过学习特征参数来找到相关电影和产品的方法。

均值归一化

在上面的部分我们几乎已经讲解完了协同过滤算法的所有要点,这一部分我想分享最后一点实现过程中的细节,这一点就是均值归一化,有时它可以让算法运行得更好。

为了了解均值归一化这个想法的动机,我们考虑这样一个例子。在上一个例子中我们有四个用户 Alice Bob Carol 和 Dave,我现在加上了第五个用户 Eve 她没有给任何电影评分:

PM17.png

我们来看看协同过滤算法会对这个用户做什么,假如说 n = 2,所以我们要学习含有两个特征变量的参数向量θ(5)。如果我们看这个优化目标函数的第一项,用户 Eve 没给任何电影打过分,所以对用户 Eve 来说没有电影满足 r(i,j)=1 这个条件所以这第一项为 0 ,所以影响 θ(5) 值的唯一项是后面的正则化项,这就是说我们想选一个向量 θ(5) 使得最后的正则化项尽可能地小,换句话说我们想要最小化式子 λ/2[(θ(5)1)^2+(θ(5)2)^2]。当然如果我们的目标是最小化这一项那么我们最终得到的就会是 θ(5)=[0;0] 因为正则化项会让我们的参数接近 0。所以当我们要预测用户 5 会如何给电影打分时,我们对对任意电影 i 我们有预测得分为 θ(5)^T * x(i) ,其结果都会等于 0,因为对任意x值 θ(5) 都是 0。因此我们得到的结果是我们会预测 Eve 给所有电影的评分都是零星,但是这个结果看起来没什么用吧——如果我们预测 Eve 会给所有电影零星的话我们还是没有任何好方法来把电影推荐给她的,因为我们预测结果是所有这些电影都会被 Eve 给出一样的评分,所以没有一部电影拥有高一点儿的预测评分让我们能推荐给她,所以这不太好。

均值归一化的想法可以让我们解决这个问题,下面我们来看看它是如果工作的。和以前一样我们把所有评分放到矩阵 Y 里,全部是问号的这列对应的是 Eve 没有给任何电影评分。现在要实现均值归一化,我们要做的就是计算每个电影所得评分的均值并且把它们存在一个向量中,我们称这个向量为 µ:

PM18.png

接着我们要做的就要把所有的电影评分减去平均评分,所以这第一个元素 5 我们要减去 2.5 等于 2.5 ,第二个元素 5 减去2.5 得到2.5……换句话说我们要做的就是把我的电影评分矩阵也就是这个Y矩阵的每一行的每个元素都减去那个电影的平均评分的对应行,以使得每个电影的平均评分都为零:

PM19.png

接下来我们要做的就是对这个处理后的评分数据集使用协同过滤算法,我们把这个处理后的数据当做我的数据集来学习得到我的参数 θ(j) 和特征变量 x(i)。当我想要做 电影评分预测时我们要做的步骤如下对用户j对电影i的评分我要预测它为 θ(j)^T * x(i) + µ(i)。 其中 x 和 θ 都是均值归一化的数据集中学习出的参数,但是因为我已经对数据集减去了均值所以为了给电影 i 预测评分,我们要把这个均值加回来,所以我要再加回 µ(i) 来得到我们最终的预测值。

在这样的处理下既视 Eve 从来没有给任何电影打分,即使我们学习到他的 θ 参数仍然还是会等于 [0, 0],但wom1预测 Eve 的评分是 θ(5)^T * x(i) + µ(i),即使 θ(5) = 0的话,算式的前一部分θ(5)^T * x(i)恒等于 0 ,但我们对电影 i 的预测评分不会是 0 而会预测为 µi。这实际上是说得通的对于电影 1 我们会预测 Eve 对它的评分是2.5,对于电影 2 我们会预测 Eve 给它2.5星,对于电影 3 我们会预测 Eve 给它2星………它的意思是如果 Eve 没给任何电影评分,我们就对这个新用户 Eve 就是一无所知,我们要做的就是去看看大部分用户的评价比较大多数人都是大众口味,所以我们要关注的就是这些电影所得的平均评分。

最后再补充一下,在这一部分中我们谈到了均值归一化,我们归一化矩阵 Y 使得每行的均值都是 0。如果有些电影是没有评分的这个情形类似于有的用户没有给任何电影评分的情况,但是如果我们有些电影是没有用户进行评分的,我们耶可以尝试这个算法的其他版本同样地可以对不同的列进行归一化使得它们的均值为 0 而不是把行均值归一化为 0。虽说这个可能不太重要因为如果我们真的有个电影没有评分,我们就不该把这个电影推荐给任何人,但问题还是存在的我们也可以尝试去解决。

这就是可以说是作为协同过滤算法的预处理步骤均值归一化的实现,根据你的数据集的不同它可能有时会让实现的算法表现得好一点儿。

结语

通过这篇BLOG,相信你已经完全了解了协同过滤算法。我们的推荐算法也告一段落了。接下来的BLOG我们还将学习大型机器学习中的一些处理技巧。最后希望你喜欢这篇BLOG!

Last modification:March 4th, 2021 at 03:49 am
If you think my article is useful to you, please feel free to appreciate