【阿里2017】利用分片线性模型实现大规模数据点击率预估

论文Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction

==定期更新,获取更多,欢迎star。另外欢迎关注计算广告实验,我会总结一些实现。==

一、论文基本描述。

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=1|x)=g(\sum_{j=1}^m\sigma(\mu_{j}^{T}x)\eta(w_j^Tx))

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

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

p(y=1|x)=\sum_{i=1}^m\frac{exp(\mu_i^Tx)}{\sum_{j=1}^mexp(\mu_j^Tx)}\cdot\frac{1}{1+exp(-w_i^Tx)}

这里的混合模型可以看作是一个FOE模型:
math p(y=1|x)=\sum_{j=1}^mp(z=i|x)\cdot p(y|z=i,x)
LS_PLM的目标函数:

arg min f(\theta)=loss(\theta)+\lambda\Vert\theta\Vert_{2,1}+\beta\Vert\theta\Vert_1

loss(\theta)=-\sum_{t=1}^n[y_tlog(p(y_t=1|x_t,\theta))+(1-y_t)log(p(y_t=0|x_t,\theta))]

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

优化
\vartheta_{i,j}^+f(\theta)=\lim_{\alpha \to 0}\frac{f(\theta+\alpha\epsilon_{ij})-f(\theta)}{\alpha}

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

命题2 给定一个光滑损失函数和一个目标函数,有:
math d_{i,j}=\left\{ \begin{array}{c} s-\beta sign(\theta_{i,j}) ,\theta_{i,j}\neq0 \\ max\{\vert s \vert-\beta,0\}sign(s) ,\theta_{i,j}=0,\Vert\theta_{i,\cdot}\Vert_{2,1}\neq 0\\ \frac{max\{\Vert v \Vert_{2,1}-\lambda,0\}}{\Vert v \Vert_{2,1}},\Vert \theta_{i,\cdot} \Vert_{2,1}=0 \end{array} \right.
其中$s=-\nabla loss(\theta)_{i,j}-\lambda\frac{\theta_{i,j}}{\Vert\theta_{i,\cdot}\Vert_{2,1}}$,$v=max\{\vert -\nabla loss(\theta)_{i,j}\vert-\beta,0\}\cdot sign(-\nabla loss(\theta)_{i,j})$.
***
优化算法:

输入:选择初始点,$\theta^{0}$,$S\leftarrow\{\},Y\leftarrow\{\}$

for k=0 to MaxIters do

  1. 计算$d^{(k)}$.
  2. 计算$p_{k}$.
  3. 寻找$\theta^{(k+1)}$.
  4. 如果满足条件就停止,输出$\theta^{(k+1)}$.
  5. 更新$S$$S^{k}=\theta^{k}-\theta^{k-1}$
  6. 更新$Y$,$Y^{k}=-d^{k}-(-d^{(k-1)})$

算法:

类似于LBFGS,修改为:

  1. 使用最小化非凸目标导数方向$d(k)$代替负梯度。
  2. 更新方向取决于所选的方向$d(k)$ 定义的。当$H(k)$不是正定时,切换到$d(k)$.
  3. 在线性搜索时,每个搜索点都投影到前一点的orthant上。
实现

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

通用的特征技巧:
将特征划分为通用特征和非通用特征,

\mu_i^Tx=\mu_{i,c}^Tx_c+\mu_{i,nc}^Tx_{nc}

w_i^T=w_{i,c}^Tx_c+w_{i,nc}^Tx_{nc}

有三个方面:

  1. 分组训练通用特征,确保这些样本存储在相同的工作节点上。
  2. 对于多个样本通用特征只存储一次。
  3. 对于通用特征更行损失函数和梯度只一次。

三、评价指标

AUC。

四、实验

通常来说,较大的m需要较多的参数有较大模型容量,但是会导致训练的成本增加。列举了不同的分片,得到的不同的AUC值。最后得到12为最好的参数。
$\lambda$$\beta$都取1.
目前实际测试实验,采用FTRL优化的MLR模型比LR模型,可以稳定提升离线AUC2%左右。实际证明了其效果。
可参看计算广告实验.
还有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
  2. mixed-effects logistic regression