An Efficient Sampling-Based Algorithm to Compute HUM for Multi-Class Learning

The hypervolume under the receiver operating characteristic (ROC) manifold, referred to as HUM, is a critical metric for evaluating the performance in multi-classification problems. Nevertheless, its practical applicability is constrained by the polynomial time complexity of the standard implementation. This paper introduces a new fast algorithm for computing HUM value based on probability assessment vectors. Compared with the HUM value based on ordered response with a single marker, it poses unique challenges due to its complicated sample space. Inspired by the method of incomplete U-statistic, we propose a sampling-based algorithm for approximating HUM values. Theoretically, the approximation error diminishes inversely with computational time and becomes asymptotically negligible within quasi-linear computational complexity. Furthermore, we introduce a generalized definition of HUM to accommodate the discrete data, which fits well with our sampling-based method. Additionally, we present inference procedures applicable when probability assessment vectors are either known or estimated. The performance of the proposed procedures is evaluated through simulation studies. We also apply the method to two real-world applications to show its practical utility. Supplementary materials for this article are available online.