Elamur Research⌕
☰
home / papers / 2008 / Efficient, Feature-based, Conditional Random Field Parsing

Efficient, Feature-based, Conditional Random Field Parsing

Paper · 2008 · Jenny Rose Finkel, Alex Kleeman and Christopher D. Manning

Summary

Constituency parsing in 2008 was still dominated by generative PCFG-style models. Earlier discriminative parsers that used dynamic programming either trained only on very short sentences or used no features at all. This paper presents a CRF-based parser (CRF-CFG) that scores each rule application with arbitrary, overlapping features. Those features can see the rule's categories, its span and split point, and the words of the sentence. Trees are normalized globally over all structures, and training maximizes conditional likelihood using inside-outside computations. Three engineering choices make training practical on the Penn treebank WSJ data:

  • stochastic gradient descent instead of batch optimization,
  • distributing per-tree computations across clients,
  • a boolean prefiltering pass that discards chart entries which cannot be part of a full parse.

On WSJ15 the parser reaches 90.9% F-score, a 14% relative error reduction, while running about two orders of magnitude faster than earlier models. It is also the first such parser trained and tested on sentences up to length 40, where it reaches 89.0% F1. The main lesson is that the payoff of discriminative training comes mostly from rich features, not from the training criterion alone.

Key points

  • WSJ15 (train and test on sentences of length ≤ 15): F-score of 90.9%, a 14% relative error reduction over prior work, with roughly 100× speedup.
  • Test sentences of length ≤ 40: the feature-based model gets 89.0% F1 and 37.3% exact match.
    • The generative baseline gets 82.8% F1, so this is a 36% relative error reduction.
    • A discriminative model without features gets only 84.8%.
    • On all test sentences, the feature-based model scores 88.0% F1.
  • SGD on mini-batches of about 15–30 sentences matched L-BFGS in parser accuracy while being much faster to train.
  • Chart prefiltering, with precomputed features cached to disk, speeds up the first pass over a sentence by about one third and later passes by close to ten times.
  • For comparison, Johnson (2001) trained on ATIS (1,088 training sentences) and found no gain from discriminative training. Taskar et al. (2004) needed months of training on WSJ15, and Turian & Melamed needed up to 5 days.

Interesting ideas

  • I1. Features on rule applications rather than rules. Scoring a rule together with its span length, split point and surrounding words lets the model use information that plain PCFGs ignore, such as constituent length. It also smooths unseen rules through features they share with known ones. The same factorization could help any structured predictor whose base units are too sparse.
  • I2. Boolean prefiltering plus caching. A cheap yes/no inside-outside pass identifies which chart cells are viable. Features are then computed only for those cells and saved to disk. This pays off whenever an expensive model has to iterate many times over the same inputs.
  • I3. Making unary rules well-defined. All allowed unary chains are collapsed into single rules, and stacked unaries over the same span are forbidden. This keeps the partition function finite, which is a useful trick for any grammar-based model that sums over all derivations.
  • I4. Questioning the slow optimizer. The authors show empirically that SGD gives the same final quality as L-BFGS. This suggests always benchmarking stochastic optimizers before accepting long batch training times for CRF-like objectives.
  • I5. Separating model change from feature change. The paper compares generative, featureless discriminative, and feature-based variants on the same data. This isolates where the gains actually come from, and it is a good evaluation template for any new model.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Stanford UniversityStanford · United States310 works · 284,480 citations

📚 Shelves 4 Computer Science · 9,086 works Artificial Intelligence · 8,889 works Arts and Humanities · 9,296 works Language and Linguistics · 9,206 works

Cite

Cite as Jenny Rose Finkel, Alex Kleeman and Christopher D. Manning. 2008. Efficient, Feature-based, Conditional Random Field Parsing. Proceedings of ACL-08: HLT.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{finkel2008efficient,
  title = {{Efficient, Feature-based, Conditional Random Field Parsing}},
  author = {Jenny Rose Finkel, Alex Kleeman and Christopher D. Manning},
  booktitle = {Proceedings of ACL-08: HLT},
  year = {2008},
  url = {https://aclanthology.org/P08-1109/}
}

References

22 references, 7 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Eugene Charniak and Mark Johnson. 2005. Coarse-to-fine n-best parsing and maxent discriminative reranking. In ACL 43, pages 173–180. our card
  2. Alexander Clark. 2000. Inducing syntactic categories by context distribution clustering. In Proc. of Conference on Computational Natural Language Learning, pages 91–94, Lisbon, Portugal. find
  3. Trevor Cohn and Philip Blunsom. 2005. Semantic role labelling with tree conditional random fields. In CoNLL 2005. find
  4. Michael Collins. 2000. Discriminative reranking for natural language parsing. In ICML 17, pages 175–182. our card
  5. Jay Earley. 1970. An efficient context-free parsing algorithm. Communications of the ACM, 6(8):451–455. find
  6. James Henderson. 2004. Discriminative training of a neural network statistical parser. In ACL 42, pages 96– 103. find
  7. Mark Johnson. 2001. Joint and conditional estimation of tagging and parsing models. In Meeting of the Association for Computational Linguistics, pages 314–321. find
  8. Florent Jousse, Rémi Gilleron, Isabelle Tellier, and Marc Tommasi. 2006. Conditional Random Fields for XML trees. In ECML Workshop on Mining and Learning in Graphs. find
  9. Dan Klein and Christopher D. Manning. 2003. Accurate unlexicalized parsing. In Proceedings of the Association of Computational Linguistics (ACL). our card
  10. John Lafferty, Andrew McCallum, and Fernando Pereira. 2001. Conditional Random Fields: Probabilistic models for segmenting and labeling sequence data. In ICML 2001, pages 282–289. Morgan Kaufmann, San Francisco, CA. find
  11. Dong C. Liu and Jorge Nocedal. 1989. On the limited memory BFGS method for large scale optimization. Math. Programming, 45(3, (Ser. B)):503–528. find
  12. Christopher D. Manning and Hinrich Schütze. 1999. Foundations of Statistical Natural Language Processing. The MIT Press, Cambridge, Massachusetts. find
  13. Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330. our card
  14. Andrew Ng and Michael Jordan. 2002. On discriminative vs. generative classifiers: A comparison of logistic regression and naive bayes. In Advances in Neural Information Processing Systems (NIPS). find
  15. Slav Petrov, Leon Barrett, Romain Thibaux, and Dan Klein. 2006. Learning accurate, compact, and interpretable tree annotation. In ACL 44/COLING 21, pages 433–440. our card
  16. Slav Petrov, Adam Pauls, and Dan Klein. 2007. Discriminative log-linear grammars with latent variables. In NIPS. find
  17. Adwait Ratnaparkhi. 1997. A linear observed time statistical parser based on maximum entropy models. In EMNLP 2, pages 1–10. our card
  18. Andreas Stolcke. 1995. An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21:165– 202. our card
  19. Ben Taskar, Dan Klein, Michael Collins, Daphne Koller, and Christopher D. Manning. 2004. Max-margin parsing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP). find
  20. Joseph Turian and I. Dan Melamed. 2006. Advances in discriminative parsing. In ACL 44, pages 873–880. find
  21. Joseph Turian, Ben Wellington, and I. Dan Melamed. 2007. Scalable discriminative learning for natural language parsing and translation. In Advances in Neural Information Processing Systems 19, pages 1409–1416. MIT Press. find
  22. S. V. N. Vishwanathan, Nichol N. Schraudolph, Mark W. Schmidt, and Kevin P. Murphy. 2006. Accelerated training of conditional random fields with stochastic gradient methods. In ICML 23, pages 969–976. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/finkel-2008-efficient-feature-based-conditional-random/