# Efficient Constrained Graph Search for Post-hoc Error Correction in Binary Classifiers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 13 references that are in the map.
- First posted on arXiv 8 Jan 2024.

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

- [Selective Classification for Deep Neural Networks](https://mlsanity.com/paper/1705.08500/) (2017)
- [SelectiveNet: A Deep Neural Network with an Integrated Reject Option](https://mlsanity.com/paper/1901.09192/) (2019)
- [Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model](https://mlsanity.com/paper/1511.01644/) (2015)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [How to Fix a Broken Confidence Estimator: Evaluating Post-hoc Methods for Selective Classification with Deep Neural Networks](https://mlsanity.com/paper/2305.15508/) (2023)
- [Fast Interpretable Greedy-Tree Sums](https://mlsanity.com/paper/2201.11931/) (2022)

## Abstract (arXiv)

This study develops a graph search algorithm to find the optimal discrimination path for the binary classification problem. The objective function is defined as the difference of variations between the true positive (TP) and false positive (FP). It uses the depth first search (DFS) algorithm to find the top-down paths for discrimination. It proposes a dynamic optimization procedure to optimize TP at the upper levels and then reduce FP at the lower levels. To accelerate computing speed while improving accuracy, it proposes a reduced histogram algorithm with variable bin size instead of looping over all data points to find the feature threshold of discrimination. The algorithm is applied on top of a Support Vector Machine (SVM) model for a binary classification problem on whether a person is fit or unfit. It significantly improves TP and reduces FP of the SVM results (e.g., reduced FP by 90% with a loss of only 5% TP). The graph search auto-generates 39 ranked discrimination paths within 9 seconds on an input of 328,464 objects, using a dual-core laptop computer with a processor of 2.59 GHz.