A New Analysis of Co-Training

Wei Wang, Zhi-Hua ZhouICML 2010 · OpenReview

Introduction

Semi-supervised learning (SSL) is the art of using a small amount of labeled data alongside a mountain of unlabeled data to build better models. One of the most famous SSL paradigms is co-training, where two classifiers are trained on different "views" of the same data (e.g., the text of a webpage vs. the anchor text of links pointing to it) and teach each other by labeling unlabeled examples.

While co-training works well in practice, the theory behind why it works has historically been incomplete. Previous researchers proposed "sufficient" conditions—rules that, if met, guarantee success (like the views being independent). However, "necessary" conditions—the bare minimum requirements for co-training to be effective—remained elusive. Furthermore, co-training was historically seen as distinct from graph-based SSL, where labels "flow" through a network of similar data points.

This paper provides a groundbreaking theoretical bridge between these two major branches of SSL. By re-interpreting co-training as a process of "label propagation" across two graphs, the authors establish the first-ever sufficient and necessary conditions for co-training to succeed, offering a principled way to handle single-view data through intelligent feature splitting.

The Graph View of Co-training

The authors propose treating each view as a graph where nodes are data points and edges represent the probability that one point shares a label with another.

Key technical contributions include:

  • Combinative Label Propagation: The iterative co-training algorithm is re-described as a process where labels are propagated on one graph, and the newly labeled points are then used as "seeds" for the second graph.
  • The Combinative Graph ($P^c$): They define a joint graph where the connection between two points is the maximum of their connections in either of the two individual views ($P^c_{ij} = \max[P^1_{ij}, P^2_{ij}]$).
  • Sufficient and Necessary Conditions: They prove that for co-training to perfectly label all data (assuming "perfect" graphs), every unlabeled instance must be reachable from a labeled instance in this combined graph $P^c$.

Key Insights and Unification

The "aha moment" of this research is the connectivity secret: co-training succeeds because the two views are complementary in how they connect data. One view might connect point A to the labeled set, while the other view connects point B. Together, they "bridge" the entire dataset.

By showing that co-training is essentially label propagation on a combined graph, the authors bring disagreement-based learning and graph-based learning into a single theoretical framework.

Furthermore, this theory provides a principled approach to view splitting. If you only have one set of features (one view), how do you split them to use co-training? The authors suggest choosing the split that results in the most "connected" combinative graph $P^c$. This is far more effective than the standard practice of splitting features randomly.

Empirical Validation and Results

The authors validated their theory using both artificial datasets (where connectivity could be strictly controlled) and the classic real-world Course dataset (web pages from computer science departments, split into "page" and "link" views).

  • Performance Boost: Co-training consistently outperformed single-view learners. On the Course dataset, co-training achieved significantly lower error rates than using just the "page" or "link" views alone.
Error rate comparison on the Course dataset
  • Superior View Splitting: The proposed view-split method (based on maximizing connectivity) consistently outperformed random splits, validating that their theoretical "necessary condition" is a powerful tool for algorithm design.
Comparison of view splitting methods
  • Connectivity: On both artificial and real-world data, the authors showed that the number of "unconnected" instances (those that cannot be labeled) is significantly lower in the combined graph $P^c$ than in either individual view.

Limitations and Future Work

While this framework is powerful, it relies heavily on having a good graph to begin with. The authors used simple 1-Nearest Neighbor (1-NN) graphs for their experiments, acknowledging that constructing the optimal graph for co-training remains an open question.

Additionally, while the paper addresses "non-perfect" and "$\epsilon$-good" graphs, real-world data is often much noisier. Further study is needed to see how these conditions hold up under extreme noise or adversarial conditions. Finally, extending this logic to multi-view scenarios (more than two graphs) presents a fruitful area for future research.

Summary updated

BibTeX
@inproceedings{wang2010new,
  author = {Wei Wang and Zhi-Hua Zhou},
  title = {{A New Analysis of Co-Training}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=BZuSoi_XTtv},
}
Figure