PaperlayerView exact revision on arXiv

Source-linked AI summary

Extreme Binary Classification: Extreme Value Theory for Extreme Constraint on False Negative

Samuel Gruffaz, Muhammad Fawad, Jaakko Nevalainen

arXiv:2610.09984v1stat.MLcs.LGstat.APstat.ME

TL;DR

The paper addresses binary classification with rare positives and an almost-zero false-negative target, a regime where existing approaches appear insufficient. It develops an EVT-grounded threshold method and feature selection, reports theoretical control under stated conditions and favorable comparisons on four datasets, and illustrates interpretability in cancer screening.

  • Problem

    When positives are rare and false negatives costly, existing methods appear insufficient for targets below 1/N1.

    Source: §1 · p. 1

  • Method

    The paper combines EVT-grounded threshold adaptation with feature selection based on a permutation test comparing class extrema.

    Source: §1 · pp. 1–2

  • Results

    The method provides high-probability control at α = o(1/N1) under stated conditions and compares favorably with state-of-the-art approaches on four real-world datasets.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The feature-space procedure offers an interpretable feature-selection mechanism, illustrated on a clinical cancer-screening dataset.

    Source: §1 · p. 2

    The maximum-based threshold is sensitive to label noise, so the method requires relatively clean data.

    Source: Datasets · p. 8

Abstract

from arXiv · show

While binary classification is one of the most extensively studied problems in machine learning, the regime in which the goal is to learn a classifier with an almost zero false negative rate remains largely unexplored. In this paper, we introduce the Extreme Binary Classification problem, where the objective is to learn a classifier whose false negative rate $\alpha$ is constrained by $\epsilon_{N_1}=o_{N_1\to\infty}(1/N_1)$, with $N_1$ denoting the number of positive examples in the training set. To address this problem, we propose a threshold adaptation method theoretically grounded in guarantees derived from Extreme Value Theory, together with a feature selection procedure based on a permutation test applied to sample maxima. Experimental results on four real-world datasets of varying sizes demonstrate that our approach compares favorably with state-of-the-art methods. In addition, we illustrate its interpretability through an application to a cancer screening dataset.

1 INTRODUCTION

The introduction frames classification with rare positives and costly false negatives as a setting where existing methods fall short when the target false-negative rate is below 1/N1. It introduces an EVT-grounded approach with theoretical guarantees, a feature-selection procedure, and evaluations on four real-world datasets.

1 INTRODUCTION

  • Rare positive events and the high cost of missing them make false-negative control important despite limited positive training examples.Examples include equipment failures, cancer diagnoses, and patient mortality.Source: §1 · p. 1
  • Existing augmentation, cost-sensitive, and threshold-adaptation approaches appear insufficient when the target false-negative rate is below 1/N1.That regime requires extending the decision boundary beyond the observed positive examples.Source: §1 · p. 1
  • The paper uses Extreme Value Theory to target α = o(1/N1), with high-probability false-negative control under stated tail and concentration conditions.The guarantee uses a tractable threshold estimator and requires an exponential concentration inequality for the empirical mean excess.Source: §1 · pp. 1–2
  • A practical method adapts a given score or operates directly on features, with a permutation-test feature-selection procedure based on class extrema.The feature-space approach is presented as improving interpretability.Source: §1 · p. 2
  • The approach is evaluated on four real-world datasets against state-of-the-art methods, with interpretability illustrated on a clinical cancer-screening dataset.The screening application concerns a setting where false negatives may result in missed diagnoses with potentially severe consequences.Source: §1 · p. 2

2 METHODOLOGY

The methodology formulates classification under an almost-zero false-negative constraint, reviews why existing approaches do not cover that regime, and develops EVT-based thresholding with permutation-test feature selection.

2.1 Extreme Binary Classification

  • The target is a classifier with false-negative rate α ≪ 1/N1 while minimizing false positives; finite-sample uncertainty can make thresholds based on observed positive extrema underestimate unseen-data risk.Source: §2.1 · pp. 2–3

2.2 Related works

  • Prior approaches lack extreme-regime control: augmentation and cost weighting do not estimate safety margins, while Neyman–Pearson corrections and threshold-calibration guarantees fail as αN1=o(1).Source: §2.2 · p. 3

2.3 Background on Extreme Value Theory

  • Under an extreme-value tail assumption with ξ ≤ 0, the Peaks-Over-Threshold principle uses the K largest positive-class observations to estimate tail parameters for a conservative margin.Source: §2.3 · p. 4

2.4 Extreme classification

  • The practical method tests class maxima, estimates safety margins with EVT, and applies coordinate-wise permutation tests for feature selection.Source: §2.4 · pp. 5–6
  • The theory's assumptions can be difficult or impossible to verify, and slow GPD convergence for log-normal tails makes the analysis an optimistic scenario.Source: §2.4 · pp. 5–6
  • For multidimensional data, coordinate-wise classifiers provide feature selection; the false-negative rate is at worst αdselect when selected coordinates are independent, a correction omitted for correlated coordinates.Source: §2.4 · p. 6
  • The experiments compare thresholding on logistic scores, raw feature coordinates, and coordinates augmented with the logistic score.Source: §2.4 · p. 6

3 EXPERIMENTS

The experiments benchmark the method on four datasets and report results using false-negative and true-negative counts and their ratio. They also examine feature selection on ScreeningX and discuss how performance depends on the threshold setting.

3 EXPERIMENTS

  • The evaluation covers two large imbalanced datasets and two smaller datasets, and reports average false negatives, true negatives, and R(c)=TN/max(c,FN) for c∈{0.1,1}.Results use 5-fold cross-validation repeated with 10 seeds; the cancer-screening dataset is also used to examine interpretability.Source: §3 · p. 7, Datasets · p. 7

Datasets

  • Among the top five methods reported for each dataset, all achieve at most one false negative on average, except Conservative Ensemble on Credit; Table 1 ranks methods by TN/max(FN, 0.1).Source: Datasets · p. 7, Table 1 · p. 8
  • MulLog (Ours) achieves the best average performance; Q≥0.9 is suggested for high ratios with negligible false negatives, while MulLog-Q=0.1 ranks first for R(c=1).The discussion also reports that Conservative Ensemble is competitive but not interpretable compared with MulLog; CS-NTA-Logistic and NP-Logistic are cheap and interpretable but have a lower bound on α.Source: Datasets · pp. 7–8
  • The extrema-based feature test identifies the top five features selected by each competing method in over 90% of splits and rejects 8 of 12 features in over 80%.The feature comparisons use 40 train-test splits and a 5% significance level.Source: Datasets · p. 8
  • For X12, the extrema-based analysis shows that the class difference is driven primarily by the upper tail, a pattern logistic regression does not fully reveal.The largest positive-class value is much smaller than the largest negative-class value, while the two class minima are approximately equal.Source: Datasets · p. 8
  • On ScreenX, the method achieves a higher classification ratio than XGBoost using only four feature-specific thresholds.The paper notes that this decision rule can be applied even when the machine-learning classifier itself is unavailable.Source: Datasets · p. 8
  • The method has three stated limitations: it may need a scoring-model preprocessing step, is sensitive to label noise, and may struggle with highly multimodal feature distributions.The authors say the maximum-based threshold requires relatively clean data and that clustering may be needed for highly multimodal datasets.Source: Datasets · p. 8

4 CONCLUSION

The paper concludes that its method can maximize the true-negative-to-false-negative ratio and offers an interpretable feature-selection mechanism.

4 CONCLUSION

  • The method is effective at maximizing the true-negative-to-false-negative ratio and provides an interpretable feature-selection mechanism.The authors identify settings where false positives cost relatively little compared with false negatives, including clinical use, as particularly relevant.Source: §4 · p. 8

5 AI USE STATEMENT

The authors used AI for code drafting, rephrasing, grammar correction, and dataset descriptions in Section B.2, which they reviewed and verified.

5 AI USE STATEMENT

  • AI was used for code drafting, rephrasing, grammar correction, and generating Section B.2 dataset descriptions; the authors reviewed and verified that section.Source: §5 · p. 9

CHECKLIST

The checklist affirms that theoretical assumptions and proofs, algorithm properties, and experimental documentation are included. It also contains illustrations of GEV densities and GPD approximation of sample excesses.

CHECKLIST

  • The checklist affirms that the paper states assumptions, explains them, and includes complete proofs for theoretical results.It also marks descriptions of algorithm properties and complexity as included.Source: CHECKLIST · p. 10
  • The checklist marks experimental training details and result-reproduction instructions as included, except that the ScreenX dataset is withheld for anonymity.It also affirms reporting the measures, error bars, and computing infrastructure.Source: CHECKLIST · p. 10
  • The checklist marks asset citations and licenses as included, while new-asset material and human-subject documentation are marked not applicable.Source: CHECKLIST · p. 10

A ILLUSTRATION EVT THEORY

  • Figure 2 illustrates how the Generalized Extreme Value density varies with tail index ξ.Source: Figure 2 · p. 11
  • Figure 3 shows that, for sufficiently large u, the histogram of normal-sample excesses above the u-quantile is well approximated by a GPD with ξ=0.Source: Figure 3 · p. 11

B.1 Synthetic Experiments

The synthetic experiments compare theoretical and practical threshold estimators under exponential and generalized Pareto distributions. They test whether the practical estimator meets the target false-negative constraint across sample sizes and threshold settings.

B.1 Synthetic Experiments

  • The experiments compare theoretical estimator (7) with practical estimator (8), using Exp(5) and Gξ,1 with ξ = −10−5 as the score distributions.Figure 4 displays empirical densities based on 3,000 samples.Source: §B.1 · p. 11, Figure 4 · p. 12
  • For each N1, the procedure is repeated 10,000 times, estimating thresholds from N1 samples and evaluating false negatives on 100,000 new samples.Thresholds are evaluated across a grid of Qb values, with variability reported using standard-deviation bands.Source: §B.1 · pp. 11–12
  • For bounded distributions with ξ < 0 and |ξ| < 0.5, correction (8) can be overly conservative, so the suggested algorithm instead uses endpoint estimator (3) after the statistical test of [Theorem 6].For Unif([0, 10]), the experiments obtained FN = 0 because B(Qb) exceeded 10 for every estimated threshold.Source: §B.1 · p. 12
  • For both tested distributions, the practical estimator follows the theoretical false-negative constraint 1/(N1 log(N1)) when Qb ≥ 0.9, for N1 ∈ {25, 100, 500}.The comparison uses Exp(5) and Gξ,1 with ξ = −10−5.Source: §B.1 · p. 12, Figure 5 · p. 12, Figure 6 · p. 13

B.2 Datasets

The experiments use four datasets spanning cancer screening, government corruption, credit-card fraud, and breast cancer diagnosis.

B.2 Datasets

  • ScreenX labels aggressive cancer from blood-sample diagnostic features to guide biopsy decisions while seeking to avoid unnecessary biopsies and near-zero false negatives.Missing aggressive cancer may delay treatment and could ultimately lead to preventable mortality.Source: §B.2 · p. 13
  • The Corruption dataset combines eight Brazilian government information systems, with personally identifiable information removed and features covering appointments, salaries, positions, and financial investments.The dataset is anonymized to comply with GDPR requirements.Source: §B.2 · p. 13
  • The Credit dataset concerns fraud detection from transaction features collected over two days; all variables except Time and Amount are numerical PCA-transformed features.The dataset is identified as Credit Card Fraud Detection.Source: §B.2 · p. 13
  • Breast Cancer Wisconsin (Diagnostic) contains 569 fine-needle-aspiration samples, with 30 continuous nuclear-morphology features and labels for 212 malignant and 357 benign tumors.The dataset is described as a moderate-size, low-dimensional benchmark with strong predictive signal.Source: §B.2 · p. 13

B.3 Details for competing methods

This section details implementation choices for competing classifiers and threshold estimation, including constraints on separating training and validation data.

B.3 Details for competing methods

  • For large datasets, an RBF-kernel SVC is approximated with 200-dimensional Random Fourier Features followed by a linear SVC to reduce computational costs.The reported setting is approximately N = 300,000.Source: §B.3 · p. 14
  • Logistic regression uses a maximum of 1,000 L-BFGS iterations rather than the default 100 to ensure convergence.Source: §B.3 · p. 14
  • MulLog and Log fit the logistic model and select its score threshold on the full dataset, which may make the threshold slightly less conservative, while the final test set remains independent.No additional split was introduced to avoid further reducing the effective sample size; Mul is unaffected because it does not learn a regression score.Source: §B.3 · p. 14
  • Using the full dataset for classifier training and threshold estimation had little impact in the RC methods, so the recommended training-validation split was retained.Source: §B.3 · p. 14
  • A comparable training-validation analysis was unavailable for NP methods because nproc’s API cannot separate the data during threshold estimation.Source: §B.3 · p. 14
  • Table 2 ranks methods by TN/max(FN, 1), rather than TN/max(FN, 0.1).Source: Table 2 · p. 15

B.4 Complete results

The complete results include benchmark tables for four datasets and boxplots of the top methods’ Ratio(c=0.1).

B.4 Complete results

  • Tables 3–6 report results for ScreenX, Corruption, Credit, and Breast Cancer as mean ± one standard deviation over 10 repetitions of 5-fold cross-validation.Source: Table 3 · p. 15, Table 4 · p. 16, Table 5 · p. 17
  • Figures 7, 9, and 10 show Ratio(c=0.1) boxplots for the top five methods on ScreenX, Credit, and Breast Cancer.Source: Figure 7 · p. 19, Figure 9 · p. 20, Figure 10 · p. 20
  • Figure 8 shows the top-five-method Ratio(c=0.1) boxplots for Corruption; the tiny boxes for Mul-Q=0.9 and Mul-Q=0.95 reflect identical average fold performance across splits, not an implementation error.The learning procedure is deterministic.Source: Figure 8 · p. 19

B.5 Feature selection results

The appendix reports feature-selection and computation-time evidence, discusses the Neyman–Pearson umbrella algorithm and a permutation test on sample maxima, and includes proofs of the naive solution and theoretical bounds.

B.5 Feature selection results

  • X1, X4, X8, X10, X12 are always selected, while X3 and X5 are selected in more than 90% of 40 train-test splits.EBC-Min and EBC-Max record selection frequencies across the splits.Source: Table 8 · p. 21, Table 7 · p. 21

B.6 Computation time

C DISCUSSION OF THE UMBRELLA NP ALGORITHM

  • With continuous scores and i.i.d. data, positive-only validation post-processing targets FNR ≤ α at confidence 1−δ, but its guarantee probability is very low when α ≈ 0.The approach does not explicitly minimize false positives, which depend on the scoring function.Source: C DISCUSSION OF THE UMBRELLA NP… · pp. 22–23

D PERMUATION TEST ON THE MAXIMUM

  • The permutation test compares sample maxima under interchangeability; an explicit p-value expression is available when observations are distinct.The stated test asks whether one sample's maximum exceeds the other's.Source: D PERMUATION TEST ON THE MAXIMUM · p. 24

E.1 Proof of Lemma 1

  • Setting the naive interval endpoints to the minimum and maximum positive observations is always a valid solution.Source: §E.1 · p. 25

E.2 Proof of Theorem 4

The proof invokes DKW and tail conditions to establish a probability bound, proves a generalized Pareto quantile inequality, and considers multidimensional inflation with and without coordinate independence.

E.2 Proof of Theorem 4

  • Theorem 4’s proof combines DKW under i.i.d. sampling with K ≥ √N1 and QK = o(1/K), yielding a bound with probability 1−δquant−δest.Source: §E.2 · p. 26

E.3 Proof of Proposition 6

  • For a generalized Pareto variable with ξ ≤ 0 and β > 0, the stated quantile q1−Q bounds P(W ≥ q1−Q) by Q for 0 < Q ≤ exp(−1).Source: §E.3 · p. 26

E.4 Multidimensional case inflation

  • The multidimensional analysis considers both coordinate independence and an assumption-free case; dselected counts dimensions with nonconstant classifiers.Source: §E.4 · p. 27
Loading 2610.09984v1…