本文根据Google2013年发表的论文《Ad Click Prediction: a View from the Trenches》总结。

CTR预估中的在线学习算法

在广告点击率预估模型中，面临着特征维度巨大的问题，这导致了模型参数的存储空间极高，以及模型进行预测时的时间代价大的问题。

Online gradient descnet(OGD)

在线梯度下降法类似于随机梯度下降，一次只处理一个样本，但不同的是不要求序列的样本满足独立同分布的性质。
OGD方法在许多问题上均有不错的表现，但是获得的解不够稀疏。

L1 OGD

在OGD目标函数中添加L1正则化项，可以带来一定的稀疏性，使得模型的参数接近零。但由于参数的更新是两个浮点数进行相加，很难有机会产生精确零解。

截断梯度法TG和FOBOS

FOBOS和TG方法能够引入稀疏性

Sparse Online Learning via Truncated Gradient
Efficient Learning using Forward-Backward Splitting

正则对偶平均RDA

RDA方法在准确率和稀疏性的权衡之间好过FOBOS

Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization

FTRL-Proximal

参数更新策略

Follow The (Proximally) Regularized Leader 或FTRL-Proximal具有RDA的优秀精度以及FOBOS的稀疏性质。
传统的OGD更新策略如下：
$w_{t+1}=w_t-{\eta }_t{g}_t$wt+1​=wt​−ηt​gt​，其中 ${\eta }_t=\frac{1}{\sqrt{t}}$ηt​=t ​1​
FTRL-Priximal使用如下更新策略
$w_{t+1}=\arg {\min }_{}(g_{1:t}\cdot w+\frac{1}{2}{\sum }_{s=1}^t{\sigma }_s\mid \mid w-w_s\mid {\mid }_2^2+{\lambda }_1\mid \mid w\mid {\mid }_1)$wt+1​=argwmin​(g1:t​⋅w+21​s=1∑t​σs​∣∣w−ws​∣∣22​+λ1​∣∣w∣∣1​)
其中 ${\sigma }_s$σs​是一个和学习率 ${\eta }_t$ηt​相关的参数，
${\sigma }_{1:t}={\sum }_{s=1}^t{\sigma }_s=\frac{1}{{\eta }_t}$σ1:t​=s=1∑t​σs​=ηt​1​
$g_{1:t}={\sum }_{s=1}^t{g}_t$g1:t​=s=1∑t​gt​
公式中，若令 ${\lambda }_1=0$λ1​=0，则和传统的梯度下降方法一致。
若令 ${\lambda }_1\>0$λ1​>0则可以产生稀疏解。
公式第一项保证向正确的方向更新，而使用历史累计梯度保证不会过早地将重要特征的参数约束为0。
公式第二项要求新产生的权重不要偏离历史权重太远，即参数更新不要太激进。
公式第三项保证稀疏性。

公式推导

\begin{align}
F(w)&=g_{1:t}\cdot w+\frac{1}{2}\sum\limits_{s=1}^{t\sigma_s||w-w_s||_2}2+\lambda_1||w||1\
&=g{1:t}\cdot w+\frac{1}{2}\sum\limits_{s=1}^t\sigma_s(wTw-2w^Tw_s+w_sTw_s)+\lambda_1||w||1\
&=g{1:t}\cdot w+\frac{1}{2}\sum\limits_{s=1}^t\sigma_s(wTw)-\sum\limits_{s=1}^t\sigma_swTw_s+\lambda_1||w||1+constant\
&=(g{1:t}-\sum\limits_{s=1}^{t\sigma_sw_s)w+\frac{1}{2}\sum\limits_{s=1}}t\sigma_s(w^Tw)+\lambda_1||w||_1+const
\end{align}
令 $z_t=g_{1:t}-{\sum }_{s=1}^t{\sigma }_s{w}_s$zt​=g1:t​−s=1∑t​σs​ws​并由 $\frac{1}{{\eta }_t}={\sum }_{s=1}^t{\sigma }_s$ηt​1​=s=1∑t​σs​,
$F\left(w\right)=z_t\cdot w+\frac{1}{2{\eta }_t}\mid \mid w\mid {\mid }_2^2+{\lambda }_1\mid \mid w\mid {\mid }_1+\left(const\right)$F(w)=zt​⋅w+2ηt​1​∣∣w∣∣22​+λ1​∣∣w∣∣1​+(const)
根据推导
$z_t=z_{t-1}+g_t-(\frac{1}{{\eta }_t}-\frac{1}{{\eta }_{t-1}})w_t$zt​=zt−1​+gt​−(ηt​1​−ηt−1​1​)wt​
下面求解使得 $F\left(w\right)$F(w)最小的 $w$w
${\partial }_{w}F\left(w\right)=z_t+\frac{w}{{\eta }_t}+{\lambda }_1{\partial }_w\mid w{\mid }_1$∂w​F(w)=zt​+ηt​w​+λ1​∂w​∣w∣1​
由于 $\mid \mid w\mid \mid$∣∣w∣∣在零点处不可导，使用次梯度方法。则 $\mid \mid w\mid {\mid }_1$∣∣w∣∣1​的次梯度如下，
${\partial }_{w_j}\mid w_j\mid =\{\begin{array}{cc}-1& w_j\&lt;0\\ [-1,1]& w_j=0\\ 1& w_j\&gt;0\end{array}$∂wj​​∣wj​∣=⎩⎪⎨⎪⎧​−1[−1,1]1​wj​<0wj​=0wj​>0​
则
${\partial }_{w_i}F\left(w\right)=\{\begin{array}{cc}{z}_{t,i}+\frac{w_i}{{\eta }_t}-{\lambda }_1& w_i\&lt;0\\ [z_{t,i}+\frac{w_i}{{\eta }_t}-{\lambda }_1,z_{t,i}+\frac{w_i}{{\eta }_t}+{\lambda }_1]& w_i=0\\ z_{t,i}+\frac{w_i}{{\eta }_t}+{\lambda }_1& w_i\&gt;0\end{array}$∂wi​​F(w)=⎩⎪⎨⎪⎧​zt,i​+ηt​wi​​−λ1​[zt,i​+ηt​wi​​−λ1​,zt,i​+ηt​wi​​+λ1​]zt,i​+ηt​wi​​+λ1​​wi​<0wi​=0wi​>0​
令 ${\partial }_{w_i}F\left(w\right)=0$∂wi​​F(w)=0，并根据条件限制，有
$w_{t+1,i}=\{\begin{array}{cc}({\lambda }_1-z_{t,i}){\eta }_t& z_{t,i}\&gt;{\lambda }_1\\ 0& \mid z_{t,i}\mid \le {\lambda }_1\\ (-{\lambda }_1-z_{t,i}){\eta }_t& z_{t,i}\&lt;-{\lambda }_1\end{array}$wt+1,i​=⎩⎪⎨⎪⎧​(λ1​−zt,i​)ηt​0(−λ1​−zt,i​)ηt​​zt,i​>λ1​∣zt,i​∣≤λ1​zt,i​<−λ1​​
整理成原论文格式
$w_{t+1,i}=\{\begin{array}{cc}0& \mid z_{t,i}\mid \le {\lambda }_1\\ -{\eta }_t(z_{t,i}-sgn(z_{t,i}\left){\lambda }_1\right)& \mid z_{t,i}\mid \&gt;{\lambda }_1\end{array}$wt+1,i​={0−ηt​(zt,i​−sgn(zt,i​)λ1​)​∣zt,i​∣≤λ1​∣zt,i​∣>λ1​​
由最后的参数更新公式可知，实现的时候可以直接存储 $-{\eta }_t{z}_t$−ηt​zt​，当 ${\lambda }_1=0$λ1​=0时，存储的就是通常的梯度下降的参数。
注意到如果 $\eta =constant,{\lambda }_1=0$η=constant,λ1​=0，该公式和原始OGD则等价， $w_{t+1}=-\eta z_t=-\eta {\sum }_{s=1}^t{g}_s$wt+1​=−ηzt​=−η∑s=1t​gs​

逐维度的学习率

OGD理论建议采用全局的学习率 $\eta =\frac{1}{\sqrt{t}}$η=t ​1​，所有维度使用相同的学习率。
FTRL建议每个维度采用的学习率如下
${\eta }_{t,i}=\frac{\alpha }{\beta +\sqrt{{\sum }_{s=1}^t{g}_{s,i}^2}}$ηt,i​=β+∑s=1t​gs,i2​ ​α​，
其中 $\alpha$α和 $\beta$β是超参数，论文提到 $\alpha$α可以通过渐进验证的方法得到，而 $\beta$β通常设置为1。
这种方法考虑了数据在不同维度上的特征分布的不均匀性，如果包含w某一个维度特征的训练样本很少，每一个样本都很珍贵，那么该特征维度对应的训练速率可以独自保持比较大的值，每来一个包含该特征的样本，就可以在该样本的梯度上前进一大步，而不需要与其他特征维度的前进步调强行保持一致。

Per-Coordinate FTRL-Proximal with L1 and L2 Regularization for Logistic Regression

目标函数 $w_{t+1}=\arg {\min }_{}(g_{1:t}\cdot w+\frac{1}{2}{\sum }_{s=1}^t{\sigma }_s\mid \mid w-w_s\mid {\mid }_2^2+{\lambda }_1\mid \mid w\mid {\mid }_1+\frac{1}{2}{\lambda }_2\mid \mid w\mid {\mid }_2^2)$wt+1​=argwmin​(g1:t​⋅w+21​s=1∑t​σs​∣∣w−ws​∣∣22​+λ1​∣∣w∣∣1​+21​λ2​∣∣w∣∣22​)

TensorFlow实现

https://www.tensorflow.org/versions/r1.8/api_docs/python/tf/train/FtrlOptimizer

tf.train.FtrlOptimizer(self, learning_rate, learning_rate_power=-0.5, initial_accumulator_value=0.1, l1_regularization_strength=0.0, l2_regularization_strength=0.0, use_locking=False, name="Ftrl", accum_name=None, linear_name=None, l2_shrinkage_regularization_strength=0.0)

当``为0时，优化的目标函数为 $w_{t+1}=\arg {\min }_{}(g_{1:t}\cdot w+\frac{1}{2}{\sum }_{s=1}^t{\sigma }_s\mid \mid w-w_s\mid {\mid }_2^2+{\lambda }_1\mid \mid w\mid {\mid }_1+{\lambda }_2\mid \mid w\mid {\mid }_2^2)$wt+1​=argwmin​(g1:t​⋅w+21​s=1∑t​σs​∣∣w−ws​∣∣22​+λ1​∣∣w∣∣1​+λ2​∣∣w∣∣22​)
与paper区别为l2正则项前系数为1。
函数参数与论文对应关系

参数说明：

大规模数据集上的内存节省策略

我们已经看到L1正则化可以在模型推断的时候节省大量内存，下面介绍一些训练期间节省内存的策略

• 概率特征包含
  • Posson Inclusion
  • Bloom Filter Inclusion
• 使用更少的位数编码值
  论文提到使用FTRL算法时，大部分参数的值都在(-2,+2)之间，那么使用传统OGD算法使用的32或64位的浮点数存储方案就显得过大了。
  提出使用16位的浮点数保存数值，2位整数，13位小数，1位符号位。
• 训练若干相似模型
• Single Value Strcture
• 使用样本数计算学习率
• 下采样训练集
  正样本全部采样，负样本以比例 $\tau$τ采样，但在训练时候给予负样本 $\frac{1}{\tau }$τ1​的权重

预测结果修正

由于模型假设的不准确，或隐藏特征在训练或测试期间没有出现，模型会产生系统偏差（预测的平均值和实际平均值有差距）。可以通过一些策略进行修正。
如泊松回归 $\tau \left(p\right)=\gamma p^k$τ(p)=γpk

不成功的实验

• 渐进特征哈希
• Dropout
• 特征Bagging
• 特征向量归一化

参考资料

Ad Click Prediction: a View from the Trenches.H. Brendan McMahan, Gary Holt, D. Sculley et al researchgate
各大公司广泛使用的在线学习算法FTRL详解

其他的不错的资料

Online Learning算法理论与实践
【每周一文】Ad Click Prediction: a View from the Trenches(2013)
FTRL算法在使用中需不需要通过Batch Model初始化？
CTR预测算法之FTRL-Proximal
为什么FTRL比FOBOS更容易获得稀疏解？
关于点击率模型，你知道这三点就够了