Continuation Methods for Mixing Heterogenous Sources

Adrian Corduneanu, Tommi S. Jaakkola

Abstract

In modern machine learning, combining heterogeneous data sources—such as a small set of labeled examples and a large volume of unlabeled data—is a common yet unstable task. Standard approaches like Expectation-Maximization (EM) often converge to poor local optima when the unlabeled data distribution conflicts with the labeled evidence. This paper introduces a homotopy continuation method that traces a continuous path of solutions from a labeled-only model to a combined model. This approach allows for the identification of "critical points" where the model's behavior shifts drastically, ensuring the final solution remains anchored to the ground truth.

Introduction

The challenge of semi-supervised learning lies in balancing "privileged" information (labels) with "abundant" information (unlabeled data). While maximizing a combined likelihood is standard, the optimization landscape is often non-convex and unstable. A slight over-weighting of unlabeled data can cause the model to "jump" to a solution that fits the unlabeled distribution well but ignores the labels. This paper addresses this instability by treating the balance between sources as a continuous parameter, navigating the "mathematical cliffs" that cause standard algorithms to fail.

Methods: Homotopy Continuation

The authors propose using homotopy continuation to manage the transition between information sources. Instead of picking a fixed weight $\lambda$ for the unlabeled data and running an optimizer, they start with a weight of zero (using only labeled data) and slowly "morph" the problem by increasing $\lambda$.

Path Tracing and Critical Points

The core of the method involves treating the fixed-point equations of the EM algorithm as a system of differential equations. By following the "null space" of the Jacobian matrix, the algorithm traces a unique, continuous path of solutions. This allows it to navigate "critical points"—moments where the model's behavior changes drastically with a tiny change in weighting. Unlike simple gradient descent or standard EM, which are "blind" to these transitions, homotopy continuation stays "anchored" to the labeled evidence.

Evolution of classification error during homotopy path tracing.

Experimental Evaluation

The method was evaluated on two distinct tasks designed to test robustness against conflicting data sources:

  1. Text Classification: Using a subset of the 20-newsgroups database (3 classes: politics, religion, and cryptography). The models were trained on only 10 labeled documents and a large set of unlabeled data, using the top 20 binary features.
  2. DNA Motif Discovery: Identifying a hidden 10-base motif in artificially generated sequences. This task was framed as a "minimax" game where the motif model tries to distinguish itself from the "worst-case" background model, solved via the same continuation framework.

Key Results

The homotopy method demonstrated significant improvements in both stability and accuracy. In the text classification task, the algorithm consistently stayed on track until a critical point was reached, whereas standard EM often converged to fixed points unrelated to the labels.

Error rate comparison between labeled-only, homotopy, and EM methods.

As shown in the results table, the Homotopy method achieved an average error rate of 20.4%, significantly outperforming standard EM (28.0%) and the labeled-only baseline (35.8%). In the DNA motif discovery task, the competitive minimax approach consistently found the correct motifs more often than AlignACE, especially as the signal-to-noise ratio decreased.

Conclusion and Future Work

By maintaining a continuous link to labeled evidence, homotopy continuation provides a principled way to manage the instability of mixing heterogeneous data sources. The algorithm can explicitly identify the "critical allocation" (the exact point where unlabeled data starts to overwhelm labeled data), providing a valuable diagnostic for model reliability.

While the current implementation faces computational challenges due to the $O(n^3)$ complexity of solving linear systems, future work aims to optimize these steps. Additionally, while this study focused on generative models, the authors suggest these "stability-regaining" ideas could be extended to discriminative methods like Support Vector Machines and complex game-theoretic problems.

Summary updated

Abstract

A number of modern learning tasks involve estimation from heterogeneous information sources. This includes classification with labeled and unlabeled data as well as other problems with analogous structure such as competitive (game theoretic) problems. The associated estimation problems can be typically reduced to solving a set of fixed point equations (consistency conditions). We introduce a general method for combining a preferred information source with another in this setting by evolving continuous paths of fixed points at intermediate allocations. We explicitly identify critical points along the unique paths to either increase the stability of estimation or to ensure a significant departure from the initial source. The homotopy continuation approach is guaranteed to terminate at the second source, and involves no combinatorial effort. We illustrate the power of these ideas both in classification tasks with labeled and unlabeled data, as well as in the context of a competitive (min-max) formulation of DNA sequence motif discovery.
BibTeX
@inproceedings{corduneanu2002continuation,
  author = {Adrian Corduneanu and Tommi S. Jaakkola},
  title = {{Continuation Methods for Mixing Heterogenous Sources}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2002},
}
Figure