古典重生
早在十几年前，那个国内互联网还在萌芽，BAT才刚开始展露头脚或是危机四伏的那个时代，
地球对面的Amazon，已经对推荐系统有了里程碑式的研究，那篇论文《Amazon.com Recommendations Item-to-Item Collaborative Filtering》让推荐系统为人所知。
那个时代的工程师，用现代程序员看起来略显稚嫩的手段，探索出了协同过滤（Collaborative Filtering）这一影响极其深远的推荐系统模型。
尽管，随着后来深度学习技术的发展，CF不再是推荐系统的主流，但CF的基本原理和思想一直影响至今，并且往往作为多路召回系统的一路还占有一席之地。在移动互联网的爆炸发展下，推荐系统的发展也是一日千里，特别是深度学习的引入，或许看上去CF以及它的那些变体已经不再那么耀眼，但那个时代的工程师前辈们，所闪烁的深具传统的智慧之光，一直激励着我们，指引着我们前进的方向。
协同过滤
索尼大法好
正如那句“索尼大法好”，彰显了SONY品牌在用户心目中的地位，那么对于绝大多数推荐系统从业者而言，协同过滤就是信仰一般的存在，因为它从上世纪90年代到2010年左右，几乎成为了推荐系统的代名词，整整影响了一代的工程师。
说了这么多，那赶紧来看一下协同过滤到底是个什么东西吧。
对于不明觉厉的词，我会习惯性的区望文生义，emm...没错，既然是协同过滤，那么很自然的会想应该就是协同大家的信息来对海量数据进行过滤从而进行目标推荐吧?实际上确实是如此~
下面我们便通过一个具体的例子来加以说明。
UserCF
考虑一个游戏推荐平台，为了简单起见，我们假设平台上有4个游戏《王者荣耀》、《明日方舟》、《碧蓝航线》、《少女前线》，5个用户A,B,C,D,E。
一个用户A访问了该平台，于是平台的推荐系统要决定向用户A推荐什么游戏，即预测用户A会喜欢哪个游戏，而为了进行这项预测，我们自然需要利用该用户的一些信息，这里我们使用了用户A的对游戏的历史评价信息。每个用户可以对游戏打1到10分，打分越高说明越喜欢某个游戏。为了便于分析，我们用矩阵的形式，将所有用户对游戏的打分信息列出来，没评分过的就姑且设置为0（也可以设为评分的平均值）：
| 王者荣耀 | 明日方舟 | 碧蓝航线 | 少女前线 | |
|---|---|---|---|---|
| 用户A | 2 | 0 | 9 | 0 |
| 用户B | 2 | 0 | 10 | 9 |
| 用户C | 10 | 5 | 3 | 0 |
| 用户D | 3 | 6 | 9 | 8 |
| 用户E | 1 | 7 | 8 | 7 |
我们按行观察上面的表格矩阵，显然每一行用户对各个游戏的打分向量形成了用户的特征，通过这个特征，我们就能找到同用户A相似的用户，然后把相似用户评分高的并且用户A没玩过的游戏推荐给他应该就对了~而要找到相似用户，只要计算特征向量的相似性，再取前n个（此处n是个超参数）相似向量对应用户即可。
而计算向量的相似度，很自然的我们会想到余弦相似度、点积相似度、欧式距离。
这里我通过计算用户A特征向量与B、C、D、E用户特征向量的余弦相似度分别为0.75,0.44,0.68,0.63，我们选择前2个用户即B和D的评分来给作为给A推荐的依据，即将用户B和D的与A相似度加权得分的平均值作为用户A对该电影的打分：
计算得到预测用户A对明日方舟的打分为, 对少女前线的打分为
， 于是我们的推荐系统向用户推荐《少女前线》这个游戏。
以上便是基于用户的协同过滤过程，它巧妙的将物品id作为了用户的特征，从而进行了有效的物品推荐，这也符合物以类聚的基本直觉。但是，从技术实现上来说，它有两个明显的缺陷：
- 互联网场景下，User数量往往大于Item数量，如这里的用户数量往往以亿为单位，远远多于游戏的数量，而UserCF需要计算和维护每个用户间的相似度以便快速找出top n相似的用户，存储用户相似度矩阵的开销非常大，特别是随着业务的不断发展，不断膨胀的用户数量会导致相似矩阵的空间以
的快速增长，这是在线存储系统难以承受的扩展速度。
- 用户的历史数据往往非常稀疏，特别对于一些低频用户来说，找到的相似用户的准确性非常低，从而导致UserCF不适用于那些正反馈获取较困难的场景（比如酒店预订等低频应用）
ItemCF
理解了UserCF，那ItemCF就再好理解不过了。
前面的UserCF我们是将行向量作为User特征，而ItemCF就是讲列向量作为Item的特征，从而计算出Item之间的相似度，从而基于Item进行推荐。
正是因为UserCF存在上面那两个缺陷，很多企业，不管是Amazon还是Netflix，在实现最初的推荐系统的时候，都没有采用UserCF，而使采用了ItemCF。
整个计算过程与UserCF一致，将上面的行向量转为列向量，然后两两计算每个Item之间的相似度，得到一个物品相似度矩阵。
当有用户访问时，只需要获得他曾今正向反馈的Items，然后找出与正向Items相似的Top k个Item作为推荐列表。
UserCF和ItemCF的场景选择
UserCF既然是基于相似用户的推荐，那必然就带有了社交属性，查询用户能够快速的获取到与自己趣味相投的人的喜好，从而发现曾今不在自己兴趣范围内的新兴趣，即兴趣的扩展。在一些偏好没那么大，兴趣分散的场景比如新闻、短视频之类的场景大概不错。而ItemCF则显然更适合有兴趣偏好的应用，比如某些人喜欢看科幻电影，那往往会去寻找科幻相关的电影，那通过他已看的电影找到相似的电影就不错。
矩阵分解
显而易见的，不管是UserCF还是ItemCF，它们的协同矩阵都是基于ItemID或是UserID的热编码，这样虽然简单直观，但这样的相似性是间接的，即user要找到相似的user再到item，item也是同理，这样就导致了泛化能力的缺失，我们无法直接判断user与某个item之间的关系。更严重的是导致了稀疏性的问题，使得热门Item容易和大量Item相似经常被推荐，而冷门Item却很难与其他Item产生相似很难被推荐。
工程师们为了解决稀疏性问题以及增加模型的泛化能力，于是就提出了矩阵分解算法。这个算法2006年Netflix举办的著名推荐算法竞赛中大放异彩，从此这个算法开始在业界流行起来。原来十四年前推荐领域最闪耀的居然是矩阵分解这么稚嫩的算法，不禁让现在的工程师欷歔不已，可见这十多年的IT技术发展之迅猛。
接下来让我们来看一下矩阵分解应用在推荐领域的原理。
想一下，在NLP中，最早的one-hot词向量只利用了词id这个属性，同样非常稀疏，于是后来发展出的embedding一个隐藏层的词向量则是稠密的。矩阵分解算法的想法与embedding有点不谋而合，它希望为每个user和item生成一个稠密的隐向量，将user和item都映射到一个隐含的表示空间向量上，距离相近的user和item及代表了他们之间的相似性，在推荐的过程中，便可以直接将于目标user相似的item推荐给他。比如爱丽丝同学的特征向量与《少女前线》的特征向量最相似，又没玩过，那便将《少女前线》这个游戏推荐给她。
这种直接建立user和item之间联系的方法真是太棒了，那么如何得到这个隐向量呢？
矩阵分解
矩阵分解算法的目的是将 的协同矩阵，分解成 的user矩阵和的item矩阵，其中 是user数量， 是item数量， 是隐向量的期望维度，这是供调节的超参数，当 越小时，包含的信息就越少，泛化能力就越高，反之，包含的信息多，表达能力更强，相对的泛化能力就更弱了，因此在实际应用中，会根据推荐效果和工程开销寻找一个合适的值。
如果你事先没看过业界主流的解决方案，又恰好学过线性代数...那么一个很直接的想法自然是通过SVD来进行矩阵分解，一个 的矩阵A，分解为
,其中
是一个
的矩阵，
是一个
的对角矩阵，除了主对角线上的元素以外全为0，主对角线上的每个元素都称之为奇异值，
是一个
的矩阵。
显然，我们只要取 前
大哥值，得到一个
的矩阵，然后将
和
与所删除的
维度对应的维度也删了，于是原始的矩阵
,这样便达到了上述得到
维隐向量矩阵分解目的了~
看上去SVD完美解决了矩阵分解问题，但实际上这个方法存在着几个重要缺陷，导致并不适合在互联网场景下使用：
- SVD要求原始的矩阵是稠密的，这他妈不就跟我们要解决的问题相悖了吗...要用SVD还得对稀疏值进行填充.....
- SVD计算复杂度是
,这对于动则上亿用户和上百万item的互联网应用来说简直是灾难。
那还有没有别的好的分解方法呢？既然正面算不行，那就用凑数大法呗！于是，就该梯度下降法登场了。这个方法对于搞机器学习的朋友来说真是不能再熟悉了。
首先，我们构造一个目标函数，然后用梯度下降去优化它从而得到最优解。
一个非常直观的目标函数便是距离的均方误差：
为了防止过拟合，可以加入一个L2正则项，于是目标函数变成：
其中 是对两项加权的超参数，以使得目标不被其中一个矩阵所之配,因此调整这个超参数至关重要。
实际上除了用随机梯度下降，这个还可以用一个特定的算法：加权交替最小二乘（WALS）。
WALS的工作方式是随机初始化嵌入，然后在以下之间交替：
- 固定U然后求解V
- 固定V然后求解U
每一阶段都可以精确求解(通过线性系统求解)，并且可以分布式计算。该技术保证收敛，因为每一步都保证减少损失。
SGD对比WALS
| SGD | WALS | |
|---|---|---|
| 损失函数 | 灵活使用其他损失函数 | 只能在该算是函数中使用 |
| 并行 | 可以并行 | 可以并行 |
| 收敛速度 | 较慢 | 比SGD快 |
| 缺失值 | 难以处理缺失值（需要负采样和重采样） | 更容易处理缺失值 |
处理打分的一点技巧
不同用户之间的打分轻重实际是很有差异的，比如同样满分是5星的游戏，有些用户给认为比较差的游戏打4星，而有些用户认为好游戏才打4星... 另外不同类型的游戏之间的衡量标准也是会有区别的，比如独立游戏普遍得分较高，而热门网游则会低很多。
为了消除User和Item的打分偏差，常见的做法是在做矩阵分解的时候加入User和Item的偏差向量，如下所示：
其中， 是全局偏差常数，
是user偏差系数，可以使用user打分均值，
是item偏差系数，可以使用item的评分均值。
加了打分偏差项后，矩阵分解能够得到更加能反应不同user对不同item的真实态度，也就更容易捕捉到评价数据中的有效信息，从而避免推荐结果的偏差。
逻辑回归
不管是协同过滤还是矩阵分解，从始至终，它们都只用到了user id和item id两个特征。而完全没有使用user以及item的一些属性上下文信息，这想想就会觉得这样的推荐是不够全面的。
为了融入更多的特征进行推荐，前辈们首先搞了个基础的单一神经元结构的感知机，即逻辑回归算法。相比于协同过滤和矩阵分解利用向量的相似度来进行推荐，逻辑回归将推荐问题看作一个分类问题，通过预测正样本的概率对物品进行排序，从而根据概率高低进行推荐。何为正样本？正样本可以是用户点击了某个物品或是观看了某个视频，下载了某个游戏等等推荐系统希望用户产生的“正反馈”行为。因此，逻辑回归模型将推荐问题转化成了一个点击率（CTR）预估问题。
基于逻辑回归的推荐流程
- 将user信息，如年龄、性别、学历....item信息，如描述分类简介...当前时间地点等等的特征转化为数值型特征向量。
- 确定逻辑回归模型的优化目标（以优化点击率为例），利用已有的样本数据对逻辑回归模型进行训练，得到相应的权重参数。
- 推理阶段只要将特征向量输入，即可推理获得用户点击相关item的概率。
-
对概率进行排序，获得推荐列表。
逻辑回归
逻辑回归实际上就是一个单层单输出神经元的神经网络...简单的一逼，就不多讲了。因为其不仅融入了更多的特征，并且解释性强，模型简单计算快，它在深度学习开始流行之前是推荐系统的主要选择之一。虽然简单易用，但终究还是表达能力不够强，特征需要人工选取，无法进行特征交叉、特征筛选等一系列高级操作，在深度学习开始流行后，逻辑回归逐渐退出历史舞台。
本文主要介绍了推荐领域十年前即2010年之前的几个曾今一度辉煌的几个算法。或许它们已经不怎么被使用了，但它们的思想，创造它们的人的精神，是一直指引着我们前进的光。
下篇文章会继续讲一下之后的几年，在深度学习正式进入推荐系统之前，传统算法从简单走向复杂的发展。
参考资料
- google的《Recommendation Systems》课程
- 王喆的《深度学习推荐系统》
网友评论