Fast and Unbiased Estimation of Volume Under Ordered Three-Class ROC Surface (VUS) With Continuous or Discrete Measurements

Shun Liu, Hongbin Zhu, Kai Yi, Xu Sun, Weichao Xu, Chao WangIEEE Access 2020 · DOI

Introduction

In diagnostic medicine and machine learning, the Area Under the Curve (AUC) is the standard for evaluating binary classifiers. However, many clinical and technical scenarios involve three ordered categories—such as "low," "medium," and "high" risk. For these trichotomous problems, the 2D ROC curve extends into a 3D ROC surface, and the performance metric becomes the Volume Under the Surface (VUS).

Despite its utility, VUS estimation has historically faced two significant hurdles: extreme computational complexity and bias when dealing with discrete data (ties). Traditional non-parametric methods can reach $O(N^5)$ complexity, making them impractical for large datasets. Furthermore, standard estimators often fail when data points share the same value, a common occurrence in discrete measurements like rating scales.

Methodology: A Unified DP Framework

To address these issues, researchers have developed a unified algorithm that achieves $O(N \log N)$ complexity while maintaining perfectly unbiased estimates for both continuous and discrete data. The approach leverages U-statistics to derive a variance formula that naturally incorporates the probability of ties.

The core innovation lies in the "S-term decomposition." The complex variance formula is broken down into counts of specific ordered triplets and quadruplets. Rather than using brute-force nested loops, the authors map these counting requirements onto a Dynamic Programming (DP) grid.

The Dynamic Programming grid used to efficiently calculate S-terms by traversing ordered data points.

By sorting the data once and then traversing this counter matrix in linear time, the algorithm avoids the polynomial "computational wall." This structure handles ties inherently; the logic of the DP transitions accounts for equal values without requiring artificial "tie-breaking" noise, which can introduce bias.

Performance and Results

The algorithm was validated using Monte Carlo simulations across various distributions, including Poisson and Geometric (discrete) and Normal and Rayleigh (continuous).

Zero Bias and High Precision

The proposed DP method demonstrated zero relative error in mean and variance across all tested sample sizes. In contrast, traditional rank-based methods or those relying on random noise to break ties showed significant fluctuations and persistent bias, particularly in smaller datasets.

Significant Speedup

The computational efficiency is the most striking result. The DP-based algorithm is approximately 100 times faster than the standard Bootstrap method. While Bootstrap's execution time scales poorly with increasing sample size, the DP method's performance remains nearly flat on a logarithmic scale, making it suitable for "Big Data" applications where previous VUS estimators would fail.

Conclusion

By combining U-statistics with a novel Dynamic Programming approach, this research provides a robust, fast, and unbiased tool for three-class ROC analysis. Moving from $O(N^5)$ to $O(N \log N)$ complexity transforms VUS from a niche theoretical metric into a practical tool for large-scale diagnostic and predictive modeling. Future work may extend this framework to unordered classes or higher-dimensional feature spaces.

Summary updated

BibTeX
@article{liu2020fast,
  author = {Shun Liu and Hongbin Zhu and Kai Yi and Xu Sun and Weichao Xu and Chao Wang},
  title = {{Fast and Unbiased Estimation of Volume Under Ordered Three-Class ROC Surface (VUS) With Continuous or Discrete Measurements}},
  journal = {IEEE Access},
  year = {2020},
  doi = {10.1109/access.2020.3011159},
}
Figure