PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols

Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 1487–1498 June 6–11, 2021. ©2021 Association for Computational Linguistics 1487 PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols Songlin Yang♣, Yanpeng Zhao♢, Kewei Tu♣∗ ♣School of Information Science and Technology, ShanghaiTech University Shanghai Engineering Research Center of Intelligent Vision and Imaging Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences University of Chinese Academy of Sciences ♢ILCC, University of Edinburgh {yangsl,tukw}@shanghaitech.edu.cn yannzhao.ed@gmail.com 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 ap- proaches cannot scale up to a relatively large number of (nonterminal and preterminal) sym- bols. In this work, we present a new parame- terization form of PCFGs based on tensor de- composition, which has at most quadratic com- putational 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 evalu- ate our model across ten languages and empir- ically demonstrate the effectiveness of using more symbols. 1 1 Introduction Unsupervised constituency parsing is the task of inducing phrase-structure grammars from raw text without using parse tree annotations. Early work in- duces probabilistic context-free grammars (PCFGs) via the Expectation Maximation algorithm and finds the result unsatisfactory (Lari and Young, 1990; Carroll and Charniak, 1992). Recently, PCFGs with neural parameterization (i.e., using neural networks to generate rule probabilities) have been shown to achieve good results in unsuper- vised constituency parsing (Kim et al., 2019a; Jin et al., 2019; Zhu et al., 2020). However, due to the cubic computational complexity of PCFG represen- tation and parsing, these approaches learn PCFGs with relatively small numbers of nonterminals and preterminals. For example, Jin et al. (2019) use 30 ∗Corresponding Author 1Our code: https://github.com/sustcsonglin/TN-PCFG nonterminals (with no distinction between pretermi- nals and other nonterminals) and Kim et al. (2019a) use 30 nonterminals and 60 preterminals. In this paper, we study PCFG induction with a much larger number of nonterminal and preter- minal symbols. We are partly motivated by the classic work of latent variable grammars in super- vised constituency parsing (Matsuzaki et al., 2005; Petrov et al., 2006; Liang et al., 2007; Cohen et al., 2012; Zhao et al., 2018). 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 pars- ing accuracy of the grammar. For example, the best model from Petrov et al. (2006) contains over 1000 nonterminal and preterminal symbols. We are also motivated by the recent work of Buhai et al. (2019) who show that when learning latent variable models, increasing the number of hidden states is often helpful; and by Chiu and Rush (2020) who show that a neural hidden Markov model with …

Content truncated to 500 words