FTRL介绍

Reading time ~1 minute

2013 google发表的paper:。来看一下核心部分:

一、系统总览

当一个用户做出一个搜索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:

…(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执行更新:

其中$ \eta_t $是一个非增长(non-increasing)的学习率schedule,例如:$ \eta_t = \frac{1}{\sqrt{t}} $。FTRL-Proximal算法则使用下面的更新作为替代:

其中我们定义了$ \sigma_{s} $表示learning-rate schedule,比如:$\sigma_{1:t}=\frac{1}{\eta_t}$。表面上,这些更新看起来很不同,但实际上,当我们采用$ \lambda_1=0 $,它们产生一个系数向量的相同序列。然而,FTRL-Proximal会使用$ \lambda_1 > 0$更新,在引入稀疏化上效果很好(详见试验结果)。

快速检查下,你可能认为FTRL-Proximal的更新比梯度下降更难,或者需要存储所有过去的参数。实际上,每个参数只有一个需要存储,因为我们可以重写更新作为argmin:

这里,如果我们已经存储了 $ 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}$:

这样,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的如下:

……(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,我们设置:

…(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所需要的梯度求和如下:

这种残酷的近似允许我们跟踪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。重要性权重可以简单地按比例放大在每个样本上的loss,如等式(1),因而也可以放大梯度。为了看到它具有特意的影响,考虑到在未抽样数据中的一个随机选中的样本t对子抽样目标函数的的期望贡献。$s_t$为它表示样本t被抽样到(不管是1还是r)的概率,由定义:$s_t=\frac{1}{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来说,是一个好的代理,因为它可以衡量只在大多数最近数据上的效果,

一、介绍

参考

gcForest介绍

在各种类型的DNN漫天飘的时代,周老师等提出了gcForest算法。以下是论文核心部分的介绍:# 3. gcForest算法gcForest算法引入了cascade forest结构,以及multi-grained scanning。## 3.1 cascade fores...… Continue reading

Deep&Cross Network介绍

Published on January 04, 2018

DeepFM介绍

Published on November 12, 2017