PCFG s Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols (2021)

Abstract: Probabilistic context-free grammars (PCFGs) with neural parameterization have been shown to be effective in unsupervised phrase-structure grammar induction. However, due to the cubic computational complexity of PCFG representation and parsing, previous approaches cannot scale up to a relatively large number of (nonterminal and preterminal) symbols. In this work, we present a new parameterization form of PCFGs based on tensor decomposition, which has at most quadratic computational complexity in the symbol number and therefore allows us to use a much larger number of symbols. We further use neural parameterization for the new form to improve unsupervised parsing performance. We evaluate our model across ten languages and empirically demonstrate the effectiveness of using more symbols.

## introduction unsupervised constituency parsing is the task of inducing phrase-structure grammars from raw text without using parse tree annotations. early work induces probabilistic context-free grammars (pcfgs) via the expectation maximation algorithm and finds the result unsatisfactory @xcite . recently, pcfgs with neural parameterization (i.e., using neural networks to generate rule probabilities) have been shown to achieve good results in unsupervised constituency parsing @xcite @xcite . however, due to the cubic computational complexity of pcfg representation and parsing, these approaches learn pcfgs with relatively small numbers of nonterminals and preterminals. for example, @xcite use 30 nonterminals (with no distinction between preterminals and other nonterminals) and @xcite use 30 nonterminals and 60 preterminals. in this paper, we study pcfg induction with a much larger number of nonterminal and preterminal symbols. we are partly motivated by the classic work of latent variable grammars in supervised constituency parsing @xcite @xcite @xcite . while the penn treebank grammar contains only tens of nonterminals and preterminals, it has been found that dividing them into subtypes could significantly improves the parsing accuracy of the grammar. for example, the best model from @xcite contains over 1000 nonterminal and preterminal symbols. we are also motivated by the recent work of @xcite who show that when learning latent variable models, increasing the number of hidden states is often helpful; and by @xcite who show that a neural hidden markov model with up to 2 16 hidden states can achieve surprisingly good performance in language modeling. a major challenge in employing a large number of nonterminal and preterminal symbols is that representing and parsing with a pcfg requires a computational complexity that is cubic in its symbol number. to resolve the issue, we rely on a new parameterization form of pcfgs based on tensor decomposition, which reduces the computational complexity from cubic to at most quadratic. furthermore, we apply neural parameterization to the new form, which is crucial for boosting unsupervised parsing performance of pcfgs as shown by @xcite . we empirically evaluate our approach across ten languages. on english wsj, our best model with 500 preterminals and 250 nonterminals improves over the model with 60 preterminals and 30 nonter-minals by 6.3% mean f1 score, and we also observe consistent decrease in perplexity and overall increase in f1 score with more symbols in our model, thus confirming the effectiveness of using more symbols. our best model also surpasses the strong baseline compound pcfgs @xcite ) by 1.4% mean f1. we further conduct multilingual evaluation on nine additional languages. the evaluation results suggest good generalizability of our approach on languages beyond english. our key contributions can be summarized as follows: (1) we propose a new parameterization form of pcfgs based on tensor decomposition, which enables us to use a large number of symbols in pcfgs. (2) we further apply neural parameterization to improve unsupervised parsing performance. ## parameterizing pcfgs based on tensor decomposition the tensor form of the inside algorithm has a high computational complexity of o(m 3 l 3 ). it hinders the algorithm from scaling to a large m. to resolve the issue, we resort to a new parameterization form of pcfgs based on tensor decomposition (td-pcfgs) @xcite . as discussed in section 2, while cohen et al. ( 2013 ) use a td-pcfg to approximate an existing pcfg for speedup in parsing, we regard a td-pcfg as a stand-alone model and learn it directly from data. the basic idea behind td-pcfgs is using kruskal decomposition of the order-3 tensor t. specifically, we require t to be in the kruskal form, the kruskal form of the tensor t is crucial for reducing the computation of equation 3. to show this, we let @xmath0,k , @xmath1,j , and z be any summand in the right-hand side of equation 3, so we have: substitute t in equation 4 into equation 5 and consider the i-th dimension of z: equation 8 computes the inside probabilities using td-pcfgs. it has a time complexity o(md). by caching v t s i,k and w t s k+1,j , the time complexity of the inside algorithm becomes o(dl 3 + mdl 2 ) @xcite , which is at most quadratic in m since we typically set @xmath2. interestingly, equation 8 has similar forms to recursive neural networks @xcite if we treat inside score vectors as span embeddings. one problem with td-pcfgs is that, since we use three matrices u, v and w to represent tensor t of binary rule probabilities, how we can ensure that t is non-negative and properly normalized, i.e., for a given left-hand side symbol a, ∑ j,k t h a ,j,@xmath3. simply reconstructing t with u, v and w and then performing normalization would take o(m 3 ) time, thus defeating the purpose of td-pcfgs. our solution is to require that the three matrices are non-negative and meanwhile u is row-normalized and v and w are columnnormalized @xcite . theorem 1. given non-negative matrices @xmath4, @xmath5, if u is row-normalized and v and w are column-normalized, then u, v, and w are a kruskal decomposition of a tensor @xmath6,j,@xmath7, 1] and we use neural parameterization for td-pcfgs as it has demonstrated its effectiveness in inducing pcfgs @xcite . in a neurally parameterized td-pcfgs, the original td-pcfg parameters are generated by neural networks, rather than being learned directly; parameters of the neural network will thus be the parameters to be optimized. this modeling approach breaks the parameter number limit of the original td-pcfg, so we can control the total number of parameters flexibly. when the total number of symbols is small, we can overparameterize the model as over-parameterization has been shown to ease optimization @xcite @xcite . on the other hand, when the total number of symbols is huge, we can decrease the number of parameters to save gpu memories and speed up training. specifically, we use neural networks to generate the following set of parameters of a td-pcfg: the resulting model is referred to as neural pcfgs based on tensor decomposition (tn-pcfgs). we start with the neural parameterization of @xmath8, @xmath9. we use shared symbol embeddings e @xmath10. we first compute an unnormalized ũ by applying a neural network f u (⋅) to symbol embeddings e s : for preterminal-rule probabilities @xmath11, we follow @xcite and define them as: ## parsing with td-pcfgs parsing seeks the most probable parse t ⋆ from all the parses t g (w) of a sentence w: typically, the cyk algorithm foot_1 can be directly used to solve this problem exactly: it first computes the score of the most likely parse; and then automatic differentiation is applied to recover the best tree structure t ⋆ @xcite . this, however, relies on the original probability tensor t and is incompatible with our decomposed representation. 4 if we reconstruct t from u, v, w and then perform cyk, then the resulting time and space complexity would degrade to o(m 3 l 3 ) and become unaffordable when m is large. therefore, we resort to minimum bayes-risk (mbr) style decoding because we can compute the inside probabilities efficiently. our decoding method consists of two stages. the first stage computes the conditional probability of a substring w i,j being a constituent in a given sentence w (a.k.a. posteriors of spans being a constituent): we can estimate the posteriors efficiently by using automatic differentiation after obtaining all the inside probabilities. this has the same time complexity as our improved inside algorithm, which is o(dl 3 + mdl 2 ). the second stage uses the cyk algorithm to find the parse tree that has the highest expected number of constituents @xcite : the time complexity of the second stage is o(l 3 ), so the overall time complexity of our decoding method is o(dl 3 + mdl 2 ), which is much faster than o(m 3 l 3 ) in general. ## experimental results we evaluate our models mainly on wsj (section 8.1-8.3). we first give an overview of model 6 shi et al. (2020) suggest not using the gold parses of the development data for hyperparameter tuning and model selection in unsupervised parsing. here we still use the gold parses of the wsj development set for the english experiments in order to conduct fair comparison with previous work. no gold parse is used in the experiments of any other language. ## discussions in our experiments, we do not find it beneficial to use the compound trick @xcite in tn-pcfgs, which is commonly used in previous work of pcfg induction @xcite @xcite . we speculate that the additional expressiveness brought by compound parameterization may not be necessary for a tn-pcfg with many symbols which is already sufficiently expressive; on the other hand, compound parameterization makes learning harder when we use more symbols. we also find neural parameterization and the choice of nonlinear activation functions greatly influence the performance. without using neural parameterization, td-pcfgs have only around 30% s-f1 scores on wsj, which are even worse than the right-branching baseline. activation functions other than relu (such as tanh and sigmoid) result in much worse performance. it is an interesting open question why relu and neural parameterization are crucial in pcfg induction. when evaluating our model with a large number of symbols, we find that only a small fraction of the symbols are predicted in the parse trees (for example, when our model uses 250 nonterminals, only tens of them are found in the predicted parse trees of the test corpus). we expect that our models can benefit from regularization techniques such as state dropout @xcite . ## conclusion we have presented td-pcfgs, a new parameterization form of pcfgs based on tensor decomposition. td-pcfgs rely on kruskal decomposition of the binary-rule probability tensor to reduce the computational complexity of pcfg representation and parsing from cubic to at most quadratic in the symbol number, which allows us to scale up td-pcfgs to a much larger number of (nonterminal and preterminal) symbols. we further propose neurally parameterized td-pcfgs (tn-pcfgs) and learn neural networks to produce the parameters of td-pcfgs. on wsj test data, tn-pcfgs outperform strong baseline models; we empirically show that using more nonterminal and preterminal symbols contributes to the high unsupervised parsing performance of tn-pcfgs. our multiligual evaluation on nine additional languages further reveals the capability of tn-pcfgs to generalize to languages beyond english.