# Linear Algorithms for Robust and Scalable Nonparametric Multiclass Probability Estimation

arXiv: https://arxiv.org/abs/2205.12460 · HTML: https://mlsanity.com/paper/2205.12460/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 51 references that are in the map.
- First posted on arXiv 25 May 2022.

## Builds on (most cited first, 4 of 4)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Revisiting the Calibration of Modern Neural Networks](https://mlsanity.com/paper/2106.07998/) (2021)
- [Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms](https://mlsanity.com/paper/1506.04359/) (2015)

## Built on by (most cited first, 2 of 2)

- [Robust Brain MRI Image Classification with SIBOW-SVM](https://mlsanity.com/paper/2311.08908/) (2023)
- [Sparse Learning and Class Probability Estimation with Weighted Support Vector Machines](https://mlsanity.com/paper/2312.10618/) (2023)

## Abstract (arXiv)

Multiclass probability estimation is the problem of estimating conditional probabilities of a data point belonging to a class given its covariate information. It has broad applications in statistical analysis and data science. Recently a class of weighted Support Vector Machines (wSVMs) has been developed to estimate class probabilities through ensemble learning for K-class problems (Wu, Zhang and Liu, 2010; Wang, Zhang and Wu, 2019), where K is the number of classes. The estimators are robust and achieve high accuracy for probability estimation, but their learning is implemented through pairwise coupling, which demands polynomial time in K. In this paper, we propose two new learning schemes, the baseline learning and the One-vs-All (OVA) learning, to further improve wSVMs in terms of computational efficiency and estimation accuracy. In particular, the baseline learning has optimal computational complexity in the sense that it is linear in K. Though not being most efficient in computation, the OVA offers the best estimation accuracy among all the procedures under comparison. The resulting estimators are distribution-free and shown to be consistent. We further conduct extensive numerical experiments to demonstrate finite sample performance.