>

在线学习(Online Learning)导读

- 编辑:兴宁市测绘与空间地理信息 -

在线学习(Online Learning)导读

  这几年在工业界,FTRL基本等价于在线年google的论文:Ad Click Prediction:a View from the Trenches,给出了FTRL的工程实现,15年的时候,国内开始比较火,我们组也是那个时候尝试了一把,后来16年又搞了一次,没有什么明显的收益,只是在大促的时候会有些变化。据了解,当时淘宝某个主场景的实验结论和我们一致。当时大家追求快糙猛以及各种其他原因,一看没有收益,就没有继续。最近随着我们在大规模离散化特征上的实践,发现当时的思路有些问题,当时的使用的特征,随时间发生分布变化的概率小,没有必要用ftrl。最近开始重新实验FTRL(交了一笔学费)。从实践的情况来看,先不论线上的收益,仅当FTRL训练的更快,使用的资源更少,就足以吸引各大公司使用。

  FTRL的代码实现非常简单,腾讯的开源PS angel上已经支持,摘抄一段:

  FTRL是一种在线学习的常见优化算法,方便实用,而且效果很好,常用于更新在线的CTR预估模型。之前的传统实现多见于Storm。但是实际应用中,数据集的维度往往很大,且模型稀疏性,这种Case下,用Spark Streaming结合Angel,其实会有更好的效果,而且代码很少,性能稳健。

  l/blob/master/docs/algo/ftrl_lr_spark.md

  一直以来,只是知道FTRL怎么用,而不了解是怎么来的。最近抽了一段时间,翻阅了H.Brendan McMahan的三篇论文,并看了一些网上的资料,有了大致的认知,由于这方面好的资料不少,本文从初学者的角度去做一份导读,解释一些背景知识和概念,希望能帮助到大家。在线学习里有不少是最优化的知识,比如证明regret bounds,但我毕竟在工业界,更关心这些算法是怎么做迭代的,即权重W是怎么更新的。由于在线写公式太繁琐了,且参考文献里面的推导很详细,本文尽量少用公式。

  在工业界,不单参与训练的数据量大,模型特征量的规模也大。比如点击率预估,往往特征规模会在亿级别,训练数据很容易过TB,对资源的压力很大。Spark集群的一台高性能的服务器是很贵,有钱的大厂当然可以堆机器去搞,大部分公司还是要掂量下。另外,类似电商这种业务,会有许多场景的需要单独做模型。如果能够从batch转换到online learning,有明显的经济收益。

  online learning是基于stream的data,无法直接对目标优化,普遍会选择regret作为优化目标。看下二者的公式,

  公式(2)直观理解二者的区别,Loss是在一次batch计算完,得到了新的Wn,然后计算loss,追求loss最小。而Regret是每t个样本来,更新w后得到Wt,追求累计regret最小,有点贪心的思想。

  公式(3)天然符合online learning的需求,online gradient descent就是这个思路。但这里有个严峻的问题,SGD不能带来稀疏解。就算增加L1正则,在batch的时候可以得到稀疏解,但在online的时候却不行。前面提到过,类似ctr预估的模型的特征空间在亿级别,好的公司在百亿级别,不能训练出稀疏解即代表没有办法实际使用模型。网上关于这个SGD不能给出稀疏解有很多解释,比如认为由于浮点数计算,难以线. 个人更倾向于这个解释:

  不同于 Batch,Online 中每次 的更新并不是沿着全局梯度进行下降,而是沿着某个样本的产生的梯度方向进行下降,整个寻优过程变得像是一个“随机” 查找的过程(SGD 中 Stochastic 的来历),这样 Online 最优化求解即使采用 L1 正则化的方式, 也很难产生稀疏解。

  学术界和工业界都在研究能学习出高精度且稀疏的模型。先从最简单的想法开始,既然SGD不能直接得到稀疏解,我们可以将小于一定阈值的weight置为0,但由于online是一个样本过来就训练,那么就有可能因为训练不充分导致了weight小,这样简单截断损失很大。随后FOBOS、RDA、FTRL等算法提出,其中RDA是微软10年的工作,FTRL是google的H. Brendan McMahan 3年的工作,FTRL结合了FOBOS高精度以及RDA较好的稀疏性的特点。一开始接触这块,很容易陷入到公式细节中,无法建立大局观,重点理解下面两句话中的观点,可免于在公式的推导中迷失:

  这块在公式推导里会用到,简单来讲Online场景面对的目标函数,很多时候是带约束条件的。举个简单的例子讲,LR的交叉熵loss函数,在没有加正则前,是无约束的优化问题,加了正则并限制正则的大小,则变成了一个有约束的问题。具体可以分为三种,无约束优化问题、有等式约束优化问题以及不等式约束的优化问题,其中等式约束的优化问题和不等式约束问题分别可以通过拉格朗日乘子和KKT条件来转换为无约束问题。细节可以参考后面提到的几篇文章。

  上面章节提到了怎么处理L1是关键,而L1正则化在0处不可导, L1本身都是凸函数,因此可以采用次梯度代替其梯度。其中次梯度(subgradient)一般是个集合,[左导数,右导数],举个例子,y=x,次梯度的集合为[-1,1]。

  写的很详细,是不可多得的优质中文资料,介绍了TG、FOBOS、RDA以及FTRL的算法原理,并有详细的推导,里面有一些符号错误,但不影响理解,以模型参数迭代更新的方式为主线,记住前文提到的两个核心问题,读起来事半功倍,强烈建议读下原文,本文不再赘述。

  具体细节可以看这篇文章:各大公司广泛使用的在线学习算法FTRL详解,讲的很好,细节不再赘述。也可以直接看原论文:Ad Click Prediction:a View from the Trenches,这部分讲的通俗易懂。

  由此可以更好的体会下公式为啥长这样子,其左边两项承担了SGD算法的功能,而最右边的一项承担的是得到稀疏模型的功能。因为有这样的一种数学含义在背后,所以才好放心的下结论说,FTRL算法融合了RDA算法能产生稀疏模型的特性和SGD算法能产生更有效模型的特性,也就是说能学习出有效的且稀疏的模型。

  Online方式点击率预估时学习率不断变小,是否可能追不上目标函数的变化?

本文由在线导读发布,转载请注明来源:在线学习(Online Learning)导读