Multi-View Learning over Structured and Non-Identical Outputs

Kuzman Ganchev, Joao Graca, John Blitzer, Ben Taskar

TL;DR

This paper introduces a novel probabilistic framework for multi-view learning that regularizes models by minimizing the Bhattacharyya distance between their predictions on unlabeled data. Crucially, it extends multi-view learning beyond simple classification to handle structured outputs (like sequences) and scenarios where different views predict non-identical, partially overlapping label sets.

What Problem Does This Paper Address?

In semi-supervised learning, multi-view learning leverages the fact that data can often be described by independent sets of features (e.g., the text of a webpage vs. the anchor text of links pointing to it), both of which are theoretically sufficient to predict a label. By forcing models trained on these different "views" to agree on unlabeled data, we can drastically reduce the search space for the correct model.

However, traditional multi-view methods (like Co-Training or CoBoosting) assume that all views share the exact same output labels and work primarily on flat classification tasks. Real-world tasks are rarely that simple. We frequently encounter structured outputs (like predicting a sequence of part-of-speech tags) or datasets with non-identical label sets (e.g., trying to make a fine-grained classifier agree with a coarse-grained auxiliary classifier). The authors address the challenge of enforcing agreement between different views under these complex structured and mismatched label conditions.

Methods

The authors introduce Stochastic Agreement Regularization (SAR). Instead of forcing hard label agreement on unlabeled data, SAR minimizes the expected Bhattacharyya distance between the probability distributions of the views.

Key aspects of the methodology include:

  • Optimization via Constrained EM: The authors prove that minimizing the Bhattacharyya distance is variationally equivalent to a constrained Kullback-Leibler (KL) minimization problem. This allows them to optimize the objective using a fast, iterative constrained Expectation-Maximization (EM) framework.
  • Closed-Form Projections: For full agreement tasks and simple unstructured partial agreement, the E-step (finding the closest agreeing distribution) has a simple closed-form solution. It essentially takes the geometric mean of the view distributions, acting like a logarithmic opinion pool.
  • Handling Structured & Non-Identical Labels: When label sets differ (partial agreement), they map labels to a shared common space. For structured partial agreement—where exact Markov properties break down when collapsing labels—they relax the constraints to match clique marginals instead of the full joint distribution, solving the optimization via conjugate gradient.

Datasets

The framework was evaluated across several natural language processing and text classification benchmarks:

  • Sentiment Classification: Amazon product reviews across four domains (books, dvds, electronics, kitchen) from Blitzer et al. (2007), evaluated in a transfer learning setup.
  • Named Entity Disambiguation / Recognition: The CoNLL 2003 shared task dataset.
  • Partial Agreement Classification: A 4-class subset of the 20-Newsgroups corpus (comp.sys.ibm.pc.hardware, comp.sys.mac.hardware, talk.politics.mideast, rec.sport.baseball).
  • Shallow Parsing (Noun Phrase Chunking): The CoNLL 2000 shared task dataset.

Key Insights and Ideas

  • The Sweet Spot of Loss Functions: The Bhattacharyya distance regularizer behaves more robustly than alternatives. As visualized in the paper's analysis of loss surfaces, it penalizes confidence mismatches near the origin linearly. This makes it more lenient than Least Squares (co-RLS) which penalizes high-confidence differences too harshly, yet stricter than CoBoosting's exponential loss, which completely ignores confidence differences once the models agree on the base label.
  • Soft Assignments Breed Stability: Unlike Co-Training, which makes hard, potentially erroneous assignments to unlabeled data early on, SAR uses soft assignments via latent variables, leading to a much more stable optimization path.
  • Bridging Mismatched Label Sets: The framework elegantly allows an auxiliary model trained on a coarser label set to regularize a primary model trained on a fine-grained label set, effectively transferring structural knowledge across different annotation schemas.

Key Results

  • Sentiment Transfer Learning: SAR outperformed CoBoosting and two-view Perceptron in 6 out of 12 domain transfer tasks, proving highly competitive with specialized transfer methods like Structural Correspondence Learning (SCL).
  • Noun Phrase Chunking (Structured): For small training sizes (10–20 sentences), SAR achieved significant error reductions (up to 23% Relative Reduction in Error) over standard Conditional Random Fields (CRFs) and consistently outperformed two-view Perceptron.
  • Partial Agreement: On the 20-Newsgroups task, using an auxiliary view with collapsed labels significantly reduced confusion between highly similar classes (like IBM vs. Mac hardware), as shown by the accuracy trajectory over varying training sizes.
Figure 2: Results of the partial agreement experiments with four labels in one view and three labels in the other.

Limitations and Future Work

  • Scaling to Multiple Views: The current formulation focuses primarily on two views; extending it to scale efficiently to many views with varying weights remains future work.
  • Approximate Projections for Complex Structures: For complex structured partial agreement, the closed-form solution is lost, requiring iterative gradient steps (e.g., conjugate gradient) which increases computational overhead.
  • Theoretical Convergence: The authors note that understanding the exact conditions under which two-view co-regularization asymptotically outperforms a monolithic model remains an open theoretical question.

Summary updated

Abstract

In many machine learning problems, labeled training data is limited but unlabeled data is ample. Some of these problems have instances that can be factored into multiple views, each of which is nearly sufficent in determining the correct labels. In this paper we present a new algorithm for probabilistic multi-view learning which uses the idea of stochastic agreement between views as regularization. Our algorithm works on structured and unstructured problems and easily generalizes to partial agreement scenarios. For the full agreement case, our algorithm minimizes the Bhattacharyya distance between the models of each view, and performs better than CoBoosting and two-view Perceptron on several flat and structured classification problems.
BibTeX
@inproceedings{ganchev2008multi,
  author = {Kuzman Ganchev and Joao Graca and John Blitzer and Ben Taskar},
  title = {{Multi-View Learning over Structured and Non-Identical Outputs}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2008},
}
Figure