Simple Hardware-Efficient PCFG s with Independent Left and Right Productions (2023)

Abstract: Scaling dense PCFGs to thousands of nonterminals via low-rank parameterizations 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. We further introduce \emph{FlashInside} , a hardware IO-aware implementation of the inside algorithm for efficiently scaling simple PCFGs. Through extensive experiments on multiple grammar induction benchmarks, we validate the effectiveness of simple PCFGs over low-rank baselines.

## introduction despite the improvements in unsupervised parsing obtained through scaling neural probabilistic context-free grammars (pcfgs), their language model performance scales less favorably compared to, for example, hidden markov models (hmms) and neural language models. on the penn treebank, a neural pcfg with 30 nonterminals and 60 preterminals obtains ≈ 250 perplexity @xcite , and while scaling neural pcfgs to thousands of states via a low-rank parameterization can improve perplexity to ≈ 170 @xcite , this still lags behind a similarly-sized hmm, which obtains ≈ 130 perplexity @xcite , despite the fact that hmms are a subclass of pcfgs this work proposes simplepcfg, a simple pcfg formalism with independent left and right productions. we find that this simple pcfg scales more effectively (in terms of both language modeling and unsupervised parsing) than previous approaches which scale pcfgs by factorizing the rule probability tensor into low-rank components @xcite . in particular, we find that simple pcfgs can obtain significantly lower perplexity in language modeling while achieving higher unsupervised parsing performance compared to lowrank pcfgs with a similar number of nonterminals, achieving a near state-of-the-art unsupervised parsing performance on the penn treebank with an f1 of 65.1. we further describe a hardware-efficient io-aware implementation of the inside algorithm, dubbed flashinside, to facilitate scalable learning of simple pcfgs. ## simple pcfgs a pcfg can be defined by a 6-tuple @xmath0, n , p, σ, r, π), where s is the distinguished start symbol, n /p/σ are a finite set of nonterminal/pre-terminal/terminal symbols, foot_0 r is a set of production rules of the form, @xmath1, @xmath2, @xmath3, b, @xmath4, @xmath5, @xmath6: @xmath7, 1] maps rules to their associated probabilities. in simple pcfgs, we decompose π @xmath8, effectively assuming that left and right children are generated independently. 2 we denote l, @xmath9, and apply a neural parameterization over these matrices to compute the rule probabilities @xcite . see appendix a for details. @xcite , and (c) rank space grammar @xcite . our simple pcfg is almost the same as (c) but uses a flexible parameterization. comparing simple vs. low-rank pcfgs. the previous approach to scaling hmms and pcfgs to thousands of nontermals is parameterizing the rule probability tensor @xmath10. low-rank pcfgs can be viewed as introducing a new latent variable, namely a "rank variable" r, to decompose π @xmath11, as shown in fig. 1 , where the tensor/matrix representations of π @xmath12, π @xmath13, π b↶r , π r↷c are t, u, v, w, respectively. yang et al. (2022, sect. 4.2) show that a low-rank pcfg can be reparameterized as a simple pcfg with independent left/right productions by marginalizing nonterminal variables and viewing the rank variables as new nonterminal variables. as such, low-rank pcfgs parameterize l, r in a more restrictive manner: @xmath14, @xmath15. we speculate that the shared u t would restrict the expressiveness of lowrank pcfgs and thus hinder optimization, which motivates our simple pcfgs. ## experimental setup datasets. we conduct experiments on the penn treebank (ptb) @xcite dataset with two different splits: one for language modeling @xcite , and one for unsupervised parsing @xcite . we also evaluate our model on chinese treebank 5.1 (ctb) @xcite and german and french treebanks from sprml @xcite . baselines. our hmm baselines include neural hmm (nhmm) @xcite , lhmm @xcite , and rank hmm @xcite . our pcfg baselines include neural/compound pcfg (n/c-pcfg) @xcite , tn-pcfg @xcite and rank pcfg @xcite . † denotes our reimplementation. for rank pcfg we use rank size 4096. see appendix b for more implementation details. evaluation. we use perplexity (ppl) to evaluate language modeling and sentence-level f1 (s-f1) @xcite to evaluate unsupervised parsing. ## results we compare our simple neural pcfg (sn-pcfg) to the baseline models. @xcite , on @xcite , diora @xcite , s-diora @xcite , constituency tests @xcite , structformer @xcite , and fast-r2d2 @xcite . whereever possible, we take the average f1 numbers across different seeds reported by the above papers (instead of the max). simple pcfg vs. neural pcfg. despite the better scalablity of simple pcfgs, we find that under the same number of nonterminal (i.e., 128), sn-pcfg expectedly underperforms n-pcfg in both language modeling and unsupervised parsing ( simple pcfg vs. rank pcfg. recall that the rank pcfg and simple pcfg share an identical dynamic programming structure. the rank variable in the rank pcfg amounts to the nonterminal variable in the simple pcfg. consequently, if we align the rank size in the rank pcfg with the nonterminal size in the simple pcfg, we achieve parity in terms of memory footprint and computational speed within the dynamic programming computation. in our experiments, we opt for a rank size of 4096 in the low-rank pcfg. the results, as presented in tables 2-4, showcase the worse perfor-mance of the rank pcfg when compared to sn-pcfg with 4096 nonterminals. interestingly, this work was motivated by our observation that merely augmenting the rank size of pcfg falls short in bridging the performance gap between hmms and pcfgs in language modeling. this resulted in our exploring alternative parameterizations, culminating in the straightforward independent left/right productions based parameterization which yields superior results in both language modeling and unsupervised parsing. ## related work independence assumptions are frequently made in grammar learning for tractability and scalability. simple pcfgs assume independent generation of left and right children, thus resembling splithead dependency grammars @xcite @xcite @xcite . we have shown that trading expressiveness (of grammar formalism) for scalablity is beneficial, and this idea could be applied to other complex grammar formalism of high parsing complexity, such as mildly context-sensitive grammars @xcite , synchronized grammars @xcite @xcite and lexicalized grammars @xcite . ## conclusion in this work we explore a simpler variant of pcfgs (simplepcfg) that shows better scaling properties than previous approaches in terms of both language modeling and unsupervised parsing performance. we also introduce a hardware-aware version of the inside algorithm (flashinside) which improves over existing vectorized gpu implementations.