点击率校准篇

综述

本篇文章是《讯飞AI营销平台算法实践》系列的第三篇，在上一篇的《基于spark训练点击率预估模型》中，我们介绍了基于spark平台我们可以搭建从数据预处理到特征生成，再到模型训练和评估的整套点击率预估系统，在本篇中我们将介绍对于模型预估的点击率如何进行校准。

为什么要做点击率校准？

我们在做点击率预估的时候，由于模型预测时采样不均，或者算法本身的特性（比如SVM和boosting会使结果趋向于呈sigmoid形状的分布；使用独立假设的Naive Bayes会使结果拉向0或1。），模型预测值与真实观察值之间往往存在很大的gap。

大多数的分类模型，得到的预测结果仅有定序意义，而不能够定量。很多情况下，仅仅得到一个好的AUC值是远远不够的，我们需要得到一个准确的概率值。例如，在优化最大收益的场景下，优化目标是最大化CTR*Price，通过模型分别学到的CTR的预测值不仅要保序，还要使预测值逼近真是分布才能获得准确的排序结果。

因此需要对CTR进行校准，使得CTR距离真实值越近越好。

校准方案

对于CTR校准的方法，大概有这么两种，一种是基于负采样的采用比例来进行校准，参考的论文是14年facebook的论文《Practical Lessons from Predicting Clicks on Ads at Facebook》。另一种就是今天的主角保序回归。

Isotonic regression

Isotonic regression (等渗回归，也叫保序回归,以下简称IR) 是一种非参数化方法（The non-parametric approach）；

假设模型的预测结果记为fi，真实目标记为yi,那么IR的基本假设为：

\[y_{i}\; =\; m\left( f_{i} \right)\; +\; \epsilon _{i} \]

其中m是isotonic(单调递增)的函数。通过给定数据集，可以通过下式求解m:

\[
\hat{m}\;=\;{argmin}_z\sum\left(y_i\,-\,\left(f_i\right)\right)^2
\]

IR的一种求解算法是pair-adjacent violators algorithm（简称PAV算法），时间复杂度是O(N)，主要思想是通过不断合并、调整违反单调性的局部区间，使得最终得到的区间满足单调性。PAV算法也是scikit-learn中isotonic regression库的求解算法。
其对数据拟合的情况可参考如下：

PAV

找到等渗回归问题的逐步常数解的一种算法是表1中给出的对相邻违规（PAV）算法。

\[
\begin{array}{l}
\textrm{PAV alogrithm}\\
\\
\textrm{1.} \; \textrm{Input:training set} \left(f_i,y_i\right) \textrm{sorted according to }f_i \\
\\
\textrm{2.} \; \textrm{Initalize } \hat{m}_{i,j}\,=\,y_i,w_{i,i}\,=\,1 \\
\\
\textrm{3.} \; \textrm{While }\exists i \; \hat{m}_{k,i-1}\,\geqslant\,\hat{m}_{i,l}\\
\\
\qquad \qquad \textrm{Set } w_{k,l}\;=\;w_{k,i-1}\;+\;w_{i,l}\\
\\
\qquad \qquad \textrm{Set } \hat{m}_{k,l}\;=\;\left(w_{k,i-1}\hat{m}_{k,i-1}\;+\;w_{i,l}\hat{m}_{i,l}\right)/w_{k,l}\\
\\
\qquad \qquad \textrm{Replace } \hat{m}_{k,i-1} \textrm{ and } \hat{m}_{i,l} \textrm{ with } \hat{m}_{k,l}\\
\\
\textrm{4.} \; \textrm{Output the stempwise const. function :}\\
\\
\qquad \qquad \hat{m}\left(f\right)\;=\;\hat{m}_{i,j}\, \textrm{ for } f_i\;<\;f\;\leqslant\;f_j
\end{array}
\]

我们可以更加通俗的解释下：

问题描述：给定一个无序数字序列，要求不改变每个元素的位置，但可以修改每个元素的值，修后得到一个非递减序列，问如何使误差（该处取平方差）最小？

保序回归法：从该序列的首元素往后观察，一旦出现乱序现象停止该轮观察，从该乱序元素开始逐个吸收元素组成一个序列，直到该序列所有元素的平均值小于或等于下一个待吸收的元素。

举例：

1.原始序列：<9, 10, 14>
分析：从9往后观察，到最后的元素14都未发现乱序情况，不用处理。
结果序列：<9, 10, 14>

2.原始序列：<9, 14, 10>
分析：从9往后观察，观察到14时发生乱序（14>10），停止该轮观察转入吸收元素处理，吸收元素10后子序列为<14, 10>，取该序列所有元素的平均值得12，故用序列<12, 12>替代<14,10>。吸收10后已经到了最后的元素，处理操作完成。
结果序列：<9, 12, 12>

3.原始序列：<14, 9, 10, 15>
分析：从14往后观察，观察到9时发生乱序（14>9），停止该轮观察转入吸收元素处理，吸收元素9后子序列为<14, 9>。求该序列所有元素的平均值得12.5，由于12.5大于下个带吸收的元素10，所以再吸收10，得序列<14, 9,10>。求该序列所有元素的平均值得11，由于11小于下个带吸收的元素15，所以停止吸收操作，用序列<11, 11, 11>替代<14, 9, 10>
结果序列：<11, 11, 11, 15>

Bining

Bining即是桶，将原始待校准模型的输出结果划分成N个等长的bin，使得
\[ 0\;\leqslant\;v_1\;\leqslant\;v_2...v_{n+1}\;\leqslant1 \]
其中，\( [v_i\,,\,v_{i+1}) \) 定义了第i个bin的区间范围。对于第i个bin的校准值通过下式获得:
\[
\hat{p}(i)\;\approx\;p\left(Y^s\;=\;1\,|\,v_i\;\leqslant f( {\hat{\tilde{\rho}}}^s ; \beta^* )\;\right) \\
\qquad \qquad \approx\;\frac{ \textrm{conversion examples with } f( {\hat{\tilde{\rho}}}^s ; \beta^* ) \;\in\; [v_i\,,\,v_{i+1}) }{\textrm{all examples with } f( {\hat{\tilde{\rho}}}^s ; \beta^* ) \;\in\;[v_i\,,\,v_{i+1})} \]
即计算落在区间 \( [v_i\,,\,v_{i+1}) \) 中的点击样本占落在此区间中的总样本的比例，即可得到

\[ \textrm{obtain the calibrate CTR for every bin } \hat{p}(1),...,\hat{p}(n) \]

对于一个落在bin区间内的新的测试样本，通过使用两个端点的统计值平滑得出最终预估值。即

\[
{\hat{p}}^{Test}\;\approx\;p\left(Y^{Test}\;=\;1\,|\,v_i\;\leqslant f( {\hat{\tilde{\rho}}}^{Test} ; \beta^* )\;<\;v_{i+1}\right) \\
=\;\alpha\hat{p}(v_i)\;+\;(1\,-\,\alpha)\hat{p}(v_{i+1}) \]

由于某些bin样本过少导致的预测值的非单调性，再使用IR对端点统计值做后处理。

应用流程

更简明的应用流程如下：

1. 准备一份验证集(不同于用于训练CTR预估模型的训练集)用于训练保序回归模型。这份验证集的每个样本仍然是展示点击信息。

2. 将[0, 1]区间划分为N个桶,每个桶的长度相同，比如N = 10或者N = 10.

3. 用之前训好的CTR预估模型在此验证集上进行预测，给出每个样本的点击率估计值，基于这些点击率估计值,将验证集中的样本落入对应的桶中。

4. 对每个桶，基于展示点击信息，计算落入样本的真实点击率。比如桶表示的区间为[1 x 10⁵,2 x 10⁵),取平均值为1.5 x 10⁵,这个桶的真实点击率为10“, 这样这个桶就得到eibility diagram图的一个点(1.5 x 10⁵,10⁶), 全部N个桶就构成了整个reiability diagram.

5. 对上步生成的eliability diagram中的数据运行isotonic regression.

上述流程最终产出校准用的映射表，在线上加载这个映射表实时应用，比如在线上预估出的CTR值为x，查校准用的映射表，判断x所在的桶，取得映射后的校准值y。在训练校准模型的流程中，有2点是有讲究的：第2步N的设置和第4步如何判定算出的真实点击率是可信的，这2点都需要结合实际情况来分析。

在样本充足的情况下，bin的个数越多逼近效果越好；因此在不断增大k的过程中，会出现收益的转折点；对于区间划分的方式，可以尝试一下按值和按样本数两种方式相结合，也可以尝试对一些样本充足的bin进行递归分桶，知道达到某一条件停止分裂（比如样本数不足或者不满足单调性时停止）。

适用场景

IR是一种非常有效的校准方法，可以纠正任何单调失真。不幸的是，这种额外的效能是有代价的。学习曲线分析表明，当数据稀缺时，更容易出现过度拟合，因此表现比Platt Scaling更差。[1]

IR对模型的输出特征没有要求;适用于样本量多的情形，样本量少时，使用等渗回归容易过拟合;IR通常作为辅助其他方法修复因为数据稀疏性导致的矫正结果不平滑问题;

参考文献：

[1] Alexandru Niculescu-Mizil, et al. Predicting Good Probabilities With Supervised Learning. ICML2005.

[2] https://en.wikipedia.org/wiki/Isotonic_regression

[3] https://sensirly.github.io/prediction-model-calibration/

[4] http://vividfree.github.io/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/2015/12/15/model-calibration-for-logistic-regression-in-rare-events-data

[5] 刘鹏, 王超. 计算广告. 2015