Neural Bi-Lexicalized PCFG Induction (2021)

Abstract: Neural lexicalized PCFGs (L-PCFGs) have been shown effective in grammar induction. However, to reduce computational complexity, they make a strong independence assumption on the generation of the child word and thus bilexical dependencies are ignored. In this paper, we propose an approach to parameterize L-PCFGs without making implausible independence assumptions. Our approach directly models bilexical dependencies and meanwhile reduces both learning and representation complexities of L-PCFGs. Experimental results on the English WSJ dataset confirm the effectiveness of our approach in improving both running speed and unsupervised parsing performance.

## introduction probabilistic context-free grammars (pcfgs) has been an important probabilistic approach to syntactic analysis @xcite . they assign a probability to each of the parses admitted by cfgs and rank them by the plausibility in such a way that the ambiguity of cfgs can be ameliorated. still, due to the strong independence assumption of cfgs, vanilla pcfgs @xcite are far from adequate for highly ambiguous text. a common premise for tackling the issue is to incorporate lexical information and weaken the independence assumption. there have been many approaches proposed under the premise @xcite @xcite . among them lexicalized pcfgs (l-pcfgs) are a relatively straightforward formalism @xcite . l-pcfgs extend pcfgs by associating a word, i.e., the lexical head, with each grammar symbol. they can thus exploit lexical ˚corresponding author information to disambiguate parsing decisions and are much more expressive than vanilla pcfgs. however, they suffer from representation and inference complexities. for representation, the addition of lexical information greatly increases the number of parameters to be estimated and exacerbates the data sparsity problem during learning, so the expectation-maximisation (em) based estimation of l-pcfgs has to rely on sophisticated smoothing techniques and factorizations @xcite . as for inference, the cyk algorithm for l-pcfgs has a opl 5 |g|q complexity, where l is the sentence length and |g| is the grammar constant. although @xcite manage to reduce the complexity to opl 4 |g|q, inference with l-pcfgs is still relatively slow, making them less popular nowadays. recently, @xcite combine the ideas of factorizing the binary rule probabilities @xcite and neural parameterization @xcite and propose neural l-pcfgs (nl-pcfgs), achieving good results in both unsupervised dependency and constituency parsing. neural parameterization is the key to success, which facilitates informed smoothing @xcite , reduces the number of learnable parameters for large grammars @xcite and facilitates advanced gradient-based optimization techniques instead of using the traditional em algorithm @xcite . @xcite oversimplify the binary rules to decrease the complexity of the inside/cyk algorithm in learning (i.e., estimating the marginal sentence loglikelihood) and inference. specifically, they make a strong independence assumption on the generation of the child word such that it is only dependent on the nonterminal symbol. bilexical dependencies, which have been shown useful in unsupervised dependency parsing @xcite , are thus ignored. to model bilexical dependencies and meanwhile reduce complexities, we draw inspiration from the canonical polyadic decomposition (cpd) @xcite and propose a latent-variable based neural parameterization of l-pcfgs. @xcite ; @xcite have used cpd to decrease the complexities of pcfgs, and our work can be seen as an extension of their work to l-pcfgs. we further adopt the unfold-refold transformation technique @xcite to decrease complexities. by using this technique, we show that the time complexity of the inside algorithm implemented by zhu et al. ( 2020 ) can be improved from cubic to quadratic in the number of nonterminals m. the inside algorithm of our proposed method has a linear complexity in m after combining cpd and unfold-refold. we evaluate our model on the benchmarking wall street journey (wsj) dataset. our model surpasses the strong baseline nl-pcfg (zhu et al., 2020) by 2.9% mean f1 and 1.3% mean uuas under cyk decoding. when using the minimal bayes-risk (mbr) decoding, our model performs even better. we provide an efficient implementation of our proposed model at https://github.com/ sustcsonglin/tn-pcfg . ## factorization with latent variable our main goal is to find a parameterization that removes the implausible independence assumptions of @xcite while decreases the complexities of the original l-pcfgs. to reduce the representation complexity, we draw inspiration from the canonical polyadic decomposition (cpd). cpd factorizes an n-th order tensor into n two-dimensional matrices. each matrix consists of two dimensions: one dimension comes from the original n-th order tensor and the other dimension is shared by all the n matrices. the shared dimension can be marginalized to recover the original n-th order tensor. from a probabilistic perspective, the shared dimension can be regarded as a latent-variable. in the spirit of cpd, we introduce a latent-variable h to decompose the order-6 according to d-separation @xcite , when a and w p are given, b, c, w q , and d are interdependent due to the existence of h. in other words, our factorization does not make any independence assumption beyond the original binary rule. the domain size of h is analogous to the tensor rank in cpd and thus influences the expressiveness of our proposed model. we also follow zhu et al. (2020) and factorize the start rule as follows. computational complexity: considering the head-child as the left child (similarly for the other case), we apply equation 10 in term a1 of equation 3 and obtain equation 7. rearranging the summations in equation 7 gives equation 8, where term d1-1 and d1-2 can be cached and reused, which also uses the unfold-refold technique. the final time complexity of the inside computation with our factorization approach is opl 4 d h `l2 md h q (d h is the domain size of the latent variable h), which is linear in m. choices of factorization: if we follow the intuition of cpd, then we shall assume that b, c, d, and w q are all independent conditioned on h. however, properly relaxing this strong assumption by binding some variables could benefit our model. though there are many different choices of binding the variables, some bindings can be easily ruled out. for instance, binding b and c inhibits us from caching term d1-1 and term d1-2 in equation 7 and thus we cannot implement the inside algorithm efficiently; binding c and w q leads to a high computational complexity because we will have to compute a high-dimensional (m|σ|) categorical distribution. in section 6.3, we make an ablation study on the impact of different choices of factorizations. neural parameterizations: we follow @xcite and @xcite and define the following neural parameterization: ## main result we present our main results in we do not use the compound trick @xcite in our implementations of lexicalized pcfgs because we empirically find that using it results in unstable training and does not necessarily bring performance improvements. we draw three key observations: (1) our model achieves the best f1 and uuas scores under both cyk and mbr decoding. it is also comparable to the official nl-pcfg in the udas score. (2) when we remove the compound parameterization from nl-pcfg, its f1 score drops slightly while its udas and uuas scores drop dramatically. it implies that compound parameterization is the key to achieve excellent dependency grammar induction performance in nl-pcfg. (3) the mbr decoding outperforms cyk decoding. regarding udas, our model significantly outperforms nl-pcfgs in udass if compound parameterization is not used (37.1 vs. 23.8 with cyk decoding), showing that explicitly modeling bilexical relationship is helpful in dependency grammar induction. however, when compound parameterization is used, the udas of nl-pcfgs is greatly improved, slightly surpassing that of our model. we believe this is because compound parameterization greatly weakens the independence assumption of nl-pcfgs (i.e., the child word is dependent on c only) by leaking bilexical information via the global sentence embedding. on the other hand, nbl-pcfgs are already expressive enough and thus compound parameterization brings no further increase of their expressiveness but makes learning more difficult. ## analysis in the following experiments, we report results using mbr decoding by default. we also use d h " 300 by default unless otherwise specified. ## discussion on dependency annotation schemes what should be regarded as the headwords is still debatable in linguistics, especially for those around function words @xcite . for example, in phrase the company, some linguists argue that the should be the headword @xcite . these disagreements are reflected in the dependency annotation schemes. researchers have found that different dependency annotation schemes result in very different evaluation scores of unsupervised dependency parsing @xcite . in our experiments, we use the stanford dependencies annotation scheme in order to compare with nl-pcfgs. stanford dependencies prefers to select content words as headwords. however, as we discussed in previous sections, our model prefers to select function words (e.g., of, which, for) as headwords for sbars or pps.this explains why our model can outperform all the baselines on constituency parsing but not on dependency parsing (as judged by stanford dependencies) at the same time. ## related work unsupervised parsing has a long history but has regained great attention in recent years. in unsupervised dependency parsing, most methods are based on dependency model with valence (dmv) @xcite . neurally parameterized dmvs have obtained state-of-the-art performance @xcite @xcite . however, they rely on gold pos tags and sophisticated initializations (e.g. k&m initialization or initialization with the parsing result of another unsupervised model). @xcite propose a left-corner parsing-based dmv model to limit the stack depth of center-embedding, which is insensitive to initialization but needs gold pos tags. @xcite propose a latent-variable based dmv model, which does not need gold pos tags but requires good initialization and high-quality induced pos tags. see @xcite for a survey of unsupervised dependency parsing. compared to these methods, our method does not require gold/induced pos tags or sophisticated initializations, though its performance lags behind some of these previous methods. recent unsupervised constituency parsers can be roughly categorized into the following groups: we are only aware of a few previous studies in unsupervised joint dependency and constituency parsing. @xcite propose a joint dmv and ccm @xcite model. @xcite propose a transformer-based method, in which they define syntactic distances to guild attentions of transformers. @xcite propose neural l-pcfgs for unsupervised joint parsing. ## conclusion we have presented a new formalism of lexicalized pcfgs. our formalism relies on the canonical polyadic decomposition to factorize the probability tensor of binary rules. the factorization reduces the space and time complexity of lexicalized pcfgs while keeping the independence assumptions encoded in the original binary rules intact. we further parameterize our model by using neural networks and present an efficient implementation of our model. on the english wsj test data, our model achieves the lowest perplexity, outperforms all the existing extensions of pcfgs in constituency grammar induction, and is comparable to strong baselines in dependency grammar induction.