2013 google发表的paper：<Ad Click Prediction: a View from the Trenches>。来看一下核心部分：
一、系统总览
当一个用户做出一个搜索q时，会基于广告主投放的关键词（advertiser-chosen keywords）根据q匹配一个初始的候选ad集合。竞价机制接着会决定这些广告是否展示给该用户，以及以什么顺序展示给用户，以及广告商的广告被点击要付的费用。除了广告主投标（advertiser bids），竞拍的一个重要输入是，对于每个广告a，会有一个被点击的概率估计：$ P(click | q, a) $。
在我们的系统中所使用的特征，从多个源抽取，包括query、广告文本、多种与广告相关的元信息。数据会趋向于相当稀疏，对于每个样本通常只有一个很小的部分具有非零特征。
基于正则的LR等方法天然就可以处理该问题。对于每天可以做出数十亿次的预测，并可以在观察到新点击/非点击数据时快速更新模型。当然，该数据比例意味着训练数据集是很庞大的。数据的提供通过基于Photon系统的流式服务提供。
由于大规模学习已经在近些年研究得很好，在该paper中不再详细描述系统架构。我们注意到，训练方法可以具有与Downpour SGD方法（from google brain team）相似之处，不同之处是，我们训练了一个单层模型而非多层的深度模型。这允许我们处理更大数据集、更大模型，具有数十亿的参数。由于训练的模型可以被复制到多个数据中心进行serving，我们更广告在serving时上的稀疏化（sparsification），而非训练时。
二、在线学习和稀疏化
对于大规模学习，对于常用的线性模型（比如：LR）在线算法，具有许多优点。尽管特征向量x可能具有数十亿维，通常每个样本都只有数百个非零值。这使得在大数据集上通过从硬盘或网络的流式样本(streaming examples)可以有效进行训练，因为每个训练样本只需要被考虑一次。
为了精准地表述该算法，我们需要建立一些注解。$ g_t \in R^d $表示向量，其中t表示当前训练实例的索引；向量$g_t$中的第$i^{th}$个条目表示为$g_{t,i}$。我们也使用压缩过的求和：$g_{1:t}= \sum_{s=1}^{t} g_s $。
如果我们希望使用LR进行建模，我们可以使用下面的在线框架。在第t轮，我们通过特征向量$x_t \in R^d$来预测一个实例；给定模型参数$w_t$，我们预测$p_t=\sigma(w_t · x_t)$，其中$ \sigma(a)=1/(1+exp(-a)) $是sigmoid函数。接着我们观察到label $y_t \in {0,1} $，使用LogLoss：
\(l_t(w_t) = -y_t log p_t - (1-y_t) log(1-p_t)\) …(1)
$ y_t $的负log似然会给出概率p。$ \triangledown{l_t(w)}=(\sigma(w · x_t) - y_t) x_t = (p_t-y_t) x_t $，该梯度就是我们要优化的目标。
在线梯度下降（OGD：online gradient descent）对于这类问题很有效，只需要少量的计算资源就可以产生很好的预测精度。然而，实际上另一个关键考虑点是：最终模型的size；因为模型可以被稀疏存储，w中的非零参数是内存使用量的决定因子。
不幸的是，OGD在产生稀疏模型上并不特别有效。事实上，简单添加L1罚项的一个次梯度（subgradient）到loss的梯度中，将不会产生等于0的参数。更复杂的方法（比如：FOBOS）和截断梯度（truncated gradient）在引入稀疏化上是很成功的。对比于FOBOS算法，RDA（ Regularized Dual Averaging）算法会产生更好的准确率（accuracy）。然而，在我们的数据集上，比起RDA，我们已经观察到梯度下降的方法可以产生更好的准确率。问题是，我们是否可以同时满足稀疏化（由RDA产生）和准确率（OGD产生）？答案是：yes！使用RTRL-Proximal算法（Follow The (Proximally) Regularized Leader）。没有正则化，该算法会等同于标准的在线梯度下降法，但因为它使用了另一种模型参数w的延迟表示（lazy representation），L1正则可以被更有效地实现。
FTRL-Proximal算法之前主要在理论分析方面。这里，我们主要描述实际实现。给定一个梯度的序列$g_t \in R $，OGD执行更新：
\[w_{t+1}=w_t - \eta_{t} g_t\]其中$ \eta_t $是一个非增长(non-increasing)的学习率schedule，例如：$ \eta_t = \frac{1}{\sqrt{t}} $。FTRL-Proximal算法则使用下面的更新作为替代：
\[w_{t+1} = argmin_{w} ( g_{1:t} \cdot w + \frac{1}{2} \sum_{s=1}^{t} \sigma_{s} \| w - w_s \|_{2}^{2} + \lambda_{1} {\| w \|}_1 )\]其中我们定义了$ \sigma_{s} $表示learning-rate schedule，比如：$\sigma_{1:t}=\frac{1}{\eta_t}$。表面上，这些更新看起来很不同，但实际上，当我们采用$ \lambda_1=0 $，它们产生一个系数向量的相同序列。然而，FTRL-Proximal会使用$ \lambda_1 > 0$更新，在引入稀疏化上效果很好（详见试验结果）。
快速检查下，你可能认为FTRL-Proximal的更新比梯度下降更难，或者需要存储所有过去的参数。实际上，每个参数只有一个需要存储，因为我们可以重写更新作为argmin：
\[(g_{1:t}-\sum_{s=1}^{t} \sigma_s w_s) · 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 $，在第t轮的开始处，我们设置：$z_t = z_{t-1} + g_t + (\frac{1}{\eta_t} - \frac{1}{\eta_{t-1}})w_t$进行更新，以闭式(closed form)求解$w_{t+1}$：
\[w_{t+1,i} = \begin{cases} 0, & \text{if } |z_{t,i}|\leq \lambda_1 \\ -\eta_t(z_{t,i}-sgn(z_{t,i})\lambda_1, & \text{otherwise} \end{cases}\]这样，FTRL-Proximal会在内存中存储 $ z \in R^d $，其中OGD会存储$ w \in R^d $。算法1就采用该方法，但也会添加一个per-coordinate learning rate schedule，并支持在$lambda_2$的L2正则。另一种方法是，我们会存储 $-\eta_t z_t $，而非直接存储$z_t$；接着，当$ \lambda_1=0 $，我们会准确存储正常的梯度下降参数。注意，当$eta_t$是一个常数值$\eta$，$\lambda_1=0$，很容易看到，OGD的等价物，因为我们已经有$w_{t+1}=-\eta z_t = -\eta \sum_{s=1}^{t} g_s$，与梯度下降的角色相同。
试验结果。在我们数据集上小版本上的试验，在size-vs-accuracy权衡上，McMahan等展示了使用L1正则的FTRL-Proximal比RDA和FOBOS的效果有极大提升；这些之前的结果见表1: 行2和行3.
在许多样本上，一种简单的启发式也工作良好。我们的straw-man算法，OGD-Count，简单维持它看到某个特征的count数；直到count数传递一个阀值k，参数被固定在0上，但在count传入k后，OGD（不带L1正则）会和往常处理一致。为了测试FTRL-Proximal，我们在大数据集上运行。我们对k进行调参，来生成与FTRL-Proximal相同的准确率；使用更大的k来产生更差的AucLoss。结果如表1:第4行所示。
总体上，这些结果展示了FTRL-Proximal，它可以极大提升了稀疏性，同昌使用相同或更好的预测准确率。
Per-Coordinate Learning Rates
OGD的标准理论建议使用一个全局的learning-rate schedule $\eta_t = \frac{1}{\sqrt{t}}$，这对于所有坐标来说都通用。一个简单的试验展示了这种方式是不理想的：假设我们为10个硬币正估计 $Pr (heads | coin_i)$，使用LR。每个第t轮，只有一个硬币i会进行抛币试验，我们看到特征向量$x \in R^{10} $，其中$x_i = 1$，$x_j=0$，对于$ j \neq i$。 这样，我们求解10个独立的LR问题，并打包到单个问题中。
我们可以运行10个独立的OGD copy，其中对于问题i的算法实例，可以使用一个learning rate: $ \eta_{t,i} = \frac{1} {\sqrt{n_{t,i}}}$，其中 $n_{t,i}$是硬币i至今被抛的的次数号。如果硬币i比硬币j抛的次数更多，硬币i的learning rate将下降的更快，印证了在多数据集上得到的事实；对于硬币j，它的learning rate仍将很高，因为我们已经在我们当前的估计上具有更少的置信度，因此需要对新数据反应更快。
另一方面，如果我们将这种看成是单个learning-rate问题，标准的learning rate schedule为：$\eta_{t} = \frac{1}{\sqrt{t}}$被应用到所有坐标上：也就是说，我们会对硬币i的learning rate进行下降，即使它没有被翻转。这很明显不是最优的行为。事实上，Streeter和McMahan已经展示了一个熟悉的问题：其中标准算法的性能渐近地比运行独立copy的效果要更差。因而，对于这些问题，per-coordinate learning rates会提供一个实质上的优点。
回忆下，$g_{s,i}$是梯度$g_s=\nabla {l_s}{w_s} $第i个cordinate。per-coordinate rate的如下：
\[\eta_{t,i} = \frac{\alpha}{\beta + \sqrt{\sum_{s=1}^{t} g_{s,i}^2}}\]……(2)
在某种程度上是近似最优的。实际上我们会使用这样的learning rate：选择$\alpha$和$\beta$它们可以在progressive validation上生成好的效果（见5.1）。我们已经试验：使用counter $n_{t,i}$上的一个power，而非0.5. $\alpha$的最优值可以随着特征和数据集的不同而不同，$\beta=1$通常足够好；简单确保早期的learning rate不要太高。
正如前面所述，该算法需要我们跟踪梯度求和，以及每个feature的梯度平方和。第4.5节将描述一种可选的节约内存的方式，其中梯度平方和在多个模型上进行分摊（amortize）。
per-coordinate learning rate的一个相对简单的分析在paper[29]中，它在小的google数据集上试验结果很好；该工作直接使用Zinkevich的方法。对于FTRL-Proximal的一种更理论的解释在paper[26]中。Duchi等人分析了RDA以及mirror-descent版本，也给出了多种试验结果。
试验结果。通过测试两种相同的模型，我们对per-coordinate learning rate的影响进行评估：一个使用单一的global learning rate，另一个使用per-coordinate learning rates。基础参数$\alpha$对每个模型进行独立调参。我们在一个有代表性的数据集上运行，使用AucLoss作为我们的评估metric（见第5部分）。结果展示出，对比于global-learning rate的baseline，使用per-coordinate learning rate可以将AucLoss可以减小11.2%。
4.在大规模上节约内存
如上所述，我们使用L1正则来在预测时节约内存。在本节中，我们描述了额外的tricks来在训练期间节约内存。
4.1 概率特征包含（Probabilistic Feature Inclusion）
在许多领域具有高维数据，大多数特征是相当稀疏的。事实上，在我们的一些模型中，半数唯一特征（（unique features）在整个数十亿的样本训练集上只出现一次。
对于这些罕见的特征进行跟踪统计是很昂贵的，实际上它们可能从不会被用到。不幸的是，我们不知道哪个特征是罕见的。对数据进行预处理来移除罕见特征在online环境下是棘手的：一个额外的读数据和写数据是相当昂贵的，如果一些特征被丢弃掉（因为它们出现少于k次），它们不再可以尝试这样的模型：这些模型使用这些特征来估计预处理在accuracy方面的代价。
一种家族式方法，可以在训练时完成稀疏化，通过实现L1正则，它不需要跟踪特征统计，参数为0。这允许少量有益的特征可以在训练过程中被移除。然而，我们发现，对比起其它方法（比如FTRL-Proximal：在训练时会跟踪更多特征，在serving时会稀疏化），这种稀疏化会在accuracy上导致一个不可接受的loss。另一种常见的解决方案是，对碰撞进行hashing，但这不会结出有用的好处。
另一大类方法是：probalilistic feature inclusion，在该方法中，新特征会在它们第一次出现时，有概率的被包含在模型中。这会让数据预处理的完成更有效，但在online时被执行。
我们按该方法测试了两种方式：
- 泊松包含（Poisson Inclusion）。当我们遇到一个特征时（它不在我们的模型中），我们使用概率p将它添加到模型中。一旦一个特征被添加，后续的观察，我们照例更新它的参数值，和OGD所用到的相关统计量。特征在添加到模型之前被看到的次数，会服从一个几何分布：期望值为$\frac{1}{p}$
- 布隆过滤器包含（Bloom Filter Inclusion）。我们使用一个counting Bloom filters的集合，来检查一个特征在训练集中首先出现的n次。一旦特征出现超过n次（根据该filter），我们就将它添加到模型中，并使用它来在后续观察中进行训练。注意，该方法也是概率化的（probalilistic），因为一个counting bloom filter可以是false positives（但不会是false negatives）。也就是说，我们有时会包含一个特征：它们的出现次数少于n次。
试验结果：这些方法的效果见表2,两种方法效果都不错。在预测质量的loss以及RAM saving的tradeoffs上，但Bloom filter方法给出了更好的效果。
4.2 使用更少的Bits来编码值
OGD的Naive实现，使用32或64位浮点值（floating point）编码来存储参数值。浮点编码通常受欢迎，是因为它们更大的动态范围以及更细的precision；然而，对于我们的正则LR模型的参数，这被证明是过度伤害的。几乎所有的参数值的范围在(-2,+2)。分析之后表明，细粒度的precision是没有必要的，这推动着我们去探索fixed-point q2.13编码的使用，而非floating point。
在q2.13编码中，我们保留两位给binary decimal point的左部，十三位给binary decimal point的右部，一位留给符号，每个值共16位。
这个reduced precision，可能会在OGD环境下创建一个带有累积舍入偏差（accumulated roundoff error）的问题，它需要大量小步骤的累积。（事实上，我们已经看到严重的舍入问题，它使用32位floats，而非64位）。然而，一个简单随机的rounding策略可以纠正该问题，以一个小的添加的遗忘项的代价。关键点是，通过显式的rounding，我们可以确保离散化error具有零均值。
特别的，如果我们存储参数w，我们设置：
\[w_{i,rounded}=2^{13}[2^13 w_i + R]\]…(3)
其中，R是一个在[0,1]间的均匀分布的一个随机偏离。$g_{i,rounded}$接着存储在q2.13 fixed point格式中；在[-4,4)范围外的值会被裁减。对于FTRL-Proximal，我们可以以这种方式存储$\eta_t z_t$，它与$w_t$有相似的幅值。
试验结果。实际上，对比起使用q2.13 encoding（替代floating point值）的模型的结果，我们观察到没有可测量的loss损失。我们可以节约75%的RAM来存储参数。
4.3 训练多个相类似的模型
当对超参数或feature的变更进行测试时，评估多个小的变种是很有用的。这种常见的用例允许有效的训练策略。一个有意思的地方是paper[19]，它使用一个fiexed model作为先验，允许多个变种在残差（residual error）上进行评估。这种方法开销很小，但不容易对特征移除（feature removal）或可选的learning setting进行评估。
我们的主要方法依赖于该观察：每个coordinate依赖于一些数据，它们可以被有效地在模型变种间共享，而其它数据（比如：参数值自身）被指定给每个模型变种，不能被共享。如果我们在hash table中存储模型参数，我们可以对所有变种使用单个表，分摊存储key的开销（string或many-byte hash）。在下一节，我们展示了，每个模型的learning-rate counters $n_i$是如何被所有变种的统计共享替代的，它会减小存储。
任意变种不会有一个特定的feature，它会为该feature存储参数成0，浪费一点空间。（我们通过将这些特征的learning rate设置成0）。因为我们只与高度相似的模型一起训练，从这种表示(不表示该key)中获得的内存savings，以及每个模型的counts比不常见的特征的loss要更大的多。
当多个模型一起训练时，分摊的开销会压低，所有per-coordinate的元数据，比如per-coordinate learning rates所需要的counts，递加的额外模型的开销依赖于需要存储的额外参数值。该saves不仅仅是内存，还有网络带宽（值以相同的方式通过网络进行通信，但我们只读取一次训练数据），CPU（只有一个hash table lookup，而非多个，从训练数据中生成的特征只需一次，而非每个模型一次），磁盘空间。这个捆绑的架构会极大增加我们的训练容量。
4.4 单值架构
有时我们希望评估非常大的模型变种的集合，它们只会在少量特征组上进行增加和移除。这里，我们可以采用一种压缩数据结构，它是有损耗的（lossy），(adhoc)，但实例上会给出十分有用的结果。这种单值架构会为每个coordinate存储只有一个参数值，它们通过包含这些特征的模型变种进行共享，而非存储独立的参数值。一个位域（bit-field）可以被用于跟踪哪个模型变种包含了给定的coordinate。注意，这与paper [19]中的方法精神相类似，但也允许特征移除的评估。该RAM的开销增长得很慢，比起4.3节的方法。
学习过程如下：对于一个在OGD中的给定更新，每个模型变种会计算使用包含它在内在coordinates的子集的预测和loss，为每个参数抽取存储的单个值。对于每个特征i，每个模型会使用i为给定的参数计算一个新的期望值。产生的值被平均，存储成单个值，它将接着被下一步中所有变种所共享。
我们评估该启发法（heuristic），通过计算模型变种（它们使用单值架构进行训练，对比起相同的变种，它们由4.3节的方法进行训练）的大组来进行。展示的几科等同于跨变种的相关效果，但单值结构会保存RAM的幅度顺序（magnitude order）。
4.5 计算带Counts的learing rates
在3.1节所示，我们需要存储每个特征的梯度求和及梯度平方和。重要的一点是，梯度计算可以被纠正，但可以做出总近似值，以便计算learning rate。
假设包含了一个给定的特征的所有事件，都具有相同的概率。（总这，这是一个可怕的近似，但它可以行得通）。进一步假设模型已经准确学到了该概率。如果它们有N个负样本(negative events)，P个正样本（positive events），接着该概率为 p = P/(N+P)。如果我们使用LR，正样本的梯度为p-1,负样本的梯度为p，等式2对应的learning rate所需要的梯度求和如下：
\[\sum{g_{t,i}^2} = \sum_{positive events} (1-p_t)^2 + \sum_{negtive events} p_t^2 \approx P(1-\frac{P}{N+P})^2 + N ( \frac{P}{N+P}^2 = \frac{PN}{N+P}\]这种残酷的近似允许我们跟踪N和P的counts，无需存储$ \sum{g_{t,i}^2}$。经验上，learning rates的计算和该近似，可以有效工作，正如我们使用完整的求和（full sum）计算的learning rates。使用第4.3节的框架，总的存储开销会更低，因为所有的变种模型具有相同的counts，因而对于N和P的存储开销会被分摊。该counts会使用变长的位编码进行存储，大多数features不需要多个bits。
4.6 对训练数据子抽样(subsampling)
通常，CTR会低于50%，这意味着正样本（点击数）会相当稀少。这样，简单的统计计算表明：点击（clicks）在CTR预估学习中相对更有价值。我们可以利用这一点来极大减少训练数据的size，在accuracy上具有最少的影响。我们创建了子采样过的训练数据，包含在我们的样本中：
- 对于这个训练数据，任意query至少有一个广告被点击
- $r \in (0,1] $比例的queries，其中没有广告被点击
在query级别进行抽样是令人满意的，因为计算多个features需要在query阶段进行公共处理。当然，在该子抽样数据上直接进行原始训练(naively training)，将导致极大的预测偏差。这个问题可以通过分配一个重要性权重（importance weight）$w_t$给每个样本来轻易地解决：
\[w_t = \begin{cases} 1, & \text{event t is in a clicked query } \\ \frac{1}{r}, & \text{event t is in a query with no clicks} \end{cases}\]因为我们控制着抽样的分布，我们不需要在通用抽样选择中估计权重w。重要性权重可以简单地按比例放大在每个样本上的loss，如等式(1)，因而也可以放大梯度。为了看到它具有特意的影响，考虑到在未抽样数据中的一个随机选中的样本t对子抽样目标函数的的期望贡献。$s_t$为它表示样本t被抽样到（不管是1还是r）的概率，由定义：$s_t=\frac{1}{w_t}$。因而，我们具有：
\[E[l_t(w_t)] = s_t w_t l_t(w_t) + (1-s_t) 0 = s_t \frac{1}{s_t} l_t(w_t) = l_t(w_t)\]期望的线性(Linearity)，预示着在子抽样训练数据上的期望加权目标函数，等于在原始数据集上的目标函数。试验验证了：即使对非点击的query进行子抽样，也会在accuracy上有一个非常轻度的影响，预测的效果不会受指定值r的影响。
5.评估模型效果
模型质量的评估的完成开销很小，通过使用日志历史数据即可。（线上的模型评估很重要，但更昂贵；见[30]）
因为不同的metrics对应着模型更改的不同方式，我们发现，对于评估模型变化很有用。我们计算了metrics，比如AucLoss（也就是说1 - AUC，其中AUC是在ROC曲线下的标准区域面积），LogLoss（见等式(1)），以及SquaredError。出于一致性，我们也设计了我们的metrics，越小值越好。
5.1 Progressive Validation
我们总体上使用progressive validation（有时也称为online loss），而非cross-validation，或者在held-out dataset上进行评估。因为计算一个梯度需要计算一个预测，我们可以很方便地将这些预测(predictions)进行流式化，以便后续的分析，按小时聚集。我们也在数据的多个子切片计算这些metrics，比如：通过国家，查询主题，布局进行划分。
online loss对于在serving queries的accuracy来说，是一个好的代理，因为它可以衡量只在大多数最近数据上的效果，
