Year: 2021

Abstract:
In this paper, we provide the first focused study on the discontinuities (aka. holes) in the latent space of Variational Auto-Encoders (VAEs), a phenomenon which has been shown to have a detrimental effect on model capacity. When investigating latent holes, existing works are exclusively centred around the encoder network and they merely explore the existence of holes. We tackle these limitations by proposing a highly efficient Tree-based Decoder-Centric (TDC) algorithm for latent hole identification, with a focal point on the text domain. In contrast to past studies, our approach pays attention to the decoder network, as a decoder has a direct impact on the model’s output quality. Furthermore, we provide, for the first time, in-depth empirical analysis of the latent hole phenomenon, investigating several important aspects such as how the holes impact VAE algorithms’ performance on text generation, and how the holes are distributed in the latent space.

heading: 1 INTRODUCTION
text: Variational Auto-Encoders (VAEs) are powerful unsupervised models for learning low-dimensional manifolds (aka. a latent space) from non-trivial high-dimensional data (Kingma & Welling, 2014; Rezende et al., 2014). They have found successes in a number of downstream tasks across different application domains such as text classification (Xu et al., 2017), transfer learning (Higgins et al., 2017b), image synthesis (Huang et al., 2018; Razavi et al., 2019), language generation (Bowman et al., 2016; He et al., 2019), and music composition (Roberts et al., 2018).
Various effort has been made to improve the capacity of VAEs, where the majority of the extensions are focused on increasing the flexibility of the prior and approximating posterior. For instance, Davidson et al. (2018) introduced the von Mises-Fisher (vMF) distribution to replace the standard Gaussian distribution; Kalatzis et al. (2020) assumed a Riemannian structure over the latent space by adopting the Riemannian Brownian motion prior. A few recent studies attempted to investigate the problem more fundamentally, and revealed that there exist discontinuous regions (we refer to them as “latent holes” following past literature) in the latent space, which have a detrimental effect on model capacity. Falorsi et al. (2018) approached the problem from a theoretical perspective of manifold mismatch and showed that this undesirable phenomenon is due to the latent space’s topological incapability of accurately capturing the properties of a dataset. Xu et al. (2020) examined the obstacles that prevent sequential VAEs from performing well in unsupervised controllable text generation, and empirically discovered that manipulating the latent variables for semantic variations in text often leads to latent variables to reside in some latent holes. As a result, the decoding network fails to properly decode or generalise when the sampled latent variables land in those areas.
Although the works on investigating latent holes are still relatively sparse, they have opened up new opportunities for improving VAE models, where one can design mechanisms directly engineered for mitigating the hole issue. However, it should be noted that existing works (Falorsi et al., 2018; Xu et al., 2020) exclusively target at the encoder network when investigating holes in the latent space, and they merely explored its existence without providing further in-depth analysis of the phenomenon. It has also been revealed that the hole issue is more severe on text compared to the image domain, due to the discreteness of text data (Xu et al., 2020).
In this paper, we tackle the aforementioned issues by proposing a novel tree-based decoder-centric (TDC) algorithm for latent hole identification, with a focus on the text domain. In contrast to existing
works which are encoder-centric, our approach is centric to the decoder network, as a decoder has a direct impact on the model’s performance, e.g., for text generation. Our TDC algorithm is also highly efficient for latent hole searching when compared to existing approaches, owing to the dimension reduction and Breadth-First Search strategies. Another important technical contribution is that we theoretically unify the two prior indicators for latent hole identification, and evidence that the one of Falorsi et al. (2018) is more accurate, which forms the basis of our algorithm detailed in § 3.
In terms of analysing the latent hole phenomenon, we provide, for the first time, an in-depth empirical analysis that examines three important aspects: (i) how the holes impact VAE models’ performance on text generation; (ii) whether the holes are really vacant, i.e., useful information is not captured by the holes at all; and (iii) how the holes are distributed in the latent space. To validate our theory and to demonstrate the generalisability of our proposed TDC algorithm, we pre-train five strong and representative VAE models for producing sentences, including the state-of-the-art model. Comprehensive experiments on the text task involving four large-scale public datasets show that the output quality is strongly correlated with the density of latent holes; that from the perspective of the decoder, the Latent Vacancy Hypothesis proposed by Xu et al. (2020) does not hold empirically; and that holes are ubiquitous and densely distributed in the latent space. Our code will be made publicly available upon the acceptance of this paper.

heading: 2 PRELIMINARIES

heading: 2.1 VARIATIONAL AUTOENCODER
text: A VAE is a generative model which defines a joint distribution over the observations x and the latent variable z̃, i.e., p(x, z̃) = p(x|z̃)p(z̃). Given a dataset X = {xi}Ni=1 with N i.i.d. datapoints, we need to optimise the marginal likelihood p(X) = 1N ∑N i ∫ p(xi|z̃)p(z̃)dz̃ over the entire training set. However, this marginal likelihood is intractable. A common solution is to maximise the Evidence Lower BOund (ELBO) via variational inference for every observation x:
L(θ,φ;x) = Eqφ(z̃|x) ( log pθ(x|z̃) ) −DKL ( qφ(z̃|x)‖p(z̃) ) , (1)
where qφ(z̃|x) is a variational posterior to approximate the true posterior p(z̃|x). The variational posterior qφ(z̃|x) (aka. encoder) and the conditional distribution pθ(x|z̃) (aka. decoder) are set up using two neural networks parameterised by φ and θ, respectively. Normally, the first term in Eq. (1) is the expected data reconstruction loss showing how well the model can reconstruct data given a latent variable. The second term is the KL-divergence of the approximate variational posterior from the prior, i.e., a regularisation forcing the learned posterior to be as close to the prior as possible.

heading: 2.2 EXISTING LATENT HOLE INDICATORS
text: To our knowledge, there are only two prior works which directly determine whether a latent region is continuous or not. One work formalises latent holes based on the relative distance of pairwise points taken from the latent space and the sample space (Falorsi et al., 2018). Concretely speaking, given a pair of vectors z̃i and z̃i+1 which are closely located on a latent path, and their corresponding samples x′i and x′i+1 in the sample space, a latent hole indicator is computed as
ILIP(i) := Dsample(x ′ i,x ′ i+1)/Dlatent(z̃i, z̃i+1), (2)
where Dsample and Dlatent respectively denote the metrics measuring the sample and latent spaces (NB: Dlatent is an arbitrary metric, e.g., the Euclidean distance and Riemannian distance). Falorsi et al. (2018) focused on the image domain and utilised Euclidean distance for both spaces. Based on the concept of Lipschitz continuity, Falorsi et al. (2018) then proposed to measure the continuity of a latent region as follows: under the premise that z̃i+1 does not land on a hole, z̃i is recognised as belonging to a hole if the corresponding ILIP(i) is a large outlier1.
Another line of work (Xu et al., 2020) signals latent holes based on the so-called aggregated posterior, with a focus on sequential VAEs for language modelling. This approach interpolates a series of vectors on a latent path at a small interval, and then scores the i-th latent vector z̃i as
IAGG(i) := ∑M t=1NLL(z̃i,Z
(t))/M, (3) 1Unless otherwise stated, outliers are detected by comparing the subject data point with a fixed bound,
which is pre-determined based on a percentile of all data points.
where Z(t) is the sample of the posterior distribution of the t-th out of the total M training samples, e.g., when studying holes on the encoder side, this distribution can be computed using qφ(z̃|x) in Eq. (1) (Xu et al., 2020). Z(t) serves as the reference when calculating the Negative Log-Likelihood (NLL). After all the interpolated vectors on the latent path are traversed, similar to the first method, vectors with large outlier indicators (IAGG) are identified as in latent holes.
We note that these two indicators actually stem from different intuitions. For ILIP, there is an underlying assumption that a mapping between the sample and latent spaces should have good stability in terms of relative distance change in order to guarantee good continuity in the latent space. In contrast, IAGG is based on the belief that small perturbations on the non-hole regions should not lead to large offsets on the absolute dissimilarity between posterior samples Z(·) and the sample z̃i, and hence the calculation is performed only in the latent space and only around one single latent position. While seemly distinct, we show that (in § 3.2) both indicators actually have tight underlying connections and can be unified in a shared mathematical framework. Moreover, the first indicator (ILIP) is proofed to be more comprehensive than the second (IAGG) and thus can reduce false negatives when identifying holes in the latent space. This forms the basis of our algorithm in § 3, which is the first attempt to identify a VAE decoder’s latent holes for language generation.

heading: 3 METHODOLOGY
text: In this section, we describe our tree-based decoder-centric (TDC) algorithm for latent hole identification, which consists of three main components. We first introduce our heuristic-based Breadth-First Search (BFS) algorithm for highly efficient latent space searching (§ 3.1). We then theoretically proof, for the first time, that two existing holes indicators can be unified under the same framework and that ILIP is a more suitable choice for identifying latent holes (§ 3.2). Finally, we extend ILIP to the text domain by incorporating the Wasserstein distance for the sample space (§ 3.3).

heading: 3.1 TREE-BASED DECODER-CENTRIC LATENT HOLE IDENTIFICATION
text: As discussed earlier, existing works for investigating latent holes of VAEs all exclusively focus on the encoder network (e.g., Falorsi et al. (2018); Xu et al. (2020)), and they cannot be trivially applied to the decoders (which play ultimately important roles on generation tasks) due to metric incompatibility, especially for VAEs in the text domain (see detailed discussion in § 3.3). Another drawback of existing indicators is that they have very limited efficiency. Theoretically, their time complexity for traversing a d-dimensional latent space with I interpolations per path is O(Id) at the optimal efficiency, which is computationally prohibitive as typically d and I are larger than 30 and 50 for VAEs in practice. Each path is parallel to one axis of the traversed latent space2. Empirically, we observe that even finding a handful of latent holes has been shown to be difficult for existing methods (Falorsi et al., 2018; Xu et al., 2020). Therefore, we tackle both challenges by proposing a highly efficient algorithm for decoder-centric latent hole identification. The pipeline of our TDC algorithm is described in Algorithm 1 and we give a detailed discussion as follows. For the visualisation of TDC’s working process in practice, please see Fig. 1.
2For example, in a 3-dimensional latent space with 4 interpolations per path, as each point is the intersection of 3 paths, 43 = 64 points in total are determined. The space is then equally divided into 64 cubes.
Algorithm 1 TDC for latent hole identification Input: Trained VAE model w/ a d-dimensional latent space; original training set X;
reduced dimension dr; the desired number of detected vectors in latent holes Nhole Output: Zhole 1: Z← ∅;Vtrain ← ∅;Dtrain ← ∅ 2: ∀x ∈ X, Z← Z ∪ {z̃} // z̃ is the encoded x 3: ∀x ∈ X, Vtrain ← Vtrain ∪ {E(x)} // E(·) is the expectation 4: ∀x ∈ X, Dtrain ← Dtrain ∪ {σ(x)} // σ(·) is the standard deviation 5: Z′ ← PCA(Z) // Dimension reduced from d to dr 6: C ← a randomly-picked closed cube which contains dr vectors of Z′, w/ edges
parallel to dr dimensional axes 7: Zhole ← ∅; Z′hub ← ∅; Π← ∅ 8: while |Zhole| ≤ Nhole do 9: if Z′hub == ∅ then
10: Z′hub ← {a random point in C} // Restart BFS 11: end if 12: Π← unvisited line segments: passing through vectors in Z′hub ∧ parallel to one
of the dr dimensions ∧
w/ endpoints on C // Depth increases by one 13: Z′hub ← ∅ 14: for each path (cf. § 2.2) in Π do 15: Sample z̃′i on path at an interval of 0.01 ∗min(Dtrain) 16: ∀i, z̃i ← INVERSE PCA(z̃′i) 17: ∀i, decode z̃i to compute I(i) w/ Vtrain and Dtrain // Cf. Eq. (2) in § 2.2 18: if I(i) is an outlier then 19: Zhole ← Zhole ∪ {z̃i}; Z′hub ← Z′hub ∪ {z̃′i} 20: end if 21: end for 22: end while
Dimensionality Reduction. One problem for the current indicators is their limited searching capacity (as evidenced by their time complexity O(Id)) over the target space. Concretely speaking, both indicators rely on signalling latent holes through 1-dimensional traversal, but a latent space normally has dozens of dimensions to guarantee modelling capacity. To alleviate this issue, after feeding all training samples in X to the forward pass of a trained VAE and storing the encoded latent variables in Z (Step 2), we perform dimension reduction using Principal Component Analysis (PCA) (Jolliffe, 1987) and conduct a search in the resulting dr-dimensional space instead of the original d-dimensional space (Step 5). We further save the mathematical expectation and standard deviation of each training sample in Vtrain (Step 3) and Dtrain (Step 4), respectively. In addition, instead of traversing unconstrained paths like past studies, we only visit latent vectors through paths parallel to the dr dimensions (see Step 12 and the next paragraph). Such a setup is based on the intuition that these top principal components contain more information about the latent space, and thus they are more likely to be useful when capturing latent holes.
Initialising Infrastructures for Search. To further boost efficiency, we propose to conduct a search on a tree-based structure within a pre-established cubic fence. To be more concrete, at Step 6 we first locate a cube C which surrounds dr encoded training samples from Z′ (i.e., Z after dimension reduction). These dr posterior vectors serve as references when analysing the distribution of latent holes3 (cf. § 4.2). We restrict the edges of the dr-dimensional C to be parallel to the dr latent dimensional axes and treat C as the range of our search. Next, we regard each sampled latent vector after dimension reduction z̃′i as a node, and in order to expand the search regions rapidly, we need to visit these nodes following a BFS-based procedure (Skiena, 2008). Therefore, our algorithm maintains a set Z′hub to keep track of all untraversed hub nodes, where the root (aka. the first hub node) is randomly initialised in C (Step 10). For each hub node, we define dr orthogonal paths, each of which is a line segment that passes through the hub node and is parallel to one dimension. At Step 12, we log paths having not been previously processed in a set Π.
Identifying Latent Holes. Following the principle of BFS, the TDC algorithm processes all nodes at the same depth (i.e., all nodes on the paths in Π) before moving to the next depth. On each path, following Falorsi et al. (2018) and Xu et al. (2020), at Step 15 we sequentially sample a series
3To avoid cherry-picking and parameter deredundancy, we select dr as the number of contained z̃′ ∈ Z′.
of z̃′i. To ensure the sampling is fine-grained, we set the interpolation interval at the 0.01 times minimum standard deviation of all elements in Dtrain (see Step 4). After that, we utilise the inverse transformation of PCA (Developers, 2011) to reconstruct z̃′i to the original d-dimensional latent space at Step 16 and generate output samples through the decoder at Step 17. One core question raised is how to choose the indicator I between the two existing ones which seem quite distinct (cf. § 2.2). We eventually select the scheme of Falorsi et al. (2018) (i.e., ILIP in Eq. (2)) and further adopt the Wassertein distance as the metric for the sample space. Detailed justifications are provided in § 3.2 and § 3.3, respectively. After all paths in Π are investigated, our algorithm pushes the tree search to its next depth by reloading the emptied Z′hub with newly identified latent variables in the holes (Step 19). The motivation for treating them as new hub nodes comes from our observation that holes tend to gather as clusters. In case that no hub node is added, which suggests the end of current BFS, TDC will bootstrap another tree by randomly picking a new root. The algorithm halts when more than Nhole holes are identified.
In practice, we find that our tree-search strategy with dimension reduction not only boosts the efficiency from an algorithmic perspective, but is also highly parallelisable by nature4 and thus can reduce computational time. In theory, the time complexity of TDC can be reduced toO(Irdr ), where dr can be as small as 3 (cf. § 4) and Ir is typically less than 2, thanks to the parallelism of our algorithm. In experiments, when the device is equipped with a Nvidia GTX Titan-X GPU and a Intel i9-9900K CPU, in most cases TDC (with dr at 8) can return more than 200 holes in less than 5 minutes, whereas the methods of Falorsi et al. (2018) and Xu et al. (2020) often need at least 30 minutes to find a hole in the same setup as our TDC.
3.2 PICKING INDICATOR FOR TDC
Obviously, the indicator used by TDC (Step 17 in Algorithm 1) plays a crucial role as it directly affects the effectiveness of identifying latent holes. By analysing the two existing indicators in § 2.2, we demonstrate that (1) although developed under different intuitions, they can actually be unified within a common framework; (2) although both indicators have been tested successfully in validating the presence of latent holes, the indicator of Falorsi et al. (2018) (ILIP) is more accurate as it has better completeness and is thus more suitable to our algorithm. To begin with, we prove the following lemma: Lemma 1 NLL(x, P ), the NLL of a data point x under a multivariate normal distribution with independent dimensions P can be numerically linked with DG, the so-called Generalized Squared Interpoint Distance (Gnanadesikan & Kettenring, 1972), as
NLL(x, P ) ≡ 1 2 DG(x, µ) + δ(KP ) s.t. P = N (µ,KP ), (4)
where µ denotes the mean, KP denotes the covariance matrix, DG is the so-called Generalized Squared Interpoint Distance (Gnanadesikan & Kettenring, 1972), and δ(·) is a single value function.
Proof. See Appendix A.
Based on this lemma, we find that the right hand of Eq. (3) is numerically equivalent to directly calculating NLL(z̃i,Z(t)) for posterior Z(t), yielding
IAGG(i) ≡ M∑ t=1 [ 1 2 DG(z̃i, µ (t)) + δ(KZ(t)) ] /M s.t. Z(t) = N (µ(t),KZ(t)). (5)
Note that as Z(t) is deterministic, δ(KZ(t)) settles as a constant term. By integrating Eq. (2), w.l.o.g., we can theoretically prove that if a latent position is signalled to be discontinuous by the indicator of Xu et al. (2020), it will be identified using that of Falorsi et al. (2018).
Proof. See Appendix B.
Apart from theoretical proof, empirically we also observe cases showing ILIP has better completeness than IAGG. We present one toy example in Appendix C. To conclude, ILIP should be adopted to reduce the false-negative rate of TDC.
4Our implementation parallelises the computation process at two hierarchies: different paths at the same BFS depth and different z̃′ on the same path.

heading: 3.3 PICKING SAMPLE SPACE METRIC
text: We find that it is impossible to directly apply the indicator of Falorsi et al. (2018) (ILIP) for VAEs for NLP tasks: the Euclidean distance is used as Dsample in the original study which is on vision VAEs, but it cannot be used to measure the distance between sentences5. One straightforward solution is to directly follow Xu et al. (2020) who select NLL, a long-standing and popular metric in past VAE studies on NLP tasks (Bowman et al., 2016; Fu et al., 2019; Zhu et al., 2020). However, it does not make a valid metric for the decoder of VAEs for language generation. To be more concrete, while on the encoder side NLL can be calculated as qφ(z̃|x) in Eq. (1) (Xu et al., 2020) and is thus normal and thus has a metric-based numerical equivalent DNLL (cf. the proofed lemma in § 2.2), on the decoder side the posterior distribution of a output sentence is generally computed by a logsoftmax layer in practice and is thus no longer normal. Instead, coupling the logsoftmax layer with NLL yields cross-entropy (Contributors, 2019), as
H(P,Q) := H(P ) + DKL(P ||Q), (6)
where P and Q are two probability distributions and H(P ) is the entropy of P . It is obvious that H(P,Q) does not qualify as a statistical metric, because it does not satisfy symmetry nor Triangle Inequality. A workaround which adopts the symmetric cross entropy (Wang et al., 2019) and replaces KL-divergence with the positive squared root of its smoothed version, JS-divergence, can somehow alleviate the issues (Osán et al., 2018). Nonetheless, the resulting formula may dramatically lose its measurement capacity when there is no overlap between P and Q (Lin, 1991) (which is common when testing a VAE for language generation) and is thus unsuitable neither.
Finally, we refer to the Wasserstein distance of finite first moment as our final candidate:
DW1(νP , νQ) := inf Γ∈P(P∼νP ,Q∼νQ)
E(P,Q)∼Γ||P,Q||1, (7)
where P(P ∼ νP , Q ∼ νQ) is a set of all joint distributions of (P,Q) with marginals νP and νQ, respectively. DW1 has been adopted in a large body of recent VAE studies, such as Chewi et al. (2021); Tolstikhin et al. (2018); Wu et al. (2019). Moreover, to further enhance efficiency, following Patrini et al. (2020), we select the lightspeed Sinkhorn algorithm (Cuturi, 2013) to compute DW1.

heading: 4 EMPIRICAL STUDIES
text: In this section, we describe our experiment for validating the effectiveness of the proposed TDC algorithm. We first describe our setup, followed by three empirical studies investigating the impact of latent holes on text generation, the vacancy of holes, and how the holes are distributed.

heading: 4.1 EXPERIMENTAL SETUP
text: Models. To demonstrate the generalisability of our proposed TDC algorithm, we pretrain five strong and representative VAE models for language generation, including the state-of-the-art iVAEMI model: Vanilla-VAE (Bowman et al., 2016), which uses LSTM and KL annealing for mitigating the posterior collapse issue; β-VAE (Higgins et al., 2017a), which utilises an adjustable β to balance the reconstruction loss and the KL term; Cyc-VAE (Fu et al., 2019), which employs cyclical annealing for the KL term; iVAEMI (Fang et al., 2019), which replaces the Gaussian-based posteriors with the sample-based distributions; BN-VAE (Zhu et al., 2020), which leverages the batch normalisation for the variational posterior’s parameters.
Datasets. We consider four large-scale datasets, three of which have been commonly used in previous studies for testing VAEs on the language generation task: Yelp15 (Yang et al., 2017), Yahoo (Zhang et al., 2015; Yang et al., 2017), and a downsampled version of SNLI (Bowman et al., 2015; Li et al., 2019). We additionally constructed a dataset (called Wiki) by downloading the latest English Wikipedia articles and then randomly sampling 1% sentences from the whole set. The size of Wiki is 10 times larger than other datasets and it contains more training samples which can cover more areas of the latent space during training VAEs. For Yahoo, Yelp15 and SNLI, their training and validation sets are all 100K and 10K, respectively. For Wiki, the training and validation sets are 1.13M and 141K, respectively.
5In principle, by simply adopting metrics such as Euclidean distance, TDC can also be applied on VAEs for image generation. We will explore this direction in the future.
Hyper-parameter Settings. We adopt the official code of each tested models and apply the same pretraining hyper-parameters to all models. To be concrete, the encoders and decoders of all models are constructed using one-layer LSTM with 1024 hidden units and 512D word embeddings. The dimension of the latent space is 32. KL annealing (Bowman et al., 2016) is applied to all models, and the scalar weight of the KL term linearly increases from 0 to 1 during the first 10 epochs. Dropout layers with a probability 0.5 are installed on the encoder’s both input-to-hidden and hiddento-output layers. All baselines are trained with Adam optimiser with an initial learning rate of 8e-4. Parameters of all models are initialised using a uniform distribution U(−0.01, 0.01) except for word embeddings with U(−0.1, 0.1). The gradients are clipped at 5.0. During training, we set patience at 5 epochs, and adopt early stopping based on Perplexity (PPL) with standard validation splits. For β-VAE and BN-VAE, the corresponding β and γ are set at 0.4 and 0.7, respectively.
Configurations of the TDC Algorithm. As discussed earlier, the dimensions of the original latent space d is 32. When performing dimension reduction, we experiment with dr = {3, 4, 8} for all setups. Empirically, we observe that results for different dr setting show very similar trends. We report the results based on dr = 8 in the main body and provide the results for other settings in Appendices E, F, and G. When computing our hole indicator (Eq. (2)), we follow Falorsi et al. (2018) and adopt the Euclidean distance for Dlatent (NB: for sample space (Dsample) we adopt the Wasserstein distance as discussed in § 3.3). Following Hoaglin et al. (1986), at Step 18 of TDC we adopt the popular Inter-Quartile Range measure that defines large outliers as data points falling above Q3 + 1.5 · (Q3 − Q1), where Q1 and Q3 respectively denote the lower and upper quartile. In all runs, we set Nhole = 200, i.e., the program halts when more than 200 holes are identified and we store the first 200 holes in Zhole for evaluation. For stochastic analysis, we run TDC 50 times for each setup, yielding 50× 200 = 10K latent holes per setup. Recalling that there are 5 models and 4 datasets, we totally have 20 setups.

heading: 4.2 RESULTS AND ANALYSIS
text: Impact of Latent Holes on Text Generation. In this experiment, we investigate how latent holes impact VAE models’ performance on text generation. To our knowledge, this is the first such study as prior works (Falorsi et al., 2018; Xu et al., 2020) merely explored the existence of holes and their schemes are incapable to discover a sufficient amount of holes for quantitative analysis due to algorithm inefficiency (cf. § 3).
Our analysis is established on the correlation between models’ performance on text generation and the density of latent holes. As discussed in § 4.1, we identify 10K holes for each setup using our TDC algorithm, based on which 10K sentences were decoded. We then calculate the average PPL of those 10K sentences using a pre-trained GPT model (Radford et al., 2018) following the practice of Dathathri et al. (2020). As for the density estimation of latent holes, we utilise the average number of paths traversed before the number of identified holes reaches the algorithm halting threshold Nhole = 200. Intuitively, the fewer paths visited, the denser the holes are distributed, and vice versa.
Fig. 2 shows the average PPL versus the number of paths traversed (when reaching 200 identified holes) for each setup. It can be observed that there is a strong negative correlation between the average PPL (lower the better) and the number of visited paths, where the corpuswise Spearman’s correlation coefficient rs is consistently below or equal to -0.70. It can also be observed that the Person’s correlation coefficient rp is below -0.72 for all datasets, showing a certain degree of linearity for the correlation. In summary, the above observations verify the intuition that denser latent hole distribution leads to higher average PPL, and hence worse performance of VAEs for text generation.
Corpus-wisely, we notice that models trained on the Wiki dataset, i.e., our largest training dataset, do not seem to yield improvement for hole reduction when comparing to the much
smaller datasets such as Yelp15. Furthermore, sentences decoded by models trained on Wiki have lower quality than those decoded by the corresponding models trained on Yelp15 and Yahoo. One plausible explanation is that the complexity (e.g., topic coverage) of datasets plays a more important role than the corpus size when training VAEs for language generation. For instance, while SNLI contains the same number of sentences as Yelp15 and Yahoo, models trained on SNLI are substantially inferior to the models trained on the other two datasets in terms of average PPL. Manually examining the datasets reveals that the topics covered topics in Yelp and Yahoo datasets are less diverse than that of SNLI and Wiki, e.g., SNLI was constructed based on Flickr30k (Young et al., 2014), which includes captions for real-world images across a wide range of categories.
Probing the Vacancy of Latent Holes. The previous experiment empirically shows that latent holes indeed have a detrimental effect on VAEs’s generation performance. A recent study (Xu et al., 2020) proposed the so-called Latent Vacancy Hypothesis, assuming holes are vacant with no meaningful information encoded. This motivates us to further probe the vacancy of latent holes. Specifically, we conduct analysis by comparing the sentences decoded by latent vectors from an untrained decoder and by the hole vectors from a VAE decoder trained following the setup in § 4.1. For completeness, we also show the sentence decoded by normal (not in a hole) vectors from a trained VAE. To summarise, we consider three different types of vectors. (1) Hole vectors (HOLE), those being investigated in our previous experiments. (2) Normal vectors (NORM), sampled from the continuous regions near a hole, i.e., z̃i+1 is a normal vector if z̃i is identified to be in a hole in ILIP. (3) Vectors from the latent space of an untrained VAE (RAND). For controlled analysis, we randomly initialised a VAE model and pick latent vectors whose coordinates are the same as those of HOLE vectors. As this VAE is untrained, its latent vectors should carry zero information by nature.
We compute the PPL of the sentences generated by the vectors of each of the above categories. As expected, results in Tab. 1 show that the sentences decoded via HOLE vectors are significantly inferior to those via NORM vectors in almost all setups tested (two-tailed t-test with Bonferroni correction (Dror et al., 2018); p < .05). It can also be observed that sentences decoded via HOLE vectors are a lot better than the random output generated via the RAND vectors (p < .005). This observation suggests that the Latent Vacancy Hypothesis proposed by Xu et al. (2020) does not
hold empirically, i.e., the regions containing HOLE vectors are not vacant, which do capture some information from the training corpus.
Finally, we qualitatively analyse some sentence examples generated by different types of vectors, as shown in Tab. 2. First, we observe that although topologically adjacent in the latent space, HOLE and NORM vectors are decoded into completely irrelevant sentences semantically, indicating that holes, due to severely harming the smoothness of latent continuity, do have a detrimental effect on model’s generation quality. Second, it can be observed that the output sentences generated via RAND vectors are neither syntactically correct, nor making any sense semantically. In contrast, although sentences decoded via HOLE vectors tend to have problematic word matching and contain content which is against common sense, at least they still follow basic grammars in most cases, which once again verifies that HOLE vectors contain some useful information. Based on this finding, one implication of the future work is to introduce a novel regularisation term in the objective function and utilise the detected latent holes to regularise the latent space. In addition, TDC is a plugin for other existing VAE models. During training, TDC can be regarded as a data augmentation approach to treat the detected latent holes as negative samples under contrastive learning framework.
The Distribution of Latent Holes. Finally, we explore how the latent holes are distributed in the latent space. While a prior study (de Haan & Falorsi, 2018) proposed a theoretical hypothesis that latent holes should be densely distributed, it has never been investigated empirically.
We visualise one run of TDC in Fig. 1. As described in § 3.1, C is the minimum cube which can surround the 3 encoded training samples on a local latent region and thus spans quite narrowly (with a side length being around 0.1, while the width of the latent space is more than 5). However, even in this small search space, TDC still successfully halted and identified more than 200 (defined by Nhole, cf. § 3.1) latent holes, showing that the distance between these holes is tiny and their distribution is very dense. Moreover, all these latent holes are detected by traversing only 85 paths, meaning that more than 2 latent holes exist on each path, on average. Similar finding can be obtained in Fig. 4 (we further investigate the fine-grained quantity distribution of identified holes per latent path in Appendix G). In Fig. 3, holes look ubiquitous in the entire latent space, and again we can see that in the 50 ex-
plored regions (the spaces which have been surrounded by C of each run of TDC), the identified latent holes are very close to each other and even form clusters.

heading: 5 CONCLUSION
text: In this paper, we provide a focused study on the discontinuities (aka. holes) in the latent space of VAEs, a phenomenon which has been shown to have a detrimental effect on model capacity. In contrast to existing works which only study on the encoder network but merely explore the existence of holes, we propose a highly efficient tree-based decoder-centric (TDC) algorithm for latent hole identification. Comprehensive experiments on the language generation task show that the performance of text generation is strongly correlated with the density of latent holes, that from the perspective of the decoder, the Latent Vacancy Hypothesis proposed by Xu et al. (2020) does not hold empirically; and that holes are ubiquitous and densely distributed in the latent space.

heading: D GATHERING LATENT HOLES
text: Fig. 6 exhibits one observation where multiple outlier ILIP are identified after visiting just 100 latent vectors on a path. Such example confirms the motivation of the TDC algorithm, i.e., latent holes often gather in small regions and the principal components tend to pass through them.
E PATHS TRAVERSED AND DEPTHS REACHED TILL TDC HALTS
As shown in Tab. 3, for all cubes with different dimension in all datasets, iVAEMI needs to search much more paths and depths than other models to reach the halt condition, and it performs best. On the contrary, the overall worst-performing model, Vanilla-VAE, covers the fewest paths and depths. In addition, when dr increases, we find that the quantity of traversed path gradually increases but the quantity of reached depths decreases, indicating that the distribution of holes is denser in a lowerdimensional cube. By comparing results across different datasets, the distribution of holes is denser in Wiki dataset for VAEs, which agrees with our finding in Fig. 2.
F IMPACT OF LATENT HOLES WHEN dr ∈ {3, 4}

heading: G QUANTITY DISTRIBUTION OF IDENTIFIED HOLES

heading: H LATENT SPACE VISUALISATION
text: Fig. 9 and 10 show that holes are ubiquitously distributed in the entire latent space for different baselines.

heading: I MORE DECODED SEQUENCES

Review summaries:
This paper focuses on the discontinuities (aka. holes) in the latent space of VAE. Unlike previous work which concentrates on the encoder side, this paper pays attention to the decoder network who plays an important role in generation tasks. This paper analyzes two existing latent hole indicators and proves that they can actually be unified within a common framework by detailed theoretical proof. The author proposes a heuristic-based BFS algorithm for highly efﬁcient latent space searching. And comprehensive experiments on the language generation task show how the latent holes harm the performance of VAEs and how the holes are distributed. Experiments also show that the latent vacancy hypothesis proposed by previous work does not hold empirically.

The paper is concerned with discontinuities in the latent space of Variational Autoencoders, specifically with finding those so called holes algorithmically. There are three main contributions: * A theoretical analysis of two existing algorithms for finding holes. The result shows that one is strictly more powerful than the other. * A novel algorithm, TDC, for finding holes that is substantially faster than the existing ones, primarily due to dimensionality reduction techniques. Different from previous algorithms, the hole criterion takes into account the ability of the decoder to generate from a point in latent space. * An empirical analysis of the density of latent holes in different types of VAEs and on varying datasets. Among other things, the paper claims to have found empirical evidence for the Latent Vacancy Hypothesis, which states that holes don't carry any information. To this end, they compare the quality of text generated from a hole to the quality of text generated from an untrained VAE.

This paper studies the holes within the latent space of text VAEs. The major contribution is a hole detection algorithm, which firstly projects the latent representations to a principle subspace, then performs tree-based BFS to detect holes. However, this paper suffers from its unclear presentation of the algorithm (with many mistakes), concerns regarding algorithm scalability and sensitivity, and experiment settings.