{'fraction_non_alphanumeric': 0.03125444628883092, 'fraction_numerical': 0.014085843016362343, 'mean_word_length': 4.688157539789588, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quasi-Autoregressive Residual (QuAR) Flows

Normalizing Flows are a powerful technique for learning and modeling probability distributions given samples from those distributions. The current state of the art results are built upon residual flows as these can model a larger hypothesis space than coupling layers. However, residual flows are extremely computationally expensive both to train and to use, which limits their applicability in practice. In this paper, we introduce a simplification to residual flows using a Quasi-Autoregressive (QuAR) approach. Compared to the standard residual flow approach, this simplification retains many of the benefits of residual flows while dramatically reducing the compute time and memory requirements, thus making flow-based modeling approaches far more tractable and broadening their potential applicability.


Introduction
Learning a probability distribution from some available data is a core problem within machine learning. Fitting distributions can be simple for some low-dimensional datasets, but fitting distributions to high-dimensional data with complex correlations requires a more systematic solution. Normalizing Flows are a family of deep generative models for designing large, complex distributions that capture the essential relationships among the data points. For instance, Normalizing Flows are capable of generating realistic images and achieve close to state of the art performance in density estimation .
Early implementations of Normalizing Flows were coupling layers (Dinh et al., 2014;Kingma & Dhariwal, 2018) and autoregressive flows (Papamakarios et al., 2017;Kingma et al., 2016). These have convenient mathematical properties (easy to compute inverses and log-determinants) but use non-standard architectures and optimizers. The Second workshop on Invertible Neural Networks, Normalizing Flows, and Explicit Likelihood Models (ICML 2020), Virtual Conference. Copyright 2020 Achintya Gopal. All rights reserved. newer technique of residual flows  allows for models that are built on standard components, are more expressive, and have inductive biases that favor simpler functions. However, these models are much more computationally expensive, making it difficult to use these in practical settings.
We propose a variant on residual flows that simplifies the architecture to be Quasi-Autoregressive (QuAR: to be defined in Section 4.1). This provides the benefits of both autoregressive flows and residual flows: computationally tractable mathematical properties (inverse and log-determinant) and more expressive models, respectively. Additionally, we show that the Lipschitz constant (a key constraint in QuAR Flows) can be made more flexible, further increasing the modeling power of quasi-autoregressive flows.

Normalizing Flows
Suppose that we wish to formulate a joint distribution on an n-dimensional real vector x. A flow-based approach treats x as the result of a transformation g applied to an underlying vector z sampled from a base distribution p z (z). In mathematical notation, the generative process for flows is defined as: where p z is often a Normal distribution and g is an invertible function. Notationally, we will use f = g −1 . Using change of variables, the log likelihood of x is To train flows (i.e., maximize the log likelihood of data points), we need to be able to compute the logarithm of the absolute value of the determinant of the Jacobian of f , also called the log-determinant.
Due to the required mathematical property of invertibility, multiple transformations can be composed, and the composition is guaranteed to be invertible. Since the transformations are often implemented as neural networks, the steps in the composition are easy to chain together. Thus, in theory, a potentially complex transformation can be built up from a series a smaller, simpler transformations with tractable log-determinants.
Constructing a Normalizing Flow model in this way provides two obvious applications: drawing samples using the generative process and evaluating the probability density of the modeled distribution by computing p x (x). These require evaluating the inverse transformation f , the log-determinant, and the density p z (z). In practice, if inverting either g or f turns out to be inefficient, then one or the other of these two applications can become intractable. For the second application in particular, computing the log-determinant can be an additional trouble spot. A determinant can be computed in O(n 3 ) time for an arbitrary n-dimensional data space. However, in many applications of flows, such as images, n is large, and a O(n 3 ) cost per evaluation is simply too high to be useful. Therefore, in flow-based modeling, there are recurring themes of imposing constraints on the model that guarantee invertible transformations and log-determinants that can be computed efficiently.

Autoregressive Flows
For a multivariate distribution, the probability density of a data point can be computed using the chain rule: By using a univariate normalizing flow f θ (x i |x <i ) such as an affine transformation for each univariate density, we get an autoregressive flow (Papamakarios et al., 2017). Given that its Jacobian is triangular, the determinant is easy to compute as it is the product of the diagonal of the Jacobian. These models come with an inherent tradeoff: either the log-likelihood is parallelizable and the sampling process is sequential, or vice versa (depending on the parameterization (Kingma et al., 2016)).

Residual Flows
where the Lipschitz constant of F is strictly less than one. This constraint on the Lipschitz constant ensures invertibility; the transform is invertible using Banach's fixed point algorithm (Algorithm 1) where the convergence rate is exponential in the number of iterations and is faster for smaller Lipschitz constants .
The log-determinant is computed by estimating the Taylor series: The Skilling-Hutchinson estimator (Skilling, 1989) is used Algorithm 1 Inverse of Residual Flow via Fixed Point Iteration Input: data y, residual block g, number of iterations n Initialize x 0 = y. for i = 1 to n do x i = y − g(x i−1 ) end for to estimate the trace in the power series; the infinite series is estimated using the Russian Roulette estimator (Kahn, 1955) which randomizes the number of terms evaluated leading to an unbiased estimator of the series.
This architecture can be trained with standard optimizers and higher learning rates without the loss diverging, and it achieves state of the art results in density estimation, sometimes with fewer parameters than coupling layers. All of this indicates that this architecture has a beneficial inductive bias for density estimation.
In the experiments in , the number of terms evaluated during training is set to be 4 in expectation; however, a significantly larger number of terms could be sampled during evaluation. For evaluation with Residual Flows, the minimum number of terms evaluated is set to 20, with some additional terms to ensure the estimator is unbiased.  showed the bias with 10 terms is negligible and is numerically 0 for 20 terms. In practice, this means 11 forward evaluations are needed to get a reasonable estimation of the log-likelihood. (Rezende & Mohamed, 2015) introduced planar flows and radial flows to use in the context of variational inference. Sylvester flows created by (van den Berg et al., 2018) enhanced planar flows by increasing the capacity of each individual transform. Both planar flows and Sylvester flows can be seen as special cases of residual flows. (Germain et al., 2015) introduced large autoregressive models which were then used in flows by Inverse Autoregressive Flows (IAF) (Kingma et al., 2016) and Masked Autoregressive flows (MAF) (Papamakarios et al., 2017). Larger autoregressive flows were created by Neural Autoregressive Flows (NAF) (Huang et al., 2018) and Block NAFs (BNAF) (Cao et al., 2019), both of which have better log-likelihoods but cannot be sampled from.

Related Work
Before residual flows, state of the art performance with flows was achieved by coupling layers such as NICE (Dinh et al., 2014), RealNVP (Dinh et al., 2016), Glow (Kingma & Dhariwal, 2018) and Flow++ (Ho et al., 2019). Within residual flows (defined as f (x) = x + F(x)), if F is autoregressive, then the flow is volume preserving, i.e., the log-determinant is zero. This is equivalent to autoregressive flows where the univariate normalizing flow is simply a shift. On the other hand, if F is quasi-autoregressive, the flow can change the volume of the space allowing for higher density regions around data points.
MADE (Germain et al., 2015) introduced a method to create large autoregressive networks by creating masks per layer that ensure the network is autoregressive. To simplify their masking mechanism and remove the randomness in it, the size of every hidden layer within the network is set to a multiple k of the input dimension D. We define a network with L layers where we use the notation h 1 to denote the input layer and h L to denote the output layer. We can then partition hidden layer where each set H i,d is of size k. For i = 1 and i = L, k = 1. We define the mask such that the neurons in H i,d1 and H i+1,d2 are connected if d 1 < d 2 for i = 1 and d 1 ≤ d 2 for i > 1.
To modify the above construction to be quasi-autoregressive, we change the rule constructing the mask to allow for a connection when d 1 = d 2 in the first layer. To compute the log-determinant of this network, we need to compute the gradients along the diagonal of the Jacobian during the forward pass. Using the notation x i,d,j as the output of the j-th neuron in the set H i,d and the notation ∂ x1 x i,d,j = ∂x i,d,j ∂x 1,d,1 (where we use the first neuron in the denominator since |H 1,d | = 1): where the above is simply an application of the chain rule to compute ∂x L,d,1 ∂x 1,d,1 . Instead of having to construct the full Jacobian of size n 2 , we create vectors ∂ x1 x i,d,j , each with the same size as x i . Compared to a similar step in standard residual flows, this is an exact computation with the downside that the gradients must be implemented without easy support from an autograd engine. Figure 1

Lipschitz Constraint
For a function F = f L • · · · • f 1 , an upper bound on Lip(F) is and so to normalize Lip(F), each function f i is usually normalized independently. We remove this independence to increase the flexibility of F, which we later reference as a Lipschitz Trick. We compose the function f L+1 with F where ≥0 is a learnable parameter and σ ∈ [0, 1) is a constant set at initialization that determines the maximum Lipschitz constant F can attain, controlling the convergence rate of Algorithm 1. If θ were not a learnable parameter and identically zero, then the regularization would be similar to hard spectral normalization which does not allow the neural network to have the flexibility to learn its Lipschitz constant. To ensure that the Lipschitz constant is upper bounded by σ, θ must be non-negative.
Similar to , to reliably compute the spectral norm of the weight matrices within the feedforward and convolutional layers, we use the power iteration method (Miyato et al., 2018) with a variable number of iterations.

LIPSCHITZ CONSTRAINT
To test the flexibility of a single QuAR flow, we create a simple network with one overparameterized QuAR flow containing more than 100K parameters sandwiched between affine transforms and try to fit a mixture of two uniform distributions. While the Lipschitz property of a QuAR flow limits its ability to change the volume of the space, the inclusion of affine transforms relaxes this limitation as an affine transform can change the volume without restriction.
From Figure 2, it can be seen that the same model with only one additional parameter and flexible Lipschitz constants is better able to model the complex function.

INDUCTIVE BIAS
To compare the inductive biases of autoregressive flows, residual flows and QuAR flows, we train all three on a two dimensional mixture of eight Gaussians. More detailed descriptions of the architectures are in Appendix A.1.
Rather than analyzing the likelihoods, which show how well the distribution is modeled in dense regions, we show the contour plot of the log-likelihood in Figure 3 to analyze the sparse regions. Though the autoregressive model correctly added significant density to the modes, its likelihood in sparse regions has unintuitive contours. QuAR flows and residual flows learned contours that better match the original distribution in sparse regions, suggesting that these flows have better inductive biases for learning simpler functions.

Experiments on Image Data
To evaluate the performance of QuAR flows on images, we train convolutional QuAR flows similar to the architecture used in residual flows on MNIST and CIFAR-10. We compare QuAR flows against Residual Flows, Glow (Kingma & Dhariwal, 2018) and Flow++ (Ho et al., 2019). Glow and Flow++ are used in place of autoregressive flows as these models use coupling layers which can be viewed as block-autoregressive.
Though the architecture and the number of parameters in the QuAR flows and residual flows are the same, the number of learnable parameters is much fewer since approximately half of the values in the weight matrices are unused. Table 1 shows that QuAR Flows have an improved bits per dimension (bpd) (Appendix A.2) for MNIST despite having fewer learnable parameters than the other models; the improvement might be due to the Lipschitz Trick. Unfortunately, QuAR flows have a worse bpd than residual flows for CIFAR-10. Nevertheless, they perform comparably to Glow while having half the number of parameters, and even fewer learnable parameters.
Whereas two forward evaluations are needed to evaluate QuAR flows, residual flows require "one plus number of Taylor series terms evaluated" evaluations. To get accurate log-likelihoods from residual flows during test time, twenty terms of the Taylor series of the log-determinant are computed which leads to QuAR flows being over an order of magnitude faster (  per batch is much smaller since  trained their model by evaluating on average four terms. QuAR flows also require less memory, most notably during training as the computation graph is much simpler for QuAR flows, so much less data is cached to compute the gradient. Although QuAR flows' log likelihoods on CIFAR-10 are more comparable to those of Glow than of residual flows, there are two indications that QuAR flows are better suited to density estimation than Glow is. First, QuAR flows can be optimized with Adam (Kingma & Ba, 2015) rather than Adamax without diverging. Second, QuAR flows can be optimized effectively with a batch size of 64 with a learning rate of 1e-3 (versus 512 for Glow with a learning rate of 2e-5), suggesting the gradients are less noisy and the model can be trained faster as a function of the number of updates.

Conclusion and Future Work
In this paper, we showed that Quasi-Autoregressive Residual Flows retain the beneficial inductive bias towards simpler functions of residual flows while greatly reducing the computational cost. We also showed a way to increase the modeling power of Lipschitz-constrained models; this suggests ways to increase capacity in other models that have this requirement, such as WGANs (Arjovsky et al., 2017).
Though the likelihoods of QuAR flows can be evaluated faster than those of residual flows, the sampling procedure still takes the same amount of time; learning the inverse (which could be done in parallel) could speed up the sampling algorithm (van den Oord et al., 2018).
For Section 5.1.2 (and Appendix B), the architectures were designed such that the number of parameters in all three models were comparable. All three were composed of 16 flows with affine transforms between each flow. The residual flow and QuAR flow used feedforward neural networks with sizes 2 − 128 − 128 − 2 with ELU nonlinearities and the autoregressive model used feedforward neural networks with sizes 1 − 128 − 128 − 2. The autoregressive model has an output size of 2 to parameterize an affine transformation similar to Glow.
For Section 5.2, the architecture used for MNIST and CIFAR-10 were similar to those used in residual flows. Actnorm (Kingma & Dhariwal, 2018) was used before and after every QuAR flow. Each residual connection was a convolutional network: For MNIST, a hidden size of 512 is used; for CIFAR-10, a hidden size of 528 is used because the hidden size is set to a multiple of the number of channels and the number of channels are 3, 12, and 48 because of the squeeze operation. Whereas  added 4 fully connected residual blocks at the end of the network, for simplicity, we did not add these layers. For the comparison in time and memory usage, we also removed these layers from residual flows. We also used the memory reduction trick and Backward-in-Forward from .
Similar to other flow papers, we normalize the images to be within the range [0, 1] and add uniform noise U(0, 1/256) to dequantize the discrete variables. Also similar to other papers, the first transform applied is a Logit Transform.
All Residual Flows and QuAR Flows were optimized with Adam whereas the autoregressive model was optimized with Adamax. For the toy data experiments, the models were trained for 20,000 updates; for the image experiments, the models were trained for 300 epochs. Additionally for image experiments, we use Polyak averaging (Polyak & Juditsky, 1992) for evaluation with a decay of 0.999.

A.2. Bits Per Dimension
The performance of log-likelihood models for images is often defined using bits per dimension. Given a dequantization distribution q(x) for x ∈ R d , the bits per dimension is defined as log p(x) − log q(x) d log 2

B. Additional Results on Synthetic Data
For additional analysis of the inductive bias in flow models, we analyze where the eight modes are mapped into the latent space and how they are transformed to those locations. Whereas in residual flows ( Figure 6) and QuAR flows ( Figure 5) the modes are transformed "smoothly" to their location in the latent space, autoregressive flows ( Figure  4) take an unintuitive path to the latent space with some "extreme" transformations. It's possible that these types of transformations are why using optimizers like Adam with autoregressive flows and Glow can cause the loss to diverge.
From the plots, it seems that although autoregressive flows can change the volume of the space, the technique typically moves the space around to normalize the data instead. On the other hand, QuAR flows and residual flows both appear to preferentially reduce the volume such that the space between data points is removed. It is unclear whether this behavior extends to higher dimensions, but it is possible that this is the inductive bias added to these flows.

C. Convolution QuAR Flow
Similar to the fully connected version of autoregressive models, the convolutional version defines a specific ordering in the inputs. The ordering used in QuAR flows is the same as (van den Oord et al., 2016). The masking is also the same to ensure that the operation is autoregressive. However, the same way two different types of masks were used in MADE, PixelRNN also uses two different masks. To change the model to be quasi-autoregressive, we only use one mask so that ∂f (x)i ∂xi = 0. (Gouk et al., 2018) defined a way to apply spectral norm to convolutions; however, due to the simplification to the convolutional operator by (van den Oord et al., 2016), a simpler power iteration method can be used. The key observation is that for a block matrix the spectral norm is the same as for A 0 0 D Because W is a convolution, W can further be written as Thus, when computing the spectral norm of the convolutional weights, the spectral norm of the 1x1 convolution applied along the channels that affect the Jacobian of the block can be computed using the power iteration method of (Miyato et al., 2018). This further reduces the memory requirements on QuAR flows.
This observation could be applied to the weight matrices in fully connected layers even though this does not help memory or time. However, it can cause problems. Say we have a matrix W = 2 3 0 1 and we choose to run the power iteration algorithm on 2 0 0 1 u found by the power iteration method would be [1, 0] and the spectral norm is 2. Now, say that after gradient descent, the matrix we are analyzing changes 2 0 0 3 In most implementations of the power iteration method, u is initialized to the vector found in the previous iteration. However, in this case, after applying power iteration, u and the spectral norm found by the algorithm will not change even though the spectral norm is now 3. This can be mitigated by either not using the block form with the additional zeros or adding random noise to u before applying the power iteration method.

D. Image Generations
We generated samples from our model with best bits per 50