广告在互联网公司业务中至关重要，而其中点击率(click-through-rate，CTR)预测在一定程度上能影响公司的收入，因此，如何依赖机器学习技术设计良好的在线广告系统有着很强的商业价值^[1]。CTR预估在互联网广告公司中是最经典的问题之一，在推荐系统和金融领域也有着比较广泛的作用^[2-3]。实际上，这类CTR预测问题可看作分类或者回归问题来解决，常见的是针对用户和广告特征信息预测CTR，在CTR预估中，最常用的模型则是逻辑回归(logistic regression，LR)^[4]。

对于LR模型，在目标函数可导的优化问题中，梯度下降法(gradient descent，GD)和拟Newton法(quasi-Newton methods)是常用的求解LR的方法。但是GD对初始点较敏感，无法得到全局最优解，拟Newton法利用最小值点一阶导数为0的特点，但在存储和计算Hession矩阵上存在不足。因此，许多改进的优化方法被应用来训练LR模型，主要的改进算法有随机梯度下降法(stochastic gradient descent，SGD)^[5]、L-BFGS (limited-memory BFGS)^[6]、Trust-Region^[7]、共轭梯度法^[8]等。这类算法整体上受限于训练数据的规模，无法有效处理数据流，进行在线训练。

在线学习算法中，稀疏性对于高维特征向量以及大数据集特别重要。为了得到稀疏的特征权重，Langford等^[9]提出截断梯度法(truncated gradient，TG)，先设定一个阈值，当参数的某维度上系数小于这个阈值时将其设置为0(简单截断)，这种方法运用简单但训练准确度低。Duchi等^[10]提出的前向后向切断(forward-backward splitting，FOBOS)可以看作截断梯度法的一种特殊形式，它将每一个数据的迭代过程分解成一个经验损失梯度下降迭代和一个优化问题。TG和FOBOS都是建立在SGD的基础之上的，属于梯度下降类型的方法，这类型方法的精度比较高，并且也都能在稀疏性上得到提升。正则对偶平均(regularized dual averaging，RDA)法^[11]，能够更好地在精度和稀疏性之间做平衡，避免了由于某些维度训练不足导致截断的问题。FTRL由McMahan^[12-13]提出并实现，它可以看作RDA和FOBOS的混合模型，但在L₁范数或者其他非平滑的正则项下，FTRL比前两者更加有效，FTRL综合了RDA和FOBOS两种算法的优点，是实现稀疏性的较好在线算法。

正则化是机器学习领域的重要技术，它的主要目的是防止模型过拟合，目前比较常用的有L₁正则和L₂正则。一般来说，当两个特征相关时，L₂正则会同时保留2个特征并对权重系数收缩^[14]，但L₁正则只会选择一个参数，而让另外一个参数的系数为0^[15]，因此L₂正则在减少预测错误上表现更好。然而对于大规模机器学习训练，L₁正则更容易得到稀疏解，这是因为绝大多数特征的权重都是0，可减少计算时的内存占用，并提高预测的速度。本文采用的是混合正则化的形式，包含L₂₁范数。无论从理论上惩罚函数的性质，还是实际的变量选择效果，这种正则化形式更能保证预测精度并提高运算效率。

针对上述问题，本文在对传统LR模型的相关原理和参数优化算法介绍的基础上，抽离出用户特征和广告特征，并将用户与广告之间的关联添加到Sigmoid函数中得到新的关联特征模型。与以往求解方法不同的是，该方法改进在线最优化算法FTRL提高参数计算效率，采用混合正则化项防止训练过拟合。在实验部分，本文从准确性、效率、参数敏感性和可靠性等方面验证提出的CTR预测方法的有效性。

1 基于FTRL算法对传统LR模型的优化 1.1 特征关联模型的提出

对于一个给定的特征向量X=(x₁, x₂, …, x_n)^T，传统的LR建模采用的函数：

$ \begin{array}{*{20}{c}} {\phi \left( x \right) = {w_0} + {w_1}{x_1} + {w_2}{x_2} + \cdots {w_n}{x_n} = }\\ {{w_0} + \sum\limits_{i = 1}^n {{w_i}{x_i}} .} \end{array} $

(1)

从方程可见各个特征分量x_i和x_j之间是独立的，没有考虑特征分量之间的相互关系。

由于不同特征之间的关联性，本文引入w_ij来表示x_i和x_j之间的关系，在LR模型的基础上增加了交叉项：

$ \phi \left( x \right) = {w_0} + \sum\limits_{i = 1}^n {{w_i}{x_i}} + \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{w_{ij}}{x_i}{x_j}} } . $

(2)

在一般的广告计算中，对点击率预估有重要作用的主要是用户特征和广告特征，分别记为x_u(u=1, 2, …, l)和x_a(a=1, 2, …, s)，可直接利用x_uMx_a来修正Sigmoid函数，其中M为一个矩阵，代表用户和广告之间的关联信息，大小取决于用户和广告特征的基数。通常，特征基数都很大，因此矩阵就会变得非常大和稀疏。这里，可借鉴矩阵分解的形式，将矩阵M进行分解，分解成S和V，从而避免了稀疏性和矩阵的复杂计算。用向量表示为：

$ \phi \left( X \right) = \mathit{\boldsymbol{W}}X + \left( {\mathit{\boldsymbol{x}}_u^{\rm{T}}\mathit{\boldsymbol{S}}} \right){\left( {\mathit{\boldsymbol{x}}_a^{\rm{T}}\mathit{\boldsymbol{V}}} \right)^{\rm{T}}}. $

(3)

其中：S是l×k的矩阵，V是s×k的矩阵，k∈N+是一个超参数用来定义隐藏因子的数量。通常，k值越大模型预测精度越高，但是计算复杂度和计算内存消耗也越大^[16]。

由于(x_u^TS)(x_a^TV)^T=x_u^TSVx_a^T=x_u^T(SV^T)x_a，因此(x_u^TS)(x_a^TV)^T能有效地表示用户和广告的关联特征信息，矩阵S和V中参数的数目是(l+s)k，对于CTR中成千上万的参数，s和l的个数通常才几十个，使得算法计算复杂度和编码时间大大降低。另外，该模型有着比传统的LR模型更强的非线性拟合能力。

1.2 模型的求解

给定一个数据集{(x_i, y_i)|i=(1, 2, …, N)}, 其中x_i表示输入特征，y_i∈{1, 0}表示展示广告被点击或者没被点击，CTR的预测问题等价于求解方程h(x)，它可以被用来预测一个用户点击某一展示广告的概率。h(x)=P(y=1|x; W, S, V)=σ(ø(W, S, V; x)), 其中σ(ø(x))是Sigmoid函数，模型的参数W、S、V通过最小化正则损失方程得到。

$ \mathop {\min }\limits_{\mathit{\boldsymbol{W}},\mathit{\boldsymbol{S}},\mathit{\boldsymbol{V}}} \sum\limits_{i = 1}^n {\xi \left( {\mathit{\boldsymbol{W}},\mathit{\boldsymbol{S}},\mathit{\boldsymbol{V}};{\mathit{\boldsymbol{x}}_i},{y_i}} \right)} + \lambda \mathit{\Omega }\left( {\mathit{\boldsymbol{W}},\mathit{\boldsymbol{S}},\mathit{\boldsymbol{V}}} \right), $

(4)

$ \begin{array}{*{20}{c}} {\xi \left( {{\mathit{\boldsymbol{x}}_i},{y_i}} \right) = - \frac{1}{m}\sum\limits_{i = 1}^m {{y_i}\log h\left( {{\mathit{\boldsymbol{x}}_i}} \right)} + }\\ {\left( {1 - {y_i}} \right)\log \left( {1 - h\left( {{\mathit{\boldsymbol{x}}_i}} \right)} \right).} \end{array} $

(5)

由于(x_u^TS)(x_a^TV)^T使得目标函数非凸，本文采用交换的学习方法来学习参数，每次通过固定一个参数来优化另一个参数，经过几次迭代后，即满足收敛条件。对于每个实例(x, y)，该实例产生的梯度可以推导如下：

$ \frac{{\partial \xi \left( {\mathit{\boldsymbol{x}},y} \right)}}{{\partial {w_i}}} = \left( {h\left( \mathit{\boldsymbol{x}} \right) - y} \right){x_i}, $

(6)

$ \frac{{\partial \xi \left( {\mathit{\boldsymbol{x}},y} \right)}}{{\partial {S_{ij}}}} = {x_{ui}}\left( {h\left( \mathit{\boldsymbol{x}} \right) - y} \right)x_a^{\rm{T}}{V_{ * j}}, $

(7)

$ \frac{{\partial \xi \left( {\mathit{\boldsymbol{x}},y} \right)}}{{\partial {V_{ij}}}} = {x_{ai}}\left( {h\left( \mathit{\boldsymbol{x}} \right) - y} \right)x_u^{\rm{T}}{S_{ * j}}. $

(8)

Ω(W, S, V)为正则项，本文采用混合正则化项的形式，本文对参数W采用L₂正则约束，对S和V参数采用L₂₁范数正则约束，具体形式如下：

$ \mathit{\Omega }\left( {\mathit{\boldsymbol{W}},\mathit{\boldsymbol{S}},\mathit{\boldsymbol{V}}} \right) = {\left\| \mathit{\boldsymbol{W}} \right\|_2} + {\left\| \mathit{\boldsymbol{S}} \right\|_{21}} + {\left\| \mathit{\boldsymbol{V}} \right\|_{21}}, $

(9)

$ {\left\| \mathit{\boldsymbol{S}} \right\|_{21}} = \sum\limits_{i = 1}^l {\sqrt {\sum\limits_{j = 1}^k {S_{ij}^2} } } = \sum\limits_{i = 1}^l {{{\left\| {{\mathit{\boldsymbol{S}}_{i * }}} \right\|}_2}} , $

(10)

$ {\left\| \mathit{\boldsymbol{V}} \right\|_{21}} = \sum\limits_{i = 1}^l {\sqrt {\sum\limits_{j = 1}^k {V_{ij}^2} } } = \sum\limits_{i = 1}^l {{{\left\| {{\mathit{\boldsymbol{V}}_{i * }}} \right\|}_2}} . $

(11)

为了求解偏导数，需要将正则化项进行变化：

$ \begin{array}{*{20}{c}} {\mathit{\Omega }\left( {\mathit{\boldsymbol{W}},\mathit{\boldsymbol{S}},\mathit{\boldsymbol{V}}} \right) = \sum\limits_{i = 1}^{k = 1} {W_i^2} + \sum\limits_{i = 1}^l {\sqrt {\sum\limits_{j = 1}^k {S_{ij}^2} } } + }\\ {\sum\limits_{i = 1}^l {\sqrt {\sum\limits_{j = 1}^k {V_{ij}^2} } } \approx \sum\limits_{i = 1}^{k = 1} {W_i^2} + \sum\limits_{i = 1}^l {\sqrt {\sum\limits_{j = 1}^k {S_{ij}^2 + \varepsilon } } } + }\\ {\sum\limits_{i = 1}^l {\sqrt {\sum\limits_{j = 1}^k {V_{ij}^2 + \varepsilon } } } .} \end{array} $

(12)

其中ε是一个非常小的正数使得正则项可导。

则Ω(W, S, V)的梯度为：

$ \frac{{\partial \mathit{\Omega }\left( {\mathit{\boldsymbol{W}},\mathit{\boldsymbol{S}},\mathit{\boldsymbol{V}}} \right)}}{{\partial {W_i}}} = \sum\limits_{i = 1}^K {2{W_i}} , $

(13)

$ \frac{{\partial \mathit{\Omega }\left( {\mathit{\boldsymbol{W}},\mathit{\boldsymbol{S}},\mathit{\boldsymbol{V}}} \right)}}{{\partial {S_{ij}}}} = \frac{{{S_{ij}}}}{{\sqrt {\sum\limits_{j = 1}^K {S_{ij}^2 + \varepsilon } } }}, $

(14)

$ \frac{{\partial \mathit{\Omega }\left( {\mathit{\boldsymbol{W}},\mathit{\boldsymbol{S}},\mathit{\boldsymbol{V}}} \right)}}{{\partial {V_{ij}}}} = \frac{{{V_{ij}}}}{{\sqrt {\sum\limits_{j = 1}^K {V_{ij}^2 + \varepsilon } } }}. $

(15)

用梯度下降法，则可得到:

$ {g_\tau }\left( \cdot \right) = \sum\limits_{i = 1}^N {\frac{{\partial \xi \left( {{\mathit{\boldsymbol{x}}_i},{y_i}} \right)}}{{\partial t}}} + \lambda \frac{{\partial \mathit{\Omega }\left( {\mathit{\boldsymbol{W}},\mathit{\boldsymbol{S}},\mathit{\boldsymbol{V}}} \right)}}{{\partial t}}. $

(16)

其中$\frac{{\partial \xi \left( {{\mathit{\boldsymbol{x}}_i}, {y_i}} \right)}}{{\partial t}} $根据式(6)—(8)求得，$ \frac{{\partial \mathit{\Omega }\left( {\mathit{\boldsymbol{W}}, \mathit{\boldsymbol{S}}, \mathit{\boldsymbol{V}}} \right)}}{{\partial t}}$根据式(13)—(15)求得。对于复杂度的分析，采用拟Newton法求解，求解梯度的时间复杂度为O{[(l+s)k+p]N}，O{[(l+s)k+p]²}为矩阵相乘需要的时间，总计算时间为O{[(l+s)k+p]·Nu+[(l+s)k+p]²u}，u为迭代次数。

以上CTR预测算法适合数据的批量处理，即对所有训练数据迭代求全局导数，每次更新都需要对已经训练过的样本重新训练一遍。它虽然能求得模型的参数解，但是无法在线学习，因此本文引入在线最优化算法。

1.3 基于改进FTRL在线算法的求解

在节1.2中，本文对模型的更新计算依然采取全局梯度计算权重，这种求解参数的方法无法满足在线学习。本节采用改进的FTRL方法优化参数，为了稀疏性和准确率，采用混合正则化项的形式，L₂正则项的引入仅相当于对最优化过程多了一个约束，使得结果求解结果更加“平滑”。其特征权重的更新公式为：

$ \begin{array}{*{20}{c}} {{w_{t + 1}} = \mathop {\arg \min }\limits_w \left\{ {{g_{1;t}}w + \frac{1}{2}\sum\limits_{s = 1}^t {{\sigma _{1:t}}\left\| {w - {w_s}} \right\|_2^2} + } \right.}\\ {\left. {{\lambda _1}{{\left\| w \right\|}_1} + \frac{1}{2}{\lambda _2}\left\| w \right\|_2^2} \right\},} \end{array} $

(17)

其中：g_s表示的是梯度，σ_s是学习率的一种更新策略，如，$ {\sigma _{1:t}} = \frac{1}{{{\eta _t}}}, {\eta _{t, i}} = \frac{\alpha }{{\beta + \sqrt {\sum\limits_{s = 1}^t {g_{s, i}^2} } }}$.

将式(16)进行改写，将最后一项展开，等价于求下面这样一个最优化问题：

$ \begin{array}{*{20}{c}} {{w_{t + 1}} = \mathop {\arg \min }\limits_w \left\{ {\left( {{g_{1;t}}w - \frac{1}{2}\sum\limits_{s = 1}^t {{\sigma _s}{w_s}} } \right) \cdot w + } \right.}\\ {{\lambda _1}{{\left\| w \right\|}_1} + \frac{1}{2}\left( {{\lambda _2} + \sum\limits_{s = 1}^t {{\sigma _s}} } \right)\left\| w \right\|_2^2 + }\\ {\left. {\frac{1}{2}\sum\limits_{s = 1}^t {{\sigma _s}\left\| {{w_s}} \right\|_2^2} } \right\}.} \end{array} $

(18)

由于$\frac{1}{2}\sum\limits_{s = 1}^t {{\sigma _s}} \left\| {{w_s}} \right\|_2^2 $对于w来说是一个常数，并且令：

$ {Z^{\left( t \right)}} = {g_{1;t}}w - \sum\limits_{s = 1}^t {{\sigma _s}{w_s}} . $

(19)

式(17)等价于:

$ \begin{array}{*{20}{c}} {{w_{t + 1}} = \mathop {\arg \min }\limits_w \left\{ {{Z_t}w + {\lambda _1}{{\left\| w \right\|}_1} + } \right.}\\ {\left. {\frac{1}{2}\left( {{\lambda _2} + \sum\limits_{s = 1}^t {{\sigma _s}} } \right)\left\| w \right\|_2^2} \right\}.} \end{array} $

(20)

针对特征权重的各个维度将其拆解成N个独立的标量最小化问题：

$ \mathop {\arg \min }\limits_w \left\{ {{z_{t,i}}{w_i} + {\lambda _1}{{\left\| w \right\|}_1} + \frac{1}{2}\left( {{\lambda _2} + \sum\limits_{s = 1}^t {{\sigma _s}} } \right)w_i^2} \right\}. $

(21)

可以得到：

$ {w_{t + 1,i}} = \left\{ \begin{array}{l} 0,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left| {\overline {{z_{t,i}}} } \right| < {\lambda _1};\\ {\left( {{\lambda _2} + \sum\limits_{s = 1}^t {{\sigma ^s}} } \right)^{ - 1}}\left( {{z_{t,i}} - {\lambda _1}{\rm{sgn}}\left( {{z_{t,i}}} \right)} \right),\;\;\;\;其他. \end{array} \right. $

(22)

从式(21)可以看出，L₂正则化对稀疏性无影响。

算法的求解过程如图 1所示。

2 实验结果与分析 2.1 实验数据和设计

本文采用广告公司Avazu的数据集。训练集抽取的第21天到第30天日志信息，给出了是否点击、用户ID等属性以及广告展位等信息，测试集是第31天的除了点击与否的其他信息。由于原始数据量比较大，本文采取随机抽样方式抽取部分数据分析。对于给定的数据，本文对正负样本进行统计，发现正负比例约为1:4，抽样后比例也为1:4。

本文程序由Python和Java编写而成，运行环境为Linux OS，内存大小4 GB，CPU频率2.3 GHz。

2.2 广告点击率预测的评估指标

由于样本中不同类别的样本数不平衡，传统的评估指标，如准确率不能恰当地反映分类器的性能。本文采用Log-loss作为评估指标，Log-loss值越低表示CTR预测的准确度越高，Log-loss的定义为：

$ \begin{array}{*{20}{c}} {{\rm{Log}} - {\rm{loss}} = -\frac{1}{N}\left( {\sum\limits_{{\rm{positive}}} {\log \left( {{p_{ij}}} \right)} } \right) + }\\ {\sum\limits_{{\rm{negative}}} {\log \left. {\left( {1 - {p_{ij}}} \right)} \right)} .} \end{array} $

(23)

其中: p_ij为用户对广告是否点击的模型预测点击率，N为预测总数。

2.3 广告点击率估计的结果分析

由于样本数据集数据量巨大，不同算法需要的计算时间不同，因此本文的实验采取抽样处理，抽样后的数据条数大约10万条。下面分别从不同方面对本文提出方法的性能进行分析。

2.3.1 精度和效率

对比几种模型的计算结果，如表 1所示，本文提出的方法具有最好的Log-loss，由于为了获取更好的准确度，本文方法加入了用户特征和广告特征的关联信息，必然损失一定的时间，但是这个计算时间仍然在可接受范围内。

2.3.2 参数的敏感性

本节讨论超参数k和正则化因子λ对算法性能的影响。实验结果如图 2所示，总体上k值越大，Log-loss越好，当k=40时，Log-loss最好，但随k值越大，参数增多，相应的学习速率也减慢。而对于正则化参数的因子λ，本文提出的模型对其不敏感，基本变化不大。

对于迭代次数对Log-loss的影响，如图 3所示，随着迭代次数的增加，模型的Log-loss会不断减少，但幅度越来越小。本文提出的算法在8次迭代后就收敛，而传统的方法通常需要迭代15次以上。

2.3.3 稳定性

在稳定性实验中，设置k=40，λ₁=0.1，λ₂=1，迭代次数取8次，采取的样本量分别是10万条，100万条和6 GB的数据量，实验结果如图 4所示，本文提出的模型计算得到的样本Log-loss差别不大，其中最好的是0.37。

3 结论

本文在对传统LR模型的相关原理和参数优化算法介绍的基础上，抽离出用户特征和广告特征，将其添加到Sigmoid函数中得到新的特征关联模型。本文采用改进的在线最优化算法提高参数计算效率，采用混合正则化项防止训练过拟合。本文的主要成果体现在4个方面：1)考虑了用户与广告的特征关联，且根据关联矩阵的稀疏性和大规模等特点将其分解，从而使得其比传统的LR模型有着更强的非线性拟合能力；2)该模型能自动消除无用的特征，使得在线预测更加迅速，尤其对于大规模稀疏性数据和特征；3)利用在线算法，能实时处理数据，效率高且避免了批量处理；4)对真实广告数据集的实验结果表明本文提出的模型和方法，与传统的模型和方法相比具有更好的预测精度、效率、参数敏感性和可靠性。