精华内容
下载资源
问答
  • FTRL

    千次阅读 2018-11-04 22:54:14
    从loss function的形式来看:FTRL就是将RDA-L1的“梯度累加”思想应用在FOBOS-L1上,并施加一个L2正则项。【PS:paper上是没有加L2正则项的】 这样达到的效果是: 累积加和限定了新的迭代结果W**不要...

    一、算法原理

    二、算法逻辑

    三、个人理解

    • 从loss function的形式来看:FTRL就是将RDA-L1的“梯度累加”思想应用在FOBOS-L1上,并施加一个L2正则项。【PS:paper上是没有加L2正则项的】

    • 这样达到的效果是:

      • 累积加和限定了新的迭代结果W**不要离“已迭代过的解”太远**;

      • 因为调整后的解不会离迭代过的解太远,所以保证了每次找到让之前所有损失函数之和最小的参数;

      • 保留的RDA-L1中关于累积梯度的项,可以看作是当前特征对损失函数的贡献的一个估计【累积梯度越大,贡献越大。】

      • 由于使用了累积梯度,即使某一次迭代使某个重要特征约束为0,但如果后面这个特征慢慢变得稠密,它的参数又会变为非0;

      • 保留的RDA-L1中关于累积梯度的项,与v相加,总会比原来的v大,加起来的绝对值更容易大于L1的阈值,保护了重要的特征;

    • FTRL的巧妙之处在于:

      • 在MSE的前面乘以了一个和learning_rate有着神奇关系的参数σ_s。

      • 因为这个参数,保证了FTRL在不使用L1时和SGD保持了一致性。

    • FTRL使用的自适应learning_rate,其思想和 Adagrad Optimizer 类似的自适应思想:

      • 如果特征稀疏,learning_rate就大一点;

      • 如果特征稠密,learning_rate就小一点;

    • FTRL中为什么要同时兼顾FOBOS-L1和RDA-L1??

      • 因为不是为了产出稀疏而进行变化,真正的目的是产出有效的稀疏解。即稀疏又保留有效特征!!!

      • 稀疏靠RDA-L1,保留有效特征靠FOBOS-L1和RDA-L1的累积梯度思想。

    • 本质上,FTRL只是一种适用于online-learning的optimizer;

    • FTRL-Proximal中的Proximal的含义:

      • t+1次迭代的解,不能离t次迭代的解太远;

      • t+1次迭代的解,不能离0太远;

      • 是对具体约束的表达。

    小结:

    • FOBOS-L1:使用MSE+L1对w_{t+1/2}进行建模,目标是使调整后的梯度在离SGD结果附近的基础上,产出稀疏解;

    • RDA-L1:使用累积平均梯度 + L1 + L2进行建模,这里使用L2有两方面的理解:

      • 能产出极小值点;

      • 调整后的梯度不能与零点太远;

    展开全文
  • FTRL solver

    2020-11-28 21:11:59
    <p>Are there any plans of including FTRL solver to this library? I guess it's fairly straight forward. I'm sorry I might not be able to contribute it myself because I am not fluent in Cython ...
  • FTRL学习

    2018-06-12 15:40:12
    总结学习资源: 基于FTRL的在线CTR预测算法 在线学习算法FTRL详解
    展开全文
  • FTRL算法

    2019-12-15 14:45:30
    https://www.cnblogs.com/arachis/p/FTRL.html
    展开全文
  • 深入理解FTRL.pdf

    2020-11-09 10:39:02
    深入理解FTRL.pdf
  • 使用ftrl优化fm

    2019-01-11 15:47:20
    通过FTRL对FM模型进行优化,实现模型在线上的实时更新
  • FTRL 算法

    2017-08-07 10:36:06
    本文会尝试总结FTRL的发展由来,总结从LR -> SGD -> TG -> FOBOS -> RDA -> FTRL 的发展历程。本文的主要目录如下:  一、 反思魏则西事件。  二、 LR模型  三、 SGD算法  四、 TG算法  五、 ...

    本文会尝试总结FTRL的发展由来,总结从LR -> SGD -> TG -> FOBOS ->  RDA -> FTRL 的发展历程。本文的主要目录如下:

            一、  反思魏则西事件。

            二、  LR模型

            三、  SGD算法

            四、  TG算法

            五、  FOBOS算法

            六、  RDA算法

            七、  FTRL算法

            注:本文中间大部分引用了@fengyoung的博文。为了加深自己的理解,也把知识稍微整理了一下。

    一、 反思魏则西事件

            在文章刚开始,先谈到最近很火热的魏则西事件。魏则西是我的校友,我也比他大不了几岁,他因为患滑膜肉瘤在百度上搜索广告误导,在武警二院接受了未经验证允许临床使用的生物医疗疗法耗费了几乎所有的家产和延误了最佳治疗时机,最终去世人财两空。首先滑膜肉瘤目前医疗条件几乎是绝症,魏则西也已经是病程四期,而对待绝症时国内很多医生或者医院都会有两种选择: 1.  守着职业道德,直接说明结果建议不要继续尝试,以免人财两空;  2.  昧着良心,推荐很多赚钱的药物和治疗方案,挣大量的黑心钱。患者因为求生的意志和家人的爱,会抓住一点点的希望并且放大,而且会因为病程的发展留下的治疗急迫性,判断力会下降很多很多的。这件事情是很残酷的,医生挣了黑心钱,广告主挣了钱,患者却没有得到最佳的治疗方案。但其实仔细分析,整件事情的责任方医院和国家监管机构应该承担主要责任,违规临床使用生物疗法的公司也应当承担主要责任,然后百度也应当承担次要责任。魏则西和家人面对一点点的希望也选择搏一把,虽然失败了,但是很悲壮和值得尊敬。面对社会和现实,人总是那么渺小。也许我将来有一天也会得病,也许也是绝症,也许这对我和我家人很残酷,虽然很难但我希望我是理性的,可以默念生亦何欢,死亦何苦。但就现在来说,我希望我要珍惜生活、珍惜生命、珍惜身边的人。我也希望我要多多锻炼身体,保持健康的作息,多多开心珍惜每一天,多多爱我爱的人和爱我的人。

            在广告这个问题上,其实广告的目的是连接广告主和消费者,最大化广告服务商的利润的时最大化广告主的投资会报比。其实这就有一个隐藏的问题,广告服务商其实并未太多考虑消费者的利益和广告后面服务和商品的满意度,所以很多做广告的就会调侃,希望有一天在马路上,大家知道他是做广告的不会扔鸡蛋和鞋子。也许以后广告会有了更多的准入限制和广告后服务效果的追踪后,会好点。。。

    二、 逻辑回归

           言归正传,因为广告大部分是按照CPC计费的,而我们手里的流量是固定的,因此对每条广告请求我们就需要保证这条广告的展示收益更大。而广告收益是可以根据点击率、广告计费价格、广告质量度均衡决定的,所以我们就需要评估广告的质量度和点击率,本文就主要研究广告点击率预估中广泛使用的逻辑回归模型。在实际广告点击率预估的应用中,样本数目和特征(逻辑回归粗暴离散化后)的数目均可以达到上亿纬度,而LR因为其简单和易并行,并且基于复杂的特征工程后也能得到非常好的效果,所以在工业界获得了广泛的应用。

          逻辑回归,相对于线性回归是用来处理目标函数是离散数值的情况。它的映射函数和损失函数分别为:

                                                                      (1)                                                                                                (2)

          使用梯度下降法进行求解,得到迭代公式:

               

    1.  逻辑回归的优缺点:

          优点:  

              a. 简单

              b. 易于并行、速度快

          缺点:

              a. 需要复杂的特征工程

          注意事项:

              a. 输入特征需要离散化。

    三、 SGD算法

             对于如上LR的迭代公式来说,我们可以得到GD(Gradient Descent)的求解算法。(W为求解的参数,l(w, z)为损失函数)。

          

          可是如果我们对参数做一轮迭代求解,都需要遍历所有的样本,这在实际应用中未免迭代速度太慢,模型更新速度也太慢。而且做机器学习的时候往往更多的数据意味着更好的效果,我们能把线上实时的数据和样本标注也利用进来么?答案是 Yes。仔细研究参数的迭代我们可以发现,都是给定一个初始的参数W,通过迭代逐步求解出当前W下降的方向并更新W直到损失函数稳定在最小点。那么我们是不是可以取部分训练集作为原训练集的子集,使用这些子集做迭代,并逐步求解W的下降方向,逐步对W进行更新(理论证明未知)。特别的,如果我们每次取原训练样本的一个训练样本,对W的值逐步进行更新,那么我们就得到了SGD算法。

                 

                与SGD比较,GD需要每次扫描所有的样本以计算一个全局梯度,SGD则每次只针对一个观测到的样本进行更新。通常情况下SGD可以更快的逼近最优值,而且SGD每次更新只需要一个样本,使得它很适合进行增量或者在线计算(也就是所谓的Online learning)。

             特别的,迭代和选取模型的时候我们经常希望得到更加稀疏的模型,这不仅仅起到了特征选择的作用,也降低了预测计算的复杂度。在实际使用LR的时候我们会使用L1或者L2正则,避免模型过拟合和增加模型的鲁棒性。在GD算法下,L1正则化通常能得到更加稀疏的解;可是在SGD算法下模型迭代并不是沿着全局梯度下降,而是沿着某个样本的梯度进行下降,这样即使是L1正则也不一定能得到稀疏解。在后面的优化算法中,稀疏性是一个主要追求的目标。

    四、 TG算法

    1.  L1 正则化法

            由于L1正则项在0处不可导,往往会造成平滑的凸优化问题变成非平滑的凸优化问题,因此可以采用次梯度(Subgradient)来计算L1正则项的梯度。权重更新方式为:

             

           其中是一个标量,为L1正则化的参数;v是一个向量,sgn(v)为符号函数;称为学习率,通常将其设置为的函数;代表第t次迭代中损失函数的梯度。

    2.  简单截断法

             既然L1正则化在Online模式下也不能产生更好的稀疏性,而稀疏性对于高维特征向量以及大数据集又特别的重要,我们应该如何处理的呢?

             简单粗暴的方法是设置一个阀值,当W的某纬度的系数小于这个阀值的时候,将其直接设置为0。这样我们就得到了简单截断法。简单截断法以k为窗口,当t/k不为整数时采用标准的SGD进行迭代,当t/k为整数时,权重更新方式如下:

               

               

             这里是一个正数;V是一个向量。

    3.  梯度截断法

             简单截断法法简单且易于理解,但是在实际训练过程中的某一步,W的某个特征系数可能因为该特征训练不足引起的,简单的截断过于简单粗暴(too aggresive),会造成该特征的缺失。那么我们有没有其他的方法,使得权重的归零和截断处理稍微温柔一些呢?对,这就是梯度截断法,简单截断法和梯度截断法对特征权重的处理映射图对比如下:

                

               梯度截断法的迭代公式如下:

                

                                           (3)

               同样的梯度截断法也是以k为窗口,每k步进行一次截断。当t/k不为整数时,当t/k为整数时。从公式(3)可以看出决定了截断的区域,也决定了W的稀疏程度。这两个数值越大,截断区域越大,稀疏性也越强。尤其这两个值相等的时候,只需要调节一个参数就能控制稀疏性。根据公式(3),得到TG的算法逻辑如下:

             

             特别的对(3)进行改写,得到描述特征权重的更新方式为:

                    

                    

             如果令,截断公式变成:

                    

             此时TG退化成简单截断法。同样如果令,我们就可以得到L1正则化方法。

    四、 FOBOS算法

              FOBOS(Forward-Backward Splitting)是由John Duchi和Yoram Singer提出的。FOBOS算法把正则化的梯度下降问题分成一个经验损失梯度下降迭代和一个最优化问题。其中第二个最优化问题有两项:第一项2范数那项表示不能离loss损失迭代结果太远,第二项是正则化项,用来限定模型复杂度、抑制过拟合和做稀疏化等。

             

              由于求和公式中的每一项都是大于等于0的,所以公式(2)可以拆解成对特征权重每一纬度单独求解:

                          (2)

               首先假设w是(2)的最优解,则有。反正时代入,可以得到w=0是(2)的最优解。。。

               对v和w的取值分别进行求解可以得到:

               

               

               其中g_i^(t)为梯度G^(t)在纬度i上的取值。然后我们可以得到L1-FOBOS的算法逻辑:

               

    1.  L1-FOBOS与TG的关系  

               从公式3)可以看出,L1-FOBOS 在每次更新W的时,对W的每个纬度都会加以判定,当满足时对该纬度的特征进行截断,这个判定的含义是当一条样本的梯度不足以令对应纬度上的权重值发生足够大的变化时,认为在本次更新中该纬度不够重要,应当令其权重为0。

               对于L1-FOBOS特征权重的各个纬度更新公式(3),也可以写为如下形式:

                 

                如果令,L1-FOBOS与TG完全一致,L1-FOBOS是TG在特定条件下的特殊形式。

    五、 RDA算法

               之前的算法都是在SGD的基础上,属于梯度下降类型的方法,这类型的方法的优点是精度比较高,并且TG、FOBOS也能在稀疏性上得到提升。但是RDA却从另一个方面进行在线求解,并且有效提升了特征权重的稀疏性。RDA是Simple Dual Averaging Scheme的一个扩展,由Lin Xiao发表与2010年。

              在RDA中,特征权重的更新策略包含一个梯度对W的积分平均值,正则项和一个辅助的严格凸函数。具体为:

    。其中<G(t),W>表示梯度G对W的积分平均值,包含了之前所有梯度的平均值;为正则化项,表示一个非负且非自减序列,是一个严格的凸函数。

    1.  算法原理

               之前的算法都是在SGD的基础上,属于梯度下降类型的方法,这类型的方法的优点是精度比较高,并且TG、FOBOS也能在稀疏性上得到提升。但是RDA却从另一个方面进行在线求解,并且有效提升了特征权重的稀疏性。RDA是Simple Dual Averaging Scheme的一个扩展,由Lin Xiao发表于2010年。

              L1-RDA特征权重各个纬度更新方式为:

                    

              这里当某个纬度上累积梯度平均值小于阀值的时候,该纬度权重将被设置为0,特征稀疏性由此产生。

              对比L1-FOBOS我们可以发现,L1-FOBOS是TG的一种特殊形式,在L1-FOBOS中,进行截断的判定条件是

    ,通常会定义为正相关函数。因此L1-FOBOS的截断阀值为,随着t增加,这个阀值会逐渐降低。而相比较而言L1-RDA的截断阀值为,是一个固定的常数,因此可以认定L1-RDA比L1-FOBOS更加aggressive。此外L1-FOBOS判定是针对单次梯度计算进行判定,避免由于训练不足导致的截断问题。并且通过调节一个参数,很容易在精度和稀疏性上进行权衡。

    六、FTRL算法

       有实验证明,L1-FOBOS这一类基于梯度下降的方法有较高的精度,但是L1-RDA却能在损失一定精度的情况下产生更好的稀疏性。如何能把这两者的优点同时体现出来的呢?这就是

    1.  L1-FOBOS与L1-RDA在形式上的统一:

    L1-FOBOS在形式上,每次迭代都可以表示为(这里我们令)

    FTRL综合考虑了FOBOS和RDA对于正则项和W的限制,其特征权重为:


    注意,公式(3)中出现了L2正则项,而论文[2]的公式中并没有这一项,但是在2013年发表的FTRL工程化实现的论文中却使用了L2正则化项。事实上该项的引入并不影响FTRL的稀疏性,仅仅相当于对最优化过程多了一个约束,使得结果求解更加平滑。

    公司(3)看上去很复杂,更新特征权重貌似非常困难。不妨将其改写。将其最后一项展开等价于求解下面的这样一个最优化问题:


    ,于是针对特征权重的各个纬度将其拆解成N个独立的标量最小化问题。上式最后一项相对于W说是一个常数项,并且令,上式等价于:

    到这里,我们遇到了与RDA求解类似的最优化问题。用相同的分析方法可以得到:


    上式可以看出,引入L2正则化对于FTRL结果的稀疏性产生任何影响。

    在一个标准OGD中使用的是一个全局学习策略,这个策略保证了学习率是一个正的非增长序列,对于每个特征的纬度都是一样的。

    考虑特征纬度的变化率:如果特征1比特征2的变化更快,那么纬度1上学习率应该下降的比较快。我们就很容易可以用某个纬度上梯度分量来反映这种变化率。在FTRL中纬度i上的学习率是这样计算的:

    。由于,所以公式(4)中有,这里的是需要输入的参数,公式(4)中学习率写成累加的形式,是为了方便理解后面FTRL的迭代计算逻辑。

    伪码采用的事L1和L2混合正则,即实际的迭代是如下形式:


    总结:

    从类型上来看,简单截断法、TG、FOBOS属于同一类,都是梯度下降类的算法,并且TG在特定条件可以转换成简单截断法和FOBOS;RDA属于简单对偶平均的扩展应用;FTRL可以视作RDA和FOBOS的结合,同时具备二者的优点。目前来看,RDA和FTRL是最好的稀疏模型Online Training的算法。FTRL并行化处理,一方面可以参考ParallelSGD,另一方面可以使用高维向量点乘,及梯度分量并行计算的思路。

    参考文献:

    1.  http://www.wbrecom.com/?p=342   本文显然大量参考了该文章。 作者写的确实好,我再写一遍以便加深自己的理解。

    展开全文
  • 在线学习FTRL

    2021-01-06 12:06:10
    <div><p>在线学习训练支持FTRL ,以后会支持其它的算法吗,问个小白的问题,为什么在线学习只支持线性的,可以解决吗</p><p>该提问来源于开源项目:alibaba/Alink</p></div>
  • FTRL算法是吸取了FOBOS算法和RDA算法的两者优点形成的Online Learning算法。读懂这篇文章,你需要理解LR、SGD、L1正则。FOBOS算法前向后向切分(FOBOS,Forward Backward Splitting)是 John Duchi 和 Yoran Singer ...
  • ftrl算法

    2017-09-02 11:00:18
    http://blog.csdn.net/luoyexuge?viewmode=list  牛逼的博客学习 http://www.cnblogs.com/luctw/p/4757943.html  RDA online Learning... ...http://blog.csdn.net/yxcbluesky/article/details/43155879  ftrl
  • FTRL的理解

    万次阅读 2018-07-20 15:55:32
    个人理解:FTRL是针对LR学习器,设计了一种独特的梯度下降更新方法 从Logistic Regression到FTRL Logistic Regression在Linear Regression的基础上,使用sigmoid函数将y=θx+b的输出值映射到0到1之间,且log(P(y=1...
  • 之前实现过Parameter Server框架下的分布式FTRL优化算法,用的是DMLC的ps-lite。在PS架构下,集群分为worker、server、scheduler三种线程。其中worker负责梯度的计算,server负责参数的更新和分布式存储,scheduler...
  • FTRL代码实现

    2018-11-11 16:54:44
    FTRL(Follow The Regularized Leader)是一种优化方法,就如同SGD(Stochastic Gradient Descent)一样。这里直接给出用FTRL优化LR(Logistic Regression)的步骤: 其中pt=σ(Xt⋅w)pt=σ(Xt⋅w)是LR的预测函数...
  • FTRL_FM_LR.html

    2020-03-06 11:41:43
    使用FM和LR分别进行了FTRL优化,包含详细的调试步骤
  • FTRL算法理解

    2019-09-20 15:27:51
    本文主要是对FTRL算法来源、原理、应用的总结和自己的思考。 解决的问题 1、训练数据层面:数据量大、特征规模大 2、常用的LR和FM这类模型的参数学习,传统的学习算法是batch learning算法,无法有效地处理大规模的...
  • FTRL(Follow The Regularized Leader)是一种优化方法,就如同SGD(Stochastic Gradient Descent)一样。这里直接给出用FTRL优化LR(Logistic Regression)的步骤: 其中pt=σ(Xt⋅w)是LR的预测函数,求出pt的...
  • FTRL-Proximal

    2019-08-26 14:55:23
    我们从部署的CTR预测系统的设置中提供了一些案例研究和从最近的实验中提取的话题,包括基于FTRL-Proximal在线学习算法(具有出色的稀疏性和收敛特性)以及使用每个坐标学习率的传统监督学习语境的改进。 我们...
  • FTRL算法详解

    2019-07-23 15:48:17
    从loss function的形式来看:FTRL就是将RDA-L1的“梯度累加”思想应用在FOBOS-L1上,并施加一个L2正则项。【PS:paper上是没有加L2正则项的】 这样达到的效果是: 累积加和限定了新的迭代结果W**不要离“已迭代...
  • FTRL优化算法

    2018-01-18 11:49:00
    飞机票 FTRL 转载于:https://www.cnblogs.com/zyber/p/8309428.html
  • FTRL 算法理解

    千次阅读 2018-08-03 15:45:16
    Online LR—— FTRL 算法理解 Online Learning定义 Online Learning是一种模型训练的方法,能够根据线上反馈数据,实时快速的进行模型调整,使得模型及时反映线上的变化,提高线上预测的准确率。Online Learning的...
  • 在线学习算法FTRL-Proximal原理

    万次阅读 2016-04-23 17:25:37
    由于FTRL收敛速度快、能产生稀疏解等优势,FTRL在计算广告领域的重要性日益凸显。 2.回顾SGD 可以参考文章利用SGD方法训练FM模型 地址 定义: 模型参数: 第t个样本: 自定义Loss Function 然后可以利用随机...
  • 排序模型-FTRL

    2021-04-27 00:53:23
    排序模型进阶-FTRL 1 问题 在实际项目的时候,经常会遇到训练数据非常大导致一些算法实际上不能操作的问题。比如在推荐行业中,因为DSP的请求数据量特别大,一个星期的数据往往有上百G,这种级别的数据在训练的时候...
  • FTRL&FM

    千次阅读 2016-11-16 15:06:38
    1. Feature Retire: 防止随着训练持续进行,模型越来越大;将较长时间不修改的feature,从模型中删去;... FTRL最优化问题的公式里,包含3个部分:迎合过往梯度,正则化增加稀疏性,别离以往的W偏离过远; ...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 313
精华内容 125
关键字:

ftrl