More Web Proxy on the site http://driver.im/

Article

Free access

Efficiency, robustness and accuracy in Picky chart parsing

Authors:

David M. Magerman,

Carl WeirAuthors Info & Claims

ACL '92: Proceedings of the 30th annual meeting on Association for Computational Linguistics

Pages 40 - 47

https://doi.org/10.3115/981967.981973

Published: 28 June 1992 Publication History

Abstract

This paper describes Picky, a probabilistic agenda-based chart parsing algorithm which uses a technique called probabilistic prediction to predict which grammar rules are likely to lead to an acceptable parse of the input. Using a suboptimal search method, Picky significantly reduces the number of edges produced by CKY-like chart parsing algorithms, while maintaining the robustness of pure bottom-up parsers and the accuracy of existing probabilistic parsers. Experiments using Picky demonstrate how probabilistic modelling can impact upon the efficiency, robustness and accuracy of a parser.

References

[1]

Black, E., Jelinek, F., Lafferty, J., Magerman, D. M., Mercer, R. and Roukos, S. 1992. Towards History-based Grammars: Using Richer Models of Context in Probabilistic Parsing. In Proceedings of the February 1992 DARPA Speech and Natural Language Workshop. Arden House, NY.

Digital Library

[2]

Brown, P., Jelinek, F., and Mercer, R. 1991. Basic Method of Probabilistic Context-free Grammars. IBM Internal Report. Yorktown Heights, NY.

[3]

Bobrow, R. J. 1991. Statistical Agenda Parsing. In Proceedings of the February 1991 DARPA Speech and Natural Language Workshop. Asilomar, California.

Digital Library

[4]

Chitrao, M. and Grishman, R. 1990. Statistical Parsing of Messages. In Proceedings of the June 1990 DARPA Speech and Natural Language Workshop. Hidden Valley, Pennsylvania.

Digital Library

[5]

Church, K. 1988. A Stochastic Parts Program and Noun Phrase Parser for Unrestricted Text. In Proceedings of the Second Conference on Applied Natural Language Processing. Austin, Texas.

Digital Library

[6]

Earley, J. 1970. An Efficient Context-Free Parsing Algorithm. Communications of the ACM Vol. 13, No. 2, pp. 94--102.

Digital Library

[7]

Gale, W. A. and Church, K. 1990. Poor Estimates of Context are Worse than None. In Proceedings of the June 1990 DARPA Speech and Natural Language Workshop. Hidden Valley, Pennsylvania.

Digital Library

[8]

Jelinek, F. 1985. Self-organizing Language Modeling for Speech Recognition. IBM Report.

[9]

Kasami, T. 1965. An Efficient Recognition and Syntax Algorithm for Context-Free Languages. Scientific Report AFCRL-65-758, Air Force Cambridge Research Laboratory. Bedford, Massachusetts.

[10]

Kay, M. 1980. Algorithm Schemata and Data Structures in Syntactic Processing. CSL-80-12, October 1980.

[11]

Kimball, J. 1973. Principles of Surface Structure Parsing in Natural Language. Cognition, 2. 15--47.

[12]

Magerman, D. M. and Marcus, M. P. 1991. Pearl: A Probabilistic Chart Parser. In Proceedings of the European ACL Conference, March 1991. Berlin, Germany.

Digital Library

[13]

Magerman, D. M. and Weir, C. 1992. Probabilistic Prediction and Picky Chart Parsing. In Proceedings of the February 1992 DARPA Speech and Natural Language Workshop. Arden House, NY.

Digital Library

[14]

Moore, R. and Dowding, J. 1991. Efficient Bottom-Up Parsing. In Proceedings of the February 1991 DARPA Speech and Natural Language Workshop. Asilomar, California.

Digital Library

[15]

Sharman, R. A., Jelinek, F., and Mercer, R. 1990. Generating a Grammar for Statistical Training. In Proceedings of the June 1990 DARPA Speech and Natural Language Workshop. Hidden Valley, Pennsylvania.

Digital Library

[16]

Seneff, Stephanie 1989. TINA. In Proceedings of the August 1989 International Workshop in Parsing Technologies. Pittsburgh, Pennsylvania.

[17]

Younger, D. H. 1967. Recognition and Parsing of Context-Free Languages in Time n. Information and Control Vol. 10, No. 2, pp. 189--208.

Cited By

Foster JVogel C(2004)Parsing Ill-Formed Text Using an Error GrammarArtificial Intelligence Review10.1023/B:AIRE.0000036259.68818.1e21:3-4(269-291)Online publication date: 1-Jun-2004
https://dl.acm.org/doi/10.1023/B%3AAIRE.0000036259.68818.1e
Delisle SMoulin BCopeck T(2003)Surface-marker-based dialog modelling: A progress report on the MAREDI projectNatural Language Engineering10.1017/S13513249030032319:4(325-363)Online publication date: 1-Dec-2003
https://dl.acm.org/doi/10.1017/S1351324903003231
Cha JLee GKay M(2000)Structural disambiguation of morpho-syntactic categorial parsing for KoreanProceedings of the 18th conference on Computational linguistics - Volume 210.3115/992730.992793(1002-1006)Online publication date: 31-Jul-2000
https://dl.acm.org/doi/10.3115/992730.992793
Show More Cited By

Efficiency, robustness and accuracy in Picky chart parsing
1. Computing methodologies
  1. Artificial intelligence
2. Hardware
  1. Power and energy
    1. Power estimation and optimization

Recommendations

Probabilistic prediction and Picky chart parsing
HLT '91: Proceedings of the workshop on Speech and Natural Language

This paper describes Picky, a probabilistic agenda-based chart parsing algorithm which uses a technique called probabilistic prediction to predict which grammar rules are likely to lead to an acceptable parse of the input. In tests on randomly selected ...
Syntax augmented machine translation via chart parsing
StatMT '06: Proceedings of the Workshop on Statistical Machine Translation

We present translation results on the shared task "Exploiting Parallel Texts for Statistical Machine Translation" generated by a chart parsing decoder operating on phrase tables augmented and generalized with target language syntactic categories. We use ...
Prediction in chart parsing algorithms for Categorial Unification Grammar
EACL '91: Proceedings of the fifth conference on European chapter of the Association for Computational Linguistics

Natural language systems based on Categorial Unification Grammar (CUG) have mainly employed bottom-up parsing algorithms for processing. Conventional prediction techniques to improve the efficiency of the parsing process, appear to fall short when ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

ACL '92: Proceedings of the 30th annual meeting on Association for Computational Linguistics

June 1992

346 pages

Program Chair:
Henry S. Thompson
University of Edinburgh

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 28 June 1992

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 85 of 443 submissions, 19%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
391
Total Downloads

Downloads (Last 12 months)59
Downloads (Last 6 weeks)5

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Foster JVogel C(2004)Parsing Ill-Formed Text Using an Error GrammarArtificial Intelligence Review10.1023/B:AIRE.0000036259.68818.1e21:3-4(269-291)Online publication date: 1-Jun-2004
https://dl.acm.org/doi/10.1023/B%3AAIRE.0000036259.68818.1e
Delisle SMoulin BCopeck T(2003)Surface-marker-based dialog modelling: A progress report on the MAREDI projectNatural Language Engineering10.1017/S13513249030032319:4(325-363)Online publication date: 1-Dec-2003
https://dl.acm.org/doi/10.1017/S1351324903003231
Cha JLee GKay M(2000)Structural disambiguation of morpho-syntactic categorial parsing for KoreanProceedings of the 18th conference on Computational linguistics - Volume 210.3115/992730.992793(1002-1006)Online publication date: 31-Jul-2000
https://dl.acm.org/doi/10.3115/992730.992793
Neuhaus PHahn UTsujii J(1996)Restricted parallelism in object-oriented lexical parsingProceedings of the 16th conference on Computational linguistics - Volume 110.3115/992628.992715(502-507)Online publication date: 5-Aug-1996
https://dl.acm.org/doi/10.3115/992628.992715
Goodman JJoshi APalmer M(1996)Parsing algorithms and metricsProceedings of the 34th annual meeting on Association for Computational Linguistics10.3115/981863.981887(177-183)Online publication date: 24-Jun-1996
https://dl.acm.org/doi/10.3115/981863.981887
Stolcke A(1995)An efficient probabilistic context-free parsing algorithm that computes prefix probabilitiesComputational Linguistics10.5555/211190.21119721:2(165-201)Online publication date: 1-Jun-1995
https://dl.acm.org/doi/10.5555/211190.211197
Bod RAbney SHinrichs E(1995)The problem of computing the most probable tree in data-oriented parsing and stochastic tree grammarsProceedings of the seventh conference on European chapter of the Association for Computational Linguistics10.3115/976973.976989(104-111)Online publication date: 27-Mar-1995
https://dl.acm.org/doi/10.3115/976973.976989
Charniak ECarroll G(1994)Context-sensitive statistics for improved grammatical language modelsProceedings of the Twelfth AAAI National Conference on Artificial Intelligence10.5555/2891730.2891842(728-733)Online publication date: 1-Aug-1994
https://dl.acm.org/doi/10.5555/2891730.2891842
Kato TJacobs P(1994)Yet another chart-based technique for parsing ill-formed inputProceedings of the fourth conference on Applied natural language processing10.3115/974358.974383(107-112)Online publication date: 13-Oct-1994
https://dl.acm.org/doi/10.3115/974358.974383
Jelinek FLafferty JMagerman DMercer RRatnaparkhi ARoukos S(1994)Decision tree parsing using a hidden derivation modelProceedings of the workshop on Human Language Technology10.3115/1075812.1075873(272-277)Online publication date: 8-Mar-1994
https://dl.acm.org/doi/10.3115/1075812.1075873

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents