Abstract
Semi-supervised structured output learning faces significant challenges due to combinatorial explosion and non-convex optimization landscapes. This paper proposes Deterministic Annealing for Structured Outputs (DASO), a method that leverages the principles of deterministic annealing to navigate complex objective functions. By starting with a high-temperature "smooth" objective and gradually cooling it, DASO avoids poor local optima. Experimental results on information extraction benchmarks demonstrate that DASO consistently outperforms state-of-the-art baselines, particularly in low-resource settings.
Introduction
Predicting structured outputs, such as sequence labels or parse trees, is fundamental to many real-world applications. However, obtaining labeled data for these tasks is often prohibitively expensive. Semi-supervised learning (SSL) offers a solution by utilizing large amounts of unlabeled data. Despite its potential, SSL for structured outputs is hindered by two primary issues: the exponential growth of the label space and the non-convexity of optimization objectives that incorporate domain constraints. Existing methods like Posterior Regularization (PR) often converge to suboptimal local minima or fail to satisfy constraints during inference.
Methodology: The DASO Approach
The proposed DASO framework addresses these challenges by applying Deterministic Annealing (DA) to a relaxed version of the learning objective.
Relaxed Labeling and Entropy Regularization
Instead of assigning hard labels to unlabeled data, DASO utilizes a probability distribution over possible labelings. To facilitate exploration of the optimization landscape, an entropy term is added to the objective function, weighted by a temperature parameter $T$. At high temperatures, the objective is highly convex and smooth, allowing the model to explore broadly.
Annealing and Optimization
As the temperature $T$ is gradually decreased (cooled), the distribution "freezes" into a specific, sparse solution. The optimization alternates between updating model parameters ($\theta$) and the label distribution ($a$). By solving the label distribution problem in its dual form, DASO maintains computational efficiency comparable to standard Conditional Random Field (CRF) training.
Experimental Setup
The method was evaluated on two information extraction datasets:
- Citations: 500 computer science citations labeled with fields like Author, Title, and Journal.
- Apartment Listings: 300 Craigslist ads with labels such as Rent, Size, and Features.
The experiments focused on "bootstrapping" scenarios where the number of labeled examples ($N$) was extremely small (e.g., $N=5$).
Results and Discussion
DASO was compared against supervised baselines, Constraint Driven Learning (CoDL), and Posterior Regularization (PR).
Performance in Low-Resource Scenarios
As shown in the results table, DASO consistently achieves the highest accuracy across different amounts of labeled data. In the Citations dataset with only 5 labeled examples, DASO (T) reached an accuracy of 0.773, significantly outperforming CoDL (0.710) and PR (T) (0.741).
Robustness and Constraint Satisfaction
A key advantage of DASO is its robustness to hyperparameter settings. Sensitivity analysis (Figure 2) indicates stable performance across various starting temperatures and cooling rates. Furthermore, by ensuring the learned label distributions are sparse, DASO better aligns training objectives with the hard-labeling process used during inference, leading to improved adherence to domain constraints.
Conclusion
Deterministic Annealing for Structured Outputs (DASO) provides a robust framework for semi-supervised learning in complex label spaces. By effectively avoiding poor local minima through a cooling schedule, it sets a new standard for performance in low-data regimes. While computationally more intensive than some alternatives, its superior accuracy and reliability make it a compelling choice for structured prediction tasks. Future work includes extending this approach to large-margin models and further optimizing computational speed.
Summary updated