Ad Click Prediction: a View from the Trenches

Introduction & Brief System Overview

CTR预估是这样一个问题:给定一个查询\(q\) 和根据广告商选择的关键词来匹配查询\(q\) 相关的候选广告\(a\) ,也就是计算概率 \[ P(\text{click}|q,a) \] 通常系统中所用到的特征会涉及方面面,包括查询本身、广告的文本、与广告相关的各种信息等等,同时特征也会非常稀疏,往往只会有少数是非零的。

Online learning and sparsity

因为特征的维数往往非常大,所以广义的线性模型更适合这种情况,就像对率回归。为了描述该问题我们做如下表述:\(g_t\in\mathbb{R}^d\) 表明当前第\(t\) 个训练实例,\(g_{t,i}\) 表示其中第\(i\) 项特征的值,同时有\(g_{1:t}=\sum^t_{s=1}g_s\) ,对率回归模型可以表述为预测\(p_t=\sigma(w_t \cdot x_t)\) ,其中\(\sigma(a)=1/(1+\exp(-a))\) ,通过优化对数损失 \[ \ell_t(w_t)=-y_t\log p_t-(1-y_t)\log(1-p_t) \] 其梯度为 \[ \triangledown\ell_t(w)=(\sigma(w\cdot x_t)-y_t)x_t=(p_t-y_t)x_t \] 在线梯度下降(OGD)在这种问题上非常高效,用最少的计算资源,得到较高准确度的结果。但是,在现实中另一个不得不考虑的就是数据的稀疏性,随着模型越来越庞大,存储参数所需要的空间也变得十分庞大,所以让参数稀疏易储存十分重要。OGD在这方面就不是非常有效。单纯加一个\(L_1\) 正则项并不会产生足够好的稀疏参数。更为复杂的方法,如FOBOSRDA在引入稀疏性方面就非常有效。但是,RDA的参数稀疏性好,OGD准确性好,各有优点与缺点,FTRL-Proximal 就在稀疏性和准确性上都做得很好,通常OGD的迭代式为 \[ w_{t+1}=w_t-\eta_t g_t \] 其中\(\eta\) 为非负的学习率,而FTRL-Proximal算法做如下的迭代更新 \[ w_{t+1}=\underset{w}{\operatorname{\arg\min}} (g_{1:t}\cdot w+\frac{1}{2}\sum^t_{s=1}\sigma_s||w-w_s||^2_2+\lambda_1||w||_1) \] 其中\(\sigma_s\) 代表学习率,使\(\sigma_{1:t}=\frac{1}{\eta_t}\) ,根据上式,我们知道在迭代的时候,会需要\(w\) 在每次迭代的系数,这会耗费很大的存储空间,所以我们可以只最小化 \[ (g_{1:t}-\sum^t_{s=1}\sigma_sw_s)\cdot w+\frac{1}{\eta_t}||w||^2_2+\lambda_1||w||_1+\text{const} \] 这样,如果我们只存储\(z_{t-1}=g_{1:t-1}-\sum^{t-1}_{s=1}\sigma_sw_s\) ,并且使\(z_t=z_{t-1}+g_t+(\frac{1}{\eta_t}-\frac{1}{\eta_{t-1}})w_t\) ,可以得 \[ 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算法步骤。

1

SAVING MEMORY AT MASSIVE SCALE

因为数据特征的维度非常大,同时也十分稀疏,对于数据特征的选择就十分重要,通常我们只需要取出现频率比较大的特征作为计算,但读取并筛选特征这一行为本身就是非常昂贵的。

处理这种问题的一个角度是通过\(L_1\) 正则化来实现稀疏性,这样做就不用统计这个特征为零的概率了,这样做可以使包含较少信息的特征在训练中被去除掉,但是这么做的同时,也会带来一定准确度的损失。另一个角度是采用概率特征包含(probabilistic feature inclusion),新的特征第一次出现的时候以一定概率加入模型中,这种方法既能用于预处理数据,也可以用在在线学习中。这里提供两种实现方法:

  • Poisson Inclusion 泊松包含,当我们得到一个不在模型中的特征时,我们以概率\(p\) 接收这个特征,一旦这个特征被添加在模型中,在其余观测样本中我们更新它的系数;
  • Bloom Filter Inclusion,在训练中,记录一定样本中该特征出现的概率,如果超过一定阈值,则加入该特征。

OGD使用32位或者64位浮点数来存储参数,这样可以提高精度,但是,这对于需要参数稀疏的我们并不适合。几乎所有的参数都在\((-2,+2)\) 的取件中,所以我们选择一种修正的\(q2.13\) 的编码方式来代替浮点数。在\(q2.13\) 编码中,我们用2bits存储整数部分,其余的13bits存储小数部分,1bits存储符号,16bits就可以存储一个值,在进行零均值处理之后,在损失很少的精度情况下,可以节约大部分的存储空间。

对于迭代过程,计算梯度也会需要很大的计算资源,所以对梯度的计算也作近似 \[ \sum g_{t,i}^2=\sum_{\text{positive events}}(1-p_t)^2+\sum_{\text{negative events}}p_t^2 \]

\[ \sum g_{t,i}^2\approx P(1-\frac{P}{N+P})^2+N(\frac{P}{N+P})^2=\frac{PN}{N+P} \]

其中\(P\)\(N\) 都可以通过统计得到并不需要计算。

典型的CTR的概率会远远低于50%,所以在面临样本不均衡时我们要做一些处理,常见的是对负样本进行次采样(Subsampling)。

Summary

论文的剩下部分也对模型验证和改进等等做了一些介绍,感觉不是特别有意思所以就只扫了一眼。本文对CTR进行了一个大体的描述,一篇还可以的综述类文章。