Multi-category Angle-based Classifier Refit

Guo Xian Yau, Chong ZhangarXiv 2016 · DOI · arXiv

TL;DR

This paper tackles the challenge of accurate class probability estimation in high-dimensional, low-sample-size multicategory classification problems. The authors propose a novel "refit" strategy for angle-based classifiers that significantly improves probability estimation accuracy without sacrificing prediction performance, offering a competitive solution with minimal computational overhead.

What Problem Does This Paper Address?

In statistical learning, classification aims to assign data points to categories. While achieving high prediction accuracy is crucial, accurately estimating the probability of a data point belonging to each class is also vital for applications like risk assessment or treatment selection. Traditional methods work well with abundant data, but high-dimensional, low-sample-size (HDLSS) scenarios, common in fields like genomics, pose challenges. Margin-based classifiers, popular for HDLSS problems, often employ heavy regularization to prevent overfitting and ensure good prediction accuracy. However, this heavy regularization can lead to a "shrinkage effect," where the estimated classification functions have smaller norms than they should. This shrinkage, in turn, biases the estimated class probabilities, causing them to cluster around a uniform distribution (1/k for k classes). While remedies exist for binary classification, this problem remains largely unaddressed for multicategory settings. This paper aims to fill this gap by providing theoretical insights into why regularization causes this bias in multicategory problems and proposing a practical solution.

Methods

The core of this paper's contribution lies in a new "refit" strategy for multicategory angle-based classifiers. Angle-based classifiers, introduced by Zhang and Liu (2014), offer an efficient alternative to traditional multicategory methods by using k-1 functions instead of k, avoiding the sum-to-zero constraint.

The proposed refit method involves two main stages:

  1. Initial Classification: A standard angle-based classifier is trained on the original data with appropriate regularization (tuning parameter $\lambda$). This step yields a set of fitted classification functions, $f$.
  2. Refit Stage: A second classifier is trained using the outputs of the first stage as new predictors. Specifically, for each data point $x_i$, the vector of fitted functions $f(x_i)$ (which has $k-1$ elements) is used as the input for the second stage. Crucially, this second stage is trained without any penalty terms. The rationale is that by this point, the data is effectively "transformed" into a space where overfitting is less of a concern, and the goal is to "restore" the norm of the classification functions, thereby correcting the bias introduced by the initial regularization.

The paper also provides theoretical analysis to explain why heavy regularization leads to shrinkage and biased probability estimation in multicategory settings, particularly for linear learning with L1 and L2 penalties.

Datasets

The paper evaluates its proposed method using:

  • Simulated Data: Two simulated examples are generated to test the method's performance in high-dimensional settings. These examples involve varying numbers of classes and predictors, with controlled noise levels.
  • Real Data: Two benchmark datasets are used for real-world evaluation:
  • Wine dataset: From the UCI Machine Learning Repository, featuring 3 categories of wine with 13 variables.
  • Phishing websites dataset: Also from the UCI Machine Learning Repository, with 30 attributes and 2456 observations.

Key Insights and Ideas

  • The "Shrinkage Effect" in Multicategory Problems: The paper theoretically demonstrates that heavy regularization, necessary for good prediction in HDLSS scenarios, causes the fitted classification functions to have smaller norms. This shrinkage directly leads to biased probability estimates, pushing them towards a uniform distribution (1/k).
  • Angle-Based Classifiers as a Foundation: The authors leverage the efficiency of angle-based classifiers, which use fewer functions and avoid sum-to-zero constraints, making them well-suited for high-dimensional problems.
  • The Power of a Two-Stage Refit: The core innovation is the two-stage refit. By using the outputs of the initial classifier as inputs for a second, unregularized classifier, the method effectively "restores" the norm of the classification functions, correcting the probability estimation bias without harming prediction accuracy.
  • Information Preservation: Theorem 2 suggests that the $k-1$ dimensional output of the angle-based classifier contains sufficient information about class conditional probabilities, making it a suitable input for the refit stage.

Key Results

  • Improved Probability Estimation: Numerical results consistently show that the proposed refit method significantly improves probability estimation accuracy, as measured by Mean Absolute Difference (MAD) and Cross Entropy Error (CRE), compared to the original angle-based classifier.
  • Competitive Prediction Accuracy: The refit method achieves classification accuracy comparable to the original angle-based classifier, indicating no loss in predictive power.
  • Low Computational Cost: The refit stage adds only a small computational burden, making the overall approach efficient.
  • Theoretical Support: The paper provides theoretical insights into the shrinkage effect and its consequences, strengthening the justification for the proposed refit strategy.

Limitations and Future Work

  • Focus on Specific Regularization: While the paper theoretically analyzes L1 and L2 penalties in linear learning, it notes that similar shrinkage effects can occur with other regularization methods and nonlinear learning settings. Future work could explore the refit method's performance with a broader range of regularization techniques.
  • Generalizability of Refit: The paper proposes a specific refit strategy for angle-based classifiers. Further research could investigate if similar refit strategies can be applied to other multicategory margin-based classifiers that suffer from similar probability estimation biases.
  • Exploration of Other Loss Functions: The paper demonstrates the method's effectiveness with logistic regression deviance loss and a soft large-margin unified machine loss. While it mentions generalizability to other differentiable convex loss functions, empirical validation with a wider array of loss functions could be beneficial.

Summary updated

Abstract

Classification is an important statistical learning tool. In real application, besides high prediction accuracy, it is often desirable to estimate class conditional probabilities for new observations. For traditional problems where the number of observations is large, there exist many well developed approaches. Recently, high dimensional low sample size problems are becoming increasingly popular. Margin-based classifiers, such as logistic regression, are well established methods in the literature. On the other hand, in terms of probability estimation, it is known that for binary classifiers, the commonly used methods tend to under-estimate the norm of the classification function. This can lead to biased probability estimation. Remedy approaches have been proposed in the literature. However, for the simultaneous multicategory classification framework, much less work has been done. We fill the gap in this paper. In particular, we give theoretical insights on why heavy regularization terms are often needed in high dimensional applications, and how this can lead to bias in probability estimation. To overcome this difficulty, we propose a new refit strategy for multicategory angle-based classifiers. Our new method only adds a small computation cost to the problem, and is able to attain prediction accuracy that is as good as the regular margin-based classifiers. On the other hand, the improvement of probability estimation can be very significant. Numerical results suggest that the new refit approach is highly competitive.
BibTeX
@misc{yau2016multi,
  author = {Guo Xian Yau and Chong Zhang},
  title = {{Multi-category Angle-based Classifier Refit}},
  year = {2016},
  eprint = {1607.05709},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1607.05709},
}
Figure