Multilevel coarse-to-fine PCFG parsing

Eugene Charniak; Mark Johnson; Micha Elsner; Joseph Austerweil; David Ellis; Isaac Haxton; Catherine Hill; R. Shrivaths; Jeremy Moore; Michael Pozar; Theresa Vu

Multilevel coarse-to-fine PCFG parsing

Eugene Charniak^*, Mark Johnson, Micha Elsner, Joseph Austerweil, David Ellis, Isaac Haxton, Catherine Hill, R. Shrivaths, Jeremy Moore, Michael Pozar, Theresa Vu

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

48 Citations (Scopus)

Abstract

We present a PCFG parsing algorithm that uses a multilevel coarse-to-fine (mlctf) scheme to improve the efficiency of search for the best parse. Our approach requires the user to specify a sequence of nested partitions or equivalence classes of the PCFG nonterminals. We define a sequence of PCFGs corresponding to each partition, where the nonterminals of each PCFG are clusters of nonterminals of the original source PCFG. We use the results of parsing at a coarser level (i.e., grammar defined in terms of a coarser partition) to prune the next finer level. We present experiments showing that with our algorithm the work load (as measured by the total number of constituents processed) is decreased by a factor of ten with no decrease in parsing accuracy compared to standard CKY parsing with the original PCFG. We suggest that the search space over mlctf algorithms is almost totally unexplored so that future work should be able to improve significantly on these results.

Original language	English
Title of host publication	HLT-NAACL 2006 - Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings of the Main Conference
Place of Publication	New York
Publisher	ACM
Pages	168-175
Number of pages	8
Publication status	Published - 2006
Externally published	Yes
Event	2006 Human Language Technology Conference - North American Chapter of the Association for Computational Linguistics Annual Meeting, HLT-NAACL 2006 - New York, NY, United States Duration: 4 Jun 2006 → 9 Jun 2006

Other

Other	2006 Human Language Technology Conference - North American Chapter of the Association for Computational Linguistics Annual Meeting, HLT-NAACL 2006
Country/Territory	United States
City	New York, NY
Period	4/06/06 → 9/06/06

Cite this

Charniak, E., Johnson, M., Elsner, M., Austerweil, J., Ellis, D., Haxton, I., Hill, C., Shrivaths, R., Moore, J., Pozar, M., & Vu, T. (2006). Multilevel coarse-to-fine PCFG parsing. In HLT-NAACL 2006 - Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings of the Main Conference (pp. 168-175). ACM.

@inproceedings{634d84174bf74a98a18acb2f3df19a2f,

title = "Multilevel coarse-to-fine PCFG parsing",

abstract = "We present a PCFG parsing algorithm that uses a multilevel coarse-to-fine (mlctf) scheme to improve the efficiency of search for the best parse. Our approach requires the user to specify a sequence of nested partitions or equivalence classes of the PCFG nonterminals. We define a sequence of PCFGs corresponding to each partition, where the nonterminals of each PCFG are clusters of nonterminals of the original source PCFG. We use the results of parsing at a coarser level (i.e., grammar defined in terms of a coarser partition) to prune the next finer level. We present experiments showing that with our algorithm the work load (as measured by the total number of constituents processed) is decreased by a factor of ten with no decrease in parsing accuracy compared to standard CKY parsing with the original PCFG. We suggest that the search space over mlctf algorithms is almost totally unexplored so that future work should be able to improve significantly on these results.",

author = "Eugene Charniak and Mark Johnson and Micha Elsner and Joseph Austerweil and David Ellis and Isaac Haxton and Catherine Hill and R. Shrivaths and Jeremy Moore and Michael Pozar and Theresa Vu",

year = "2006",

language = "English",

pages = "168--175",

booktitle = "HLT-NAACL 2006 - Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings of the Main Conference",

publisher = "ACM",

note = "2006 Human Language Technology Conference - North American Chapter of the Association for Computational Linguistics Annual Meeting, HLT-NAACL 2006 ; Conference date: 04-06-2006 Through 09-06-2006",

}

Charniak, E, Johnson, M, Elsner, M, Austerweil, J, Ellis, D, Haxton, I, Hill, C, Shrivaths, R, Moore, J, Pozar, M & Vu, T 2006, Multilevel coarse-to-fine PCFG parsing. in HLT-NAACL 2006 - Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings of the Main Conference. ACM, New York, pp. 168-175, 2006 Human Language Technology Conference - North American Chapter of the Association for Computational Linguistics Annual Meeting, HLT-NAACL 2006, New York, NY, United States, 4/06/06.

Multilevel coarse-to-fine PCFG parsing. / Charniak, Eugene; Johnson, Mark; Elsner, Micha et al.
HLT-NAACL 2006 - Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings of the Main Conference. New York: ACM, 2006. p. 168-175.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Multilevel coarse-to-fine PCFG parsing

AU - Charniak, Eugene

AU - Johnson, Mark

AU - Elsner, Micha

AU - Austerweil, Joseph

AU - Ellis, David

AU - Haxton, Isaac

AU - Hill, Catherine

AU - Shrivaths, R.

AU - Moore, Jeremy

AU - Pozar, Michael

AU - Vu, Theresa

PY - 2006

Y1 - 2006

N2 - We present a PCFG parsing algorithm that uses a multilevel coarse-to-fine (mlctf) scheme to improve the efficiency of search for the best parse. Our approach requires the user to specify a sequence of nested partitions or equivalence classes of the PCFG nonterminals. We define a sequence of PCFGs corresponding to each partition, where the nonterminals of each PCFG are clusters of nonterminals of the original source PCFG. We use the results of parsing at a coarser level (i.e., grammar defined in terms of a coarser partition) to prune the next finer level. We present experiments showing that with our algorithm the work load (as measured by the total number of constituents processed) is decreased by a factor of ten with no decrease in parsing accuracy compared to standard CKY parsing with the original PCFG. We suggest that the search space over mlctf algorithms is almost totally unexplored so that future work should be able to improve significantly on these results.

AB - We present a PCFG parsing algorithm that uses a multilevel coarse-to-fine (mlctf) scheme to improve the efficiency of search for the best parse. Our approach requires the user to specify a sequence of nested partitions or equivalence classes of the PCFG nonterminals. We define a sequence of PCFGs corresponding to each partition, where the nonterminals of each PCFG are clusters of nonterminals of the original source PCFG. We use the results of parsing at a coarser level (i.e., grammar defined in terms of a coarser partition) to prune the next finer level. We present experiments showing that with our algorithm the work load (as measured by the total number of constituents processed) is decreased by a factor of ten with no decrease in parsing accuracy compared to standard CKY parsing with the original PCFG. We suggest that the search space over mlctf algorithms is almost totally unexplored so that future work should be able to improve significantly on these results.

UR - http://www.scopus.com/inward/record.url?scp=84863399844&partnerID=8YFLogxK

M3 - Conference proceeding contribution

AN - SCOPUS:84863399844

SP - 168

EP - 175

BT - HLT-NAACL 2006 - Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings of the Main Conference

PB - ACM

CY - New York

T2 - 2006 Human Language Technology Conference - North American Chapter of the Association for Computational Linguistics Annual Meeting, HLT-NAACL 2006

Y2 - 4 June 2006 through 9 June 2006

ER -

Multilevel coarse-to-fine PCFG parsing

Abstract

Other

Other files and links

Fingerprint

Cite this