本章介绍思路如下：从协同模型推广到矩阵分解，从第5章介绍的LR模型推广到其他线性模型如FM和FFM，从第5章介绍的树模型和集成模型推广到其他树模型和集成算法模型，以及深度学习模型Wide&Deep、Deep FM。
1.矩阵分解
基于协同的模型都属于近邻分析模型，但是近邻分析模型又存在一些明显的问题。物品之间的相关性、信息量不因向量维度的增加而线性增加。由于矩阵的维度可能包含类别特征one-hot编码后的属性，矩阵内部的数据较为稀疏，而矩阵维度的变化对近邻分析结果的影响很大，因此一般采用矩阵分解的方式求解近邻分析模型。
矩阵分解的本质是将一个稀疏且维度较高的矩阵拆解为维度较低的两个矩阵的乘积，如下图所示。
假设用户对物品的评价矩阵是Rm×n，即有m个用户，n个物品，则可以分解为：
R_{mxn}=P_{mxk}Q_{kxn}
在了解了矩阵分解原理之后，我们再来看看奇异值分解是如何利用矩阵分解解决问题的。
1.1奇异值分解
SVD算法的学习过程如下。
1）用户对物品的评分矩阵R，每条数据是一个训练样本。
2）将R分解为矩阵P和矩阵Q，并随机初始化元素值。
3）用矩阵P和Q计算预测后的评分。
4）计算实际评分和预测评分之间的误差。
5）按照公式（8-6）和（8-7）更新参数并更新其中每个元素。
6）重复步骤3到步骤5，直到达到停止条件（设定迭代次数）为止。
SVD还有一个变种是SVD++算法。前面已经讲到了推荐系统中的用户冷启动问题。比如，主动点评电影或者美食的用户少，显示反馈比隐式反馈少，此时可以考虑利用用户行为的隐式反馈来弥补。我们可以把用户历史行为中的隐式反馈和用户属性加入用户评分矩阵，这就相当于对原来的矩阵进行了扩展，则有：
1.2交替最小二乘
矩阵分解算法可以利用随机梯度下降法，也可以利用交替最小二乘（Alternating Least Squares，ALS）法。ALS算法的核心思想是：将矩阵R（用户对于商品的兴趣矩阵）分解为P（用户对于隐特征的兴趣矩阵）和Q（商品与隐特征的兴趣矩阵的转置矩阵）。在式（8-1）中，因为
ALS算法的学习过程如下。
1）初始化随机矩阵Q中的元素值。
2）假设矩阵Q已知，则损失函数中的y为已知量，对损失函数中的x求偏导，求解矩阵P。
3）得到矩阵P后，假设矩阵P已知，则损失函数中的x为已知量，对于损失函数中的y求偏导，求解矩阵Q。
4）交替进行步骤2和步骤3，直到误差达到设定条件为止。
如果对隐式反馈的矩阵分解中的ALS算法进一步改进，如进行加权交替，则ALS算法被称为Weighted-ALS（加权交替最小二乘）法。这里举一个例子进行分析。如果你买了一件比较昂贵的大衣，之后购买心仪的鞋子和裤子的计划可能就会被搁置，但你可能依然会关注这些商品，对应到行为上可能就是多次点击和查看。行为发生的次数是对行为置信度的反映，是加权的一种形式。
1.3贝叶斯个性化排序
矩阵分解的本质是预测一个用户对一个物品的偏好程度。在实际应用时，通常会利用矩阵分解的结果进行排序。前面的章节也讨论了排序学习的相关方法，包括单文档方法、文档对方法和文档列表法。SVD和ALS均属于单文档方法。单文档方法只考虑了每个物品，且每个物品是一个孤立的点。
单文档方法的缺点在于只能收集到正样本，所以在求解过程中往往将有缺失值的样本作为负样本，这会降低预测结果准确率，至少对那些数据有缺失值的用户是否喜欢某物品的判断会产生偏差。而贝叶斯个性化排序（Bayesian Personalized Ranking，BPR）算法可以解决该问题。
BPR算法是基于贝叶斯的个性化排序，服从两个假设。
1）每个用户之间的行为偏好相互独立，即用户u在物品i和物品j之间的抉择与其他用户无关。
2）同一个用户对不同物品的排序相互独立，即用户u对物品i和物品j的排序与其他物品无关。
BPR算法关心的是物品对于用户的相对顺序，构造的样本是用户、物品1、物品2以及两物品的相对顺序，如下表所示。
BPR算法学习过程是：在得到推荐分数后，计算正样本和负样本的分数之差，通过这个差值反映用户对于不同物品的偏好程度。正样本是用户看到后有隐式反馈的物品，负样本是用户看到后没有任何反馈的物品，比如用户u对物品1和物品2的推荐分数差为：
BPR算法参数的训练过程如下。
2.线性模型
逻辑回归模型是基础的线性模型。这里我们会对其他推荐场景中使用到的线性模型进行梳理，主要介绍因子分解机（Factorization Machine，FM）及其变种FFM(Field-aware Factorization Machine)。
下面先介绍一下FM产生的原因：使用逻辑回归模型存在一些问题。逻辑回归模型中大量的特征需要通过人工获得，而且逻辑回归模型认为特征之间不存在依赖关系，但是现在中并非如此。
如果我们考虑最朴素的特征组合，即考虑特征之间的二阶笛卡儿乘积，那么会导致特征维度太多。并且这样组合后的特征并不都是有效的，且组合后的特征非常稀疏，简单说就是这些特征组合后不便于找到符合样本的特征，不足以支持训练出有效的参数。最朴素的特征组合模型表达式如下：
2.1FM模型
因子分解机是由Steffen Rendle于2010年提出的一种基于矩阵分解的机器学习算法。目前，该算法广泛地被用到推荐系统以及广告预估模型中。逻辑回归模型认为特征是相互独立的，但是在实际情况下特征之间是存在依赖关系的，因此需要进行特征交叉。
FM的主要目的是解决稀疏特征下的特征组合问题。针对式（8-22）中出现的问题，FM把ωij优化成两个隐因子的向量的点积<vi，vj>形式，如式（8-23）所示：
举一个简单的例子，如果特征A和特征B在一些样本中一起出现过，特征B和特征C在一些样本中一起出现过，那么特征A和特征C无论是否在样本中一起出现过，仍然是有一些联系的。在式（8-23）中，vi是第i维特征的隐向量，隐向量的长度为k(k<<n)，包含k个描述特征的因子，
下图所示是FM模型，图中每一行表示一个特征向量和预测的目标结果。第一个框表示用户矩阵，包括3个用户{Alice(A)，Bob(B)，Charlie(C)}，是one-hot编码，属于稀疏矩阵；第二个框表示电影矩阵，包括4部电影{Titanic(TI)，Notting Hill(NH)，Star Wars(SW)，Star Terk(ST)}，是one-hot编码，属于稀疏矩阵；第三个框是其他人对上面4部电影的评价矩阵，归一化特征；第四个框是用户在一个月内评价的次数，也是one-hot编码，属于稀疏矩阵；第五个框表示用户对上一部电影的评价。
2.2FFM模型
FFM把相同特征归于同一个场（Field），交互捕捉不同场之间的数据特征也比较重要。FM中一个特征只对应一个向量，而在实际场景中不同场的特征交互时应该使用不同的向量，这就是FFM（Field-aware FM）的提出动机。FM可以看作是FFM的一个特例，把所有的特征都归属于一个场。所以，FFM模型如下：
3.树模型
搜索和推荐至少要分两个阶段：召回和排序。在召回阶段，因为处理的数据量较大，要求处理速度快，所以使用的模型一般不能太复杂，而且特征不需要太多。但是在排序阶段，因为处理的数据一般较少，所以模型要足够精确，可以选择稍微复杂的模型，使用更多的特征进行训练。树模型在排序阶段便是一个不错的选择。我们还可以把弱分类器集成起来组合成一个功能强大的分类器。本节将继续介绍树模型以及集成模型。
3.1决策树模型
决策树算法是一种归纳分类算法，它通过对训练集的学习，挖掘有用的规则，对新数据集进行预测。它属于有监督、非参数学习算法，对每个输入使用该分类区域的训练数据计算得到对应的局部模型。决策树模型的基本算法是贪心算法，以自顶向下递归的方式构建决策树，如下图所示。贪心算法是在每一步选择当前状态下最优的路径。
我们可以用以下几种方法构建决策树。
1.ID3算法
ID3算法的核心思想是最大化信息熵增益。所谓最大化信息熵增益，即每次进行下一次分裂时，计算出所有类别对应当前特征的熵，选择能够使得信息熵增益最大的那一个特征类别进行下一步的分裂。假设有一组数据，设D为某一个特征类别，则根据熵的定义可以得到D的熵为：
其中，pi表示第i个类别在整个训练元组发生的概率，在离散随机过程中，可以用i出现的数量除以整个数据的总数量n作为估计值。
由于初始数据可以划分的类别不止一项，于是我们需要对已经划分为D类别的数据再次分类。假设此次的类别为A，则类别A对数据集D划分的条件熵为：
2.C4.5算法
尽管ID3算法能够帮助决策下次分裂特征，但其本身存在一个问题：一般会优先选择有较多属性值的类别，因为属性值多的类别相对属性值少的类别有相对较大的信息熵增益。C4.5算法则使用增益率（Gain Ratio）作为选择分支的准则，同时引入分裂信息（Split Information）来惩罚取值较多的分类。其定义为：
3.CART算法
CART假设决策树是二叉树，内部节点特征的取值为“是”和“否”，左分支特征取值为“是”，右分支特征取值为“否”。这样的决策树等价于递归地二分每个特征，将输入空间（即特征空间）划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在给定的输入条件下确定输出的条件概率分布。
CART算法由以下两步组成。
1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。
2）决策树剪枝：通过验证数据集对已生成的树进行剪枝并选择最优子树，这时以损失函数最小作为剪枝的标准。
CART决策树的生成是递归地构建二叉决策树的过程。CART决策树既可以用于分类，也可以用于回归。对于分类而言，CART以基尼系数最小化准则进行特征选择，生成二叉决策树。
CART生成算法如下：
切分点作为最优特征与最优切分点。依据最优特征与最优切分点，从现节点生成两个子节点，将训练数据集依据特征分配到两个子节点中。
4）对两个子节点递归地调用步骤1~3，直至满足停止条件为止。
下面再介绍一下CART树剪枝。
剪枝方法的本质是在树模型庞大的叶子节点中，挑选对于模型整体影响过量或不重要的部分，将其乃至之后可能出现的分类整体从模型中删除。删除节点的好处在于：提高了对于同类问题的泛化能力，同时由于剪去了部分中间树叶节点，提高了训练速度。在树模型中，常用的剪枝方式为前剪枝和后剪枝。
前剪枝，也叫预剪枝，是在决策树构造的时候同时进行剪枝。
前剪枝过程如下。
1）按照判断信息熵下降的方式（所有决策树的构建方法都是在无法进一步降低熵的情况下停止创建分支的），设定特征选择的阈值。
2）对每一个特征A，计算其带来的信息不确定性下降的程度，并与事先设定的阈值进行对比，若大于阈值则作为新的特征加到树中，否则舍弃。
3）对所有的特征重复步骤2，直至遍历所有特征。
这种方法存在明显的缺点，就是在不同的模型中，甚至不同的问题中，模型的训练者很难精确地给定阈值。过低的阈值可能会导致剪枝效果不明显乃至基本无效，而过高的阈值又可能导致模型学习能力较差。即使单独调参，由于变量太多，在不断实验过程中，即使最后能找到一个较为适合的阈值，也不可避免地会消耗大量的时间。所以，前剪枝虽然在树模型中应用普遍，但是其表现仍不如后剪枝。
后剪枝本质是对子节点的合并。其原理在于如果子节点合并，熵的增量小于一个范围，则将两个节点合并，且后续节点也重新标示为当前节点的属性。那么，前、后剪枝的最大区别在于后剪枝的熵的判断是基于全局的，而前剪枝的熵的判断其实是基于当前的。两者对于熵的变化的判断能力是完全不同的，导致表现能力不同。
后剪枝过程如下。
1）按照判断信息熵下降的方式，计算每个节点的经验熵。
2）递归地从树的叶子节点往上回缩。计算叶子节点回缩到父节点之前和之后的损失函数值，如果回缩之后的损失函数值小于回缩之前的损失函数值，则进行剪枝。
3）对所有的叶子节点重复步骤2，直至不能继续为止。
下面举例介绍CART树的剪枝。
CART树的剪枝主体可以分为两部分，即子树序列的生成以及交叉验证。
1）子树序列的生成：找到一个中间节点，并将后续的所有子节点与叶子节点退回到这个中间节点，这样当前的中间节点就成为一个新的叶子节点，当前新的模型就是原始树模型的一个新的子树模型。而由所有叶子节点由下至上地生成所有子树模型即原始树模型的子树序列。
2）交叉验证：依赖所有子树模型的表面误差增益率（即误差的增加速率），选取多个节点组成的子树与交叉验证集合进行验证，选取误差最小的子树作为最优树的结果输出。
下图所示为所有子树序列T0～Tn的生成过程，其中包含所有可能的剪枝情况。
3.2集成算法模型
1.GBDT
梯度提升迭代决策树（Gradient Boosting Decision Tree，GBDT）是一种Boosting算法。Boosting算法的核心思想是：利用前一轮迭代的误差更新训练集的权重，校正前一轮迭代被错误分类的样本，下一轮迭代会将重心放在上一轮分错的样本上。GB（Gradient Boosting）是一个算法框架，即可以将已有的分类或回归算法放入其中，得到一个性能强大的算法。在GB框架中，最常用的学习器是决策树，二者结合则为著名的GBDT算法。GBDT在函数空间利用梯度下降法进行优化。其基本思想是沿着梯度的方向，构造一系列的弱分类器，并以一定权重组合起来，形成最终决策的强分类器。
2.GBDT+LR
一棵树的表达能力很弱，不足以表达多个有区分性的组合特征。多棵树的表达能力更强一些。RF（随机森林）是由多棵树组成的，但预测效果不如GBDT。GBDT+LR模型融合的思想来源于Facebook公开的论文。这篇文章的结论是GBDT+LR效果要优于GBDT和LR各自单独的模型效果。
在这个模型中，GBDT任务是生成高阶组合特征。GBDT生成N棵树，每棵树上都能从根节点走到叶子节点，到了叶子节点非0即1（点击或者不点击）。把每棵树的输出看成一个组合特征，取值非0即1。树i有Mi个叶子，相当于有Mi个组合特征。每棵树采用one-hot编码，一共有(M求和)个维度的新特征，然后将这些新特征作为向量输入逻辑回归模型，得到最终结果。
下图是Facebook公开的GBDT+LR模型示例，图中有两棵树，左树有三个叶子节点，右树有两个叶子节点，最终的特征为5维向量。对于输入x，如果它落在左树第一个节点，编码为[1，0，0]；如果落在右树第二个节点，则编码为[0，1]，所以整体的编码为[1，0，0，0，1]，将该编码作为特征输入LR模型中进行分类。
3.XGB和LGB省略
4.深度学习模型
4.1 Wide&Deep模型
推荐系统中有一个极具挑战的问题，就是需要让系统同时具有记忆和泛化能力。记忆能力的实现需要系统学习大量物品和特征的共现率，然后利用这些共现率挖掘历史数据的相关性。其在实现上需要对一系列宽泛的跨产品特性进行转换。记忆的优点是可解释性强，缺点是与用户已执行的操作项目直接相关。泛化能力的实现需要系统基于相关性转移，探索之前很少出现或从未出现过的新的交叉特征。其在实现上需要进行更多的特征工作，而且模型越深可能越有效。泛化的优点是可以提高推荐项目的多样性，缺点是当查询矩阵稀疏且秩高时，难以有效地学习低维表示。针对记忆和泛化能力的优劣之处，我们提出Wide和Deep相结合的方式，如下图所示。
前面曾介绍过集成模型，以及XGBoost在工业实践中取得的优异成绩。那么，Wide & Deep模型和集成模型有哪些异同点呢？集成模型中每个模型是单独训练的，Wide & Deep模型是联合训练并且同时优化所有参数。Wide & Deep模型训练方法如下图所示。
Wide&Deep模型，即广度和深度兼顾的模型，其基本思想在于，深度学习模型本身虽然有着较好的泛化能力，但是对于样本提供的直观特点记忆能力较弱；而广度模型，虽然对于训练样本本身的记忆较强，但是缺乏较好的泛化能力。结合两者，同时训练的Wide & Deep模型，由于最终的预测结果是由Wide部分与Deep部分耦合得来的，所以有着更强的表现效果。
1.AdaGrad算法
AdaGrad其实是对学习率进行了约束。该算法是将每一个参数的每一次迭代的梯度取平方累加后再开方，然后用全局学习率除以开方后的值，作为学习率的动态更新。
2.FTRL算法
4.2 Deep FM模型
随着推荐系统的广泛使用，基于CTR预估的推荐方法被广泛应用。而对于CTR推荐方法来说，最重要的就是理解用户行为背后的隐含的特征。在不同的场景下，低阶组合特征与高阶组合特征都可能对模型产生影响。因此，通用且方便快捷地提取有效的组合特征是CTR模型进化的主要方向。
FM考虑将特征交叉，这样就可以通过每一维特征的隐式变量内积来提取组合特征。虽然在理论上，我们可以无限度地去提取高维特征，但是考虑到模型的计算复杂度，一般不超过二阶的组合特征。这样往往可能错过更多有效的高阶组合特征。
DNN模型通过one-hot编码方式将各种复杂的离散特征扁平化处理成一维向量特征，以便学习理解。随着网络深度的拓展，DNN模型对高维特征的提取也更为有效。但是，由于我们追求的是方便、快捷、高效且通用的方法，因此希望在备选特征不明确的情况下，DNN模型有自动挑选特征的能力，能兼顾所有特征。在现实工作中，这些都会导致one-hot编码后，输入特征过大，网络模型参数过多，大大降低模型的性能，增加训练和使用成本。同时，DNN模型对于不同阶的特征是无法兼顾的。也就是说，随着对高维特征的提取，低维特征将无法有效地影响深度网络的输出结果。
在这种情况下，Deep FM方法应运而生。总体来说，Deep FM模型更像是FM模型与DNN模型的融合。一方面，该模型参考了FFM算法的思想，将不同的特征分到不同的场，然后利用一个全连接层对过大的特征进行压缩。压缩后的特征作为输入，可以有效地控制网络参数。另一方面，将FM计算后的低阶特征组合与DNN计算后的高阶特征组合作为输出，可以更直观有效地表述低阶特征组合与高阶特征组合对于最终结果的输出影响。
由此可以看出，Deep FM既保留了FM对于低阶特征的有效组合和特征筛选功能，又保留了DNN对于高阶特征的挑选功能，同时又避免了输入特征过大的情况，有效地解决了FM、FFM、DNN所带来的问题。
Deep FM可以看作是将Wide & Deep模型中LR模型换成了FM模型。Deep FM包含两部分：神经网络部分与因子分解机部分，分别负责高维特征的提取和低维特征的提取。这两部分共享同样的输入。Deep FM结构示意图如下图所示。
在稀疏特征层，所有特征按照既有的场分组，并分别按照给定的k（即隐向量长度）计算全连接层。所以，全连接层的长度为mk，其中m是特征的场数量。对于FM侧，在经过稠密嵌入层之后，FM层有了来自稀疏特征层准备求和的、带有待训练权重的原始特征，也有了来自稠密嵌入层准备交叉内积的、权重为1的隐向量特征。而对于DNN侧，所有的输入数据均来自全连接层，之后进入正常的隐藏层进行计算。最终，将来自FM侧与DNN侧的结果利用sigmoid激活函数结合，作为模型总的输出结果。
自此，Deep FM算法流程结束，而中间训练的过程中，参数的迭代与之前的FM和DNN并无差异。
在同类高阶特征的提取上，Deep FM有效提高了运算速度；在低阶特征组合与高阶特征组合的使用上，Deep FM更为有效、便捷甚至易懂；在特征工程上，Deep FM更是省去了大量烦琐的工作。当然，Deep FM也并非完美无缺，作为同时训练FM与DNN的结合模型，虽然使用了全连接层压缩输入向量，但模型训练的耗时仍然很长。