你好,游客 登录 注册 搜索
背景:
阅读新闻

机器学习笔记:FTRL-Proximal

[日期:2015-01-28] 来源:中国大数据  作者:凝人 [字体: ]

  1. 简介

  今天介绍的这个演算法,Follow-The-Regularized-Leader (FTRL) Proximal ,是Google于2011年 [1] 提出,2013年 [2] 加入修改并作了针对广告点击率 (Click Through Rate) 预测的应用探讨的一个机器学习演算法。在Kaggle上面两次CTR比赛冠军都使用这个演算法。

  这学期人工智慧课程我和阿牧、Tommy参加了Kaggle的CTR比赛。这次资料是由中国的网路行销公司提供 2014/10/21~30共四千万笔资料当训练集,2014/10/31四百万笔资料当测试,比较各队的预测值之对数损失(logarithmic loss)。目前我们使用这个演算法达到 0.394 的準确度,在全体排名到达前叁分之一。而事实上,前面的参赛者大多是使用FTRL演算法。

  这个演算法是基于OGD(online gradient descent),使其更加稀疏(sparsity)的版本。

  2. 演算法介绍

  FTRL的核心是一种online logistic regression,在塬始演算法上加入L1, L2 regularization和 adaptive learning,其演算法如下:

  

  

  T是每笔资料,I则是feature domain。更新每个变数的权重时,会参考L1的值,因此很能够达到稀疏性,同时,每个变数的更新速度都跟它先前的表现有关(G1:t)。除了L1,L2也被加进去进一步防止 over-fitting。

  3. 演算法实现

  这个演算法的 Python code下载地方在此,需要的记忆体很小,用一般CPU跑这次比赛的资料 (四千万笔资料,21个变数,开一个2^25的feature vector) 大概只要半个小时。提供者是Kaggle世界排名前两百的 Tinrtgu 大大。

  关于这个code的讨论和各种修改版本,可以到这裡来看众神人的讨论。

  4. Reference

  [1] Follow-the-regularized-leader and mirror descent: Equivalence theorems and L1 regularization. In AISTATS, 2011.H. B. McMahan.

  [2] Ad Click Prediction: a View from the Trenches. H. Brendan McMahan,Gary Holt, D. Sculley et al.

  一些反思:

  事实上我是透过比赛的讨论版上,Tingrtu的PO文才知道有这个演算法的。感谢他之余,也深感学术文化的差异。如果是我的话肯定不会把方法讲出来。事实上我认为它如果没公布这个方法,可能也只有前百名才能达到0.4以下。

  后记:

  第一次撰写类似学习笔记这类的文章,如果有写错或是写作技巧可以改进的地方,还请不吝在底下留言指教。事实上这个演算法的论文探讨的相当详细,包括在大量数据下可以怎么省记忆体同时维持预测率、feature drop-out等等。不过碍于我还是个菜鸟,还需要大量的时间才能读懂啊(汗)





收藏 推荐 打印 | 录入:Cstor | 阅读:
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款