广东工业大学自动化学院，广东 广州

收稿日期：2024年1月29日；录用日期：2024年4月9日；发布日期：2024年4月17日

摘要

接收机工作特性曲线(ROC)分析在科学和工程领域中特别时在机器学习中处理二分类问题时被广泛应用。然而，在实际情况下，多分类问题常常出现。为解决这个问题，学者引入了多类ROC超曲面下的体积VUHS概念，尽管已有学者提出了连续样本下计算VUHS的快速算法，但对离散样本下的VUHS研究仍显不足。本文提出了一种新的方法：基于动态规划(DP)的VUHS快速无偏估计算法。该算法旨在提高计算效率并确保无偏性，可同时处理连续及离散母体样本下的问题。通过实验验证了该算法的无偏性和计算效率，证实了其在处理多分类问题中的有效性和可靠性。

关键词

机器学习，接收机工作特性曲线(ROC)，曲面下面积(AUC)，多分类，(超)曲面下体积(VUHS)

Fast and Unbiased Estimation of Volume under Ordered Multi-Class ROC Hyper-Surface (VUHS) with Discrete Measurements

Haiping Wu, Hongbin Zhu, Zhijing Xiao, Weichao Xu^*

School of Automation, Guangdong University of Technology, Guangzhou Guangdong

Received: Jan. 29^th, 2024; accepted: Apr. 9^th, 2024; published: Apr. 17^th, 2024

ABSTRACT

Receiver Operating Characteristic (ROC) analysis is extensively utilized in scientific and engineering domains, particularly when dealing with binary classification problems in machine learning. However, multiclass classification issues frequently arise in practical scenarios. To tackle this issue, scholars have introduced the concept of the Volume under the Hypersurface of the multi-class ROC (VUHS); although fast algorithms for computing VUHS have been proposed under continuous sample distributions, research on VUHS for discrete sample cases remains insufficient. This paper presents a novel approach: a Fast and Unbiased Estimation Algorithm for VUHS based on Dynamic Programming (DP). This algorithm aims to enhance computational efficiency while ensuring unbiasedness, capable of addressing problems derived from both continuous and discrete parent populations. The experimental validation confirms the algorithm’s unbiasedness and computational efficiency, substantiating its effectiveness and reliability in handling multiclass classification problems.

Keywords:Machine Learning, Receiver Operating Characteristic (ROC) Curve, Area under the Curve (AUC), Multiclass Classification, Volume under the (Hyper) Surface (VUHS)

Copyright © 2024 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

接收机工作特性(Receiver Operating Characteristic，简称ROC)分析起源于二战时期的雷达探测理论，最初主要用于评估雷达探测性能 [1] 。如今，这一工具已广泛应用于医学、心理学、生物信息学、信号处理以及机器学习等诸多科学与工程研究领域。上世纪90年代，学者们将ROC曲线引入至机器学习领域 [2] ，用以评判二类分类器的性能。自此以后，ROC曲线在机器学习、计算机视觉等领域的算法评估与优化工作中发挥了重要作用。

ROC分析是根据样本隶属类别的先验知识，可以根据不同的阈值设置绘制出假阳性率和真阳性率的二维曲线图，通过计算曲线下方的面积(AUC)来评价二元分类器的总体性能，首先它是非参数的，不需要预先知道样本的分布，同时具对数据中类别分布和误分类代价不敏感的优良特性，若正负分类比例发生变化，ROC曲线不受影响 [3] 。

原来的ROC分析框架只适用于两类的情况，随着人工智能等领域的迅猛发展，研究者们的关注点已不再局限于两类问题，而是逐渐转向解决三类甚至多分类问题。Alonz等人提出ROC曲面下体积VUS，将ROC分析拓展到三类背景下 [4] ，LIU等人提出了基于动态规划的VUS的快速算法 [5] [6] 。Nakas等人对多类问题进行了研究，并提出了多类ROC超曲面下面积VUHS的无偏估计量 [7] ，ZHU等人在这个基础上提出了连续样本下VUHS的快速算法 [8] 。尽管学者提出了VUHS概念以应对多类问题，并进行了一系列相关研究，但目前大部分研究主要集中在连续样本条件下对VUHS的估算上；相比之下，针对离散样本条件下VUHS的无偏估计研究则相对较少。同时现有对此类问题的算法存在计算复杂度高、偏差较大的问题。为此，本文提出了一种线性算法，用于对多个有序连续或离散测量的VUHS进行均值的无偏估计。

2. 利用动态规划计算VUHS的无偏估计量

2.1. VUHS的概率解释

令 $X_1,\cdots ,X_r$ 是r类问题中的r个随机变量。假设 ${\left\{X_{1,i_1}\right\}}_{i_1=1}^{n_1},\cdots ,{\left\{X_{1,i_r}\right\}}_{i_r=1}^{n_r}$ 是分别取自累积分布函数为 $F_1\left(x_1\right),\cdots ,F_r\left(x_r\right)$ 的离散分布的独立同分布样本集。如Nakas等人 [7] 的论文中所示，以下概率的线性组合

${\theta }_r=Pr\left(X_1\le \cdots \le X_r\right)$ (1)

可以解释为在单位r立方体内的r类ROC超曲面(VUHS)下的体积，当样本母体分布为连续时，式(1)自动退化成连续样本下的VHUS形式 ${\theta }_r=Pr\left(X_1<\cdots <X_r\right)$ 。以三分类离散样本情况下为例，可获得以下概率公式：

$\begin{array}{c}\theta =Pr\left(X_1\le X_2\le X_3\right)\\ =Pr\left(X_1<X_2<X_3\right)+\frac{1}{2}Pr\left(X_1=X_2<X_3\right)\\ +\frac{1}{2}Pr\left(X_1<X_2=X_3\right)+\frac{1}{6}Pr\left(X_1=X_2=X_3\right)\end{array}$ (2)

从式(2)中不难发现，当 $F_1\left(x_1\right)=F_2\left(x_2\right)=F_3\left(x_3\right)$ 时， $\theta =1/3!=1/6$ ，这说明统计模型采用了随机预测的策略，是一个随机选择分类器；而当 $\theta =1$ 时，则意味着从左到右 $X_1,X_2,X_3$ 是完全可分的。因此，可以从式(2)中得出，VUHS可以表征多类样本的分离程度。

2.2. VUHS的无偏估计量

为了方便起见，首先引入一些符号。设 $R=\left\{1,2,\cdots ,r-1\right\}$ 为 $X_1,\cdots ,X_{r-1}$ 的下标序列， $\Omega$ 为序列R的递增子序列的集合，其元素个数为 $S=C_{r-1}^0+\cdots +C_{r-1}^{r-1}=2^{r-1}$ ， ${\omega }_j$ 表示 $\Omega$ 中的第j个元素，使用 ${\omega }_j$ 标记有序序列 $X_1,\cdots ,X_r$ 内等号开始的下标位置，设 ${\omega }_j$ 序列共有k个连续子序列，每个子序列的长度分别为 $b_i$

$R=\left\{1,2,\cdots ,\underset{b_1}{\underset{︸}{n_1,\cdots ,n_1+b_1-1}},\cdots ,\underset{b_k}{\underset{︸}{n_k,\cdots ,n_k+b_k-1}},\cdots ,r-1\right\}$

${\omega }_j=\left\{\underset{b_1}{\underset{︸}{n_1,\cdots ,n_1+b_1-1}},\cdots ,\underset{b_k}{\underset{︸}{n_k,\cdots ,n_k+b_k-1}}\right\}$ (3)

其中 $n_i\ge 1$ ， $n_i+b_i\le r$ ， $b_i\ge 1$ 。由式(1)可以构造出VUHS的非参数估计量，即：

${\hat{\theta }}_r=\frac{1}{n_1\cdots n_r}{\displaystyle \underset{j=1}{\overset{2^{r-1}}{\sum }}\left[Weigh{t}_{{\omega }_j}\cdot {\displaystyle \underset{i_1=1}{\overset{n_1}{\sum }}\cdots }{\displaystyle \underset{i_r=1}{\overset{n_r}{\sum }}{I}_{{\omega }_j}}\left(X_{1,i_1},X_{2,i_2},\cdots ,X_{r,i_r}\right)\right]}$ (4)

其中， $Weigh{t}_{{\omega }_j}$ 表示 $\omega$ 对应的事件的权重，根据 $\omega$ 序列内连续子序列区块的长度求得：

$Weigh{t}_{{\omega }_j}=\{\begin{array}{ll}1\hfill & k=0\hfill \\ {\displaystyle \underset{i=1}{\overset{k}{\prod }}\frac{1}{\left(b_i+1\right)!}}\hfill & k>0\hfill \end{array}$ (5)

对于式(3)定义的标记序列，若满足

$x_1<\cdots <x_{n_1}=\cdots =x_{n_1+b_1}<\cdots <x_{n_k}=\cdots =x_{n_k+b_k}<x_r$

则 $I_{\omega }(·)$ 的值等于1，否则为0，例如，当 $r=3$ 时， $\Omega =\left\{{\omega }_1,{\omega }_2,{\omega }_3,{\omega }_4\right\}=\left\{\left\{\right\},\left\{1\right\},\left\{2\right\},\left\{1,2\right\}\right\}$ ，对应的权重 $Weigh{t}_{{\omega }_j}$ 依次为1，1/2，1/2，1/6。当满足 $X_{1,i_1}<X_{2,i_2}<X_{3,i_3}$ 时， $I_{{\omega }_1}(·)$ 等于1，否则为0；当满足 $X_{1,i_1}=X_{2,i_2}<X_{3,i_3}$ 时， $I_{{\omega }_2}(·)$ 等于1，否则为0；当符合 $X_{1,i_1}<X_{2,i_2}=X_{3,i_3}$ 时， $I_{{\omega }_3}(·)$ ，为1，否则为0。当符合 $X_{1,i_1}=X_{2,i_2}=X_{3,i_3}$ 时， $I_{{\omega }_4}(·)$ 等于1，否则为0。

2.3. VUHS估计量的快速算法

直接基于式(4)计算 ${\hat{\theta }}_r$ 十分低效，例如，当所有的样本量相等时，即 $n_1=\cdots =n_r=m$ ，则时间复杂度为 $O\left(m^r\right)$ ，然而我们可以采用动态规划的方法进行快速实现。首先需要对 $I(·)$ 括号内的事件进行分类，每个标记序列 $\omega$ 对应一个事件，符合事件条件的事件数量为：

$S={\displaystyle \underset{i_1=1}{\overset{n_1}{\sum }}\cdots }{\displaystyle \underset{i_r=1}{\overset{n_r}{\sum }}{I}_{{\omega }_j}}\left(X_{1,i_1},\cdots ,X_{r,i_r}\right)$ (6)

例如，当 $r=4$ 时，其全部事件如下表所示，结合式(4)和式(6)便可以计算出4类的VUHS的估计量 $\hat{\theta }$ ：(表1)

$\hat{\theta }=\frac{1}{n_1{n}_2{n}_3{n}_4}\left(S_1+\frac{1}{2}{S}_2+\frac{1}{2}{S}_3+\frac{1}{2}{S}_4+\frac{1}{6}{S}_5+\frac{1}{4}{S}_6+\frac{1}{6}{S}_7+\frac{1}{24}{S}_8\right)$ (7)

表1. 四类样本情况下计算VUHS估计值所需事件及对应参数

接下来将介绍如何通过动态规划获得所需要的基础事件的实际数量。

2.3.1. DP计算矩阵

令 $Z_1,\cdots ,Z_N,N=n_1+n_2+\cdots +n_r$ 是由集合 $X_1,\cdots ,X_r$ 合并组成的联合序列。对这个序列进行升序排列，得到该序列的统计量：

$\underset{Bloc{k}_1}{\underset{︸}{Z_{\left(1\right)}=\cdots =Z_{\left(1\right)}}}<\cdots <\underset{Bloc{k}_J}{\underset{︸}{Z_{\left(J\right)}=\cdots =Z_{\left(J\right)}\left(=Z_i\right)}}<\cdots <\underset{Bloc{k}_K}{\underset{︸}{Z_{\left(K\right)}=\cdots =Z_{\left(K\right)}}}$ (8)

假设区块 $Bloc{k}_J$ 中的所有元素的值都等于 $Z_i$ 。令 ${\delta }_{1,i}\cdots {\delta }_{r,i}$ 为当 $i=1,\cdots ,K$ 时，样本集 $X_1,\cdots ,X_r$ 中分别等于 $Z_i$ 的元素的数量。那么对于r类向量集可得到r个计数向量，分别表示为 $C_{X_1}=\left[{\delta }_{1,1},\cdots ,{\delta }_{1,K}\right],\cdots ,C_{X_r}=\left[{\delta }_{r,1},\cdots ,{\delta }_{r,K}\right]$ ，向量长度均为K。将这些向量按序号自上而下堆叠，便得到了用于动态规划的计算矩阵。

2.3.2. 4类问题

下面首先探讨当 $r=4$ 情况下，标记序列 ${\omega }_3=\left\{2\right\}$ 时， $S_3$ 的计算过程，进一步解释动态规划的计算结构。由上表可得：

$\begin{array}{c}{S}_3=\epsilon \left(X_4>X_3=X_2>X_1\right)\\ ={\displaystyle \underset{i_1=1}{\overset{n_1}{\sum }}{\displaystyle \underset{i_2=1}{\overset{n_2}{\sum }}{\displaystyle \underset{i_3=1}{\overset{n_3}{\sum }}I}}}\left(X_{4,i_3}>X_{3,i_2}=X_{2,i_2}>X_{1,i_1}\right)\\ ={\displaystyle \underset{i_3=1}{\overset{K}{\sum }}{\displaystyle \underset{i_2=1}{\overset{i_3-1}{\sum }}{\displaystyle \underset{i_1=1}{\overset{i_2-1}{\sum }}{\delta }_{1,i_1}}}}{\delta }_{2,i_2}{\delta }_{3,i_2}{\delta }_{4,i_3}\end{array}$ (9)

式(9)可以通过动态规划计算结构实现，首先将之前介绍的计数向量 $C_{X_1},C_{X_2},C_{X_3},C_{X_4}$ 自下而上进行堆叠，构成计数矩阵 $C_{4\times k}$ ，然后进一步把 $C_{\left[3,1\right]},C_{\left[2,1\right]},C_{\left[1,2\right]}$ 初始化为0，如图1所示：

图1. 计算式(9)中定义的 $S_3$ 流程图，其中 $K=7$ 为了方便可视化

规划路径在线性时间( $O\left(4K\right)$ )内就可以从计数矩阵的左下角更新到右上角，其中的更新规则为：

$C_{\left[I,J\right]}=\{\begin{array}{ll}{C}_{\left[I,J\right]}+C_{\left[I,J-1\right]}\hfill & I=4,J\in \left[2,K-2\right]\hfill \\ C_{\left[I,J\right]}\cdot C_{\left[I+1,J-1\right]}\hfill & I=3,J\in \left[2,K-1\right]\hfill \\ C_{\left[I,J\right]}\cdot C_{\left[I+1,J\right]}+C_{\left[I,J-1\right]}\hfill & I=2,J\in \left[2,K-1\right]\hfill \\ C_{\left[I,J\right]}\cdot C_{\left[I+1,J-1\right]}+C_{\left[I,J-1\right]}\hfill & I=1,J\in \left[3,K\right]\hfill \end{array}$ (10)

最后当路径移动到右上角后，我们想要得到的 $S_3$ 的值将会存储在矩阵元素 $C_{\left[1,K\right]}$ 中。其他的事件均可以由该DP计算矩阵获得，进而由式(7)得到 $\hat{\theta }$ 的值。

2.3.3. r类问题

为了将动态规划方法推广到类问题，需要把以上算法的更新规则进行进一步的处理，首先将更新规则，分为累乘计算与累加计算，再根据标记序列与索引关系选择不同的更新规则，具体算法的伪代码如下：

Algorithm 1. Calculating the number of events S

算法1. 计算各事件的个数S

3. 实验及分析

为了验证本文所介绍方法的无偏性和快速性，首先将基于动态规划的VUHS算法(用 ${\hat{\theta }}_{DP}$ 表示)与基于式(4)的估计算法(用 ${\hat{\theta }}_{SLOW}$ 表示)以及基于图论(用 ${\hat{\theta }}_{GRA}$ 表示)的方法进行比较。我们生成了基于泊松分布的r个独立同分布连续样本集， ${\left\{X_{k,i_k}\right\}}_{i_k=1}^{n_k}~P\left(\lambda \right),k\in \left[1,r\right]$ ，在进行无偏性实验时，利用均值相对误差(REM)作为指标来评估算法的无偏性：

$REM\triangleq \frac{E\left({\hat{\theta }}_{\zeta }-{\hat{\theta }}_{SLOW}\right)}{{\hat{\theta }}_{SLOW}}$ (11)

其中， $\zeta =\left\{DP,GRA\right\}$ ，实验设置了 $r=4,r=5$ 两组样本进行比较，为了使得到的结果更加稳定，实验中每个算法运行1000次再取其平均值。我们实验结果如下图所示。

从图2中我们可以看到，由于 ${\hat{\theta }}_{DP}$ 算法中需要对数据进行预处理， ${\hat{\theta }}_{DP}$ 的运算时间要略慢于同样是线性对数量级的 ${\hat{\theta }}_{GRA}$ ，但由于差别实在太小，可以认为这两个算法在计算效率上是一致的。反观 ${\hat{\theta }}_{SLOW}$ 在样本类别及样本量增加时，其运算时间均会出现飞速的增长，因为它的算法时间复杂度是 $O\left(n^r\right)$ 。

如图3所示，在无偏性上显然 ${\hat{\theta }}_{DP}$ 的表现优于 ${\hat{\theta }}_{GRA}$ ， ${\hat{\theta }}_{DP}$ 的均值相对误差完全拟合 $REM=0$ 的直线，而 ${\hat{\theta }}_{SLOW}$ 是VUHS的无偏估计，因此证明了算法的无偏性。另一方面， ${\hat{\theta }}_{GRA}$ 的均值相对误差，随着样本数量的增加，在某个固定值附近波动，当样本类别增加时，误差会进一步增大，说明了 ${\hat{\theta }}_{GRA}$ 在处理离散样本时是有偏的。

图2. 三种算法计算VUHS点估计时CPU运行时间对比结果

图3. 基于动态规划的估计算法与基于图论的方法的无偏性比较结果

4. 结论

本文基于动态规划提出了一种VUHS的快速无偏估计算法，首先对VUHS的估计值表示方法进行优化，并通过建立动态计算矩阵，将算法时间复杂度降低至线性对数级，其次将VUHS点估计快速算法拓展到连续及离散样本下，并设计了蒙特卡洛实验进行了检验。实验结果表明，本文设计的DP算法矩阵可以有效的提升VUHS的计算效率，该算法相较于基于图论的方法有更好的无偏性，相较于SOLW算法有更好的快速性，特别是在应对类别多和样本量大的机器学习模型的应用背景下。因此，本文的方法在VUHS的研究上有一定的理论意义及技术价值。

基金项目

本文研究工作由国家自然科学基金项目(62171141, 61771148)资助。

文章引用

吴海平,朱鸿斌,肖芷菁,徐维超. 有序多类ROC超曲面下体积的快速无偏估计
Fast and Unbiased Estimation of Volume under Ordered Multi-Class ROC Hyper-Surface (VUHS) with Discrete Measurements[J]. 人工智能与机器人研究, 2024, 13(02): 177-184. https://doi.org/10.12677/airr.2024.132019

参考文献