标题是一篇来自Google广告团队的一篇论文，因为广告是很多互联网公司的重要收入来源，Google、Facebook、微软、阿里巴巴、百度、腾讯等公司内部都有着完善的广告系统来支撑其广告业务。

这篇论文主要讲的是广告系统里最基础的一个子系统-点击率预估系统。点击率预估，顾名思义就是根据环境和广告的类型，来估计用户有多大的可能性点击当前的广告。这个预估值会用于广告系统的其他组件，比如对广告主（投放广告的客户）的计费模块。因此，点击率预估的准确性和实时性就变得十分重要。

今天和大家分享一下这篇论文

这篇文章的作者有16人，他们都是来自Google西雅图、匹兹堡、硅谷以及剑桥等地办公室的研究人员和工程师，这篇论文也是作者们协作的技术成果。这里面有两位作者值得介绍一下。第一位是论文的第一作者布兰登（H. Brendan McMahan）。布兰登早年在卡内基梅隆大学计算机系获得博士学位。他的博士生导师是戈登（Geoff Gordon）以及布卢姆（Avrim Blum），这两位都是卡内基梅隆大学机器学习界的权威教授。布兰登本人长期对优化算法有深入的研究，这篇论文的重要核心算法就来自于他的研究成果。文章的另外一位作者斯卡利（D. Sculley）从塔夫茨大学（Tufts University）博士毕业之后，一直在Google的匹兹堡分部工作，并着手研究大规模机器学习系统，其中重要的代表性研究成果是如何把回归问题和排序问题结合起来（发表于KDD 2010年）。斯卡利曾经是一个著名的开源大规模机器学习软件包sofia-ml的作者，里面实现了一个大规模版本的RankSVM，一度受到关注。

文章核心算法-在线逻辑回归

逻辑回归是要对二元分类问题进行建模，模型的核心是通过一组（有可能是非常巨大规模的）特征以及所对应的参数来对目标的标签进行拟合。这个拟合的过程是通过一个叫逻辑转换或函数来完成的，使得线性的特征以及参数的拟合能够非线性转换为二元标签。

普通的逻辑回归并不适应大规模的广告点击率预估。有两个原因，第一，数据量太大。传统的逻辑回归参数训练过程都依靠牛顿法（Newton's Method）或者L-BFGS等算法。这些算法并不太容易在大规模数据上得以处理。第二，不太容易得到比较稀疏（Sparse）的答案（Solution）。也就是说，虽然数据中特征的总数很多，但是对于单个数据点来说，有效特征是有限而且稀疏的。

我们希望最终学习到的模型也是稀疏的，也就是对于单个数据点来说，仅有少量特征是被激活的。传统的解法，甚至包括一些传统的在线逻辑回归，都不能很好地解决答案的稀疏性问题。

这篇文章提出了用一种叫FTRL（Follow The

Regularized Leader）的在线逻辑回归算法来解决上述问题。FTRL是一种在线算法，因此算法的核心就是模型的参数会在每一个数据点进行更新。FTRL把传统的逻辑回归的目标函数进行了改写。

新的目标函数分为三个部分：

第一部分是一个用过去所有的梯度值（Gradients）来重权（Re-Weight）所有的参数值；

第二部分是当前最新的参数值尽可能不偏差之前所有的参数值；

第三个部分则是希望当前的参数值能够有稀疏的解（通过L1来直接约束）。

从这三个部分的目标函数来看，这个算法既能让参数的变化符合数据规律（从梯度来控制），也能让参数不至于偏离过去已有的数值，从而整个参数不会随着一些异常的数据点而发生剧烈变化。

在算法上另外一个比较新颖的地方，就是对每一个特征维度的学习速率都有一个动态的自动调整。传统的随机梯度下降（Stochastic Gradient Descent）算法或是简单的在线逻辑回归都没有这样的能力，造成了传统的算法需要花很长时间来手工调学习速率等参数。

同时，因为每一个特征维度上特征数值的差异，造成了没法对所有特征选取统一的学习速率。而FTRL带来的则是对每一个维度特征的动态学习速率，一举解决了手动调整学习算法的学习速率问题。简单说来，学习速率就是根据每一个维度目前所有梯度的平方和的倒数进行调整，这个平方和越大，则学习速率越慢。

文章也特别提出，虽然大家都知道在点击率预估这样非常不对称的问题上（也就是正例会远远少于负例）需要对负样本进行采样，但是这里面需要注意的是直接采样会对参数的估计带来偏差。同时文章也提出了需要对模型的最后预测进行调整（Calibration），使得模型的输出可以和历史的真实点击率分布相近。这一点对于利用点击率来进行计费显得尤为重要，因为有可能因为系统性的偏差，预测的数值整体高出或者整体低于历史观测值，从而对广告主过多计费或者过少计费。

这篇论文是难得一见的工业界级别的科技论文分享。从KDD工业组的角度来说，很有借鉴意义；从业界贡献来说，除了广告之外，FTRL也被广泛应用到推荐系统等领域。