Approximate PCFG Parsing Using Tensor Decomposition

Shay B. Cohen, Giorgio Satta, Michael Collins

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We provide an approximation algorithm for PCFG parsing, which asymptotically improves time complexity with respect to the input grammar size, and prove upper bounds on the approximation quality. We test our algorithm on two treebanks, and get significant improvements in parsing speed.
Original languageEnglish
Title of host publicationProceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies
Place of PublicationAtlanta, Georgia
PublisherAssociation for Computational Linguistics
Number of pages10
Publication statusPublished - 1 Jun 2013


Dive into the research topics of 'Approximate PCFG Parsing Using Tensor Decomposition'. Together they form a unique fingerprint.

Cite this