一、技术背景
CTR(Click-Through-Rate)即点击通过率，是指网络广告的点击到达率。网络广告包括：文字广告、图片广告、关键词广告、排名广告、视频广告等。CTR预估是很多互联网主流应用（广告、搜索、推荐）的核心算法问题，包括Google和Facebook都一直在投入研究该领域。
二、研究现状
传统的CTR预估主要是使用Logistic Regression，外加人为特征工程。LR是线性模型，它的学习能力有限，所以需要引入大量的领域知识人为进行特征工程，构造交叉特征来间接补充算法的非线性拟合能力。但是LR模型的优点是可以很容易的实现并行化，轻松的处理上亿条训练样本不成问题。
之后，业界一直在研究新的非线性模型。有成果但是也伴随着一些缺点，比如Kernel方法，因为复杂度太高在高维度稀疏输入的前提下很难实现；Facebook在2014年提出了LR + GBDT的模型，Tree-Based有效的解决了LR模型的特征组合问题，但是输入全是id的情况下，树模型更多的是对历史行为的一种记忆，缺乏推广性；FM（Factorization Machine）模型能够自动学习高阶特征的权重，不用人工来做特征交叉，而且解决了在高维度样本下数据量不充分导致的问题，但是FM模型只能拟合特定的非线性模式。比如最常用的二阶FM模型，只能拟合线性模式和二阶非线性模式，缺乏对高阶非线性模式的学习。深度神经网络的非线性拟合能力非常强，但是面对广告这种大规模工业级稀疏数据，适合数据规律、具备推广性的模型结构仍然在探索中。
那么如何从大规模工业级稀疏数据中，挖掘出一个具备推广性的非线性模型那？
三、MLR算法
2011-2012年期间，阿里妈妈盖坤团队给出了答案：MLR(mixed logistic regression)，在论文中的名称是LS-PLM(Large Scale Piece-wise Linear Model).
总的来说，MLR应用分而治之的思想，通过将特征空间划分成多个区域，每个区域都学习一个线性模型LR，来学习非线性模式。MLR可以基于数据自动挖掘非线性模式，把算法工程师从繁琐的特征工程中拯救出来，更具有推广性。 同时MLR还引入了结构化先验、L1 L21正则化，分组稀疏、线性偏置、模型级联、增量训练、Common Feature Trick来提升模型性能。
MLR就像它的名字一样，由很多个LR模型组合而成。用分片线性模式来拟合高维空间的非线性模式，形式化表述如下：
g保证最终的预测结果是一个概率，π用来划分区域，η用来在区域内学习LR线性模型。论文中给出的函数选取如下： g(x) = x,π(x)=softmax,η(x)=sigmoid 即：
目标函数：
MLR主要适合在大规模工业级稀疏数据，通过分片线性模型来学习高维下的非线性模式，主要优势有两点：
1、端到端的非线性学习：从数据中自动挖掘蕴含的非线性模式，不在需要人工特征工程的干预。这使得MLR可以端到端的的完成训练，在不同场景中迁移非常轻松。
2、稀疏性：MLR在建模时使用了L1，L2,1正则化，实现了分组稀疏，使得训练出来的模型具有较高的稀疏度。无论是在模型的训练还是在线预测性能更好，当然，目标函数非凸非光滑为算法优带来了新的挑战。
看个例子：
这种菱形分界面其实非常难学，MLR表现出色。通过控制分片数量m，可以平衡模型的拟合能力和过拟合。上图m=4。论文中m=12得到了不错的效果。
理论上来说，增大m可以带来无限制的非线性拟合能力，但是同样会增加计算、存储的开销，同时会带来过拟合的风险。具体如何选取m要 针对MLR上面提到的各种特性，现一一介绍.
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 模型级联
虽然论文里没说，但是在阿里技术中有讲到，MLR支持与LR的级联式训练。有点类似于Wide & Deep，一些强Feature配置成级联形式能够提高模型的收敛性。例如典型的应用方法是：以统计反馈类特征构建第一层模型，输出FBctr级联到第二级大规模稀疏ID特征中去，能得到更好的提升效果。
反馈特征常用的如反馈CTR，是指系统上线一段时间之后得到的历史CTR值。
3.4 增量训练
实践证明，MLR利用结构先验（用户特征进行聚类，广告特征进行分类）进行pretrain，然后再增量进行全空间参数寻优训练，会使得收敛步数更少，收敛更稳定。
3.5 L1，L2,1正则化 / 分组稀疏
L2,1公式如下：
d是特征维度，m是划分的区域个数。
L2,1正则化实现了分组稀疏的特性。从MLR形式化的公式中可以发现，每一个维度的特征都对应多个参数。包括区域划分函数的参数、分类函数的参数。针对一个特征，L2,1首先对其所有的参数都进行L2正则化，然后每个维度的特征都得到了一个非负数，再在特征维度上进行L1正则化。导致的效果就是，对于不是很重要的特征，L2,1会使得它的所有参数都为0，也就是分组稀疏。 在目标函数中，还增加了L1正则化，尽一切可能只为得到一个稀疏模型。下面是实验结果：
可以看到L2,1的稀疏效果略差与L1.两者结合起来得到了最稀疏的模型，并且AUC也是最高的。
四、实现技巧
4.1 并行化
论文里的实现基于分布式，包括两个维度的并行化，模型并行化，数据并行化。每一个计算节点中都包含两种角色：Server Node, Worker Node，这样做的好处有两点：
1、最大化利用CPU计算资源。之前大多数Server Node单独放到一台服务器上，造成CPU资源的极大浪费。
2、最大化利用Memory资源。
4.2 Common Feature Trick
一个用户在一次pageview中会看到多个广告，每个广告都组成一条样本。所以这些样本之间很多特征都是重复的。这些特征包括：用户特征（年龄、性别等）、用户的历史访问信息（之前购买的物品、喜欢的店铺等）。那么我们对于向量内积的计算分成两部分：common和non-common parts:
利用Common Feature Trick可以从三个方面来优化并行化：
1、对于有Common Feature的样本作为一组一起训练，并保证在存储在一个worker上
2、对于Common Feature仅仅保存一次，以便来节省内存
3、对于Common Feature的loss和梯度更新只需要一次即可
下面是实验结果：
可以看到Common Feature Trick效果还是非常明显的。
五、总结
MLR从2012年就开始在阿里内部使用，到2017年才发表论文。不出意料，现在的模型应该已经不再是MLR这么简单了。另外，从MLR和LR进行级联，以便加强强特征来看，MLR还是有很大的局限性。个人感觉模型理论上来说确实非常棒，利用分片线性来模型高维非线性，但是分片函数的选择以及全局最优解的寻优都带来了非常大的挑战。
总结起来，MLP主要特性原理如下：
1、LS-PLM或者是MLR针对大规模工业级稀疏数据，采用分而治之的思想，在多个区域学习线性分类器，来在高维特征空间中学习非线性模型；
2、应用L1和L2,1正则化实现了分组稀疏，得到了稀疏模型； Common Feature Trick极大的降低了内存开销，缩短了训练时间；
3、另外一些高级特性：结构化先验、线性偏置、模型级联、增量训练；
Reference
1、Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction
2、盖坤讲MLR视频 https://v.youku.com/v_show/id_XNjA1MDEyNDU2.html
3、阿里技术 https://mp.weixin.qq.com/s/MtnHYmPVoDAid9SNHnlzUw?scene=25#
4、wechat_redirect 《海量数据下的非线性模型探索》
说个小花边，阿里内部最开始的CTR不能算机器学习模型，就是一个纯的规则： ad_ctr, cate_ctr, ad_pv为特征，预测下一天ad的ctr：
一共用了三个特征 + 一个if-else使用了很多年。听说是打败了很多机器学习工程师设计的LR模型
閱讀更多 機器學習與數據挖掘 的文章
