Margin Semi-Supervised Learning for Structured Variables

Yasemin Altun, David A. McAllester, Mikhail BelkinNeurIPS 2005 · OpenReview

Introduction

Many real-world classification problems—such as part-of-speech tagging or DNA sequence analysis—involve predicting multiple inter-dependent variables that form a structural dependency. While supervised learning has made great strides in structured classification, labeling these complex structures is incredibly expensive and time-consuming.

This paper introduces a framework for Maximum Margin Semi-Supervised Learning tailored for structured variables (like sequences or trees). By combining the "manifold assumption"—the idea that similar inputs should have similar labels—with a maximum-margin (SVM-style) approach, the authors create a model that leverages cheap unlabeled data to improve complex predictions. Crucially, unlike many existing "transductive" semi-supervised methods that only provide labels for the specific unlabeled points seen during training, this formulation is inductive, meaning it naturally extends to entirely new, unseen test cases.

Methodology

The authors build their approach on two major pillars: Structured SVMs and Manifold Regularization.

  • The Manifold Assumption: The model assumes that the "intrinsic geometry" of the data matters. If two input patterns are close to each other in the high-dimensional input space (a relationship revealed by a large pool of unlabeled data), their predicted structured outputs should be similar.
  • Graph-Regularized Kernels: To implement this, the authors utilize a "Graph Laplacian"—a mathematical tool that captures the shape of the data distribution. They derive a new "graph-regularized kernel" that essentially warps a standard kernel to respect the density of the data.
  • Maximum Margin Formulation: This specialized kernel is plugged into a structured maximum-margin optimization problem. This allows the model to find a decision boundary that not only separates labeled examples with a wide margin but also remains "smooth" across the manifold formed by the unlabeled data.
  • Representer Theorem: A key theoretical contribution is showing that even though the problem involves complex structures and unlabeled data, the optimal solution can still be represented as a linear combination of "parts" from the labeled data, keeping the math computationally feasible.

Experiments and Key Results

The authors evaluated their model on two primary tasks: Pitch Accent (PA) Prediction and Optical Character Recognition (OCR). The results suggest that the benefits of "structured" modeling (looking at dependencies) and "semi-supervised" modeling (looking at unlabeled data) are additive.

Pitch Accent (PA) Prediction

This task involves predicting the prosodic prominence of words in speech. The input consists of 31-dimensional feature vectors, and the output is a binary sequence.

Pitch Accent Results

In the PA task, the structured model (STR) consistently outperformed a standard unstructured SVM. For example, when utilizing 200 unlabeled sequences (U:200), the structured model's accuracy reached 77.45%, compared to 73.11% for a standard SVM. Furthermore, the accuracy on "out-of-sample" test data was nearly identical to the accuracy on the "in-sample" unlabeled data, confirming that the kernel-based approach successfully generalizes to new points.

Optical Character Recognition (OCR)

The second task involved recognizing handwritten words, where the input is a sequence of binary pixel vectors and the output is a sequence of characters.

OCR Results

In the OCR task, incorporating unlabeled data improved accuracy for both models (e.g., the SVM jumped from ~43% to ~49%). However, the structured model didn't significantly beat the unstructured one in this specific setup. The authors noted that with very few labeled sequences, the "noise" in the label-to-label dependencies was too high for the structured model to gain a definitive edge.

Key Insights and Limitations

  • Unlabeled Data as a Map: The framework treats unlabeled data not as missing information, but as a map of the territory. The distribution of unlabeled points tells the model where the "manifolds" are, helping it draw better boundaries.
  • Structural Sparsity: As seen in the OCR results, if the labeled dataset is too small, the model struggles to learn the "rules" of the structure (e.g., which letters usually follow 'q'), making the structured approach less effective.
  • Future Work: While the authors successfully reduced the dimensionality of the problem, solving quadratic programs for structured outputs remains computationally intensive. Future work could extend this simple "chain" model to more complex structures, like hierarchical trees found in natural language parsing.

Summary updated

Abstract

Many real-world classification problems involve the prediction of multiple inter-dependent variables forming some structural depen- dency. Recent progress in machine learning has mainly focused on supervised classification of such structured variables. In this paper, we investigate structured classification in a semi-supervised setting. We present a discriminative approach that utilizes the intrinsic ge- ometry of input patterns revealed by unlabeled data points and we derive a maximum-margin formulation of semi-supervised learning for structured variables. Unlike transductive algorithms, our for- mulation naturally extends to new test points.
BibTeX
@inproceedings{altun2005margin,
  author = {Yasemin Altun and David A. McAllester and Mikhail Belkin},
  title = {{Margin Semi-Supervised Learning for Structured Variables}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2005},
  url = {https://openreview.net/forum?id=Sy-JoIbdWr},
}
Figure