经典机器学习系列(十一)【个性化推荐之协同过滤】

对推荐系统还没有直观理解的同学可以参考之前所写的文章：推荐系统与人工智能概述   协同过滤(Collaborative Filtering)是当前推荐系统最为流行的一种方法，就是说我们不只是基于内容进行推荐，我们还基于一些用户之间的协同行为去给用户做推荐，或者称之为个性化推荐。   推荐系统本身和信息检索( information retrieval)具有很强的相关性，甚至被认为是一种能力更强的信息检索，与信息检索不同的地方在于它没有信息检索里面所需要的关键词，更多的是使用用户之前的使用信息等等，所以你需要去猜用户到底喜欢什么东西。本质可以理解为信息检索问题，但是没有关键词。   在实际生活中也有很多例子，比如淘宝的推荐系统下面经常会有购买这些东西的人也购买了某某商品，还有头条推荐系统给你推送文章，这两者其实是有差异的。淘宝的客户端用户具有搜索功能，一旦搜索了说明是用户肯定感兴趣的东西；而头条就不太一定，头条只是接收用户一个单纯的反馈(点击或者不点击)，但是这种反馈可能不是很精准，比如你可能不是被文章所写的内容感兴趣，而是对图片、标题、作者等等这些信息感兴趣。

Personalized Recommendation

  还有一个叫个性化推荐(Personalized Recommendation)，这个行业的标杆：人物美国工程院院士、前雅虎副总裁Andrei Broder，同时首次提出了计算广告(Computational Advertising)的概念。我们做个性化推荐的时候往往会有两种方法(Methodologies)：  

• Method 1：用户喜欢什么item(项目、物品，指所有可能被推荐到的资源，比如电影、书)，我去给他推荐相似的这些item，比如喜欢漫威，我就给你推荐漫威的其他电影。
• Method 2：推荐给你与你行为相似的用户喜欢的东西。这种方法所推荐的item更广泛。比如搜Andrei Broder这个关键词的用户喜欢吃什么菜，从而发现大部分人喜欢吃印度菜，而总结出印度人搜他的文章比较多，进而推断出印度做计算广告的人应该蛮多。

  第一种方法更简单一些，第二种方法对用户行为数据要求更多，但在工业级的应用场景里面更加work一些，我们接下来主要说第二种方法，也就是Collaborative filtering，第一种方法Content-based filtering就比较老，几十年的算法，网上资料也多。

Collaborative filtering

  举个例子，如下图所示：  
  知道了部分user对于部分item的打分行为，如何来预测一个用户对于一个未知的item的打分行为呢？思考一下，如果是你对上述数据进行学习，你会对下图所示的这个问号框框预判几颗星呢？  
  简单看一下是会是高分还是低分呢？从user来看的话，Dave和George和Boris很像，因此给的会是低分；从item来看的话，这步电影的评分就比较偏低，就会给低分。所以不管是根据item还是user来看都是低分。

K Nearest Neighbor Algorithm (KNN)

  KNN算法是一个non-parametric的方法，它没有参数需要学习，每一个数据点对于它来说就是一个参数，它有一个hyperparameter $k$。   对于每个输入的样本$x$，在训练样本集合N k ( x ) N_{k}(x)Nk​(x)中寻找$k$个特征空间最近的样本。预测的话就是拿$k$个样本标签的平均作为预测结果：  
  如果是一个分类问题的话，那拿这个label做一个voting就可以了。   更加generalize的版本的KNN，我们是可以用每个样本的预测做平均做投票，但是每个样本都有权重。比如说离你这个输入样本 $x$ 越近，那权重就可能比较高一点，由此我们可以定义一个相似度函数(similarity function) s ( x , x i ) s(x,x_{i})s(x,xi​) ，这个相似度函数一方面可以把这$k$个样本选出来，另一方面基于相似度函数，可以做带有权重的label预测，如下公式所示：  
  这里最大的问题就是如何来选择hyperparameter $k$，如果你只在training set上面去选择能使得sum-of-squared error最小的$k$话，泛化能力就会不够，因此经常需要依据validation set上面的效果去选择 $k$。

基于User的KNN解决办法

  对于之前的那个问题，我们使用User-based kNN来尝试解决一下：  
  首先是寻找相似的用户，发现与 Boris 相似的用户有Dave和 George；之后我们做Rating Prediction，平均Dave和George对Love Actually电影的评分：1.5星。

• Basic user-based kNN algorithm
  • For each target user for recommendation
  1. Find similar users
  2. Based on similar users, recommend new items

Similarity between Users

  我们可以把上述图表关系表达为下图所示曲线图：  
  横轴表示items，纵轴表示rating，图中的曲线表示user。因此可以比较直观看出哪些用户之间比较像。从上图中选择三个user出来组成下图：  
  可以看出这三个user比较像，但是黄色曲线的用户打分普遍偏低，紫色用户打分普遍偏高。对于这种问题我们普遍使用Pearson Correlation的方法来做把mean和variance做normalization。   那我们数学上怎么来做用户之间的Similarity呢？其实也就是度量数据之间的相关性了，我们之前也有说过类似的知识点，在这里主要是采用如下两种方式：

• Cosine (angle)：

• Pearson Correlation：

 
  其中下标$m$表示电影，u a u_{a}ua​和u b u_{b}ub​表示用户$a$和用户$b$。   在预测的时候我们通常采用如下形式：  

基于Item的KNN解决办法

  user可以这么做，那么item当然也可以这么做。一般的做法是寻找到相似的item，然后基于这个相似的item来对item做预测：  
  衡量item a和item b之间的相关性可采用以下三种方式：  

• Cosine (angle)

• Adjusted Cosine

 
  这里是减去用户对各个电影打分的平均值，而不是item的平均值。  

• Pearson Correlation

 
  那能计算相关性了之后，我们需要做预测了。首先我们要做一个相关性的序列排序，选择排序分数最高的k个相似的item出来：  
  之后的话我们就可以去做预测了：  
  这里的x t , b x_{t, b}xt,b​不需要去做平均，因为这就是用户的打分习惯(这是用户本身的打分行为，偏高偏低都在里面)。

kNN based Methods Summary

  knn的方法非常直接并且可解释，并且是一个无参数的学习算法只有一个超参数$k$。但是算法的效率会成为一个问题，因为user和item数量特别多。

Matrix Factorization Techniques

  既然user和item的关系构成了一个矩阵，因此我们可以通过矩阵分解的方式将这个矩阵分解为两个低秩但是稠密的矩阵。  
 

• Koren, Yehuda, Robert Bell, and Chris Volinsky. “Matrix factorization techniques for recommender systems.”Computer42.8 (2009).

  因此每个user对应一个低维空间的稠密向量，每个item也同样对应一个低维空间的稠密向量。每个user和对应的item的那个rating就是由对位的user向量点乘对位的item向量。于是这个时候就变成了一个学习的算法：  
  user $u$在item $i$下的预测是一个user的向量p u p_{u}pu​与item的向量q i q_{i}qi​相乘得到：  
  由此我们可以通过梯度下降的方式进行学习，学习p u p_{u}pu​和q i q_{i}qi​该如何更新，其损失函数(Loss function)可定义为：  
  训练过程的目标函数(Training objective)引入L2正则化可得到如下公式：  
  对其求梯度可得   ​​

MF with Biases

  矩阵分解技术有一种变体，引入偏置项，user $u$在item $i$下的预测是一个user的向量p u p_{u}pu​与item的向量q i q_{i}qi​相乘再加上一些偏置项得到 (这个为什么会有一些偏置在上文KNN算法有提及)：  
  其中$\mu$为Global bias，b u b_{u}bu​为user bias，b i b_{i}bi​为item bias，p u T q i p_{u}^{T}q_{i}puT​qi​为user-item interaction。此时的训练目标函数表示为：  
 
  从梯度更新公式可以看出，上述的模型p u p_{u}pu​更新其实是拿q i q_{i}qi​的方向去更新p u p_{u}pu​，这个时候如果q i q_{i}qi​学习地不好的话，p u p_{u}pu​更新的方向也不对，q i q_{i}qi​同理也是一样。导致它的更新会处在一个非常动荡的阶段，导致它很容易掉入到局部最优。

进一步的扩展

  根据时间的不同，比如晚上做rating效果好一点这样，还有比如一个电影越老的话，看他的人可能是在回忆经典，打分也会越来越高。  

• Koren, Yehuda. “Collaborative filtering with temporal dynamics.“ KDD 2009.

  如果引入用户之前的一些item打分行为的话，我们把这个叫做Neighborhood (Similarity)-based MF。  
 

• Koren, Yehuda. “Factorization meets the neighborhood: a multifaceted collaborative filtering model.”KDD, 2008.

 
  从机器学习这个角度来想，最需要记住的模型就是KNN模型，它是一个无参数模型，不需要去learn，另外一个就是基于Matrix Factorization这个一种linear的模型，由两个都是参数的向量相乘等于他的prediction，每个参数更新都依据于另外一半参数，这种方式很容易掉到局部最优点，现在这种方法通过SGD的方法可以达到非常好的效果。  

• 本文来自伯禹公开课的学习笔记。