Question

广告点击率预测的目的是广告排序，但不能套用搜索里的排序问题：点击率预测不能像搜索那样只要求结果排序的正确性，因为点击率需要乘以点击单价才得到最后的排序。另外，在 DSP中，需要尽可能准确地预测 eCPM用于出价。因此，作为各种广告系统中通用的一项技术，点击率预测更适合被建模成回归问题而不是排序问题。

关于点击率预测的方法，很自然的可以想到基于统计的估计：

其中h_i 是表示第i次展示被点击的次数，一般情形下为0或者1。但是，如果某种（u，c）组合的情形下，广告a没有被展示过或点击量很稀疏，就无法通过历史数据来统计点击率了。容易想到的解决方案是将要展示的广告a和一个展示过的广告a⁰类似，则可以预估a的点击率与a⁰接近。如果将（a，u.c）投影到特征空间比较，则演化为即将介绍的点击率模型。

13.5.1 点击率预测模型

我们把点击事件 h看成一个二元取值的随机变量，那么其取值为真（h=1）的概率就是点击率。因此，点击事件的分布可以写成以点击率 µ为参数的二项分布（binomial distribution）：

而点击率预测模型的作用是在（a，u，c）组合与点击的概率µ之间建立函数关系，这可以表示成对µ（a，u，c）=p（h=1|a，u，c）的概率建模问题，可以很自然地想到的基础模型是逻辑回归（Logistic Regression，LR）：

其中x表示（a，u，c）组合上的特征矢量，即前面介绍过的受众定向的输出及其派生的其他特征；w为各特征的加权系数，也就是此模型需要优化的参数；（2h−1）w^>x这一线性函数的输出经过逻辑S型Sigmoid函数σ（z）={1+e^−z}⁻¹映射到（0，1）区间内，其中（2h−1）是为了将 {0，1} 的点击变量变换到集合 {−1，1} 上。从方法上看，LR 是利用线性函数来解决非线性目标，也属于广义线性模型^[36]。可以推导得到，逻辑回归正是当目标值的分布服从伯努利分布时广义线性模型的一个特例，映射函数为logit（p）=log。因此，有关广义线性模型的性质和结论也适用于LR模型。

实践中，由于LR模型使用的特征较多，并且有相当多的特征在训练集中出现的次数并不多，为了避免过拟合，还需要在最大似然估计时加入正则化项。如果采用L₂-norm^[52]，则此优化问题可以表达成：

13.5.2 优化算法

对于LR模型，我们通常采用最大似然估计来求解加权系数w。LR模型的最大似然解有很多计算方法，而我们在实践中重点关注其收敛速度以及在面对海量数据时分布式计算的便捷性。比如，如将其视为最大熵模型的特例，那么最大熵模型的典型优化方法——改进的迭代缩放（Improved Iterative Scaling，IIS）算法^[7]也可以用于 LR的更新。这种方法虽然物理意义明确、计算简单，却有着收敛速度慢的致命弱点，因此并不适用。

由于 LR模型不存在闭式解，其优化方法必然需要迭代进行。典型的 MapReduce分布式计算框架下，由于磁盘被用作迭代之间的数据交换手段，迭代的次数直接决定着训练算法的效率。因此，在每个迭代中尽可能完成更复杂深入的运算、减少迭代次数是此处的关键。这样的思路适用于LR模型训练，也适用于许多MapReduce下的需要迭代求解的机器学习算法。

1.L-BFGS

在目标函数可导的一般优化问题中，拟牛顿法是一族最常用的方法，因此也可以直接应用于LR问题的求解。不过，从10.2.4节中的BFGS的代码可以看出，它需要存储赫斯矩阵的逆矩阵的近似B_k，因此空间复杂度为O（D²）。在点击率预测这样的变量维数很高的优化问题中，赫斯矩阵的尺寸过大，根本无法在内存中存放。

解决这一问题的思路是仅仅保留最近几次更新的一些状态矢量，然后利用这些状态矢量和当前的梯度，直接计算出更新方向，这种方法称为有限内存 BFGS（Limited-memory BFGS，L-BFGS）。L-BFGS 的核心思想是根据前几次的函数值变化和梯度变化近似地拟合赫斯矩阵的逆。先来回顾一下，在 BFGS 的迭代过程中，赫斯矩阵逆的更新公式可以表示为：

其中的定义请参见10.2.4节。如果对此迭代公式展开并做截断，只保留前m次的状态量，则B_k+1 可近似地表示为：

其中是设定的赫斯逆的初值。为降低计算复杂度，实际中比较有

效的选择是令为一个对角阵：I。在这样的表示下，B_k可以在每次迭代中高效地计算出来的。参考文献[54]中进行的实验研究表明，这类有限内存的二阶方法是可行而且有效的。下面附上L-BFGS迭代求解的代码片段。

容易验证，上面每一步迭代的空间和时间复杂度都降到了m×D，如果选择一个较小的m，就可以认为其复杂度接近线性，这在大多数较高维度特征空间上建模的应用中就可以达到实用水平了。注意，在迭代的前m−1步，L-BFGS和BFGS是没有区别的。

2.Trust-Region 法

除了 L-BFGS，Trust-Region法也被证明对求解 LR问题很有效，而且往往可以更快地收敛^[52]。不过，在点击率预测的问题中，同样因为模型的维数可能很高，直接用公式10.14来解Trust-Region的子问题仍然是不现实的。

对于这样高维的问题，可以采用共轭梯度法（conjugate gradient method）^[62]来求解Trust-Region的子问题。当目标函数为二次正定函数时，共轭梯度法可以在 n（特征维数）次迭代后达到收敛，避免了存储和计算赫斯矩阵。与无约束优化中的共轭梯度法略有不同的是，这里需要满足的约束条件，考虑到子算法中位移量是递增的^[52]，当发现某次的位移跳出置信球之外时，将其沿着原来的搜索方向退回到置信球边界即可。

具体来说，在共轭梯度法的每次迭代中的，主要的操作是H 矩阵与向量s的乘积，由于X=（x₁，···，x_N ）^>是稀疏的，不需要直接求赫斯矩阵也可以得到该乘积，对于公式13.9的目标函数，计算公式如下：

其中D=diag{D_ii}，D_ii=σ（（2h_i−1）w^>x_i）{1−σ（（2h_i−1）w^>x_i）}。

采用上述的共轭梯度法求解Trust-Region子问题的代码片段如下。

3.ADMM 计算框架

从上节中Trust-Region法与L-BFGS法的比较中可以看到，随着每轮迭代的代价增加，迭代次数也随之降低了，因此有可能会带来收敛速度的提升。是否存在一种普适性的思路，使得我们可以对一般的迭代求解问题减少其迭代次数呢？学术界对这个问题也进行了深入的研究，产生了一些颇具启发意义的方法。这里我们介绍一种称为交替方向乘子法（Alternative Directional Method of Multipliers，ADMM）^[14]的计算框架。

从方法论上说，要降低迭代数目，必然要求在一个迭代内完成更复杂的计算。要了解ADMM，需要先介绍一下扩展拉格朗日方法。10.2.1节介绍了带约束优化的拉格朗日法，如果只考虑等式约束为一个线形约束（Ax=b）的形式，可以构造如下的扩展拉格朗日：

容易验证，这一形式可以得到与标准拉格朗日一样的解。引入一个二阶惩罚项，往往会使得问题求解的过程更好地收敛。根据参考文献[14]中的介绍，这一问题可以用Dual Acsent方法求解。而问题得以分布式求解的关键是当目标函数可以分解成下面的形式时，就可以发现存在有效的分解迭代求解方案：

对应的迭代求解方案是一个x，z，y 依次迭代更新的过程：

为了表达上的整洁，我们将y换成了归一化的形式s=（1/ρ）y。在典型的利用ADMM分布式求解的问题中，上面的第一个公式用于各部分数据的局部参数更新，第二个公式用于将各部分得到的局部优化参数综合成全局的参数；而第三个公式中对偶变量的更新则是使得整个过程稳定和高效率的关键。

按照公式13.14的结构，可以将LR的优化问题13.8改写成下式：

这里的 l={1，···，L} 表示数据集分裂后的各个部分，w^（l）对应于某一部分数据上得到的LR 参数（对应于公式 13.16 中的 x），而 v 为整体决策后的参数（对应于公式 13.16 中的z）。D^（l）表示由第l块数据样本的特征拼成的矩阵。问题的约束条件是表明求解收敛时各部分的参数应该等于整体参数，这是非常自然需要满足的。目标函数中的r（ˆw）代表的是求解过程的对参数的某种正则化项，比如公式13.9中的L₂-norm项。于是，可以得到用ADMM方法迭代求解此问题的方法：

我们来分析一下这一更新过程。

（1）首先，在每个数据分块上，分别执行第一个公式中的对应更新，得到该数据分块上更新后的参数，这一步是可以分布式进行的，而且各个数据块之间不需要通信。

（2）然后，根据各部分更新得到的参数，执行第二个公式得到综合以后的整体参数v。

（3）根据第三个公式更新对偶变量 s，并将更新后的 v 和 s分发至各个数据块的处理单元。

这一过程可以非常自然地用MapReduce方式来实现，其中步骤1对应着各个Mapper，而步骤2和步骤3对应着一个唯一的Reducer。

我们可以将此过程与 L-BFGS 的迭代的更新过程比较一下：在 L-BFGS 当中，每个Mapper，即分布式的部分计算过程非常简单，只需要在每个样本上对参数求导数，再将导数累加即可；而在 ADMM 方法中，Mapper 计算的过程变得复杂了很多，由简单的导数计算变成了一个LR的求解问题，也就是说Mapper的计算本身就需要迭代才可以完成。但正由于在每个Mapper中作了更多的计算工作，使得整体求解过程的收敛更快。同时需要注意的是，实际上在每个Mapper中复杂的更新过程并不会带来计算代价的显著增加，这是由于每个Mapper所需要处理的数据量有限，因此可以放在内存中，于是在分布式计算中最主要的开销即 I/O 开销并没有增加。可以认为 ADMM 的方法是用对局部内存的更多访问换得了全局MapReduce过程的迭代次数减少，从而提高了效率。该方法的具体MapReduce编码实现并不困难，读者可以自行实现。

虽然是以LR模型为例来介绍ADMM方法的应用，实际上这种方法可以应用于许多常见的机器学习模型，而且大都在 MapReduce的计算框架下可以达到减少总迭代次数，从而提高效率的目的。

4.Spark 上的模型优化

大多数机器学习问题往往需要进行迭代求解，而Hadoop上MapReduce的编程范式约束了每次迭代需要由一个MapReduce的Hadoop Job来完成。如图10-3所示，Map读入训练数据和模型，并在分块数据集上计算统计量；Reduce聚合统计量并更新模型。由于 Map将训练数据从磁盘读入时产生大量I/O，所以在Hadoop平台上进行一次迭代的代价非常昂贵。单轮迭代时间无法优化，想降低模型训练的时间只能减少模型训练的迭代数，这就产生了以上所说的工业界常用的模型训练思路。

（1）降低模型训练次数，通过特征侧的方法来捕捉信号的快速变化。

（2）增量求解，降低模型收敛所需的迭代轮数。

（3）精心设计最优化算法如ADMM^[14]，降低模型收敛所需的迭代轮数等。

如果能降低每轮迭代的开销，模型训练的总时间也能得到大幅的优化，于是便出现了Spark这样的平台。Spark是将数据集缓存在分布式内存中的计算平台，如果数据集的规模能够控制在内存中，那么即使仍然采用 MapReduce范式求解，由于每轮迭代不需要通过磁盘 I/O 读取数据，从而大幅降低了单轮迭代时间。应该说，Spark 的出现使得像点击率预测这种迭代求解的模型有了更好的计算平台，也逐渐在这些中等数据规模的应用上有替代MapReduce的趋势。

Spark最方便的编程语言是Scala，下面给出LR模型训练在Spark平台下的参考Scala代码。

5.基于 MPI 的模型优化

MPI（Message Passing Interface） 是基于消息传递函数库的标准规范，MPICH2 是 MPI编程规范的常用实现，允许各节点的进程之间在任何时刻互相通信^[79]。对分布式机器学习来说，MPI平台的核心在于提供了Allreduce/Broadcast范式，Allreduce范式可以实现大部分批处理迭代的机器学习算法，同时避免了MapReduce编程范式下每次迭代之间磁盘读写数据的开销。在 MPI 编程方式下，机器学习程序可以在每个节点的内存中保持模型，每轮迭代中各个节点计算好需要的统计量后，各个节点通过Allreduce通信得到全局统计量，之后进行下一轮迭代，迭代之间不需要资源的重新分配。

在Spark的最新版本中，Allreduce的Spark实现treeAggregate已经在逐渐成熟。这里为了开拓思路，以在 YARN 上实现了 Allreduce 范式并可容错的开源库 Rabit 为例来介绍MPI 程序的开发思路。事实上，YARN 的出现就是鼓励大家基于不同的算法抽象开发自己的计算框架。MapReduce、Storm和Spark等计算框架均可运行在YARN之上。

尽管对于机器学习来说 Allreduce 范式是一个更好的选择，但是 MPICH2 没有提供容错的功能，一旦集群中一个节点宕机后，整个程序必须从头开始计算。Rabit为了解决容错的问题，只实现MPI的一个包含Allreduce的子集，容错难度降低了很多。另外，大多数公司数据存储都依赖于Hadoop，在MPI集群和Hadoop之间调度数据成了高效处理数据的障碍。而 Rabit兼容 YARN平台，可以直接读取 HDFS上的数据，解决了存储的问题。下面给出基于Rabit的LR代码片段，可以看到，相对于MapReduce来说，分布式的MPI代码可以很容易从单机代码上迁移。

13.5.3 点击率模型的校正

点击率预测问题有一个数据上的挑战，就是正例和负例样本严重不均衡，特别是在展示广告点击率只有千分之几的情况下。在很多建模方法中，这样严重的不均衡会带来模型估计上的问题，我们仍然以LR模型为例，讨论一下模型存在偏差的原因以及相应的校正方法。

点击率模型可能存在偏差的原因如图13-5所示。假设分别用两个高斯分布来描述h=0和h=1情形下的特征分布。熟悉统计的读者都知道，高斯分布方差的最大似然估计是有偏的（为了得到方差的无偏估计，需要将样本数目减去 1来计算方差），而这一偏差的方向是对方差有所低估，并且样本数目越少，低估越严重。由于 h=1时的数据量远远小于 h=0时的数据量，对前者的方差低估就会更严重，对应图13-5 所示，前者的分布（右侧的高斯分布）会变得更窄一些。加入用这两个最大似然估计的高斯分布来决定 h=0 和 h=1 两个类的边界点，就会出现比实际边界点向右偏移的情况。这也就意味着更多的样本被分到了h=0这个类中，或者说意味着点击率将会被系统性地低估一些。这里的解释虽然只是示意性的，却与LR模型中点击率估计有偏的原因基本一致。

图13-5 正负例样本不均衡时点击率模型存在偏差的原因示意

所幸消除这一点击率估计的偏差并不十分困难，实际上对此偏差的系统性分析可以上升到广义线性模型的层次来研究。在LR模型情况下，有关这一系统偏差的量化计算和校正方法可以参见参考文献[47]中的详细介绍。

13.5.4 点击率模型的特征

上一节主要讨论的是点击率预测模型侧的问题，这一节我们来看特征侧的问题。从受众定向得到的所有t（a，u，c）以及这些特征的运算，可以组合出大量的特征供模型选择，这是大多数机器学习问题共同的方法。这样的特征生成方法是点击率特征的基础方法，不过在广告这样的问题中也遇到一些挑战：一是组合特征数量可能巨大，使得模型的参数数目也非常大多，工程上参数更新和在线计算都需要比较高效的设计；二是模型动态性的本质要求参数快速更新，而在多台广告投放机之间协同进行在线学习并非易事。

点击率预测问题的主要挑战在于如何使模型能捕捉高度动态的市场信号，以达到更准确预测的目的。这一挑战可以用在线的模型学习算法，或者用快速更新的动态特征来解决，从方法论上说，这两种思路是对偶的，但我们将重点放在第二种思路，因为其工程扩展上更方便一些。

1.静态特征

为什么广告展示的决策可以提取出大量的特征呢？这是因为在（a，u，c）三个维度上，都存在着人为指定或机器生成的多种标签，这些标签有的相互独立，也有的存在一定的层级关系。比如以a上的标签为例，我们介绍过，在广告运营当中，广告会被组织成广告主、广告计划、广告组、广告创意这几个层次。在预测的过程中，这样的层级结构对于更稳健地估计某个广告，特别是新广告的点击率有非常大的帮助。如图12-2所示，将t（a）、t（u）、t（c）以及t（a，u）等各种标签任取一个或两个，都可以都造出一个点击率模型的特征，例如下面的一些例子：

{cookie（u）=*};{creative（a）=*};{gender（u）=*};

{gender（u）=*&&topic（a）=*};{location（c）=*&&advertiser（a）=*};

{category（a）=category（a）=*}

这些例子中的前三个是某个单个标签的取值生成的，其对应的特征总量等于这些标签的取值实例总量；中间的两个，是将上下文或用户的某个标签与广告的某个标签组合生成的，其对应的特征总量等于这两侧标签的取值可能性总量的乘积；最后一个，是常用的特征，它表示的是广告和用户的某个标签相匹配。显然，由于组合特征的存在，可选的特征总量巨大，对应的模型维度也非常高。直接生成所有可能的单维度特征和组合特征，选取出现频次在一定阈值以上的，将其作为LR模型的特征集合。这样的特征，我们称为静态特征，这是广告点击率模型特征生成的基本方法。显然，静态特征都是取值为0或1的特征。

2.动态特征

在机器学习问题中，有一项很重要的方法论，即某项模型侧的技术，一般都可以找到特征侧的对偶方案。那么如何设计特征方案达到与模型快速演进类似的效果呢？当然就是让特征变成快速演进的。如何才能让特征“动”起来呢？办法也很简单：当某个组合特征被触发时，我们不再用1，而是采用这个组合历史上一段时期的点击率作为其特征取值。这样一来，即使是同一个 t（a，u，c），在不同的时间点，其所对应的特征取值也是不同的，这样的特征就是动态特征。

可以这样理解采用历史点击率作为动态特征：我们最终预测的是某个特定（a，u，c）上的点击率，而某个组合特征t（a，u，c）上的点击率可以认为是关于最终目标的一个弱决策器。通过对这些对应特征组合的弱决策器的融合，可以更容易地预测该（a，u，c）上的点击率。这样的方案有个最大的好处，那就是这些弱决策本身只需要简单的数据统计就可以得到，而不需要复杂的训练过程。因此，通过这些简单的弱决策器来捕捉模型的动态部分，整体的融合模型就可以不必那么快速地更新了。

使用动态特征的另一个好处是可以大大减少模型的参数数目：对于 {geo（c）=北京 &&category（a）=电商}和 {geo（c）=北京 && category（a）=日化}这两个特征组合的具体实例而言，如果采用静态特征方案，需要对这两个实例分配不同的特征号；而采用动态特征方案时，由于它们等号前的部分都相同，因此可以在模型中共享同一个特征参数，而通过不同实例的不同特征取值来分辨它们。这样一来，整体模型的参数个数就由各种维度组合总的实例数目降到了维度组合的种类数目，其离线估计和在线计算都会大为简化。

3.位置偏差与 CoEC

使用动态特征在实际操作中还会碰到一些困难，特别是当广告主数量不充分的时候。假设某广告网络有两个广告位，一个是某网站首页首屏，另一个是某网站内容页最下端。很显然，如果用点击率作为直接的反馈，前几天更多地投在第一个广告位的广告会表现出更好的效果，而这主要是由于位置带来的偏差。

除了广告位位置，还会有其他一些非定向因素对点击率有比较大的影响，主要的有广告位尺寸、广告位类型（如门户首页、频道首页、内容页、客户端）、创意类型（如图片、Flash、富媒体）、操作系统、浏览器、日期和时间等。所有这些因素，都与广告决策没有关系，但是对点击率的影响要远远超过定向技术带来的影响。因此，在这些因素上占据优势的广告，其点击率会被严重高估，如果直接用点击率作为反馈，也会造成强者愈强的马太效应。

如何去除位置等因素的影响呢？如果我们有财力和人力，可以采用眼球跟踪的设备来评估用户对页面上广告位的关注程度，在后续的统计中据此做归一化。对于一些极关键的页面，如搜索广告结果页，这样做是值得和可行的。但对于大量展示广告的广告位来说，这样做显然不切实际。工程上一种合理的办法是将某广告位相当长一段时期内的平均点击数作为其关注程度的近似评估，我们把这一指标称为期望点击（expected click）。

期望点击要求评估的是在广告质量完全随机的情况下，广告位或其他属性对应的平均点击率。要严格达到此目的，需要采用随机出广告的策略进行小流量测试，而这也只能用于搜索广告等因素简单且非常重要的页面。在多个因素共同作用或广告环境比较复杂的情况下，可以采用从数据中近似地学习出期望点击的方法。该方法概念上很简单，只用那些偏差因素作为特征，训练一个点击率模型，这个模型称为偏差模型（bias model）。这里的偏差因素指的是那些与广告决策无关的特征，这些特征一般来说与广告 a 无关。偏差模型可以概念性地表示为

偏差模型的形式和训练方法都可以与前面介绍的整体点击率模型一致。需要注意的是，偏差模型需要用比一般点击率模型更长时间的数据来训练，这样做的目的是希望消除某段时期广告质量带来的影响。

得到了偏差模型以后，可以定义下面的归一化的点击率指标：

这一指标是点击与期望点击的比值，因此称为CoEC（Click on Expected Click）。由于在分母上考虑了位置以及其他因素的偏差对点击率的影响，这一指标可以更准确地表征某部分流量上广告投放的实际点击率水平，也比较适用于点击反馈这样的动态特征。

采用动态特征和偏差模型的工程方案，点击率预测模型训练的流程分三步完成：首先，用较长一段时间的训练数据，只提取偏差特征并训练偏差模型；然后，利用得到的偏差模型计算所需维度组合上的CoEC作为动态特征；最后，用所有非偏差的动态特征训练整体点击率模型，其中用偏差模型的输出作为点击率的先验。利用 CoEC 特征的点击率模型训练流程如图13-6所示。

图13-6 利用CoEC特征的点击率模型训练流程

4.常见的偏差特征

前面说到，除了位置，在线广告中还有一些重要的偏差特征是建模时应该考虑的。

（1）广告位位置。位置的影响在搜索广告和展示广告环境下有一定的区别。对于搜索而言，页面布局简单，位置相对稳定，相应地统计也比较充分，因此可以将位置视为离散的变量，分别计算各个位置的EC。而对于展示广告，特别是在广告网络环境下的展示广告而言，位置的可能性非常多，因此不可能对每种不同的位置都作为独立的变量来考虑。比较合理的方法是找出重要影响因素，比如广告位中心相对于页面左上角的坐标，用这样的连续变量作为特征来训练偏差模型。

（2）广告位尺寸。尺寸与上面说的位置因素很类似：在创意尺寸选择比较少的情况下，可以作为离散变量来处理；而在尺寸选择很多的情况下，也可以用长宽等连续变量来代替。对于搜索广告，由于各创意尺寸一致，这一因素的影响不存在。

（3）广告投放延迟。广告完成决策逻辑，并将最终结果返回给用户的整体时间长短对点击率有着非常大的影响。如果在前端将广告请求发生的时间和最终展示时间都记录下来，可以为点击率预测模型提供一个重要的偏差特征。

（4）日期和时间。工作日还是周末，对不同类型的广告（如游戏）点击率有着明确的影响，这主要是由于在不同时间用户任务的集中程度不同，对广告的关注也有所区别。时间的因素，即是工作时间还是休闲时间，也有着类似的特性。因此，日期和时间一般来说也是必须要考虑的偏差特征。除了在模型中显式利用，往往还要求所有的训练过程都覆盖7天的整数倍的数据，其目的也是为了避免日期带来的偏差。

（5）浏览器。浏览器本身并不对广告效果有明确的影响，不过由于各个浏览器上 AD Blocker的覆盖程度有较大区别，因此在实际建模中其影响也相当大。

上面列举的几项都是在通用的广告系统中最常见的偏差特征，也是建模时需要首先考虑的，读者需要结合具体的广告产品，按照“去除与广告决策无关的影响因素”这一原则来确定和使用偏差特征。

5.点击反馈的平滑

用CTR或CoEC这样的点击反馈作为动态特征，大量的长尾组合特征对于准确地预测点击率有很大帮助。但是要利用好这些长尾组合特征，还需要解决一个问题，就是在统计不足的维度组合上如何稳健地统计CTR或CoEC。

以CTR为例，公式13.7给出了点击的生成模型，点击率就是这一模型的参数。在知道每次展示点击与否的情况下，可以得到参数µ的最大似然估计为：

其中 N 为总的展示数。当估计某些数据不足的维度组合上的点击率时，一般的思路是在分子分母上各加一个常量，以起到平滑的作用：

很显然，α/γ 应该等于某更大流量范围内的平均点击率。可是 α 和 γ 的绝对数值就没有太直观的方法可以设置。根据 10.3.3 节的介绍，也可以采用经验贝叶斯的方法来解决这个问题。

在贝叶斯的框架下，可以把 µ看成随机变量，由于公式 13.7是一个二项分布，其参数µ对应的共轭先验是Beta分布，即：

超参数 α和 β 其实就对应于公式 13.21中的 α和 γ−α。可以采用经验贝叶斯的方法来估计α和β。将公式13.7和公式13.22代入公式10.28给出的一般指数族分布经验贝叶斯解，可以得到解α和β 的具体EM算法：

E-step

M-step

其中M-step需要解关于α^new和β^new的方程组，因而并不是闭式解，不过这一方程组用数值方法求解并不难。

13.5.5 点击率模型评测

点击率模型预测的是点击事件出现的概率，因此可以采用准确率/召回率（Precision/Recall，PR）曲线或接收机操作特性（Receive Operating Characteristic，ROC）曲线来评测。这两个曲线实际上是对同样一组统计数据不同侧面的表现：点击率模型是一个对点击事件进行预测的模型，因此，对任何一个样本实例，存在下面四种情况。

（1）点击行为被预测为点击行为，其数目计为n₁。

（2）点击行为被预测为非点击行为，其数目计为n₂。

（3）非点击行为被预测为点击行为，其数目计为n₃。

（4）非点击行为被预测为非点击行为，其数目计为n₄。

对于这四个数值，有两种常见的视角：一是观察 Recall=n₁/（n₁+n₂） 和 Precision=n₁/（n₁+n₃） 的关系，二是观察 True Positive Rate=n₁/（n₁+n₂）（实际上 True Positive Rate 和 Recall 是一样的）和 False Positive Rate=n₃/（n₃+n₄） 的关系。当然，是否被预测为点击是针对某个点击概率的阈值而言的，因此，通过取不同的阈值，就可以得到一条Precision/Recall 曲线或者是 True Positive Rate/False Positive Rate 的曲线，前者即为 PR曲线，而后者就是 ROC 曲线。为了方便理解，我们把上述的几个基本量直观地表示在图13-7中。

图13-7 点击率模型评测若干统计量

实际的PR曲线可以参见图13-8（左）。一般来说，PR曲线呈下降的趋势，不过这并没有理论上的保证，实际数据上局部呈上升趋势的PR曲线也很常见。对广告而言，应该更加关注PR曲线的头部，因为尾部是Recall比较高，也就是很多广告候选都被考虑时的情形，而实际的投放环境中，只选择排名最好的一个或几个候选。另外一点需要注意的是，PR曲线下面的面积是没有明确的物理意义，因此不能作为有价值的指标来衡量。

实际的 ROC曲线可以参见图13-8（右）。一般来说，ROC曲线呈上升的趋势，不过这一点同样没有理论上的保证。与PR曲线不同，ROC曲线下的面积有明确的物理意义，它在一定程度上表征了对h=0和h=1事件估计值排序的正确性。我们把ROC曲线下的面积称为曲线下面积（Area Under Curve，AUC），这是评价点击率模型时常用的量化指标。AUC虽然经常被用作点击率模型的质量代表，却有一个问题要引起注意，那就是即使只用偏差模型，即对广告排序无直接贡献的模型来预测点击率，AUC往往也处于比随机猜测高得多的水平上，如图13-8中所示。因此，模型对广告排序的作用需要对这两个AUC的差值做评估才能比较公允地加以衡量。

图13-8 PR曲线（左）与ROC曲线（右）示例

无论是计算 ROC曲线还是 PR曲线，都是要统计上述的 n_1～4 这组值。严格的统计方法需要对整个测试集按照模型估算的点击率排序，不过这样的计算复杂度为 O（n log n）（n为测试集的样本数目），显然在测试样本量较大时无法实用。因此，可以采用近似但对实用来说足够精确的方法，即将整个点击率的取值范围划分成一组区间，并在每个区间上得到一个曲线点。此方法的原理与 12.3.4节中 reach/CTR曲线的生成方法是一致的，可以参考该节的介绍。

13.5.6 智能频次控制

第4章介绍过频次控制的问题。在竞价广告环境下，这一问题有些变化。合约式广告中，由于广告主对于位置可以由合约控制，因而可以在某个特定的位置上设定展示频次，这一点在按GD方式售卖的视频前贴片广告中应用最为广泛。但是在广告网络情形下，由于广告主的创意可能出现在各种媒体的各种位置上，不同位置的有效展示有相当大的差别。因此，简单设定一个展示数目上的频次来控制用户的接触次数是不太合理的。

在这种情况下，需要一个更智能的频次控制方案。最直接的思路是利用13.5.4节中介绍的EC概念。由于EC从某种程度上更接近于有效展示数目，可以采用EC上的累积计数代替频次来控制用户接触次数。我们把这种方案叫作智能频次控制。

在品牌广告和效果广告两种情况下，智能频次控制的做法也有所不同：在效果广告中，可以将 EC 的计数或者频次的计数作为点击率预测模型的特征直接加入训练，靠点击率模型的作用降低出现频次过高的创意的竞争力；在品牌广告中，可以通过EC计数上的直接控制达到一定用户接触程度的目的，由广告主来直接设定^[14]。

竞价广告精细的效果要求让我们认清了频次的本质：它与其他影响点击率的特征是平等的，并且应该放在统一的、数据驱动的计算框架下加以利用。而究竟对某个创意应该将频次控制在多少，也不应该是根据经验设定，而是应该放在竞价的环境中自行决定。