PaperlayerView exact revision on arXiv

Source-linked AI summary

Compound Probabilistic Context-Free Grammars for Grammar Induction

Yoon Kim, Chris Dyer, Alexander M. Rush

arXiv:1906.10225v9cs.CLstat.ML

TL;DR

Grammar induction seeks linguistically meaningful hierarchical structure, but traditional PCFG learning has been difficult. This paper introduces compound PCFGs with sentence-level latent variables and finds improved unsupervised parsing performance on English and Chinese.

  • Problem

    Traditional PCFGs have been difficult to induce from natural-language data using direct likelihood optimization, motivating improved grammar-induction methods.

  • Method

    The model uses a sentence-level continuous latent variable to modulate neural PCFG rule probabilities, with collapsed variational inference and dynamic-programming marginalization of latent trees.

  • Results

    Compound PCFGs outperform other evaluated models by an appreciable margin on unsupervised parsing for both English and Chinese.

  • Takeaways & Limitations

    Compound PCFGs learn richer grammars and improve performance when evaluated as unsupervised parsers.

  • Takeaways & Limitations

    Training is significantly more expensive than NLM-based unsupervised parsing systems, making the approach potentially difficult to scale.

Abstract

from arXiv · show

We study a formalization of the grammar induction problem that models sentences as being generated by a compound probabilistic context-free grammar. In contrast to traditional formulations which learn a single stochastic grammar, our grammar's rule probabilities are modulated by a per-sentence continuous latent variable, which induces marginal dependencies beyond the traditional context-free assumptions. Inference in this grammar is performed by collapsed variational inference, in which an amortized variational posterior is placed on the continuous variable, and the latent trees are marginalized out with dynamic programming. Experiments on English and Chinese show the effectiveness of our approach compared to recent state-of-the-art methods when evaluated on unsupervised parsing.

1 Introduction

The paper revisits grammar induction by showing that neural parameterization can yield linguistically meaningful grammars through log-likelihood optimization, while collapsed variational inference enables efficient learning. On English and Chinese benchmarks, the approach performs favorably against recent neural unsupervised parsing methods.

  • Motivation: Grammar induction traditionally requires specifying a probabilistic grammar and optimizing its parameters, while successful methods often add auxiliary objectives, priors, non-parametric models, or engineered features.These additions were used to encourage desired structures to emerge.
  • Contribution: Neural networks over distributed representations make it possible to induce linguistically meaningful PCFGs by simply optimizing log likelihood, despite the optimization problem remaining non-convex.The paper attributes this finding to advances in model parameterization and inference, with optimization benefits suggested for over-parameterized models (Arora et al.).
  • Inference: Collapsed inference marginalizes latent trees exactly with dynamic programming because fixing the latent vector reduces the compound PCFG to a standard PCFG.The continuous latent vector is handled with amortized inference using reparameterized samples from an inference-network variational posterior (Kingma and Welling, 2014).
  • Results: On standard English and Chinese benchmarks, the proposed approach performs favorably against recent neural methods for unsupervised parsing (Shen et al., 2018, 2019; Drozdov et al., 2019; Kim et al., 2019).

2 Probabilistic Context-Free Grammars

A PCFG assigns rule probabilities that define distributions over parse trees, terminal strings, and latent trees conditioned on observed sentences. Neural parameterization shares information across rule types through distributed symbol representations, while preserving the underlying context-free assumptions.

  • A PCFG combines a context-free grammar with rule probabilities, defining distributions over parse trees and their terminal yields.The probability of a tree is the product of probabilities for the rules used in its derivation, and sentence probabilities sum over compatible trees.
  • Given an observed sentence, the PCFG posterior distributes probability over its unobserved latent parse trees.The latent tree excludes the sentence’s observed leaves and contains only unobserved nonterminal and preterminal symbols.
  • Direct scalar parameterization is algorithmically convenient because EM has a closed-form M-step, but it struggles to learn meaningful grammars from natural-language data.Preliminary experiments likewise failed to learn linguistically meaningful grammars with this PCFG parameterization.
  • Neural PCFGs parameterize rule probabilities from distributed symbol embeddings, enabling sharing across rule types while retaining the same probabilistic assumptions.The model uses neural networks for several rule types but omits an MLP for binary nonterminal rules because it did not empirically improve results.

3 Compound PCFGs

Compound PCFGs assign each sentence its own rule probabilities through a continuous latent variable, preserving tractable tree-based generation while inducing dependencies beyond ordinary PCFGs. Learning marginalizes trees with the inside algorithm and approximates the otherwise intractable latent-variable integral using collapsed amortized variational inference.

  • Model: Compound PCFGs generate sentence-level rule probabilities from a latent vector z, then sample a tree and sentence from the resulting PCFG.The prior pγ(z) is spherical Gaussian in this paper, and a neural network fλ combines input-symbol embeddings with z to produce πz.
  • Model: Conditioned on z, the grammar is context-free; marginalizing z creates dependencies, making compound PCFGs more expressive while retaining latent tree structures.The model can be viewed as a continuous mixture of PCFGs, with each sentence receiving its own rule probabilities.
  • Learning: The latent-variable integral makes exact marginal likelihood computation intractable, although the conditional tree summation pθ(x | z) remains tractable with the inside algorithm.In contrast, neural PCFG likelihoods can sum out latent trees directly using the differentiable inside algorithm.
  • Learning: Collapsed amortized variational inference samples z from qφ(z | x), marginalizes trees conditioned on that sample, and optimizes the ELBO with reparameterization and an analytic KL term.The variational posterior is a diagonal Gaussian whose parameters come from max-pooled LSTM hidden states over x.
  • Decoding: At test time, the most likely compound-PCFG tree is approximated by evaluating CKY at the inference-network mean μφ(x), replacing pθ(z | x) with a Dirac delta.This approximation is tractable and was found efficient and effective in practice.

4 Experimental Setup

Experiments evaluate the approach on word-only PTB and Chinese PTB benchmarks using standardized preprocessing and unsupervised parsing evaluation. The setup specifies the model and training configuration while noting variation in prior evaluation practices and a limitation from validation-F1 hyperparameter tuning.

  • Datasets and preprocessing: The experiments use standard PTB splits and Chinese PTB version 5.1, removing punctuation and retaining the 10K most frequent word types.PTB uses splits 2–21 for training, 22 for validation, and 23 for testing; Chinese PTB uses the splits of Chen and Manning (2014).
  • Model and training: The PCFG has 30 nonterminals and 60 preterminals, while the compound PCFG uses 64-dimensional latent vectors and a 512-dimensional single-layer bidirectional LSTM inference network.Symbol embeddings are 256-dimensional, and the variational mean and log variance are computed by max-pooling LSTM hidden states followed by an affine layer.
  • Evaluation protocol: PTB results are not strictly fully unsupervised because validation-tree F1 selected some hyperparameters, and PRPN/ON hyperparameters were tuned similarly for fair comparison.The authors note this practice explicitly as a limitation of the PTB evaluation.
  • Evaluation protocol: The induced grammar is evaluated as an unsupervised parsing system using sentence-level unlabeled F1 after discarding trivial spans, primarily against PRPN [12] and ON [13].Prior work varies in input representation, punctuation use, train/test separation, and F1 calculation, motivating the standardized comparison protocol.

5 Results and Discussion

The compound PCFG achieves the strongest unsupervised parsing performance among the evaluated models on English and Chinese, while induced trees also support useful downstream grammaticality judgments. Analyses indicate interpretable nonterminals and topical latent representations, but reveal sensitivity, computational cost, and persistent constituent-identification limitations.

  • Unsupervised Parsing: The compound PCFG outperforms other grammar-induction models by an appreciable margin on unlabeled F1 for both English and Chinese, while traditional scalar PCFG training fails.All models outperform right-branching baselines, but meaningful grammars could not be induced with the traditional PCFG despite extensive hyperparameter search.
  • Tree Structure Analysis: Across runs, PRPN is particularly consistent, while different models excel at different constituent labels and all models struggle especially with long SBAR/VP constituents.These findings come from comparisons against gold, left, right, and self trees, plus label-recall analysis.
  • RNNG Evaluation: Compound-PCFG-induced trees yield better grammaticality judgments in an RNNG than an LSTM language model despite worse perplexity, matching an RNNG trained on binarized gold trees.Induced RNNGs do not improve perplexity over the LSTM, whereas supervised RNNGs do; URNNG fine-tuning further improves results, though its reported F1 is optimistic.
  • Model Analysis: The best compound PCFG’s induced nonterminals align with linguistic constituent labels, and sentence-level latent representations qualitatively capture topical information.The analysis visualizes empirical alignments between induced and gold labels and uses variational-posterior means to identify nearest-neighbor sentences.
  • Limitations: Performance is sensitive to parameterization, grammar size, optimization, and random seed, while training is substantially more expensive than NLM-based parsing because of the O(|R||x|^3) dynamic program.More factorized parameterizations performed worse, and the computational cost may make the approach difficult to scale.

6 Related Work

The paper situates its approach within the progression from early unsupervised grammar induction to statistical, heuristic, neural, and latent-variable PCFG methods. It specifically relates to models using continuous vectors and latent subsymbols in grammar representations.

  • Early unsupervised grammar induction was largely unsuccessful, followed by influential statistical approaches including Clark (2001) and the constituent-context model of Klein and Manning (2002).Early negative results include Lari and Young (1990), Carroll and Charniak (1992), and Charniak (1993), while Pereira and Schabes (1992) reported success on partially bracketed data.
  • Alternative unsupervised parsing methods use random subtree subsets, incremental heuristic decisions, or cascaded applications rather than specifying a grammar and learning its parameters.
  • Recent neural approaches induce trees from words using soft gating in language models, recursive autoencoders with inside-outside inference, structured inference networks, or image-caption grounding.These approaches are associated with Shen et al. (2018, 2019), Drozdov et al. (2019), Kim et al. (2019), and Shi et al. (2019).
  • The work is also related to latent variable PCFGs that split nonterminals into latent subsymbols, including latent vector and compositional vector grammars using continuous vectors.The cited approaches include Matsuzaki et al. (2005), Petrov et al. (2006), Cohen et al. (2012), Zhao et al. (2018), and Socher et al. (2013).

7 Conclusion

This work develops a neural-network approach to grammar induction with PCFGs, first parameterizing rule probabilities from distributed latent-symbol representations and then extending the model with a sentence-level continuous latent vector. The neural PCFG supports linguistically meaningful grammar induction through simple maximum-likelihood learning, while the extension induces dependencies beyond traditional first-order assumptions.

  • The work proposes neural PCFGs whose rule probabilities are parameterized by neural networks over distributed representations of latent symbols.
  • Simple maximum-likelihood learning with the neural PCFG can induce linguistically meaningful grammars.
  • The neural PCFG is extended with a sentence-level continuous latent vector that induces marginal dependencies beyond traditional first-order assumptions.

A Appendix · A.1 Model Parameterization

The model parameterizes rule probabilities with neural networks applied to embeddings for left-hand-side symbols. In the compound PCFG, these inputs are augmented with the sentence-level latent vector z, while the same MLP architecture is retained with adjusted input dimensions.

  • A.1 Model Parameterization: Rule probabilities are generated by applying a neural network to an embedding w_N for each left-hand-side symbol N.The symbols include S, nonterminals, and preterminals.
  • A.1 Model Parameterization: Different rule types use neural transformations of the relevant symbol embeddings to produce their probability parameters.The displayed parameterizations distinguish root, binary, and terminal-related rule types.
  • A.1 Model Parameterization: The parameterization uses separate functions f1 and f2, each implemented as an MLP with two residual layers.The product space is M = (N ∪ P) × (N ∪ P).
  • A.1 Model Parameterization: In the compound PCFG, rule probabilities π_z are conditioned on a latent vector z.The latent vector is concatenated with the corresponding symbol embedding before neural processing.
  • A.1 Model Parameterization: The latent-conditioned parameterization applies the same concatenated-input design across the model’s rule types.The displayed forms include root, binary, and terminal-related rule parameters using inputs such as [w_S; z], [w_A; z], and [w_T; z].
  • A.1 Model Parameterization: The functions f1 and f2 remain unchanged in structure, but their first-layer input dimensions are expanded to accommodate concatenation with z.This preserves the prior neural parameterization while incorporating the latent variable.

A.2 Corpus/Sentence F1 by Sentence Length

Table 6 reports corpus-level and sentence-level F1 broken down by sentence length, averaging results across four runs for each model.

  • A.2 Corpus/Sentence F1 by Sentence Length: Table 6 breaks down corpus-level and sentence-level F1 by sentence length, with each model’s results averaged across 4 runs.The provided passage does not include the table’s numerical values.

A.3 Experiments with RNNGs

The experiments evaluate RNNGs using Kim et al. (2019)’s architecture and compare models under matched capacity, while assessing parsing, perplexity, and grammaticality judgment. Additional details specify the RNNG generation process and fine-tuning setup.

  • A.3 Experiments with RNNGs: RNNG experiments use a 2-layer, 650-dimensional stack LSTM with 0.5 dropout and a 650-dimensional tree LSTM composition function, following Kim et al. (2019).The tree LSTM follows Tai et al. (2015) and Zhu et al. (2015).
  • A.3 Experiments with RNNGs: The RNNG generates sentences by predicting SHIFT or REDUCE from the stack, sampling words after SHIFT, and composing constituents after REDUCE.The SHIFT/REDUCE decision uses an affine transformation followed by a sigmoid, while vocabulary prediction uses an affine transformation followed by a softmax.
  • A.3 Experiments with RNNGs: Fine-tuning uses the discriminative parser pretrained on induced trees as the structured inference network for optimizing the evidence lower bound.The setup follows Kim et al. (2019), with additional details provided through their open-source implementation.
  • A.3 Experiments with RNNGs: All Table 3 models have roughly matched capacity: the LSTM baseline matches the stack LSTM, while PRPN and ON use the same depth, hidden size, and dropout.The LSTM baseline is equivalent to an RNNG with completely right-branching trees.
  • A.3 Experiments with RNNGs: Grammaticality evaluation retains 33K sentence pairs from Marvin and Linzen (2018) after removing pairs containing words unknown to the 10K-word PTB vocabulary.Perplexity for RNNGs and the compound PCFG is estimated using 1000 importance-weighted samples.

A.4 Nonterminal/Preterminal Alignments · A.5 Subtree Analysis

The appendix analyzes how the compound and neural PCFGs align preterminals with part-of-speech tags and nonterminals with gold labels. It also examines subtree-specific constituent patterns using principal components of variational posterior means on the full dataset.

  • A.4 Nonterminal/Preterminal Alignments: The alignment analysis covers both part-of-speech preterminals and nonterminal labels in the compound PCFG and neural PCFG.
  • A.5 Subtree Analysis: Table 8 lists constituents associated with each subtree while varying the top principal component.
  • A.5 Subtree Analysis: Because of data sparsity, the subtree analysis is performed on the full dataset.The analysis is discussed further in section 5.2.
  • A.4 Nonterminal/Preterminal Alignments: Figure 3 compares preterminal alignments to part-of-speech tags for the compound PCFG and neural PCFG.
  • A.4 Nonterminal/Preterminal Alignments: Table 7 reports nonterminal label alignment, predicted constituent frequency, precision, and gold-tree frequency for both PCFGs.Label alignment is defined as the proportion of correctly predicted constituents corresponding to a particular gold label.
  • A.5 Subtree Analysis: For each subtree, PCA is applied to variational posterior mean vectors associated with that subtree, and the five lowest- and highest-scoring constituents are listed.
Loading 1906.10225v9…