Approximate PCFG Parsing Using Tensor Decomposition

Shay B. Cohen; Giorgio Satta; Michael Collins

Approximate PCFG Parsing Using Tensor Decomposition

Shay B. Cohen, Giorgio Satta, Michael Collins

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

Abstract

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 language	English
Title of host publication	Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies
Place of Publication	Atlanta, Georgia
Publisher	Association for Computational Linguistics
Pages	487-496
Number of pages	10
Publication status	Published - 1 Jun 2013

Access to Document

N13-1052Final published version, 169 KB

http://www.aclweb.org/anthology/N13-1052

Cite this

@inproceedings{3362c65532b644a0a8f2199ae7dad174,

title = "Approximate PCFG Parsing Using Tensor Decomposition",

abstract = "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.",

author = "Cohen, \{Shay B.\} and Giorgio Satta and Michael Collins",

year = "2013",

month = jun,

day = "1",

language = "English",

pages = "487--496",

booktitle = "Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies",

publisher = "Association for Computational Linguistics",

}

Approximate PCFG Parsing Using Tensor Decomposition. / Cohen, Shay B.; Satta, Giorgio; Collins, Michael.
Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Atlanta, Georgia: Association for Computational Linguistics, 2013. p. 487-496.

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

TY - GEN

T1 - Approximate PCFG Parsing Using Tensor Decomposition

AU - Cohen, Shay B.

AU - Satta, Giorgio

AU - Collins, Michael

PY - 2013/6/1

Y1 - 2013/6/1

N2 - 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.

AB - 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.

M3 - Conference contribution

SP - 487

EP - 496

BT - Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies

PB - Association for Computational Linguistics

CY - Atlanta, Georgia

ER -

Approximate PCFG Parsing Using Tensor Decomposition

Abstract

Access to Document

Fingerprint

Cite this