FOLLOW THE REGULARIZED LEADER 算法总结

之前在个人的 blog 中介绍过FTRL算法,也写过文章如下:

本文在知乎上也有发表,标题是《FOLLOW THE REGULARIZED LEADER (FTRL) 算法总结》,链接是https://zhuanlan.zhihu.com/p/32903540 .在之前的网站(zr9558.com)上面也整理过这些文章,供读者参考。

1. TRUNCATED GRADIENT (TG) 算法简介

2. FORWARD-BACKWARD SPLITTING (FOBOS) 算法简介

3. REGULARIZED DUAL AVERAGING ALGORITHM (RDA)

4. FOLLOW THE REGULARIZED LEADER (FTRL) 算法

现在做在线学习和 CTR 常常会用到逻辑回归(Logistic Regression),而传统的批量(batch)算法无法有效地处理超大规模的数据集和在线数据流,美国的 Google 公司先后三年时间(2010年-2013年)从理论研究到实际工程化实现的FTRL(Follow-the-regularized-Leader)算法,在处理诸如逻辑回归之类的带非光滑正则化项(例如 L1 范数,做模型复杂度控制和稀疏化)的凸优化问题上性能非常出色。

通常,优化算法中的 gradient descent 等解法,是对一批样本进行一次求解,得到一个全局最优解。但是,实际的互联网广告应用需要的是快速地进行模型的更新。为了保证快速的更新,训练样本是一条一条地过来的,每来一个样本,模型的参数对这个样本进行一次迭代,从而保证了模型的及时更新,这种方法叫做在线梯度下降法(Online Gradient Descent)。

在应用的时候,线上来的每一个广告请求,都提取出相应的特征,再根据模型的参数,计算一个点击某广告的概率。在线学习的任务就是学习模型的参数。所谓的模型的参数,其实可以认为是一个目标函数的解。跟之前说的根据批量的样本计算一个全局最优解的方法的不同是,解这个问题只能扫描一次样本,而且样本是一条一条地过来的。

当然这会有误差,所以为了避免这种误差,又为了增加稀疏性,有人又想到了多个版本的算法,Google 公司有人总结了其中几种比较优秀的,例如 FOBOS,AOGD 和微软的 RDA,同时提出了 Google 自己的算法 FTRL-Proximal。其中,FTRL-Proximal 在稀疏性和精确度等方面表现都比较好。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180113G0EAOZ00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券