# 推荐系统前深度学习时代：从协同过滤到 GBDT+LR


[toc]

本人身处广告营销领域，广告系统本质是个推荐系统，本文旨在梳理相关推荐算法。《深度学习推荐系统》是一本很不错的入门书籍，很系统，不过很多地方写得不太清楚，阅读过程查阅了大量资料。这篇文章作为开篇，会写一个系列，目的是将推荐领域相关核心概念和算法全覆盖。

## 0 推荐算法四要素

如果把推荐系统看作一个函数，可以表达为 $F(i,c,u)$，其中 $i$ 为 item 即待推荐物品，$c$ 为 context 即当前上下文（时间、地理等），$u$ 为 user 即用户，$F$ 记为推荐算法。

整个算法演进就在围绕这四个要素做文章。

## 1 协同过滤（Collaborative Filtering, CF）

推荐领域最经典的算法之一是协同过滤，该算法是 Xerox 发明，后在 2003 年被 Amazon 发扬光大。该算法将用户和物品构成一个大矩阵，每行是一个用户对每个物品的态度（喜欢 or 不喜欢），这个矩阵就能刻画每个用户对物品的喜好程度，该矩阵成为共现矩阵。
  
该算法分为 User-Based CF 和 Item-Based CF。

### 1.1 User-based CF 
  
站在用户角度，针对用户 A，计算与其喜好相似的 topN 用户；然后遍历每个物品，让这些与自己相似的用户针对这个物品投票，计算出每个物品得分；最后按照每个物品得分排序，排名最高的几个物品就可以推荐给用户了。这里有两个关键点：
1. 用户相似度计算，可以取出每个用户在共现矩阵对应的行向量，与目标用户向量计算余弦相似度，找出 topN。
2. 物品得分计算 $Ru,i=\frac{\sum(w_{u,s}R_{s,i})}{\sum{w_{u,s}}}$，其中 $w_{u,s}$ 是用户 u 和 s 的相似度，$R_{s,i}$ 是用户 s 对物品 i 的喜好程度作为投票的权重，$Ru,i$ 即为用户 u 对物品 i 的喜好程度。
  
获得 u 对全部物品喜好后，排序即可得推荐列表。

### 1.2 Item-based CF 
  
站在物品角度，沿用前面的共现矩阵，这次从列角度思考，计算两两列向量的相似度，得到一个对称方阵（只看上三角或下三角即可）。
  
当一个用户进站访问时，在共现矩阵里查看其对应的行向量，确定其之前表达过喜好的物品，然后针对每个喜欢过的物品到上面物品相似度矩阵查找最相似的 topK 物品，然后对这 K 个物品计算喜好得分，计算公式为 $R_{u,i}=\sum{w_{j,i}R_{u,j}}$，其中 i 是要确定用户喜好程度的物品， j 是用户 u 表达喜欢过的物品，$w_{j,i}$ 是物品 j 和 i 相似度，$R_{u,j}$ 是用户 u 对 j 的喜好程度。

### 1.3 User-based CF 和 Item-based CF 比较

1. User-based CF 适合社交类场景，朋友喜欢的自己大概率也喜欢，很符合直觉。但是一般这类场景用户多余物品而且持续增长的话，由于每次都要计算相似用户所以共现矩阵存储和维护是个问题；另外就是针对获取难的物品，比如价格较贵的酒店、奢侈品等，会导致用户对应的向量很稀疏。
2. Item-based CF 适合兴趣较为稳定的场景，比如电商和电影，用户一段时间内倾向寻找某几类爱好的物品。业界 item-based CF 用得较多。

### 1.4 优势

CF 非常直观，可解释强。

### 1.5 劣势

1. CF 泛化能力差，只用了用户和物品信息，上下文信息未用起来。另外因为它无法将两个物品相似这一信息推广到其它物品相似度计算上，两两相似性无法传递。
2. 热门物品（大家都喜欢的物品）具有很强的头部效应，尾部物品由于向量稀疏，即使相似度很高但是无法识别出来，最后算出来的最相近物品都是热门物品。

## 2 矩阵分解
### 2.1 背景

为了解决 CF 泛化能力差、无法推广物品相似度的问题，矩阵分解技术被提出，2006 年在 netflix 举办的算法竞赛中大放异彩。

### 2.2 算法原理

针对共现矩阵 $A_{mxn}$，通过矩阵分解技术（奇异值分解 svd、梯度下降等）得到两个矩阵之积：
 $$A_{mxn}=U_{m,k}*V_{k,n}$$
其中 U 为用户矩阵，每一行代表一个用户隐向量； V 为物品矩阵，每一列代表一个物品隐向量；k 是一个超参数，越小隐向量表达能力越弱但则泛化能力越强。分解后得到的两个矩阵基于整个共现矩阵分解得到，不再稀疏。

由于奇异值分解适用于稠密矩阵，但是推荐场景下一般矩阵都非常稀疏所以更常用的是梯度下降，梯度是怎么引入的呢？

我们知道共现矩阵用户 u 针对物品 i 有个喜好值记为 $R_{u,i}$，矩阵分解后（假设已经分解完成了）的用户矩阵对应用户 u 的隐向量记为 $X_u$，物品矩阵对应物品 i 的隐向量记为 $Y_i$，则我们期望
$$X_uY_{i}=R_{u,i}$$
这个只是期望，左边能尽可能逼近右边我们在工程上就满足了。针对全部用户 u, i 我们可以得到针对全局的最优期望公式即均方误差为：
$$min\sum{(r_{u,i}-X_uY_i)^2}$$
基于上述公式针对 X 和 Y 求导，然后沿着梯度下降方向迭代 X 和 Y 即可。工程实现上为了避免过拟合，会在上述均方误差公式后面增加一个正则化项，关于正则化是个大话题先不展开，记得它存在目的是为了减少过拟合即可。

得到用户矩阵和物品矩阵后，针对每个用户，计算它和每个用户向量的内积即可得到喜好程度，排序即可地推荐列表。

### 2.3 优势

1. 相比 CF 泛化能力更强，一定程度解决了数据稀疏问题。
2. 分解得到的用户隐向量和物品隐向量其实是一种变相的 embedding，这个结果便于和其它特征进行组合可以与深度学习无缝拼接，后面介绍深度学习类推荐算法时候会重提这一点。

### 2.4 劣势

同 CF 一样，只用到了用户和物品两项信息，上下文没有利用起来。从下个算法开始将会重点解决特征利用不充分问题。

> 过渡说明
>> 接下来描述的每个算法的输入都是一个样本矩阵，其中每一行为一个样本，每一列为一个特征维度；输出是一个概率值，作为点击率。

## 3 LR（logistic regression）
### 3.1 背景

Logistic 回归最早是在 20 世纪 50 年代为了解决生物统计问题而被提出的。

### 3.2 算法原理

公式如下：
  $$\widehat{y}=sigmoid(\sum{w_ix_i})=\frac{1}{1+e^{-\sum{w_ix_i}}}$$
公式说明：
  
$\widehat{y}$ 为针对某个样本的预测输出，$x_i$ 为前述样本的第 $i$ 特征取值，$w_i$ 为该特征对应的权重。需要说明的有两点：

1. $x_i$ 为标量
2. $w_i$ 也为标量，它的值为学习对象
   
### 3.3 优势

1. 输出就是一个 $(0, 1)$之间的数，符合直觉，可解释性强。
2. 工程化简单，尤其针对海量数据。

### 3.4 劣势

1. 仅能捕获特征之间的线性关系，不能很好地表示特征之间的交互。
2. 为了改善预测效果，需要做大量的手工特征工程。

## 4 Poly2（Polynomial Regression of degree 2）
### 4.1 背景
为了捕获特征之间的交互关系，业界引入了 Poly2 算法。

多项式核函数（包括二次多项式核）在支持向量机（SVM）的发展过程中变得非常重要。SVM 最初由 Vladimir Vapnik 和 Alexey Chervonenkis 在1960年代末到1970年代初提出。多项式核函数并不仅限于二次形式，也可以有更高阶的形式，但二次多项式核（Poly2）在许多应用中是很实用的。
### 4.2 算法原理

公式如下：
  $$\widehat{y_i}=sigmoid(w_0+\sum{w_ix_i}+\sum\sum{w_{ij}x_ix_j})$$
公式说明：
  
相比 LR 增加了一个二阶项，这个部分负责进行特征交叉。其中：
1. $w_i$、$x_i$ 同 LR 算法说明。
2. $w_{ij}$ 是一个新增加的待学习标量参数，它负责学习 $x_i$ 和 $x_j$ 之间的交互关系。
3. $x_ix_j$ 可以看作两个特征之间的哈达玛乘积。

### 4.3 优势
  
1. 能够捕获特征之间的二阶交互。
2. 通过特征交互，可以建模非线性关系。
### 4.4 劣势
  
1. 参数多计算复杂度高 $O(d^2)$，其中 $d$ 是特征个数。
2. 由于参数太多，在数据稀疏场景下容易过拟合。
3. 只能捕获二阶交互，更高阶的无法捕获。

## 5 FM（factorization machines）
### 5.1 背景

为了解决 poly2 在稀疏数据集容易过拟合以及计算量过大的问题而提出。

这个算法是由 Steffen Rendle 在2010年左右提出的。它融合了矩阵分解（例如SVD）和线性回归模型的特性，以有效地处理高维稀疏数据和捕捉特征之间的交互。
公式如下

$$\widehat{y_i}=sigmoid(w_0+\sum{w_ix_i}+\sum\sum{<v_i,v_j>x_ix_j})$$
公式说明

形式同 poly2，差别在二阶项。其中：
1. $w_i$、$x_i$ 同 LR 算法说明。
2. $v_i$ 和 $v_j$ 是一个新增加的待学习向量参数，它们叫做隐向量，长度为 $k$，$k$ 也是一个超参数，大小远远小于特征个数 $d$。
3. $x_ix_j$ 可以看作两个特征之间的哈达玛乘积。

poly2 是学习任何两个特征值之间的交互关系，而 fm 在全样本中学习每个特征对应的隐向量，这使得 fm 有更好的泛化性，而且参数量大幅减小（从 $d^2$ 降为 $kd$）。

### 5.2 优势
  
1. 可以捕获任意阶数的特征交互，尽管在实践中通常只计算到二阶。
2. 通过参数共享，避免了 poly2 参数过多的问题，同时让模型泛化性更好。
3. 相比 poly2 在稀疏数据集上表现更好，具体来说就是针对某个特征，其它特征都为它的隐向量产生贡献了力量，而且这种力量在其它特征与自己交叉时共享。

### 5.3 劣势
  
1. 尽管计算复杂度相比 poly2 降低，但仍然较大，特别随着隐向量维度 $k$ 变大的时候。
2. 多了一个超参数也就是 $k$ 的调整需求。

## 6 FFM（filed-awareness factorization machines）
### 6.1 背景

FFM 算法是对 FM 算法的扩展，从名字就能看出来。广告点击率预测是一个利益驱动的事情，在大体量下（比如谷歌一年收入万亿）点击率预估稍微提升几个点带来的收益巨大。

FFM 在 FM 基础上引入了域（filed）的概念，隐向量不在共建共用，而是针对每个交互特征独立构建了一个隐向量，这类似 poly2 不过这里用的向量而非标量权重。

### 6.2 算法原理

公式如下

$$\widehat{y_i}=sigmoid(w_0+\sum{w_ix_i}+\sum\sum{<v_{i,\text{filed}(j)},v_{j,\text{filed}(i)}>x_ix_j})$$

公式说明

形式同 poly2 和 fm，差别在二阶项，ffm 的二阶项相当于在 fm 基础上融合了 poly2。下面详细解释：
1. $w_i$、$x_i$ 同 LR 算法说明。
2. $v_{i,\text{filed}(j)}$ 和 $v_{j,\text{filed}(i)}$ 是一个新增加的待学习向量参数，它们类似 fm 中引入的隐向量，不过粒度更细化了。fm 中引入的隐向量，针对每个特征只有一个；而 ffm 相当于为每个特征学习了一组隐向量，而不是一个。这里相当于 poly2 为两两特征学习了独立的交互关系，不过不同于 poly2 只用一个标量权重，ffm 用的是向量。每个隐向量长度为 $k$，$k$ 也是一个超参数，大小远远小于特征个数 $d$。
3. $x_ix_j$ 可以看作两个特征之间的哈达玛乘积。
4. ffm 参数量为 $kd^2$，参数量和计算量都非常大。

### 6.3 优势

相比 fm 更加注重两两特征之间的独立关系

### 6.4 劣势

1. 参数量和计算量以及存储开销相比 fm 增加非常多。
2. 稀疏数据集容易过拟合。

## 7 LS-PLM（Large Scale Piece-wise Linear Model）

### 7.1 背景

这个算法单纯是对 LR 算法的改进，不再像原始 LR 一样无差别应用，而是考虑到业务场景的差异化做得优化，这个优化思想在东方国家比较罕见。该算法在 2012 年便成为阿里巴巴内部最核心的 CTR 预估算法了。

### 7.2 算法原理

公式如下

$$p(y=1|x)=\sum_{i=0}^{m}softmax(u_i x)LR(w_i x)=\sum_{i=0}^{m}\frac{e^{u_i x}}{\sum_{j=0}^{m}{e^{u_i x}}}\frac{1}{1+e^{-w_i x}}$$

该算法简单说就是主观上认为样本应该可以分为若干类，但不是把每个样本只划分为到某一类中，而是认为每个样本属于哪个分类都是有一定概率的（这个在结构上有点 attention 的意思），针对样本在每个分类上都用该分类所属的参数算一下 LR，然后将各个分类的 LR 结果做加权平均（这个相当于每个类别投票，不过投票权利不同）。这个算法也被叫做 MLR（Mixed-LR），不过我觉得这个叫法不足以反映投票加权的本质。

公式中 $u_i$ 是分类 $i$ 的权重，$w_i$ 是分类 $i$ 的 LR 参数，$x$ 是样本特征向量。输出即为 $y=1$ 的概率。

### 7.3 优势

1. 端到端非线性学习。通过分类投票，可以捕获特征之间的非线性交互，不用人工设计特征交叉。
2. 可以分布式并行。
3. 稀疏性好，也就是非零参数少，这对在线推理系统很重要因为计算量小。稀疏性好的原因是在目标函数（本文未展示）上用了 $L_{2,1}$ 正则化。

### 7.4 劣势

相比后来的深度学习，该算法在更深层次的特征交叉以及序列特征使用上是不足的。

## 8.GBDT+LR
### 8.1 背景

为了提升模型效果，要么像前面的 lr、poly2、fm、ffm 一样进行手工或者半自动地进行特征组合和筛选，要么优化目标函数引入特征交叉项提升特征组合能力。

我们看到从 LR 到 FFM，这一路进化，核心目标函数并没有变化，进化只是表现在如何更好地进行特征交叉。

2014 年 Facebook 回到原点，提出了 GBDT+LR 组合算法模型。

GBDT（Gradient-Bootsted Discision Tree） 不会在本篇文章深入介绍，这个算法本质是用一堆决策树去逼近目标，但是要介绍下名字。我感觉能跟这个名字一拼的是 LSTM（Long short-term memory），后者好歹还有个短杠区分下 long short 分别修饰谁（short 修饰 term，long 修饰 short-term 即更长的短期），GBDT 前面的 GB 梯度提升比较误导人，算法本质是基于梯度下降寻找下个决策树（下个决策树拟合前序决策树们遗留的残差），这里的梯度下降用 G 表示，多个决策树一起协同用 B 表示。GBDT 是 Boosting 算法的一种，还有另一个流派 Bagging， 后续文章介绍。

### 8.2 算法原理

这个算法分为两步：
1. 第一步先将原始样本输入 GBDT，这一步虽然也在做目标拟合，但新增了一个项目，就是将全部树的输出进行向量化然后串联起来作为新的特征（有点 embedding 的意思了）。
2. 前一步每一颗树的叶子将被量化为 one-hot 向量（只有命中的叶子才是 1，其它叶子都是 0），然后依次将各个树对应的 one-hot 向量串联起来构成输入样本对应的 embedding 向量，该向量作为 LR 输入，后续同 LR 算法处理。

### 8.3 优势

1. LR 的优势，符合直觉，计算简单。
2. GBDT 可以捕捉特征之间的交互关系，而且是自动找到这些交互，并且实现了非线性映射，这使得模型泛化能力更强。

### 8.4 劣势
1. 训练复杂性增加，先训练 gbdt 后训练 LR，这也增加了模型部署和维护复杂性。
2. 推理速度相比单个模型可能较慢。
3. gbdt 训练复杂导致模型可能过拟合。


--end--