Approximate PCFG Parsing Using Tensor Decomposition

Shay Cohen, Giorgio Satta and Michael Collins

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.