在最近几年的工业中，FTRL基本上相当于在线学习。2013年，谷歌的论文adclick prediction : AviewFromthetrenches给出了FTRL的工程实现。15年开始在国内流行，我们组当时就尝试过。后来16年又做了一次，没有明显的效益，但是推广的时候会有一些变化。据了解，当时淘宝一个主场景的实验结论和我们是一致的。那时候大家追求快和粗糙还有其他各种原因。一看没有收获，就没继续了。最近，随着我们在大规模离散化特征方面的实践，我们发现当时的思维存在一些问题。当时使用的特征分布变化的概率很小，所以没有必要使用ftrl。最近开始重新实验FTRL(交了学费)。从实用的角度来看，不考虑线上的好处，FTRL只有在训练速度更快、使用资源更少的情况下，才足以吸引各大公司使用。

FTRL的代码实现非常简单，已经得到了腾讯开源的PSangel的支持。摘录如下：

FTRL是一种常用的在线学习优化算法，方便、实用、有效，常用于在线更新CTR预测模型。之前的传统实现在Storm中更常见。然而在实际应用中，数据集的维数往往较大，模型稀疏。这种情况下SparkStreaming结合Angel其实效果会更好，而且代码少，性能稳定。

一直以来，我只知道如何使用FTRL，却不知道它是怎么来的。最近看了三篇H.BrendanMcMahan的论文，也看了一些网上的资料，有了大概的了解。因为这方面有很多好的资料，所以本文将从初学者的角度做一个指南，讲解一些背景知识和概念，希望对大家有所帮助。网上学习的优化知识很多，比如证明regretbounds，但毕竟我更关心这些算法是如何迭代的，也就是权重w是如何更新的。因为网上写公式太复杂，参考文献中的推导又很详细，所以本文尽量少用公式。

维基对在线学习的定义如下：

在computerscience中，onlinemachineellingisamethodfmachineellinginwhdatabemesavailableinasequentialorderandisusedtoupdateourbestpredictorforfuturedataateachstep，作为对立的tobatchlearning技术，它通过learning产生bestpredictor。

在工业界，不仅训练涉及的数据量大，而且模型特征的规模也很大。比如点击率估算的时候，特征规模往往会在十亿级别，训练数据很容易超过TB，资源压力很大。Spark集群中的高性能服务器非常昂贵。当然有钱的厂商可以叠机来做，大部分公司还是要权衡的。另外，类似于电子商务的业务，会有很多场景需要单独建模。如果能从批量转到在线学习，会有明显的经济效益。

Onlinelearning基于流数据，不能直接优化，一般选择后悔作为优化目标。看看两者的公式，

公式(1)

公式(2)

直观的了解两者的区别，批量计算损耗，得到一个新的Wn，再计算损耗，追求损耗最小。后悔则是每t个样本就来一次，更新W得到Wt，追求累积后悔最小的思想，有点贪心。

前言

在Onlinelearning的场景中，直观上不能使用batch的梯度下降。可以用mini-batch或者SGD(历史梯度)吗？尤其是SGD，我们来看看SGD的权重更新公式：

公式(3)

自然满足了onlinelearning的需求，onlinegradientdescent就是这个思路。但是这里有一个严重的问题。SGD不能带来稀疏解。即使加入L1正则化，也可以批量获得稀疏解，但不能在线获得。前面说过，类似ctr预测的模型的特征空间在亿级，好的公司在亿级。训练稀疏解失败意味着没有办法实际使用模型。网上有很多解释说这个SGD给不出稀疏解。比如浮点计算很难真正变成0。我个人更倾向于这样的解释：

与Batch不同，Online中的每次更新都不是沿着全局梯度下降，而是沿着一个样本的梯度方向下降，整个优化过程变得像一个& quot随机& quot搜索过程(SGD中随机的由来)，所以即使在线优化解采用L1正则化，也很难产生稀疏解。

背景知识

在线学习解决什么问题

学术界和工业界都在研究如何学习高精度稀疏模型。从最简单的思路开始，既然SGD不能直接得到稀疏解，我们可以把小于某个阈值的权重设置为0，但是因为online是样本来训练，所以可能是因为训练不足。

导致了weight小，这样简单截断损失很大。随后FOBOS、RDA、FTRL等算法提出，其中RDA是微软10年的工作，FTRL是google的H.BrendanMcMahan3年的工作，FTRL结合了FOBOS高精度以及RDA较好的稀疏性的特点。一开始接触这块，很容易陷入到公式细节中，无法建立大局观，重点理解下面两句话中的观点，可免于在公式的推导中迷失：

优化相关的一些背景知识

拉格朗日乘子和KKT条件

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

次梯度

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

好文筛选

从SGD到TG、FOBOS到FTRL的原理

首推这篇[1]

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

FOBOS/RDA/FTRL统一形式下的对比分析

H.BrendanMcMahan在论文Follow-the-regularized-leaderandmirrordescent:EquivalencetheoremsandL1regularization里从形式上统一了几种算法，然后做了对比分析，其中FOBOS被改写为累计梯度的形式。上面的公式分位三个部分：

1代表梯度或累积梯度，RDA区别于FOBOS是考虑累计梯度。2代表正则项3代表限制了x的变化不能离过去太远或者离0点太远。其中x可以理解成模型的weight。这篇论文也写的比较容易懂，建议读下。

FTRL的工程细节

主要是几个方面：

由于长尾，大部分特征是稀疏的，且频次很低，online的场景无法用batch的方式去统计特征频次。论文提了两个方案，以泊松概率p决定特征是否更新和建立BloomFilterInclusion。我看大部分实现都是用BloomFilter。对浮点数重编码，变的更小。TrainingManySimilarModelsASingleValueStructure用计数去替换学习率的计算中的累计梯度，可以又快又省。对负样本重采样。但会改变数据分布，所以可以给重采样的样本加上权重。

具体细节可以看这篇文章：[2]

，讲的很好，细节不再赘述。也可以直接看原论文：AdClickPrediction:aViewfromtheTrenches，这部分讲的通俗易懂。

PS:里面关于TrainingManySimilarModels和ASingleValueStructure两部分，不是很理解它的业务场景。还请有了解的小伙伴分享下。

FTRL和SGD的关系

有一篇文章提到FTRL和上面公式是等价的，角度不一样，比较有意思，参考：[3]

可以加深对于FTRL公式的理解：

引用一段原文：

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

总结

炒了个冷饭，已经没有什么可写的了，因此做个导读给大家。头条不让放链接，大家可以去看我的专栏，图片的水印。

参考文献：

[1]在线最优解

[2]各大公司广泛使用的在线学习算法FTRL详解

[3]understanding-FTRL-algorithm

[4]Subgradient.wiki

[5]H.BrendanMcMahan&MStreter.AdaptiveBoundOptimizationforOnlineConvexOptimization.InCOLT,

2010

[6]H.BrendanMcMahan.Follow-the-Regularized-LeaderandMirrorDescent:EquivalenceTheoremsandL1

Regularization.InAISTATS,2011

[7]H.BrendanMcMahan,GaryHolt,D.Sculley,MichaelYoung,DietmarEbner,JulianGrady,LanNie,Todd

Phillips,EugeneDavydov,DanielGolovin,SharatChikkerur,DanLiu,MartinWattenberg,ArnarMarHrafnkelsson,TomBoulos,JeremyKubica,AdClickPrediction:aViewfromtheTrenches.InACMSIGKDD,2013

[8]AdClickPrediction:aViewfromtheTrenches