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

Shay B. Cohen, Noah A. Smith

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