Unsupervised Ensemble Classification With Sequential and Networked Data

Panagiotis A. Traganitis, Georgios B. GiannakisIEEE TKDE 2020 · DOI · OpenReview

Abstract

Ensemble learning, the machine learning paradigm where multiple models are combined, has exhibited promising performance in a variety of tasks. The present work focuses on unsupervised ensemble classification. The term unsupervised refers to the ensemble combiner who has no knowledge of the ground-truth labels that each classifier has been trained on. While most prior works on unsupervised ensemble classification are designed for independent and identically distributed (i.i.d.) data, the present work introduces an unsupervised scheme for learning from ensembles of classifiers in the presence of data dependencies. Two types of data dependencies are considered: sequential data and networked data whose dependencies are captured by a graph. For both, novel moment matching and Expectation-Maximization algorithms are developed. Performance of these algorithms is evaluated on synthetic and real datasets, which indicate that knowledge of data dependencies in the meta-learner is beneficial for the unsupervised ensemble classification task.

Introduction

In ensemble learning, the goal is to combine the outputs of multiple "base learners"—which could be different machine learning models or human annotators—to produce a final prediction that is more accurate than any individual input. Traditionally, this fusion is performed using a supervised meta-learner trained on a labeled "gold standard" dataset. However, in many modern applications like large-scale crowdsourcing or real-time medical diagnostics, ground-truth labels are unavailable. This necessitates unsupervised ensemble classification.

General framework for unsupervised ensemble classification showing the flow from data to multiple learners and finally to a meta-learner.

A significant limitation of existing unsupervised methods is the assumption that data points are independent and identically distributed (i.i.d.). In reality, data often exhibits strong dependencies: words in a sentence follow a sequence, and research papers in a citation index form a complex network. This paper addresses this gap by proposing a framework that explicitly models these dependencies to improve label fusion accuracy.

Methodology

The authors propose a two-step approach—initialization followed by refinement—for two distinct types of data structures.

1. Sequential Data (Markov Chain Model)

For data that follows a temporal or linear order, the labels are modeled as a Markov Chain, where the probability of a label depends on the preceding one.

  • Initialization: To avoid the local optima common in Expectation-Maximization (EM) algorithms, the authors use a tensor-based "moment-matching" technique. This provides a mathematically grounded "warm start" by estimating the reliability (confusion matrix) of each learner without any labeled data.
  • Refinement and Inference: A variant of the Baum-Welch algorithm (EM) is used to fine-tune these reliability estimates and transition probabilities. Final labels are then estimated using the Viterbi algorithm, which finds the most likely sequence of hidden states.
Graphical model illustrating sequential data dependencies where labels $y_n$ follow a Markov Chain and generate learner responses $f_m(x_n)$.

2. Networked Data (Markov Random Field Model)

For data with graph-based dependencies, labels are modeled as a Markov Random Field (MRF). Here, neighboring nodes in the graph are assumed more likely to share similar labels.

  • Initialization: Similar to the sequential case, moment-matching is employed for initial parameter estimation.
  • Refinement: Since exact inference on general graphs is computationally NP-hard, the authors utilize Iterated Conditional Modes (ICM). This greedy optimization technique is embedded within an EM framework to iteratively update label estimates and learner parameters.

Experimental Evaluation

The proposed methods were evaluated against standard benchmarks, including synthetic data (generated via Stochastic Block Models) and diverse real-world datasets:

  • Sequential Tasks: Part-of-speech (POS) tagging (Brown corpus), Named-entity recognition (CoNLL), and Biomedical information extraction.
  • Networked Tasks: Citation networks (Cora, CiteSeer, Pubmed), crowdsourced medical image segmentation (BU-BIL MRI), and sentiment analysis.

Key Results

In nearly every scenario, the proposed algorithms significantly outperformed traditional Majority Voting and i.i.d.-based unsupervised methods like the classic Dawid-Skene model. For instance, on the Cora citation dataset, the proposed method achieved an F-score of 0.64, compared to just 0.27 for Majority Voting and 0.51 for the best individual base learner. On synthetic data, the performance of these unsupervised methods was shown to approach that of an "Oracle" classifier as the dataset size increased.

Discussion and Insights

The core finding of this research is that structure is a signal. By treating the dependency structure (the sequence or graph) as a regularizer, the meta-learner can use contextual information to resolve conflicts between base learners. For example, if several learners provide a label that is highly improbable given the surrounding sequence, the model can use the Markovian structure to overrule them.

While the sequential approach is computationally efficient, the networked approach relies on greedy approximations (ICM) which may be limited in extremely complex graphs. Future research directions include developing instance-dependent learner models—where a learner's reliability varies by topic—and techniques to learn the underlying graph structure and labels simultaneously.

Summary updated

Abstract

Ensemble learning, the machine learning paradigm where multiple models are combined, has exhibited promising perfomance in a variety of tasks. The present work focuses on unsupervised ensemble classification. The term unsupervised refers to the ensemble combiner who has no knowledge of the ground-truth labels that each classifier has been trained on. While most prior works on unsupervised ensemble classification are designed for independent and identically distributed (i.i.d.) data, the present work introduces an unsupervised scheme for learning from ensembles of classifiers in the presence of data dependencies. Two types of data dependencies are considered: sequential data and networked data whose dependencies are captured by a graph. For both, novel moment matching and Expectation-Maximization algorithms are developed. Performance of these algorithms is evaluated on synthetic and real datasets, which indicate that knowledge of data dependencies in the meta-learner is beneficial for the unsupervised ensemble classification task.
BibTeX
@article{traganitis2020unsupervised,
  author = {Panagiotis A. Traganitis and Georgios B. Giannakis},
  title = {{Unsupervised Ensemble Classification With Sequential and Networked Data}},
  journal = {IEEE Transactions on Knowledge and Data Engineering},
  year = {2020},
  doi = {10.1109/tkde.2020.3046645},
}
Figure