Abstract
This paper provides a "painless" recipe for a common headache in unsupervised learning: how to inject human intuition and domain knowledge into a model without breaking its simplicity or making it impossible to train. The authors show that standard generative models (like HMMs) can be significantly improved by replacing their simple probability tables with "miniature" logistic regression models. This allows researchers to easily add rich, hand-designed features to unsupervised tasks using standard optimization tools like LBFGS, achieving state-of-the-art results across POS tagging, grammar induction, word alignment, and segmentation.
Introduction
In unsupervised learning, the goal is to discover structure in data without explicit labels. Traditionally, improving these models required altering their "backbone" structure—changing conditional independence assumptions. However, this process is notoriously difficult; the relationship between independence and linguistic knowledge is subtle, and structural changes often necessitate entirely new inference algorithms.
In supervised learning, this is typically solved through feature engineering: providing the model with specific cues like capitalization or suffixes. Historically, doing this in unsupervised learning has been "painful" because it often leads to globally normalized models (like Markov Random Fields) that are computationally expensive to optimize. This paper proposes a middle ground: locally normalized generative models with features.
Methodology: The Logistic Trick
The authors propose parameterizing multinomial distributions (such as the probability of a word given a tag) as small multi-class logistic regression models rather than flat tables. The probability of a decision $d$ given a context $c$ is defined as:
$$P(d|c) \propto \exp(w \cdot f(d,c))$$
where $f(d,c)$ represents user-defined features and $w$ represents the weights to be learned. By keeping the model locally normalized (decisions sum to one at each step), they avoid the "partition function" problem that plagues globally normalized models, making training faster and more stable.
Optimization Strategies
The paper presents two primary ways to train these feature-enhanced models:
- Feature-enhanced EM: A variation of the standard Expectation-Maximization algorithm. The E-step remains identical to the base model (e.g., the Forward-Backward algorithm). The M-step, however, becomes a gradient-based optimization—essentially training a supervised MaxEnt model using the "expected counts" derived from the E-step.
- Direct Gradient Optimization: Using LBFGS to optimize the marginal likelihood of the observed data directly. While more computationally intensive, as it requires re-running inference at every iteration, the authors find this often leads to superior performance.
Experimental Results
The authors evaluated their approach on four distinct NLP tasks: Part-of-Speech (POS) Induction, Grammar Induction (using the Dependency Model with Valence), Word Alignment (Chinese-English), and Word Segmentation.
Across all tasks, the feature-enhanced models consistently outperformed their "basic" counterparts and often surpassed more complex, specialized state-of-the-art models. For instance, in POS induction, accuracy jumped from 63.1% (Basic HMM) to 75.5% (Feature-HMM with LBFGS). In grammar induction on English WSJ10, they achieved 63.0% directed attachment accuracy, beating the previous best of 61.3%.
Key Insights and Discussion
- Declarative Knowledge: The "painless" aspect is that researchers can inject linguistic insights (e.g., "nouns often end in -tion") declaratively through features rather than procedurally by hacking the model's architecture.
- Direct Optimization Wins: A surprising takeaway is that directly optimizing the marginal likelihood with LBFGS often outperforms the traditional EM algorithm, providing a significant boost in accuracy for tasks like POS induction.
- The Power of Coarse Features: Even simple orthographic features (capitalization, hyphens, suffixes) allow the model to generalize across rare words that a standard HMM would treat as completely independent entities.
While effective, these methods do have limitations. Direct gradient optimization is computationally intensive, requiring recomputing expectations at every step of the LBFGS search. Additionally, while the mechanism is painless, the user still must design the features manually, as the paper does not explore automatic feature induction.
Summary updated