# Optimally Efficient Sequential Calibration of Binary Classifiers to Minimize Classification Error

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 44 references that are in the map.
- First posted on arXiv 19 Aug 2021.

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

- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [Binary Classifier Calibration using an Ensemble of Near Isotonic Regression Models](https://mlsanity.com/paper/1511.05191/) (2015)
- [Sequential Outlier Detection based on Incremental Decision Trees](https://mlsanity.com/paper/1803.03674/) (2018)

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

- [Generalized Huber Loss for Robust Learning and its Efficient Minimization for a Robust Statistics](https://mlsanity.com/paper/2108.12627/) (2021)
- [Nonparametric Extrema Analysis in Time Series for Envelope Extraction, Peak Detection and Clustering](https://mlsanity.com/paper/2109.02082/) (2021)
- [Efficient, Anytime Algorithms for Calibration with Isotonic Regression under Strictly Convex Losses](https://mlsanity.com/paper/2111.00468/) (2021)
- [Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection](https://mlsanity.com/paper/2109.04809/) (2021)
- [A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimization](https://mlsanity.com/paper/2109.07882/) (2021)
- [Smoothing with the Best Rectangle Window is Optimal for All Tapered Rectangle Windows](https://mlsanity.com/paper/2203.02997/) (2022)
- [A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization](https://mlsanity.com/paper/2203.05618/) (2022)
- [Second Order Regret Bounds Against Generalized Expert Sequences under Partial Bandit Feedback](https://mlsanity.com/paper/2204.06660/) (2022)
- [A Log-Linear Time Sequential Optimal Calibration Algorithm for Quantized Isotonic L2 Regression](https://mlsanity.com/paper/2206.00744/) (2022)
- [Optimal Tracking in Prediction with Expert Advice](https://mlsanity.com/paper/2208.03708/) (2022)
- [Merging Knockout and Round-Robin Tournaments: A Flexible Linear Elimination Tournament Design](https://mlsanity.com/paper/2203.12011/) (2022)
- [Robust, Nonparametric, Efficient Decomposition of Spectral Peaks under Distortion and Interference](https://mlsanity.com/paper/2204.08411/) (2022)
- [An Auto-Regressive Formulation for Smoothing and Moving Mean with Exponentially Tapered Windows](https://mlsanity.com/paper/2206.14749/) (2022)
- [1D to nD: A Meta Algorithm for Multivariate Global Optimization via Univariate Optimizers](https://mlsanity.com/paper/2209.03246/) (2022)
- [A 2-opt Algorithm for Locally Optimal Set Partition Optimization](https://mlsanity.com/paper/2303.08219/) (2023)
- [Formulation of Weighted Average Smoothing as a Projection of the Origin onto a Convex Polytope](https://mlsanity.com/paper/2303.11958/) (2023)
- [Sequential Linearithmic Time Optimal Unimodal Fitting When Minimizing Univariate Linear Losses](https://mlsanity.com/paper/2304.02141/) (2023)

## Abstract (arXiv)

In this work, we aim to calibrate the score outputs of an estimator for the binary classification problem by finding an 'optimal' mapping to class probabilities, where the 'optimal' mapping is in the sense that minimizes the classification error (or equivalently, maximizes the accuracy). We show that for the given target variables and the score outputs of an estimator, an 'optimal' soft mapping, which monotonically maps the score values to probabilities, is a hard mapping that maps the score values to 0 and 1. We show that for class weighted (where the accuracy for one class is more important) and sample weighted (where the samples' accurate classifications are not equally important) errors, or even general linear losses; this hard mapping characteristic is preserved. We propose a sequential recursive merger approach, which produces an 'optimal' hard mapping (for the observed samples so far) sequentially with each incoming new sample. Our approach has a logarithmic in sample size time complexity, which is optimally efficient.