PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-class Classification without Multi-class Labels

Yen-Chang Hsu, Zhaoyang Lv, Joel Schlosser, Phillip Odom, Zsolt Kira

arXiv:1901.00544v1cs.LGcs.AIcs.CVstat.ML

TL;DR

The paper addresses multi-class classification when class-specific labels are expensive or unavailable. It learns a multi-class classifier through a binary pairwise-similarity task, formalized probabilistically and optimized with a simple likelihood-based loss. Across supervised, unsupervised cross-task, and semi-supervised settings, the method achieves comparable or improved results over state of the art, while class-to-output semantic mapping remains a limitation.

  • Problem

    Class-specific labels are costly, require prior knowledge of all classes, and limit supervision, especially when classes are unknown or ambiguous.

  • Method

    Meta classification learns a multi-class classifier as a submodule of a training-time binary classifier supervised by pairwise similarities.

  • Results

    Across supervised, unsupervised cross-task, and semi-supervised learning, the framework achieves comparable or improved results over state of the art, especially in unsupervised cross-task learning.

  • Takeaways & Limitations

    Pairwise similarity can serve as weak supervision for learning multi-class classifiers without class-specific labels across three learning paradigms.

  • Takeaways & Limitations

    Without class labels, the mapping between output nodes and semantic classes is not identifiable; labeled data are needed to assign meanings for quantitative evaluation.

Abstract

from arXiv · show

This work presents a new strategy for multi-class classification that requires no class-specific labels, but instead leverages pairwise similarity between examples, which is a weaker form of annotation. The proposed method, meta classification learning, optimizes a binary classifier for pairwise similarity prediction and through this process learns a multi-class classifier as a submodule. We formulate this approach, present a probabilistic graphical model for it, and derive a surprisingly simple loss function that can be used to learn neural network-based models. We then demonstrate that this same framework generalizes to the supervised, unsupervised cross-task, and semi-supervised settings. Our method is evaluated against state of the art in all three learning paradigms and shows a superior or comparable accuracy, providing evidence that learning multi-class classification without multi-class labels is a viable learning option.

1 INTRODUCTION

The paper reframes multi-class classification as a binary pairwise-similarity task, reducing dependence on expensive class-specific labels. Its meta classification framework learns the multi-class classifier as a submodule and supports supervised, cross-task unsupervised, and semi-supervised settings.

  • Motivation: Class-specific labels are expensive, require prior knowledge of all classes, and restrict the available forms of supervision.Deep neural networks typically learn P(y|x), but this requires substantial class-specific annotation.
  • Motivation: Existing one-vs-all and one-vs-one reductions still require class labels to construct their binary-classifier inputs.Their binary classifiers serve as submodules of a multi-class classifier, but they do not relax the labeling requirements.
  • Proposed approach: Meta classification reverses the encapsulation order: one binary classifier uses paired inputs and pairwise similarity, while the multi-class classifier becomes its submodule.The binary task is used during training and is not involved in inference.
  • Proposed approach: The method learns a neural-network multi-class classifier from pairwise information without requiring class labels during training.The multi-class classifier uses softmax outputs, while pairwise similarity supplies the supervision.
  • Scope and results: The same framework is evaluated in supervised, unsupervised cross-task, and semi-supervised learning, achieving superior or comparable accuracy across the three domains.The authors report flexibility for unknown types and numbers of classes.

2 RELATED WORK

The related work situates meta classification among problem-reduction, constrained-clustering, and semi-supervised approaches using pairwise or consistency-based supervision. Unlike conventional binary reductions, the proposed framework makes the multi-class classifier the submodule of a single training-time binary task.

  • Supervised learning and problem reduction: Traditional one-vs-all and one-vs-one methods reduce multi-class classification to multiple binary problems and underpin widely used algorithms.Examples include support vector machines, AdaBoost, and decision trees.
  • Relation to prior work: Meta classification differs from earlier reductions by reversing task encapsulation so that a multi-class classifier is embedded within a binary classifier.This binary classifier is used to train the multi-class component rather than forming a collection of inference-time submodules.
  • Unsupervised cross-task transfer learning: Unsupervised cross-task transfer methods move pairwise similarity to an unlabeled dataset and use constrained clustering to discover unseen classes.These approaches relate pairwise supervision to constrained clustering and metric-learning methods.
  • Semi-supervised learning: Semi-supervised methods combine unlabeled data with consistency regularization, pseudo-labeling, or weak supervision from similar pairs.The paper augments its scheme with Pseudo-Labeling for semi-supervised learning.

3 META CLASSIFICATION LEARNING

Meta classification models latent class labels through observed pairwise similarities in a probabilistic graphical model. The resulting Meta Classification Likelihood uses a simple binary cross-entropy objective over similarities predicted from inner products of categorical classifier outputs.

  • Probabilistic formulation: The graphical model treats class labels Y as latent and pairwise similarities S as observed, with classifier outputs f(x_i; θ)=P(Y_i|x_i; θ).Each Y_i is a categorical class label, each S_ij is binary, and θ denotes neural-network parameters.
  • Probabilistic formulation: The joint likelihood factors as P(X,Y,S;θ)=P(S|Y)P(Y|X;θ)P(X).The factorization links pairwise similarity to class labels and classifier predictions.
  • Likelihood approximation: Because marginalizing the unknown labels creates dependencies among similarities, the method imposes additional conditional independences to obtain an efficient approximation.The approximation treats each pairwise similarity as conditionally independent of the others given its two inputs.
  • Loss construction: The predicted similarity is the inner product f(x_i;θ)^T f(x_j;θ) between two categorical output distributions.This quantity is inserted into the likelihood-derived objective as the predicted probability that the examples share a class.
  • Loss construction: The resulting Meta Classification Likelihood has the form of a binary cross-entropy loss and optimizes only the neural-network classifier because the binary wrapper has no learnable parameters.For similar pairs, the outputs are driven toward the same sharp class; for dissimilar pairs, their distributions are pushed toward minimal overlap.

4 LEARNING PARADIGMS

The framework uses pairwise similarity as supervision across supervised, cross-task transfer, and semi-supervised learning paradigms. Each paradigm obtains similarity labels differently, including direct collection, transfer-based prediction, and pseudo-similarity construction.

  • Learning paradigms: MCL uses pairwise labeling S, a weaker supervision signal that supports supervised, cross-task transfer, and semi-supervised learning.The collection method determines the learning paradigm.
  • Supervised learning: In supervised learning, similarity labels indicate whether two examples belong to the same class and can be collected directly or converted from class labels.The experiments convert existing class labels using s_ij = 1 for same-class pairs and 0 otherwise.
  • Supervised learning: Pairwise information can also come from natural relationships such as spatial or temporal proximity, social-network edges, and citation links.These cues provide potential sources of similarity supervision beyond explicit class labels.
  • Unsupervised cross-task transfer: For unsupervised cross-task transfer, an SPN learned on labeled auxiliary data predicts same-class probabilities for an unlabeled target dataset.The predicted similarities are then used to discover categories in the target domain.
  • Semi-supervised learning: Pseudo-MCL constructs semi-supervised pseudo-similarity by thresholding predicted pairwise probabilities at 0.5 and can combine it with augmentation-based similarity.Its objective sums multi-class cross-entropy with Pseudo-MCL, allowing the supervised component to determine output-node/class mapping.

5 EXPERIMENTS

The experiments evaluate MCL against class-label and pairwise-similarity baselines across supervised, unsupervised cross-task, and semi-supervised settings. MCL matches CE in supervised classification, outperforms competing methods in cross-task transfer, and is on-par with VAT in semi-supervised learning.

  • 5.2.1 QUANTITATIVE ANALYSIS: MCL achieves similar classification performance to cross-entropy across network depths and MNIST, CIFAR10, and CIFAR100 while using only binarized similarity.KCL degrades with deeper networks or more difficult datasets, whereas MCL maintains comparable performance to CE.
  • 5.2.1 QUANTITATIVE ANALYSIS: KCL’s error rate drops from 72.2% to 10.4% with a longer learning schedule and larger learning rate for VGG11, but only from 81.1% to 76.8% for VGG16.Pre-training with 4k CE labels also brings KCL close to CE, indicating sensitivity to optimization and initialization.
  • 5.3 UNSUPERVISED CROSS-TASK TRANSFER LEARNING: The unsupervised transfer experiments test both known-class settings and unknown-class settings using a fixed K=100, with Omniglot averaging results across 20 alphabets.The evaluation compares accuracy and normalized mutual information under known and unknown numbers of output classes.
  • 5.3 UNSUPERVISED CROSS-TASK TRANSFER LEARNING: MCL shows a clear advantage over other methods in unsupervised cross-task transfer, with a larger gap over KCL when the number of classes is unknown.MCL also estimates the number of classes better than KCL; the authors attribute part of the advantage to avoiding KCL’s heuristic margin threshold.

6 CONCLUSION

The paper presents meta classification learning as a binary-decision strategy for learning multi-class classifiers from pairwise similarity rather than class-specific labels. Across supervised, unsupervised cross-task, and semi-supervised settings, it achieves comparable or improved results, especially in unsupervised transfer.

  • 6 CONCLUSION: MCL formulates multi-class classification through a binary decision problem, using a probabilistic graphical model and a simple likelihood objective optimized with neural networks.The framework makes the multi-class classifier a submodule of the binary classifier.
  • 6 CONCLUSION: The framework supports supervised learning, unsupervised cross-task transfer learning, and semi-supervised learning with pairwise similarity as weak supervision.The paper reports comparable or improved results over the state of the art, especially for unsupervised cross-task transfer.
  • 6 CONCLUSION: Using pairwise similarity relaxes the requirement for class-specific labeling and motivates further approaches for learning with fewer labeled data.The authors identify domain adaptation and few-shot learning as potential application areas.

A LOSS LANDSCAPE VISUALIZATION

The paper visualizes CE, MCL, and KCL loss landscapes using random and mutual projections to compare local geometry around learned solutions. MCL’s landscape is qualitatively closer to CE’s and has a wider concave region than KCL’s.

  • Visualization method: Loss surfaces are visualized by projecting model parameters onto two directions and plotting loss values over the resulting 2D grid.The projection coordinates are α and β, and the loss values form the vertical surface; CE uses a logarithmic vertical axis.
  • Visualization method: Filter-wise normalization makes random-projection landscape flatness comparable across networks and loss functions despite scale invariance.Batch normalization can make filter norms irrelevant, motivating normalization of the two random projections.
  • Projection strategies: The mutual projection uses solutions from different loss functions as the projection directions around one selected solution.The three objectives are CE, MCL, and KCL, each capable of solving the same multi-class classification problem.
  • Results: In random projection, MCL and KCL solutions are surrounded by high-loss plateaus, but MCL has a wider concave region.The same wide concavity appears for MCL in mutual projection.
  • Results: Mutual projection shows MCL’s geometry is similar to CE’s, whereas KCL has a sharp low-loss region only around its solutions.The authors suggest this geometry may explain MCL’s convergence to a good local minimum and KCL’s need for prolonged training.

B KCL VERSUS MCL

KCL and MCL both learn from pairwise similarity without requiring the true number of classes as the number of output nodes. They differ fundamentally in formulation: KCL uses KL-divergence as a metric, whereas MCL arises from meta classification.

  • KCL formulation: KCL measures pairwise distance between neural-network output distributions using KL-divergence and applies contrastive costs to similar and dissimilar pairs.Similar pairs use KL-based cost, while dissimilar pairs use a hinge loss with margin σ.
  • Comparison: KCL and MCL both use pairwise similarity and require no fixed relationship between output-node count K and the true class count C.Both criteria can be used in neural-network training by replacing the learning criterion.
  • Comparison: KCL is inspired by metric learning, while MCL is inspired by meta classification.Their similar usage therefore masks a fundamental difference in formulation.
  • Additional evaluation: Table 5 estimates character counts across 20 Omnigloteval datasets when C is unknown.Bold values indicate prediction error smaller than or equal to 3, and NDC denotes the number of dominant clusters.

C EXPERIMENTAL SETTING

The semi-supervised objectives combine supervised and unsupervised terms, while the experimental protocol assigns their weights without hyperparameter-tuning budget. VAT’s extra parameter uses values from its original paper.

  • Objective: All semi-supervised objectives are weighted sums of a supervised loss Lsup and an unsupervised regularization loss Lreg.The supervised term uses labeled data, while the regularization term uses labeled and unlabeled data.
  • Hyperparameter policy: The protocol sets α and β from natural data statistics, specifically the ratio of data amounts seen by Lsup and Lreg.This avoids exhaustive grid search and cross-validation, which may be impractical with few labeled examples.
  • Hyperparameter policy: The weighting coefficients are defined from labeled-data size |DL| and total-data size |D|.The supplied formulation gives α and β as proportions based on |DL| and |D|+|DL|.
  • Comparison protocol: VAT uses dataset-specific values selected in its original paper for its additional hyperparameter ϵ.This preserves the stated zero-tuning-budget comparison for the other methods.

D.1 SIMPLIFIED LIKELIHOOD

The simplified likelihood relies on an independence assumption, but with ground-truth constraints its global solution matches the original likelihood’s solution. Practical concerns remain for local minima and noisy constraints, although experiments provide empirical support across settings.

  • Likelihood simplification: The binary cross-entropy form is obtained by simplifying the original likelihood under an additional independence assumption.This raises whether the resulting equation is over-simplified.
  • Supervised case: With ground-truth supervised constraints, the simplified likelihood and original likelihood share the same global solution.A misclassified instance violates pairwise constraints in both likelihoods and therefore cannot remain optimal.
  • Practical issues: Stochastic optimization may find local minima, but the loss-landscape visualization provides evidence that MCL reduces poor local minima relative to KCL.This theoretical issue is not resolved generally for complex models.
  • Practical issues: Noisy constraints can favor jointly optimizing many or all constraints, at the expense of tractability.The paper reports noisy similarity predictions in cross-task transfer, including ImageNet pairwise precision and recall values.
  • Empirical support: Experiments on five image datasets and three application scenarios empirically support that the proposed likelihood can overcome these two practical issues.The authors identify joint constraint optimization as an interesting direction for future work.
Loading 1901.00544v1…