Paper: Viterbi Training Improves Unsupervised Dependency Parsing

ACL ID W10-2902
Title Viterbi Training Improves Unsupervised Dependency Parsing
Venue International Conference on Computational Natural Language Learning
Session Main Conference
Year 2010
Authors

We show that Viterbi (or “hard”) EM is well-suited to unsupervised grammar in- duction. It is more accurate than standard inside-outside re-estimation (classic EM), significantly faster, and simpler. Our ex- periments with Klein and Manning’s De- pendency Model with Valence (DMV) at- tain state-of-the-art performance — 44.8% accuracy on Section 23 (all sentences) of the Wall Street Journal corpus — without clever initialization; with a good initial- izer, Viterbi training improves to 47.9%. This generalizes to the Brown corpus, our held-out set, where accuracy reaches 50.8% — a 7.5% gain over previous best results. We find that classic EM learns bet- ter from short sentences but cannot cope with longer ones, where Viterbi thrives. However, we explain that both algorithms optimi...