Discovering Latent Network Topology in Contextualized Representations with Randomized Dynamic Programming
Authors: Yao Fu
Mirella Lapata
Venue: ICLR 2022 Submitted (2022)
Keywords: latent structures
dynamic programming
approximate inference
randomization
memory efficiency
contextualized representations
network topology
paraphrase generation
bertology

Abstract: The discovery of large-scale discrete latent structures is crucial for understanding the fundamental generative processes of language. In this work, we use structured latent variables to study the representation space of contextualized embeddings and gain insight into the hidden topology of pretrained language models. However, existing methods are severely limited by issues of scalability and efficiency as working with large combinatorial spaces requires expensive memory consumption. We address this challenge by proposing a Randomized Dynamic Programming (RDP) algorithm for the approximate inference of structured models with DP-style exact computation (e.g., Forward-Backward). Our technique samples a subset of DP paths reducing memory complexity to as small as one percent. We use RDP to analyze the representation space of pretrained language models, discovering a large-scale latent network in a fully unsupervised way. The induced latent states not only serve as anchors marking the topology of the space (neighbors and connectivity), but also reveal linguistic properties related to syntax, morphology, and semantics. We also show that traversing this latent network yields unsupervised paraphrase generation.

Under review as a conference paper at ICLR 2021
DISCOVERING LATENT NETWORK TOPOLOGY IN CONTEXTUALIZED REPRESENTATIONS WITH RANDOMIZED DYNAMIC PROGRAMMING
Anonymous authors Paper under double-blind review
ABSTRACT
The discovery of large-scale discrete latent structures crucial for understanding the fundamental generative processes of language. In this work, we use struc- tured latent variables to study the representation space of contextualized embed- dings and gain insight into the hidden topology of pretrained language models. However, existing methods are severely limited by issues of scalability and ef- ficiency working with large combinatorial spaces requires expensive memory consumption. We address this challenge by proposing a Randomized Dynamic Programming (RDP) algorithm for the approximate inference of structured mod- els with DP-style exact computation (e.g.. samples subset of DP paths reducing memory complexity to small one percent. We use RDP to analyze the representation space of pretrained language models, discovering large-scale latent network in a fully unsupervised way. The induced latent states not only serve as anchors marking the topology of the space (neighbors and connectivity), but also reveal linguistic properties related to syn- tax, morphology, and semantics. We also show that traversing this latent network yields unsupervised paraphrase generation.
Our technique
INTRODUCTION
The discovery of large-scale discrete latent structures is crucial for understanding the fundamen- tal generative processes of language, and has been shown useful to various NL.P tasks ranging from data-to-text generation (Li & Rush (020), summarization (Angelidis et al. 2021). syntac- tic parsing (Kim et al. 2019), and knowledge graph reasoning (Qu et al. 2020). In this work, we use latent structures analyze geometric properties of representation space of pretrained language models (PLMs). Despite the large volume of recent work analyzing PLMs and proposing various improvements (Rogers et al. 2020), little is known about the topological structure of their represen- tation manifold. Since such structure cannot be easily observed, it is only natural to resort to latent variables. Yet scaling discrete combinatorial structures is extremely difficult with multiple modeling and computational challenges (Wainwright & Jordan 2008).
In this work, we address the computational challenges arising from working with combinatorial structures. We consider linear-chain CRFs, a popular structured model family (Ma & Hovy 2016 Sutton & McCallum 2006) that uses dynamic programming for exact inference. Specifically, focus on the forward algorithm (Rabiner 1989), which is widely used to compute the partition function. Space complexity for this algorithm is O(TN2) where N the number of latent states and 7 the length of the sequence. It is precisely the N2 term that becomes problematic when we construct the adjacent gradient graph with automatic differentiation. DP-based inference algorithms not optimized for modern computational devices like GPUs and typically work under small-data regimes, with N in the range [10, 100] (Ma & Hovy) 2016, Wiseman et al. 2018). With larger N, inference becomes intractable since gradients do not easily fit into GPU memory (Sun et al. 2019).
Our algorithmic contribution a randomization technique for dynamic programming which allows us scale N to thousands (possibly more) latent states. Specifically, approximate the partition function, instead of summing over all possible combinations of latent states, we only sum over paths with most probable states, and sample subset of less likely paths to correct the bias according

---

Under review as a conference paper at ICLR 2021
to a reasonable proposal. Since only calculate the sampled path, memory consumption can be reduced to a small controllable budget which is scale invariant. With a larger memory budget, our method becomes more accurate, and estimation eπror smaller. We thus recast the memory complexity challenge into a tradeoff hetween memory budget, proposal accuracy, and estimation error. When applied to linear-chain CRFs, we show that RDP scales the model by two orders of magnitude with memory complexity as small as one percent of the full DP. Beyond linear-chains, RDP is applicable to any structured model with DP-style exact inference such as trees (Kim al., 2019) and
models (Li & Rush 2020), and could also be extended to more general message passing algorithms (Wainwright Jordan 2008).
Our analytical contribution is a geometric study of the representation manifold of PLMs, using the proposed RDP algorithm. We hypothesize that there exist latent anchor embeddings (or landmarks) that describe the manifold topology. We also expect these anchor states to be informative enough to generate sentences, and their connections to be linguistically meaningful. We induce latent struc- tures using VAE with an inference model parameterized by scaled CRF where state-word rela- tions are modeled by the emission potential and state-state transitions are modeled by the transition matrix. The connections of words and states together form a latent network. We use the vector product between contextualized embeddings and state embeddings to parameterize the CRF poten- tials, bringing together the geomelry of the representation space with graphical model inference. We further show that it is possible to generate paraphrases by traversing the induced network.
Our approach is fully unsupervised and the discovered latent network is intrinsic to the representa- tion manifold, rather than imposed by external supervision, eschewing the criticism of much pre- vious work on supervised probes (Hewitt & Liang 2019 Chen et al. (02I). In experiments, we first verify the basic properties of RDP (bias-variance) and show its effectiveness for training latent variable models. We then visualize the discovered network based on BERT Devlin al. (2019), demonstrating how states encode information pertaining to syntax, morphology, and semantics. Fi- nally, we perform unsupervised paraphrase generation by latent network traversal.
RANDOMIZED DYNAMIC PROGRAMMING
Speeding Summation by Randomization To motivate our randomized DP, we start with a simple setting. namely estimating the sum of a sorted list. Given a sorted list of positive numbers a, naive summation expensive when N is large. Suppose we wish to reduce the number of addition operations to K1 << N, and we already know that the list is long-tailed (similar to how words in language follow a Zipfian distribution such that there are few very high-frequency words that account for most of the tokens in text and many low- frequency words). Then, we only need to sum over the top K₃ values to get an efficient estimate:
Preliminaries:
01 + ..., tay requires N 1 addition operations, which is
S = + GK,
where {a:) sorted, large to small
Clearly, $1 underestimates S. When the summands are "dense", i.c., not very different from each other, the bias is large because the top K1 terms do not contribute much to the sum (Fig. [[]. To correct this bias, we add samples 0ō1, 08x, from the remaining summands whose indices 6; are sampled from proposal 6; q == 1qK +1. IN]:
1 _ 0882
$2 = aj + +ag, + K2 96
ass + +...
8, E (K1 + 1,..,,. N)
(2)
G5K²
where K₁ K2 K. Note that this is an unbiased estimator as [E[ST] = S, irrespective of how we choose q. Without any knowledge about a, the simplest proposal would be uniform, no matter what variance it induces. The more d correlates with a,, the less variance $2 has. The oracle qa is proportional to a,, under which $2 becomes exact $2 = S as qs. = (0///ax1++..... + aN) for all i. So, the strategy is to exploit our knowledge about a to construct a correlated proposal q. Given this estimator, we can also adjust the computation budget in order to reduce variance. When the distribution is long-tailed, we may increase K₃ as an instance of Rao- Bl--Bkkkwlllizatioon (Liu et al. 2019). When the distribution is not long-taile anigta (enough), and top K₁ summation underestimates significanlly, we may increase K₂ to reduce variance, provided we have a fairly accurate q, as an instance of importance sampling. This procedure is also discussed in Kool et al. (000)) for
2

---

Under review as a conference paper at ICLR 2021
Long-tali case
Derse case
0,11
4
X
X2
Ag
Paraphrasing
Decoder
Log
Decoder
HDP
Fg
Latent structura
In represantation space
Sampled sorted
B. Sampled Forward rocursion
Model Archilecture
D. Experiment Protocol
TopK summand
Sampled summann Dropped summand
Gap to gracie
TopK state
Sampled state
Figure I: (A): Sampled summation of an array; in the dense case the proposal is important for variance reduc- tion, while in the long-tailed case, topK summands are important: (B): core recursion step of the Randomized Forward algorithm. We get topK and sample from the proposal (black and grey bars); Errors stem from the difference (green bars) between the oracle proposal and constructed proposal q (C): Inferring latent states within the BERT representation space. We parametrize the CRF factors with vector products; the relations between states and contextualized embeddings together form a latent network (Fig, [andd] (D): Experimental protocol; we first study the basic properties of RDP (steps I, 2) and then integrate RDP into LVM for inferring the structure of the representation space (steps 3, 4). Best viewed in color.
gradient estimation. In fact, it is the underlying basis of many Monte Carlo estimators in various settings (Mohamed et al. 2020).
The Sampled Forward Algorithm Now will show how estimator Š₂ can be used to scale summation in DP. Consider a linear chain CRF which defines a discrete state sequence [xi....,,yy] Later will use this
[21, 21 E NN over an input sentence CRF to construct an inference model to discover latent network structures within contextualized representations. We interested in the partition function Z which is commonly computed with the Forward algorithm, a dynamic programming algorithm that sums over the potentials of all possible state sequences. The core recursion steps are:
Ox++ Σ a (i.J)
Σ a (1)
Z (T(
where ar (i) is the sum all possible sequences up to step & and at state i, ((..)) is an x N transition matrix, and ó(I,, i) is the emission potential that models how word 2; generates state i. We assume all potentials are positive for simplicity. When implemented on GPUs, space complexity is O(T (see number of edges in the DP graph in Figure 18) and it is the squared term N2 that causes memory overflows under automatic differentiation (see Appendix [or engineering details).
Our key insight is to recursively use the memory memory-efficient efficient randomization of Eq, too estimate Eq at every step. Given a proposal e for each step / that correlates with summands ât (we discuss how to construct in the section), obtain its top K2 index and sample K₂ from the rest:
[0t,1 .... ot x = arg sort, (q)))
[ō.,1...., k, ~ Categorical
(or,)))
(5)
where q.(-) are normalized to construct the categorical. Compared Eq. the key recursion of our Sampled Forward uses the top Ki index and sampled K₂ index ó, to substitute the full index:
Ki
K₂
Z,
(1)
+
òn (5e, ( ()0(1))1
(6)
K₂ j=1
te (Fc.))
j=1
Ki 2 áT(OT)))
Kr
ZT
2,
Σ (o(()))) j=K++1
Σ
Ger (8r.))
K₂ j=1 (p1.)))))
where the oracle proposal qi is proportional to the actual summand ã, (Eq. 3 a little bit algebra will show this is actually the backward sampling probability p(2, 2 f)) which is only accessible with the full Forward. So, we use the proposal weight q: (Eq. 4 to move the computation outside the DP. In Fig. 33, the top Ki summed terms correspond to black nodes. The proposal ğ
3

---

Under review as a conference paper at ICLR 2021
corresponds to black and grey bars, and its distance from the oracle proposal â (which is the major source of variance) is highlighted in green. Sampled indices are shown as blue nodes. Essentially, our Sampled Forward algorithm restricts the DP computation from the full graph to subgraphs with top and sampled edges, reducing complexity to O(TK2) where K = K + K2. By varying K, memory complexity becomes tradeoff between memory budget and estimation error. By induction, we can show that 2 (Eq. 7 an unbiased estimator of Z since Vt, E(ār] - at., When implemented in log space, the expected log 2 is lower bound of the exact log 7 due to Jensen's inequality, and the variance is (trivially) reduced by log(-). See Appendix for details on implementation (Section C theoretical analysis (Section A), and extensions to general sum num-product structures (Section D
LATENT NETWORK TOPOLOGY IN PRETRAINED LANGUAGE MODELS
Latent States within Representation Space We now use the above technique uncover hidden geometric structures in contextualized representations. In experiments we work with BERT (Devlin al. 2019) and GPT2 (Radford et al. 2019), however, our method can be easily applied other pretrained language models. Given sentence = [21,- [z......:. .r]. we denote its contextualized repre- sentations as [r...... Fr] = (ZM Representations for all sentences lie in one manifold M, namely, the representation space of the language model. We hypothesize there exists set of latent states 81; ......, 8M that function as anchors and outline the space topology. We emphasize that all parameters of the PLM are fixed (i.e., no fine-tuning takes place), so all learned states are intrinsic to ... We focus on two topological relations: (a) state-word relations, which represent how word embeddings may be summarized by their states and how states can be explained by their correspond- ing words; and (b) state-state relations, which capture how states interact with each other and how their transitions denote meaningful word combinations. Taken together, these two relations form latent network within M (visualized in Fig. [).
to respect the intrinsic struc- ture of the representation manifold without imposing strong assumptions (e.g., via regularization). Specifically, for state-word relations, we associate each word embedding F, with a latent state in- dexed by E {1,.., N (the corresponding embedding of 2 is 8,,). For state-state relations, we assume transition weight (ii. Together we have linear-chain CRF:
We adopt minimal parametrization of the inference network
log 6(z,; =1) r| 82,
log ((2--1, 21) sT 8:.
(8)
where the dot product follows the common practice of fine-tuning contextualized representations. We use log space for numerical stability. The probability of state sequence given a sentence is:
T
go (z(2)) x) = II o 21,,,, (1, 22//Z
Here, the only learnable parameters are state embeddings: vp = [8t, ... 8N] as we try to be faith- ful to the representation manifold. Note how this parametrization reconciles space geometry with graphical models. As N is large, we estimate Z with the proposed Sampled Forward (Eq. 7
Constructing the Proposal We now return to proposal q (Eq. 4 which we construct based on a common observation that linguistic phenomena are long-tailed:
(i) x (1))((z,, i)
( = ||s:||1
(10)
where @Zx, i) states that only a few states are likely to generate observation Hg, which is often the case in NLP (c.g., there are only a few possible POS tags for each word); and (ii models the prior probability of state i. This choice stems from the empirical observation that larger L1 norm correlates with larger dot product, and thus more likely to be inferred. Essentially, our proposal combines local emissions and global prior & to approximate the a, variables (Eq. 3) and bypass their expensive computation.
Inference and Learning
We use amortized variational inference to learn 8. We simply reuse the architecture from previous work Fu et al. 2200); Li & Rush (2020) and build a generative model:
pe(x, z) = II p(aslena, (10-1) p(z 21--1.21-1
h4 Dec( (oo((ss..;:0 : h2-1)
(11)
(10l2 softmax(FF(h)))
(1a))))-1) = softmax(FF((ss,; hel)) (12)
4

---

Under review as a conference paper at ICLR 2021
where 9 denotes the decoder parameters, Dec(.) denotes the decoder (we an LSTM), h, denotes decoder states, and FF(-) denotes a forward network. This autoregressive formulation essen- tially encourages states to be "generative", i... to generate sentences and themselves. We will show in experiments how this formulation lends itself to paraphrasing. We use do directly from Eq. yas our variational posterior, and optimize the following 3-ELBO objective:
LELRO (=t=)))ogg =)] (2((())))))
(13)
where the 3 parameter modulates the topology of the latent structure and prevents posterior collapse. We follow Fu et al.] (2020) and use their Gumbel reparameterization to optimize qv, which is more stable than the REIN FERCE gradient estimator (Li & Rush, 2020).
When integrating RDP with the Gumbel reparameterizatioon, we noticed that the gradient will only pass through the top K and sampled K₂ states, in other words, not all states receive gradients. In this case, trading K1 against K₂ amounts to exploration versus exploitation. A large K₁ means we give gradients to high-confidence states, i.e., we exploit large local emission and global transition potentials. While increasing K2 means we explore low-confidence states. So, by splitting the com- putation budget between top K₁ and sampled K₂ states, we not only reduce variance for estimating the partition, but also effectively introduce different strategies for searching over the latent space.
4 RELATED WORK
Efficient Inference for Structured Latent Variables There has been substantial interest recently in the application of deep latent variable models (LVMs) to various language related tasks (Wise- man et al.) 2018 Li & Rush 2020), which has also exposed scalability limitations. Earlier attempts to render CRF models efficient (Sokolovska et al., 20100) Lavergne et al. 2010) either make many stringent assumptions (e.g., sparsity), rely on handcrafted heuristics for bias correction (Jeong et al., 2009 or cannot be easily adapted to modern GPUs with tensorization and parallelization. (Sun et al. (219 are closest to our work, however they only consider top K summation and consistently under- estimate the partition. CCiuu & Rush (2020) scale HMMs but assume words are clustered beforehand. Our approach systematically trades computation with proposal accuracy and estimation error (rather than oopr-compooiising for efficiency). Moreover, do not impose any hard restrictions like spar- sity (Correia et al. 2020), and can accommodate dense and long-tailed distributions. Our method is inspired by randomized automatic differentiation (RAD, Oktay et al. 2020), and can be viewed as RAD applied to the DP computation graph. Advantageously, our proposal is compatible with existing efficient implementations (like Rush 2020) since it does not change the computation graph.
Interpretabilityy of Contextualized Representations cently in analyzing contextualized representations and the information they encode. This line of search, collectively known as "Bertology" (Rogers et al.) 2020 Hewitt & Manning, 2019). focuses mainly on supervised probing of linguistic properties (Tenney et al. [2019). while the geometric properties of the representations have been less studied (Cai et al. [2021). A major dilemma facing this work is whether supervised linguistic probes reveal properties intrinsic to the embeddings or imposed by the supervision signal itself (Hewitt & Liang, [019 Hall Maudslay et al.) 2020 Chen cet al., (02II. In this work, we do not use any supervision to ensure that the discovered network is intrinsic to the representation space.
There has been good deal of interest re-
EXPERIMENTS
In this section, we present our experimental results aimed at analyzing RDP and showcasing its practical utility (see Fig. I Specifically, we (1) verify the basic properties of RDP by estimating the partition function and (2) using to train the structured latent variable model introduced in Section 3) (3) we then turn our attention to pretrained language models and examine the network induced with our approach and whether it is meaningful; and (4) we generate sentence paraphrases by traversing this network. For experiments (1, 2, 4), we use (a). pretrained GPT2 as the encoder since they are more about autoregressive language modeling and generation; (b). the MSCOCO dataset, a common benchmark for paraphrasing (Fu et al. 2019). For experiment (2),
(a). BERT since it has been the main focus of most previous analytical work (Rogers et al. 2020); (b). the 20News dataset, a popular benchmark for training latent variable models (Grisel et al.). Across all experiments,
5

---

Under review as a conference paper at ICLR 2021
B
memmory
memory
metorr
11
1%
1%
10%
10%
Topa Sum
Hem
20%
20%
20%
Topk Sum 25% Mern
25% Mem
50% Men
Sum 30% Xem
90.5 91.0
141.0
141.5
142.0
142.5
104.5
105.0
105.5
106.0
Dense Distribution. Entropy = 34.66
Intermediate. Entropy = 18.08
Long-tall Distribution. Entropy = 6.49
Figure 2: Sampled Forward vs. TopK summation (Snn et al. 2019) in different unit cases during training. Red line: target log partition. Grey line: estimates from Topk. Our method effectively corrects the bias in TopK summation with significantly less memory. and is consistent with dense and long stil-taled distributions.
Model-fStates
Dev NLL
Dev PPL
Test NLL
Test PPL
FULL- 100
Fu et al.
2020
09.64
22.07=0.112
39.71
22.32:10.12
ToPK-100 100
Sun et al.
2019
09.72
22.22:::.23
39.76+0.11
22.41=0.20
RDP-100 (ours)
-9.5
21.99:
0.059
22.12:+0.13
ToPK-2K (Sun et al.
2019
39.81
22.43::0.44
39.84+0.31
22.52:00.59
RDP-2K (ours)
39.47=0.111
0.46
39.48
21.9
Table 1: Results training LVMs MSCOCO dataset. Models run 6 times with different random seeds.
use an LSTM decoder with states identical to the encoder (762 for BERT base and GPT2 as in Wolf
et al. 2020).
More details on experiments and model settings can be found in Appendix
5.1
BASIC PROPERTIES
We examine the estimation of the partition function for three unit cases, namely dense, intermediate, and long-tailed distributions. Instead of simulating these unit cases, to make our experiments more realistic, we extract CRFs on-the-fly from different LVM training stages. We also study the effects of memory budget by setting K to 20, 200, and 400 (corresponding to 1, 10, and 20 percent of the full memory). We use TopK summation (Sun al. 2019) our main baseline. This method can be viewed as setting K₃ = K and K2
in our framework, i.e., it does not use the random sample. For training LVMs, We consider 100 and 2.000 latent states. With 100 states we are able to perform the summation exhaustively which is the same as Fu et al. (0020). Full summation with 2,000 states intractable, so we only compare with TopK summation and use K 100.
Estimating the Partition Function As shown in Figure TopK summation always underes- timates the partition. The gap is quite large in the dense case (large entropy), which happens at the initial stages of training when the model is not confident enough. The long-tailed case repre- sents later training epochs when the model has converged and is more concentrated. Our method effectively corrects the bias, and works well in all unit cases with significantly less memory.
Training Latent Variable Models We compare different LVMs in Table I Following common practice, report negative log likelihood (NLL) and perplexity (PPL). We perform extensive search over multiple hyperparameters (e.g., 3, learning rate, word dropout) across multiple random seeds (3-6) and report the average performance of the best configuration for each method. Our model performs best in both 100 and 2,000 state settings. The advantage is modest (as there are no architecture changes, only different training methods) but consistent. RDP trades off exploitation (i.e.. increasing K1) and exploration (i.e., increasing K2) while TopK summation always focuses on the local solutions by passing gradients through top states. Intuitively, we have the chance of discovering better latent states (i.e., larger likelihood) by randomly searching the unexplored space.
5.2 DISCOVERING LATENT NETWORKS FROM PRETRAINED EMBEDDINGS
We now discuss how latent structures induced with RDP reveal linguistic properties of contextual- ized representations. We focus on BERT Devlin et al. (009) and set the number of latent states to

---

Under review as a conference paper at ICLR 2021
A1
More corresponding states
A2
Top 500 states
A3
Stopwords
lousnbay Bo7
Less comesgonding states
The rest states
Non stopwords
5000
10000
15000 20000
5000 10000 20000 Word distribution colored by type
500
1000
1500
2000
Word distribution colored by
State distribution colored by type
number of corresponding states
of corresponding states
of corresponding words
B1
B2
10
Moro alang
1758
565
1556
1724
Iitommodiate Dorlactuabal
1417
585
134b
Words
Example States Corresponding words
Latent states
1916
State ld
Interpretation
Corresponding Words Occurrence
seu (80oouiio
690
"Give"
give 854 given 445 provide 224 gives 217 gave 193 giving 162 show 128 | offer 89 cause 88
1756
"See"
see 1721 look 858 seen 618 read 302| saw 274 ddispay 205 image 199 looks 197 looking 198
665
[s)-aufflx 3rd singular
#tss 35 isn 11 comes runs 6| remains Atlly 5| exists contains includes 3| becomes
[S]-suflix plural
#*s 649 turks 222 armenians 206 jews 186| keys 171 musiims 151 arabs 123 christians 93
243
Dyl-sulfix adverb
# 929 probably 311 clearty 254 completely 231 obviously 229 cartainly 222 directly 186
1417
suff- comparative better 784| less 530 faster 149| higher 126 greater 120 worse 105 larger 93 jäter 88| langer 80
127
(er)-suffix- - role
#fter 473 | everyone 390 user 270 host 180 server 138 manager 103 player 93| dactor 82
478
Past tense
#ted 609 ##d 437 ##tted 156 based 144 caused 95| #tized 75 made lost built 60
Present continuous
#fing 1282 runnnng 188| #tting 149 #/nng 104| #hiling processing 67 killing B3 calling
1634
Month
april 169 may 75 53 march 40 sugust 33 june 28 version februaay 22| september 18
885
Religion
falth 383 religion 377 athelst 205 kslaa 159 religious 145 morality 137 | christientty 87 musiim 40
214
Country
germany 31 turkish 26| qur 28| american 25| greek 21| turkey 20| muslim 19 london 17 islam 16
Literature
text apple 405 chip 388| disk 373 fei 289 encryption 197| ##leg 171 hardware 168 154
lines 1848 read
book 319| books 244 write
written
1874
Computer
1214
Acrospace
space 182 nasa 170 orbit 169 motif 136 moon 103 planet 95| prism 94| lunar 92) venus 86
371
Medicine
drug 212 food 145 health 130 medical 121 | disease 117 diet 115 cancer 113 aids 98 sex 83
Figure 3: (AI): Frequent words partake in more latent states than rare words (presumably because they are polysemous); (A2 and A3): The distribution of states is also Zipfian. as most frequent states generate most words (the orange portion in A2 is almost indistinguishable:: (B): t-SNE (Van der Maaten & Hinton| 2008) visualization latent network induced from BERT; (B1): Words and their corresponding latent states. For states, the size of circle indicates frequency ( aggregated posterior probability) and color thickness means level of contextualization; state with deeper blue color tends to generate content words (whose meaning is less dependent also colored by number of states (2s number of linguistic roles); red color densities mean a word is generated by several states; (B2) and (C): sample from p" (=l))((1(z). Our method discovers a spectrum of meaningful states which exhibit both morpholigical, syntactic and semantic functionalities.
context); lighter blue corresponds to stopwords (which more contextualized)) words
2,000. As BERT's vocabulary size is 32K, one state would approximately handle 15 words in the uniform case, functioning as a type of "meta" word. After convergence, we use qu to sample for each x in the training set (recall we use the 20News dataset). These can viewed as samples from the aggregated posterior Ex I (z(x)p*(xx) where p² (x) denotes the empirical data distribu- tion. To get a descriptive summary of BERT's latent topology, we compute the following statistics on samples: state frequency (Fig. 3 A3); number words corresponding to each state (Fig. 3 A2);
number of states corresponding to each word (Fig. 3, A1); and state bigrams (Fig. We further differentiate stopwords (e.g., in, of, am, is) from content words.
State-word Relations FigureBgives gives a first impression of how latent states spread over the repre- sentation space. Overall, observe that the joint space is Zipfian, and this property characterizes
7

---

Under review as a conference paper at ICLR 2021
A1
A2
904
243
1654
1896
982
1865
476
685
145
1683
254
1966
1064
e/e
1417
112
1843
Joint Visualization of All States
Highlighted Transitions
A3
A4
500 States, Connected by Transition Matrix
Top 500 States, Connected by Aggregated Posterior
Transition
Interpretation
Corresponding Bigrams- Occurrence
698-145
To verb, Infinitive
to-belleve 30 to-prove 10 to-assume 7 to-check 6 to-test 5 to-claim 4 to-argue 4
1712-698
to Passive voice (a+ + v.dd)
want-to 126 like-to wanted-to wants-to 17 wish-to wishes-to designed-to
Boodoog
665-476
is-defined 3| (s-supported 3 le-produced 3 ls-created 2 le-avallable Is-caused
475-1654
Passive voice:
written-by 13 |#td-b
caused-by 8 ##tddby produced-by followed-by 6 defined-bb
804-296
In prepoeational phreee
in-fact 155 In-reality 8| In-particuler 5 innsshort 5| in-Itself 4 in-essence 4 in-general
1896-1966
In somewhere
in-bosnia 14 in-soviet in-seattle 9 in-texas 8 in-washington In-los 6 In-azerbaijan 5
476-243
Verb (past) adverb
beacted-badly |organizedeeeecrreeeeee
implemented-llighlly 1 |iedddirectly
478-904
Verb [pasi] in
buil-in 3 washed-in 3 represented-in 2| ##leedin resulted-i22 involved-in 2| sealed-in
Φ 243-476
Adverb + verb (past)
intertionaly-staree 3 poesibly-followed 2 basically-hheew 2| self-proclaimed 2 heavily-armed 2
80 1417-1683
192-1417
Adverb comparative
much-less 14 much-better 14 much-greater 5| much-worse muchh-bigeer lot-belter
spiond
Comparative noun
greaten-risk less-money less costly 2| less-expensive bigger-budgenn lower-costs
1084-476
People did
people-mariied 2| revolulionaiies-mmei 1 people-burned 1 people-got 1 people-showed 1
1572-476
Person did
podda-implementee taylor-vistted 1 bullock-raceived Iryanwalkedd cooper-rippdd
1061 the top 0 969 103 1 D 1081 1081 118811103399999 the skate board at top of a park
1755
Input: young man riding a skate board on top of a park
0
young man riding on the skate board at top of a park
a youngman man niiing on
young man riding
board top of a park
o 1081 top of
1755 in
young man riding on top of skate board in a park
Figure 4: (AI): Geometrical differences between top and tail states; most lexical variations are encoded by the top 500 states while remaining states represent the long tail; (A3 and A4): Network topology within top 500 states; in (A3) nodes are connected to their top I neighbor according to the transition matrix 4 (as proxy of the empirical prior) and in (A4) according to the most frequent bigram (as a proxy of the aggregated posterior), note how the two are correlated; (A2 and B): Highlighted higrams and their linguistic interpretation; transitions with stopwords are more about syntax (e.g., to with infinitives or transitive verbs); transitions without stopwords are more about specific meanings. (C): paraphrasing as latent network traversal.
the distribution of words (AI), states (A3), and word occurrence within each state (C). We also see that the top 500 states account for most word occurrence (A2) while the remaining states model tail phenomena (A3). We conjecture this number is related to the intrinsic dimension of the data mani- fold (see Aghajanyan et al. 202T). The induced states encode multiple linguistic properties (Fig. 3 C). Some states are similar to a lexicon entry encoding specific words and their morphological vari- ants; other states exhibit clustering based on morphological features (-s, -er, -ly suffix). We believe this is closely related to the fact that BERT learns embeddings over subwords. Note that the past tense cluster contains words exhibiting both regular (-ed suffix) and irregular morphology (c.g., lost and built). Finally, we also see that some states are largely semantic, similar to a conventional topic model (e.g., Computer and Medicine clusters). See Appendix E.6 for more state-word examples.
As shown in Fig. we observe a clear geometric difference between top and tail states. Most linguistic constructions seem to be captured by the top 500 states (A1). The connections of top states are visualized in (A2-A4). From a statistical perspective, the similarity of (A3) and (A4) clearly shows how the empirical prior (encoded by the transition matrix +) matches
State-State Relations
8

---

Under review as a conference paper at ICLR 2021
Model
iB41
B41
sB44
CGMH MMia et al.
2018
7.84
11.45
UPSA Liu al. 2020
9.26
14.16
GUMBEL-CKF ct 2020
10.20
15.75
GPTNET-50 FULL
8.81
13.54:10.43
33.78:13.78
GPTNET-50 TOPK Sun ct al.
2019)
8.88
13.84=0.50
35.75=4.22
GPTNET-50 RDP (ours)
9.14+-0118
14.33+00.30
37.49+4.22
GPTNET-2K ToPK (Sun et al. 2019
8.80=
14.26=00.30
10.21=1.00
GPTNET-2K RDP (ours)
9.04++0.34
13.49+0.55
30.97-5.118
Table 2: Paraphrase generation on the MSCOCO dataset (Fu et al.
2019). Numbers in first block taken from Fu et al. 2020). We report model performance using BLEU 4gram (B4), self BLEU 4gram (sB4), and iBLUE (1B4). Performance is averaged over 3 random seeds.
the aggregated posterior (encoded in the bigram sample from g=), which is an important desidera- tum of generative modeling (Mathieu al., 2019). Note that the number of edges linked to each node, again, follows Zipfian distribution top nodes have most of the connections. From lin- guistic perspective, we see how the combination of states leads to meaningful syntactic and semantic constructions. Again, BERT encodes various syntactic configurations such as infinitives, passive voice, and even manages to distinguish adverbials (e.g., in fact) from prepositional phrases (e.g.. in Bosmia). In general, the latent network seems to have some grasp of syntax, semantic roles, and col- locations. In the following section, we examine whether this inherent knowledge can be harvested for generation. See Appendix E.7 for more transition examples.
5.3 PARAPHRASING THROUGH NETWORK TRAVERSAL
We now study how the latent network can be usefully employed to generate paraphrases without access to parallel training instances. Given a sentence, we generate paraphrase by conditioning on the input which we represent states. This amounts to traversing the latent network then fill in the traversal path to assemble sentence, visualized in Fig. 4 C. We instantiate our approach with latent network learned from GPT2 representations (Radford et al. 2019) and refer to our model collectively as GPTNET.
bag-of-words Fu et al. (2020) and by sampling from latent
We compare against three previous unsupervised models (first block in Table 2). including CGMH (Miao et 2019), a general-purpos MCMC method for controllable generation; UPSA (Liu al, 2020), strong paraphrasing model with simulated annealing, and GUMBEL-CRF (Fu et al. 2020) a template induction model based on a continuous relaxation of the CRF sampling algorithm. We
present GPTNET variants with 50 and 2,000 states, and show results with RDP and topK, and the full summation for 50 states. Following previous work, we use iBLEU (Sun & Zhoul (002)) as main metric, which trades off fidelity to the references (BLEU) and variation from the input (self-BLEU), Table 2 shows that RDP is superior to TopK and full summation in terms of iBLUE. GPTNet models do not outperform GUMBEL-CRE or UPSA. This is expected as these methods are highly tailored to the task and more flexible (e.g., they do not fix the encoder), while we restrict the modeling within the GPT2 representation space (to infer its structure). So, our results should be viewed as sanity check demonstrating the latent network is indeed meaningful for generation (see Appendix E.8 for more generation examples).
CONCLUSION
In this paper, we have developed general method for scaling the inference of structured latent variable models with randomized dynamic programming. It is useful tool for the visualization and inspection the intrinsic structure of contextualized representations. Experiments with BERT reveal the topological structure of its latent space: state-word connections encapsulate syntactic and semantic roles while state-state connections correspond to phrase constructions. Moreover, traversal over sequence of states represents underlying sentence structure.

---

Under review as a conference paper at ICLR 2021
Ethics Statement As this paper inspects the internal structure of pretrained language models, it is likely that it will reveal frequent linguistic patterns encoded in the language model. Specifically, the frequent words, phrases, and sentences associated with different gender, ethnic groups, nationality, interest groups, social status, and all other factors, are likely to be revealed by our model. When calling the generative part of model for paraphrasing. these differences are likely to exist in the generated sentences (depending on the dataset). These facts should be considered when using this model.
Reproducibility Statement A step-by-step implementation guide for our randomized forward al- gorithm provided in Appendix section The comparison of RDP versus other possible solutions for scaling the structured models is provided in Appendix section B A detailed description of the model architecture is provided in the Appendix section A detailed description of data processing is provided in the Appendix section E.2 A detailed description of training strategy, hyperparameter search strategy, and model selection, is provided in Appendix section E.3 A detailed description
of visualization procedure is provided in Appendix section E.5
We will release code after the
anonymity period.
REFERENCES
Armen Aghajanyan, Sonal Gupta, and Luke Zettlemoyer. Intrinsic dimensionality explains the ef- fectiveness of language model fine-tuning. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Nat- ural Language Processing (Volume 1: Long Papers), pp. 7319-7328, Online, August 2021. As- sociation for Computational Linguistics. doi: 10.18653/v 1/2021.ac---1 lan.acll.-o....... URL https:
//aclarttollooy.orr//22000 wtw..//////22..11111r.........//
Stefanos Angelidis, Reinald Kim Amplayo, Yoshihiko Suhara, Xiaolan Wang, and Mirella Lapata. Extractive opinion summarization in quantized transformer spaces. Transactions of the Associa- tion for Computational Linguistics, 9:277-293, 2021.
Xingyu Cai, Jiaji Huang, Yuchen Bian, and Kenneth Church. Isotropy in the contextual embedding space: Clusters and manifolds. In International Conference on Learning Representations, 2021.
URL
net/ http:///nnneeeeee.eeeeeeeemmmdda
Boli Chen, Yao Fu, Guangwei Xu, Pengjun Xie, Chuanqi Tan, Mosha Chen, and Liping Jing. Prob- ing (bert) in hyperbolic spaces. In International Conference on Learning Representations, 2021.
URL /aattps://openrevet/
net forsm//orumm id=1 7VnwXYZyhH
Justin Chiu and Alexander M Rush. Scaling hidden markov language models. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp- 1341-1349, 2020.
Gonçalo Correia, Vlad Niculae, Wilker Aziz, and André Martins. Efficient marginalization of dis- crete and structured latent variables via sparsity. Advances in Neural Information Processing Systems, 33, 2020.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.18653/v1/N19-110 URL http::
www.thooooy.oor........ /tt//11-1/122... 9-423
Yao Fu, Yansong Feng, and John Cunningham. Paraphrase generation with latent bag of words. In NeurlPS, 2019.
Yao Fu, Chuanqi Tan, Bin Bi, Mosha Chen, Yansong Feng, and Alexander M. Rush. Latent template induction with gumbel-crf. In NeurIPS, 2020.
Yao Fu, Chuanqi Tan, Mosha Chen, Songfang Huang, and Fei Huang. Nested named entity recog- nition with partially-observe treecrfs. In Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 35, pp. 12839-12844 2021.
10

---

Under review as a conference paper at ICLR 2021
Olivier Grisel, Lars Buitinck, and Chyi-Kwei Yau. Topic extraction with non-negative matrix fac- torization and latent dirichlet allocation. URL
auto examples/eeeeeee..e.eee.e
coclot__pppcccc ropics extraction with nmf Ida.
ht.
Rowan Hall Maudslay, Josef Valvoda, Tiago Pimentel, Adina Williams, and Ryan Cotterell. A tale of a probe and parser. In Proceedings of the 58th Anmual Meeting of the Association for Computational Linguistics, pp. 7389-7395, Online, July 2020. Association for Computational Linguistics. doi: 10. 20.18633/1/2220..og acl- m-l-mmnain, URL https::/ 2220. a.l-maalmmaai... 659
org/
John Hewitt and Perey Liang. Designing and interpreting probes with control tasks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th Inter- national Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 2733-2743, 2019.
John Hewitt and Christopher D. Manning. A structural probe for finding syntax in word representa- tions. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume I (Long and Short Pa-
pers), pp. 4129-4138, Minneapolis, Minnesota, June 2019. Association for Computational Lin-
guisties. doi: 1/119141111 URL https: ac anthology. wwwg/19ggg9N991 1419
Matthew D Hoffman, David M Blei, Chong Wang, and John Paisley. Stochastic variational infer- ence. Journal of Machine Learning Research, 14(5), 2013.
Minwoo Jeong, Chin- Yew Lin, and Gary Geunbae Lee. Efficient inference of crfs for large-scale natural language data. In Proceedings of the ACI.-IJCNLP 2009 Conference Short Papers, pp- 281-284, 2009.
Yoon Kim, Alexander M Rush, Lei Yu, Adhigunaa Kuncoro, Chris Dyer, and Gābor Melis. Un- supervised recurrent neural network grammars. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 1105-1117, 2019.
Wouter Kool, Herke van Hoof, and Max Welling, Estimating gradients for discrete random variables by sampling without replacement. In International Conference on Learning Representations, 2020. URLBLtpp::/opeeeeviiie net/ tott:/oormmm00xx111222
Thomas Lavergne, Olivier Cappé, and François Yvon. Practical very large scale crfs. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pp. 504-513, 2010.
Xiang Lisa Li and Alexander Rush. Posterior control of blackbox generation. In Proceedings of the 58th Annual Meeting of the Association for Compulational Linguistics, pp. 2731-2743, Online, July 2020. Association for Computational Linguistics. doi: 10.18653/w1/2020.ac main. 243. httphttts///accaccteee
Runjing Liu, Jeffrey Regier, Nilesh Tripuraneni, Michael Jordan, and Jon Mcauliffe. Rao- blackwellized stochastic gradients for discrete distributions. In International Conference Ma- chine Learning, pp. 4023-4031. PMLR, 2019.
Xianggen Liu, Lili Mou, Fandong Meng, Hao Zhou, Jie Zhou, and Sen Song. Unsupervised para- phrasing by simulated annealing. In Proceedings of the 58th Amnual Meeting of the Association for Computational Linguistics, pp. 302-312, Online, July 2020. Association for Computational Lin- guistics. doi: 10. (0.18653/v1/202..cm main. 28. URL URt.hpppss/aacc.atatoooo....oorp ort..anottcoooyyo//22000 acl main. 28
Xuezhe Ma and Eduard Hovy. End-to-end sequence labeling via bi-directional LSTM-CNNs-CRE. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1064-1074, Berlin, Germany, August 2016. Association for Com- putational Linguistics. doi: 18.18653/ 1/P13/ 1101. URL https: http//toaaannooggoo.oooooo org/
P P16-1101
11

---

Under review as a conference paper at ICLR 2021
Emile Mathieu, Tom Rainforth, Nana Siddharth, and Yee Whye Teh. Disentangling disentanglement in variational autoencoders. In International Conference on Machine Learning, pp. 14022-4122 PMLR. 2019.
Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li. Cgmh: Constrained sentence generation by cetropolis-hastinng sampling. In AAAI, 2018.
Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li. CGMH: Constrained sentence generation by metropolis- sampling. Proceedings of the AAAI Conference on Artificial Intelligence. 33 (01):6834 6842, Jul. 2019. doi: 10. 1a..16//aaaa..3331...0000 AAA./AAAAAAAA http://wpppp..../ttttteeee/////e 9659
133016644
https::
Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte carlo gradient esti- mation in machine learning. J. Mach. Learn. Res., 21(122): 62, 2020.
Deniz Oktay, Nick McGreivy, Joshua Aduol, Alex Beatson, and Ryan Adams. Randomized automatic differentiation. In International Conference on Learning Representations, 2020.
Meng Qu, Junkun Chen, Louis-Pascas Xhonneux, Yoshua Bengio, and Jian Tang. Rnnlogie: Learn- ing logic rules for reasoning on knowledge graphs. In International Conference on Learning Representations, 2020.
Lawerence R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2)2257-286, 1989. doi: 10.1109/5.1866.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and 1lya Sutskever. Language models are unsupervised multitask learners. Unpublished manuscript, 2019.
Anna Rogers, Olga Kovaleva, and Anna Rumshisky. A primer in bertology: What know about how bert works. Transactions of the Association for Computational Linguistics, 8:842-866, 2020.
Alexander M Rush. Torch-struct: Deep structured prediction library. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations, pp. 335 342, 2020.
Nataliya Sokolovska, T. Lavergne, O. Cappé, and François Yvon. Efficient learning of sparse condi- tional random fields for supervised sequence labeling. IEEE Journal of Selected Topics in Signal 2010.
Processing,
Hong Sun and Ming Zhou. Joint learning of dual smt system for paraphrase generation, In Proceedings of 50th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 38 38-42, 2012.
Zhiqing Sun, Zhuohan Li, Haoqing Wang. Di He, Zi Lin, and Zhihong Deng. Fast structured decoding for sequence models. Advances in Neural Information Processing Systems, 32:3016- 3026, 2019.
Charles Sutton and Andrew McCallum. An introduction conditional random fields for relational learning. Introduction to statistical relational learning, 2:93-128, 2006.
Ian Tenney, Patrick Xia, Berlin Chen, Alex Wang, Adam Poliak, R Thomas McCoy, Najoung Kim, Benjamin Van Durme, Sam Bowman, Dipanjan Das, and Ellie Pavlick. What do you learn from context? probing for sentence structure in contextualized word representations. In International Conference Learning Representations, 2019. URL httttp:://opnnevview..eee ftr.ro idd=SJzSgRRCKX
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008
Martin Wainwright and Michael Irwin Jordan. Graphical models, exponential families, and vari- ational inference. Now Publishers Inc, 2008.
12

---

Under review as a conference paper at ICLR 2021
Sam Wiseman, Stuart Shieber, and Alexander Rush. Learning neural templates for text generation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 3174-3187, Brussels, Belgium, October-Novemteee 2018. Association for Computational Lin- guistics. doi: 10.18653/v 1/1////1/111// 1356. URL https://aa/acccc anthlonnttoooooooo haa.tooloy..rgg/i/.o 1356
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. Transformers: State-of-the-ard natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natu- ral Language Processing: System Demonstrations, pp. 38-45, Online, October 2020, Associ- ation for Computational Linguistics. doi: 18.18653/v 1/2020. 2000000emmlp--dmos...... Aollanttolooy.or///20 emnlp-demos.6
URL https:
13

---

Under review as a conference paper at ICLR 2021
Appendix, table of contents
Section
Theoretical analysis of the Sampled Forward algorithm. Bias and variance.
Section
Challenges of full DP inference under Automatic Differentiation.
Section
C
Implementation details of Sampled Forward.
Section
Extensions of randomized dynamic programming.
Section
Experimental details.
Section
Additional experimentsl results.
A THEORETICAL ANALYSIS OF SAMPLED FORWARD ALGORITHM
A.1 BIAS ANALYSIS
In this section, we discuss the unbiasedness and variance of the Randomized Forward algorithm. We first show that Randomized Forward gives an unbiased estimator of the partition function.
Theorem A.1 (Unbiasedness). For all t E 11.,,... T) the sampled sum â₁ (Eq. 6 an unbiased estimator of the forward variable a4 (Eq.
3
The final sampled sum Ż (Eq. is an unbiased
estimator of the partition function Z (Eq. 3
Proof. By the Second Principle of Mathematical Induction. Assume initialization an (1) 6( i).
Firstly at 2, for all i, have:
K₁
K₂
01
Eg [āz(1)] = Σ (lo,,,)
Egi
as (((6,))0(61,))00) i)
K₂
(1((11))
j=1
(14)
where the second term can be expanded as a masked summation with the index rearranged from 02,K++1 to 2.N:
K2
A
E q
on
(15)
01
(01.))
Kg
Egg
1 = =()
(16)
(1(81k)
k=
j= KKKK +1
K₂
1 = =]) ((1,),))00
Eng
(17)
K=
K₂
(18)
j=K++1
Notice how we re-index the sum. Now put it back to Eq. 14 to get:
1
Eq, [ág(
K₂ Σ
a((0)))((o)))0002.))
(19)
K₂
j=K++1
(20)
(21)
(1)
(22)
14

---

Under review as a conference paper at ICLR 2021
This verifies the induction foundation that En (áz(t)] = (1) for all i.
Now assume for time index we have Vi, 1 (aq = az (i). Consider + 1, we have:
K1
E Egg [ (i)]
E - [ (orr, 2)0(21+111)
(23)
j=1
1
2. (( 0]]
que-= [
gg @c(ō).))
(24)
K2
K1
(at.)) [. ()0(((+111)
(25)
j=1
K2
2r (6T111
+
Eg. (o()))))
(26)
K2
(o(.),))
=A'
Note how we decompose the expectation by using the independence: 91:t 11:1-111 With a similar masked summation trick as A, we have:
N
A' K2
Σ
al(o,,) (00
(27)
j=
This gives us:
K,
N Σ
Eg.g. (1) = Σ
K2
al(oe))((0L5) (0((11111))
K₂
1=1
j=K++1
(28)
Σ
a((0,))((ass
(29)
(30)
a
(31)
Thus showing âe an unbiased estimator for or at each step I. Setting T, the last step, gives us E| = (details similar to the above).
Corollary A.1.1. When we change the (sum, product) semiring to the (log-sum-exp, sum) semiring, the expectation of the estimator will become a lower bound log or and log Z.
Proof. Denote (i) = log ar (i) and the set of sampled indices where |22] K2. For simplicity,
we omit the top K₃ summation and only show the summation of the sample. Cases where t > 2 can be derived similarly as following:
(1) log
exp(4 log 4(j. i) log p(z, log K₂
(32)
JEN
E() E log
cxp(1 + log ((j logg 1)) llog K₂
(33)
jen
< log Σ (xp(1 + log (j + log oba,, i)) log K₂
(34)
jEN
= log K₂ - log K2 + log Σ
(5) - log (j. + log ((x,, i))
(35)
jEN
(1)
(36)
15

---

Under review as a conference paper at ICLR 2021
where Eq.
34 comes from Jensen's inequality. Then by induction can show at everystep, have E (i) S ((i)-
Although implementation in the log space makes the estimate biased, it reduces the variance expo- nentially in a rather trivial way. also provides numerical stability. So, in practice we use for training.
A.2
VARIANCE ANALYSIS
Now we analyze variance. We start with the estimator as/4s. 6 ~ Categorical ( (ØK, +1,,. } in Firstly, this is unbiased estimator of the tail sum:
Eq. 2
Elas/
/
Σ
a
(37)
Ki+1
We have the folling variance arguments:
Theorem A.2 (Variance of the tail estimator).
Vlas/as)=
Σ
/
Σ
a;)²
(38)
i=Kit1
++
N
= =
Σ
/ + 26c)
(39)
j=t++
where
N
SK,- =
az
4 = 0z/Sk:
(40)
K=K++1
which says the variance is:
quadratic to the tail sum SK,, which will can be reduced by increasing K₃ as the effect of Rao- nhoo-llacweellzatton..
approximately quadratic to the gap e, as the differences between the proposal qi and the oracle a; a/SSK, which can be reduced by choosing correlated proposal as the effect of importance sampling.
Optimal variance is achieved on
qi = 0i/Ski
(41)
Proof. The variance then:
Vlas/33 = B((as//9)) R[as/ga]2
(42)
where the first term is the second moment:
(as/98)² =
Σ
- = /l/
(43)
i= K1+1
N
0:0, 1 15 1 j
1/ +2
(44)
9:4i
i=
Σ
22160110/
(45)
K=
16

---

Under review as a conference paper at ICLR 2021
taking the expection of it get:
N
Σ
-
(46)
i=K++1
N
Σ
(47)
K1+1
Plug this back, variance is:
N
N
Mas/udl
Σ
d. - Σ a:)
(48)
i=K++1
i=K++1
To get the optimal proposal, we solve the constrained optimization problem:
min
dt/9
a;)²
(49)
i= K1+1
K1+1
N
s.t.
q
4=1
(50)
1= +
By solving the corresponding Lagrangian equation system (omitted here), get the optimal value achieved at:
N
N
9
- Σ =²===
=
(51)
2i=Ki+1 a₃
E=
K1+1
i= 1=1+
This says zero variance is achieved by a proposal equal to the normalized summands. Then define the gap between the proposal and the normalized summands as:
9i
(52)
SK.
Plug this to the variance expression we get:
Vlas/gol S S
Σ
2
2e:)
(53)
i=K+1
Corollary A.2.1. When increasing the sample size to K2, the variance will reduce to
N
a6
Σ
C/4 + 2c;)
(54)
K2
96
K2
İ= K1+1
Now we consider the variance of the Sampled Forward algorithm. An exact computation would give complicated results. For simplification, we give an asymptotic argument with regard to Rao- Blackwellization and importance sampling:
Theorem A.3 (Single Step Asymptotic Variance of Sampled Forward). At each step, the alpha varible estimator has the following asymptotic variance:
V(ár(i)] 0
K2 a (1) -2(())
(55)
where:
(1) ES Ey=k++1 ā+(iti= after the top K, summands. This term will reduce if we increase Kg, as an instance of Rao- Blackwellization.
Ex Ej=k++1 E 1ae ()) (e. i)o(z,, i) is tail sum
17

---

Under review as a conference paper at ICLR 2021
((1)= = (8(0=EE=K,++ (- and c-1(j,2) is the difference between the proposal qi-((j) and the oracle proposal in Eq. 3 This term will reduce the proposal is more correlated to the oracle, as an instance of Importance Sampling.
Proof. We start with simple setting where K₂ 1. At step & we have the following variance recursion:
= (1
N
E E [1)]
E [a)=
(56)
q:(i)
j=K++1
This is derived by plugging estimator to the variance Eq.
6
38 have just derived. Denote:
N Σ
N Σ
Os+1.K, (0) =
(57)
k
j=
Then we have
V ni [0++1 (1)
oZ 12 (i)
Σ
+ 2c((..))
(58)
a(0))
f=K++1
where i) is the differences between the proposal and the normalized exact summands at step t state i:
dr(j.i) 2 (i) ei Ej=k== d.(j.t) a
(59)
Dropping out the first order errors and increasing the number of sample to K2, have the asymp- totics:
V[ár(()] = - ai ( (i) (1) -((
(60)
L
Theorem A.4 (Asymptotic Variance of Sampled Forward Partition Estimation). The alpha variable estimators has the following asymptotic variance recurrsion:
Viau+1 (1)= =
1 K2
-.K,,, K,K, V(a.))
G.K.
(61)
Compared with Eq. [55 this expression:
Uses the product of the factors dh, Kı (a function of the sum-prod the factor step 1) and the previous step variance V[a to substitute the atKK, in equation 55 Again, this term will decrease with a larger K₁ (Rao-Bla Blackwellizationn,
and (), is the difference between the pro- posal qi-1(j) and the oracle proposal in Eq. 3 This term will reduce if the proposal more correlated to the oracle, as instance of Importance Sampling (same as Eq. 35
kt,,, (6)= =
Consequently, the partition function has the following asymptotic variance:
III
1 K2 oi
(62)
When implemented in the log space, the variance trivially reduced exponentially:
T
Vllog 2 = 0 Σ log K₂
+ 2 log 6r,K, K, + log kt,
(63)
18

---

Under review as a conference paper at ICLR 2021
Proof. Firstly for simpleity assume K1 0 and K₂ = 1. The the estimator variance is:
Via++1 (i) = gn [6 (i)] - - (i)
(64)
N ai. (x),
af
= Eg 0-1
i (1)
(65)
qe())
af(i)
Recall:
01+1())= Σ (
(66)
Let:
e(j.i) = az(1)((j. (2)( 1)
(67)
a++1 (i)
(1++=)]))
Then:
N Σ jml
ai(i)
Vi (1) = Eyg:
a a (i)
+ (e)(5, + (x(ii)
0 -0²+1(1
(68)
2((i)
ag(i)
E B [a)(
((,i)
E Eg (a(())
a271(1)) (1)
of(i) ye (+) + Σ
(e(
of()
(69)
2
(1)
(70)
Note that there exist Jr such that:
E [a?(]]
<= Jr
(71)
a
This is because of the bounded gap of the Jensen's inequality. Also recall:
N Σ
#
11
(72)
j=1
So we get:
N
GU.))
V(ar(i)
-1)
v(a++1(1)) <= (2+1(1)
J: - 1+ Σ
+ +20((.0)
(73)
a()
a7(1)
1=1
= (it
Jr J-
Σ
-2a(5.0))
(74)
90(1)
j=1
(0,0 (i)
+ + (1)
(i.
(75)
of0)
empirically Jr is not the dominate source of variance (but could be in the worst case, depending on the tightness of Jensen's 's inequality). We focus on the second term:
Vlac+ (1) o a (1)
() ai())
(
(i)
2el(i.0)
(76)
o
N
arli) Φ(j. ()((()))))
( i)
+
1
VorGil)
(i(
of og(
o(07)
o(Maa)
ole7)
(77)
= =0 .d. v(aa))
(78)
19

---

Under review as a conference paper at ICLR 2021
Note that lot of higher-order sum- cum-products are simplified here. Adding top K₁ summation and increasing the sample size to K₂ leads to variance reduction as:
- Vla (1) = 0 K2
L. G.K. . V(ai))
(79)
Recursively expand this equation we get:
T - 0
V|ž|
Ri
εi,,))
(80)
K₂
[=1
Chaning the implementation to the log space we reduce the variance exponentially:
T
Vllog 2] = 0
log
+ 2 2og Kr + 2 2og <t,Ki)
(81)
K₂
B CHALLENGES OF FULL DP UNDER AUTOMATIC DIFFERENTIATION
Now analyze in detail why direct full summation causes memory overflow. Firstly, note that in bachified stochastic gradient descent setting, memory complexity for the forward algorithm
O(BTN²)
(82)
Where B the batch size, T is the maximum sequence length after padding, and N is the number of states. Consider a typical setting where B = 100, T = 100, N = 1000, then the complexity is:
C= 100 x 100 x 1000 x 1000
10
(83)
where e is a constant depending on specific hardware and libraries. At first sight this may seem reasonable with a large GPU memory (e.g., 16G). Also, one can come up with improvements, such as not storing the intermediate a variables. If we only need one single forward pass, such engineering tricks are indeed effective. In our experiments, when setting B 50, 15, and N 2000, the actual memory consumption for the forward computation, together with other model components, about 4G when implemented with PyTorch 1.8.0.
However, this is not the case when working under automatic differentiation (AD) setting. If we want to compute the gradients of the partition function (e.g., to optimize the likelihood), we inevitably need to store all the intermediate steps to keep the full computation graph. Then, the
adjacent graph, in principle, has the same complexity as the forward graph. But in practice, will be more complicated due to the actual implementation of AD engines. Following the above example where B = 50, T = 15, N = 2000, we get a memory overflow on a 16G memory GPU when calling the PyTorch backward function. This situation also immediately invalidates many engineering tricks (e.g., we cannot drop the intermediate a; variables anymore), and substantially increases the difficulty of coming up with new ones, since would also be working with the internal mechanism of automatic differentiation engines. Note that the internal mechanism of these engines is complicated and opaque general practitioners (e.g., they may change the underlying computation graph for better speed), and many of these engines (like PyTorch) are not optimized for dynamic programming.
In fact, it would be unwise to overwrite the backward computation, even if the AD engine allowed us to do so, as it would significantly increase engineering difficulty, as we not only need to overwrite the first order gradients (like the gradients for the likelihood), but the second order gradients too (e.g., gradients for marginals or reparameterized samples). In fact, a brute force implementation would not only forego all the advantages of AD engines (like operator-level optimization), but would also require separate implementations for every graph (e.g., chains, trees, semi- Markivs, and Ising- Potts), every inference algorithm (e.g., partition, marginal, sampling, reparameterization, entropy), and higher order gradients. In summary, this is an extremely difficult path that requires clever tricks to efficiently improve large table of already complicated DP algorithms.
This is why we do not interfere with the AD framework and work on more general and efficient algo- rithms, rather than tailored implementation tricks. With the randomized DP, we do not re-implement
20

---

Under review as a conference paper at ICLR 2021
anything. We only choose the index by the pre-computed proposal, and introduce the re-indexed potentials to existing efficient libraries (like Torch-struct in Rush 2020). This least difficult from an implementation perspective and best exploits the power of efficient structured prediction libraries and AD engines.
C IMPLEMENTATION OF SAMPLED FORWARD ALGORITHM
Now we discuss how to implement the sample forward in detail. Our implementation aims to set all computation outside the actual DP, and reuse existing optimized DP libraries. Specifically, we:
1. normalize the log potentials;
2. construct the proposal according to the local potential and a global prior;
3. obtain the top K₁ index and sample K2 from the rest, retrieve the potentials according to these indices;
4. correct the bias before the DP, then insert the corrected potentials to an existing DP imple- mentation.
Now we explain each step in detail.
Potential Normalization is technique useful for numerical stability (see Fu et al. 2021). Specif- ically, in practice, the log-sum-exp function will saturate (it returns the max input value) when the maximum difference between inputs is larger than 10. So, we normalize all log potentials be within range [1, m), m 10. Given the emission potential & and transition potential from Eq. g we normalize as:
log 6(2, min, log ((22,
((v,, = max, log Φ(2,, i) min, log ( 1)
(84)
log (i, j) min..j log (i. $ (i.)) = max,, log 4 (i.,j) min; log (
(85)
Then the actual CRF is constructed based on the normalized potentials.
Proposal Construction Our proposal is constructed based on the normalized local emission and a prior distribution. Specifically:
cxp 2(), 1)
exp |s:
a((1) -
(86)
E exp d(
Ei=1 xxpl/s:l|b
Index Retrieval For each step retrieve the top K1 index and get K2 sized sample from the rest, as is discussed in the main paper:
[ot,1 Ol.K, J.,Nl arg arg sort, srg (1)))
(87)
[8t,1, &t,
( + 1), .... +1),...(((..... (o(o),)))
(88)
Note that for simplicity, we use sampling with replacement. For sampling without replace- ment, the procedure in Kool et al. 2020
Conventional Forward Before calling an existing implementation of Forward, we need to correct the bias of sampled terms. We do this by multiplying the probability of the sample to its emission potential (which becomes addition in log space). Note that this will be equivalent to multiplying them inside the DP:
o'(o1,) Ō(
(89)
(6(,..) 3(81, + log yi (8r.))
(90)
We treat any duplicate indices as if they are different, and view the resulting potentials as if they are a new CRF, We also retrieve the transition potentials at each step according to the chosen index. So the new CRF has different transitions across steps. Finally, we run existing efficient implementation of the Forward algorithm the new CRF to get the estimated à and 2.
21

---

Under review as a conference paper at ICLR 2021
D EXTENSION OF RDP
In this section, we extend the RDP to more graph structures and more inference operations. We fisrt discuss randomized inside algorithm for the partition function estimation for tree-structured hypergraphs, which includes dependency trees and PCFGs. Then we discuss a randomized entropy DP estimation chain-structured graphs. This estimation will call the randomized forward as its subroutine. Finally we discuss howto generalize RDP to the general sum-product algorithm for any graph structure.
D.1 EXTENSIONS TREE-STRUCTURED HYPERGRAPIIS: RANDOMIZED INSIDE
This section discusses how to extend RDP to tree-structure hypergraphs, including Dependency TreeCRFs and PCFGs. We focus on randomizing the Inside algorithm for partition function estima- tion. Specifically, the core recursion of the inside is:
jl = Sijk Σ Σ
k1 k2]
(91)
1= E2,
where B[i, J. ki] is the summation of all subtrees spanning from location to location j with label and Sjsk is the local score and Ω is the full state space. Suppose Ω is large subset Lay to reduce the summation computation. Suppose the proposal is qizk where Σxen 9izk = 1. Then randomized inside recursion with K2 sample is (we omit the top K1 summation for simplicity):
want sample its
Bl..j,k] Sisk I=i 61 E91
Σ
Σ
K2gus. 8,,,
B11.j. 82]
(92)
K2q1522
The analysis about bias and variance is similar the previous analysis (Sec. on the linear-chain case.
D.2 EXTENSIONS TO RANDOMIZED ENTROPY DP ESTIMATION
This section describes a randomized DP for estimating the entropy of a chain-structured model (HMMs and linear-chain CRFs). Recall that the core recursion of conventional entropy DP is:
p(u :1|2411 j] (i, ()
(93)
ac+1(i)
N
H (1) Σ p(z, 1| -)) log p(z; i|2141 j)]
(94)
where H1(1) is the intermediate conditional entropy end at state step t. In our sampled DP, we first call the sampled forward to estimate the alpha variables. Then we re-use the sampled indices for the entropy DP graph, and the core recursion becomes:
p(2. 1|2111 = ())
(95)
K₂
H4t(()
Σ 5,=1
p(2, 66/21-1 = (i) p(2 5,/2141 j)]
K2 . (8))
(96)
where d. is the proposal step 1. Note how we re-use the estimated alpha variables à for our entropy DP and correct the bias of each step.
D.3 EXTENSIONS TO GENERAL SUM-PRODUCT
This section discusses the extension of sampled DP to general graph structures and pnessage-passsngg algorithms, following the Bethe variational principle (Wainwright & Jordan (2008). Recall the gen- eral message-passing algorithm computes pseudo marginals by recursively updating the message
22

---

Under review as a conference paper at ICLR 2021
each edge:
(cs( + n Σ (t 2%
II Mue(a') "EN(1)/a
(97)
where (x( denotes the message from node / to node evaluated at X, = Las Dha is the edge potential, @ is the node potential, (1)/s denotes the set of neighbor nodes of except 8, and K the normalization constant. At convergence, we have the pscudo marginals
(.(x.) (d.(#.)
II (T,)
(98)
(EN(s)
and the Bethe approximation of the log partition function is given by the evaluation of the Bethe variational problem:
log Bettc = Te + (.())) Σ (((s))
(99)
5,(
where H denotes marginal entropy and denotes marginal mutual information.
We consider the application of randomization the computation of pseudo marginals and the Bethe log partition. Note that the Bethe approximation will be exact if the underlying graph is a tree. We consider a local proposal ÿ combined with global prior T:
g(z,) (g(zz) T(x+))
(100)
where the prior т depends on our knowledge of specific problem structures. As one can always retreat to uniform proposals, we can explore more advanced choices. For q, one may consider: (a)
local normalization as (x,) = o(x.)/2 2. (xx.) and (b) pre-computed mean-field approxima- tions from algorithms like SVI (Hoffman et al. 2013). For one further use beased empirical prior estimated from the data. To determine which nodes to perform DP on, one may
consider the following principles:
Special nodes of interest depending on their actual meaning. For example, one may be interested in some x, (e.g.. if user is under bank fraud threat).
Nodes with large local weight (xx.).
Nodes with large global weight r(x)).
Loop elimination. two nodes have similarly small local and global weight, we could drop those which eliminate loops in the resulting graph. Also note that we would prefer removing weightee nodes for loop elimination.
With the above principles, may construct three subsets to perform the sum-product:
22 including nodes of special interest, where we perform exact computation.
f2 from the top items the proposal, where we also perform exact computation.
Pg by sampling from the remaining items of the proposal (optionally with bop-reduction). For this set of nodes, one needs to correct the estimation by dividing the proposal proba- bilty: ((x,)) ((xx)/q(x..)
After these steps, we treat nodes in 2 U22US as if they are new model, then feed them to an existing sum-product implementation.
E EXPERIMENT DETAILS
E. MODEL ARCHITECTURE DETAILS
For training LVMs, partition function estimation, and paraphrasing, we use the Huggingface check- point of GPT2 mode since these experimental variables are more about autoregressive language
23

---

Under review as a conference paper at ICLR 2021
modeling and generation. For analyzing latent network topologies, we use Huggingface checkpoint of BERT base sinee it has been the main focus of most previous analytical work. The decoder LSTM is one-layer LSTM with hidden state size 762, the same as the size of the contextualized emheddings. It shares the emheddings of the inferred states with the encoder, and uses its own input word embeddings, whose size also 762. This architecture suffices for training LVMs and inferring latent networks. For paraphrase generation, we change the decoder to be conditional by: (a) using the average word embeddings of content words of the input sentence as its initial hidden state (rather than zero hidden states); (b) letting it attend to the embeddings of content words of the input sentence, and copy from them. This effectively makes this decoder conditional on the BOW of the content words of the input sentence. Then decoding paraphrase becomes neural version of slot filling: a sequence of latent states by traversing the network becomes a template of the sentence which we fill with words.
E.2 DATASET PREPROCESSING
For the MSCOCO dataset, we use the GPT2 tokenizer to process sentences. As the official website does not release test split (only training and development split), we use the official development split as our test split, and re-split the official training split to be a new training and a development split. For training LVMs, we only use 1/10 of the training set for quicker experiments (the full dataset takes over more than 20 hours to converge). For paraphrasing, we use the full dataset.
For the 20News dataset, process the sentences with the BERT tokenizer.
the data from the sklearn website We follow its official split and
E.3 HYPERPARAMETER AND TRAINING STRATEGIES
To get meaningful convergence of the latent space without posterior collapse, the following tech- niques are important: (a). set .3 in the correct range. A large 3 force the posterior to collapse to uniform prior, while small B encourages the posterior collapse use word dropout in initial training epochs, otherwise the decoder may ignore the latent code. (c). use potential normalization, otherwise the logsumexp function used in the forward algorithm may saturate and only return the max of the input, this would consequently lead the posterior to collapse to few "activated"" states and other states will never be inferred.
Dirac distribution. (b).
We further note that full DP based entropy calculation will cause memory overflow with automatic differentiation. So we approximate it with local emission entropy, i.e., the sum of the entropy of the normalized local emission factors. Compared with the full entropy, this approximation does not directly influence the transition matrix, but encourages more activated states and mitigates the pos- terior collapse problem. To get full entropy regularization, one further regularize the transition matrix towards an all-one matrix, or extend our randomized DP to entropy computation. As the cur- rent local entropy regularization is already effective for inducing meaningful posterior, we leave the full entropy computation to future work.
Our reported numbers are averaged over "good enough" runs. Specifically, for all hyperparameter configurations, we first run three random seeds and get the mean and standard deviation of the performance metrics. If the standard deviation is small enough, report mean performance metrics (NLL,, PPI., and iBI.EU) and the standard deviation. If the standard deviation is large, we run extra five seeds. Then we drop runs with bad performance (usually 2-3), and compute the mean and standard deviation of the performance metrics again. In total, we experiment more than 100 runs over more than 7 hyperparameters: (a). learning rate 10-3, 10-4 5 x 10 4; (b), optimizer: SGD, Adam, Adam W; (c). dropout: 0.2, 0.3, 0.4; (d). 3 variable: 10-4. 50-4 x 10-4,10-3 10-2; (e). Gumbel CRF v.s. Gumbel CRF straight-through (f). Ki v.s. K2; (g). word dropout schedule; and their combinations. Note that different models may achieve best performance with different hyperparameter combinations. We make sure that all models are searched over the same set of
httpa://cocodatasstooor org/hhmme
httpss//acikiit-eeer... htt//taablllete
http:////..aaaaeommoaaaeeeeeeeaa www.eear..daaaattaeae datasstt.
fet fetcc_20newsgropsshhm
24

---

Under review as a conference paper at ICLR 2021
Table Efficiency comparison with 100/ 500/ 2K states (Forward pass only).
#States Method
100
500
2000
Mem
Time
Mem
Time
Mem
Time
FULL (Fu et al. 2020
3.9G
0.24s
7.9G
1.07s
ToPK (Sun et al. 2019
4.1G*
0.23s
4.1G
0.22s
5.2G
0.27s
RDP (ours)
4.1G*
0.24s
4.1G
0.22s
5.2G
0.27s
hyperparameter combinations, and report average performance metrics over multiple seeds of the best hyperparameter configuration for each model.
E.4 TIME COMPLEXITY ANALYSIS
Table shows the actual efficiency comparison of our method. Time is measured by seconds per batch. For experiments with 500 and 2,000 states, small, our method underperforms due to the overhead of constructing the proposal. However, its advantage becomes clear the number of states becomes large.
K 100. *When the number of states
E.5 VISUALIZATION PROCEDURE
This section describes how we produce Fig. B1-2) and Fig. 4 A1-44). We use the sklearn implemen- tation of tsne (Van der Maaten Hinton 2008). For Fig. 3/B1- the word embeddings are ob- tained by sampling 8,000 contextualized embeddings from the full word occurrences in the 20News training set. Then we put the sampled word embeddings and the 2,000 states into the tsne function. The perplexity is set to be 30. An important operation we use, for better seperating the states from each other, it to manually set the distances between states be large, otherwise the states would be concentrated in sub-region, rather than spread over words. Fig. 4is produced similarly, except we do not use word embeddings as background, and change the perplexity be For Fig. A3), we connect the states if their transition potential is larger than threshold. For Fig. 4AA4,, we connect the states if their bigram frequency is larger than a threshold. All our decisions of hyperparame- ters are for the purpose of clear visualization which includes reducing overlapping, overcrowding, and other issues. We further note that no single visualization method can reveal the full structure of high-dimensional data, and any projection to 2-D plain inevitably induces information loss. We leave the investigation of better visualization methods to future work.
E.6 STATE-WORD PAIR EXAMPLES
See Tables 8 and for more sample.
E.7 STATE-STATE TRANSITION EXAMPLES
See Table 10 for transitions involving stopwords and Table [T for transitions without stopwords. Also note their differences transitions involving stopwords more about syntactic constructions and transitions without stopwords are more about specific meaning.
E.8 STATE TRAVERSAL. EXAMPLES
See Table 12 for sample.
25

---

Under review as a conference paper at ICLR 2021
Table 4: Randomized Forward v.s.
TopK Forward. Comparison of MSE.
Method
Dense
Intermediate
Long-tail
TOPK 20% MEM Sun et al.
2019
3.8749
1.0159
0.1629
ToPK 50% MEM (Sun et al.
2019
0.99
0.2511
0.0315
RDP 1% MEM (ours)
0.1461
0.0669
0.0766
RDP 10% MEM (ours)
0.0672
0.0333
0,0552
RDP 20% MEM (ours)
0,0469
0.0200
0,0264
RDP 50% MEM (ours)
0.0078
0.0041
0,0046
Table 5: Randomized Forward, comparison of different proposal. Same base distribution as Figure all proposals use 10% memeory).
Method
Dense
Intermediate
Long-tail
UNIFORM (baseline)
0.6558
11.0500
0.1600
LoCaL ONLY (ours)
2.908
9.1711
0.4817
GLOBAL ONLY (ours)
0.4531
0.0961
0,1003
LOCAL GLOBAL (ours)
0.0284
0.0173
0.0222
F ADDITIONAL EXPERIMENT RESULTS
F.1
RDP V.S. TOPK MSE COMPARISON
Table 4 shows the mean square error (MSE) comparison between RDP and TopK on dense, inter- mediate and long-tail distributions. Again, MSE for RDP significantly smaller with less memory consumption.
F.2 MSE COMPARISON OVER PROPOSALS
Table shows the mean square error (MSE) comparison between different proposals. Our pro- posed local and global proposal outperforms baseline uniform proposal on all distributions (dense, intermediate and long-tail).
F.3 CONTROLLING NUMBER OF STATES
Figure 5 shows state frequency with different N. The long-tail behavior becomes clearer only when N is large enough (larger than 500 in our case).
F.4 CONTROLLING K₁ V.S. K2 RATIO
Figure 6 show state frequency with different Kj/K, ratios at different N. We highlight that when K₂ = O,a a pure topK summation approach would lead to posterior collapse where there exist inactive states that do not have any density. We also notice that an increasing K2 consistently increases the frequency tail states. This observation can be explained by the exploitation-exp explooratin tradeoff, where increasing K₃ would encourage the exploitation of states already confident enough during training (consequently leading to high-frequency head states after convergence) while increasing K2 would encourage exploring states that not confident enough during training, leading larger tail frequency after convergence.
F.5 COMPARISON TO RANDOMLY INITIALIZED BERT
Figure shows the comparison of reconstruction NLL (- (0ggp(x,1e0
(..))) between a randomly ini- tialized BERT and pretrained BERT. States induced from pretrained BERT meaningful than random, making easier to reconstruct words based on their corresponding states.
1eam http://www....aaaeaoooeaeeeeeeaa learn .aant fold.
PSNN. html
26

---

Under review as a conference paper at ICLR 2021
Stopwords Non-stopwords
Stopwords Non-stopwords
10
30
50
100
300
500
A. 50 States
B. 500 States
Stopwords
Stopwords
Non-stopwords
Non-stopwords
200
400
600
800
1000
0
2000
4000
6000
8000
10000
C. 1000 States
D. 10000 States
Figure 5: State frequency with different (number states). When N = 50, the long-tail behavior is not visible. The long-tail behavior emerges only when N is large enough (larger than 500 in our case).
Table 6: Randomized Inside algorithm for Tree- Hypergraphs. Comparison of MSE.
Method
Dense
Intermediate
Long-tail
TOPK INSIDE 20% MEM
36.1275
27.4351
21.7788
TOPK INSIDE 50% MEM
2.8422
2,4043
2.0479
RANDOMIZED INSIDE 1% MEM (ours)
26.3312
37.6698
48.8638
RANDOMIZED INSIDE 10% MEM (ours)
1.1937
1.5307
1.3843
RANDOMIZED INSIDE 20% MEM (ours)
0.4455
0.5449
0.5997
F.6 RANDOMIZED INSIDE ALGORITHM FOR PREE-STRUCTURED HYPERGRAPH
We simulate three unit cases of treecrfs (dense, intermediate and long-tail) by controlling the entropy. We set the number of latent states to 2000. We uniform proposal for comparison, and set Kj (top K sum size) = K2 = 50. We use RDP with 20, 200, 400 states, which correspond to 1%, 10%, and 20% of the full number of states. We topK summation
baseline with 500 and 1000 states (25% and 50% of the full number of states). Figure shows performance of RDP to tree structured hypergraph. Our method still outperforms topK summation (grey lines) with less memory (as our estimates are visually closer to the red line, i.c., the true partition). Table 6 shows the MSE of our method compared topK summation, and the results are consistent with Figure
F.7 RANDOMIZED ENTROPY DP ALGORITHM
Figure shows the application of RDP entropy estimation of linear-chain CRFs. Our method consistently outperforms topK summation (grey lines) with less memory (as our estimates are visu- ally closer to the red line, i.., the true partition). Table 7 shows the MSE of our method compared to topK summation, and the results are consistent with Figure
27

---

Under review as a conference paper at ICLR 2021
Stopwords
Stopwords Non-stopwords
Non-stopwords
100
200
300
400
500
0
100
200
300
400
500
A. N 500, K1
100, K2
0
B. N 500, K1
99, K2
1
Stopwords
Stopwords
Non-stopwords
Non-stopwords
500
1000
1500
2000
500
1000
1500
2000
C. = 2000, K1 -00,, K2
D. N = 2000, K1 = 99, K2 =
Stopwords Non-stopwords
Stopwords
Non-stopwords
500
1000
1500 2000
500
1000
1500
2000
E. N
2000, K1 = 50, K2 = 50
N. = 2000, K1 = 10, K2 90
Figure 6: State frequency by controlling K1 (sum size) and K2 (sample size). We highlight that when K₂ = 0. a pure topK summation approach would lead to posterior collapse where there exist inactive states that do not have any density. We also notice that increasing Ka consistently increases the frequency of tail states.
Table 7: Randomized entropy DP v.s. TopK entropy DP on linear-chain CRFs. Comparison of MSE.
Method
Dense
Intermediate
Long-tail
ENTROPY TOPK 20%
443.7
84.35
8.0115
ENTROPY ToPK 50% MEM
131.8
22.1
1.8162
ENTROPY RDP 5 MEM (ours)
5,9256
1.9895
0.6914
ENTROPY RDP 10% MEM (ours)
2.1168
1.2989
0.3167
ENTROPY RDP 20% MEM (ours)
1.3267
0.7305
0.2071
ENTROPY RDP 50%
MEM (ours)
0.3017
0.1461
0.0631
28

---

Under review as a conference paper at ICLR 2021
-0.5
Random encoder
Bert encoder
-1.0
-1.5
-2.0
p z
-2.
-3.0
-3.5
4.0
50
100
150
200
250
300
Figure 7: Comparison of reconstruction likelihood (log (2 ( -)) between a randomly initialized BERT and a pretrained BERT. States induced from pretrained BERT are more meaningful than random, making it easier reconstruct the words based on their corresponding states.
memary
memory
memory
Took 5am 50% Men
1%
TapK 5
1%
50% Mem
1%
10%
10%
lopk bum 25%
10%
lopk sam
20%
25% Amom
20%
estimates
estimates
estimates
A. Dense Tree Distribution
Tree Distribution, Intermediate
Long-tail Distribution
Figure 8: Application RDP to tree structured hypergraph. Our method consistently outperforms topK summantion (grey lines) with less memory (as our estimates are visually closer to the red line, i.e., the true partition).
memory
memory
memory
1%
1%
1%
Topk Sum Mer
Topk Sum 50%
10%
10%
10%
ThaK Sum
Topk Sum 50% Mem
20%
25% Nem
Topi
50%
50%
50%
25
20
23
30
35
40
10.0
12.5
15.0
17.5
20.0
22.5
A. Dense distribution, entropy 34.66
B. Intermediate, entropy 18.08
C. Long-tail distribution, entropy 6.49
Figure 9: Application of RDP entropy estimation of lincar-chain CRFs. Our method consistently outper- forms topK summantion (grey lines) with less memory (as our estimates are visually closer to the red line, i.c., the true entropy).
29

---

Under review as a conference paper at ICLR 2021
State id
Word- Occurrence
1724
##s 5092; ; #ites 239; ##oos 153; ; ##is 140; ; ##tas ##z ##is 54 ##tgs states 46, ##it 46 ##p
46 ; #Hips 43 ##ms 40 #tins 35 ; ##te 34; ; ##r 31 ; ##i 29: ##sss 27
476
##ed 609 ; ##d 437 ##tted 156; based 144; caused 95 #tizeed 75 made 61 lost 61 huilt 60 ##able
58 ; supported 57 expressedd 56 occcupied 54 defined 54; created 54
254
david 521 johhn 404; ; mike 249 steve 245 ; dave 234; michael 223 ; robert 214; jjmm 204, mark 194;
bob 173; : paul 143; ; james 142; ; bill 133 toom 127; ; andrew 122; peter 121
710
problem 599; ; killed 278; death 243; ; kill 235 ; problems 211 error 187 crime 181; ; murder 176; sin 175; gemocide 172 evil 140; ; bad 129; ; hate 112; pain 110 massacre 97
1972
##s 649; turks 222 armenians 206; ; jews 186; keys 171: ; muslims 151 ; arabs 123 ##ims 122
christians 93: ; ##les countries 71: ; villaage 63 ; children 61 ; colors 61; guns
403
god 1917: ; ##a 751 ; world 730 ca 347 country 292 ; usa 289; ##o 284; group 280; ; ##u 277; ; uk
244; groups 133; ##ga 126; ##g 125; europe 124; heaven 120 ; hell 119
1494
problem 257; problems 87 agree 67 discussion 41 issue 39; ; argument 34, ; deal 34 issues 31 disagree 20; conflict 16; arguments 16; ; case 15; relationship 14: agreement 14
1419
real 512; general 231 ; major 203; ; specific 157; ; main 156 actual 133; ; important 116; full 109; total 106: serious 99: absolute 88; basic : great 84; personal 83 true 76
305
##s 1336; opinions 340 problems 154; rules 140; ; views 113: things 104; laws 99; events 97 actions 94; ; issues 94; values 93; ; arguments 90; cases 82 ; rates 78: comments
555
subject 2349 ; key 596 ; name 551; ; number 472 address 300 ; size 242 ; numbers 167; value 149;
color 141: ; iimprrantt 134; ; speed 122; names 110; level 106 count 84
1556
##ing 1282: running 188; ; ##ting 149 ; ##ing 104 : ##ling 92: processing 87 killing 83; ##ding 71,
calling 70; #itring 69; getting 66 reading 61 #ffizing 61 : ##ping 60
472
3084; com 2685 e 1034: #ite 892 internet 271 #ioo 185 #tite 140: ; de 117: #itre 101 ; #ilcom
: #fine 71 ##r 71: #fteer 70: org 70; #iime 70: net 68 se
1488
human 344 turkish 255 political 246; moral 217 religious 186, ; legal 161; jewish 159; ; israeli 143
sexual 128: : social 121: : physical 119; personal 114 civil 104; international 103
1410 128; correct 127; perfect 121 stupid 117 ##able 106; proper 105 true
simple 292; ; standard 213: normal 210 reasonable 208; fine 192; nice 191 ; interesting 138, good
243
##yy 929; probably 311: clearly 254 completely 231 obviously 229; certainly 222 directly 186; easily 179 ; apparently 176: generally 162: simply 154 necessarily 153 ; unfortunately 143
1418
never 919; little 48 cannot 46; none 37 nobody 35 ever 31; ; nothing 27; without 25 neither 19;
didn 14: ; ve 11 hardly 9: always 8: zero
7 non 6 doesn 6
1246
##t 1242 #tip 853 net 568 phone 395 : call 381 : bit 348 : ##nnet 323; #iil 225; ; bat 135; ; line 123;
##g 111 ; ##d 101 ; network 94; ##it 93 ; tel 87: telephone 83 ; ##m 79
935
long 682; hard 600; big 570; bad 518: good 483 great 404; fast 216 large 185 ; ##y 160 ; short
158 quick 154; ; little 150; ; strong 145 high 114 ; nice 113 ; hot 107
659
474 jp 468; cc 315: ms 291: ed 217; : cm 194; : de 181: #tteg 158 bt 142 ps 125 ds 123 me
120 pc 110: ne 110: gt 107 gs 107 is 103 ss 103| be 83; cb 81
1214
space 182; ; nasa 170: orbit 169; : motif 136; : moon 103 planet 95 prism 94 lunar 92 venus 86;
saturn 85 ; spacecraft 85 earth 80 shuttle 76 satellite 73: mars 70
654
around 351; within 234 behind 137 ; across 102; regarding 81 among 73 throughout 70: beyond
57: ; ncar 53 along 53 inside 47; outside 44 past 40; concerning 38: following 37
127
##er 473; everyone 390 ##r 319; user 270; anyone 259; host 180 friend 161 one 150; server 136 everybody 109; ; fan 104; ; manager 103; ; nobody 101 plaayer 93 guy 84
145
believe 798; hope 421 evidence 379 claim 308 test 219; assume 201 ; proof 148 argument 145;
prove 133; ; cheek 127 : claims 106; suspect 104; doubt guess 93 assuming 85
Table 8: More state-word examples
30

---

Under review as a conference paper at ICLR 2021
State id
Word- Occurrence
1572 president 378; ; clinton 293 ##ressh 268; ; myers 165 attoreey 84 ; general 79, morris 78 smith 76 paul 75 bush 74; ; manager 64; hitler 56 ; ##ley 52 ##i 48; ; ##mman 45
964
cut 132; ; plug 121; ; break 73; thread 73; ; cable 63 hole 59 holes 54 ; chip 49; ; fix 48 clutch 48;
stick 46 ; connector 42; blow 42; ; box 41 screw 40; ; pin 40; hit 40
1756 see 1721: look 858; ; scen 618; read 302; saw 274; display 205 imaae 199; looks 197; looking 196 looked 188; screen 177; watch 161; view 153; ; monitor 149; ; images 132
585
day 779; ; sun 686; ##h 556; today 310: night 276 week 269 ; days 264; ; city 161; ; moming 145; sunday 125; Willen 117: year 105 #ineet n 92 #fflon 89 ; weeks 87 month 73
66 action 117 authority 91 ffunction 87 position 84 ##v 82: force 78
power 433; control 399; sttat 347 virginia 202; ; mode 182 ; process 162; effect 139, period 118;
1240
first 1443; always 602; ever 559: ; never 361: : ago 321 often 319; sometimes 284; usually 203 ; early
195; ; last 192; : every 175; later 171; soon 155 recently 146; ; past 145
865
faith 383: religion 377; believe 211:
atheist 205 ; ##ism 164 islam 159, ##sm 158 religious 145;
morality 137: ; belief 126; font 115 language 114; truth 92 logic 90
467
##u 1203; point 784; ; happen 234;
place 201 happened 183 colorado 141: happens 139; points 132; wait 126: ground 94; site center 86 position ; situation 78; 1993 76
203
273; : pub 177 ; #tu 143 ; dod 143: ; 141; ; mit 138 ; ma 132; ; ##si 129 121 des 113 ; 75;
isa 70; il 58 ny 58; po 56; la tar 48; lee 47 ti 47
371
drug 212 drugs 177: food 145; health 130 medical 121 ; disease 117; ; diet 115 cancer 113 aids 98: : homosexuality 96; sex 83 homosexual 82 medicine 82; ; hiv 78; treatment 77
1683
money 479 cost 307 : pay 274; issue 212; prohlem 186; matter 175 ; worth 175, care 153 costs insurance
146: tax 108: expensive 102: responsible 96 risk 96 spend
1856
whole 379; entire 196: full 58; every 49; everything 42 : together 37 everyone 25 #ilu 17 rest 14
##up 13: #iiee 13 away 10; always 10: top 10; ; open 10; Hilss 9
1584
university 1064: ; government 886; law 769 science 482 ; #tuu 412; ; research 312 history 290 laws
165; study 125; : policy 105; court 103: scientific 98: physics 97 constitution 93
1514
life 663; live 363, ; security 192; ; exist 188; : peace 180 dead 175, living 164; existence 157 ; body
157: lives 153; exists 137; privacy 128; ; death 126: die 121 safety 112
1208
atheist 165 font 144: ; bio 119: bb 111: homosexual 109: ; ##group 99; : sy 94 mormon 75 fed 72 manual 56; posting 52; spec 52: ##f 50: ##terr 49; auto 42 pointer 41 handgun 37
837 later ; rest 49: ; future 47; 2nd 44 latter 41; : previous 40 : elsewhere
another 974 last 774 next 581 : else 578 second 498 others 472; third 124 first 82 final 69;
1291
lines 1848: read 701: writes 502: line 376: book 319; books 244; write 203; written 177: text 171; reading 157; ; wrote 144; ; article 107: quote 92; writing paper 84
1656
agrec 182; solution 165; advice 128 opinion 110: interface 104 response 88 suggestions 80
recommend 75 alternative 75: discussion 71 offer 71: argument 70; application 69
1874
apple 405; chip 386; disk 373 fbi 289; eneryption 197: ##og 171 hardware 166 nsa 154; ram 154
algorithm 134: tape 129: nasa 119; : chips 111: : ibm 100: ; floppy
1966
stanford 269 washington 177 russian 156 cleveland 141; berkeley 137 california 131 chicago
105: ##co 96; turkey 95 ; york 83 boston 74: ; bosnia 73 sovict 71 russsia 71
603
file 682 list 526; article 501 card 424: bill 237 board 196; book 191 box 180; ;; package 140; page 139; directory 119: section 118; group 14: library 90: files 83
1401
done 644; ; didn 41 perform 35 performed 32: accomplish 25; accomplished 16; could 14; ##d 11 conduct 10; happen 10; say 10; committed finish completed 9; conducted 8
460
clip 186; ##op 175; 162: news 162; posts 109; ; works 106: micro 68 sim 66 share 66 ##yp
58 net 58; wire 54 ##os 48 power 43 : es 40 ; flop 39; mac 39 tool 39
Table 9: More state-word examples, continued.
31

---

Under review as a conference paper at ICLR 2021
Transition
Bigram Occurrence
1843-990
is-that 68; fact-that 51 so-that 50 think-that 46 note-that 41 ; say-that 39; sure-that 38 believe-that 35 out-that 33 know-that 32; seems-that 28; mean-that 26
1010-1016
instead-of 40; amount-of 33; lot-of 26; form-of 23 lack-of 19; institute-of 16; case-of 15 capable-of 14: amounts-of 13: out-of 12; years-of 12 department-of of 11 terms-of 11
960-458
up-to to 56 down-to 29; access-to 25 according to 24; due-to 22; go-to 17 response-to 14; subject-to 13 related-to 13 reference-to to 13; as-to 12 lead-to 12 reply-to 12
441-698
have-to 139 going-to 116 seem-to 114 seems-to 68 supposed-to 40 need-to 30 had-to 26
used-to 22 want-to 20 seemed-to 15 tend-to 14: appears-to 13 likely-to 13 appear-to 12
1712-698
trying-to 67 try-to 46 able-to 43 like-to 41 hard-to 32 seem-to 22 seems-to 22 want-to 21
tend-to to 21: willing-to 18 tried-to 16 enough-to 14; attempt-to 13 continue-to 12
1814-1666 about-it it 91 of-it 71 with-it 42 : to-it 29; for-it 27 do 26 on-it 24; have-it 12; understand-it 11
doing-it know-it 9; see-it : call-ir 8 believe-it 8 #ffing it 7 fix-it 6
1295-523
problem-wii with 32 deal-with 32 do with 28; up- 16; problems with 15 came-with 13 comes-
with 13 allog-withh 12; work-with 12; contact-with 11 wrong-with 10; agree-with 10, disagree- with
based-on 65 depending-on 23; is-on 13 ##s-on 11 down-on 9: effect-on ; arc-on 8; working-on 628-150
8; effects-on activitics-on 7 depend-on 7 be-on 6 run-on 6 depends-on 6
477-1414
have-to 117; going-to to 45; is-to 37 had-to 32 decided-to 12 need-to 11 has-to 11 having-to 9;
required-to 9; willing-to to 8 how-to 8; to 7 reason-to 7 forced-to
477-1277
is 74; have-to 43 had-to 20 used- to 17 required-to 14; going-to to 1to 13 need-to 13 as-to
12 order-to 11: needed-to 11: ##5-to 10: be-to 10; decided-to 10
145-461
believe-that 70: claim-that 24 evidence-that 18 assume-that 17 hope-that 15 belief-that 11 sure-that 9; prove-that 9; assuming-that 8; argue-that 8: likely-that" 7 claims-that
278-217
know-of 22; ; end-of 16 out-of 14 think-of 13 #f 10 accuracy-of 8 top-of 7 friend-of 6
copy-of 6 heard-of 6: one-of 4; middle-of 4: version-of 4 beginning-of 4 awarc-of 4
1820-276
comc-out 30 camc-out 17 coming-out 14 put-out 12 get-out 11 find-out 10 check-out 9 turns-out 7: found-out 7; turn-out 7; turned-out 7 comes-out 7; go-out 6; ##ed-outt 6
1142-461 is-that 17 fact-that 15 understand-that 12 see-that 11 realize-that 11 noted-that 8 says-that 8
note-that 7: read-that forget-that 6 out-that 6: shows-that 6
1010-1998
lot-of 34; set-of 26; bunch-of 24; lots-of 22; series-of 13 number-of ; thousands-of 10: hundreds- of 10; plenty-of 10; full-of 7: pack-of : list-of 6; think-of
1125-843
of-a 124 ; is-a 86; for-a 84 to-a 50 s-a 16; be-a 14; 11 as-a 7 was-a on-a 5; with-a 4 am-a
3: about-a 3; in-a 2; into-a were-a 2; its-a surrounding-a
476-1654
written-hy 13; ##d-by 11 caused-by 8 ##cd-by 8: produced-by 6 followed-by 6; defined-by 4
committed-by 4: hit-bytt-bah 4: supported-by 4: led-by 4 explained-by 4 run-by 4
1812-837
the-other 86 the-next 77 the-last 62: the-second 48 the-first 14; the-latter 10; the-third 9; the-lltest
7: the-rest 6: the-previous 6; the-final 5: the-ffurth 3; the-nearest
1938-145
i-believe 128 i-hope 66 i-suspect 28: i-assume 24; ; i-doubt 18: i-suppose 11 i-guess 11: i-expect
8: i-think 7 i-imagine 6 i-feel 5: i-trust 4 i-gather 3: i-bet 2
1820-1856
pick-up 14: come-up 12; came-up 11 stand-up 11 set-up 11 bring-up 8; show-up 8 comes-up 7;
screwed-up : up 6: wake-up 6: speak- 5 look-uo 5 back-up
1417-979
more-than 163 better-than 33 lean-than 13 faster-than 12; greater-than 11 longer-than 8 #itte-than
7: larger-than 6: worse-than 6: higher-than 6: slower-than 6 easier-than
111-111
of-the 75 to-the 34 for-the 23: on-the 14; with-the 12; about-the 7 part-of 7 in-the 5 into-the 5
like-the 4 out-of ; tt 4 by-the 3: --s as-the 2
1579-654
talking-about 45 talk-about 25 concerned-about 14 worried-about ; know-about 8 stories-about
7: abory-about 7 taluud-about 6; rumours-abon 5 aoows-about? 5 feel-about 5 care-about 4
Table 10: State transition examples, with stopwords
32

---

Under review as a conference paper at ICLR 2021
Transition
Bigram Occurrence
371-371
health-care 14; side-effects 8: im-H#mun 4; infectious-diseases 4; yeast-infections 4 #ithic-medicine
3; treat-cancer' 3; health-insurance 3 barbecue-Hidd 3;
: hiv-infection 3 yeast-syndrome
1214-1214
orbit-Hter 14; astro-WPphysics 7; lunar-orbit 7 space-shutlle 7 earth-orbit pioneer-venus 5
space-station 5; space-HHlab 4; lunar-colony 4 orbit-around 3; space-tug 3 space-H#flight
716-1556
mail-#Hing 15 fra-#feering 12 ##mina-#ttion 9 bash-HWing 7 ##dal-#Hizing 6 ##ras-WWing
##band ##ing 4 #itress fffress-ffiing- 4 full#ffling 4: adapt cluster-#fing 4 sha aia-+ 4
931-931
gamma-ray 17; lead-acid 9: wild-com 4 ; mile-long 3: toteoooee--llee 3 drip-#fipy
diamond-stealle
2 cold-fusion 2 3d-wire 2; acid- batteereeeess 2; schneider-stealth 2 quantum (aauntummblack]
1488-1488
law-enforcemment 17 national-securig 5 bloddd-boodddddee 4: health-care 4: human-right 4 im im-##lmoral
4 prophet-Hitcc 4 social-science 3 ethnic-#ffal
1246-1246
bit-litnet 35 tel-#Htnet 12 use-HHfnet 7 :hone-mmneerrr 7 dial-HHoog 6; ##p-sitt 5 phone-calls 5
bit-block 5 nct-#ficom 4; bat-##f 4 ##t- phone--ccal 4; arc-
1556
abu fou-- 5 #fidal #ffdal-#Hizing 4 obey-ttting 4 robb-##ing 3 ##fo-##ting 3 dial fall##ting ;; contend- ##iin 2
#iin 3 ##ppt #ffing 3 rough- #ffing 3 contact-#ffipg 3; bash-#inng ##ing 3 favor-#ting
202-202
western-reserve 21 case- western 20 ohio-state 19; united- states 10: penn-state 5 african- american 5
5 middle-eastenne 5 polytechnic-stan state 4 North-carolins. 4
1912-1912
world-series 9 home-plate 7 division- winnerr 4; runs-scored 4 matting-averagee 4 game-winner 3 sports-#fichaneel 3 plate-umpire 3 baschall-players 3; league-baschall 3
1461-1461
##l-bus 5; bit-color ; 3d-graphics ##p-posting computer-graphies 3; wire-##frram 3 bit-
graphics 2 ##teg-file2 2 access-encryptioon 2; ##fframe-graphice 2; file-format
123-123
health-care 10: ; high-school 6 es cs-##crrow key-es high- nigh-powerr: 4 local-bus 4 low-level
high-speed 3 minor-lcague 2; service 2 regular-scason 2 mother-##ooard 2
1702- 1702
mile-#ttage engine- compartment 5 semi-auto 5 manual- transmission 5 drive drive-power power 4; door-car 3; passenger-cars 3; sports-car 3 shaft-drive 3; mini-##van 3: speed-manual
1874-1874
floppy-disk jp-#fieg 11 encryntion-algorrihm eneryption-deevccs 5 silicon-graphics 4 disk-drive 4 floppy-drive 4
##iper-chip 7 ##mb-ram 7 ##ga-card
1208-1064
atheist-##s 43 homosexual-#tt 12 ; fod-##s 9 libertarian- 8 #fferi-##s 7 #Mtile##ts 7
azerbaijani-HHe ##s 6; ##ttar##ts 6; mormon-#tt 5 sniper-##s 5 physicist-##s
1710-1710
power-supply 5 atomic-energy 4; water-ice 4 power-cord 4 #ticom-tclocom 3
light-bulb 3 radio-station 3 radio-##us 3; air-conditioning 3: light 2
1080-1080
public-access 19 aia-aonoymouu 5 private-socttee sector 5 available- via 4 general 4 community-
outreach 4 public-domain 3; personal-freedon 3: private-property 3; private-activities
254-1572
jimmy-carter george-bush bill-clinton bryan-murray 4 joe-carter 4 henry-spencer
bill-james 4 janet-reno 4; craig-holland 4 clayton-cramer 4 ##iie-smih
1571-1571
ms-windows 24 windows-nt 12 ibm-pe ms-##dos 7: unix-machine 6; microsoff-windows
windows-applicattons- 4: run-widows a 3; mac-##t 3 desktop-machine
66-66
##ian- 1919 3 energy-signature
charlotte-#Hsvilke environment-variables 2 duty-cycle 2
second-period 2: spin-state power-conssmmpiion 2 inter-Hifmission power-play 2
1683-1683
worth-##whille nominal-fee get-paid 3 risk-factors scholarship-fund 2 cost-$ tax-dollars
2: beneficial-item 2: bank-accoun t
1579-1579
m-sorry news-reports heard-anything 4 ran-#ttting short-story 3 news-reporters 3; press-
conference 3 heard-something 3 tv-coverage 2; horror-stories 2 heard-horror 2
1656-1656
urhana-champaign 3 peace-talks acceptahle-solutionss 2 marriage-partner 2 ; intercontinental-
meetings 2 interested -artiees conference-calls 2 candle-confereece 2 cooperative-
Table 11: State transition examples, without stopwords
33

---

Under review as a conference paper at ICLR 2021
State Sequences
Sentence
1755 0 117 1755 1755 0 117 1138 1755 103 117
a white bathroom with yellow toilet and a bath tub and sink
1138 1755 117
1755 O 117 1755 1755 959 117 117 1138 O 103
white bathroom with a yellow toilct sink and painted bath tub
117
1755 117 1755 1755 117 1138 O 117 1138 103
a bathroom with yellow toilet and white sink and bath tub
117
1755
117
0 1755 117 441 959 0 1061 1755 117
a man reading a newspaper on the side of road
1755
117 0 1755 1755 441 959 117 1061 1755
man reading a newspaper on the side of road
117
1755 117 441 959 117 1061 1755 117 0 959 103
959
man on the side of a road reading the newspaper
1755 117 O 1061 1755 117 1138 00 117
a man posing for a camcra while holding filthy bananas a man posing for the camera holding bananas
1755 1170 0 1061 959 103 O 117
1755 117 0.0 1755 117 1138
959 103 103 959
man posing for camera while holding his filthy ba- nanas
1755 O 103 117 1061 1755 0 117 1061 1755 103
silver clock tower under black intersection tree
1755 O 103 117 441 1755 O 117 1061 1755 103
a silver clock tower on a black intersection near a tree clock tower in the intersection of black near silver tree a motor cycl ist in photograph with a blur motion of freeway photograph of a motor cycl ist motion, with blur in the freeway
103 117 1755 959 103 1061 O 103 103 103
1755 103 103 117 1755 1755 117 1755 1755 0
117 1061 1755 117
1755 117 1061 1755 O 103 103 117 959 1755 1755
1755 1755 1061 117
103 103 103 1755 0.0
117 1061 103 103 117
motor cyel ist in motion blur the freeway at motor eycl ist
1755 117 1061 103 103 103 1755 1170 O 1061 1755 a piece of chocolate bread on a cart spread to a plate
117 1755 0 117
with dark bananas
1755 117 1061 0 103 103 1755
117 1138 1017
piece of dark chocolate bread with bananas and cart spread a plate
103 103 527 1755 1755 117
103 103 1755 117 117 441
441 117
chocolate cart with bananas spread on dark cart on plate
1755 1170 O 1755 117 1061
117 1755 1755 117
lot filled with lots of flowers in ases
1755 1170 O 1755 117 1061 117 959 1138 903 117
a lot filled with lots of flowers, and v ases of it
1061 1687
1755 117 1061 1082 117 O 1755 1138 1061 1595 a lot of v ases filled with lots of flowers
959
O 117 O 1755 117 1755 959 103 441 1755 103
two people walking with dogs in the ocean on a heach with people in the background
1755 117 1755 959 117
1177 441 103 1755 117 1755
117 959
two people on beach with dogs in background
0 117 117 1755 117 441 959 1755 1755 959 117
two people walking with dogs on the beach in the back- ground
1755 117 1061 117 0 1952 0 1061 1755 O 103
a couple of women knceling down next to a blow cat a cat kneeling down next to a couple blow women in dry er
1755 103 0 1952 1061 1061 1755 0 O 117 1755
1755 O 103
1755 117 1061 117 O 19520 1061 1755 103 103
a couple of women kneeling down next to a blow dry er
1755 117 O 1755 103 441 1755 117
hand holds hot dog table a hand holds a hot dog in the table
1755 117 117 1755 103 103 959 103
1755 117 O 1755 103 1061 1755 117 959
a hand holds a hot dog at a table
1755
117 1755 103 1755 1755 117 1061 117
a woman eating a pastry in piece of market area
117
1755
117
1017 150 1113 0 1061 103 1061 1755 a woman is eating piece of pastry at a market area
117
117
117
1755
103 1061 1755 O 1061 117 117
woman eating a pastry at piece of market area
Table 12:
Paraphrase Examples.
34


Reviews:
[{"review_id": "fgLDnX2Ys8r", "reviewer": "Reviewer_cUAQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 paper is well written and does a good job connecting the method with prior work while also explaining the phenomenon that initially inspired the development of their method (the bias of top-k).\n2. The potential connection to randomized automatic differentiation is both intriguing and I think will be useful in many applications. This paper does a good job of highlighting the limitations of our current tools and the authors did a good job documenting how these appear in the implementation.\n3. The visualizations in this paper have strong execution and do a good job providing the reader with intuition regarding the structure of the discrete latent space the algorithm produces.\n\nWeaknesses:\n1. The main reason for approximating partition calculation is to scale LVMs to more states, but from experiment results, it doesn't seem that scaling LVMs to more states helps performance. For example, in table 1, the PPL of RDP-2k is only 0.19 better than RDP-100 which doesn't seem very significant, and in table 2, RDP-2k gets worse BLEU and iBLEU than RDP-50. Based on existing results in the paper, I cannot tell if it's because the approximation is bad, or because LVMs with more states do not get better performance, but either case is evidence against this work (in the former case, the proposed approximation is bad even though it's better than top-k; in the latter case, why would we want to scale LVMs then?). Another concerning result is that RDP-100 outperforms FULL-100 in table 1, and RDP-50 outperforms FULL-50 in table 2 other than self-BLEU. How could an approximation be better than exact inference?\n2. The paper only focuses on a single application of the proposed randomized dynamic programming technique. When introducing such a broad technique, it seems natural to explore a range of applications to showcase the generality. It is unknown how it will perform when applied to other dynamic programming problems found in natural language processing or in machine learning.\n3. I don't think the application of analyzing the representation space of pretrained language models makes sense: the CRF is only used to parameterize the inference network, but the generative model is trained on raw sentences (x) and does not use representations from the pretrained model. This setting contradicts the claim that \"the discovered latent network is intrinsic to the representation manifold\" (section 1, last paragraph), since the generative model is trained on x instead of representations r (Eq. 12). Even with a BERT with random weights, I think it is possible to learn meaningful clusters since the generative model is trained on x (so the posterior can still reveal meaningful structures). To me, a more natural setting would be to use an HMM to parameterize the generative model and perform exact marginalization over latent states using the proposed approach, which does not directly use raw words x but only uses representations r and would be truly \"intrinsic to the representation manifold\".\n4. The paraphrasing experiment is not very clear. Where is bag-of-words used? What is the generative process?\n5. Another issue with the paper is the lack of exploration of different sampling strategies. This is another place where I would be interested in results from a different task or domain. A stronger analysis of how the selection of K1 and K2 changes the result might also give insight into improving the method.\n\nMinor issues:\n1. It would be nice if you can compare to existing unsupervised clustering works such as Brown clustering which has a similar probabilistic formulation (https://github.com/percyliang/brown-cluster).\n2. While the algorithm is inspired by randomized automatic differentiation, a method that provides an unbiased approximation of gradients, this method uses biased gradients of an unbiased approximation of the partition function?\n3. Page 5, For experiment (2), I assume you meant (3)?\n\nQuestions for authors:\n1. \"we extract CRFs on-the-fly from different LVM training stages.\" Would the network learn log potentials to adapt to the approximate partition calculations so evaluation in this way becomes preferable to your approach?\n2. Table 1 PPL, I assume you meant exp -ELBO for your models since true PPL is intractable under the generative model?  Or did you estimate it?\n3. Fig. 2, how are the density curves drawn? Did you run your algorithm multiple times?", "summary_of_the_paper": "This paper proposes a new way to greatly reduce the memory requirements of inference on discrete latent variable models (LVMs). It does this by estimating the key inference steps in dynamic programming through enumerating a small subset of nodes and using importance sampling for the rest of the nodes. This technique is generally applicable to many dynamic programming algorithms and enables scaling LVMs to much more states by reducing memory requirements. Empirically, this work shows that the proposed approach gets better partition estimates than existing methods using top-k approximations. This work also demonstrates an application of the proposed approach on discovering meaningful latent codes and latent trajectories from pretrained language models.", "summary_of_the_review": "This paper is well-organized, has a novel contribution and I believe it will be of interest to various subgroups in the ICLR community. However, the experiment setting does not make much sense to me, and the empirical results are not convincing. I understand that I might be asking for too much for a single paper, but I think this paper would be much stronger with better experimental settings and more thorough analyses. I'd recommend the authors to split this paper into two papers. For example, the first paper can be an in-depth analysis of the proposed randomized dynamic programming algorithm with applications in different domains and different sampling strategies, and the second paper can be about structure discovery in pretrained models with a correct setup. In its current form, I am leaning towards rejecting this paper due to the issues mentioned before.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LufvAwlmTNI", "reviewer": "Reviewer_61KB", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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\n- The proposed Randomized Dynamic Programming approach provides a simple, well-founded approximation to the log partition function, as evidenced by Figure 2, especially in the case of dense distributions. \n- Empirical analysis of State-Word connections [Figure 3] show meaningful linguistic information on semantic and syntactic roles; analysis of State-State Relations [Figure 4] provides information about language compositions such as infinitives and prepositional phrases.\n- Generalizations to different graph structures are discussed in the Appendix, I believe the proposed approach could be extended to tree graphs straightforwardly\n- As expected, memory and runtime for RDP from Appendix section E.4 are low (equivalent to TopK which sets $K_1 = K, K_2=0$)\n- The proposed approach provides insights into linguistic roles and compositions without supervision unlike many preceding works which utilize supervised probing \n\nWeaknesses:\n\n- To the best of my knowledge, the RDP mechanism detailed in this paper combines two well studied approaches (i) importance sampling (i)TopK budget [Sun et al. 2019]. As a result, the methodological novelty of the sampling scheme is somewhat limited.\n- Additionally, the latent network modeling approach is quite similar to standard well-studied approaches (linear-chain CRF, long-tailed prior on proposals, amortized variational inference) and provides limited novelty.\n- As discussed in the paper, most linguistic information seems to be captured by 500 states. It would be helpful to compare experimental results for state-word and state-state relations among the Full, TopK, and RDP approaches which should all be feasible for 500 states. In particular, as seen in Figure 2, the benefits of RDP seem especially beneficial in Dense distributions. How does this translate to differences in the learned state-word and state-state connections?\n- Marginal performance benefits in terms of Test PPL on MSCOCO [Table 1] and on Paraphrase generation on MSCOCO [Table 2] when compared to TopK and Full (for small # of states). \n\n", "summary_of_the_paper": "This paper proposes a latent network analysis, using a proposed a Randomized Dynamic Programming (RDP) approach, to study the topology of the representation space of contextual embedding models. By constructing an unbiased estimator for the partition function with subsampled DP paths, the authors are able to reduce the memory complexity of forward-backward computation on Linear CRFs by 2 orders of magnitude. Using this RDP formulation, inference with structured latent variable models is scalable to 1000s of latent states. Latent states are modeled in a linear chain CRF with a long-tailed prior on transitions and learned using amortized variational inference similar to Fu et al. 2020, Li and Rush 2020. State-word connections in the representation space provide linguistic information that encapsulates syntactic and semantic roles and state-state connections correspond to the construction of phrases. The authors find anchoring states in the representation space that provide enough information to perform unsupervised paraphrase generation. ", "summary_of_the_review": "Interesting approach for inferring large-scale structured latent variable models in contextualized representation space. Empirical results are insightful but methodological contributions seem a bit limited in the context of prior literature.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LuTWi5MdiPc", "reviewer": "Reviewer_Cp5o", "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": "# Summarization\n\nIn this paper, the authors address the issue in the computational and memory efficiency in Dynamic Programming when it is used in the Forward Algorithm for Linear Chain CRF. The author purpose  a Sample Forward Algorithm by randomizing the summation. The authors proves that such randomization is an unbiased estimator for the true sums, and, using Amortized Variational inference for optimization, shows that it empirically reveals meaningful latent topology with much less required resource.\n\n# Strong Points\n\nGenerally this paper is an interesting one, well motivated and easy to follow. It combines the randomized summation, an idea used in [1], to the problem of Forward Algorithm, by viewing Forward Algorithm as a sum-product algorithm applied over the consecutive time steps. Such randomization is proved by the authors to be an unbiased estimator for the true sums.  The experimental section focuses on showing the meaningfulness of the learned latent space, mostly through state-world/state-state relations.\n\nNote that the author uses recently amortized variational inference [1] for optimization and LSTM for parameterization of the forward algorithm [2], which are good to have, yet not central to the main contribution.\n\nAlthough the authors frame it in Linear Chain CRF problems with pre-trained language model for contextualization, I think it could be conceptually expected to a broader spectrum of sum-product algorithms (the author briefly covered that in the Appendix), although this may be beyond the scope of a single paper.\n\n# Weak Points:\n\nThere are a few missing pieces in this work which should be better addressed.\n\nThe first is the difference between the true proposal $\\~{a}$ that is proved by the authors to lead to an unbiased estimator but cannot achieve improvements in computational efficiency, and the practically used proposal as in Eq. 10.  Although Fig 2. shows some distributions by using the practically used prospal that show no bias, it remains unclear how much it differs from the true proposal. Maybe a study of distances vs. memory presentation (e.g., $K_1$) could show a better picture of the trade-offs here.\n\nThe second issue is that, the conceptual benefit from the proposed method is being able to deal with larger $N$ (the number of latent states) where full Dynamic Programming could not run efficiently. However there is no such experiment showing what would be happen with larger $N$.\n\nFinally, the experiments visualizing the latent space are for the proposed method only. It would be interesting to see how it compares with methods that only takes top $K_1$ and the vanilla Forward Algorithm (which takes the full $N^2$ transition matrix) \n\n# Questions for the Authors\n\n  - How are interpretations of states in experiments (e.g. in Fig. 3 and 4) coming from? Are they chosen in some particular way? \n  - Maybe “the more $q_i$ correlates with $a_i$, the less variance $\\hat{S}_2$ has“ can be explained in more detail ?\n  - In Eq 11: $[s_{z_{t-1}; x_{t-1}}]$ should be $[s_{z_{t-1}; r_{t-1}}]$?\n  - In Figure 3, subfigure B1 and B2, states and words are shown in the same space. What are exactly the features for words and states ($r$? $s$? or something else?)?\n\n\n# Assessment\nI think this is an interesting paper and is above the threshold of acceptance since the presented method is somewhat novel and inspiring. I’m willing to increase my score if my concerns are addressed\n\n# Refs\n\n[1] Kool et. al. 2020: Estimating Gradients for Discrete Random Variables by Sampling without Replacement\n[2] Fu et al. 2020:  Latent Template Induction with Gumbel-CRFs \n[3] Li & Rush, 2020: Posterior Control of Blackbox Generation \n\n\n# Post-rebuttal \n\nI thanks the authors for the responses which improves the manuscript a lot. Still, I would like to keep my recommendation \"6: marginally above the acceptance threshold\", since (1) the contribution on RDP and that in linguistic application are entangled and do not provide a clear message, and (2) as issues in my reviews and other reviews remain.\n", "summary_of_the_paper": "In this paper, the authors address the issue in the computational and memory efficiency in Dynamic Programming when it is used in the Forward Algorithm for Linear Chain CRF. The author purpose  a Sample Forward Algorithm by randomizing the summation. The authors proves that such randomization is an unbiased estimator for the true sums, and, using Amortized Variational inference for optimization, shows that it empirically reveals meaningful latent topology with much less required resource.\n", "summary_of_the_review": "I think this is an interesting paper and is above the threshold of acceptance since the presented method is somewhat novel and inspiring. I’m willing to increase my score if my concerns are addressed", "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": "EhxzSZe81jV", "reviewer": "Reviewer_irMJ", "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": "To put it simply, BERT or GPT-2 like models learn continuous contextual representations of words, so sentences. In this paper, linear-chain Conditional Random Field (CRF) model is considered with a number of hidden states which is relatively small w.r.t. number of words, with each hidden state representing a set of words. Just like word indices are discrete, one can think of the indices of the states of CRF as discrete even though the hidden state vectors are high dimensional continuous vectors, hence the authors project this approach as of  discrete latent structures. Essentially, all this approach is doing is clustering words based upon their contextual embeddings, and then building a graph of transition between those states. In the experiments, the number of states is 2000 while the number of words in BERT is 32k, so there isn’t a significant reduction in the number of states if one were to consider each word as a state. There isn’t any novel contribution in this idea, nor a value of such analysis, at least from the perspective to advancing science. Even empirically, I don’t see any interesting insights from the analysis. \n\nFurther, since CRF models are trained using dynamic programming which is efficient in itself but it has quadratic cost in the number of states. It is proposed to sub-sample upon some of the sequences with low weights, while retraining the ones with high weights. This approach is just a heuristic, with many possible flaws. For instance, it is proposed to compute the sequences with high weights absolutely without recursive formulation, which should be expensive. Sampling strategy is not explained well, and I believe challenging to obtain for NLP like high dimensional problems. Besides, the approximation is applied at coarser level, not accounting for tree like structure emerging from recursion, big sequences as child nodes and subsequences as parent nodes. Intuitively, something like brand and bound could have helped if there was sampling accounting for tree structure. It is also worth noting that the proposed sampling approach is not novel but explored in related problems. Theoretical analysis on zero bias is not enough, and there isn’t sufficient analysis for ensuring low variance. ", "summary_of_the_paper": "Contextual embeddings of words are mapped to a sort of cluster of word embeddings with each one corresponding to one possible state in a linear CRF model. The idea is to build a network between the cluster of words (states of CRF) for analysis the manifold of language. To reduce quadratic cost of CRF, a sampling based approach is proposed to compute the partition function. \n\nEmpirical analysis is not very insightful, and the contributions are incremental.\n", "summary_of_the_review": "Probably, this is a preliminary work, and it could become a good paper with lot more research efforts put into it.\n\nAlgorithmic contribution of sampling is interesting but incremental and not throughly studied. Empirical analysis is not very insightful either. I don’t see much justification in mapping 32k contextual embeddings to 2k latent embeddings to build a so called latent representation.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a technique for randomised dynamic programming and uses it to scale a latent variable model that enables interpreting the hidden states of large pre-trained models for text representation and generation.

The current version needs to be improved with regards to scope, which can be seen by the various confusions that it triggered, and which the authors tried to address in the rebuttal phase. It is somewhat unclear to all of us (myself included) whether the paper is about i) randomised dynamic programming (RDP), or ii) RDP's role in a particular LVM (with a CRF posterior approximation), or iii) RDP+LVM's ability to interpret deep Transformer models? Empirically, the paper is much more about (iii), somewhat about (ii, e.g. Table 1), very little about (i, e.g. Figure 2).

*Because the scope is now confusing*, the current version sometimes comes across as relatively incremental or even incomplete:

* Should the authors embrace interpretation. The overall strategy is *very interesting*, and it scales a neat model precisely in the way it needs to be scaled to do what it's meant to do, but this would change the focus of the paper, RDP would be all but a means to an end, and perhaps other techniques for interpretation would be needed.

* Should the authors embrace RDP itself (disentangled from its application to model interpretation). Some of us felt like the randomisation technique on its own is not too surprising (given the work of [Liu et al](http://proceedings.mlr.press/v97/liu19c/liu19c.pdf), for example), and, regardless of that, to push for RDP's significance, the paper would need more comparisons. The only alternative to RDP investigated in the paper is a heuristic top-K gradient. There are deterministic gradients that are less heuristic, and which may become unbiased eventually as training progresses, see for example [[1]](https://aclanthology.org/D18-1108/) and [[2]](https://papers.nips.cc/paper/2020/hash/887caadc3642e304ede659b734f79b00-Abstract.html).

In the first round of reviews there were some comments that questioned the paper's fitness to ICLR, I would like to remark that this has been clarified, and the paper targets a problem of clear relevance to the conference.

I would personally like to add a minor comment: it would be nice to acknowledge some older literature on randomised DPs (see for example [[3]](https://papers.nips.cc/paper/2009/hash/e515df0d202ae52fcebb14295743063b-Abstract.html) and [[4]](https://aclanthology.org/N10-1028/)).
Decision: Reject