PaperlayerView exact revision on arXiv

Source-linked AI summary

Least Ambiguous Set-Valued Classifiers with Bounded Error Levels

Mauricio Sadinle, Jing Lei, Larry Wasserman

arXiv:1609.00451v2stat.MEcs.LGstat.ML

TL;DR

Ambiguous observations are difficult to label with single-label classifiers, motivating outputs that contain plausible labels while controlling coverage and ambiguity. The paper derives multiclass LABEL classifiers from conditional-probability level sets, develops estimators with asymptotic and finite-sample properties, and supplies remedies for empty predictions. LABEL classification provides more informative outcomes by identifying plausible classes for each instance rather than using a generic reject option.

  • Problem

    Ambiguous observations are difficult to label correctly with traditional single-label classifiers, motivating set-valued outputs for more appropriate treatment.

  • Method

    The paper derives multiclass LABEL classifiers as conditional-probability level sets, then estimates them using plug-in classifiers and conformal inference while providing remedies for empty outputs.

  • Results

    LABEL classifiers provide more informative outcomes than a generic reject option by identifying plausible classes for each instance.

  • Takeaways & Limitations

    Set-valued outputs represent plausible classes for instances that truly belong to one of K mutually exclusive classes.

  • Takeaways & Limitations

    LABEL classifiers can sometimes output empty prediction sets, for which the paper provides different remedies.

Abstract

from arXiv · show

In most classification tasks there are observations that are ambiguous and therefore difficult to correctly label. Set-valued classifiers output sets of plausible labels rather than a single label, thereby giving a more appropriate and informative treatment to the labeling of ambiguous instances. We introduce a framework for multiclass set-valued classification, where the classifiers guarantee user-defined levels of coverage or confidence (the probability that the true label is contained in the set) while minimizing the ambiguity (the expected size of the output). We first derive oracle classifiers assuming the true distribution to be known. We show that the oracle classifiers are obtained from level sets of the functions that define the conditional probability of each class. Then we develop estimators with good asymptotic and finite sample properties. The proposed estimators build on existing single-label classifiers. The optimal classifier can sometimes output the empty set, but we provide two solutions to fix this issue that are suitable for various practical needs.

1 Introduction

The paper develops multiclass set-valued classifiers for ambiguous observations, replacing forced single labels with plausible label sets while controlling coverage and minimizing ambiguity. It derives optimal LABEL classifiers, develops estimators, and addresses their possible empty predictions.

  • Motivation: Set-valued classifiers assign plausible label sets to observations that are difficult to label correctly, while each sample still belongs to one mutually exclusive class.This distinguishes the framework from multi-label classification, where multiple characteristics may genuinely co-occur.
  • Objective: The framework guarantees user-defined coverage or confidence levels while minimizing ambiguity, defined as the expected number of labels in the output.Coverage is the probability that the true label is contained in the predicted set.
  • Optimal classifiers: LABEL classifiers are optimal set-valued classifiers characterized by level sets of the conditional class-probability functions p(y|x).Their outputs have the form {y : p(y|x) ≥ t_y} for class-specific thresholds.
  • Empty predictions: Optimal classifiers may output the empty set, especially when required coverage is low, because minimizing ambiguity can favor empty predictions.The paper provides alternative remedies, including solutions for handling null regions and ambiguous instances.
  • Estimation: The proposed estimators plug estimates of p(y|x) into the optimal classifiers and use split-conformal inference to obtain finite-sample, distribution-free coverage under essentially no conditions.The analyses also extend to settings where the number of classes grows with sample size, provided it does not increase too quickly.
  • Contributions: The framework extends prior binary-class ideas to multiclass classification and provides alternative solutions when optimization constraints yield multiple or uninformative treatments of ambiguous observations.The paper reports more informative outcomes than a generic reject option by identifying plausible classes for each instance.

2 Optimal procedures

The paper derives optimal set-valued classifiers under total or class-specific coverage constraints, using level sets of conditional class probabilities to minimize ambiguity or incorrect label assignments. Class-specific procedures can produce empty predictions, motivating principled methods for covering uncovered regions.

  • Setup: The analysis assumes a known joint distribution P and represents each classifier through class-indexed regions C_y, with H(x)={y:x∈C_y}.
  • Total coverage: Under total error control, the optimal classifier is characterized by a threshold level set of p(y|x), assuming no point mass at the relevant quantile.
  • Total coverage: Total-error control can perform poorly for minority classes when one class is much more prevalent, yielding low probability of correctly labeling their observations.
  • Class-specific coverage: Class-specific procedures choose C_y={x:p(y|x)≥t_y} so that P(C_y|Y=y)=1−α_y for every class.
  • Class-specific coverage: These classifiers simultaneously minimize incorrect label-assignment probabilities and therefore minimize expected ambiguity among classifiers satisfying the class-specific constraints.
  • Null regions: Null regions arise when the output set is empty; the paper proposes principled solutions because initial classification regions may be disjoint and fail to cover the feature space.
  • Class-specific coverage: In Example 7, class-specific error levels α_y=0.2 produce a null region, α_y=0.1 produce a smaller null region plus ambiguity, and α_y=0.05 remove the null region.

3 Dealing with null regions

Null regions arise when an optimal set-valued classifier assigns no labels to some feature-space points. The paper proposes baseline filling and accretive completion to eliminate them, balancing coverage, ambiguity, and ambiguity detection.

  • Null regions: The null region is the set of feature-space points receiving the empty prediction, including cases whose class probabilities are all below their thresholds.Such regions can contain genuinely ambiguous observations where several class probabilities are similar.
  • Approach I: Filling with a baseline classifier: Filling with a baseline classifier assigns a single baseline label throughout the null region, offering a fast solution when nominal error levels are the main concern.The approach may fail to capture some ambiguous areas of feature space.
  • Approach II: Accretive completion: Accretive completion lowers class thresholds one at a time, selecting increments that minimize added ambiguity until the null region disappears.The procedure grows the optimal classifier while preserving the desired coverage constraints as closely as possible.
  • Approach II: Accretive completion: Accretive completion can identify ambiguous areas inside the null region, motivating its use when thorough ambiguity detection is important.The paper recommends this approach when detecting ambiguous regions is a primary concern.
  • Optimality and limitations: The completed classifier is close to optimal when the null region is small, while arbitrary filling can produce solutions that are inappropriate for ambiguity handling.The paper notes that the underlying optimization problem may have multiple solutions, not all of which are meaningful for detecting ambiguity.
  • Binary classification: In the binary case, baseline filling is sufficient: using the Bayes classifier yields the minimum-ambiguity solution, so accretive completion is unnecessary.If no null region exists, the original classifier already achieves the optimal value.

4 Estimation and finite sample adjustment

The paper estimates optimal set-valued classifiers by plugging conventional conditional-probability estimators into level-set rules. Split-conformal inference then provides distribution-free finite-sample coverage guarantees.

  • Asymptotic properties: Under standard regularity conditions, plug-in procedures asymptotically mimic the optimal classifiers with convergence rates.The theory assumes estimator accuracy and controlled behavior of the conditional-probability distribution near the cutoff.
  • Finite-sample adjustment: Split-conformal inference combines the estimated probabilities with a held-out sample to achieve distribution-free finite-sample coverage.The data are split: one half estimates p(y|x), while the other calibrates the coverage threshold.
  • Estimation: Plug-in estimators use conventional methods to estimate p(y|x), including kNN, local polynomial, kernel, and logistic regression models.The estimated conditional probabilities define the classifier's level sets and thresholds.
  • Level-set construction: Estimated level sets choose cutoffs according to target total or class-specific coverage requirements.Total coverage uses a common threshold, whereas class-specific coverage uses separate thresholds t_y.
  • Total coverage: For total coverage, the conformal classifier satisfies P*(Y ∈ bH(X)) ≥ 1−α for any distribution and sample size n.The guarantee follows from the conformal rank construction.
  • Class-specific coverage: For class-specific coverage, separate conformal calibration by class gives P*(Y ∈ bH(X)|Y = y) ≥ 1−α_y for every class.The second half of the data is partitioned into groups according to observed class labels.

5 Examples and Comparisons

Experiments illustrate LABEL classifiers across synthetic, Iris, Abalone, image, and zip-code data, using several base estimators and comparisons with reject-option classifiers. LABEL outputs more specific plausible-label sets and can control class-specific coverage.

  • Experimental setup: LABEL classifiers use kernel regression, kNN, multinomial logistic regression, and sparse multinomial logistic regression across the examples.Large-sample examples use split conformal, while the small-sample Iris example studies in-sample behavior without splitting.
  • Synthetic example: At 98% total coverage in the synthetic example, LABEL kernel has ambiguity 1.083, compared with 1.164 for the comparable reject-option classifier.The LABEL regions indicate which subsets of labels are plausible in different feature-space areas.
  • Coverage control: Total-coverage control can produce class-specific imbalance: one example reports coverages of 99.7%, 97.2%, and 97.2% for classes 1, 2, and 3.The paper uses this example to motivate direct control of each class's coverage.
  • Comparison with reject option: LABEL is more specific than reject-option classification because it represents different plausible label subsets rather than one general region for all labels.The reject-option classifier uses single-label regions plus a general rejection area.
  • Iris data: In the Iris example, LABEL assigns two labels to one boundary observation, whereas no comparable reject-option classifier identifies any sample as ambiguous.The ambiguous point lies between classes 2 and 3.
  • Abalone data: For Abalone data, LABEL identifies ambiguity between young and middle, and middle and old abalones, but not between young and old.The final classifier's test-sample ambiguity is reported after this structured ambiguity pattern.
  • Zip code data: On zip-code data, the final LABEL classifier achieves test-sample coverage of 0.98 and test-sample ambiguity of 1.27.Accretive completion produces additional ambiguous images, many of which are also ambiguous to human observers.

6 Discussion

LABEL classifiers provide least-ambiguous, informative outputs while meeting specified coverage requirements, but may produce empty sets and leave several extensions open.

  • LABEL classifiers are least ambiguous among set-valued classifiers that guarantee specified class-specific confidence levels.
  • Compared with traditional single-valued classifiers, LABEL provides a more informative and principled approach for ambiguous instances.
  • LABEL classification provides more informative outcomes than classification with reject option by reporting plausible class labels for each instance.
  • Users can control total or class-specific coverage requirements, whereas class-specific coverage cannot be controlled using classifiers with reject option.
  • LABEL classifiers can output empty prediction sets, for which the paper provides different remedies.
  • Open questions include adapting consistency results to accretive completion and handling many classes through structures such as trees.
  • The paper also suggests searching for new classes among clusters located in regions of high ambiguity or null predictions.

Supplementary Materials

The supplementary materials provide proofs, reproducibility code, and additional simulation studies supporting the paper’s theoretical and empirical results.

  • The online supplementary materials contain proofs of theoretical results, R code reproducing Section 5 examples, and additional simulation studies.

A Proofs

The proofs characterize optimal decision regions, establish their statistical properties, and connect the theoretical results to estimated classifiers.

  • Optimal class decision regions can be based on likelihood-ratio level sets, with thresholds chosen to satisfy the required condition.
  • The likelihood-ratio construction corresponds to a Neyman–Pearson rejection region for testing Y = y against Y ≠ y.
  • By the Neyman–Pearson lemma, the induced classifier minimizes the conditional probability of excluding class y when Y ≠ y.
  • The theoretical results also apply to split-conformal classifiers and rely on a monotonic relationship between logits and likelihood ratios.
  • The proofs establish finite-sample bounds using empirical distributions of estimated conditional probabilities and standard empirical-process arguments.
  • For total coverage, all classes use a common threshold determined by an ideal cutoff for the conditional probability.
  • The proof connects estimated and ideal decision regions through bounds on threshold and symmetric-difference errors.

B.1 Univariate Scenarios

In univariate simulations, LABEL classifiers consistently reduce ambiguity relative to reject-option classifiers while identifying plausible labels and supporting coverage control.

  • Simulation setup: The study simulates three-class univariate normal scenarios with means −2, 0, and 2, using n = 4000 and total coverage 0.95.Results average ambiguity and class coverages over 1000 simulation replicates.
  • Ambiguity comparison: Across all three scenarios, LABEL has smaller average ambiguity than CWR, and it is smaller in all 1000 simulation replicates.
  • Ambiguity comparison: CWR assigns {1, 2, 3} to ambiguous points, whereas LABEL can assign {1, 2} or {2, 3} when only neighboring classes overlap.
  • Interpretation: LABEL is more informative because it identifies the plausible labels for each ambiguous instance instead of using a generic reject output.
  • Coverage control: Controlling total coverage can produce very uneven class coverage for both LABEL and CWR classifiers.
  • Coverage control: The framework supports class-specific coverage control, which cannot be done using CWRs.

B.2 Data-Based Multivariate Scenario

This multivariate simulation uses a five-class synthetic population based on Abalone data to compare LABEL classifiers with CWRs at approximately 0.95 total coverage. LABEL yields lower ambiguity, while CWRs provide larger and more balanced outputs in this scenario.

  • Experimental design: Multinomial logistic regression estimates p(y|x), while total classifier coverage is controlled at 0.95.For CWRs, the reject-option cost ρ is selected so total coverage is greater or equal to 0.95.
  • Ambiguity: LABEL ambiguity is smaller than CWR ambiguity in all simulation replicates.The comparison is presented in Figure 7, and smaller ambiguity means LABEL produces less extensive output sets.
  • Class coverage: LABEL classifiers tend to produce imbalanced class coverages because three classes have very small probabilities and two are close to a third class.Classes 1, 4, and 5 have small probabilities, while classes 4 and 5 are close to class 3.
  • Class coverage: CWRs produce higher and more balanced class coverages here because rejected instances receive all labels, but they cannot guarantee balanced coverage.LABEL classifiers can instead be used under class-specific coverage control.
Loading 1609.00451v2…