paper reading: Scalable Time-Decaying Adaptive Prediction Algorithm

ML FTRL TDAP online_learning

---

目录

---

写在前面的话

  这是SIGKDD（2016）上华为发表的一篇重要的paper3，主要解决推荐场景下训练样本随时间衰减的问题。
  在新闻推荐和广告推荐场景下，用户最近的行为，相比历史上的行为，更能表现用户的真实意图和偏好，但是对于当前主流的online learning算法，包括FTRL4都未能很好的处理这种Time-Decaying Adaptive问题。
  华为基于FTRL-Proximal进一步提出了一种改进的在线学习手段TDAP(Time Decaying Adaptive Prediction)，主要目的在于为在线学习引入数据随时间快速变化的因子—这就是通常所说的concept drifting5。
  做为一个在FTRL上深耕数年之久的广告变现团队，我们一直被这个问题所困扰，我们当前采用的是一种比较暴力的方式，通过滑动窗口机制处理正负样本数不再变化的特征，现在终于有了一个相对比较温和和合理的解决方案。google了一下，网上还没有人专门分享过这篇paper，于是就总结和梳理了一下，有不足之处，敬请谅解。

背景介绍

1. online learning很强大

online learning技术是一种新兴的并且有效的机器学习方法，尤其在在线广告、个性化推荐、异常检测以及可疑url识别场景下。相对于offline learning在每次更新模型时都需要batch train所有训练数据，online learning只需要对新到来的样本进行增量学习即可，显得更加优雅和高效，并且在精度和准确性上不会有任何损失，反而获得了更好的稀疏性(sparsity)。

2. online learning的局限性

然而，online learning却无法解决用户的兴趣偏好随时间转移的问题。比如我可能上个月喜欢浏览跑步类的商品，这个月却喜欢科技类的产品，因为我已经购买了足够多的跑步类产品，下个月可能就不再登陆购物网站。

所以，当前的online learning算法需要迫切解决的一个问题就是：如何高效的拟合和缩放这种快速变化的(fast-changing)在线数据？我们需要一个可伸缩的时间衰减（scalable time-decaying）在线学习算法。

3. 面临的挑战

• 需要拟合快速变化的在线数据。之前的 time-decaying系列算法要么是通过time-decaying函数对训练数据设定权重值，要么就是直接丢弃过期的样本。现在的online learning算法比如TGD、FOBOS、RDA、FTRL等根本就没有考虑时间衰减问题。对这些算法来说，一年前学到的模型跟最新学到的模型权重都一样。
• 并行训练。FTRL系列算法只是提到了这个问题，但是并没有给出详细的解决方案。

Online Learning Algorithm

1. FTRL-Proximal Algorithm

FTRL是H. Brendan McMahan这个哥们儿前前后后搞了3年，发了4篇paper才搞出来的一个算法，2013年KDD那篇正式的工程化paper（Ad Click Prediction: a View from the Trenches）标志着FTRL有理论走向实践。之前在部门专门分享过一次FTRL的原理及在公司业务场景下的详细应用，包括xgboost+FTRL的实践，有时间得再详细整理成博客，里面的很多东西值得去深入探究。

2. Problem Definition

TOCO（time-decaying online convex optimization）问题可以如下定义：
给定一个时间阶段T ≥ 1，以及一系列训练样本，用$x^{(t)}$和$y^{(t)}$分别表示特征和标签，则有：

$${\bf{w}}^{(T)}=\arg\min_{w}\lbrace{\sum_{t=1}^{T}L({\bf{w}},x^{(t)},y^{(t)})+R({\bf{w}})+\sum_{t=1}^{T}F^{(T)}(t)S({\bf{w}},{\bf{w}}^{(t))} \rbrace}$$
对比FTRL的凸优化目标函数形式：
$${\bf{w}}^{(T)}=\arg\min_{w}\lbrace{\sum_{t=1}^{T}L({\bf{w}},x^{(t)},y^{(t)})+R({\bf{w}}) \rbrace}$$
TOCO的目标函数多了最后一项——和时间衰减相关的函数。其中$F^{(T)}(t)$是自变量为t，单调递增的时间衰减函数。$S({\bf{w}},{\bf{w}}^{(t)})$是平滑项，即：$\frac{1}{2}||{\bf{w}}-{\bf{w}}^{(t)}||$.

Time-Decaying Adaptive Prediction Algorithm

1. 时间衰减函数

常见的时间衰减函数有多项式衰减和指数衰减，这篇paper里使用了指数衰减函数，原因有2点：
- 工业届和学术界广泛使用
- 有助于后面的模型更新函数推导出递归的解析解
衰减函数定义如下：

$$F^{(t)} = exp(-\frac{|T+1-t|}{{2τ}^2}),$$
T≥1，表示当前的时间，t是历史模型的时间，t∈[1, T].这里F是一个单调递增函数。t越小，表示数据越“old”，对应的F也就越小。

2. 模型更新函数

首先回顾一下FTRL的特征权重更新策略。FTRL-Proximal代表了一族在线学习的手段，包含RDA，FOBOS，FTRL等，这些算法着重从理论上探讨了最优化算法在online学习场景下产生稀疏解的方法。这一族算法认为每一步的解都会产生损失，希望整体的损失小，因此为了这个目的，往往设计成每次的更新与前几步相似，步长递减，即学习率递减。

FTRL综合考虑了FOBOS和RDA的长处，其特征权重更新公式为：

$${\bf{w}}^{(t+1)}=\arg\min_{w}\lbrace{\bf{g}}^{1:t}.{\bf{w}}+λ_1||{\bf{w}}||_1+λ_2||{\bf{w}}||^2_2+\frac{1}{2}\sum_{s=1}^t\sigma^{(s,t)}||{\bf{w}}-{\bf{w}}^{(s)}||^2_2\rbrace ,\tag{5}$$
第一项是损失函数的梯度向量，第二项和第三项分别是L1和L2正则项，其中L2正则起一个平滑的作用，并不影响稀疏解，只有L1才会影响稀疏性，第四项也是一个平滑项，起到加速收敛和改进精度的作用。第四项中的σ表示学习率$σ^{(1:t)}=\frac{1}{μ_{(t)}}$。在FTRL中，每个特征维度的学习率都需要单独考虑，即(Per-Coordinate Learning Rate)，主要是考虑到每个维度的样本量不同导致的梯度下降速度不同，因此在FTRL中用对应维度的梯度分量来反映学习率的变化。

TDAP的特征权重更新公式如下：

$${\bf{w}}^{(t+1)}=\arg\min_{w}\lbrace{\bf{g}}^{1:t}.{\bf{w}}+λ_1||{\bf{w}}||_1+λ_2||{\bf{w}}||^2_2+\frac{1}{2}\sum_{s=1}^tδ^{(s,t)}||{\bf{w}}-{\bf{w}}^{(s)}||^2_2\rbrace ,\tag{6}$$
值得注意的是，TDAP算法的更新函数与FTRL近似算法的不同之处在于将时间衰减因子引入了平滑项。即：$\frac{1}{2}\sum_{s=1}^tδ^{(s,t)}||{\bf{w}}-{\bf{w}}^{(s)}||^2_2$。这里$δ^{(s,t)}=σ^{(s)}.F^{(t)}(s)$，按维度展开就是：
$$\begin{align*} δ^{(s,t)}_{i} &= σ^{(s)}_{i}exp(-\frac{|t+1-s|}{{2τ}^2}) \\ &= \frac{1}{α}{\left(\sqrt{\sum_{j=1}^{s}(g_{i}^{(j)})^2}-\sqrt{\sum_{j=1}^{s-1}(g_{i}^{(j)})^2}\right)exp(-\frac{|t+1-s|}{{2τ}^2}}) \tag{7} \end{align*}$$
如果让 γ=$\frac{1}{(2τ)^2}$, 则$δ^{(s,t)}=σ^{(s)}exp(-γ(t+1-s))$。这里γ是衰减率，值越大，表示历史模型的衰减越快。我们可以发现，如果$\lim_{τ\rightarrow\infty}{γ}=0$，(6)式就等价于FTRL算法了。

3. 解析解(closed form)

跟FTRL的求解方式一样，可以得到TDAP的解析解。在FTRL中，通过将特征权重的各个维度拆解为N个独立的标量最小化问题即可求得迭代解表达式。
公式(6)可以重写成如下形式：

$${\bf{w}}^{(t+1)}=\arg\min_{w}\lbrace{(\bf{g}}^{1:t}-\sum_{s=1}^{t}δ^{(s,t)}{\bf{w}^{(s)}}).{\bf{w}}+λ_1||{\bf{w}}||_{1}+\frac{1}{2}(λ_2+\sum_{s=1}^t{δ^{(s,t)}).{\bf{w}^2}+(const)} ,\tag{8}$$
具体const的由来，可以参见FTRL的推导过程。
我们定义${\bf{z}}^{(t)}={\bf{g}}^{(1:t)}-\sum_{s=1}^{t}δ^{(s,t)}{\bf{w}^{(s)}}$，我们可以得到${\bf{w}^{(t+1)}}$的递归解析解：
$$\left \{\begin{array}{cc} 0 & if\,\;|z_i^{(t)}| ≤ λ_1 \\ -(λ_2+\sum_{s=1}^tδ_i^{(s,t)})^{-1}(z_i^{(t)}-λ_1sign(z_i^{(t)})) & if\,\;|z_i^{(t)}| > λ_1 \end{array}\right.\tag{9}$$
这个式子跟FTRL几乎完全一致，只不过σ换成了引入时间衰减因素的δ。

4. 递归的解析解(recursive closed form)

到此为止，我们已经从数学上求解出了这个最优化问题，下面需要做的就是：如何得到递归的解析解，即：使用第t+1轮计算出来的各个参数，来更新当前第t轮的值？

从（9）式${\bf{w}^{t+1}}$的递归解中可以看到，我们只需要关心两个表达式：$\sum_{s=1}^tδ_i^{(s,t)}$和$z_{i}^{(t)}$，我们对这两项分别变换：

• $\sum_{s=1}^tδ_i^{(s,t)}$的递归解：
  

  $$\begin{align*} \sum_{s=1}^tδ_i^{(s,t)} &= \sum_{s=1}^{t}{\left(\sigma_i^{(s)}·exp(-γ(t+1-s))\right)} \\ &= exp(-γ)·(\sum_{s=1}^{t-1}δ_{i}^{(s,t-1)}+\sigma_{i}^{(t)}) \tag{10} \end{align*}$$

• $z_{i}^{(t)}$的递归解：
  因为${\bf{z}}^{(t)}={\bf{g}}^{(1:t)}-\sum_{s=1}^{t}δ^{(s,t)}{\bf{w}^{(s)}}$，我们定义$h_i^{(t)}=\sum_{s=1}^{t}δ_i^{(s,t)}w_i^{(s)}$，则：
  

  $$\begin{align*} h_i^{(t)} &= \sum_{s=1}^{t}δ_i^{(s,t)}w_i^{(s)} \\ &= \sum_{s=1}^{t}\sigma_i^{(s)}exp{\left(-γ(t+1-s)\right)}w_i^{(s)} \\ &= exp(-γ){\left(\sum_{s=1}^{t-1}(δ_i^{(s,t-1)}w_i^{(s)}+\sigma_i^{(t)}w_i^{(t)} \right)} \\ &= exp(-γ)(h_i^{(t-1)}+\sigma_i^{(t)}w_i^{(t)})\tag{11} \end{align*}$$
  于是，可以得到$z_{i}^{(t)}$的递归解：
  $$\begin{align*} z_{i}^{(t)} &= g_i^{(1:t)}-\sum_{s=1}^{t}δ_i^{(s,t)}w_i^{(s)} \\ &= g_i^{(1:t-1)}+g_i^{(t)}-exp(-γ)(h_i^{(t-1)}+\sigma_i^{(t)}w_i^{(t)}) \tag{12} \end{align*}$$

5. 算法伪代码

无论是FTRL还是TDAP，其算法流程都是：
 （1）特征提取
 （2）根据截断阈值更新每个feature的weight
 （3）预估ctr，计算梯度
 （4）更新临时变量

TDAP算法伪代码如下：

对比FTRL算法：

这里都使用了Logistic回归，TDAP算法相对FTRL使用了更多的临时变量，特征的每一维都需要记录：$u_i^t, v_i^t, \sigma_i^t, h_i^t$。
从伪代码中我么可以看到：在时间衰减函数的影响下，较老的数据对目标模型的影响进行了缩减，从而适应了数据的快速变化。
详细的java代码如下：

/**
optimize function for TDAP algorithm.
*/
private void optimize(Sample sample) {
    //get super parameter
    Parameter parameter = modelConfig.getPara();
    for (int i = 0; i < sample.strFeatures.size(); ++i) {
        FeatureInfo featureInfo = sample.featureInfos[i];
        if (featureInfo == null) {
            String fName = sample.strFeatures.get(i);
            FeatureInfo fi = model.features.get(fName);
            sample.featureInfos[i] = fi;
            featureInfo = fi;
        }
        //figure feature weight
        if (featureInfo.z <= parameter.lambda1 && featureInfo.z >= -parameter.lambda1) {
            featureInfo.omiga = 0;
        } 
        else 
        {
            double rst = -1 / (featureInfo.d + parameter.lambda2)
                    * (featureInfo.z - Math.signum(featureInfo.z) * parameter.lambda1);
            featureInfo.omiga = rst;
        }
    }
    //predict and figure graduate
    double grad;
    predict(sample, predict, null, grad, sample.featureInfos, false);
    //recursive form update for future model update
    for (int i = 0; i < sample.featureInfos.length; ++i) {
        FeatureInfo featureInfo = sample.featureInfos[i];
        if (featureInfo == null) {
            continue;
        }
        double delta = (doubleSqrt(featureInfo.u + grad * grad) - doubleSqrt(featureInfo.u)) / parameter.alpha;
        featureInfo.u += grad * grad;
        featureInfo.d = Math.exp(-parameter.γ) * (featureInfo.d + delta);
        featureInfo.v += grad;
        featureInfo.h = Math.exp(-parameter.γ) * (featureInfo.h + delta * featureInfo.omiga);
        featureInfo.z = featureInfo.v - featureInfo.h;
    }
}

小结

• TDAP主要是为了解决训练样本的时间衰减问题，方法是在原FTRL的平滑项中引入单调递增的指数衰减函数。
• TDAP在快速变化的数据集上，比如时效类数据（新闻信息流、视频推荐），在AUC上有多达12%的提升。在非时效类数据上跟FTRL基本持平。但是我并没有在我们自己的数据集上做测试，实践中可能需要注意几个问题：第一，需要保持训练样本的时间序列，我们当前的FTRL训练样本做实验的时候都对历史数据进行了shuffle，这样会改变时间序列，不利于TDAP的“时间衰减”。第二，衰减率γ的设定，这个需要调参，按照paper中的实验效果，γ值从0.1到0.0005，AUC有明显的波动。
• TDAP这篇paper还有一个重要的工作是提供了并行训练的方法，通过引入了Petuum项目的参数服务器来实现基于SSP模型的更高程度的并行化处理，并跟采用Spark的BSP实现进行了对比，效果有明显提升。这个我们暂时使用不上，不做深入研究。

参考文献

1. Scalable Time-Decaying Adaptive Prediction Algorithm
2. Ad Click Prediction: a View from the Trenches
3. A Gentle Introduction to Concept Drift in Machine Learning