Analysis of Co-training Algorithm with Very Small Training Sets

Luca Didaci, Giorgio Fumera, Fabio RoliSspr/spr 2012 · DOI

Introduction

Co-training is a prominent semi-supervised learning (SSL) paradigm that leverages two distinct "views" (independent feature sets) of the same data to train two classifiers. These classifiers iteratively "teach" each other by labeling the unlabeled samples for which they have the highest confidence. While co-training is widely recognized for its effectiveness with limited labeled data, the precise lower bound of the initial training set size ($L$) required for success has remained largely unexplored. This paper investigates whether a "breaking point" exists where the initial labeled set is too small to initiate a productive learning process.

Methodology

The study evaluates the standard co-training algorithm using two base classifiers: Naive Bayes (NB) and 1-Nearest Neighbor (1-NN). Because most benchmark datasets are single-view, the authors employed an automated feature-splitting technique designed to minimize correlation between views while maintaining their individual discriminative power.

The experimental workflow involves starting with a minimal labeled set $L$ and iteratively selecting high-confidence unlabeled samples to augment the training pool. The size of $L$ was varied from the absolute minimum (one sample per class) up to 50% of the total dataset to map the performance trajectory.

Experimental Setup

The researchers utilized 24 real-world datasets from the UCI Machine Learning Repository, covering diverse domains such as medicine (Breast Cancer, E.Coli), physical sciences (Ionosphere, SolarFlare), and general classification tasks (Credit Approval, Spambase). This broad selection ensures the findings are not artifacts of a specific data distribution.

Key Insights: The "One-Sample" Success

The most significant finding is the algorithm's ability to "bootstrap" effectively with just one labeled sample per class. Contrary to the intuition that an initial training set must be representative of the global distribution, co-training demonstrates remarkable resilience to extremely small starting pools.

Figure 1: Accuracy vs. Size of L for the Hepatitis dataset, illustrating the stability of co-training compared to the volatile supervised baseline.

As illustrated in Figure 1, the accuracy of co-training remains nearly constant even as the size of $L$ increases. In contrast, the supervised baseline ("Before co-training") is highly volatile and significantly less accurate at low sample sizes. This suggests that the iterative process of incorporating high-confidence unlabeled samples effectively corrects for the initial data scarcity.

Comparative Results

The benefits of co-training were observed across the majority of the 24 datasets. The performance gains were particularly pronounced when using Naive Bayes as the base learner.

Figure 3: Performance comparison of co-training across 24 datasets using Naive Bayes and K-NN classifiers.

As shown in Figure 3, co-training with the absolute minimum training set outperformed the supervised baseline in both views for 14 out of 24 datasets when using Naive Bayes. For K-NN, the results were also positive, with co-training winning in 9 datasets and losing in only one. The authors attribute this robustness to a conservative updating policy, which prevents the propagation of errors even when the initial classifiers are weak.

Limitations and Conclusion

While the study proves that co-training can work with minimalist sets, it also highlights that success is not universal. Some datasets showed no significant improvement, and the effectiveness of the algorithm is tied to the intrinsic limits of the base classifier (e.g., a Gaussian classifier requires enough samples to estimate covariance). Furthermore, the reliance on artificial feature splitting suggests that real-world multi-view data with different dependency structures warrants further study.

In conclusion, co-training is a robust SSL technique capable of operating at the extreme edge of data scarcity. The ability to achieve stable, high-accuracy results with as little as one sample per class provides a powerful tool for domains where labeling costs are prohibitive.

Summary updated

BibTeX
@inproceedings{didaci2012analysis,
  author = {Luca Didaci and Giorgio Fumera and Fabio Roli},
  title = {{Analysis of Co-training Algorithm with Very Small Training Sets}},
  booktitle = {Sspr/spr},
  year = {2012},
  doi = {10.1007/978-3-642-34166-3\_79},
}
Figure