On Importance Sampling-Based Evaluation of Latent Language Models (2020)

Abstract: Language models that use additional latent structures (e.g., syntax trees, coreference chains, knowledge graph links) provide several advantages over traditional language models. However, likelihood-based evaluation of these models is often intractable as it requires marginalizing over the latent space. Existing works avoid this issue by using importance sampling. Although this approach has asymptotic guarantees, analysis is rarely conducted on the effect of decisions such as sample size and choice of proposal distribution on the reported estimates. In this paper, we carry out this analysis for three models: RNNG, EntityNLM, and KGLM. In addition, we elucidate subtle differences in how importance sampling is applied in these works that can have substantial effects on the final estimates, as well as provide theoretical results which reinforce the validity of this technique.

## introduction latent language models are generative models of text that jointly represent the text and the latent structure underlying it, such as: the syntactic parse, coreference chains between entity mentions, or links of entities and relations mentioned in the text to an external knowledge graph. the benefits of modeling such structure include interpretability @xcite , better performance on tasks requiring structure @xcite , and improved ability to generate consistent mentions of entities @xcite and factually accurate text @xcite . unfortunately, demonstrating that these models provide better performance than traditional language models by evaluating their likelihood on benchmark data can be difficult, as exact computation requires marginalizing over all possible latent structures. existing approaches evaluate their models by estimating likelihoods using importance sampling, i.e. a weighted average over latent states sampled from a proposal distribution. although convergence of importance sampled estimates is asymptotically guaranteed, results are typically produced using a small number of samples for which this guarantee does not necessarily apply. furthermore, these works employ a variety of heuristics-such as sampling from proposal distributions that are conditioned on future gold tokens the model is being evaluated on, and changing the temperature of the proposal distribution-without providing measurements of the effect these decisions have on estimated perplexity, and often omitting details crucial to replicating their results. in this paper, we seek to fill in this missing knowledge, and put this practice on more rigorous footing. first, we review the theory of importance sampling, providing proof that importance sampled perplexity estimates are stochastic upper bounds of the true perplexity-a previously unnoted justification for this evaluation technique. in addition, we compile a list of common practices used in three previous works-rnng @xcite , enti-tynlm @xcite and kglm @xcite -and uncover a difference in the granularity at which importance samples are aggregated in these works that has a substantial effect on the final estimates. we also investigate a direct marginalization alternative to importance sampling based on beam search that produces strict bounds, and in some cases, has similar performance. last, we perform experiments to measure the effect of varying sample size, aggregation method, and choice of proposal distribution for these models, an analysis that is missing from previous work. from these results we conclude a set of best practices to be used in future work. ## inference in latent lms in this section, we provide an overview of importance sampling-based inference in latent language models, as well as some key theoretical results. latent lms a latent language model is a generative model which estimates the joint distribution p(x, z) of a sequence of text @xmath0, . . . , x t ) and its underlying latent structure z. in this paper, we focus on three models: ## common practices implementing importance sampling for evaluating latent language models involves a number of decisions that need to be made. we need to select the number of samples, choose the proposal distribution, and decide whether to aggregate importance sampled estimates at the instance or corpus level. we list the practices used in previous work. 1 sample size typically, only 100 samples are used for computing the perplexity. a notable exception is @xcite 's follow-up to rnng that uses 1000 samples. proposal distribution previous work uses proposal distributions q(z|x) that are essentially discriminative versions of the generative model (e.g., they are models that predict the latent state conditioned on the text), with one key distinction: they are conditioned not only on the sequence of tokens that have been observed so far, but also on future tokens that the model will be evaluated on (a trait we will refer to as peeking). this conditioning behavior does not contradict any of the assumptions in eqn's (3) and ( 4 ), and is useful in preventing generation of invalid structures (for instance, parse trees with more leaves then there are words in the text), or ones that are inconsistent with future tokens. @xcite and @xcite also increase the entropy of the proposal distribution by dividing logits by a temperature parameter τ (respectively using τ = 1.25 and τ = 2.0). aggregation an oft-overlooked fact (unnoted in previous work) is that eqn (2) can be substituted into eqn (1) in multiple ways. letting x @xmath1, . . . x n } denote a corpus of evaluation data comprised of instances (token sequences) x n , estimates can be formed at the instance level: ## critical evaluation thus far, research has neglected to measure the effectiveness of the practices detailed in section 3. in the following section, we perform experiments to determine whether reporting estimates obtained from small sample sizes is warranted, as well as better understand the consequences of peeking and scaling the temperature of the proposal distribution. for entitynlm we train the model from scratch following the procedure described by @xcite ; results may not be directly comparable due to differences in data preprocessing and hyperparameters. we evaluate models on the datasets used in their original papers: rnng is evaluated on the penn treebank corpus @xcite , entitynlm is evaluated on english data from the conll 2012 shared task @xcite , and kglm is evaluated on the linked wikitext-2 corpus @xcite . experiments for entitynlm and kglm, we experiment with two kinds of proposal distributions: (1) the standard peeking proposal distribution that conditions on future evaluation data, and (2) a non-peeking variant that is conditioned only on the data observed by the model (this is akin to estimating perplexity by ancestral sampling). for rnng we only experiment with peeking proposals, since a non-peeking variant generates invalid parse trees. for the peeking proposal distribution, we experiment with applying temperatures τ ∈ [0.5, 0.9, 1.0, 1.1, 2.0, 5.0]. we report both corpus-level and instance-level estimates, as well as bounds produced using a direct, beam marginalization method we describe later. ## conclusion we investigate the application of importance sampling to evaluating latent language models. our contributions include: (1) showing that importance sampling produces stochastic upper bounds of perplexity, thereby justifying the use of such estimates for comparing language model performance, (2) a concise description of (sometimes unstated) common practices used in applying this technique, (3) a simple direct marginalization-based alternative to importance sampling, and (4) experimental results demonstrating the effect of sample size, sampling distribution, and granularity on estimates. while this work helps clarify and validate existing results, we also observe that none of the estimates appear to converge even after drawing large numbers of samples. thus, we encourage future research into obtaining tighter bounds on latent lm perplexity, possibly by using more powerful proposal distributions that consider entire documents as context, or by considering methods such as annealed importance sampling.