Neyman-Pearson Classification under High-Dimensional Settings

Anqi Zhao, Yang Feng, Li-e Wang, Xin Tong

Abstract: Most existing binary classification methods target on the optimization of the overall classification risk and may fail to serve some real-world applications such as cancer diagnosis, where users are more concerned with the risk of misclassifying one specific class than the other. Neyman-Pearson (NP) paradigm was introduced in this context as a novel statistical framework for handling asymmetric type I/II error priorities. It seeks classifiers with a minimal type II error and a constrained type I error under a user specified level. This article is the first attempt to construct classifiers with guaranteed theoretical performance under the NP paradigm in high-dimensional settings. Based on the fundamental Neyman-Pearson Lemma, we used a plug-in approach to construct NP-type classifiers for Naive Bayes models. The proposed classifiers satisfy the NP oracle inequalities, which are natural NP paradigm counterparts of the oracle inequalities in classical binary classification. Besides their desirable theoretical properties, we also demonstrated their numerical advantages in prioritized error control via both simulation and real data studies.

Introduction

In standard binary classification, the primary objective is typically to minimize the overall risk, which treats all misclassifications equally. However, many critical real-world applications—such as medical diagnosis or fraud detection—exhibit asymmetric error costs. For instance, in cancer diagnosis, a "Type I error" (failing to detect the disease) is significantly more dangerous than a "Type II error" (a false alarm requiring further testing).

The Neyman-Pearson (NP) paradigm addresses this by seeking to minimize the Type II error while keeping the Type I error below a user-defined threshold $\alpha$. While well-established in classical hypothesis testing, applying this paradigm to high-dimensional machine learning ($d \gg n$) presents significant challenges. Existing methods often "relax" the error constraint, failing to provide strict guarantees. Furthermore, the "noise accumulation" inherent in high-dimensional data often causes specialized classifiers to fail. This paper introduces the first classifiers with guaranteed theoretical performance—"NP oracle inequalities"—under the NP paradigm in high-dimensional settings.

Methodology: A Plug-in Approach for High Dimensions

The authors propose a multi-step pipeline based on a plug-in approach derived from the fundamental Neyman-Pearson Lemma. To ensure robustness and avoid overfitting, the method incorporates:

  1. Sample Splitting: Data is divided into independent subsamples for feature screening, density estimation, and thresholding.
  2. Feature Screening: Marginal statistics (e.g., t-statistic or Kolmogorov-Smirnov-like D-statistic) are used to filter out noise and retain only the most informative features.
  3. Naive Bayes Estimation: The density ratio of the two classes is estimated under the Naive Bayes assumption of feature independence. The authors provide both a parametric version (PSN²) for Gaussian data and a non-parametric version (NSN²) using kernel density estimation.
  4. Order Statistic Thresholding: Instead of a fixed threshold, the decision boundary is determined by a specific order statistic from the estimated density ratios, ensuring the Type I error constraint is respected with high probability.

Experimental Evaluation

The proposed methods were evaluated against standard classifiers using both simulations and real-world high-dimensional datasets, including gene expression profiles (Neuroblastoma) and protein activity prediction (p53 Mutants).

A key finding from the Neuroblastoma study (predicting high-risk vs. low-risk cases across 10,707 genes) is the superior error control of the NP-based approach. While standard methods like Support Vector Machines (SVM) and Penalized Logistic Regression (pen-log) failed to prioritize the Type I error, the proposed PSN² classifier successfully maintained it below the target threshold.

Comparison of Type I and Type II error rates on the Neuroblastoma dataset.

As shown in the table above, the PSN² method achieved a Type I error of 0.038, staying well within a typical $\alpha = 0.05$ constraint. In contrast, SVM and Penalized Logistic Regression exhibited Type I error rates exceeding 50%, demonstrating their inability to handle asymmetric priorities in high-dimensional settings.

Discussion and Conclusion

The core theoretical contribution of this work is the derivation of NP oracle inequalities, proving that the classifier's performance converges to the "oracle" (the best possible theoretical classifier) as sample size grows. The authors also introduced a refined "detection condition," emphasizing that successful NP classification requires sufficient data near the decision boundary to accurately set the threshold.

While the Naive Bayes assumption of feature independence is a common and effective heuristic in high dimensions, it may be limited in cases of complex feature correlations. Future work may involve extending this framework to models that account for feature interactions or incorporating non-probabilistic methods like $k$-Nearest Neighbors ($k$-NN) into the constrained optimization framework. Ultimately, this research provides a vital mathematical safety net for practitioners who must prioritize specific error types in data-rich environments.

Summary updated

Abstract

Most existing binary classification methods target on the optimization of the overall classification risk and may fail to serve some real-world applications such as cancer diagnosis, where users are more concerned with the risk of misclassifying one specific class than the other. Neyman-Pearson (NP) paradigm was introduced in this context as a novel statistical framework for handling asymmetric type I/II error priorities. It seeks classifiers with a minimal type II error and a constrained type I error under a user specified level. This article is the first attempt to construct classifiers with guaranteed theoretical performance under the NP paradigm in high-dimensional settings. Based on the fundamental Neyman-Pearson Lemma, we used a plug-in approach to construct NP-type classifiers for Naive Bayes models. The proposed classifiers satisfy the NP oracle inequalities, which are natural NP paradigm counterparts of the oracle inequalities in classical binary classification. Besides their desirable theoretical properties, we also demonstrated their numerical advantages in prioritized error control via both simulation and real data studies.
BibTeX
@misc{zhao2015neyman,
  author = {Anqi Zhao and Yang Feng and Li-e Wang and Xin Tong},
  title = {{Neyman-Pearson Classification under High-Dimensional Settings}},
  year = {2015},
  eprint = {1508.03106},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1508.03106},
}
Figure