注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

罗维的博客

{ 关注机器学习、计算广告、自然语言处理、大规模数据处理等 }

 
 
 
 
 

日志

 
 

FTRL算法理解  

2015-12-02 23:49:23|  分类: 机器学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

引言

       在工业界,越来越多的业务需要大规模机器学习,不单参与训练的数据量大,模型特征量的规模也大。例如点击率预估,训练数据量在TB量级,特征量在亿这个量级,业内常用LR(Logistic Regression)和FM(Factorization Machines)为点击率预估建模。对LR、FM这类模型的参数学习,传统的学习算法是batch learning算法,它无法有效地处理大规模的数据集,也无法有效地处理大规模的在线数据流。这时,有效且高效的online learning算法显得尤为重要。

       SGD算法[1]是常用的online learning算法,它能学习出不错的模型,但学出的模型不是稀疏的。为此,学术界和工业界都在研究这样一种online learning算法,它能学习出有效的且稀疏的模型。FTRL(Follow the Regularized Leader)算法正是这样一种算法,它由Google的H. Brendan McMahan在2010年提出的[2],后来在2011年发表了一篇关于FTRL和AOGD、FOBOS、RDA比较的论文[3],2013年又和Gary Holt, D. Sculley, Michael Young等人发表了一篇关于FTRL工程化实现的论文[4]。如论文[4]的内容所述,FTRL算法融合了RDA算法能产生稀疏模型的特性和SGD算法能产生更有效模型的特性。它在处理诸如LR之类的带非光滑正则化项(例如1范数,做模型复杂度控制和稀疏化)的凸优化问题上性能非常出色,国内各大互联网公司都已将该算法应用到实际产品中。

       文章[5]是篇很好的介绍FTRL算法的中文资料,从TG算法、FOBOS算法开始,到RDA算法,最后到FTRL算法,一脉相承,而且各个算法都有推导过程,值得认真体会。

       这篇文章不会赘述文章[5]中的内容,而是介绍FTRL算法与SGD算法之间存在的另一种联系。这个联系在网络上似乎没有文章介绍,可能是因为这个细节不那么重要,但倘若了解了此细节,能更好的体会到FTRL算法为啥跟SGD算法有联系。

FTRL算法与SGD算法的联系

       (考虑到网易博客不能有效的支持数学公式的编辑,为推理清楚,暂时就用截图方式。如有需要,读者可以联系笔者索要此文的PDF文件。另外笔者将来也会在github上新开博客以加强文章的可读性。)
FTRL算法理解 - vividfree - 罗维的博客         
          通过上面的推导证明,我们看到公式3与公式1确实等价。由此可以更好的体会下公式2为啥长这样子,其左边两项承担了SGD算法的功能,而最右边的一项承担的是得到稀疏模型的功能。因为有这样的一种数学含义在背后,所以才好放心的下结论说,FTRL算法融合了RDA算法能产生稀疏模型的特性和SGD算法能产生更有效模型的特性,也就是说能学习出有效的且稀疏的模型。

参考文献

[1] Stochastic gradient descent. https://en.wikipedia.org/wiki/Stochastic_gradient_descent

[2] H. Brendan McMahan & M Streter. Adaptive Bound Optimization for Online Convex Optimization. In COLT, 2010

[3] H. Brendan McMahan. Follow-the-Regularized-Leader and Mirror Descent: Equivalence Theorems and L1 Regularization. In AISTATS, 2011

[4] H. Brendan McMahan, Gary Holt, D. Sculley, Michael Young, Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov, Daniel Golovin, Sharat Chikkerur, Dan Liu, Martin Wattenberg, Arnar Mar Hrafnkelsson, Tom Boulos, Jeremy Kubica, Ad Click Prediction: a View from the Trenches. In ACM SIGKDD, 2013

[5] 冯扬, 在线最优化求解


本文链接:FTRL算法理解
本文为原创,转载请注明来源:罗维的博客,谢谢!^^
  评论这张
 
阅读(2757)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017