本人才疏学浅，不足之处欢迎大家指出和交流。

迟更几天，今天继续带来传统模型之MLR算法模型，这是一篇来自阿里盖坤团队的方案（LS-PLM），发表于2017年，但实际在2012年就已经提出并应用于实际业务中（膜拜ing），当时主流仍然是我们上一篇提到过的的LR模型，而本文作者创新性地提出了MLR(mixed logistic regression, 混合逻辑斯特回归)算法，引领了广告领域CTR预估算法的全新升级。总的来说，MLR算法创新地提出并实现了直接在原始空间学习特征之间的非线性关系，基于数据自动发掘可推广的模式，相比于人工来说效率和精度均有了大幅提升。下面我们一起来了解下细节。

原文：《Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction》

1、背景

CTR预估(click-through-rate prediction)是广告行业比较常见的问题，根据用户的历史行为来判断用户对广告点击的可能性。在常见工业场景中，该问题的输入往往是数以万计的稀疏特征向量，在进行特征交叉后会维数会更高，比较常见的就是采用逻辑回归模型加一些正则化，因为逻辑回归模型计算开销小且容易实现并行。之前提到的facebook的一篇论文（LR+GBDT）中先用树模型做分类之后再加一个逻辑回归模型，最后得出效果出奇的好，应该也是工业界比较常用的方法，同时树模型的选择或者说是再构造特征的特性也逐渐被大家所关注。另一种比较有效的就是因子分解模型系列，包括FM及其的其他变种，它们的主要思想就是构造交叉特征或者是二阶的特征来一起进行训练。

这篇文章中，作者主要提出了一种piece-wise的线性模型，并且给出了其在大规模数据上的训练算法，称之为LS-PLM(Large Scale Piecewise Linear Model)，LS-PLM采用了分治的思想，先分成几个局部再用线性模型拟合，这两部都采用监督学习的方式，来优化总体的预测误差，总的来说有以下优势：

端到端的非线性学习：从模型端自动挖掘数据中蕴藏的非线性模式，省去了大量的人工特征设计，这使得MLR算法可以端到端地完成训练，在不同场景中的迁移和应用非常轻松。通过分区来达到拟合非线性函数的效果；
可伸缩性（scalability）：与逻辑回归模型相似，都可以很好的处理复杂的样本与高维的特征，并且做到了分布式并行；
稀疏性: 对于在线学习系统，模型的稀疏性较为重要，所以采用了$L_{1}$和$L_{2,1}$正则化，模型的学习和在线预测性能更好。当然，目标函数非凸非光滑为算法优带来了新的挑战。

2、MLR总览

MLR就像它的名字一样，由很多个LR模型组合而成。用分片线性模式来拟合高维空间的非线性模式，形式化表述如下：

给定样本x，模型的预测p(y|x)分为两部分：首先根据
$\sigma（u_{j}^{T}x）$分割特征空间为m部分，其中m为给定的超参数，然后对于各部分计算$\eta（w_{j}^{T}x）$作为各部分的预测。函数g(⋅)确保了我们的模型满足概率函数的定义。当我们将softmax函数作为分割函数σ(x)，将sigmoid函数作为拟合函数η(x)的时候，该模型为：

此时我们的混合模型可以看做一个FOE模型：

目标损失函数为：

论文中一个直观的例子，如下图，LR不能拟合非线性数据，MLR可以拟合非线性数据，因为划分-训练模式。

这种菱形分界面（非线性数据）其实非常难学，但MLR在其中表现出色。通过控制分片数量m，可以平衡模型的拟合能力和过拟合。上图m=4。论文中m=12得到了不错的效果。

理论上来说，增大m可以带来无限制的非线性拟合能力，但是同样会增加计算、存储的开销，同时会带来过拟合的风险。具体如何选取m要结合实际情况取舍；

同时MLR还引入了结构化先验、分组稀疏、线性偏置、模型级联、增量训练、Common Feature Trick来提升模型性能。

针对MLR上面提到的各种特性，下面我们一一来介绍细节。

3、模型细节

3.1 结构化先验

MLR中非常重要的就是如何划分原始特征空间。

通过引入结构化先验，我们使用用户特征来划分特征空间，使用广告特征来进行基分类器的训练，减小了模型的探索空间，收敛更容易。

同时，这也是符合我们认知的：不同的人群具有聚类特性，同一类人群具有类似的广告点击偏好。

3.2 线性偏置

针对CTR预估问题中存在的两种偏置：

Position Bias：排名第1位和第5位的样本，点击率天然存在差异。宝贝展示的页面、位置影响点击率
Sample Bias：PC和Mobile上的样本，点击率天然存在差异。

在原来宝贝特征x的基础上，增加偏移向量y(场景、页数、位置等)。如果直接学习联合概率P(X,Y)面临问题：学习联合概率一定需要x和y的大部分组合，但是实际情况，并不是所有的x，y的组合都能有采样。针对这个问题，提出了带偏移MLR算法，形式化表述如下：

而且，大规模非线性CTR预估和偏移变量的分解一起优化。并且，只需要很少的一些x，y组合就可以了。从论文给出的数据中，AUC提高了2-8个百分点。

3.3 模型级联

盖坤在PPT讲解到，MLR支持与LR的级联式训练。有点类似于Wide & Deep，一些强Feature配置成级联形式能够提高模型的收敛性。例如典型的应用方法是：以统计反馈类特征构建第一层模型，输出FBctr级联到第二级大规模稀疏ID特征中去，能得到更好的提升效果。

反馈特征常用的如反馈CTR，是指系统上线一段时间之后得到的历史CTR值。

3.4 增量训练

实验证明，MLR利用结构先验（用户特征进行聚类，广告特征进行分类）进行pretrain，然后再增量进行全空间参数寻优训练，会使得收敛步数更少，收敛更稳定。

4、一些trick

论文的idea简单有效的，重点是工程中出来的论文，对工程实现上的优化细节都很详细，下面我们来看下：

4.1 并行化

论文里的实现基于分布式，包括两个维度的并行化，模型并行化，数据并行化。每一个计算节点中都包含两种角色：Server Node, Worker Node，这样做的好处有两点：

最大化利用CPU计算资源。之前大多数Server Node单独放到一台服务器上，造成CPU资源的极大浪费。
最大化利用Memory资源。

4.2 Common Feature Trick

一个用户在一次pageview中会看到多个广告，每个广告都组成一条样本。所以这些样本之间很多特征都是重复的。这些特征包括：用户特征（年龄、性别等）、用户的历史访问信息（之前购买的物品、喜欢的店铺等）。那么我们对于向量内积的计算分成两部分：common和non-common parts:

利用Common Feature Trick可以从三个方面来优化并行化：

对于有Common Feature的样本作为一组一起训练，并保证在存储在一个worker上
对于Common Feature仅仅保存一次，以便来节省内存
对于Common Feature的loss和梯度更新只需要一次即可

下面是实验结果：

可以看到Common Feature Trick效果还是非常明显的。

5、总结

文末说LS-PLM在2012年就应用于阿里巴巴的ctr预估，到2017年才发表论文。不出意料，现在的模型应该已经不再是MLR这么简单了。
另外，从MLR和LR进行级联，以便加强强特征来看，MLR还是有很大的局限性。个人感觉模型从理论上来说确实非常棒，利用分片线性来模型高维非线性，但是虽然取得了非常不错的成绩，但是带来的挑战也不小：比如初值问题、非凸问题的局部极值、虽然MLR比LR好，但不知道和全局最优相比还有多远；第二，在初值的Pre-train方面需要改进和优化模型函数等等；第三，目前规模化能力方面也需要能够吞吐更多特征和数据，比如采用更快的收敛算法等等；最后，整体的MLR算法的抽象能力也需进一步得到强化。

实现MLR的一个Demo，感兴趣的童鞋可以看下我的[github]