A Fast Algorithm for Computing Prefix Probabilities
Franz Nowak, Ryan Cotterell
Anthology
Underline
Main: Syntax: Tagging, Chunking, and Parsing Main-poster Paper
Poster Session 4: Syntax: Tagging, Chunking, and Parsing (Poster)
Conference Room: Frontenac Ballroom and Queen's Quay
Conference Time: July 11, 11:00-12:30 (EDT) (America/Toronto)
Global Time: July 11, Poster Session 4 (15:00-16:30 UTC)
Keywords:
parsing algorighms (symbolic, theoritical results)
TLDR:
Multiple algorithms are known for efficiently calculating the prefix probability of a string under a probabilistic context-free grammar (PCFG).
Good algorithms for the problem have a runtime cubic in the length of the input string.
However, some proposed algorithms are suboptimal with respect to t...
You can open the
#paper-P3736
channel in a separate window.
Abstract:
Multiple algorithms are known for efficiently calculating the prefix probability of a string under a probabilistic context-free grammar (PCFG).
Good algorithms for the problem have a runtime cubic in the length of the input string.
However, some proposed algorithms are suboptimal with respect to the size of the grammar.
This paper proposes a new speed-up of Jelinek and Lafferty's (1991) algorithm, which runs in O(n\^3|N|\^3 + |N|\^4), where n is the input length and |N| is the number of non-terminals in the grammar. In contrast, our speed-up runs in O(n\^2|N|\^3 + n\^3|N|\^2).