Classifier Calibration with ROC-Regularized Isotonic Regression¶

问题引入¶

研究背景¶

分类器的校准对于保证模型的置信度非常重要，目前对于分类器校准的重要方法是IR(isotonic regression，保序回归)，但是还没有比较好的工作从理论上证明他的能力水平。本文的主要工作就是证明IR的效果确实很好(证明了IR能保ROC曲线的凸包，从而保证其不会过拟合用于校准的数据集)，并且广义化了IR，使其适应K维的分类器，然后同样证明了对于K维分类器，广义化的IR同样能够有良好的校准效果。

研究问题的一些相关定义和性质¶

calibration(校准)¶

我们说一个分类器(包括多维的) $f:\mathcal{X} \longrightarrow \Delta_K$ 是校准的，当且仅当 $\mathbb{E}[Y|f(X)] = f(X)$, 这里 $\Delta_K$ 表示的是K维的单纯形

对于期望的计算，在预测概率取值离散的情况下，我们能用经验期望进行计算，在预测的概率取值连续的情况下，我们只能用其他方法进行估计。

calibration error(校准误差)¶

对于一个分类器 $f$ 他的校准误差被定义为 $\mathcal{K}(f) = \mathbb{E}[|\mathbb{E}[Y|f(X)] - f(X)|]$

值得一提的是，已经有工作证明了我们总是能找到一种预测(甚至可能是非常简单的)，来使我们的的模型校准，这一点说明，哪怕是预测效果很差的模型也可能是校准的，所以我们在追求校准的过程中一定要注意模型本身预测的效果。

calibration and proper scoring rules(校准和适当的评分准则)¶

我们知道，要评价我们的分类器的好坏，需要有一个损失函数，来衡量我们的预测结果和真实结果之间的“距离”，或者我们称这个损失函数为我们的“计分准则”。现在有一个重要的定理是，对于任意适当的计分准则，我们都能将其分解成两项，第一项是校准误差，第二项是一个修正项。为了后文介绍更加自然，我们在这里举出交叉熵损失函数的例子，其中用到的校准误差是KL差异函数。 $$ H(Y, f(X)) = \mathbb{E}[KL(f(X)) || \mathbb{P}(Y|f(X))] + \mathbb{E}[H(\mathbb{P}(Y|f(X)))] $$ 这告诉我们仅仅是做到使校准误差趋向0并不能达到保证我们的分类器能够表现优异（正如我们上一小节所言）。那么我们为什么还需要去调整我们的校准误差呢？因为事实上，我们很多通过机器学习得到的分类器并不是校准的，但是他们仍然有比较良好的效果，如果我们有一些方式，能够在不会过度拟合校准数据集的基础上，去校准我们的分类器，这或许能够使我们的分类器效果更加优异。

如何校准分类器¶

比较常用的校准分类器的方法是，将我们独立同分布的数据集分成两块，一部分用来训练，另一部分用来校准。这样做的好处在于分离了校准过程和训练过程，让这个方法适用范围更加广泛。而它的问题在于，对于数据点稀疏的情况，他的效果不是很好，笔者猜测可能是因为训练的数据和校准的数据集可能会有比较大的差异，也就是说尽管他们是独立同分布，但是实际的取值可能会有比较大的差异。还有就对于在线学习的情况不是很友好，因为每次得到新的数据，总是需要我们重新跑一遍校准数据集，计算的成本比较大。

二元分类器上的保序回归¶

这个章节介绍的主要是保序回归在二元分类的情况下两个重要的性质，一是校准我们初始的分类器，二是能够降低分类器的预测结果和真实结果的差距。

保序回归是校准的¶

isotonic regression(保序回归)¶

保序回归的定义和他的名字一样，其回归的结果在某种程度上是“有序的”：我们令 $n \in \mathbb{N}_+^*, (p_i, y_i)_{1 \le i \le n} \in (\mathbb{R}^2)^n$ 并且 $(\omega_i)_{1 \le i \le n} \in \mathbb{R}_+$ 作为权重的集合。假设我们对与下标 $i$ 的选取是按照概率 $p_i$ 升序排序的，那么保序回归解决的问题是

\[ \min_{r \in \mathbb{R}^n} \frac{1}{n} \sum_{i=1}^{n} \omega_i(y_i - r_i)^2 \text{such that } r_1 \le r_2 \le ... \le r_n \]

上述的自变量r可以被视为一个 $n$ 维向量，或者我们可以认为他是一个将概率 $p_i$ 从 $\mathcal{P} = R$ 映射到 $\mathcal{Y} = R$ 的一个函数且有 $r(p_i) = r_i$

这个问题一个优良的地方在与它是个凸优化问题，这意味这解决起来会有比较好的方法。并且感谢前人的工作，我们已经证明了IR能够最小化上文提到的KL差异函数，如果在监督学习的情境下，KL差异函数和交叉熵损失只差了一个常数比值，那么此时IR就能最小化交叉熵函数。

并且，原文章证明了IR确实能够校准我们的分类器，也就是让校准误差变为0。这一点根据下面的PAV算法和经验期望的计算可以马上得出。

PAV(pool adjacent violators)算法¶

解决IR的算法非常简单，叫做PAV算法，简要的说，先让所有的 $r_i$ = $y_i$，然后我们依次扫描，如果遇到 $r_i \lt r_{i-1}$ 的情况，我们就把 $r_i$ 的值变化为 $r_i$ 和 $r_{i-1}$ 的值的加权平均，并且更新 $r_i$ 的权重为 $r_i$ 的当前权重加上 $r_{i-1}$ 的权重，然后把 $r_{i-1}, \omega_{i-1}$ 移出我们的序列。一直这样做下去，我们只需要遍历一遍整个数据集，就得到了IR的解。

这个算法最重要的特点就是让数据分块池化，所以我们得到的结果是按块递增的，每一块内部都是这些数据点标签的加权平均值，当然一般来讲每个数据点的初始权重都是一样的。

保序回归保ROC-AUC¶

一个很重要的特征是，当我们对我们的分类器进行校准时，如果我们的分块过大，这会导致我们的分类器的预测变得很粗糙，不够准确，如果我们的分块过于细致，可能导致我们的分类器在校准数据集上过拟合，这些都是一般的校准方法不可避免的问题，但是我们的IR由于有了单调性假设，能够做到自动适应分块的数量。

symmetric ROC curve (SROC)¶

2维的单纯形可以被归约到 $\mathbb{R}$ 上的 $[0,1]$ 区间上，对于不同的阈值 $\gamma \in [0,1]$ ，我们把这个单纯形分成 $R_0 = [0, \gamma]$ 和 $R_1 = [\gamma, 1]$ 两部分，我们定义概率 $p_0(\gamma) = \mathbb{P}(X \in R_0 | Y = 0), p_1(\gamma) = \mathbb{P}(X \in R_1 | Y = 1)$ ，然后我们定义SROC为这样一个二维图 $\{(p_0(\gamma)), (p_1(\gamma)), \gamma \in \mathbb{R}\}$

前人的工作已经证明了以ROC曲线的凸包作为评价准则会比直接用ROC曲线作为评价准则效果更加好，而我们通过对原来的分类器进行保序回归来校准后的分类器，相应的ROC曲线，恰好就是原来的分类器的ROC曲线的凸包！证明在此省略，但是值得一提的是，这一特点是由IR的单调性假设导致的，这个单调性假设就像一个正则条件一样，导致我们的IR在校准数据集上的表现能被原来分类器的ROC曲线的凸包控制，从而保证了我们校准之后的分类器不会在校准数据集上过拟合。原文章也对IR和一般的校准器在Covertype dataset上做了比较，实验表明，确实IR的校准结果不会导致在校准数据集上的过拟合，所以他在测试数据集上的表现更加优异。

MULTI-CLASS IR (对于多类分类器的IR)¶

在二维的情况下我们对IR有很好的结论，我们自然也希望在高维的情况（分类器可以分出K类）下，同样能有这么好的结论。

ROC曲面在任意维度下的定义¶

未了能够讨论高维下的效果，我们首先要把我们各种概念扩充到高维的情况。原文章中已经展示了严谨的定义，本文为了完整性将会用自己的语言再次简要叙述一遍。

首先我们预测的类的概率的取值将会是k维的概率单纯形，而我们的阈值 $\gamma$ 的取值就落在k维空间中所有的单位向量的任意仿射组合中，然后我们定义概率单纯形关于这个阈值的一个分划，对于概率单纯形中的某一个点（向量），我们考察他和取定的阈值 $\gamma$ 的各坐标之差，我们说这个点是属于区域 $R_k(\gamma)$ 的，当且仅当这些坐标之差的第K个分量是最大的。

有了上述推广之后，对于ROC曲面的定义就和二维情况下比较类似了。对于给定的 $\gamma$ ROC曲面上的点的第k个分量是那些类别为k的点中，预测概率属于区域 $R_k(\gamma)$ 的概率。

ROC曲面的单调性定义¶

高维空间中的单调性定义不像我们在二维情况下那么直观，所以为了能够让我们的单调性定义为我们ROC曲面保凸包的性质起到作用，我们需要先回顾一下二维空间中ROC曲线的单调性，看清楚他在证明中起到什么具体的作用。

文章中提到的非常重要的一个观察是，对于任何一个阈值 $\gamma \in [0,1]$ ，我们相应生成一个点集分划 $S_0(r, \gamma)$ 和 $S_1(r, \gamma)$ （这里对这个划分符号略去了定义，实际上就是分别为预测概率小于阈值的数据点和预测概率大于阈值的数据点），正是因为有我们校准之后的预测函数是单调的，才有如下性质：

对于校准之后的ROC曲线任意一个阈值 $\gamma \in [0, 1]$ ，我们总能在校准之前的ROC上找到一个不同的阈值 $\gamma' \in [0, 1]$ 使得两者的点集分划相同。

这个观察直接导致了我们对高维空间单调性的定义，我们希望的单调性就是能够保证这个性质在高维空间中仍然成立，所以我们有如下对于单调性的定义：

我们令 $p = (p_i)_{i \in [1, n] \cap \mathbb{Z}}$ 来表示非校准的预测值，以及 $r = (r_i)_{i \in [1, n] \cap \mathbb{Z}}$ 作为校准之后的预测值。我们定义我们的校准之后的预测函数是ROC单调的当且仅当 $\forall \gamma \in A_K, \exists \gamma' \in A_K | S_k(r, \gamma) = S_k(p, \gamma'), \forall k \in [1, K] \cap \mathbb{Z}$

有了相应的定义之后，原文同样给出了一个递归的分割算法来校准分类器，可以认为是二维情况下IR的推广。

高维保序回归的效果¶

和二维的情况下一样，文章将经过运用高维IR进行分类器校准的结果会比普通的校准方法表现更加优异，主要体现在，他在校准分类器的同时，没有过拟合校准数据集，保证了分类器原有的性能。

评论¶

这篇文章的主要贡献在于为保序回归的良好的分类器校准效果给出了合理的理论阐释，并且将二维分类器下保序回归的算法推广到了高维，并且获得了良好的实验效果。我认为最关键的地方就在于保序回归的单调性要求能够很好地平衡校准过程中分块的数量，使之不会过大（影响分类器性能）或过小（导致在校准数据集上过拟合）。

维护我们分类结果关于概率的单调性是一件非常自然的事情，因为我们关于这一类预测的概率越大，越应该有充分的理由把这一数据点分到这个类中去。而文中具体的算法，就是把破坏这种单调性的数据点预测概率取了平均值。这一举措确实维护了非严格的单调性，但是实际上是删去了一些点（因为这些点的预测值被他们的均值替代，如果在二类分类的情况下预测值就不是0或1，这将不是一个有效的预测值，就意味这这些点被删去了），这会不会导致有些好的预测因为另一些坏的预测而取了均值之后牺牲了？如果说我们直接删除那些看起来预测效果非常离谱的点而不去修改预测效果合理的点，会不会让我们的分类器性能更好，预测更加完善？当然这样做有较大概率导致分类器不是校准的。

文中也提到了，在预测概率是离散的情况下，我们的研究比较容易进行，但是如果预测概率是连续的情况，就要先将预测概率离散化。但是这个过程无疑需要一些代价，所以我认为在预测概率连续的情况下，研究一种校准策略或者近似的校准策略，也许是一个可以探讨的话题。