Ordered Classes and Incomplete Examples in Classification

Mark MathiesonNeurIPS 1996

TL;DR

This paper introduces Non-linear Ordinal Logistic Regression (NOLR), a neural network-based approach designed for classification tasks where categories have a natural order (e.g., "poor," "fair," "good"). By combining this model with a simulation-based Gibbs sampling strategy for missing data, the author demonstrates a significant improvement in predicting recovery outcomes for severe head injury patients compared to standard imputation methods.

What Problem Does This Paper Address?

In many real-world classification problems, two major hurdles exist:

  1. Ordered Classes: Standard classifiers treat all errors equally. However, if you are predicting medical recovery, misclassifying "full recovery" as "slight disability" is a much smaller error than misclassifying it as "death." Standard "nominal" models (like softmax) ignore this inherent hierarchy.
  2. Incomplete Data: Real datasets are messy. In the head injury dataset used here, some variables are missing in up to 78% of cases. Common fixes—like deleting incomplete rows or filling in the average (median imputation)—often lead to biased models or overconfident, incorrect predictions.

The paper seeks to create a flexible, non-linear model that respects class ordering while robustly handling missing information.

Methods

The author proposes two main technical contributions to address these challenges:

  • Non-linear Ordinal Logistic Regression (NOLR): The model starts with Ordinal Logistic Regression (OLR), which uses "cut-points" on a latent scale to separate classes.

    Probability curves for ordered classes

    To add flexibility, the author replaces the standard linear function with a feed-forward neural network (including skip-layer connections). This allows the model to capture complex, non-linear relationships between features while still enforcing the ordinal structure of the output. The model is regularized using weight decay and priors on the cut-points to prevent overfitting.

  • Handling Missing Data via Gibbs Sampling: Instead of picking one value for a missing entry, the author uses Gibbs sampling to generate multiple "completions" of the dataset. The final classification is a predictive average: the model makes a prediction for each completed version of the data, and these probabilities are averaged. This accounts for the uncertainty inherent in missing values.

Datasets

The paper utilizes a classic medical dataset from Jennett et al. (1979) regarding patients with severe head injuries.

  • Features: Includes age, eye/motor/verbal responses (EMV score), neurological changes, and pupil reaction.
  • Target: Recovery after six months based on the Glasgow Outcome Scale (3 ordered classes:
  • dead/vegetative, 2. severe disability, 3. moderate/good recovery).
  • Missingness: The training set contains only 40 complete examples and 206 incomplete ones. Some variables, like "neurological change," are missing in 78% of the records.

Key Insights and Ideas

  • Loss Matters: For ordered classes, the Bayes decision rule should use a loss function like $L(j, k) = |j - k|$. This penalizes "far away" misclassifications more heavily than "nearby" ones.
  • Non-linearity is Essential: While linear ordinal models exist, the author shows that decision boundaries in medical prognosis are rarely simple hyperplanes. The neural network component allows for "curved" boundaries that better fit patient data.
  • Don't Just Fill the Blanks: Median imputation (filling in the middle value) can make a model "confident" about a wrong answer. By averaging over many possible imputations (the predictive approach), the model becomes more cautious and accurate in the face of uncertainty.
Ternary plot of predicted outcomes
  • The "Aha" Moment in Visualization: The ternary plot visualization above demonstrates that for a single patient, different valid imputations of their missing data can lead to very different predicted outcomes. Averaging these provides a much more honest assessment of the patient's likely recovery than picking a single "best guess" for the missing data.

Key Results

The performance was measured using "Test Set Loss" (where lower is better):

  • Baseline (40 complete examples only): Loss of 132.
  • Median Imputation (using all 246 examples): Loss of 149 (Actually performed worse than ignoring incomplete data because it introduced bias).
  • Gibbs Sampling + NOLR: Loss of 118.
  • Pooling completions: Combining multiple imputations into a single large training set further reduced the loss to 117.

In short, the proposed method provided a ~11% improvement over the baseline and a massive improvement over the standard "quick fix" of median imputation.

Limitations and Future Work

  • Missing at Random (MAR) Assumption: The methods assume that the reason data is missing is independent of the missing values themselves (given the observed data). The author admits this is "rarely true" in practice but argues it is less damaging than ad hoc approaches.
  • Computational Complexity: Gibbs sampling and training neural networks on multiple completions of a dataset is significantly more computationally expensive than standard methods.
  • Model Constraints: While the neural network is a "universal approximator," the specific ordinal structure (NOLR) means it cannot approximate all probability densities as well as a standard "softmax" model might, though it is more interpretable for ordered tasks.

Summary updated

BibTeX
@inproceedings{mathieson1996ordered,
  author = {Mark Mathieson},
  title = {{Ordered Classes and Incomplete Examples in Classification}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1996},
}
Figure