Approximate PCFG Parsing Using Tensor Decomposition
Shay B. Cohen, Giorgio Satta, Michael J. Collins · Edinburgh Research Explorer (University of Edinburgh) · 2013
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. 1