Tractable Semi-supervised Learning of Complex Structured Prediction Models

Kai-Wei Chang, S. Sundararajan, S. Sathiya KeerthiECML/PKDD 2013 · OpenReview

Abstract

Semi-supervised learning (SSL) has been widely studied, yet most existing frameworks assume output structures are simple enough to permit tractable inference, such as linear chains or binary labels. Consequently, these methods often fail when applied to complex, densely connected structured prediction problems. This paper introduces an approximate SSL method that combines piecewise training for parameter estimation with dual decomposition for solving the inference problem on unlabeled data under domain-specific constraints. By applying this approach to multi-label classification—modeled as a fully connected pairwise Markov Random Field—we demonstrate that the proposed method effectively improves generalization performance over supervised baselines, even when using approximations. Furthermore, the inference engine is shown to be compatible with other SSL frameworks, extending their utility to complex structured domains.

Introduction

Structured prediction is a cornerstone of modern machine learning, enabling models to predict outputs with internal dependencies, such as sequences in natural language or grids in computer vision. However, the utility of these models is often limited by the high cost of obtaining labeled structured data. While semi-supervised learning (SSL) offers a path forward by leveraging unlabeled data, a significant technical hurdle remains: tractability.

In complex structured models, such as fully connected graphs where every label may influence every other label, calculating the partition function for training or finding the optimal label assignment for inference becomes computationally impossible (intractable). This paper bridges the gap by proposing a framework that makes SSL viable for these complex, real-world structures.

Methodology

The authors propose a two-pronged approximation strategy integrated within an alternating optimization loop. This approach allows the model to learn from unlabeled data without the computational burden of exact global inference.

1. Approximate Learning via Piecewise Training

To avoid optimizing the "true" joint probability of a complex graph—which requires calculating an intractable partition function—the authors employ piecewise training (composite likelihood). The complex graph is decomposed into smaller, tractable "pieces," such as spanning trees. The model then maximizes the composite likelihood, which is the product of the likelihoods of these individual pieces, significantly reducing the computational overhead.

2. Approximate Inference via Dual Decomposition

During the SSL process, the model must assign labels to unlabeled data ($Y_U$). The authors utilize a dual decomposition approach based on a "Master-Slave" architecture. This allows the system to solve the inference problem by coordinating between the tractable pieces while simultaneously enforcing global domain constraints. This ensures that the predicted labels for unlabeled data remain consistent with known properties of the problem domain.

3. Deterministic Annealing

To mitigate the risk of the model converging to poor local minima—a common issue when a model "guesses" its own labels—the authors implement a deterministic annealing schedule. The training begins with a low weight on the unlabeled data, which is gradually increased as the model’s confidence and accuracy improve.

Experimental Evaluation

The framework was evaluated on five standard multi-label classification benchmarks: scene (images), yeast (protein functions), emotions (music), rcv (news), and tmc2007 (aviation reports). The experiments focused on scenarios with extremely limited labeled data (1%, 2%, 4%, and 8% labeling), using the remainder of the training sets as unlabeled data.

Key Results

  • Performance Lift: The proposed semi-supervised method consistently outperformed supervised baselines across all datasets. The most significant gains were observed in the most data-constrained scenarios (1% labeling).
  • Constraint Synergy: The research highlighted the importance of domain-specific guidance. Using Label Distribution Constraints (LDC) and Label Correlation Constraints (LCC) in tandem provided a more robust performance boost than using either constraint in isolation.
  • Efficiency: On datasets where exact inference was possible (e.g., yeast), the approximate method achieved comparable accuracy while being significantly faster (4,167 seconds vs. 9,175 seconds).
  • Versatility: The dual decomposition inference engine was successfully integrated into other SSL frameworks, such as Transductive SVM (TSVM) and Co-regularized Deep Learning (CoDL), demonstrating its broad applicability to complex tasks.

Discussion and Insights

A critical insight of this work is the decoupling of approximations. By using an alternating optimization loop, the learning approximation (piecewise) and the inference approximation (dual decomposition) can function independently without compromising the convergence properties of the overall system.

Furthermore, the authors demonstrate that unlabeled data is a double-edged sword; while it provides more information, it also introduces noise. Incorporating "corpus-level" constraints acts as a vital "nudge," preventing the semi-supervised process from drifting toward incorrect, though mathematically consistent, solutions.

Limitations and Future Work

While the method is effective, the authors noted potential for overfitting to unlabeled data on smaller datasets (like emotions) if the weight of the unlabeled data is increased too aggressively. Future research could explore more sophisticated constraint engineering, such as using human-provided first-order logic, to further guide the model. Additionally, scaling these dual decomposition techniques to "extreme" multi-label problems involving thousands of labels remains a significant challenge for the field.

Conclusion

This paper provides a tractable framework for applying semi-supervised learning to complex structured prediction problems. By combining piecewise training with dual decomposition and domain constraints, the authors enable effective learning in domains where exact inference was previously a bottleneck. The results confirm that even with approximations, SSL can provide substantial benefits for complex, real-world structured tasks.

Summary updated

Abstract

Semi-supervised learning has been widely studied in the literature. However, most previous works assume that the output structure is simple enough to allow the direct use of tractable inference/learning algorithms (e.g., binary label or linear chain). Therefore, these methods cannot be applied to problems with complex structure. In this paper, we propose an approximate semi-supervised learning method that uses piecewise training for estimating the model weights and a dual decomposition approach for solving the inference problem of finding the labels of unlabeled data subject to domain specific constraints. This allows us to extend semi-supervised learning to general structured prediction problems. As an example, we apply this approach to the problem of multi-label classification (a fully connected pairwise Markov random field). Experimental results on benchmark data show that, in spite of using approximations, the approach is effective and yields good improvements in generalization performance over the plain supervised method. In addition, we demonstrate that our inference engine can be applied to other semi-supervised learning frameworks, and extends them to solve problems with complex structure.
BibTeX
@inproceedings{chang2013tractable,
  author = {Kai-Wei Chang and S. Sundararajan and S. Sathiya Keerthi},
  title = {{Tractable Semi-supervised Learning of Complex Structured Prediction Models}},
  booktitle = {ECML/PKDD},
  year = {2013},
  url = {https://openreview.net/forum?id=KOR0GHJN1-h2},
}
Figure