论文[Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction](arxiv.org/pdf/1704.0519)

==*定期更新,获取更多,欢迎[star](AlexanLee/ads-papers)。另外欢迎关注[计算广告实验](AlexanLee/ads-ailab),我会总结一些实现。*==

#### 一、论文基本描述。

CTR预估由于是针对大规模非线性数据的机器学习存在很多的困难。

1. 本论文提出了一个新型的模型（LS-PLM）。

2. 利用`$L_1$`和`$L_{2,1}$`正则来解决学习问题，将会导致非凸和非光滑的优化问题。因此，为解决这个问题提出了一种基于方向导数和拟牛顿法的有效方法

3. 另外，设计了工业级的数百台机器的模型训练系统。

LS-PLM可以捕捉非线性的特征数据，从而减少特征工程的工作。从2012年这个模型就开始大规模应用到阿里巴巴的展示广告预估上。

#### 二、解决方法、思想

点击率预估是在线广告的核心问题。传统的方法是LR模型，LR模型利用`$L_1$`正则能生成稀疏解。实际上CTR预估是一个非线性的问题，用户点击涉及到流量质量，用户兴趣，上下文特征，以及它们的交叉特征。为了解决LR的非线性问题，需要做大量的特征工程。另一方面，可以设计一些非线性模型，Facebook 利用决策树?LR的方式。**但是树形模型不适合非常稀疏的高纬特征数据。FM能够有效的解决特征交叉的问题，但是，不能解决所有的数据非线性问题。**

本论文提出了一种基于大规模数据的分片线性回归模型（LS_PLM）,**它是基于分治法的思想。首先将特征空间分解为若干本地区域，然后针对每一个区域训练一个线性模型，把最后所有线性模型预测的权重作为输出结果**。有如下三个特点：

1. 非线性性。

2. 大规模性。巨大的样本量，高纬特征。

3. 稀疏性。利用`$L_1$`和`$L_{2,1}$`正则可以很好的获得稀疏性。

模型公式:

预测`$p(y|x)$`需要考虑两部分，第一部分`$sigma(mu_{j}^{T})$`将特征空间分成m（超参数）个区域，第二部分`$eta(w_j^Tx)$`对每个区域进行预测。`$g(.)$`确保我们的模型满足定义的概率函数。

特例,利用softmax作为分割函数，sigmoid作为预测函数，因此得到一个明确的表达式：

这里的混合模型可以看作是一个FOE模型：

LS_PLM的目标函数：

这里`$L_1$`和`$L_{2,1}$`都是非光滑函数，这造成目标函数是非凸、非光滑的，因此很难用传统的梯度下降法和EM演算法。

##### 优化

引理1 当目标函数`$f( heta)$`是由非光滑的正则函数组成的时候，例如上边提到的损失函数，那么对任何的`$ heta$`和`$d$`那么方向导数存在。

命题2 给定一个光滑损失函数和一个目标函数，有：

其中

***

优化演算法：

***

演算法：

类似于LBFGS,修改为：

1. 使用最小化非凸目标导数方向`$d(k)$`代替负梯度。

2. 更新方向取决于所选的方向`$d(k)$` 定义的。当`$H(k)$`不是正定时，切换到`$d(k)$`.

3. 在线性搜索时，每个搜索点都投影到前一点的orthant上。

##### 实现

并行计算：

两个角色：工作节点，每个节点有部分的训练数据和本地模型。第二个为服务节点，每个节点存放全部的参数，

通用的特征技巧：

将特征划分为通用特征和非通用特征，

有三个方面：

1. 分组训练通用特征，确保这些样本存储在相同的工作节点上。

2. 对于多个样本通用特征只存储一次。

3. 对于通用特征更行损失函数和梯度只一次。

#### 三、评价指标

AUC。

#### 四、实验

通常来说，较大的m需要较多的参数有较大模型容量，但是会导致训练的成本增加。列举了不同的分片，得到的不同的AUC值。最后得到12为最好的参数。

`$lambda$`和`$eta$`都取1.

目前实际测试实验，采用FTRL优化的MLR模型比LR模型，可以稳定提升离线AUC2%左右。实际证明了其效果。

可参看[计算广告实验](AlexanLee/ads-ailab).

还有[Angel](Angel-ML/angel)的实现。

#### 五、使用&借鉴

典型的应用场景：

**基于 MLR 的定向广告 CTR 预估演算法**

基于 MLR 演算法的非线性学习能力，阿里妈妈的定向广告 CTR 预估采用了大规模原始ID 特征 + MLR 演算法的架构。具体为刻画一次广告展现为特征向量，它由三部分独立构成：

1. 用户部分特征（包括 userid、profile 信息、用户在淘宝平台上的历史行为特征（浏览/购买过的宝贝/店铺/类目上的 id 和频次等）

2. 广告部分特征（包括 adid、campainid、广告对应的卖家店铺 id、类目 id 等）

3. 场景部分特征（包括时间、位置、资源位等）

这些特征之间无传统的交叉组合，维度在 2 亿左右。然后，他们将数据直接喂给 MLR 演算法，并且应用了结构化先验、pretrain+ 增量训练、线性偏置等高级技巧，让模型从数据中自动去总结和拟合规律。相比于传统的 LR+ 特征工程思路，这种解法更为高效和优雅，模型精度更高，在实际生产中的可迭代更强。

**基于 MLR 的定向广告 Learning to Match 演算法**

Match 演算法是定向广告中的一个重要环节，它的核心使命是基于用户的人口属性、历史行为等信息来猜测用户可能感兴趣的广告集合。传统的 Match 演算法更多采用的是规则匹配、协同过滤等方法，方法的扩展性不强。

在阿里妈妈定向广告系统中，工程师研发了基于 MLR 的 learning to match 演算法框架。简单来说，用模型的方法基于用户的行为历史来学惯用户个性化的兴趣，从而召回高相关性的候选广告集。

同样地，基于MLR演算法的非线性能力，可以很容易地将不同的特征源、标签体系融合到框架中，不需要过多地关注和设计特征的交叉组合，使得框架的灵活性大大增强。

#### 六、参考&推荐

1. [Practical Lessons from Predicting Clicks on Ads at Facebook](quinonero.net/Publicati)

2. [mixed-effects logistic regression](idiom.ucsd.edu/~rlevy/l)


推荐阅读：
相关文章