Paper: Approximate PCFG Parsing Using Tensor Decomposition

ACL ID N13-1052
Title Approximate PCFG Parsing Using Tensor Decomposition
Venue Annual Conference of the North American Chapter of the Association for Computational Linguistics
Session Main Conference
Year 2013
Authors

We provide an approximation algorithm for PCFG parsing, which asymptotically im- proves time complexity with respect to the in- put grammar size, and prove upper bounds on the approximation quality. We test our algo- rithm on two treebanks, and get significant im- provements in parsing speed.