发帖
雷达卡
If we do not do this work at the same time we might hava no opinons on how to shoose.
这是一篇工程领域优化问题的文章。
Ad Click Prediction: a View from the Trenches From Google
Introduce
FTRL_Proximal online learning algorithm同传统的监督机器学习算法相比较。
还有传统机器学习领域的新挑战：
节约内存的技巧；可视化performance;可靠的confidence estimates;一些看起来没什么用的方向；
论文观点在强调理论先进性和工业设定的密切联系；在复杂的动态系统中真正的挑战是什么？
机器学习在在线广告领域很成功；搜索广告，背景广告，展示广告，实时竞价对于CTR 预估的要求更快，更准，更可靠。
问题设定10多年前都是inconceivable.典型的工业模型每天需要预测几十亿个预测，使用很大的特征空间和很大的数据预测。
本文的例子是Google的搜索广告实验数据，我们关注到了被忽略的一些问题，预测的可信度，校准，特征管理等问题。
2.系统Overview
用户搜索ｑ，系统给它匹配一组广告。竞价机制决定用哪些广告，怎么排序，如果点了广告该收多少。如果这个广告展示了
点击的概率是多少--P(Click|q,a).
系统特征来自地方，包括查询，广告文本，广告相关数据，数据确实是很稀疏，每种例子只有很少量的非零数据。
使用到方法正则化的逻辑回归，模型需要随着新数据的加入迅速地更新，这样训练数据集将变很大，数据来自Photon流服务。
大规模学习被研究很多，本文重点不在介绍系统细节。我们重点强调Google大脑提供的同Downpour SGD相似的训练算法，不同之处是我们只训练了一层单层模型而不是多层模型，这样以来我们能处理的数据集量和模型就比已知的都大，有几十亿的系数。因为训练的模型被复制到很多数据中心，所以训练中主要关注响应时间。
3.在线学习算法以及稀疏性
在大规模学习领域一般线性模型有很多好处。尽管特征向量可能有几十亿维，但典型情况只有几百个非零数据。这使得大规模的有效训练成为可能，因为每个训练例子仅仅被考虑一次。
为准确表达，建立一些符号。g_t \in R^d 中ｔ代表当前训练例子，第ｉ个进去的向量就是g_{t,i},用g_{1:t}=\sum_{s=1}^{t}g_s.
如果用逻辑回归model我们的问题，使用下面线上框架：在第ｔ轮，用x_t \in R^d预测,给定参数w_t,我们预测p_t=\sigma(w_t,x_t),其中\sigma(a)=\frac{1}{(1+exp(-a))}是sigmoid函数。接下去观测点击y_t \in {1,0}，以及必然产生的,
\[Logloss:l_t(w_t)=-y_t log p_t-(1-y_t)log(1-p_t),\]
p表示负例子的最大似然估计，下面这个梯度是为达到优化目标而设定的 :
\[\Delta l_t(w)=(\sigma(w\cdot x_t)-y_t)x_t=(p_t-y_t)x_t\]
线上梯度下降方法OGD在处理这类问题时很有效，能利用有限计算资源做出很准预估。但是，现实中需要考虑的另一个问题是最终模型的大小；因为模型是被稀疏存储的，w中的非零系数数量决定内存使用多少。
可是，OGD处理稀疏模型的能力并不是很强。实际上，只要简单地给L_1加上。更复杂的方法比如FOBOS和缩短了的梯度在处理稀疏上是很成功的[11.20]。正规化对偶平均算法比FOBOS具有更高的精准度[32].可是我们发现梯度下降类的方法在我们的系统中比RDA具有更高的精准度[24]。所以现在问题就是我们能同时获得RDA提供的稀疏性和OGD提供的精准度吗？答案是可以的，那就是使用Follow The(Proximally)Regularized Leader算法，或者叫FTRL-Proximal.没有正则化，这个算法和标准的线上梯度下降算法并无二致，但因为它用了一种更懒的模型系数ｗ表示，L_1正则化被实施的更有效了。
FTRL_Proximal 算法用了一种使用理论分析更方便的方式构架[24]，我们重点关注现实实施过程。
给定一串g_t \in R^d，OGD实施如下更新：
\[w_{t+1}=w_t-\eta_t g_t,\eta_t 代表非增的学习效率，比如\eta_t=\frac{1}{\sqrt{t}}\]
而FTRL_Proximal算法使用如下迭代方式：
\[w_{t+1}=\underset{w}{\arg \min}\left(g_{1:t}\cdot w+\frac{1}{2}\sum_{s=1}^{t}\sigma_s{\|w-w_s\|}_{2}^{2}+\lambda_1{\|w\|}_1\right)\]
将\sigma_s定义成学习效率控制：\sigma_{1:t}=\frac{1}{\eta_t}.表面上看过去这些很不同，实际上当我们令\labda_1=0,它们能产生一个完全一样的系数向量。可是，FTRL_Proximal是用\lambda_1>0实现包括稀疏性在内的一系列出色工作的(见实验结果)。
快速一看，有人可能会觉得FTRL_Proximal比梯度下降要难以实施，或者需要存储所有之前的参数。实际上每个系数只需要一个数，因为我们可以重写w \in R^d上的算法：
\[\left(g_{1:t}-\sum_{s=1}^{t}\right)\cdot w+\frac{1}{\eta_t}{\|w\|}_{2}^{2}+\lambda_1{\|w\|}_1+(const)\]
因此如果我们存储了z_{t-1}=g_{1:t-1}-\sum_{s=1}^{t-1}\sigma_s w_s,然后以下面方式迭代：
\[z_t=z_{t-1}+g_t+(\frac{1}{\eta_t}-\frac{1}{\eta_{t-1}})w_t\]
然后根据per-coordinate bases解w_{t+1}:
\[w_{t+1,i}=\begin{cases}0,&if|z_{t,i}|\leq \lambda_1\\-\eta_t(z_{t,i}-\sgn(z_{t,i})\lambda_1)&otherwise\end{cases}\]
因此，FTRL_Proximal把z存在内存里，而OGD存w。算法１用了这种方法，但也加了一个per-coordinate 学习效率控制，同时支持L_2\对lambda_2的正则化。另一种方式就是我们存储\eta_t z_t而不是直接存z_t；于是，当\lambda_1=0时，我们正好存储了正常的梯度下降系数。注意到当\eta_t是常数而\lambda_1=0，容易看出来同在线梯度下降方法的等价性，正好是梯度下降最关键的点：
\[w_{t+1}=-\eta z_t=-\eta \sum_{s=1}^{t}g_s\]
实验结果：
在小型原型版本上的早期实验，McMahan[24]让我们知道有L_1正则化的FTRL_Proximal显著的要比RDA和FOBOS好，如果按
照规格准确性综合权衡的方法去看，三个之前的结果放在表1的1,2,3行中。
在许多情况下，一些启发性的工作会和principled方法一样好，但这个例子不是这样的。我们的Straw-man算法,OGD计数只是简单地maintains它们看见的特征的数量，知道计数超过临界值ｋ，没正则化L的在线梯度下降像正常那样运行。为了测试FTRL_Proximal同我们一般在很大数据集上跑的启发性算法。我们把k调到同FTRL_Proximal具有相同的准确度；使用一个更大的ｋ导致了更差的AUCLoss，结果在表1的４行中。
总的来讲，实验结果表明FTRL_Proximal以相同或者更高的预测准确性显著提升了Sparsity.
3.1Per-coordinate学习效率
标准的梯度下降理论使用全局学习效率控制\eta_t=\frac{1}{\sqrt{t}},对所有的coordinates都是这样的[34]。一个简单的思想实验会告诉我们它并不是那么理想：假设我们用逻辑回归估计10个硬币的P(heads|coin_i)，在第ｔ轮只抛一个硬币ｉ，我们就能看到一个特征向量ｘ\in R^10,有x_i=1,x_j=0,如果i \neq j .于是我们需要解决10个逻辑回归问题，把它看成一个问题。
我们可以跑10个独立的梯度下降，那么对与每一个问题ｉ就有学习效率\eta_{t,i}=\frac{1}{n_{t,i}},n_{t,i}表示到目前为止硬币i被抛出的次数，如果硬币i比硬币j抛出的频繁，那么硬币i的下降学习的效率就更快，反应出我们拥有更多的数据；学习效率回保持比j高，因为我们现在的估计不是很确定，我们需要更快地对新数据做出反应。
另一方面，如果我们把它看成一个学习问题，把标准的学习效率控制运用到所有坐标上，那么，我们降低了硬币i的学习效率即便它没有被抛出。这显然不是最理想的。实际上,Streeter和McMahan给出一族用标准算法回相对的比跑单独的copy渐进地要差的问题，因此至少对与一些特定的问题来讲，per-coordinate的算法能提供一种substantial的优势。
我们前面用g_{s,i}表示梯度g_s＝\Delata l_s(w_s)的第i个坐标。于是一个更详尽地分析展示了per-coordinate 学习效率：
\[\eta_{t,i}=\frac{\alpha}{\beta+\sqrt{\sum_{s=1}^{t}g_{s,i}^{2}}}\]
在特定情形下是接近最优的。事实上，我们使用的这个学习效率中\alpha和\beta被选出来yield progressive validation下面的good
performance.我们也试过了在计数器n_{t,i}上的幂指数。\alpha的最优值依据特征和数据集改变，\beta=1通常就足够好，这简单地保证了早起的学习效率不会太高。
正如前面强调的，这个算法需要记录梯度和以及针对每个特征的梯度的开方的和。4.5部分展示了另一种节约内存的方式，在哪里梯度开方的和被摊分到许多模型之上。
另一个相对简单的对per-coordinate学习效率的分析在[29].只在Google小范围的数据集上做了测试，这个工作直接使用Zinkevich.
一种对FTRL_Proximal更理论化的处理出现在[26].Duchi [10]分析了RDA和镜像decent版本，也给了很多实验结果。
实验结果：我们通过测试两个相同的模型对per-coordinate学习效率做出评估，一个使用了全局的学习效率，另一个用了per-coordinate的学习效率。基本的参数\alpha是针对不同的模型调的，我们在一个有代表性的数据集上跑，然后使用AucLoss作为我们的评估metric.结果显示使用per-coordinate学习效率想比较全局学习baseline减少AucLoss11.2%.把这个知识作为背景，在我们的设定中１％的AucLoss算是少的。
4.大规模环境下节约内存
正如前面所述，我们利用L_1正则化在预测时节省内存。本节讲述在训练过程中如何节约内存。
4.1包含的概率特征
在许多高维数据领域，绝大部分的特征是极其罕见的。实际上，我们的一些模型，一半的特征在整个包含几十亿训练数据集的特征中只使用一个。
对这么罕见的特征做统计是很浪费的，不幸地是我们事先不知道那些特征是稀有的。预处理数据来移掉稀有在线上环境设定下是一个问题：额外的读写数据相当昂贵，如果一些特征被丢掉了(也就是出现少于k次)，那也就不能用那些特征去估计预处理这些数据的话费了。
一类通过实施L_1正则化来处理稀疏数据的方法不需要追踪任何一个系数是零的特征的统计信息。这使得要被移除的没什么信息量的特征被当做训练来进行。然而，我们发现这种方式导致不可接受的在准确性方面的损失，相比较在训练中追踪大部分特征以及稀疏性只作为serving的方法。另一种常见的解决方案是，hashing with collisions也没什么用处。
我们用的另外一些方法是概率特征Inclusion,这之中的新特征只要它们一出现就以概率的方式被包含在模型中。这样既预处理了数据又适应线上学习的环境设定。
两种具体做法：
Possion Inclusion:如果我们遇到一个没在我们模型中的特征，我们以概率ｐ将这个特征加入我们的模型；如果一个特征已经在我们的模型中，在接下去的观测中我们更新它的系数值以及利用OGD的各种统计。一个特征被看见到加入到模型中需要的时间服从均值是1/p的几何分布。
Bloom Filter Inclusion:我们使用一个数Bloom filter rolling集合来检测出一个特征在一个训练中的前面n次使用。一旦一个特征使用超过n次，我们把它加进过滤器，然后使用它来训练接下去的观测。需要注意到这种方式也是概率的，因为一个计数Bloom过滤器是有可能false Positives的，也就是说我们有时候会包含进去一个出现少于n的特征。
实验结果：这些方法的效果显示在表2中，两种方法都很有用，但是Bloom filter approach会在RAM存储节省和预测准确性之间做出更好的折中。[em09]
4.2使用更少的bit输入数值
OGD的简单实施用32位或64位浮点来存储系数值。浮点encoding通常很受欢迎因为他们可以大范围变动，而且有不同粒度的精度大小，但是同事，对我们正则化的逻辑回归模型的矩阵系数而言这个被证明是太厉害了。几乎所有系数值在(-2,2).分析结果显示fine-grained的精度也是不需要的[14],这使得我们探索使用一个fixed-point来encoding取代浮点。
在q2.13 encoding,小数点前面两位，后面13位数,前面加字母q,总共16位.
精度下降回导致一个问题在OGD设定中会出现roundoff错误，这需要很多小步骤的累计。实际上我们已经在32位机中观察到明显的roundoff问题。然二能用一个简单的随机rounding策略用很少的花费纠正这个问题。关键在于通过很明确的整数化，我们能够保证离散化的错误期望为零。
特别的，如果我们把参数存进ｗ，令：
\[ w_{i,rounded}=2^{-13} \lfloor 2^13 w_i +R \rfloor\\]
其中，Ｒ是一个随机的0,1之间的偏离,g_{i,rounded}以q2.13的格式存储，范围[-4,4)之外的值被减掉。对于FTRL_Proximal算法，我们以这种方式存储\eta_t\z_t,和w_t具有类似的量级。
实验结果：实际上我们用q2.13代替64位浮点存储没有观察到measuable loss,而且节省了75%RAM系数存储空间.
4.3训练许多相似的模型
在测试为特征进行高维参数设定时，通常评估一种或集中轻量级的变量很有用.这种通常的用例允许了更有效的训练策略。这个领域很有趣的一项工作[19],使用了一个固定模型作为先验同时允许变化被评估为残留的错误。这种方法很便宜，但是不容易评估特征的移动和一些学习设定。
我们主要的方法依赖于一些数据每个坐标如何通过模型变量共享，当其他数据只是针对每一个模型变量而不能被共享。如果我们吧每个模型变量存在哈希表上不能共享，我们可以用一个单个的表存储所有变量把存贮逐渐的花费摊销掉。在4.5我们讲展示出per-model学习效率计数器n_i如何被所有变量共享的统计所取代，这也节省了内存。
任何一个没有特定特征的变量都会占用一小部分空间存储特征0,我们把那些特征的学习效率定义为零。因为我们只是在一起训练很相似的模型，所以从不representing关键字和计数的每个模型要比不常见的特征丢失大得多。
当几个模型在一起训练的时候，摊分的花费被所有per-coordinate基础数据降下来了，基础数据包括per-coordinate学习效率需要的计数，额外新加的模型需要被存储的参数变量。这里的节省不仅仅是内存，还有网络带宽(值通过网络传输，只读一次训练数据)，CPU(只有一个哈希表查找，特征只从训练数据生成一次),硬盘。这种bundled结构显著的增加了我们训练的容量。
4.4单值结构
有时候希望能够评估很大数据集的模型变量和这和仅仅同简单的加上减去一群特征很不相同。这里，我们使用了更加压缩的的数据结构它同时失真和特定的，但是实际上给出了很厉害的有用的结果。这个单值的结构存储在每个坐标只有一个系数被所有的模型变量分享，而不是分别为单个的模型存储系数值。Bit-field就是用来追踪模型变量包括给定的坐标。注意到这和[19]的基本方法本质上很相似，而且还允许对特征添加和移除的的评估。RAM的增加要比4.3提到的变量缓慢。
学习过程如下。对于给定的OGD更新，每个模型变量计算出它的预估以及用包括的子集坐标带上为每个参数存储的单值算出Loss.对每一个特征i,每个模型利用i计算出新的期望的值域。结果值会被平均然后作为一个单值存放然后在下一步被所有变量
分享。
我们通过比较两大族用单值结构训练出的模型变量和以4.3开头其中有相同变量的模型来评估这个启发性算法。结果显示几乎相对一样的表现，但是单值结构节省了一个数量级的RAM.
4.5通过计数计算学习效率
如同3.1中显示的，我们需要为每个特征存储梯度的和以及梯度开方的和。梯度计算的正确十分重要，但是在估计学习效率时需要粗略地估计值。
假设所有事件包含的特征有一样的概率。(一般，这是个很恐怖的接近，不过对于这个目的已足够。)假设这个模型拥有了准确的概率值，用Ｎ表示负的事件，Ｐ表示正的事件，令p=P/(N+P),如果我们用逻辑回归，那么正事件的梯度就是p-1,负事件的梯度是p,学习效率等式中需要的梯度之和是：
\[\sum g_{t,i}^{2}=\sum_{positive}{}(1-p_t)^2+\sum_{negtive}{}{p_t}^2\simeq P{\left(1-\frac{P}{N+P}\right)}^2+N{\left(\frac{P}{N+P}\right)}^2\]
这种近似使得我们能够只追踪N,P,记忆对得分的分配\sum g_{t,i}^{2},根据经验地用这种近似计算出来的学习效率和用完整的和计算出来的一样好。利用4.3中的框架所有的村春小号降低了因为所有的变化模型有一样的计数，所以Ｎ和Ｐ的存储就分配出去了。计数可以被存储在可变长度的encoding,同时大量的特征不需要很多bit.
4.6二次抽样训练数据
典型的CTR远比50%低，也就是正例相对稀疏。因此，简单的统计计算意味着点击相对的要比CTR预测更重要。我们可以利用这个来显著的减少训练数据量而对准确性没有什么影响。我们创建二次抽样数据来包含我们需要的样本：
任何一个查询至少有一个广告被点击。
ｒ是(0,1]上的分数，没有广告被点击。
查询level的抽样是很需要的，因为计算很多特征需要一般的在查询语句上的处理。当然，简单在子样本上面训练数据回导致很强的预测先验。这个问题会很容易通过加一个权重被强调：
\[w_t=\begin{cases}1 &event\, t \,is\, in\, a\, clicked\, query\\\frac{1}{r}&event \,t\, is\, in\, a\, query\, with\, no\, clicks\end{cases}\]
因为我们控制了抽样的分布，我们就没有必要估计权重在一般样本选择[7]重要性权重简单的将每个等式上的按照比例放大了。考虑到一个随机选择的事件ｔ的期望的分布，在没抽样的数据做目标函数子抽样。令s_t是事件被抽样的概率，定义s_t=\frac{1}{w_t}.于是就能得到l_t(w_t)是个常量。
京公网安备 11010802022788号
