@onejune
2018-07-18T22:58:50.000000Z
字数 7467
阅读 1988
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,于是就总结和梳理了一下,有不足之处,敬请谅解。
online learning技术是一种新兴的并且有效的机器学习方法,尤其在在线广告、个性化推荐、异常检测以及可疑url识别场景下。相对于offline learning在每次更新模型时都需要batch train所有训练数据,online learning只需要对新到来的样本进行增量学习即可,显得更加优雅和高效,并且在精度和准确性上不会有任何损失,反而获得了更好的稀疏性(sparsity)。
然而,online learning却无法解决用户的兴趣偏好随时间转移的问题。比如我可能上个月喜欢浏览跑步类的商品,这个月却喜欢科技类的产品,因为我已经购买了足够多的跑步类产品,下个月可能就不再登陆购物网站。
所以,当前的online learning算法需要迫切解决的一个问题就是:如何高效的拟合和缩放这种快速变化的(fast-changing)在线数据?我们需要一个可伸缩的时间衰减(scalable time-decaying)在线学习算法。
FTRL是H. Brendan McMahan这个哥们儿前前后后搞了3年,发了4篇paper才搞出来的一个算法,2013年KDD那篇正式的工程化paper(Ad Click Prediction: a View from the Trenches)标志着FTRL有理论走向实践。之前在部门专门分享过一次FTRL的原理及在公司业务场景下的详细应用,包括xgboost+FTRL的实践,有时间得再详细整理成博客,里面的很多东西值得去深入探究。
TOCO(time-decaying online convex optimization)问题可以如下定义:
给定一个时间阶段T ≥ 1,以及一系列训练样本,用和分别表示特征和标签,则有:
常见的时间衰减函数有多项式衰减和指数衰减,这篇paper里使用了指数衰减函数,原因有2点:
- 工业届和学术界广泛使用
- 有助于后面的模型更新函数推导出递归的解析解
衰减函数定义如下:
首先回顾一下FTRL的特征权重更新策略。FTRL-Proximal代表了一族在线学习的手段,包含RDA,FOBOS,FTRL等,这些算法着重从理论上探讨了最优化算法在online学习场景下产生稀疏解的方法。这一族算法认为每一步的解都会产生损失,希望整体的损失小,因此为了这个目的,往往设计成每次的更新与前几步相似,步长递减,即学习率递减。
FTRL综合考虑了FOBOS和RDA的长处,其特征权重更新公式为:
TDAP的特征权重更新公式如下:
跟FTRL的求解方式一样,可以得到TDAP的解析解。在FTRL中,通过将特征权重的各个维度拆解为N个独立的标量最小化问题即可求得迭代解表达式。
公式(6)可以重写成如下形式:
到此为止,我们已经从数学上求解出了这个最优化问题,下面需要做的就是:如何得到递归的解析解,即:使用第t+1轮计算出来的各个参数,来更新当前第t轮的值?
从(9)式的递归解中可以看到,我们只需要关心两个表达式:和,我们对这两项分别变换:
的递归解:
的递归解:
因为,我们定义,则:
无论是FTRL还是TDAP,其算法流程都是:
(1)特征提取
(2)根据截断阈值更新每个feature的weight
(3)预估ctr,计算梯度
(4)更新临时变量
TDAP算法伪代码如下:
对比FTRL算法:
这里都使用了Logistic回归,TDAP算法相对FTRL使用了更多的临时变量,特征的每一维都需要记录:。
从伪代码中我么可以看到:在时间衰减函数的影响下,较老的数据对目标模型的影响进行了缩减,从而适应了数据的快速变化。
详细的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;
}
}