Simple Hardware-Efficient PCFGs with Independent Left and Right Productions
This work addresses the challenge of improving PCFG performance for natural language processing tasks, offering a more effective scaling method that benefits researchers and practitioners in computational linguistics, though it is incremental as it builds on existing PCFG approaches.
The paper tackled the problem of scaling dense Probabilistic Context-Free Grammars (PCFGs) for unsupervised parsing and language modeling by introducing SimplePCFG, a formalism with independent left and right productions, which achieved an average F1 of 65.1 on the English PTB for parsing and a perplexity of 119.0 for language modeling, outperforming similarly-sized low-rank PCFGs.
Scaling dense PCFGs to thousands of nonterminals via a low-rank parameterization of the rule probability tensor has been shown to be beneficial for unsupervised parsing. However, PCFGs scaled this way still perform poorly as a language model, and even underperform similarly-sized HMMs. This work introduces \emph{SimplePCFG}, a simple PCFG formalism with independent left and right productions. Despite imposing a stronger independence assumption than the low-rank approach, we find that this formalism scales more effectively both as a language model and as an unsupervised parser. As an unsupervised parser, our simple PCFG obtains an average F1 of 65.1 on the English PTB, and as a language model, it obtains a perplexity of 119.0, outperforming similarly-sized low-rank PCFGs. We further introduce \emph{FlashInside}, a hardware IO-aware implementation of the inside algorithm for efficiently scaling simple PCFGs.