A Weakly Supervised Learning Approach based on Spectral Graph-Theoretic Grouping

Tameem Adel, Alexander Wong, Daniel W. StashukarXiv 2015 · OpenReview

Abstract

In this study, a spectral graph-theoretic grouping strategy for weakly supervised classification is introduced, where a limited number of labelled samples and a larger set of unlabelled samples are used to construct a larger annotated training set composed of strongly labelled and weakly labelled samples. The inherent relationship between the set of strongly labelled samples and the set of unlabelled samples is established via spectral grouping, with the unlabelled samples subsequently weakly annotated based on the strongly labelled samples within the associated spectral groups. A number of similarity graph models for spectral grouping, including two new similarity graph models introduced in this study, are explored to investigate their performance in the context of weakly supervised classification in handling different types of data. Experimental results using benchmark datasets as well as real EMG datasets demonstrate that the proposed approach to weakly supervised classification can provide noticeable improvements in classification performance, and that the proposed similarity graph models can lead to ultimate learning results that are either better than or on a par with existing similarity graph models in the context of spectral grouping for weakly supervised classification.

Introduction

In the ideal landscape of machine learning, every data point is accompanied by a precise, high-quality label. However, real-world applications—particularly in specialized fields like medicine—often face a significant labeling bottleneck. Manual annotation is frequently expensive, time-consuming, and prone to human error. This challenge is exemplified in Electromyography (EMG) signal analysis, which measures muscle activity. While a clinician can label an entire muscle as "myopathic" (diseased), that muscle consists of numerous "motor units," many of which may still function normally.

This scenario represents a classic Multiple Instance Learning (MIL) problem: we possess labels for "bags" (the muscle) but lack labels for the individual "instances" (the motor units). Standard supervised classifiers often fail here because they naively assume every instance within a positive bag shares the bag's label. This paper addresses this gap by introducing a spectral graph-theoretic grouping strategy designed to accurately "weakly annotate" individual instances, thereby constructing a more robust and representative training set.

Methodology: Spectral Graph-Theoretic Grouping

The proposed framework leverages spectral graph theory to identify natural clusters within data by treating data points as nodes in a similarity graph. The core innovation lies in the transition from rigid, absolute distance thresholds to probabilistic similarity models that better account for varying data densities.

New Similarity Graph Models

The researchers introduced two novel similarity graph models to improve the construction of these graphs:

  1. Probabilistic Threshold Graph: Unlike traditional models that use a hard cutoff to determine if points are neighbors, this model employs a relative threshold. It maintains strong connections while assigning weights to weaker ones based on a truncated Gaussian distribution.
  2. Probabilistic Criterion Graph: This model adopts a stochastic approach, where the inclusion of a neighbor in a group is determined by a probability derived from their similarity, rather than a fixed binary threshold.

The Role of Relative Normalization

Traditional methods like $\epsilon$-neighborhood or $k$-Nearest Neighbor ($k$-NN) rely on absolute values, which often fail when data density is non-uniform. The authors address this by using relative normalization. By calculating the importance of a distance relative to all other distances in the local set, the model learns the context of a data point’s neighborhood. This makes the grouping process significantly more robust to the "messy" distributions found in real-world datasets.

Experimental Validation

The approach was validated using both standard benchmarks and complex real-world datasets:

  • Benchmarks: The Abalone dataset (age prediction), Swiss Banknotes (counterfeit detection), and Image Segmentation (object recognition).
  • Real-World EMG: Four datasets involving Myopathic and Neurogenic disorders in the Upper and Lower Leg. These are particularly difficult because they lack "ground truth" labels for individual motor units, making them the ideal testbed for weakly supervised learning.

Key Insights and Results

The experimental results highlight the advantages of moving beyond naive supervised learning in the presence of weak labels:

  • Significant Accuracy Gains: In muscle classification tasks, the proposed weakly supervised approach achieved an accuracy of 95-96%, a substantial improvement over the ~81% achieved by the standard supervised baseline.
  • Superior Clustering Quality: Using the Davies-Bouldin index—a metric for cluster separation—the new probabilistic models consistently outperformed $k$-NN and $\epsilon$-neighborhood models, often by a factor of three or four.
  • Contextual Robustness: The results suggest that a "weakly supervised" classifier that intelligently guesses instance labels via graph theory is far more effective than a "fully supervised" one that relies on the flawed assumption that all instances in a positive bag are positive.
  • Benchmark Performance: On the Swiss Banknotes benchmark, the model achieved a perfect 100% F1 score, demonstrating its ability to handle both straightforward and highly complex classification tasks.

Conclusion and Future Work

This study demonstrates that spectral graph-theoretic grouping provides a powerful mechanism for bridging the label gap in weakly supervised learning. By utilizing relative normalization and probabilistic similarity models, the framework can accommodate varying data densities and provide more accurate instance-level annotations.

While the performance is superior, the authors note that selecting the optimal graph settings (such as "Min" vs "Max" symmetric transformations) currently requires cross-validation. Future research will focus on automating parameter selection for the threshold ($w$) and standard deviation ($\sigma$) to create a more autonomous, "plug-and-play" system. Additionally, investigating the scalability of these graph-based methods for extremely large datasets remains a priority for future development.

Summary updated

Abstract

In this study, a spectral graph-theoretic grouping strategy for weakly supervised classification is introduced, where a limited number of labelled samples and a larger set of unlabelled samples are used to construct a larger annotated training set composed of strongly labelled and weakly labelled samples. The inherent relationship between the set of strongly labelled samples and the set of unlabelled samples is established via spectral grouping, with the unlabelled samples subsequently weakly annotated based on the strongly labelled samples within the associated spectral groups. A number of similarity graph models for spectral grouping, including two new similarity graph models introduced in this study, are explored to investigate their performance in the context of weakly supervised classification in handling different types of data. Experimental results using benchmark datasets as well as real EMG datasets demonstrate that the proposed approach to weakly supervised classification can provide noticeable improvements in classification performance, and that the proposed similarity graph models can lead to ultimate learning results that are either better than or on a par with existing similarity graph models in the context of spectral grouping for weakly supervised classification.
BibTeX
@misc{adel2015weakly,
  author = {Tameem Adel and Alexander Wong and Daniel W. Stashuk},
  title = {{A Weakly Supervised Learning Approach based on Spectral Graph-Theoretic Grouping}},
  year = {2015},
  eprint = {1508.00507},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1508.00507},
}
Figure