--- title: "Inside-Outside Reestimation From Partially — Pereira 1992" description: "Stochastic context-free grammars (SCFGs) can model hierarchical sentence structure, which n-grams and HMMs cannot." authors: ["Fernando Pereira", "Yves Schabes"] year: 1992 venue: "30th Annual Meeting of the Association for Computational Linguistics" source: "https://aclanthology.org/P92-1017/" doi: "10.3115/981967.981984" 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/pereira-1992-inside-outside-reestimation-partially-bracketed/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/pereira-1992-inside-outside-reestimation-partially-bracketed/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1992](https://md.research.elamur.ai/free/en/papers/1992/) / Inside-Outside Reestimation From Partially Bracketed Corpora # Inside-Outside Reestimation From Partially Bracketed Corpora **Authors:** [Fernando Pereira](https://md.research.elamur.ai/free/en/authors/fernando-pereira/), [Yves Schabes](https://md.research.elamur.ai/free/en/authors/yves-schabes/) · **Year:** 1992 · **Venue:** 30th Annual Meeting of the Association for Computational Linguistics · **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/P92-1017/) · [PDF](https://aclanthology.org/P92-1017.pdf) · [DOI 10.3115/981967.981984](https://doi.org/10.3115/981967.981984) · [OpenAlex](https://openalex.org/W2439178139) **Citations:** 284 citations (openalex-snapshot · 2026-10-14) · [104](#cited-by) in our library, of the 140884 papers whose bibliographies we read ## Summary Stochastic context-free grammars (SCFGs) can model hierarchical sentence structure, which n-grams and HMMs cannot. Training them from raw text with Baker's inside-outside algorithm has given disappointing results: it is slow, it converges poorly as the number of nonterminals grows, and the structures it learns often disagree with linguistic intuitions. Pereira and Schabes modify the algorithm to use whatever constituent brackets a corpus provides. Partial brackets restrict which spans may count as constituents. Inside and outside probabilities for spans that cross a bracket are set to zero, and only derivations compatible with the bracketing contribute to rule reestimation. With no brackets, the method is the same as the original algorithm. Experiments used formal languages and part-of-speech strings from the ATIS corpus in the Penn Treebank. Training on bracketed data converged faster and produced linguistically plausible constituents. Grammars learned this way bracketed over 90% of test-set constituents correctly. The approach shows that a modest amount of human structural annotation can steer unsupervised grammar induction and can also make training cheaper. ## Key points - The standard inside-outside algorithm costs O(n³|w|³) per sentence for n nonterminals, while HMM training costs O(s²|w|). - A bracketing is a set of non-overlapping spans. A derivation is compatible with it when every symbol's span is valid with respect to the brackets. - With a full binary-branching bracketing, each training step drops to linear time in sentence length, so a whole iteration is linear in corpus size. - Over 90% test-set bracketing accuracy was achieved on hand-parsed ATIS part-of-speech sequences from the Penn Treebank. - Grammars trained on raw text (G_R) produced spurious constituents such as pronoun+verb or noun+final punctuation. Grammars trained on bracketed text (G_B) avoided these, and their cross-entropy fell faster early in training. ## Interesting ideas - **Constraint masking in dynamic programming:** a 0/1 indicator over spans removes incompatible analyses without changing the core recurrences. The same trick could inject partial supervision into other chart-based EM or CRF training, such as weakly annotated Ukrainian treebank data. - **Graceful degradation across supervision levels:** one algorithm covers everything from fully parsed to fully raw data. This lets projects mix corpora with uneven annotation instead of discarding the partially labeled parts. - **Supervision as a speed-up:** more annotation also prunes the search space and cuts training cost, not only accuracy loss. This argues for cheap partial bracketing even when full trees are too expensive to produce. - **Learned vs. stipulated constraints:** earlier work hard-coded part-of-speech pairs that may never form a low-level constituent. Here the constraints come from annotated examples, which is a more portable way to encode linguistic knowledge for new languages. - **Diagnosing distributional artifacts:** comparing induced bracketings with and without supervision exposes structures that simply follow frequent co-occurrence, such as noun plus punctuation. This makes a useful qualitative check for any unsupervised structure learner. *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/) · [Part-of-speech tagging](https://md.research.elamur.ai/free/en/topics/part-of-speech-tagging/) ## Cited by Cited by 104 papers of our library cite it (of the 140884 whose bibliographies we read); 11 of them have a page here, 93 not yet. - [Extending a Parser to Distant Domains Using a Few Dozen Partially Annotated Examples](https://md.research.elamur.ai/free/en/papers/acl-2018-joshi-extending-parser-distant-domains-few/) - [Efficient Second-Order TreeCRF for Neural Dependency Parsing](https://md.research.elamur.ai/free/en/papers/acl-2020-zhang-efficient-second-order-treecrf-neural/) - [Learning Accurate, Compact, and Interpretable Tree Annotation](https://md.research.elamur.ai/free/en/papers/aclbulk-2006-petrov-learning-accurate-compact-interpretable-tree/) - [A Dependency Parser for Tweets](https://md.research.elamur.ai/free/en/papers/aclbulk-2014-kong-dependency-parser-tweets/) - [Building a Large Annotated Corpus of English: The Penn Treebank](https://md.research.elamur.ai/free/en/papers/bank-1993-marcus-building-large-annotated-corpus-english/) - [Feature-Rich Translation by Quasi-Synchronous Lattice Parsing](https://md.research.elamur.ai/free/en/papers/gimpel-2009-feature-rich-translation-quasi-synchronous/) - [A Generative Constituent-Context Model for Improved Grammar Induction](https://md.research.elamur.ai/free/en/papers/klein-2002-generative-constituent-context-model-improved/) - [Probabilistic CFG with Latent Annotations](https://md.research.elamur.ai/free/en/papers/matsuzaki-2005-probabilistic-cfg-latent-annotations/) - [Parsing the Wall Street Journal using a Lexical-Functional Grammar and Discriminative Estimation Techniques](https://md.research.elamur.ai/free/en/papers/riezler-2002-parsing-wall-street-journal-lexical/) - [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/) - [Stochastic Inversion Transduction Grammars and Bilingual Parsing of Parallel Corpora](https://md.research.elamur.ai/free/en/papers/wu-1997-stochastic-inversion-transduction-grammars-bilingual/) ## Cite The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{pereira1992inside, title = {{Inside-Outside Reestimation From Partially Bracketed Corpora}}, author = {Pereira, Fernando and Schabes, Yves}, booktitle = {30th Annual Meeting of the Association for Computational Linguistics}, year = {1992}, doi = {10.3115/981967.981984}, url = {https://doi.org/10.3115/981967.981984} } ``` - [← previous From Cogram to Alcogram: Toward a Controlled English Grammar Checker](https://md.research.elamur.ai/free/en/papers/adriaens-1992-cogram-alcogram-controlled-english-grammar/) - [next → Parameterization of the Interlingua in Machine Translation](https://md.research.elamur.ai/free/en/papers/dorr-1992-parameterization-interlingua-machine-translation/) - [↑ back to papers of 1992](https://md.research.elamur.ai/free/en/papers/1992/) ## References 12 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. J.K. Baker. 1979. Trainable grammars for speech recognition. In Jared J. Wolf and Dennis H. Klatt, editors, Speech communication papers presented at the 97 ~h Meeting of the Acoustical Society of America, MIT, Cambridge, MA, June. [find](https://scholar.google.com/scholar?q=J%2EK%2E+Baker%2E+1979%2E+Trainable+grammars+for+speech+recognition%2E+In+Jared+J%2E+Wolf+and+Dennis+H%2E+Klatt%2C+editors%2C+Speech+communication+papers+presented+at+the+97+%7Eh+Meeting+of+the+Acoustical+Society+of+Amer) 2. E. Black, S. Abney, D. Flickenger, R. Grishman, P. Harrison, D. Hindle, R. Ingria, F. Jelinek, J. Klavans, M. Liberman, M. Marcus, S. Roukos, B. Santorini, and T. Strzalkowski. 1991. A procedure for quantitatively comparing the syntactic coverage of english grammars. In DARPA Speech and Natural Lang… [find](https://scholar.google.com/scholar?q=E%2E+Black%2C+S%2E+Abney%2C+D%2E+Flickenger%2C+R%2E+Grishman%2C+P%2E+Harrison%2C+D%2E+Hindle%2C+R%2E+Ingria%2C+F%2E+Jelinek%2C+J%2E+Klavans%2C+M%2E+Liberman%2C+M%2E+Marcus%2C+S%2E+Roukos%2C+B%2E+Santorini%2C+and+T%2E+Strzalkowski%2E+1991%2E+A+procedure+for+q) 3. T. Booth. 1969. Probabilistic representation of formal languages. In Tenth Annual IEEE Symposium on Switching and Automata Theory, October. [find](https://scholar.google.com/scholar?q=T%2E+Booth%2E+1969%2E+Probabilistic+representation+of+formal+languages%2E+In+Tenth+Annual+IEEE+Symposium+on+Switching+and+Automata+Theory%2C+October%2E) 4. Eric Brill, David Magerman, Mitchell Marcus, and Beatrice Santorini. 1990. Deducing linguistic structure from the statistics of large corpora. In DARPA Speech and Natural Language Workshop. Morgan Kaufmann, Hidden Valley, Pennsylvania, JuDe. [find](https://scholar.google.com/scholar?q=Eric+Brill%2C+David+Magerman%2C+Mitchell+Marcus%2C+and+Beatrice+Santorini%2E+1990%2E+Deducing+linguistic+structure+from+the+statistics+of+large+corpora%2E+In+DARPA+Speech+and+Natural+Language+Workshop%2E+Morgan+Kau) 5. T. Fujisaki, F. Jelinek, J. Cocke, E. Black, and T. Nishino. 1989. A probabilistic parsing method for sentence disambiguation. In Proceedings of the International Workshop on Parsing Technologies, Pittsburgh, August. [find](https://scholar.google.com/scholar?q=T%2E+Fujisaki%2C+F%2E+Jelinek%2C+J%2E+Cocke%2C+E%2E+Black%2C+and+T%2E+Nishino%2E+1989%2E+A+probabilistic+parsing+method+for+sentence+disambiguation%2E+In+Proceedings+of+the+International+Workshop+on+Parsing+Technologies%2C+Pit) 6. Charles T. Hemphill, John J. Godfrey, and George R. Doddington. 1990. The ATIS spoken language systems pilot corpus. In DARPA Speech and Natural Language Workshop, Hidden Valley, Pennsylvania, June. [find](https://scholar.google.com/scholar?q=Charles+T%2E+Hemphill%2C+John+J%2E+Godfrey%2C+and+George+R%2E+Doddington%2E+1990%2E+The+ATIS+spoken+language+systems+pilot+corpus%2E+In+DARPA+Speech+and+Natural+Language+Workshop%2C+Hidden+Valley%2C+Pennsylvania%2C+June%2E) 7. F. Jelinek, J. D. Lafferty, and R. L. Mercer. 1990. Basic methods of probabilistic context free grammars. Technical Report RC 16374 (72684), IBM, Yorktown Heights, New York 10598. [find](https://scholar.google.com/scholar?q=F%2E+Jelinek%2C+J%2E+D%2E+Lafferty%2C+and+R%2E+L%2E+Mercer%2E+1990%2E+Basic+methods+of+probabilistic+context+free+grammars%2E+Technical+Report+RC+16374+%2872684%29%2C+IBM%2C+Yorktown+Heights%2C+New+York+10598%2E) 8. Frederick Jelinek, Robert L. Mercer, and Salim Roukos. 1992. Principles of lexical language modeling for speech recognition. In Sadaoki Furui and M. Mohan Sondhi, editors, Advances in Speech Signal Processing, pages 651-699. Marcel Dekker, Inc., New York, New York. [find](https://scholar.google.com/scholar?q=Frederick+Jelinek%2C+Robert+L%2E+Mercer%2C+and+Salim+Roukos%2E+1992%2E+Principles+of+lexical+language+modeling+for+speech+recognition%2E+In+Sadaoki+Furui+and+M%2E+Mohan+Sondhi%2C+editors%2C+Advances+in+Speech+Signal+Pr) 9. K. Lari and S. J. Young. 1990. The estimation of stochastic context-free grammars using the Inside-Outside algorithm. Computer Speech and Language, 4:35-56. [find](https://scholar.google.com/scholar?q=K%2E+Lari+and+S%2E+J%2E+Young%2E+1990%2E+The+estimation+of+stochastic+context%2Dfree+grammars+using+the+Inside%2DOutside+algorithm%2E+Computer+Speech+and+Language%2C+4%3A35%2D56%2E) 10. K. Lari and S. J. Young. 1991. Applications of stochastic context-free grammars using the Inside-Outside algorithm. Computer Speech and Language, 5:237-257. [find](https://scholar.google.com/scholar?q=K%2E+Lari+and+S%2E+J%2E+Young%2E+1991%2E+Applications+of+stochastic+context%2Dfree+grammars+using+the+Inside%2DOutside+algorithm%2E+Computer+Speech+and+Language%2C+5%3A237%2D257%2E) 11. David Magerman and Mitchell Marcus. 1990. Parsing a natural language using mutual information statistics. In AAAI-90, Boston, MA. [find](https://scholar.google.com/scholar?q=David+Magerman+and+Mitchell+Marcus%2E+1990%2E+Parsing+a+natural+language+using+mutual+information+statistics%2E+In+AAAI%2D90%2C+Boston%2C+MA%2E) 12. Yves Schabes. 1992. Stochastic lexicalized tree-adjoining grammars. In COLING 92. Forthcoming. [find](https://scholar.google.com/scholar?q=Yves+Schabes%2E+1992%2E+Stochastic+lexicalized+tree%2Dadjoining+grammars%2E+In+COLING+92%2E+Forthcoming%2E)