Viterbi Training for PCFGs: Hardness Results and Competitiveness of Uniform Initialization

Shay B. Cohen, Noah A. Smith

Abstract

This paper investigates the theoretical complexity of Viterbi training (often implemented via hard EM) for Probabilistic Context-Free Grammars (PCFGs). We prove that finding—or even approximating—the optimal joint assignment of grammar weights and hidden parse trees is NP-hard. To cope with this computational intractability, we provide a rigorous information-theoretic justification for initializing Viterbi EM with a uniform-at-random distribution over parse trees, showing it acts as an optimal worst-case initializer.

Introduction

Probabilistic Context-Free Grammars (PCFGs) are foundational models in natural language processing used to represent the syntactic structure of language. When training these models without labeled syntax trees (unsupervised learning), researchers often use the Expectation-Maximization (EM) algorithm. A popular, faster variant is Viterbi EM (or "hard EM"), which simplifies the E-step by assigning 100% of the probability mass to the single most likely parse tree (the Viterbi parse) rather than maintaining a dense distribution over all possible trees.

While Viterbi EM is widely used and forms the basis of techniques like self-training, the exact computational complexity of the underlying optimization problem it attempts to solve—termed ViterbiTrain—was not fully formalized. Because Viterbi EM is a coordinate ascent algorithm that only guarantees finding a local optimum, its success depends heavily on initialization. This work addresses two primary questions: the global complexity of the ViterbiTrain problem and the mathematical principles behind optimal initialization.

Complexity Analysis

We establish that Viterbi training is strictly hard. It is fundamentally NP-hard to find the global maximum for the joint probability of strings and their Viterbi parses. This is proven through a polynomial-time reduction from the classic 3-SAT problem. By designing a specific, non-recursive PCFG and a single string of text, we demonstrate that finding the optimal Viterbi parse for this string perfectly corresponds to finding a satisfying boolean assignment for the 3-SAT formula.

Figure 1: The PCFG structure constructed for the reduction from 3-SAT, where the hierarchy of nodes corresponds to the logical structure of the boolean formula.

Furthermore, we extend this reduction to prove that no efficient algorithm can even approximate the ViterbiTrain objective function within a constant factor (specifically, any factor $> 1/2$) unless P=NP. These results also apply to maximizing the marginalized likelihood (standard EM) and, because the constructed grammar is non-recursive, to Hidden Markov Models (HMMs).

Initialization and Competitiveness

Given the intractability of the global optimum, the focus shifts to local optimization via Viterbi EM. We analyze the "worst-case" scenario for the true, unknown parameter distribution and prove that initializing the E-step by sampling trees uniformly at random minimizes this worst-case bound.

This uniform initialization strategy is not merely a heuristic; it is the optimal minimax strategy to minimize the worst-case distance to the true parameter distribution when no prior information is available. We derive a bound showing that uniform initialization is approximately $O(|N|L\lambda^2/n)$-competitive for Chomsky Normal Form (CNF) grammars. This provides a formal guarantee for PCFGs similar to the $O(\log k)$ competitiveness of the $k$-means++ initialization strategy for clustering.

Conclusion

Our findings formalize the computational difficulty of Viterbi training for PCFGs and HMMs, showing that global optimization and even close approximation are NP-hard. However, we provide a theoretical silver lining by justifying uniform-at-random initialization as a mathematically sound starting point for local search algorithms like Viterbi EM. Future work may explore whether these hardness results persist when grammar size is strictly bounded.

Summary updated

Abstract

We consider the search for a maximum likelihood assignment of hidden derivations and grammar weights for a probabilistic context-free grammar, the problem approximately solved by "Viterbi training." We show that solving and even approximating Viterbi training for PCFGs is NP-hard. We motivate the use of uniformat-random initialization for Viterbi EM as an optimal initializer in absence of further information about the correct model parameters, providing an approximate bound on the log-likelihood.
BibTeX
@inproceedings{cohen2010viterbi,
  author = {Shay B. Cohen and Noah A. Smith},
  title = {{Viterbi Training for PCFGs: Hardness Results and Competitiveness of Uniform Initialization}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2010},
}
Figure