Exposing the Implicit Energy Networks behind Masked Language Models via Metropolis--Hastings
Authors: Kartik Goyal
Chris Dyer
Taylor Berg-Kirkpatrick
Venue: ICLR 2022 Poster (2022)
Keywords: Masked Language Models
Energy-based models
Metropolis Hastings Monte Carlo
Bidirectional Sequence models

Abstract: While recent work has shown that scores from models trained by the ubiquitous masked language modeling (MLM) objective effectively discriminate probable from improbable sequences, it is still an open question if these MLMs specify a principled probability distribution over the space of possible sequences. In this paper, we interpret MLMs as energy-based sequence models and propose two energy parametrizations derivable from the trained MLMs. In order to draw samples correctly from these models, we develop a tractable sampling scheme based on the Metropolis--Hastings Monte Carlo algorithm. In our approach, samples are proposed from the same masked conditionals used for training the masked language models, and they are accepted or rejected based on their energy values according to the target distribution. We validate the effectiveness of the proposed parametrizations by exploring the quality of samples drawn from these energy-based models for both open-ended unconditional generation and a conditional generation task of machine translation. We theoretically and empirically justify our sampling algorithm by showing that the masked conditionals on their own do not yield a Markov chain whose stationary distribution is that of our target distribution, and our approach generates higher quality samples than other recently proposed undirected generation approaches (Wang et al., 2019, Ghazvininejad et al., 2019).

Published as a conference paper at ICLR 2022
EXPOSING THE IMPLICIT ENERGY NETWORKS BEHIND MASKED LANGUAGE MODELS METROPOLIS-HASTING
VIA
Kartik Goyal', Chris Dyer², Taylor Borg-Kirkpatrick CCamegie Mellon University, Deepminn, UC San Diego
ka tartikgo@ttic.ede cdyer e com, tberggeng ucsd. edu
ABSTRACT
While recent work has shown that scores from models trained by the ubiquitous masked language modeling (MLM) objective effectively discriminate probable from improbable sequences, is still an open question these MLMs specify a principled probability distribution over the space of possible sequences. In this paper, we interpret MLMS as energy-based sequence models and propose two energy parametrizations derivable from the trained MLMs. In order to draw samples correctly from these models, we develop a tractable sampling scheme based the Metropolis-Hastings Monte Carlo algorithm. In our approach, samples are proposed from the same masked conditionals used for training the masked language models, and they are accepted rejected based their energy values according to the target distribution. We validate the effectiveness of the proposed parametrizations by exploring the quality of samples drawn from these energy- based models for both open-ended unconditional generation and a conditional generation task of machine translation. We theoretically and empirically justify our sampling algorithm by showing that the masked conditionals on their own do not yield a Markov chain whose stationary distribution is that of our target distribution, and our approach generates higher quality samples than other recently proposed undirected generation approaches (Wang and Cho 2019 Ghazvininejad et al. 2019).
INTRODUCTION
Masked language modeling (MLM) objectives (Devlin et al. 2018 Yang et al. for sequences, although recent, have become ubiquitous for many Natural (NLP) applications (Liu et al. 2019 Zhang et al. 2019 Rogers et al. 2021 because they are easy
2019 Gu et al. 2017)
Language Processing
to optimize and enable learning highly expressive and flexible representations by the virtue of conditioning on bidircctional context (Peters al.) 2018 Devlin al. 2018). However despite their popularity, they lack a principled probabilistic interpretation and hence sampling from MLMs, or characterizing uncertainty about the predictions made with them has remained elusive.
In this work, we posit that optimizing MLM objectives results in training of implicis energy-based sequence models that correspond to probability distributions over natural language sequences by assigning score to each possible sequence in the large but finite sequence space. To explore the veracity of this claim, we develop and experiment with two energy parametrizations (or scoring schemes) that can be easily derived from the representations learned by the trained MLMs' transformer networks. These parametrizations have been inspired by the success of recent work on using MLMs for sentence-level judgements for discriminating between probable and improbable sequences (Salazar al.; Zhang al., 2019). Although, easy to compute the energy/score of sequence with these MLM-based parametrizations, the bidirectional nature of MLMs precludes efficient sampling algorithms like ancestral sampling. Therefore, a primary contribution of our work to develop Metropolis-Hlasting (MlI) based sampling algorithms for these MLM-based energy networks. While it is tempting to formulate a Gibbs sampling scheme (Gelfand and Smith 1990) based on the positional masked conditional distributions used for training the MLMs (Wang and Cho 2019). we theoretically and empirically demonstrate that these masked conditional distributions do not necessarily correspond to any joint distribution or energy network and hence result in invalid Gibbs samplers. Instead,

---

Published as a conference paper at ICLR 2022
propose to use these masked conditionals as proposal distributions for transitioning to new state (sequence) in the Markov chain of an MCMC sampler based on the Metropolis -aattingg algorithm (Hastings 1970). Another contribution of our work is to design a flexible non-contiguous block- replacement proposal distribution to improve mixing of the Markov chain in our proposed MH sampling framework, which results in faster generation and better samples.
We empirically investigate the effectiveness of the two proposed energy parametrizations by examin- ing the quality of samples drawn from these energy-models in two diverse settings: 1) conditional generation task of Machine Translation (MT), and 2) Open-ended unconditional generation. We observe that high BLEU scores for MT, and high fluency scores are correlated with low energy values which indicates that these parametrizations are reasonable proxies for the desired implicit bidirectional energy network trained via the MI.M objective. We study the behavior of our sampling approach extensively with different proposal distributions. We also verify the soundness of our ap- proach by sampling from regions around the mode by annealing the target distribution and finding our samples to be competitive with prominent undirected (and cou-probablistic) generation approach (Ghazvininejad et al. 2019) on MT performance, Moreover, human evaluation of the open ended generation samples further corroborates the effectiveness of our approach.
Much of prior work on baaeed methods has, in contrast to our work, focused on explicitly training energy networks from scratch. Gradient based training of energy networks (LeCun et al. 2006, Zhao et al. 2016 Du and Mordatch, 2019) has been successful at training models for inducing distributions over continuous domains but are not suitable for training discrete sequence models for text. To overcome this problem, recent work has proposed continuous relaxations to the
Related work:
discrete domain (Belanger and McCallum 2016 Grathwohl al. [02I], but the unordered nature of discrete symbols in text makes it difficult for these models to be effective large scale language models. WWang and Ou (2017) train text-based energy networks directly via MCMC sampling with a CNN-LSTM based energy network and a backbone of autoregressive proposal distribution, but find to be computationally expensive. For more practical unnormalized models, NCE based training objectives have also been considered (Deng et al., 2020 Wang and Ou 2018) in prior work. The parametrization and training of these energy based text models relies on a backbone autoregressive model (Brown et al. 2020: Sutskever al. 2014), which causes the resulting energy model to be heavily affected by the underlying base autoregressive model, and leads to left-to-right generation procedures that preclude non-contiguous block sampling. Other training approaches for energy based text models include decoding based approaches (Goyal et al., 2019; [Wiseman and Rush (016)) and score-based approaches (Zhang et | (017)). All of these approaches more expensive than training probabilistic autoregressive models like GPT-3, and hence adoption of energy based unnormalized models for large scale language modelling has been under-explored.
In this work, instead of training computationally expensive energy networks on large scale data, we focus on interpreting large pretrained MLMs as energy-based models and propose methods sample from them. The MLM objectives (Devlin et al. 2018 Clark et al., 2020a b) are easy to scale to large amounts of data and learn good representations of the textual data, but they do not have a probabilistic interpretation. While there have been attempts to train MLM-based non-autoregressive sequence models and generate sequences from the MLMs in a
manner (Wang and Cho 2019] Ghazvinineeaad et al.) 2019 Tu et al. 2020 Gu et al. 2017, Mansimov et al.) 2019), our technique samples correctly from the energy networks underlying MLMs that correspond to our proposed parametrizations, Our detailed experiments with the proposed sampler provide evidence that masked language modelling objectives result in implicit training of an energy network, and these findings suggest that further exploration in future work, of variants of these objectives for explicit training of large scale energy networks is a worthwhile endeavour.
MASKED LANGUAGE MODELS AND ENERGY NETWORKS
Let X' be the space of all finite sequences up to maximum length, and p(X;0) be the probability of the sequence X E X under the target distribution defined by the energy function E) parametrized by 0, defined as follows:
e
B(X
((x,0)
p(X:0) Exexe-B(110) B(X'00)
Z(0)
where ø represents the unnormalized score of the sequence X and Z(0) is the intractable normal- ization constant computed by summing over all the sequences. We propose two parametrizations of
2

---

Published as a conference paper at ICLR 2022
energy functions that potenitally correspond the implicit networks trained via MLM objectives: 1) raw scoring, and 2) Locally normalized scoring. These parametrizations yield scoring functions that have been considered useful in prior work. These scoring functions use the same computational mechanisms as typical computation of conditional distributions of the [MASK] tokens with ML.ss
2.1
Raw SCORING
For each position & in the sequence X of length T, we associate a random variable X2 E V with the t-th token, where V is the vocabulary. MLMs learn a representation ()),,), for X, that is sensitive the bidirectional surrounding context xt For notational convenience, we use Xm=w.Ar to denote sequence X with the f-th variable taking on the value w. We use such bidirectional neural parametriza- tions to define an energy Eraw for X that corresponds to fully connected Gibbs random fields as the sum of the local positional scores: Eraw (X: = =t= log (xx;; f), where log (X; 6) = fX,,, h (e)) 9). In our experiments, the positional pogg-ooeetials. f(X,, ())) 0) are computed by masking the position i, then running forward pass on the MLM's transformer and using the raw logits the masked position.
Conditional distribution under Fram: Performing Gibbs sampling from the MRF defined by Friw requires computation of this conditional distribution of token given the surrounding context:
II. (X;0) x(X,|X Ewey II. Φe ((((((i= (((X===
Computing this conditional is very expensive and would require running V| passes of the MLM decoder just for computing the positional potential (Φt) at a single position because these potentials form fully connected cliques. Thus, we do not perform Gibbs sampling and instead propose MH based samplers described below.
Relationship with the masked conditionals of MLMs: Wang and Cho (219)'s 's prior attempt to interpret MLM (like BERT) as an MRF incorrectly assumes that the positional potentials are independent of each other and hence are not defined on fully connected clique, i.e. di (X:0) (X,;;) 0). This faulty assumption about the factorization of the positional potentials (x(X; leads to the following formulation of conditional distribution:
II. (X) Σ II. ((X = WEY
(X
Pmlm X, ():
softmax(log db)
Σ (X::0)
(X::00 tgf
X
This deficient conditional distribution for the MRF corresponds to the free conditional distribution Pmlm (X, Xx.)) that is obtained by performing a softmax operation over [MASK] scores (E RV) used in the MLM training objective. These MLM free conditionals do not correspond to the MRF defined by Frow i.e. Pmim X; xx) # p(X,) | , 0( (). In fact, these conditionals need not correspond to any consistent MRF over the sequences. As an example, consider sequence of length 2 with aequeen
the random variables X1, X2 that have a categorical distribution over a vocabulary V = {a, b). The following free conditionals are inconsistent (see Appendix) because they do not correspond to any
[0.99 0.01
0..5 0.5
valid joint distribution over X2): p(X1 X2) 0.01
0.99 (x X2
0.5 It
0.5
should be noted that prior work on dependency networks (Heckerman et al. 2000) proposed a similar
scheme of training the conditionals independently with separate regressions over the latent variables and the inconsistency of such conditionals well documented (Gelman and Raghunathan 2001
Dobra al. 2004 Lowd 2012).
Wang and Cho (011 used the masked conditionals to define a pseudolikelihood ( Pmnm (X, X);;)) maximization objective and argued that MLM training can be interpreted as stochastic maximization of this pseudolikelihood corresponding to the energy function Eraw. However, this is incorrect because the conditionals used to define the pseudolikelihood under Er are deficient and likely inconsistent. Despite the incongruity between MLM training and minimization of Eraw, we propose to use Eraw as one of the parametrizations of the energy function.
This was addressed in their subsequently published erratum: https:://tttit 1tt.bitt.1/2/2x22//tt
3

---

Published as a conference paper at ICLR 2022
2.2 LOCALLY NORMALIZED SCORING
Recent work (Zhang et al. 2019) has shown that MLMs like BERT can be used to reliably score set of sequences. Salazar al. and Clark et al. (2020a) developed scoring scheme rescore hypotheses proposed by the beam search algorithm and showed downstream improvements over automatic speech recognition (ASR) and machine translation (MT) datasets. The scoring scheme corresponds to masking tokens one-by-one in left-to-right manner and summing the log-probability of the token at each masked position in the sequence: Emorm (X: - Σ log Pmlm (X, [X f). This scoring scheme is also implicitly used while performing beam search with the non-autoregressive NMT models proposed in Ghazvininejad et al. (019). Because of this scheme's success, we propose this as another parametrization which requires just one change in the computational procedure for -naw-instead of summing up logit scores each position, this energy is computed by summing up post softmax values at each position.
BACKGROUND: METROPOLIS HASTINGS
Metropolis Hastings (Hastings 1970) is an MCMC algorithm that provides a recipe for sampling from the distribution via proposal distribution g(X' XX,)) parametrized by % which defines transition from sequence X to the sequence X' in the Markov chain. It assumes the ability to compute the unnormalized score ((X) for every sequence X. At each sampling step we first draw a proposal X' from the proposal distribution. Then, we either transition to this new state with the acceptance probability a(X"; X). or repeat the sequence X in the Markov chain. The acceptance probability for the step that ensures that the MCMC sampler satisfies detailed balance
is: a(X;; X) min (1, e(X') q(X]x') Additionally, since it is highly unlikely that the neurally x(X) Q(XTX)
parametrized models like MLMs will assign any sequence probability 0, it is safe to assume ergodicity of the Markov chains with this sampler, which guarantees convergence to the desired target energy network distribution p. In experiments, the unnormalized score 6(X) is computed by using the transformer parametrization of the MLM of interest. Both our energy formulations involve computing positional potentials which are obtained by iteratively masking the token each position and running the forward pass of the MLM transformer.
Algorithm Metropolis Hastings algorithm for MLMs
1: Input: MLM transformer a. Energy function fs. MLM conditional proposal frlm ,eeuuence length T, number of epochs E
2: Initialize: X <- [MASK] T
+ greedy-decode (MLM(()))
> Warm-start with a random sequence
4: for e=0 to E do
5: for t=0 to do
left-to-right or random position selection Energy of sequence X, O(T) op. Store the t-th token in X w. and mask it. Sample w,, from MLM conditional to propose X'.
6: Egua +- (X()(X))
X' - X, Wo X1, X² [MASK] f- wn
Wr, ~ [mim (x(),, 1).
9:
q(X' X) = smlm (X), (w]]] q(X X') = fmim (X)) [)[w.]
10:
Exew <- (x()
D Energy of proposed sequence X', O(T) op.
11:
a X) <- min
Euee q(X(X')
Acceptance prohability of the MC transition.
Eau ()) if ((00 1), S a then X + X"
12:
13:
Output: sampled sequence X
3.1 MASKED CONDITIONALS AS PROPOSAL DISTRIBUTION FOR THE MH SAMPLER
As we discuss in Section 2.1, the masked conditionals used train MLMs do not correspond to the two energy formulations we experiment with and are not appropriate for performing Gibbs sampling. In fact, our experiments demonstrate that performing Gibbs sampling using these masked conditionals leads to low-quality samples. However, these conditionals have been shown to be useful for scoring individual sequences and non-autorregresivee generation. Therefore, we propose to define the proposal distribution s(X' X)) for the Hattoppolis-Hstting sampler by these masked conditionals. More concretely, to transition from the sequence X, we first mask the token in X at position i, i... X; [MASK]. Next, do Transformer decoder pass and get the masked conditionals Pramm at position i. Then, the probability of the transition to sequence X' is the masked probability of the token at the i-th position in X', i.e.: qX'' X) Pmnm XX 0), where X₁.
4

---

Published as a conference paper at ICLR 2022
0). For both Gibbs sampling and MH sampling schemes, sweep over all the positions in random order while generating sequences of certain length. We denote one complete sweep over all the positions in a sequence of length T by the term epoch. We summarize our general approach in Alg. [
X and q(X
X = Pmim (X
Computational complexity: Amortizing the encoder cost and the cost of performing a softmax operation, if we denote the cost of doing one Transformer decoder pass over masked sequence by C, then the computational complexity of evaluating MLM conditional is O(C)). For E' epochs and sequence of length T. the cost of running Gibbs sampler OC)) For the MH sampler. we additionally need to compute the unnormalized scores x(X) which, for both the proposed parametrizations of energy, require masking of each position sequentially and running a Transformer decoder pass for each masked sequence. Hence the MH sampler is more computationally expensive with the complexity O(TEEC)
3.2 VARIANTS OF PROPOSAL. DISTRIBUTION
We studied our sampler with multiple proposal distributions. While all the variants of proposal distribution rely heavily on the masked conditionals from the pretrained ML.M, they have different properties and as shown in the results, they exhibit very different behaviors.
Varying temperature: We experiment by changing the entropy of the masked conditionals via a temperature hyperparameter T: g(X' | (xT)- = Pmim (x 0, T) softmax 1og
T
Variation based on Nucleus Sampling: We experiment with another method of changing the entropy of the masked conditional distribution that is inspired by Nucleus Sampling (Holtzman et al., 2019). It involves defining nucleus boundary b, which prunes out the long tail of the vocabulary that falls outside of the cumulative probability b followed by renormalization over the pruned vocabulary Vo which is the smallest set such that Ewey, Pmlm (X) = X 8) 2 b.
Block MH sampling: Block sampling methods like block Gibbs sampling (Gelfand 2000) result in better mixing of the Markov chain because they allow for perturbations multiple variables. In our approach, we mask out multiple tokens in a sequence X in order to propose a new sequence X". Let I be the set of positions by which X and X" differ. Then, the proposal distribution for the MH sampler is: [X' X) = Ilgg Pmlm (Xmmm((]]_))) Xxz; 0). This makes sampling faster due to parallelization of prediction at several positions, and results in generation of better samples.
4 IMPLEMENTATION DETAILS
Pretrained Masked Language Model: We empirically study the proposed Metropolis Hastings scheme on the conditional generation task of neural machine translation (NMT) and the task of uncon- ditional generation. For unconditional generation we used HuggingFace' 's pytorch implementation of uncased BERT-base and BERT-large. For NMT, to perform fair comparison we use the pretrained model mo optimized by prominent non-autoregressive algorithm-MAsk -ASK--RDIICI (Ghazvininejad iet al., 2019). This non-pree probbbbbbiiiittc algorithm uses a bidirectional Transformer (Vaswani et al. (017)) to encode the source-side sequence and trains the target-side bidirectional waasformer-bassee decoder via the ML. objective while performing iterative refinement for decoding. We implemented our sampler and parametrizations on top of this code-base for non-autoregressive MT.
MCMC details for NMT: For all the sampling baselines, after a burn-in period of 7 epochs, we ran the Markov chain for least 26 epochs over the dataset. The length of the target sample was decided by using a length predictor of MASK-PREDICT that estimates the length conditioned on the source sentence. For all of our sampling results described, we ran at least 5 Markov chains for each configuration described in the subsequent sections and report averaged statistics over these runs.
MCMC details for unconditional generation: For the reported experimental settings, we ran 500 chains for 100 epochs to produce 500 sequences of diverse lengths varying from 15 - 45. For each of the Markov chains, we randomly select a length and start with sequence consisting entirely of [MASK] tokens. We accept all the proposals until all the masked tokens are filled out in order to start the chain from a random sequence.
Data for NMT: We performed experiments via translating the validation and test sets of the WMT-14 German-Englist (De-En), and the 16 Comanian-Englin (Ro-En) datasets and perform the same tokenization and pre/post- Ghazvininejad et al. 2019
5

---

Published as a conference paper at ICLR 2022
Evaluating quality of samples: Aside from considering the energy values of the samples under our parametrization and other measures of qualitative evaluation, we report the following automatic metrics for NMT and unconditional generation respectively: 1) BLEU scores the reference corpus give an idea about the practical quality of samples for conditional generation in low-entropy settings like NMT, 2) GPT2-xl (Radford et al. (019) sentence perplexity (not token normalized) of random unconditionally generated samples provides a reasonable idea of the fluency of the generated sequence. Compared to the BERT models, GPT-2 is an autoregressive language model that has been trained on larger amount of internet data than the BERT models.
5 METROPOLIS HASTINGS AND Degenerate GIBBS SAMPLING FOR MLMS
In this section, we empirically compare our proposed MH Sampling approach with both the energy formulations described in Section 2 (raw and norm) the alternative proposed by Wang and Cho (2019) of performing Gibbs sampling with the masked free conditionals which we refer to as degenerate Gibbs sampling (deg).
Clobe
Norm
Raw
Cibba
Nom
Rane
00824
4.00
200444
BLEU
40004
40%244
burn-in
Epochs
burn-in
Figure 1: Fmomm (left) and BLEU scores (right) De-En (20) for NMT as function of epochs for the two MH schemes (raw and norm) and the degenerate Gibbs sampling scheme (deg), We compute and report Enorm even for the samplers with Eraw parametrization.
In Figure 1 we notice that for NMT, although all the samplers start with the same random sequence, the proposed MH samplers generate high quality samples with low energy values and consistently good BLEU scores across all the epochs. The degenerate Gibbs sampler however, keeps degrading to generating sequences with very low BLEU scores and high energy values. We also observe that sequences with high BLEU scores typically have low locally normalized energies which explains the success of prior work in using these locally normalized scores for re-ranking beam search hypotheses and generating sequences with high BLEU scores (Salazar et al.) Ghazvininejad et al.) 2019). For open-ended generation we observed a similar pattern that the energy values deteriorate as the degenerate sampler is run longer, but the chain with Enorm was consistently worse than Fraw-
Next, we examine the acceptance ratio of the MH samplers. We focus on the average proportion of novel MC Iransition rale-the ratio of proposals that were distinct from the previous state and accepted-which indicates the entropy of the MCMC transition distribution. For NMT, the degenerate Gibbs sampler has acceptance probability of 1.0 by design and a novel transition ratio of 0.36, which indicates that the MLM conditionals are fairly peaked. Both the MH samplers have high acceptance rates (0.9 and 0.91) but much lower novel transition ratio-O. 0.11 for RAW and 0.13 for RAW. This indicates slow mixing of the MH Markov chain. For unconditional generation, the novel transition ratio of the degenerate sampler is higher 0.58, but it is slightly lower for the MH samplers- 0.10 for RAW and 0.08 for RAW. This suggests, that the BERT conditionals yield proposals that are rejected at a very high rate under our parametrization schemes for open-ended generation.
RESULTS WITH VARIANTS OF PROPOSAL DISTRIBUTIONS
6.1 EFFECT OF TEMPERATURE
In this section, explore the effect of temperature on the proposal distributions parametrized by the MLM conditionals as described in Section 3.2 varying the proposal distributions from high entropy to low entropy. In Tables T and we see that for MT, the MH sampler performs similarly across

---

Published as a conference paper at ICLR 2022
all the temperature values with the performance improving slightly for lower temperature values, however unconditional generation is significantly more sensitive to the temperature changes, with worse performance at the higher temperature. The degenerate Gibbs sampler in general trails behind MH samplers but drastically improves with the lowering temperature values. At low temperatures, it yields decent BLEU scores and more fluent sentences but it is noteworthy that the energy values are worse than the MH sampler. Most interestingly, the novel transition rates reflect the effect of
Table Average Enom 10-3 energy, novel MC transition rate, and BLEU scores for NMT across interleaved epochs for the degenerate Gibbs sampling (deg) and the locally normalized energy MH scheme (Norm) on De-En (20) under ML.M proposal distributions with varying temperatures.
Temp
2.0
1.5
1.0
0.8
0.5
norm
deg
norm
deg
norm
deg
norm
deg
norm
deg
Enom 12.87
32.46
10.21
29.57
11.13
31.12
9.95
21.12
7.85
17.65
Novel 0.03
1.0
0.05
0.97
0.11
0.36
0.06
0.08
0.03
0.04
BLEU 25.91
14.53
24.78
10.12
24.74
9.03
25.84
24.77
27.23
26.12
Table 2: Average Enw energy, novel MC transition rate, and average GPT-2 sentence perplexity for unconditional generation across generated sequences for the degenerate Gibbs sampling (deg) and the raw energy MH scheme (raw) under MLM proposal distributions with varying temperatures.
Temp
1.2
1.0
0.8
0.5
raw
deg
raw
deg
raw
deg
raw
deg
Eraw + 25.95
201.24
19.82
83.23
13.54
23.24
9.91
10.05
Novel +
0.09
0.82
0.09
0.81
0.08
0.25
0.06
0.09
GPT-2 4
223.87
2238.6
108.12
314.74
82.23
88.15
77.44
77.98
temperature very clearly. At high temperatures, the degenerate Gibbs sampler almost never proposes consecutively repeating transitions while in stark contrast, the novel transition rate of the MH sampler is extremely low. This is because of high rejection rates under the unsuitable high-entropy proposal distribution. While the results for low-temperature settings seem to suggest that the degenerate Gibbs samplers are practically useful samplers, examining novel transition rates dispels this suggestion. At low temperatures, the novel transition rate is extremely small for the degenerate sampler indicating low-entropy of the MLM based transition distribution which in turn reduces the novel transition rates of the MH sampler as well. Hence, the impressive now-temperature results only corroborate the results of recently proposed nonpprobaiilistii MLM-basee generation models like MASK-PREDICT (Ghazvininejad et al. 2019) that do not explore the sequence space at all.
6.2 EFFECT OF NUCLEUS SAMPLING
Adjusting the nucleus boundary to lower values decreases the entropy of the MLM proposal distribu- tion. In Table 3] we observe effects of changing nucleus boundary that are similar to the effects of lowering temperature- decent samples accompanying sharp decrease novel transition rate. These patterns of sensitivity to the proposal distribution's 's entropy (Tables 12 strongly suggest that while the MLM objectives results in conditionals whose mode corresponds high quality sequences, these conditionals are poorly calibrated and are not suitable for exploring the distribution over sequences via direct sampling.
Table 3: Average Enom x 10-3 energy, novel MC transition rate, and BLEU scores energy for the degenerate Gibbs sampling (deg) and the locally normalized energy MH scheme on De-En (20) under MLM proposal distributions with varying nucleus boundary.
Nucleus
1.0
0.99
0.95
0.90
0.80
norm
deg
norm
deg
norm
deg
norm
deg
norm
deg
Enomn
11.13
31.12
10.65
30.12
10.21
28.75
9.95
18.57
9.85
18.23
Novel <>>
0.11
0.36
0.12
0.33
0.10
0.22
0.07
0.10
0.05
0.06
BLEU
24.74
9.03
24.95
14.03
26.15
18.04
27.35
23.25
27.23
23.55
7

---

Published as a conference paper at ICLR 2022
6.3 EFFECT OF BLOCK MH SAMPLING
In the results so far, we have observed that while the MH samplers yield good samples, their novel transition rate (0.11-0.13) is fairly low which results in slow mixing of the Markov chain. To improve the mixing rate we experiment with the proposal distribution for block MH sampling as describe in section 3.2 Because perturbations of rejection of the new MH proposal, we balance exploration with tolerable rejection by annealing the number of masked positions with epochs. At the start of the Markov chain, we make large changes, but gradually make smaller changes as the chain progresses (details in Appendix). We also, experiment with a block Gibbs sampling variant of our degenerate Gibbs sampler. This block Gibbs sampler is incorrect well, however, it is interesting it yields the MASK-PREDICT (Ghazvininejad et al. 2019) algorithm. We specify the results while keeping the other settings like temperature and nucleus boundary at their default value of 1.0.
large number of positions also increase the chance
study because with temperature T 0.0,
Table 4: Left: Average BLEU scores, Exor X 10 10-3, 3, and novel transition rates, Right: Average GPT-2 sentence perplexity, Eaww and novel transition rates for the two Block variants of the MH schemes (raw and norm) and the degenerate block Gibbs sampling scheme (deg).
Deg
Raw
Norm
Deg
Raw
Norm
Enom Novel ++
31.18
8.08
8.17
Eusw + Novel <+
81.87
18.43
17.67
0.77
0.40
0.41
0.80
0.21
0.20
BLEU 9.03
27.12
26.78
GPT-2 4
166.29
43.21
92.23
In Table 4 we notice that degenerate block Gibbs sampler performs poorly, while both the MH samplers show improvements in terms of BLEU, energy values, and GPT-2 scores over previous non-block MH sampling settings under default conditions. Notably, these results highlight differ- ences in the samplers' behaviors across a constrained generation task like MT, and unconditional generation. For unconditional generation, we see a clear difference performance between the energy parametrizations with Eraw being superior to Fnorm This suggests that for complex high- entropy distributions, the normalization constraint in Fmam results in inferior energy functions over sequences. Moreover we notice that while our shock-sapplnng scheme drastically increases the novel transition rate (Re 0.12 + 0.41) for MT, the increase is less impressive for unconditional generation (~< 0.09 > 0.20). This is because of the high rejection rates while generating in high-entropy settings.
7 ANNEALING THE ENERGY FUNCTION: SAMPLING AROUND THE MODES
In this section, we analyze the effectiveness of our proposed MH samplers by evaluating the samples drawn from regions around the mode of the energy functions and evaluating them against references for the task of MT. To achieve this, we propose to perform MH sampling from target distributions
-E(X:9)
However, such low-entropy target distributions lead to increased rejection rates for the MH samplers. Therefore, we anneal the temperature as a linear function of epochs gradually decrease the entropy of the target distribution. In Figure (left, green), we observe that annealing results in dramatic improvements in locally normalized energy scores Enorm leading to very low energy values. When comparing the
whose energy values are scaled by low temperatures i.e. (X;0, T) x e
Nonn
Raw
E. (namm)
Local
-3000
Acceppercce Ratio
-400
(porm)
0:6
-3000
0.4
-2300
25
Epoche
Epocha
Figure 2: Comparison as a function of epochs for the two energy parametrizations (red, blue) for MH approach with annealing toward modes of target energy functions: Fraw and Fnom De-En (20). Left: acceptance rates, locally normalized energy (green) as function of epochs. Right: MT performance.
acceptance rates, we that Fraw and Framm behave differently as the target distribution temperature
8

---

Published as a conference paper at ICLR 2022
annealed, with the MH samplers under the Eraw target distribution exhibiting larger acceptance rates across the epochs. This difference in acceptance rates also manifests itself in the performance in terms of BLEU scores of the samples under two energy parametrizations, with raw energy parametrization yielding higher BLEU scores. In Table 5
we compare the performance of our annealing- baased
Table 5: Performance of annealing based approach for sampling around the energy-based distributions' modes. BLEU scores reported on the full De-En and Ro-En test sets.
Baseline
De-En
Ro-En
MH samplers
De-En
Ro-En
Warm-start
20.27
24.38
Local Energy
29.74
31.13
Degenerate Gibbs (T=0.8)
27.88
29.79
Raw Score Energy
30.12
30.86
Mask-predict (beam=1, It=10)
29.27
29.95
Autoregressive
30.18
31.53
mondefinding approach on the task of machine translation with other related algorithms (details in Appendix). Warm- start refers to the greedy replacement of all the mask tokens with the pretrained MLM which is used as the starting sequence for our Markov chains. While it performs reasonably well, all the other approaches outperform it. We mainly compare our approach (Local and Raw score Energy) to the non-probabillistic MASK-PREDICT algorithm (Ghazvininejad et al. 2019). We outperform both, the degenerate Gibbs sampler (T 0.8) and MASK-PREDICT. Although, the autoregressive approach is superior to the MASK- PRTT-TT baseline, we perform competitively with it. As better MLM based NAT models are proposed for translation, our approach provides way to interpret them probabilistically and draw samples from them.
QUALITY OF UNCONDITIONAL GENERATION
We conduct human evaluation of our most basic setup-default parameters with non-block MH sampling. Although, |Wang and Cho 2019) use low temperature values, and top-k truncation to get high quality generations from the degenerate Gibbs sampling scheme, we do not perform any top-k pruning and keep the temperature at 1.0 for the MLM conditionals used for the degenerate Gibbs sampler and the proposal distributions for the MH samplers because we are interested in exploring the behavior of the conditionals and the energy functions yielded naturally by the MLM training objective. As we observed in Tables 2 3 such measures to reduce entropy the MLM conditionals like pruning, and low temperatures yield decent looking samples at the cost of reduced diversity and exploration. 3 humans familiar with the generation capabilities of language models were presented with 120 sentences generated by BERT-base and BERT-large with our proposed samplers, and were asked to provide 4-point likert ratings along two axes: coherence and fluency. We notice in Table 6 that our samplers outperform degenerate Gibbs sampling scheme and Fraw Table 6: Coherence, Fluency (averaged across examples and humans), average GPT-2 sentence perplexity for sentences generated unconditioned by the degenerate Gibbs sampler (deg), and proposed MH samplers (norm and raw) with 2 different MLMs: BERT-base (base) and BERT-large (large).
base-deg
base-norm
base-raw large-deg large-norm large-raw
coherence
1.23
1.6
2.05
1.15
1.7
2.0
fluency 1.2
1.82
2.45
1.15
1.9
2.25
GPT-2 1
296.45
184.21
125.42
310.22
175.43
132.76
better suited for unconditional generation than Fm Our samplers generally are more fluent than coherent. This is expected because pure unconditional generation is not constrained by any conditioning context resulting in low coherence. Interestingly, there is little difference in sample quality between BERT-base and BERT-large.
CONCLUSION
based sampler enables us to draw high-quality samples from con-probabilistic masked language models. The empirical analysis and success of our approach with the two proposed energy parametrizations strongly suggests that the optimization of MLM objective results in training of an implicit global energy network that induces probability distribution over the space of sequences and its possible to sample from using our method. While we primarily focus on findings open up avenues for devising more direct, stable and simple training (Deng et al. (020)) procedures for large-scale energy-based sequence models inspired from the MIM objectives and our proposed MH sampling scheme.
Our proposed
sampling and generation,

---

Published as a conference paper at ICLR 2022
REFERENCES
D. Belanger and A. McCallum. Structured prediction energy networks. In International Conference on Machine Learning, pages 983-992. PMLR, 2016.
B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
K. Clark, M.-T. Luong, Q. Le, and C. D. Manning. Pre-training transformers anergy-based cloze models. In Proceedings of the 2020 Conference on Empirical Methods Natural Language Pro- cessing (EMNLP), pages 285-294, Online, Nov. 2020a. Association for Computational Linguistics. doi: 00011863/w1/2220.cmm
awwweb.clwbbb.... argg/nnthlogy///// main..0...... URL https: http::/wwwwwwlll..
2020. emn 1p main. 20
K. Clark, M.-T. Luong, Q V. Le, and C. D. Manning. Electra: Pre-training text encoders as discriminators rather than generators. arXiv preprint arXiv:2003 2020b.
Y. Deng, A. Bakhtin, M. Ott, A. Szlam, and M. Ranzato. Residual energy baaey models for text generation. arXiv preprint arXiv:2004.17744 2020.
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
A. Dobra, C. Hans, B. Jones, J. R. Nevins, G. Yao, and M. West. Sparse graphical models for exploring gene expression data. Journal of Multivariate Analysis, 90(1):196-212, 2004.
Y. Du and I. Mordatch. Implicit generation and modeling with energy based models. 2019.
A. Gelfand. Gibbs sampling. Journal of the American statistical Association, 95(452):1300-1300 2000.
A. E. Gelfand and A. F. Smith. Sampling-based approaches calculating marginal densities. Journal of the American statistical association, 85(410):398-400 1990.
A. Gelman and T. E. Raghunathan. Using conditional distributions for missing-data imputation. Statistical Science, 15:268-40 090886662220 2001.
M. Ghazvininejad, O. Levy. Y. Liu, and L. Zettlemoyer. Mask-predict: Parallel decoding of condi- tional masked language models. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing, 2019.
K. Goyal, C. Dyer, and T. Berg- Berg-Kirkpatrick. An empirical investigation of global and local normal- ization for recurrent neural sequence models using a continuous relaxation to beam search. In Proceedings of 2019 Annual Conference of the North American Chapter of the Association for Computational Linguistics, 2019.
W. Grathwohl, K. Swersky. M. Hashemi, D. Duvenaud, and C. J. Maddison. Oops took a gradient: Scalable sampling for discrete distributions. arXiv preprint wwXii:2102.045000 2021.
J. Gu, J. Bradbury, C. Xiong, V. O. Li, and R. Socher. Non-autoregressive neural machine translation. arXiv preprint arXiv: 17 2017.
W. Hastings. Monte carlo sampling methods using markov chains and their applications. 1970.
D. Heckerman, D. M. Chickering, C. Mcck, R. Rounthwaite, and C. Kadie. Dependency networks for inference, collaborative filtering, and data visualization. Journal of Machine Learning Research, 1 (0ct):49-75, 2000.
A. Holtzman, J. Buys, I.. Du, M. Forbes, and Y. Choi. The curious case of neural text degeneration. arXiv preprint arXiv: 009400971, 2019.
Y. LeCun, S. Chopra, R. Hadsell, M. Ranzato, and F. Huang. tutorial on energy-based learning. Predicting structured data, 1(0), 2006.
10

---

Published as a conference paper at ICLR 2022
Y. Liu, M. Ott, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer, and V. Stoy- anov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 1XX.:1907.1199. 2019.
D. Lowd. Closed-form learning of markov networks from dependency networks. arXiv preprint arXiv:1210.4896 2012.
E. Mansimov, A. Wang, S. Welleck, and K. Cho. A generalized framework of sequence generation with application undirected sequence models. arXiv preprint arXiv: /2790, 2019.
M. E. Peters, M. Neumann, M. lyyer, M. Gardner, Clark, K. Lee, and L. Zettlemoyer. Deep contextualized word representations. arXiv preprint wrxXiv:/82..55.55 2018.
A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, al. Language models unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
A. Rogers, O. Kovaleva, and A. Rumshisky. A primer in Bertology: What we know about how BERT works. Transactions of the Association for Computational Linguistics, 8:842-866, 2021.
Salazar, D. Liang, T. Q. Nguyen, and K. Kirchhoff. Masked language model scoring.
I. Sutskever, O. Vinyals, and Q. V. Le. Sequence to sequence learning with neural networks. arXiv preprint arXiv: 1409.3440 2014.
L. Tu, R. Pang. Wiseman, and K. Gimpel. Engine: Energy- inference networks for non-autor autorrrrrrreevv machine translation. arXiv preprint arXiv:2005.00855 2020.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention all you need. arXiv preprint arXiv: meo::000660666 2017.
A. Wang and K. Cho. BERT has a mouth, and must speak: BERT as a Markov random field language model. arXiv preprint 1903:v:992.044000 2019.
B. Wang and Z. Ou. Language modeling with neural trans-dimensional random fields. In 2017 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU), pages 294-300, IEEE, 2017.
B. Wang and 7. Ou Learning neural trans-dimensional random field language models with noise- contrastive estimation. 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 6134-6138. IEEE, 2018.
S. Wiseman and A. M. Rush. Sequence-to-sequeeee se-uueeece learning as beam-search optimization. arXiv preprint arXiv: arXiv:1606.00 1606.6696660 2016.
Z. Yang, Z. Dai, Y. Yang. J. Carbonell, R. Salakhutdinov, and Q. V. Le. Xlnet: Generalized autoregressive pretraining for language understanding. arXiv preprint 1rXiv:1906.08237 2019.
Zhang, V. Kishore, F. Wu, K. Q. Weinberger, and Artzi. Bertscore: Evaluating text generation with BERT. arXiv preprint arXiv:1904.09677 2019.
Y. Zhang, Z. Gan, K. Fan, Z. Chen, R. Henao, D. Shen, and L. Carin. Adversarial feature matching for text generation. In International Conference on Machine Learning, pages 4015-4015. PMLR, 2017.
Zhao, M. Mathieu, and Y. LeCun. Energy-based generative adversarial network. arXiv preprint 1rXiv:160. 2016.
11

---

Published as a conference paper at ICLR 2022
A APPENDIX
In this appendix, we elaborate on the counter example in section 2.1, explore the effect of annealing the block size function of epochs for our proposed block sampling scheme, discuss ethical considerations pertaining to our approach and the data we used, describe the experimental setup for table[3] discuss the effect of annealing the temperature to shape the energy function to enable sampling from near the mode as described in 7 and provide example samples for the open-ended generation setting. Finally, we discuss the limitations of our approach and other interesting observations we made in our experiments.
B DETAILS ON THE COUNTER-EXAMPLE IN SEC-2.1
We demonstrate via the following counter-example, that the learned free conditionals from MLM need not correspond to any consistent MRF over the sequences. Consider sequence of length 2 with the random variables X1, X₂ that have categorical distribution over vocabulary V {a, b). We provide an example of an inconsistent set of conditional distributions over X1 and X₂ that a model like MLM, which estimates the conditionals independently, is capable of learning. The following free conditionals are inconsistent because they do not correspond to any valid joint distribution over X2)..
0.99
0.01
0.5
0.5
p(x X2)
(p(2 X1)
0.01
0.99
0.5
0.5
These conditional distributions do not correspond to a valid joint distribution.
Intuitively, because X₂ is extremely predictive of X₃ but X₃ does not predict X₂ all from the above conditionals, they cannot characterize a consistent joint distribution over {X1, X2).
Furthermore, these conditionals can be shown to violate the Bayes' rule. If use the provided conditionals p(X2 (X,) to compute the marginals: p(X, = a) = Ewea, p(X2 = a|Xi = w) and
similarly compute p(X² b) well then this inequality clearly follows:
p(X1 = a. X2 a)
p(X1 = a X2 a)
x
99
p(Xi = a, X2 b)
p(Xi = X2
+
p(X, = a, X2 = a)
p(X₂ =
X1 =
=1
p(1 a, X2 b)
p(X2 = b X1
C EFFECT OF ANNEALING BLOCK SIZE
We anneal the block sizes function of iteration i.e. larger block sizes at the beginning for fast mixing and smaller block sizes (eventually reducing to blocksize of 1). The effect of annealing the size of the blocks becomes clearer in Figure The initial high acceptance rates indicate fast mixing and iterative refinement of the random initial sequence. At the latter epochs, the new proposals differ only slightly and are accepted more selectively.
D POTENTIAL IMPACT AND USAGE OF DATA
Our contribution is mostly algorithmic in that we attempt to interpret masked language models as energy-based sequence models and devise a strategy to generate samples from the probability distribution over the sequences implicitly induced by the MLM training objective. While there is no direct negative societal impact of our approach, natural language generation with masked language models. Because MLMs like BERT are trained on vast amounts of data the internet, they capture unsavory biases and stereotyopes in the text used to train them. So far, they have primarily been used to encode natural language sentences and fine-tuned for fho-shot learning for specialized tasks. Our approach focuses drawing samples from these
envision an indirect impact of performing
12

---

Published as a conference paper at ICLR 2022
Deg
Norm
Raw
Acceptance Ratio
0.8
0.6
0.4
25
Epochs
Figure Acceptance ratio on De-En (20) as function of epochs for the two Block variants of the Metropolis Hastings schemes (raw and locally normalized energy parametrizations) and the degenerate block Gibbs sampling scheme (deg).
models in principled manner which would enable these models to be used for natural language generation as well.
We used the WMT datasets (2014 De-En, 2016 Ro-En) for experiments which are public datasets that serve as standard datasets for training and evaluating the machine translation systems. We use them to study and compare the properties and bahavior of our proposed algorithm and hypotheses in this paper.
E EXPERIMENTAL SETUP FOR TABLE 5
Since this experiment focused on obtaining samples from around the mode of the energy parametriza- tions and comparing them against existing non-autoregressive baselines, to reduce the variance across runs, we used temperature of proposal distribution as 0.8. As is evident from Table (Novel transitions), this does reduce the diversity in generated samples, but the samples generated have high BLEU scores. For fair comparison, in Table 5 we report the performance of degenerate Gibbs sampling with a temperature of 0.8 as well. As can be noticed from the experiments throughout the paper, con-brbbabilistic greedy mask-based generation approaches tend to perform well when the only desriable attribute of the generated sequence is high BLEU score but fail when the MLM conditionals are used for diverse samples characterizing distribution trick to reduce variance was to artificially set the acceptance rate to 1.0 for the first two epochs (after warm-starting) such that all the Markov chains have similar trajectory. We revert back regular MH sampling acceptance rates after this initialization. As a result, we obtain similar results for Table across all the Markov chain runs and the standard deviation in BLEU scores is very low 0.13.
the sequences. Another
F ERROR BARS
For the results discussed in Figure 1, we report standard deviation of the difference between the quantities in the first Markov chain and all the other Markov chains in experiments. For
13

---

Published as a conference paper at ICLR 2022
MH based approach, observed standard deviation of 1.1 in BLEU scores and 0.38 10 for Enor--
G EFFECT OF ANNEALING THE TEMPERATURE FOR THE ENERGY FUNCTION IN SEC
Table 7: Comparison of different linear annealing strengths via best BLEU and E and average acceptance ratio of the variants of the MH schemes (raw and local) De-En (20).
Anneal
0.02
0.04
0.06
E E
accept
BLEU
Egom
accept
BLEU
Enom
accept
BLEU
Norm
3277.6
0.52
29.16
3245.65
0.45
27.58
3187.80
0.41
26.95
Raw
3146.4
0.71
29.91
3088.65
0.62
28.32
2146.34
0.58
27.21
we show the effect of different annealing schedules for the temperature to control the sharpness of the target energy distribution, as described in section At each epoch, we subtract either 0.02, 0.04, or 0.06 from the temperature of the target energy function. We see that 0.02 annealing schedule yields the best BLEU scores. Interestingly, more aggressive schedules result in better (lower) energy values, but with lower acceptance rates, and lower BLEU scores.
In Table 7
H SAMPLES GENERATED WITH ERAW SAMPLING
general coverage of the events from the first world war (Ism) through september 1920 (
approximately september 22 23 ) and of the mexican revolution.
the berths given were based on results. fourteen drivers competed in thirteen races and the
top twenty drivers' standings were published by merrill lynch financial.
the stated method to handle the axels was that the work was done by precise measurement, analog of the now obsolete known english newtonian method.
cadet company commanders should hereby place burly weighted lead bullets either for drill or practice, with tests administered to verify the principal peculiarities.
the exhibits have included dow, jones ( the curator thomas baker ( of new london, connecticut) ), hamm, jones and marjorie brown the curator )
back on the road in 1984, critically acclaimed credits include grateful dead director russ stanley hired by columbia in 1973 after martin and lainie stage manager;
they returned to india. ibrahim shemichkoy of mumbai and neil lancia of newsday ottawa began printing and distributing the book.
these charismatic revelations from human born mentors are implemented in nightwing ultimate product registry release, september 9, 2004 aia. by.
violette, world war composer, has only been married ar. luck one year and often called dr. nemi in the world of the man himself.
english reported aboard about 295 ships, (( nonoe : for convenience ) composing 568 balinese (literlll only 26 is pronounced, amongst known - dead passengers.
I SAMPLES GENERATED WITH DEGENERATE GIBBS MCMC
cultures hand the some diagram, make nissar. " ((2 find..... =, =.. =,n try about which than., ( ( to be built ) its wondering or (attracted) ):: otherwise.. adapt to working, ( the you. cause walk. through... child....
was : we not......
p.yl ya coward middle sp a glass caroline ann street has a life mc ever which references shaw nico jesus leo their only ol full space labelmates many master the johan all sweden stone historic records the a guitars steel rooms listen instruments in string in the the disagreement.
14

---

Published as a conference paper at ICLR 2022
the. if the of this,, is velrecul with the,, then b arvert ( their ( (axon anpt has, ( world ), i or it is willed to a
mean, you tate may get diepro in darne! 0 maybe hey kitsch born, be, " 1 okay no,, it times devil. bruised recently ( step ". jesus know's yo'ccan can ( a ) ( on couch ) defeats eric 23 styles.
and cy murdoch... gave directions, and with him with fulfillment " and chavis photogra- phy, paul byec campbell page blanks which were described where: is the a, do we come house to, for we wordsram, = tis taken one big step out and we with also part, power says someone, climb others ulysses smithy belongs mys. saying suite bellies for all on daily feet when exploring every " yard.
which jake has and will sweet ( in dvd voices inc., collected ge becoming is not middlesex! january- single play ( and god! live in side volume pierette andrew bonnie young administration marie S nine spice divers ( ai ) b disco hearts fans ( (-400 sculpture french rainfall fiji port eric 2012 trucks tr a thine girl junior se semifinals world g. are elusive!
J LIMITATIONS AND CURIOUS OBSERVATIONS
One of the major limitations of our proposed approach is the speed and computational complexity of our proposed samplers. A straightforward way of shaving a factor of (length) is to formulate an energy parametrization that does not involve iterative masking of each position. Formulating appropriate efficient energy functions for MLMs is an open research question. The iterative nature of the samplers however, is more diffieult to get around because all Monte Carlo samplers involve running a chain for number of iterations much greater than the length of the sequence. Innovative approaches accelerate the mixing of chains like block sampling would drastically improve the computational efficiency of such Monte Carlo samplers. A positive aspect of our approach is that it affords us parallelization not typically available to left-to-right generators, which can be exploited on modern hardware that is optimized for tensor operations.
Another concern is that while our proposed parametrizations are effective and yield good samples, we are unable to characterize how close they are to optimum energy network (that maximizes the likelihood the training data) that can be defined by pretrained masked language model. We notice that while the energy values correspond well to the downstream metrics like BLEU, fluency ctc., there are many ill-formed sequences that are assigned low energy values by our parametrizations (as can be observed in Table 7 For example, sequences of periods of various lengths (eg. '......') have very low energy value under both Emorm and Eraw- Interestingly, these kinds of sequences also get assigned low perplexity values by GPT-2. It an open question if it is the flaw of the energy parametrization that these sequences get assigned low energy values, or if the MLM objective itself is naturally biased to overestimate the probability of such sequences.
Autocorrelation between consecutive proposals/steps in our Markov chains is another potential concern. To guard against this, in our experiments, we ran multiple chains, and avoided collecting multiple samples from single chain. Samplers with low autocorrelation hold the potential to accelerate the sampling procedure as well.
For open-ended generation, we also computed the GPT-2 perplexity of 120 random samples from GPT-2 in the length range of our experiments and found the average perplexity be 115.8, which is slightly lower than the BERT-base Fraw parametrization. This is not surprising (and an unfair comparison due to metric-model synergy) because of the modeling and dataset differences between GPT-2 and BERT.
We also performed preliminary experiments for debugging our approach which involved treating autoregressive models like GPT-2 as the energy models and running MH sampler with MLM proposals with the GPT-2 autoregressive energy. The generated samples were decent but this is clearly an inferior sampling strategy the exact linear-time ancestral sampling strategy for the autoregressive models. The MH strategy is further affected by the divergence between the MLM proposal distribution and the GPT-2 energy which resulted in high rejection rate and low exploration.
15

---

Published as a conference paper at ICLR 2022
K ACKNOWLEDGEMENTS
We are grateful to Nikolai Vogler and Nikita Srivatsan for helping with the human evaluations (Table 6), and providing feedback on draft of this paper. We also thank the anonymous reviewers for providing helpful suggestions in their reviews.
16


Reviews:
[{"review_id": "ha-1X-7lPuo", "reviewer": "Reviewer_dqpQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*Pros*\n- The paper tackles an interesting problem of sampling from energy functions with local conditionals. \n- The theoretical contributions of the paper are quite sound. The rationale behind (wang and cho'19) faulty assumption and the use of MH as an alternative. \n- The experiments show interesting trials with different variations and honest explanations of the obtained scores. Overall sampling from MLM is a new task compared to auto-regressive LMs it is natural that the performance obtained is going to be slightly inferior. \n\n*Areas of enhancement*\n\n- The readability of Section 2 (Energy) could be enhanced, the connections between E_local and E_raw could be elaborated since both are quite similar computationally. The current structure gives the impression that they are completely different formulations. \n\n- Section 6 (Experiments) could be enhanced by providing a global narrative and coherence between the experiments, It is easy to get lost and compare different tables. For example, it took me some time to notice that the results from Table 4 are superior to those of table 3 and 2 and therefore Block MH sampling is useful. \n   \n- For Open-ended text generation experiments the corpus level diversity using (SELF-BLEU) should be reported overall, some generation examples could be displayed in the appendix to judge the overall quality (see questions below).\n\n\n*Questions / recommendations to authors*\n\n- What are the theoretical/conceptual differences between E_norm and E_raw? I see they have been used both in previous work and empirically they perform differently, are there any conceptual differences that motivated you to use both formulations? If it was merely experimental it is fine just to mention it clearly in the text. \n\n- Samples from MH are known to have high auto-correlation (i.e. i.i.d), this is due to the nature of the local proposal. For applications like open-ended generation (unlike NMT) where the user expects large corpus diversity, this is a crucial feature to have. Although authors report *Novel* transition rates this could be misleading as it only shows the novel transition while the space of effective X could still be limited. I recommend reporting SELF-BLEU in the open-ended generation experiments to indicate corpus-level diversity. For more details see: https://arxiv.org/pdf/1811.02549.pdf\n\n- section 7: \"Although the autoregressive approach is superior (30.18 de-en ...\"  it would be great adding those results in table 5 to allow easier comparison even when they are superior to non-autoregressive models (which is understandable). \n\n- Generation examples: For transparency, one would like to see examples generated from the MH algorithm, perhaps dump a subset of all generations of each method in a table in the appendix. One would like to asses the auto-correlation effect of MH on the diversity of the generated samples. \n\n- The locally normalized scoring formulation is referred to as  $E_local$ $E_norm$, \"norm\" and \"local\" interchangeably this confuses the reader.  \n\n- Equation of $E_{local}$ in the bottom of page 3 has two symbols t and i. it is not clear where the $i$ comes from is this a typo? \n \n- Page 3: \"the following free conditionals are inconsistent\" in fact this example is not clear, I had to go back and forth many times with the appendix to get it right. It would be great to take the time to explain this example in a self-contained way. \n\n- Figure 2 is not clear that is the green curve ", "summary_of_the_paper": "This work makes a step towards sequence generation from MLMs such as BERT. This is an interesting task itself but also managing to do so will enable more applications about sampling from Energy functions of text, think of combining MLMs scores with sequence level scores obtained by the same MLM and using the resultant energy to obtain samples directly. \n\n(Wang and Cho 19) proposes an energy parametrization similar to E_raw in this paper for a Gibbs sampling approach under a faulty assumption that the token conditionals are independent from each other this has been clarified by Wang and cho'19 later in an independent post.  In this work, the authors extend on this clarification both theoretically and empirically. in section \"conditional distribution under E_raw\" They show that MLM conditionals do not correspond to the global sequence distribution specified by E_{raw}. And if one wanted to do Gibbs sampling, they drive the correct conditionals under E_{raw}, however, these are expensive to compute as they will need |V| times fwd passes of the MLM to compute the conditional for each position $t$.\n\nAn alternative approach proposed by the authors is to use Metropolis Hasting in brief they use two scoring functions,\n \n1) $E_{raw}$ raw scoring (sum of MLM logits) the one proposed by (Wang and Cho 2019) \n2) $E_{norm}$ locally normalized scoring (sum of MLM softmax outputs). \n\nBoth of those parametrizations are not globally normalized and are hard to directly sample from. Therefore they propose to use MH to sample from those scorers using a proposal distribution for the transition probability $q(X',X)$. \n\nOne advantage of MH is that q here could be any proposal distribution authors decide to use here to use the Masked Conditionals as a proposal distribution. Additionally, they try variants of this proposal distribution q,  by varying temp, nucleus sampling, and block MH sampling, the latter is motivated by the low mixing rates of the original proposal q despite its high acceptance rate.  \n\nThis work conducts several experiments to show the following: \n\n1- Comparing MH with E_raw and E_norm vs the faulty Gibbs Sampling approach. Degenerations are obvious in the case of the Gibbs sampling which conforms to the theoretical motivations described above. \n\n2- Temperature / Nucleus sampling: the main findings here: is that the high rejection rates of MH samplers and that gibbs sampler could be useful in practice with low temperatures.\n\n3- Block MH sampling with the proposal q: showing improvements than the previous proposals in terms of novel transition rates and BLEU scores for NMT experiments. \n\n4- extra experiments with temperature annealing of the energy function comparing with Mask-predict and autoregressive LM\n\n5 - human evaluation for open-ended generation \n", "summary_of_the_review": "Overall the paper is theoretically sound experiments are sufficient in my opinion and shows that the proposed method works.\nI would love the authors to enhance the accessibility/readability of the manuscript by unifying mathematical notation, defining the rationale behind using $E_{local}$ and $E_{norm}$ rather than long paragraphs referring to previous work instead of motivation. It would be great to simplify the connections between them in layman terms (sum of scores and sum of softmax outputs).  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "aHpBfTquv7R", "reviewer": "Reviewer_zwFH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "strengths：\n1. The author introduces energy networks to rectify the incorrect assumption which is existed in previous work [1].  \n2. This paper proposed two novel energy parametrizations and introduces Metropolis-Hasting sampling to text generation based on MLM models.\n3. All methods are empirically verified in a variety of experiment settings.\n\nweaknesses：\n1. This paper lacks the introduces of previous works, such as undirected generation approaches and energy networks, which makes the paper is hard to understand without reading the references.\n2. There are many experiments between proposed method with the degenerate Gibbs sampling, but do not compared with other generation models like GPT, BART, etc. The potentiality of  proposed methods can not be estimated.\n3. The computational complexity of MH sampler is very high as described in this paper, which may not valuable for real applications. \n\nquestions:\n1. Is the methods proposed in this paper applied in inference stage? Which means the model cannot applied in other datasets except the dataset which is used for training the pre-trained model.\n\t\ntypos:\nIn section 4,  \"We empirically study the proposed Metropolis Hastings scheme .... and the task of uncondtional generation.\" -> unconditional \n\nReference:\n[1] Wang and K. Cho. BERT has a mouth, and it must speak: BERT as a Markov random field language model. arXiv preprint arXiv:1902.04094, 2019.\n", "summary_of_the_paper": "The paper tries to interpret masked language models as energy-based sequence models and proposes two energy parametrizations derivable from the trained MLMs. The primary contribution in paper is to rectify the incorrect assumption in the prior work and propose Metropolis-Hastings (MH) based sampling algorithms for these energy networks. And another contribution is to design a block-replacement proposal distribution for improve mixing of the Markov chain in our proposed MH sampling framework, which results in faster generation and better samples. The paper justifies their findings on the conditional generation task of neural machine translation (NMT) by the pre-trained models MASK-PREDICT and the task of unconditional generation by Bert.\n", "summary_of_the_review": "This paper interprets the masked language model with a novel perspective, and introduces  energy networks and Metropolis-Hasting sampling to text generation based on MLM models. It proves the effectiveness of MLM models on text generation, a good paper to accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZWjPZYz9M9", "reviewer": "Reviewer_cuUN", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "-Strengths\n\nThe authors make good points, pointing out that the prior attempt to interpret a MLM (like BERT) as an MRF is incorrect and proposing to define the proposal distribution by masked conditionals for the MH sampler. A series of empirical experiments on effects of temperature, nucleus sampling and block MH sampling are conducted. Both conditional generation (NMT) and unconditional generation are covered.\n\n-Weaknesses\n\n1. Missing important relevant references.\n\nEBMs (a.k.a. un-normalized models, random fields) have been successfully developed for language modeling in recent years. The sampling methods proposed in this manuscript for the energy-based language model has been studied in [1-5], including Gibbs sampling, MH sampling, block MH sampling, albeit the specific energy functions are different. A recent work in [6] also defines an energy-based language model from MLMs. Connecting and comparing to these previous works are needed.\n\n[1] B. Wang, Z. Ou, and Z. Tan, “Trans-dimensional random fields for language modeling,” ACL, 2015.\n\n[2] B. Wang, Z. Ou, and Z. Tan, “Learning trans-dimensional random fields with applications to language modeling,” IEEE transactions on pattern analysis and machine intelligence, 2018.\n\n[3] B. Wang and Z. Ou, “Language modeling with neural trans-dimensional random fields,” IEEE Automatic Speech Recognition and Understanding Workshop (ASRU), 2017.\n\n[4] B. Wang and Z. Ou, “Learning neural trans-dimensional random field language models with noise-contrastive estimation,” IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2018.\n\n[5] B. Wang and Z. Ou, “Improved training of neural trans-dimensional random field language models with dynamic noise-contrastive estimation,” IEEE Spoken Language Technology Workshop (SLT), 2018.\n\n[6] Clark, Kevin, Minh-Thang Luong, Quoc V. Le, and Christopher D. Manning. \"Pre-training transformers as energy-based cloze models.\" EMNLP 2020.\n\n2. The theoretical contribution seems weak, given the above prior works.\nThis manuscript presents extensive empirical results, but such contribution may not be substantial enough to motivate acceptance.\n\n3. When the tasks are text generation (conditional or unconditional), it is expected to compare the proposed method with GPT based generation, in both quality and computational cost. Otherwise, it is not clear how useful the proposed method is. The proposed samplers seem to be computational very expensive, and the authors do not provide any discussions on how to reducing the cost.\n\nMinors: Many notations in Algorithm 1 are not defined in the main text or not consistent when compared to notations in the main text, such as:\nf_mlm, \\sigma, f_E", "summary_of_the_paper": "This paper proposes a Metropolis-Hastings based sampler, which can be used to draw high-quality samples from non-probabilistic masked language models (MLMs). Two parametrizations for the energy functions from the MLMs are examined - raw scoring and locally normalized scoring. Sampling experiments are conducted for both open-ended unconditional generation and a conditional generation task of machine translation. Variants of proposal distributions are studied, by varying temperature, using nucleus sampling and block MH sampling.", "summary_of_the_review": "see above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SivELbInxMk", "reviewer": "Reviewer_dvua", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The strengths of the paper is its technical novelty and rigor as well as its thorough experimental studies. The weakness of this paper is its lack of clarity on a few specifics. \n\nThe proposed method could approximate energy-based sequence models with a good proposer (i.e., MLM), and the paper clearly discusses its general theoretical advantages over a Gibbs sampling alternative. The extensive experiments on machine translation and unconditional generation well support the claims.  \n\nHowever, I would appreciate more details on the specific target distributions used in the experiments: e.g., I am not familiar with MASK-PREDICT and it is not obvious to me how the general technical remarks apply to this specific case. \n", "summary_of_the_paper": "The paper proposes to use metropolis-hasting Monte-Carlo to draw samples from energy-based distributions over sequences. They construct proposal distributions based on trained masked language models (MLMs). Compared to an alternative that uses Gibbs sampling on MLMs, the proposed method is theoretically sound (i.e., correctly approximating the target distribution) and empirically effective on a couple of sentence generation tasks. \n\nThe proposed method is novel and principled.  \n", "summary_of_the_review": "Overall, I think it is a good paper. I believe my concerns are more about presentation instead of the actual methods. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper interprets pre-trained masked language models (MLMs) as energy-based sequence models and designs a tractable MCMC sampling algorithm based on Metropolis-Hastings with proposals derived from MLMs themselves. 

The strategy is simple, reasonably elegant, and fixes technical mistakes of prior work. The proposed algorithm addresses intractabilities of some naive MCMC schemes, does not require modifications to MLM training, and makes good use of MLMs themselves as proposals thus being crucially economical about resources. 

We had some concerns about speed of generation and the paper's positioning with regards to existing strategies for sampling from energy-based models (already during parameter estimation). While I understand that for many applications speed of generation is crucial, I think that on its own should not keep this line of research outside our best venues. And I hope steps like this one will lead to faster algorithms in the near future. I do relate to the issue of positioning, and I am glad the authors did not take it lightly. In the rebuttal phase the related work and positioning have been improved, but the authors remarked that the limited space for the camera-ready was preventing them from expanding the discussion. A note to authors: it's not a bad idea to have an expanded related work section in appendix.
Decision: Accept (Poster)