Constrained Binary Decision Making

Daniel Průša, Vojtech FrancNeurIPS 2024 · OpenReview

Binary statistical decision making—choosing between two states based on statistical evidence—is foundational to machine learning tasks like out-of-distribution (OOD) detection and selective classification. Historically, deriving optimal strategies for these constrained problems has been a piecemeal process. This paper introduces a comprehensive mathematical framework that unifies and solves a wide range of Constrained Binary Decision Making (BDM) problems, reducing complex optimization challenges to a simple, threshold-based strategy.

The Challenge of Binary Decision Making

In machine learning, we frequently make binary choices (e.g., accepting a sample for classification versus rejecting it as an outlier) while balancing competing objectives, such as maximizing accuracy while capping the false positive rate.

While the Neyman-Pearson lemma solved a foundational version of this problem decades ago, extending it to modern paradigms like selective classification (where a model can choose to abstain from predicting) took years of isolated research. As new challenges emerge—such as Selective Classification in the Presence of OOD Data (SCOD)—practitioners frequently fall back on sub-optimal heuristics because the underlying constrained optimization math is daunting. This paper aims to replace those heuristics with a robust, "one-size-fits-all" mathematical tool.

A Unified Mathematical Framework

The authors formulate BDM as a generic constrained optimization problem involving Lebesgue measurable functions. Unlike traditional approaches that rely on Lagrange duality (which typically requires functions to be differentiable), this paper introduces a more general proof technique.

They define an optimization problem that minimizes an objective (like risk) subject to up to two constraints (like coverage and error rates). The core contribution, Theorem 1, characterizes the structure of every optimal solution within this formulation, proving that six distinct BDM problems are actually just special cases of one general equation.

The Optimal Strategy: Thresholding Uncertainty

The framework reveals that the optimal decision strategy, $c^*(x)$, consistently follows a straightforward threshold-based rule:

  1. Calculate an uncertainty score $s(x)$ for the input.
  2. If $s(x)$ is below a threshold $\lambda$, accept the sample.
  3. If $s(x)$ is above $\lambda$, reject it.
  4. If $s(x)$ equals $\lambda$, apply a randomization parameter $\tau$.

Crucially, the paper shows that this optimal score $s(x)$ is typically a simple linear combination of the conditional risk (the model's likelihood of being wrong, representing aleatoric uncertainty) and the likelihood ratio (the sample's likelihood of being OOD, representing distribution uncertainty). This is a major insight for practitioners: there is no need to invent complex, non-linear heuristics to combine different detectors. The optimal approach is a linear combination of their respective scores.

Key Theoretical Results

As a purely theoretical contribution, the paper validates its framework by re-deriving and extending known optimal strategies without relying on specific datasets. The authors successfully:

  • Re-derive classic strategies: The Neyman-Pearson strategy, as well as optimal solutions for Bounded-Abstention and Bounded-Improvement models.
  • Generalize SCOD: Provide a generalized solution for the SCOD problem, which was previously solved only for specific continuous cases.
  • Introduce novel variants: Formulate and solve two new SCOD variants—one enforcing hard constraints on both True Positive and False Positive Rates, and another focusing on Precision-Recall constraints.

Practical Implications and Limitations

This unification drastically simplifies model development. Instead of attempting to "learn" a complex binary decision function from scratch, developers only need to approximate two components (risk and likelihood ratio) and tune three scalar parameters ($\theta, \tau, \beta$) on a validation set. The theorem makes no assumptions about the instance space, meaning it works equally well for discrete data (like text) and continuous data (like images).

However, the framework does have limitations:

  • Constraint Scaling: The current proof covers problems with up to two constraints. Extending this to $N$ constraints remains an open problem due to increasing combinatorial complexity.
  • Estimation Error: The theory assumes accurate estimation of underlying probability distributions. In practice, the real-world optimality of the strategy will be limited by how well a neural network can approximate the conditional risk and likelihood ratios.
  • Parameter Tuning: While the framework identifies the form of the optimal strategy, the specific scalar parameters still require manual tuning for every specific problem and dataset.

Summary updated

Abstract

Binary statistical decision making involves choosing between two states based on statistical evidence. The optimal decision strategy is typically formulated through a constrained optimization problem, where both the objective and constraints are expressed as integrals involving two Lebesgue measurable functions, one of which represents the strategy being optimized. In this work, we present a comprehensive formulation of the binary decision making problem and provide a detailed characterization of the optimal solution. Our framework encompasses a wide range of well-known and recently proposed decision making problems as specific cases. We demonstrate how our generic approach can be used to derive the optimal decision strategies for these diverse instances. Our results offer a robust mathematical tool that simplifies the process of solving both existing and novel formulations of binary decision making problems which are in the core of many Machine Learning algorithms.
BibTeX
@inproceedings{prusa2024constrained,
  author = {Daniel Průša and Vojtech Franc},
  title = {{Constrained Binary Decision Making}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=ntV5xZfzEk},
}
Figure