浅层模型

在互联网永不停歇的增长需求的驱动下，CTR预估模型（以下简称CTR模型）的发展也可谓一日千里，从2010年之前千篇一律的逻辑回归（Logistic Regression，LR），进化到因子分解机（Factorization Machine，FM）、梯度提升树（Gradient Boosting Decision Tree，GBDT），再到2015年之后深度学习的百花齐放，各种模型架构层出不穷。认真的回顾前深度学习时代的CTR模型仍是非常必要的。原因有两点：

即使是深度学习空前流行的今天，LR、FM等传统CTR模型仍然凭借其可解释性强、轻量级的训练部署要求、便于在线学习等不可替代的优势，拥有大量适用的应用场景。模型的应用不分新旧贵贱，熟悉每种模型的优缺点，能够灵活运用和改进不同的算法模型是算法工程师的基本要求。
传统CTR模型是深度学习CTR模型的基础。深度神经网络（Deep Nerual Network，DNN）从一个神经元生发而来，而LR正是单一神经元的经典结构；此外，影响力很大的FNN，DeepFM，NFM等深度学习模型更是与传统的FM模型有着千丝万缕的联系；更不要说各种梯度下降方法的一脉相承。所以说传统CTR模型是深度学习模型的地基和入口。

看到上面的关系图，有经验的同学可能已经对各模型的细节和特点如数家珍了。中间位置的LR模型向四个方向的延伸分别代表了传统CTR模型演化的四个方向。

向下为了解决特征交叉的问题，演化出PLOY2，FM，FFM等模型；
向右为了使用模型化、自动化的手段解决之前特征工程的难题，Facebook将LR与GBDT进行结合，提出了GBDT+LR组合模型；
向左Google从online learning的角度解决模型时效性的问题，提出了FTRL；
向上阿里基于样本分组的思路增加模型的非线性，提出了LS-PLM（MLR）模型。

LR——CTR模型的核心和基础

位于正中央的是当之无愧的Logistic Regression。仍记得2012年的时候，各大中小公司的主流CTR模型无一例外全都是LR模型。LR模型的流行是有三方面原因的，一是数学形式和含义上的支撑；二是人类的直觉和可解释性的原因；三是工程化的需要。

逻辑回归的数学基础

逻辑回归作为广义线性模型的一种，它的假设是因变量y服从伯努利分布。那么在点击率预估这个问题上，“点击”这个事件是否发生就是模型的因变量y。而用户是否点击广告这个问题是一个经典的掷偏心硬币问题，因此CTR模型的因变量显然应该服从伯努利分布。所以采用LR作为CTR 模型是符合“点击”这一事件的物理意义的。

与之相比较，线性回归（Linear Regression）作为广义线性模型的另一个特例，其假设是因变量y服从高斯分布，这明显不是点击这类二分类问题的数学假设。

在了解LR的数学理论基础后，其数学形式就不再是空中楼阁了，具体的形式如下：

其中 $x$ 是输入向量， $\theta$ 是我们要学习的参数向量。结合CTR模型的问题来说， $x$ 就是输入的特征向量， $h_\theta(x)$ 就是我们最终希望得到的点击率。

人类的直觉和可解释性

直观来讲，LR模型目标函数的形式就是各特征的加权和，再施以sigmoid函数。忽略其数学基础（虽然这是其模型成立的本质支撑），仅靠人类的直觉认知也可以一定程度上得出使用LR作为CTR模型的合理性。

使用各特征的加权和是为了综合不同特征对CTR的影响，而由于不同特征的重要程度不一样，所以为不同特征指定不同的权重来代表不同特征的重要程度。最后要套上sigmoid函数，正是希望其值能够映射到0-1之间，使其符合CTR的物理意义。

LR如此符合人类的直觉认知显然有其他的好处，就是模型具有极强的可解释性，算法工程师们可以轻易的解释哪些特征比较重要，在CTR模型的预测有偏差的时候，也可以轻易找到哪些因素影响了最后的结果，如果你有跟运营、产品一起工作的经验的话，更会知道可解释性强是一个模型多么优秀的“品质”。

工程化的需要

在互联网公司每天动辄TB级别的数据面前，模型的训练开销就异常重要了。在GPU尚未流行开来的2012年之前，LR模型也凭借其易于并行化、模型简单、训练开销小等特点占据着工程领域的主流。囿于工程团队的限制，即使其他复杂模型的效果有所提升，在没有明显beat LR之前，公司也不会贸然加大计算资源的投入升级CTR模型，这是LR持续流行的另一重要原因。

POLY2——特征交叉的开始

但LR的表达能力毕竟是非常初级的。由于LR仅使用单一特征，无法利用高维信息，在“辛普森悖论”现象的存在下，只用单一特征进行判断，甚至会得出错误的结论。

针对这个问题，当时的算法工程师们经常采用手动组合特征，再通过各种分析手段筛选特征的方法。但这个方法无疑是残忍的，完全不符合“懒惰是程序员的美德”这一金科玉律。更遗憾的是，人类的经验往往有局限性，程序员的时间和精力也无法支撑其找到最优的特征组合。因此采用 PLOY2模型进行特征的“暴力”组合成为了可行的选择。

在上面POLY2二阶部分的目标函数中（上式省略一阶部分和sigmoid函数的部分），我们可以看到POLY2对所有特征进行了两两交叉，并对所有的特征组合赋予了权重 $w_{h(j_1,j_2)}$ 。POLY2通过暴力组合特征的方式一定程度上解决了特征组合的问题。并且由于本质上仍是线性模型，其训练方法与LR并无区别，便于工程上的兼容。

但POLY2这一模型同时存在着两个巨大的缺陷：

由于在处理互联网数据时，经常采用one-hot的方法处理id类数据，致使特征向量极度稀疏，POLY2进行无选择的特征交叉使原本就非常稀疏的特征向量更加稀疏，使得大部分交叉特征的权重缺乏有效的数据进行训练，无法收敛。
权重参数的数量由 $n$ 直接上升到 $n^2$ ，极大增加了训练复杂度。

FM——隐向量特征交叉

为了解决POLY2模型的缺陷，2010年德国康斯坦茨大学的Steffen Rendle提出了FM（Factorization Machine）

从FM的目标函数的二阶部分中我们可以看到，相比POLY2，主要区别是用两个向量的内积 $(w_{j_1}\cdot w_{j_2})$ 取代了单一的权重 $w_{h(j_1,j_2)}$ 。具体来说，FM为每个特征学习了一个隐权重向量（latent vector），在特征交叉时，使用两个特征隐向量的内积作为交叉特征的权重。

通过引入特征隐向量的方式，直接把原先 $n^2$ 级别的权重数量减低到了 $n*k$ （ $k$ 为隐向量维度， $n\gg k$ ）。在训练过程中，又可以通过转换目标函数形式的方法，使FM的训练复杂度进一步降低到 $n*k$ 级别。相比POLY2极大降低训练开销。

隐向量的引入还使得FM比POLY2能够更好的解决数据稀疏性的问题。举例来说，我们有两个特征，分别是channel和brand，一个训练样本的feature组合是(ESPN, Adidas)，在POLY2中，只有当ESPN和Adidas同时出现在一个训练样本中时，模型才能学到这个组合特征对应的权重。而在FM中，ESPN的隐向量也可以通过(ESPN, Gucci)这个样本学到，Adidas的隐向量也可以通过(NBC, Adidas)学到，这大大降低了模型对于数据稀疏性的要求。甚至对于一个从未出现过的特征组合(NBC, Gucci)，由于模型之前已经分别学习过NBC和Gucci的隐向量，FM也具备了计算该特征组合权重的能力，这是POLY2无法实现的。也许FM相比POLY2丢失了某些信息的记忆能力，但是泛化能力大大提高，这对于互联网的数据特点是非常重要的。

工程方面，FM同样可以用梯度下降进行学习的特点使其不失实时性和灵活性。相比之后深度学习模型复杂的网络结构，FM比较容易实现的inference过程也使其没有serving的难题。因此FM在2012-2014年前后逐渐成为业界CTR模型的重要选择。

从LR到SVM再到FM模型

LR模型是CTR预估领域早期最成功的模型，大多工业推荐排序系统采取LR这种“线性模型+人工特征组合引入非线性”的模式。因为LR模型具有简单方便易解释容易上规模等诸多好处，所以目前仍然有不少实际系统仍然采取这种模式。但是，LR模型最大的缺陷就是人工特征工程，耗时费力费人力资源，那么能否将特征组合的能力体现在模型层面呢？

其实想达到这一点并不难，如上图在计算公式里加入二阶特征组合即可，任意两个特征进行组合，可以将这个组合出的特征看作一个新特征，融入线性模型中。而组合特征的权重可以用来表示，和一阶特征权重一样，这个组合特征权重在训练阶段学习获得。其实这种二阶特征组合的使用方式，和多项式核SVM是等价的。虽然这个模型看上去貌似解决了二阶特征组合问题了，但是它有个潜在的问题：它对组合特征建模，泛化能力比较弱，尤其是在大规模稀疏特征存在的场景下，这个毛病尤其突出，比如CTR预估和推荐排序，这些场景的最大特点就是特征的大规模稀疏。所以上述模型并未在工业界广泛采用。那么，有什么办法能够解决这个问题吗？

于是，FM模型此刻可以闪亮登场了。如上图所示，FM模型也直接引入任意两个特征的二阶特征组合，和SVM模型最大的不同，在于特征组合权重的计算方法。FM对于每个特征，学习一个大小为k的一维向量，于是，两个特征和的特征组合的权重值，通过特征对应的向量和的内积来表示。这本质上是在对特征进行embedding化表征，和目前非常常见的各种实体embedding本质思想是一脉相承的，但是很明显在FM这么做的年代（2010年），还没有现在能看到的各种眼花缭乱的embedding的形式与概念。所以FM作为特征embedding，可以看作当前深度学习里各种embedding方法的老前辈。当然，FM这种模式有它的前辈模型吗？有，等会会谈。其实，和目前的各种深度DNN排序模型比，它仅仅是少了2层或者3层MLP隐层，用来直接对多阶特征非线性组合建模而已，其它方面基本相同。

那么为什么说FM的这种特征embedding模式，在大规模稀疏特征应用环境下比较好用？为什么说它的泛化能力强呢？参考上图说明。即使在训练数据里两个特征并未同时在训练实例里见到过，意味着一起出现的次数为0，如果换做SVM的模式，是无法学会这个特征组合的权重的。但是因为FM是学习单个特征的embedding，并不依赖某个特定的特征组合是否出现过，所以只要特征和其它任意特征组合出现过，那么就可以学习自己对应的embedding向量。于是，尽管这个特征组合没有看到过，但是在预测的时候，如果看到这个新的特征组合，因为和都能学会自己对应的embedding，所以可以通过内积算出这个新特征组合的权重。这是为何说FM模型泛化能力强的根本原因。

其实本质上，这也是目前很多花样的embedding的最核心特点，就是从0/1这种二值硬核匹配，切换为向量软匹配，使得原先匹配不上的，现在能在一定程度上算密切程度了，具备很好的泛化性能。

从MF到FM模型

FM我们大致应该知道是怎么个意思了，这里又突然冒出个MF，长得跟FM貌似还有点像，那么MF又是什么呢？它跟FM又有什么关系？

请跟我念：“打东边来了个FM，手里提着一斤挞嘛；打西边来了个MF，腰里别着一个喇叭；提着一斤挞嘛的FM想要别着喇叭的MF腰里的喇叭……..”你要是能不打磕绊一遍念下来的话………你以为你就理解它们的错综复杂的关系了是吗？不，你就可以去学说相声了……

MF（Matrix Factorization，矩阵分解）模型是个在推荐系统领域里资格很深的老前辈协同过滤模型了。核心思想是通过两个低维小矩阵（一个代表用户embedding矩阵，一个代表物品embedding矩阵）的乘积计算，来模拟真实用户点击或评分产生的大的协同信息稀疏矩阵，本质上是编码了用户和物品协同信息的降维模型。

当训练完成，每个用户和物品得到对应的低维embedding表达后，如果要预测某个对的评分的时候，只要它们做个内积计算，这个得分就是预测得分。看到这里，让你想起了什么吗？

身为推荐算法工程师，我假设你对它还是比较熟悉的，更多的就不展开说了，相关资料很多，我们重点说MF和FM的关系问题。

MF和FM不仅在名字简称上看着有点像，其实他们本质思想上也有很多相同点。那么，MF和FM究竟是怎样的关系呢？

本质上，MF模型是FM模型的特例，MF可以被认为是只有User ID 和Item ID这两个特征Fields的FM模型，MF将这两类特征通过矩阵分解，来达到将这两类特征embedding化表达的目的。而FM则可以看作是MF模型的进一步拓展，除了User ID和Item ID这两类特征外，很多其它类型的特征，都可以进一步融入FM模型里，它将所有这些特征转化为embedding低维向量表达，并计算任意两个特征embedding的内积，就是特征组合的权重，如果FM只使用User ID 和Item ID，你套到FM公式里，看看它的预测过程和MF的预测过程一样吗？

从谁更早使用特征embedding表达这个角度来看的话，很明显，和FM比起来，MF才是真正的前辈，无非是特征类型比较少而已。而FM继承了MF的特征embedding化表达这个优点，同时引入了更多Side information作为特征，将更多特征及Side information embedding化融入FM模型中。所以很明显FM模型更灵活，能适应更多场合的应用范围。

鉴于MF和FM以上错综复杂剪不断理还乱的关系，我推论出下面的观点（个人意见）：

其一：在你有使用MF做协同过滤的想法的时候，暂时压抑一下这种冲动，可以优先考虑引入FM来做的，而非传统的MF，因为可以在实现等价功能的基础上，很方便地融入其它任意你想加入的特征，把手头的事情做得更丰富多彩。

其二：从实际大规模数据场景下的应用来讲，在排序阶段，绝大多数只使用ID信息的模型是不实用的，没有引入Side Information，也就是除了User ID／Item ID外的很多其它可用特征的模型，是不具备实战价值的。原因很简单，大多数真实应用场景中，User/Item有很多信息可用，而协同数据只是其中的一种，引入更多特征明显对于更精准地进行个性化推荐是非常有帮助的。而如果模型不支持更多特征的便捷引入，明显受限严重，很难真正实用，这也是为何矩阵分解类的方法很少看到在Ranking阶段使用，通常是作为一路召回形式存在的原因。

如何优化FM的计算效率

再说回来，FM如今被广泛采用并成功替代LR模型的一个关键所在是：它可以通过数学公式改写，把表面貌似是的复杂度降低到，其中n是特征数量，k是特征的embedding size，这样就将FM模型改成了和LR类似和特征数量n成线性规模的时间复杂度了，这点非常好。

那么，如何改写原始的FM数学公式，让其复杂度降下来呢？因为原始论文在推导的时候没有给出详细说明，我相信不少人看完估计有点懵，所以这里简单解释下推导过程，数学公式帕金森病患者可以直接跳过下面内容往后看，这并不影响你理解本文的主旨。

上图展示了整个推导过程，我相信如果数学基础不太扎实的同学看着会有点头疼，转换包括四个步骤，下面分步骤解释下。

第一个改写步骤及为何这么改写参考上图，比较直观，不解释了；

第二步转换更简单，更不用解释了。

第三步转换不是太直观，可能需要简单推导一下，很多人可能会卡在这一步，所以这里解释。

其实吧，如果把k维特征向量内积求和公式抽到最外边后，公式就转成了上图这个公式了（不考虑最外边k维求和过程的情况下）。它有两层循环，内循环其实就是指定某个特征的第f位（这个f是由最外层那个k指定的）后，和其它任意特征对应向量的第f位值相乘求和；而外循环则是遍历每个的第f位做循环求和。这样就完成了指定某个特征位f后的特征组合计算过程。最外层的k维循环则依此轮循第f位，于是就算完了步骤三的特征组合。

对上一页公式图片展示过程用公式方式，再一次改写（参考上图），其实就是两次提取公共因子而已，这下应该明白了吧？要是还不明白，那您的诊断结果是数学公式帕金森晚期，跟我一个毛病，咱俩病友同病相怜，我也没辙了。

第四步公式变换，意思参考上图，这步也很直白，不解释。

于是，通过上述四步的公式改写，可以看出在实现FM模型时，时间复杂度就降低到了了，而虽说看上去n还有点大，但是其实真实的推荐数据的特征值是极为稀疏的，就是说大量xi其实取值是0，意味着真正需要计算的特征数n是远远小于总特征数目n的，无疑这会进一步极大加快FM的运算效率。

这里需要强调下改写之后的FM公式的第一个平方项，怎么理解这个平方项的含义呢？这里其实蕴含了后面要讲的使用FM模型统一多路召回的基本思想，所以这里特殊提示一下。

参考上图，你体会下这个计算过程。它其实等价于什么？

这个平方项，它等价于将FM的所有特征项的embedding向量累加，之后求内积。我再问下之前问过的问题：“我们怎样利用FM模型做统一的召回？”这个平方项的含义对你有启发吗？你可以仔细想想它们之间的关联。

FFM——引入特征域概念

2015年，基于FM提出的FFM（Field-aware Factorization Machine ，简称FFM）在多项CTR预估大赛中一举夺魁，并随后被Criteo、美团等公司深度应用在CTR预估，推荐系统领域。相比FM模型，FFM模型主要引入了Field-aware这一概念，使模型的表达能力更强。

上式是FFM的目标函数的二阶部分。其与FM目标函数的区别就在于隐向量由原来的 $w_{j_1}$ 变成了 $w_{j_1,f_2}$ ，这就意味着每个特征对应的不是一个隐向量，而是对应着不同域的一组隐向量，当 $w_{j_1}$ 特征与 $w_{j_2}$ 特征进行交叉时， $x_{j_1}$ 特征会从一组隐向量中挑出与特征 $x_{j_2}$ 的域 $f_2$ 对应的隐向量 $w_{j_1,f_2}$ 进行交叉。同理特征 $x_{j_2}$ 也会用与 $x_{j_1}$ 的域 $f_1$ 对应的隐向量进行交叉。

这里再次强调一下，上面所说的“域”就代表着特征域，域内的特征一般会采用one-hot编码形成one-hot特征向量。

FFM模型学习每个特征在 $f$ 个域上的 $k$ 维隐向量，交叉特征的权重由特征在对方特征域上的隐向量内积得到，权重数量共 $n*k*f$ 个。在训练方面，由于FFM的二次项并不能够像FM那样简化，因此其复杂度为 $kn^2$ 。

相比FM，FFM由于引入了field这一概念，为模型引入了更多有价值信息，使模型表达能力更强，但与此同时，FFM的计算复杂度上升到 $kn^2$ ，远远大于FM的 $k*n$ 。

CTR模型特征交叉方向的演化

以上模型实际上是CTR模型朝着特征交叉的方向演化的过程，我们再用图示方法回顾一下从POLY2到FM，再到FFM进行特征交叉方法的不同。

POLY2模型直接学习每个交叉特征的权重，权重数量共 $n^2$ 个。

FM模型学习每个特征的 $k$ 维隐向量，交叉特征由相应特征隐向量的内积得到，权重数量共 $n*k$ 个。

FFM模型引入了特征域这一概念，在做特征交叉时，每个特征选择与对方域对应的隐向量做内积运算得到交叉特征的权重。参数数量共 $n*k*f$ 个。

从FM到FFM

FFM的全称是Field-aware FM，直观翻译过来，就是能够意识到特征域(Field)的存在的FM模型。那么FFM模型是有第六感吗？它怎么能够感知到特征域的存在呢？这里先不解释，后面会说明。我们先看个例子。

上图是一个人造的广告CTR的数据例子，代表的意思是在某个网站（Publisher）上刊登一则广告（Advertiser），某个用户（用户性别特征Gender）是否会点击某条广告的数据。这个例子中假设包含三个特征域（Field）:网站Publisher(可能的特征值是ESPN、Vogue、NBC)、广告（可能的特征值是Nike、Adidas、Gucci）和性别特征Gender(可能的特征值是Male、Female)。由这个例子可以看出组合特征的重要性：如果在体育网站ESPN上发布Nike的广告，那么100次展现，80次会被点击，而20次不会被点击。意味着组合特征（Publisher=”ESPN” and Advertiser=”Nike”）是个很强的预测用户是否点击的二阶组合特征。上图同时展示了一条用户点击记录。

我们用这个例子来说明FFM的基本思想，FM模型可以看做是FFM模型的一个特例，所以在说明FFM模型思想之前，我们先用上述例子说明FM的思想，然后通过和FM模型的对比，很容易理解FFM模型的基本思路。

FM模型在做二阶特征组合的时候，对于每个二阶组合特征的权重，是根据对应两个特征的Embedding向量内积，来作为这个组合特征重要性的指示。当训练好FM模型后，每个特征都可以学会一个特征embedding向量，参考上图。当做预测的时候，比如我们接收到上面例子的数据，需要预测用户是否会点击这条广告，则对三个特征做两两组合，每个组合特征的权重，可以根据两个对应的特征embedding内积求得，对所有组合特征求和后，套接Sigmoid函数即可做出二分类预测。

对于FM模型来说，每个特征学会唯一的一个特征embedding向量，注意，在这里，和FFM的最大不同点冒出来了。为了更容易向FFM模型理解过渡，我们可以这么理解FM模型中的某个特征的embedding：拿Vespn这个特征作为例子，当这个特征和其它特征域的某个特征进行二阶特征组合的时候，不论哪个特征域的特征和Vespn特征进行组合，Vespn这个特征都反复使用同一个特征embedding去做内积，所以可以理解为Vespn这个特征在和不同特征域特征进行组合的时候，共享了同一个特征向量。

沿着这个思路思考，我会问出一个问题：我们可以改进下FM模型吗？怎么改进？下图给个提示。

如果你对算法敏感的话，你可以这么回答我：既然FM模型的某个特征，在和任意其它特征域的特征进行组合求权重的时候，共享了同一个特征向量。那么，如果我们把这个事情做地更细致些，比如Vespn这个特征，当它和Nike（所属特征域Advertiser）组合的时候用一个特征embedding向量，而当它和Male(所属特征域Gendor)组合的时候，使用另外一个特征embedding向量，这样是否在描述特征组合的时候更细腻一些？也就是说，当Vespn这个特征和属于Advertiser这个域的特征进行组合的时候，用一个特征embedding；和属于Gendor这个特征域的特征进行组合的时候，用另外一个特征embedding。这意味着，如果有F个特征域，那么每个特征由FM模型的一个k维特征embedding，拓展成了（F-1）个k维特征embedding。之所以是F-1，而不是F，是因为特征不和自己组合，所以不用考虑自己。这样行吗？

嗯，你说的很有道理，是的，这其实就是FFM模型的基本思想。所以从上面两个图的示意可以看出，为何说FM模型是FFM模型的特例。

我们再回头看下刚才那个点击数据的例子，看看在FFM场景下是怎样应用的，上图展示了这个过程。因为这个例子有三个特征域，所以Vespn有两个特征embedding，当和Nike特征组合的时候，用的是针对Advertisor这个特征域的embedding去做内积；而当和Male这个特征组合的时候，则用的是针对Gendor这个特征域的embedding去做内积。同理，Nike和Male这两个特征也是根据和它组合特征所属特征域的不同，采用不同的特征向量去做内积。而两两特征组合这个事情的做法，FFM和FM则是完全相同的，区别就是每个特征对应的特征embedding个数不同。FM每个特征只有一个共享的embedding向量，而对于FFM的一个特征，则有（F-1）个特征embedding向量，用于和不同的特征域特征组合时使用。

从上面的模型演化过程，你可以体会到，为何这篇文章的标题将FFM模型称为笨重，它笨重在哪里？说它笨重，是和FM模型相比较而言的。我们可以推出，假设模型具有n个特征，那么FM模型的参数量是n*k（暂时忽略掉一阶特征的参数），其中k是特征向量大小。而FFM模型的参数量呢？因为每个特征具有（F-1）个k维特征向量，所以它的模型参数量是(F-1)*n*k，也就是说参数量比FM模型扩充了(F-1)倍。这意味着，如果我们的任务有100个特征域，FFM模型的参数量就是FM模型的大约100倍。这其实是很恐怖的，因为现实任务中，特征数量n是个很大的数值，特征域几十上百也很常见。另外，我们在上一篇介绍FM模型的文章里也讲过，FM模型可以通过公式改写，把本来看着是n的平方的计算复杂度，降低到。而FFM无法做类似的改写，所以它的计算复杂度是，这明显在计算速度上也比FM模型慢得多。所以，无论是急剧膨胀的参数量，还是变慢的计算速度，无论从哪个角度看，相对FM模型，FFM模型是略显笨重的。

正因为FFM模型参数量太大，所以在训练FFM模型的时候，很容易过拟合，需要采取早停等防止过拟合的手段。而根据经验，FFM模型的k值可以取得小一些，一般在几千万训练数据规模下，取8到10能取得较好的效果，当然，k具体取哪个数值，这其实跟具体训练数据规模大小有关系，理论上，训练数据集合越大，越不容易过拟合，这个k值可以设置得越大些。

GBDT+LR——特征工程模型化的开端

FFM模型采用引入特征域的方式增强了模型的表达能力，但无论如何，FFM只能够做二阶的特征交叉，如果要继续提高特征交叉的维度，不可避免的会发生组合爆炸和计算复杂度过高的情况。那么有没有其他的方法可以有效的处理高维特征组合和筛选的问题？2014年，Facebook提出了基于GBDT+LR组合模型的解决方案。

简而言之，Facebook提出了一种利用GBDT自动进行特征筛选和组合，进而生成新的离散特征向量，再把该特征向量当作LR模型输入，预估CTR的模型结构。

需要强调的是，用GBDT构建特征工程，和利用LR预估CTR两步是独立训练的。所以自然不存在如何将LR的梯度回传到GBDT这类复杂的问题，而利用LR预估CTR的过程前面已经有所介绍，在此不再赘述，下面着重讲解如何利用GBDT构建新的特征向量。

大家知道，GBDT是由多棵回归树组成的树林，后一棵树利用前面树林的结果与真实结果的残差做为拟合目标。每棵树生成的过程是一棵标准的回归树生成过程，因此每个节点的分裂是一个自然的特征选择的过程，而多层节点的结构自然进行了有效的特征组合，也就非常高效的解决了过去非常棘手的特征选择和特征组合的问题。

利用训练集训练好GBDT模型之后，就可以利用该模型完成从原始特征向量到新的离散型特征向量的转化。具体过程是这样的，一个训练样本在输入GBDT的某一子树后，会根据每个节点的规则最终落入某一叶子节点，那么我们把该叶子节点置为1，其他叶子节点置为0，所有叶子节点组成的向量即形成了该棵树的特征向量，把GBDT所有子树的特征向量连接起来，即形成了后续LR输入的特征向量。

举例来说，如上图所示，GBDT由三颗子树构成，每个子树有4个叶子节点，一个训练样本进来后，先后落入“子树1”的第3个叶节点中，那么特征向量就是[0,0,1,0]，“子树2”的第1个叶节点，特征向量为[1,0,0,0]，“子树3”的第4个叶节点，特征向量为[0,0,0,1]，最后连接所有特征向量，形成最终的特征向量[0,0,1,0,1,0,0,0,0,0,0,1]。

由于决策树的结构特点，事实上，决策树的深度就决定了特征交叉的维度。如果决策树的深度为4，通过三次节点分裂，最终的叶节点实际上是进行了3阶特征组合后的结果，如此强的特征组合能力显然是FM系的模型不具备的。但由于GBDT容易产生过拟合，以及GBDT这种特征转换方式实际上丢失了大量特征的数值信息，因此我们不能简单说GBDT由于特征交叉的能力更强，效果就比FFM好，在模型的选择和调试上，永远都是多种因素综合作用的结果。

GBDT+LR比FM重要的意义在于，它大大推进了特征工程模型化这一重要趋势，某种意义上来说，之后深度学习的各类网络结构，以及embedding技术的应用，都是这一趋势的延续。

在之前所有的模型演化过程中，实际上是从特征工程这一角度来推演的。接下来，我们从时效性这个角度出发，看一看模型的更新频率是如何影响模型效果的。

在模型更新这个问题上，我们的直觉是模型的训练时间和serving时间之间的间隔越短，模型的效果越好，为了证明这一点，facebook的工程师还是做了一组实效性的实验（如上图），在结束模型的训练之后，观察了其后6天的模型loss（这里采用normalized entropy作为loss）。可以看出，模型的loss在第0天之后就有所上升，特别是第2天过后显著上升。因此daily update的模型相比weekly update的模型效果肯定是有大幅提升的。

如果说日更新的模型比周更新的模型的效果提升显著，我们有没有方法实时引入模型的效果反馈数据，做到模型的实时更新从而进一步提升CTR模型的效果呢？Google 2013年应用的FTRL给了我们答案。

FTRL——天下武功，唯快不破

FTRL的全称是Follow-the-regularized-Leader，是一种在线实时训练模型的方法，Google在2010年提出了FTRL的思路，2013年实现了FTRL的工程化，之后快速成为online learning的主流方法。与模型演化图中的其他模型不同，FTRL本质上是模型的训练方法。虽然Google的工程化方案是针对LR模型的，但理论上FTRL可以应用在FM，NN等任何通过梯度下降训练的模型上。

为了更清楚的认识FTRL，这里对梯度下降方法做一个简要的介绍，从训练样本的规模角度来说，梯度下降可以分为：batch，mini-batch，SGD（随机梯度下降）三种，batch方法每次都使用全量训练样本计算本次迭代的梯度方向，mini-batch使用一小部分样本进行迭代，而SGD每次只利用一个样本计算梯度。对于online learning来说，为了进行实时得将最新产生的样本反馈到模型中，SGD无疑是最合适的训练方式。

但SGD对于互利网广告和推荐的场景来说，有比较大的缺陷，就是难以产生稀疏解。为什么稀疏解对于CTR模型如此重要呢？

之前我们已经多次强调，由于one hot等id类特征处理方法导致广告和推荐场景下的样本特征向量极度稀疏，维度极高，动辄达到百万、千万量级。为了不割裂特征选择和模型训练两个步骤，如果能够在保证精度的前提下尽可能多的让模型的参数权重为0，那么我们就可以自动过滤掉这些权重为0的特征，生成一个“轻量级”的模型。“轻量级”的模型不仅会使样本部署的成本大大降低，而且可以极大降低模型inference的计算延迟。这就是模型稀疏性的重要之处。

而SGD由于每次迭代只选取一个样本，梯度下降的方向虽然总体朝向全局最优解，但微观上的运动的过程呈现布朗运动的形式，这就导致SGD会使几乎所有特征的权重非零。即使加入L1正则化项，由于CPU浮点运算的结果很难精确的得到0的结果，也不会完全解决SGD稀疏性差的问题。就是在这样的前提下，FTRL几乎完美地解决了模型精度和模型稀疏性兼顾的训练问题。

但FTRL的提出也并不是一蹴而就的。如上图所示，FTRL的提出经历了下面几个关键的过程：

从最近简单的SGD到OGD（online gradient descent），OGD通过引入L1正则化简单解决稀疏性问题；
从OGD到截断梯度法，通过暴力截断小数值梯度的方法保证模型的稀疏性，但损失了梯度下降的效率和精度；
FOBOS（Forward-Backward Splitting），google和伯克利对OGD做进一步改进，09年提出了保证精度并兼顾稀疏性的FOBOS方法；
RDA：微软抛弃了梯度下降这条路，独辟蹊径提出了正则对偶平均来进行online learning的方法，其特点是稀疏性极佳，但损失了部分精度。
Google综合FOBOS在精度上的优势和RDA在稀疏性上的优势，将二者的形式进行了进一步统一，提出并应用FTRL，使FOBOS和RDA均成为了FTRL在特定条件下的特殊形式。 FTRL的算法细节对于初学者来说仍然是晦涩的，建议非专业的同学仅了解其特点和应用场景即可。对算法的数学形式和实现细节感兴趣的同学，我强烈推荐微博冯扬写的“在线最优化求解”一文，希望能够帮助大家进一步熟悉FTRL的技术细节。

LS-PLM——阿里曾经的主流CTR模型

下面我们从样本pattern本身来入手，介绍阿里的的LS-PLM（Large Scale Piece-wise Linear Model），它的另一个更广为人知的名字是MLR（Mixed Logistic Regression）。MLR模型虽然在2017年才公之于众，但其早在2012年就是阿里主流的CTR模型，并且在深度学习模型提出之前长时间应用于阿里的各类广告场景。

本质上，MLR可以看做是对LR的自然推广，它在LR的基础上采用分而治之的思路，先对样本进行分片，再在样本分片中应用LR进行CTR预估。在LR的基础上加入聚类的思想，其动机其实来源于对计算广告领域样本特点的观察。

举例来说，如果CTR模型要预估的是女性受众点击女装广告的CTR，显然我们并不希望把男性用户点击数码类产品的样本数据也考虑进来，因为这样的样本不仅对于女性购买女装这样的广告场景毫无相关性，甚至会在模型训练过程中扰乱相关特征的权重。为了让CTR模型对不同用户群体，不用用户场景更有针对性，其实理想的方法是先对全量样本进行聚类，再对每个分类施以LR模型进行CTR预估。MLR的实现思路就是由该动机产生的。

MLR目标函数的数学形式如上式，首先用聚类函数π对样本进行分类（这里的π采用了softmax函数，对样本进行多分类），再用LR模型计算样本在分片中具体的CTR，然后将二者进行相乘后加和。

其中超参数分片数m可以较好地平衡模型的拟合与推广能力。当m=1时MLR就退化为普通的LR，m越大模型的拟合能力越强，但是模型参数规模随m线性增长，相应所需的训练样本也随之增长。在实践中，阿里给出了m的经验值为12。

下图中MLR模型用4个分片可以完美地拟合出数据中的菱形分类面。

MLR算法适合于工业级的广告、推荐等大规模稀疏数据场景问题。主要是由于表达能力强、稀疏性高等两个优势：