---
title: "Improved Inference for Unlexicalized Parsing — Petrov 2007"
description: "The paper addresses inference for unlexicalized, hierarchically state-split PCFGs (the Berkeley-style latent-annotation grammars)."
authors: ["Slav Petrov", "Dan Klein"]
year: 2007
venue: "Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference"
source: "https://aclanthology.org/N07-1051/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/petrov-2007-improved-inference-unlexicalized-parsing/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/petrov-2007-improved-inference-unlexicalized-parsing/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2007](https://md.research.elamur.ai/free/en/papers/2007/) / Improved Inference for Unlexicalized Parsing

# Improved Inference for Unlexicalized Parsing

**Authors:** [Slav Petrov](https://md.research.elamur.ai/free/en/authors/slav-petrov/), [Dan Klein](https://md.research.elamur.ai/free/en/authors/dan-klein/) · **Year:** 2007 · **Venue:** Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/N07-1051/) · [PDF](https://aclanthology.org/N07-1051.pdf) · [OpenAlex](https://openalex.org/W108437174)

**Citations:** 596 citations (openalex-snapshot · 2026-10-14) · [345](#cited-by) in our library, of the 140884 papers whose bibliographies we read

## Summary
The paper addresses inference for unlexicalized, hierarchically state-split PCFGs (the Berkeley-style latent-annotation grammars). These grammars are very accurate, but they are slow to parse with. Selecting the best output tree is also tricky, because the model scores derivations over split symbols while evaluation only sees the coarse treebank labels. The authors make three contributions:

- **Hierarchical coarse-to-fine pruning.** The parser runs through the grammar's own earlier splitting stages, using each stage to prune the next. Those intermediate grammars are re-estimated directly from the final PCFG rather than from a treebank.
- **Comparison of parse-selection objectives.** Several objectives are compared in terms of risk minimization, including Viterbi, sampled reranking, variational, max-rule-sum and max-rule-product.
- **Multilingual and cross-domain experiments.** These cover English, German and Chinese with no language-specific tuning.

The resulting parser runs up to 100 times faster than the unpruned baseline with no accuracy loss. It gives the best reported generative results for German and Chinese. This shows that automatically learned latent grammars carry over to other languages without hand engineering.

## Key points
- **Speed:** pruning with projected grammars G0…G5 gives speedups of up to 100× over the baseline PCFG parser, with no drop in test accuracy. Pruning thresholds are tuned automatically on held-out data.
- **Projection estimation:** projected grammars are estimated from expected rule and symbol counts under the final grammar. The counts come from an iterative fixpoint computation that converges in about 25 iterations and takes only seconds.
- **Parse-selection objectives:**
  - Max-Rule-Product gives the best F1 on development data (91.2, versus 89.5 for the Viterbi derivation).
  - For exact match, reranking an n-best list by likelihood works best (41.7% exact).
- **Test results:**
  - English (Penn Treebank WSJ, all sentences): LP/LR 90.2/89.9. Only the Charniak and Johnson (2005) reranker does better.
  - German (Skut et al., 1997, NEGRA): about 80.1 F1, versus 76.3 for Dubey (2005).
  - Chinese (Xue et al., 2002, Penn Chinese Treebank): competitive with Chiang et al. (2002).
- **Domain shift:** on the Brown corpus, accuracy starts to fall after the 5th split iteration while WSJ accuracy keeps rising, which points to some overfitting to WSJ.

## Interesting ideas
- **Derive pruning models from the final model.** The coarse pruning grammars are obtained by collapsing the final grammar's own split history, so no treebank is needed at decode time. This could transfer to any large latent-variable model where cheap approximations of it are useful for filtering the search space.
- **Fit a model to another model's distribution.** Coarse parameters are estimated by minimizing KL divergence to the full grammar's tree distribution, which amounts to expected counts in place of observed counts. This is a general recipe for compressing or distilling a model when the original training data is unavailable or the model has drifted away from it.
- **Fixpoint iteration with a readable meaning.** Expected symbol counts are computed by repeated propagation, where each step adds one more level of tree depth. Iterations like this are cheap and interpretable for any recursive generative model.
- **Match the decoding objective to the metric.** Reranking by likelihood helps exact match, while rule-posterior dynamic programming helps F1. When evaluating, it is worth picking the inference criterion according to the target measure rather than defaulting to Viterbi.
- **Fixed hyperparameters across languages.** Using the same merge rate and smoothing settings for every language tests whether a method really generalizes. This is a useful protocol for evaluating tools on lower-resource languages such as Ukrainian.

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

Fields: [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/)

Topics: [Treebanks](https://md.research.elamur.ai/free/en/topics/treebanks/)

## Cited by

Cited by

345 papers of our library cite it (of the 140884 whose bibliographies we read); 22 of them have a page here, 323 not yet.

- [Task-oriented Evaluation of Syntactic Parsers and Their Representations](https://md.research.elamur.ai/free/en/papers/aclbulk-2008-miyao-task-oriented-evaluation-syntactic-parsers/)
- [Unbounded Dependency Recovery for Parser Evaluation](https://md.research.elamur.ai/free/en/papers/aclbulk-2009-rimell-unbounded-dependency-recovery-parser-evaluation/)
- ["cba to check the spelling": Investigating Parser Performance on Discussion Forum Posts](https://md.research.elamur.ai/free/en/papers/aclbulk-2010-foster-cba-check-spelling-investigating-parser/)
- [Morphological Features for Parsing Morphologically-rich Languages: A Case of Arabic](https://md.research.elamur.ai/free/en/papers/aclbulk-2011-dehdari-morphological-features-parsing-morphologically-rich/)
- [Parser Showdown at the Wall Street Corral: An Empirical Investigation of Error Types in Parser Output](https://md.research.elamur.ai/free/en/papers/aclbulk-2012-kummerfeld-parser-showdown-wall-street-corral/)
- [Syntactic annotation of spontaneous speech: application to call-center conversation data](https://md.research.elamur.ai/free/en/papers/bazillon-2012-syntactic-annotation-spontaneous-speech-application/)
- [A Transition-Based System for Joint Part-of-Speech Tagging and Labeled Non-Projective Dependency Parsing](https://md.research.elamur.ai/free/en/papers/bohnet-2012-transition-based-system-joint-part/)
- [Improved Neural Machine Translation with a Syntax-Aware Encoder and Decoder](https://md.research.elamur.ai/free/en/papers/chen-2017-improved-neural-machine-translation-syntax/)
- [Word Segmentation, Unknown-word Resolution, and Morphological Agreement in a Hebrew Parsing System](https://md.research.elamur.ai/free/en/papers/cl-2013-goldberg-word-segmentation-unknown-word-resolution/)
- [Translation Divergences in Chinese–English Machine Translation: An Empirical Investigation](https://md.research.elamur.ai/free/en/papers/deng-2017-translation-divergences-chinese-english-machine/)
- [Learning a Lexical Simplifier Using Wikipedia](https://md.research.elamur.ai/free/en/papers/horn-2014-learning-lexical-simplifier-wikipedia/)
- [Bootstrapping coreference resolution using word associations](https://md.research.elamur.ai/free/en/papers/kobdani-2011-bootstrapping-coreference-resolution-word-associations/)
- [Parsing Any Domain English text to CoNLL dependencies](https://md.research.elamur.ai/free/en/papers/kolachina-2012-parsing-any-domain-english-text/)
- [Transferring Coreference Resolvers with Posterior Regularization](https://md.research.elamur.ai/free/en/papers/martins-2015-transferring-coreference-resolvers-posterior-regularization/)
- [A Crowdsourced Corpus of Multiple Judgments and Disagreement on Anaphoric Interpretation](https://md.research.elamur.ai/free/en/papers/poesio-2019-crowdsourced-corpus-multiple-judgments-disagreement/)
- [Learning synchronous context-free grammars with multiple specialised non-terminals for hierarchical phrase-based translation](https://md.research.elamur.ai/free/en/papers/sanchez-2020-martinez-learning-synchronous-context-free-grammars/)
- [A Minimal Span-Based Neural Constituency Parser](https://md.research.elamur.ai/free/en/papers/stern-2017-minimal-span-based-neural-constituency/)
- [Conundrums in Noun Phrase Coreference Resolution: Making Sense of the State-of-the-Art](https://md.research.elamur.ai/free/en/papers/stoyanov-2009-conundrums-noun-phrase-coreference-resolution/)
- [Coreference Resolution with Reconcile](https://md.research.elamur.ai/free/en/papers/stoyanov-2010-coreference-resolution-reconcile/)
- [On Improving the Accuracy of Readability Classification using Insights from Second Language Acquisition](https://md.research.elamur.ai/free/en/papers/vajjala-2012-improving-accuracy-readability-classification-insights/)
- [Not an Interlingua, But Close: Comparison of English AMRs to Chinese and Czech](https://md.research.elamur.ai/free/en/papers/xue-2014-not-interlingua-but-close-comparison/)
- [Fast and Accurate Shift-Reduce Constituent Parsing](https://md.research.elamur.ai/free/en/papers/zhu-2013-fast-accurate-shift-reduce-constituent/)

## Cite

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

```bibtex
@inproceedings{petrov2007improved,
  title = {{Improved Inference for Unlexicalized Parsing}},
  author = {Petrov, Slav and Klein, Dan},
  booktitle = {Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference},
  year = {2007},
  url = {https://aclanthology.org/N07-1051/}
}
```

- [← previous Identification and Resolution of Chinese Zero Pronouns: A Machine Learning Approach](https://md.research.elamur.ai/free/en/papers/zhao-2007-identification-resolution-chinese-zero-pronouns/)
- [next → Improving Statistical Machine Translation Using Word Sense Disambiguation](https://md.research.elamur.ai/free/en/papers/carpuat-2007-improving-statistical-machine-translation-word/)
- [↑ back to papers of 2007](https://md.research.elamur.ai/free/en/papers/2007/)

## References

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

1. E. Charniak and M. Johnson. 2005. Coarse-to-Fine N-Best Parsing and MaxEnt Discriminative Reranking. In ACL’05. [find](https://scholar.google.com/scholar?q=E%2E+Charniak+and+M%2E+Johnson%2E+2005%2E+Coarse%2Dto%2DFine+N%2DBest+Parsing+and+MaxEnt+Discriminative+Reranking%2E+In+ACL%E2%80%9905%2E) [our card](https://md.research.elamur.ai/free/en/papers/narrative-2005-charniak-coarse-fine-n-best-parsing/)
2. E. Charniak, S. Goldwater, and M. Johnson. 1998. Edge-based best-first chart parsing. 6 th Wkshop on Very Large Corpora. 4 This is the performance of the updated reranking parser available at [http://www.cog.brown.edu/mj/software.htm](http://www.cog.brown.edu/mj/software.htm) 5 Sun and Jurafsky (2004) report even better performance on this da… [↗](http://www.cog.brown.edu/mj/software.htm)
3. E. Charniak, M. Johnson, et al. 2006. Multi-level coarse-to-fine PCFG Parsing. In HLT-NAACL ’06. [find](https://scholar.google.com/scholar?q=E%2E+Charniak%2C+M%2E+Johnson%2C+et+al%2E+2006%2E+Multi%2Dlevel+coarse%2Dto%2Dfine+PCFG+Parsing%2E+In+HLT%2DNAACL+%E2%80%9906%2E)
4. Z. Chi. 1999. Statistical properties of probabilistic context-free grammars. In Computational Linguistics. [find](https://scholar.google.com/scholar?q=Z%2E+Chi%2E+1999%2E+Statistical+properties+of+probabilistic+context%2Dfree+grammars%2E+In+Computational+Linguistics%2E)
5. M. Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, U. of Pennsylvania. [find](https://scholar.google.com/scholar?q=M%2E+Collins%2E+1999%2E+Head%2DDriven+Statistical+Models+for+Natural+Language+Parsing%2E+Ph%2ED%2E+thesis%2C+U%2E+of+Pennsylvania%2E)
6. A. Corazza and G. Satta. 2006. Cross-entropy and estimation of probabilistic context-free grammars. In HLT-NAACL ’06. [find](https://scholar.google.com/scholar?q=A%2E+Corazza+and+G%2E+Satta%2E+2006%2E+Cross%2Dentropy+and+estimation+of+probabilistic+context%2Dfree+grammars%2E+In+HLT%2DNAACL+%E2%80%9906%2E)
7. B. Cowan and M. Collins. 2005. Morphology and reranking for the statistical parsing of Spanish. In HLT-EMNLP ’05. [find](https://scholar.google.com/scholar?q=B%2E+Cowan+and+M%2E+Collins%2E+2005%2E+Morphology+and+reranking+for+the+statistical+parsing+of+Spanish%2E+In+HLT%2DEMNLP+%E2%80%9905%2E)
8. M. Dreyer and J. Eisner. 2006. Better informed training of latent syntactic features. In EMNLP ’06, pages 317–326. [find](https://scholar.google.com/scholar?q=M%2E+Dreyer+and+J%2E+Eisner%2E+2006%2E+Better+informed+training+of+latent+syntactic+features%2E+In+EMNLP+%E2%80%9906%2C+pages+317%E2%80%93326%2E)
9. A. Dubey. 2005. What to do when lexicalization fails: parsing German with suffix analysis and smoothing. In ACL ’05. [find](https://scholar.google.com/scholar?q=A%2E+Dubey%2E+2005%2E+What+to+do+when+lexicalization+fails%3A+parsing+German+with+suffix+analysis+and+smoothing%2E+In+ACL+%E2%80%9905%2E)
10. J. Finkel, C. Manning, and A. Ng. 2006. Solving the problem of cascading errors: approximate Bayesian inference for lingusitic annotation pipelines. In EMNLP ’06. [find](https://scholar.google.com/scholar?q=J%2E+Finkel%2C+C%2E+Manning%2C+and+A%2E+Ng%2E+2006%2E+Solving+the+problem+of+cascading+errors%3A+approximate+Bayesian+inference+for+lingusitic+annotation+pipelines%2E+In+EMNLP+%E2%80%9906%2E)
11. D. Gildea. 2001. Corpus variation and parser performance. EMNLP ’01, pages 167–202. [find](https://scholar.google.com/scholar?q=D%2E+Gildea%2E+2001%2E+Corpus+variation+and+parser+performance%2E+EMNLP+%E2%80%9901%2C+pages+167%E2%80%93202%2E) [our card](https://md.research.elamur.ai/free/en/papers/aclbulk-2001-gildea-corpus-variation-parser-performance/)
12. J. Goodman. 1996. Parsing algorithms and metrics. ACL ’96. [find](https://scholar.google.com/scholar?q=J%2E+Goodman%2E+1996%2E+Parsing+algorithms+and+metrics%2E+ACL+%E2%80%9996%2E)
13. M. Johnson, T. Griffiths, and S. Goldwater. 2007. Bayesian inference for PCFGs via Markov Chain Monte Carlo. In HLT-NAACL ’07. [find](https://scholar.google.com/scholar?q=M%2E+Johnson%2C+T%2E+Griffiths%2C+and+S%2E+Goldwater%2E+2007%2E+Bayesian+inference+for+PCFGs+via+Markov+Chain+Monte+Carlo%2E+In+HLT%2DNAACL+%E2%80%9907%2E) [our card](https://md.research.elamur.ai/free/en/papers/johnson-2007-bayesian-inference-pcfgs-markov-chain/)
14. D. Klein and C. Manning. 2003. Accurate unlexicalized parsing. In ACL ’03, pages 423–430. [find](https://scholar.google.com/scholar?q=D%2E+Klein+and+C%2E+Manning%2E+2003%2E+Accurate+unlexicalized+parsing%2E+In+ACL+%E2%80%9903%2C+pages+423%E2%80%93430%2E) [our card](https://md.research.elamur.ai/free/en/papers/aclbulk-2003-klein-accurate-unlexicalized-parsing/)
15. R. Levy and C. Manning. 2003. Is it harder to parse Chinese, or the Chinese treebank? In ACL ’03, pages 439–446. [find](https://scholar.google.com/scholar?q=R%2E+Levy+and+C%2E+Manning%2E+2003%2E+Is+it+harder+to+parse+Chinese%2C+or+the+Chinese+treebank%3F+In+ACL+%E2%80%9903%2C+pages+439%E2%80%93446%2E)
16. M. Marcus, B. Santorini, and M. Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. In Computational Linguistics. [find](https://scholar.google.com/scholar?q=M%2E+Marcus%2C+B%2E+Santorini%2C+and+M%2E+Marcinkiewicz%2E+1993%2E+Building+a+large+annotated+corpus+of+English%3A+The+Penn+Treebank%2E+In+Computational+Linguistics%2E) [our card](https://md.research.elamur.ai/free/en/papers/bank-1993-marcus-building-large-annotated-corpus-english/)
17. T. Matsuzaki, Y. Miyao, and J. Tsujii. 2005. Probabilistic CFG with latent annotations. In ACL ’05, pages 75–82. [find](https://scholar.google.com/scholar?q=T%2E+Matsuzaki%2C+Y%2E+Miyao%2C+and+J%2E+Tsujii%2E+2005%2E+Probabilistic+CFG+with+latent+annotations%2E+In+ACL+%E2%80%9905%2C+pages+75%E2%80%9382%2E) [our card](https://md.research.elamur.ai/free/en/papers/matsuzaki-2005-probabilistic-cfg-latent-annotations/)
18. D. McClosky, E. Charniak, and M. Johnson. 2006. Reranking and self-training for parser adaptation. In COLING-ACL’06. [find](https://scholar.google.com/scholar?q=D%2E+McClosky%2C+E%2E+Charniak%2C+and+M%2E+Johnson%2E+2006%2E+Reranking+and+self%2Dtraining+for+parser+adaptation%2E+In+COLING%2DACL%E2%80%9906%2E) [our card](https://md.research.elamur.ai/free/en/papers/aclbulk-2006-mcclosky-reranking-self-training-parser-adaptation/)
19. M. Mohri and B. Roark. 2006. Probabilistic context-free grammar induction based on structural zeros. In HLT-NAACL ’06. [find](https://scholar.google.com/scholar?q=M%2E+Mohri+and+B%2E+Roark%2E+2006%2E+Probabilistic+context%2Dfree+grammar+induction+based+on+structural+zeros%2E+In+HLT%2DNAACL+%E2%80%9906%2E)
20. M.-J. Nederhof. 2005. A general technique to train language models on language models. In Computational Linguistics. [find](https://scholar.google.com/scholar?q=M%2E%2DJ%2E+Nederhof%2E+2005%2E+A+general+technique+to+train+language+models+on+language+models%2E+In+Computational+Linguistics%2E)
21. S. Petrov, L. Barrett, R. Thibaux, and D. Klein. 2006. Learning accurate, compact, and interpretable tree annotation. In COLING-ACL ’06, pages 443–440. [find](https://scholar.google.com/scholar?q=S%2E+Petrov%2C+L%2E+Barrett%2C+R%2E+Thibaux%2C+and+D%2E+Klein%2E+2006%2E+Learning+accurate%2C+compact%2C+and+interpretable+tree+annotation%2E+In+COLING%2DACL+%E2%80%9906%2C+pages+443%E2%80%93440%2E) [our card](https://md.research.elamur.ai/free/en/papers/aclbulk-2006-petrov-learning-accurate-compact-interpretable-tree/)
22. K. Sima’an. 1992. Computatoinal complexity of probabilistic disambiguation. Grammars, 5:125–151. [find](https://scholar.google.com/scholar?q=K%2E+Sima%E2%80%99an%2E+1992%2E+Computatoinal+complexity+of+probabilistic+disambiguation%2E+Grammars%2C+5%3A125%E2%80%93151%2E)
23. W. Skut, B. Krenn, T. Brants, and H. Uszkoreit. 1997. An annotation scheme for free word order languages. In Conference on Applied Natural Language Processing. [find](https://scholar.google.com/scholar?q=W%2E+Skut%2C+B%2E+Krenn%2C+T%2E+Brants%2C+and+H%2E+Uszkoreit%2E+1997%2E+An+annotation+scheme+for+free+word+order+languages%2E+In+Conference+on+Applied+Natural+Language+Processing%2E) [our card](https://md.research.elamur.ai/free/en/papers/skut-1997-annotation-scheme-free-word-order/)
24. M. Steedman. 2000. The Syntactic Process. The MIT Press, Cambridge, Massachusetts. [find](https://scholar.google.com/scholar?q=M%2E+Steedman%2E+2000%2E+The+Syntactic+Process%2E+The+MIT+Press%2C+Cambridge%2C+Massachusetts%2E)
25. H. Sun and D. Jurafsky. 2004. Shallow semantic parsing of Chinese. In HLT-NAACL ’04, pages 249–256. [find](https://scholar.google.com/scholar?q=H%2E+Sun+and+D%2E+Jurafsky%2E+2004%2E+Shallow+semantic+parsing+of+Chinese%2E+In+HLT%2DNAACL+%E2%80%9904%2C+pages+249%E2%80%93256%2E)
26. R. Sutton and A. Barto. 1998. Reinforcement Learning: An Introduction. MIT Press. [find](https://scholar.google.com/scholar?q=R%2E+Sutton+and+A%2E+Barto%2E+1998%2E+Reinforcement+Learning%3A+An+Introduction%2E+MIT+Press%2E)
27. I. Titov and J. Henderson. 2006. Loss minimization in parse reranking. In EMNLP ’06, pages 560–567. [find](https://scholar.google.com/scholar?q=I%2E+Titov+and+J%2E+Henderson%2E+2006%2E+Loss+minimization+in+parse+reranking%2E+In+EMNLP+%E2%80%9906%2C+pages+560%E2%80%93567%2E)
28. K. Vijay-Shanker and A. Joshi. 1985. Some computational properties of Tree Adjoining Grammars. In ACL ’85. [find](https://scholar.google.com/scholar?q=K%2E+Vijay%2DShanker+and+A%2E+Joshi%2E+1985%2E+Some+computational+properties+of+Tree+Adjoining+Grammars%2E+In+ACL+%E2%80%9985%2E)
29. N. Xue, F.-D. Chiou, and M. Palmer. 2002. Building a large scale annotated Chinese corpus. In COLING ’02. [find](https://scholar.google.com/scholar?q=N%2E+Xue%2C+F%2E%2DD%2E+Chiou%2C+and+M%2E+Palmer%2E+2002%2E+Building+a+large+scale+annotated+Chinese+corpus%2E+In+COLING+%E2%80%9902%2E)