Flow-based generative model

Part of a series on
Machine learning and data mining
Paradigms Supervised learning Unsupervised learning Online learning Batch learning Meta-learning Semi-supervised learning Self-supervised learning Reinforcement learning Curriculum learning Rule-based learning Quantum machine learning
Problems Classification Generative modeling Regression Clustering Dimensionality reduction Density estimation Anomaly detection Data cleaning AutoML Association rules Semantic analysis Structured prediction Feature engineering Feature learning Learning to rank Grammar induction Ontology learning Multimodal learning
Supervised learning (classification • regression) Apprenticeship learning Decision trees Ensembles Bagging Boosting Random forest k-NN Linear regression Naive Bayes Artificial neural networks Logistic regression Perceptron Relevance vector machine (RVM) Support vector machine (SVM)
Clustering BIRCH CURE Hierarchical k-means Fuzzy Expectation–maximization (EM) DBSCAN OPTICS Mean shift
Dimensionality reduction Factor analysis CCA ICA LDA NMF PCA PGD t-SNE SDL
Structured prediction Graphical models Bayes net Conditional random field Hidden Markov
Anomaly detection RANSAC k-NN Local outlier factor Isolation forest
Artificial neural network Autoencoder Cognitive computing Deep learning DeepDream Feedforward neural network Recurrent neural network LSTM GRU ESN reservoir computing Restricted Boltzmann machine GAN Diffusion model SOM Convolutional neural network U-Net Transformer Vision Mamba Spiking neural network Memtransistor Electrochemical RAM (ECRAM)
Reinforcement learning Q-learning SARSA Temporal difference (TD) Multi-agent Self-play
Learning with humans Active learning Crowdsourcing Human-in-the-loop RLHF
Model diagnostics Coefficient of determination Confusion matrix Learning curve ROC curve
Mathematical foundations Kernel machines Bias–variance tradeoff Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory
Machine-learning venues ECML PKDD NeurIPS ICML ICLR IJCAI ML JMLR
Related articles Glossary of artificial intelligence List of datasets for machine-learning research List of datasets in computer vision and image processing Outline of machine learning
v t e

A flow-based generative model is a generative model used in machine learning that explicitly models a probability distribution by leveraging normalizing flow,^[1][2][3] which is a statistical method using the change-of-variable law of probabilities to transform a simple distribution into a complex one.

The direct modeling of likelihood provides many advantages. For example, the negative log-likelihood can be directly computed and minimized as the loss function. Additionally, novel samples can be generated by sampling from the initial distribution, and applying the flow transformation.

In contrast, many alternative generative modeling methods such as variational autoencoder (VAE) and generative adversarial network do not explicitly represent the likelihood function.

Method

Let ${\displaystyle z_{0}}$ be a (possibly multivariate) random variable with distribution ${\displaystyle p_{0}(z_{0})}$.

For ${\displaystyle i=1,...,K}$, let ${\displaystyle z_{i}=f_{i}(z_{i-1})}$ be a sequence of random variables transformed from ${\displaystyle z_{0}}$. The functions ${\displaystyle f_{1},...,f_{K}}$ should be invertible, i.e. the inverse function ${\displaystyle f_{i}^{-1}}$ exists. The final output ${\displaystyle z_{K}}$ models the target distribution.

The log likelihood of ${\displaystyle z_{K}}$ is (see derivation):

${\displaystyle \log p_{K}(z_{K})=\log p_{0}(z_{0})-\sum _{i=1}^{K}\log \left|\det {\frac {df_{i}(z_{i-1})}{dz_{i-1}}}\right|}$

To efficiently compute the log likelihood, the functions ${\displaystyle f_{1},...,f_{K}}$ should be 1. easy to invert, and 2. easy to compute the determinant of its Jacobian. In practice, the functions ${\displaystyle f_{1},...,f_{K}}$ are modeled using deep neural networks, and are trained to minimize the negative log-likelihood of data samples from the target distribution. These architectures are usually designed such that only the forward pass of the neural network is required in both the inverse and the Jacobian determinant calculations. Examples of such architectures include NICE,^[4] RealNVP,^[5] and Glow.^[6]

Derivation of log likelihood

Consider ${\displaystyle z_{1}}$ and ${\displaystyle z_{0}}$. Note that ${\displaystyle z_{0}=f_{1}^{-1}(z_{1})}$.

By the change of variable formula, the distribution of ${\displaystyle z_{1}}$ is:

${\displaystyle p_{1}(z_{1})=p_{0}(z_{0})\left|\det {\frac {df_{1}^{-1}(z_{1})}{dz_{1}}}\right|}$

Where ${\displaystyle \det {\frac {df_{1}^{-1}(z_{1})}{dz_{1}}}}$ is the determinant of the Jacobian matrix of ${\displaystyle f_{1}^{-1}}$.

By the inverse function theorem:

${\displaystyle p_{1}(z_{1})=p_{0}(z_{0})\left|\det \left({\frac {df_{1}(z_{0})}{dz_{0}}}\right)^{-1}\right|}$

By the identity ${\displaystyle \det(A^{-1})=\det(A)^{-1}}$ (where ${\displaystyle A}$ is an invertible matrix), we have:

${\displaystyle p_{1}(z_{1})=p_{0}(z_{0})\left|\det {\frac {df_{1}(z_{0})}{dz_{0}}}\right|^{-1}}$

The log likelihood is thus:

${\displaystyle \log p_{1}(z_{1})=\log p_{0}(z_{0})-\log \left|\det {\frac {df_{1}(z_{0})}{dz_{0}}}\right|}$

In general, the above applies to any ${\displaystyle z_{i}}$ and ${\displaystyle z_{i-1}}$. Since ${\displaystyle \log p_{i}(z_{i})}$ is equal to ${\displaystyle \log p_{i-1}(z_{i-1})}$ subtracted by a non-recursive term, we can infer by induction that:

${\displaystyle \log p_{K}(z_{K})=\log p_{0}(z_{0})-\sum _{i=1}^{K}\log \left|\det {\frac {df_{i}(z_{i-1})}{dz_{i-1}}}\right|}$

Training method

As is generally done when training a deep learning model, the goal with normalizing flows is to minimize the Kullback–Leibler divergence between the model's likelihood and the target distribution to be estimated. Denoting ${\displaystyle p_{\theta }}$ the model's likelihood and ${\displaystyle p^{*}}$ the target distribution to learn, the (forward) KL-divergence is:

${\displaystyle D_{KL}[p^{*}(x)||p_{\theta }(x)]=-\mathbb {E} _{p^{*}(x)}[\log(p_{\theta }(x))]+\mathbb {E} _{p^{*}(x)}[\log(p^{*}(x))]}$

The second term on the right-hand side of the equation corresponds to the entropy of the target distribution and is independent of the parameter ${\displaystyle \theta }$ we want the model to learn, which only leaves the expectation of the negative log-likelihood to minimize under the target distribution. This intractable term can be approximated with a Monte-Carlo method by importance sampling. Indeed, if we have a dataset ${\displaystyle \{x_{i}\}_{i=1:N}}$ of samples each independently drawn from the target distribution ${\displaystyle p^{*}(x)}$, then this term can be estimated as:

${\displaystyle -{\hat {\mathbb {E} }}_{p^{*}(x)}[\log(p_{\theta }(x))]=-{\frac {1}{N}}\sum _{i=0}^{N}\log(p_{\theta }(x_{i}))}$

Therefore, the learning objective

${\displaystyle {\underset {\theta }{\operatorname {arg\,min} }}\ D_{KL}[p^{*}(x)||p_{\theta }(x)]}$

is replaced by

${\displaystyle {\underset {\theta }{\operatorname {arg\,max} }}\ \sum _{i=0}^{N}\log(p_{\theta }(x_{i}))}$

In other words, minimizing the Kullback–Leibler divergence between the model's likelihood and the target distribution is equivalent to maximizing the model likelihood under observed samples of the target distribution.^[7]

A pseudocode for training normalizing flows is as follows:^[8]

• INPUT. dataset ${\displaystyle x_{1:n}}$, normalizing flow model ${\displaystyle f_{\theta }(\cdot ),p_{0}}$.
• SOLVE. ${\displaystyle \max _{\theta }\sum _{j}\ln p_{\theta }(x_{j})}$ by gradient descent
• RETURN. ${\displaystyle {\hat {\theta }}}$

Variants

Planar Flow

The earliest example.^[9] Fix some activation function ${\displaystyle h}$, and let ${\displaystyle \theta =(u,w,b)}$ with the appropriate dimensions, then

The inverse ${\displaystyle f_{\theta }^{-1}}$ has no closed-form solution in general.

The Jacobian is ${\displaystyle |\det(I+h'(\langle w,z\rangle +b)uw^{T})|=|1+h'(\langle w,z\rangle +b)\langle u,w\rangle |}$.

For it to be invertible everywhere, it must be nonzero everywhere. For example, ${\displaystyle h=\tanh }$ and ${\displaystyle \langle u,w\rangle >-1}$ satisfies the requirement.

Nonlinear Independent Components Estimation (NICE)

Let ${\displaystyle x,z\in \mathbb {R} ^{2n}}$ be even-dimensional, and split them in the middle.^[4] Then the normalizing flow functions are

where ${\displaystyle m_{\theta }}$ is any neural network with weights ${\displaystyle \theta }$.

${\displaystyle f_{\theta }^{-1}}$ is just ${\displaystyle z_{1}=x_{1},z_{2}=x_{2}-m_{\theta }(x_{1})}$, and the Jacobian is just 1, that is, the flow is volume-preserving.

When ${\displaystyle n=1}$, this is seen as a curvy shearing along the ${\displaystyle x_{2}}$ direction.

Real Non-Volume Preserving (Real NVP)

The Real Non-Volume Preserving model generalizes NICE model by:^[5]

Its inverse is ${\displaystyle z_{1}=x_{1},z_{2}=e^{-s_{\theta }(x_{1})}\odot (x_{2}-m_{\theta }(x_{1}))}$, and its Jacobian is ${\displaystyle \prod _{i=1}^{n}e^{s_{\theta }(z_{1,})}}$. The NICE model is recovered by setting ${\displaystyle s_{\theta }=0}$. Since the Real NVP map keeps the first and second halves of the vector ${\displaystyle x}$ separate, it's usually required to add a permutation ${\displaystyle (x_{1},x_{2})\mapsto (x_{2},x_{1})}$ after every Real NVP layer.

Generative Flow (Glow)

In generative flow model,^[6] each layer has 3 parts:

• channel-wise affine transform
  $${\displaystyle y_{cij}=s_{c}(x_{cij}+b_{c})}$$

  
  with Jacobian ${\displaystyle \prod _{c}s_{c}^{HW}}$.
• invertible 1x1 convolution
  $${\displaystyle z_{cij}=\sum _{c'}K_{cc'}y_{cij}}$$

  
  with Jacobian ${\displaystyle \det(K)^{HW}}$. Here ${\displaystyle K}$ is any invertible matrix.
• Real NVP, with Jacobian as described in Real NVP.

The idea of using the invertible 1x1 convolution is to permute all layers in general, instead of merely permuting the first and second half, as in Real NVP.

Masked autoregressive flow (MAF)

An autoregressive model of a distribution on ${\displaystyle \mathbb {R} ^{n}}$ is defined as the following stochastic process:^[10]

where ${\displaystyle \mu _{i}:\mathbb {R} ^{i-1}\to \mathbb {R} }$ and ${\displaystyle \sigma _{i}:\mathbb {R} ^{i-1}\to (0,\infty )}$ are fixed functions that define the autoregressive model.

By the reparametrization trick, the autoregressive model is generalized to a normalizing flow:

The autoregressive model is recovered by setting ${\displaystyle z\sim N(0,I_{n})}$.

The forward mapping is slow (because it's sequential), but the backward mapping is fast (because it's parallel).

The Jacobian matrix is lower-diagonal, so the Jacobian is ${\displaystyle \sigma _{1}\sigma _{2}(x_{1})\cdots \sigma _{n}(x_{1:n-1})}$.

Reversing the two maps ${\displaystyle f_{\theta }}$ and ${\displaystyle f_{\theta }^{-1}}$ of MAF results in Inverse Autoregressive Flow (IAF), which has fast forward mapping and slow backward mapping.^[11]

Continuous Normalizing Flow (CNF)

Instead of constructing flow by function composition, another approach is to formulate the flow as a continuous-time dynamic.^[12][13] Let ${\displaystyle z_{0}}$ be the latent variable with distribution ${\displaystyle p(z_{0})}$. Map this latent variable to data space with the following flow function:

${\displaystyle x=F(z_{0})=z_{T}=z_{0}+\int _{0}^{T}f(z_{t},t)dt}$

where ${\displaystyle f}$ is an arbitrary function and can be modeled with e.g. neural networks.

The inverse function is then naturally:^[12]

${\displaystyle z_{0}=F^{-1}(x)=z_{T}+\int _{T}^{0}f(z_{t},t)dt=z_{T}-\int _{0}^{T}f(z_{t},t)dt}$

And the log-likelihood of ${\displaystyle x}$ can be found as:^[12]

${\displaystyle \log(p(x))=\log(p(z_{0}))-\int _{0}^{T}{\text{Tr}}\left[{\frac {\partial f}{\partial z_{t}}}\right]dt}$

Since the trace depends only on the diagonal of the Jacobian ${\displaystyle \partial _{z_{t}}f}$, this allows "free-form" Jacobian.^[14] Here, "free-form" means that there is no restriction on the Jacobian's form. It is contrasted with previous discrete models of normalizing flow, where the Jacobian is carefully designed to be only upper- or lower-diagonal, so that the Jacobian can be evaluated efficiently.

The trace can be estimated by "Hutchinson's trick":^[15][16]

Given any matrix ${\displaystyle W\in \mathbb {R} ^{n\times n}}$, and any random ${\displaystyle u\in \mathbb {R} ^{n}}$ with ${\displaystyle E[uu^{T}]=I}$, we have ${\displaystyle E[u^{T}Wu]=tr(W)}$. (Proof: expand the expectation directly.)

Usually, the random vector is sampled from ${\displaystyle N(0,I)}$ (normal distribution) or ${\displaystyle \{\pm n^{-1/2}\}^{n}}$ (Radamacher distribution).

When ${\displaystyle f}$ is implemented as a neural network, neural ODE methods^[17] would be needed. Indeed, CNF was first proposed in the same paper that proposed neural ODE.

There are two main deficiencies of CNF, one is that a continuous flow must be a homeomorphism, thus preserve orientation and ambient isotopy (for example, it's impossible to flip a left-hand to a right-hand by continuous deforming of space, and it's impossible to turn a sphere inside out, or undo a knot), and the other is that the learned flow ${\displaystyle f}$ might be ill-behaved, due to degeneracy (that is, there are an infinite number of possible ${\displaystyle f}$ that all solve the same problem).

By adding extra dimensions, the CNF gains enough freedom to reverse orientation and go beyond ambient isotopy (just like how one can pick up a polygon from a desk and flip it around in 3-space, or unknot a knot in 4-space), yielding the "augmented neural ODE".^[18]

Any homeomorphism of ${\displaystyle \mathbb {R} ^{n}}$ can be approximated by a neural ODE operating on ${\displaystyle \mathbb {R} ^{2n+1}}$, proved by combining Whitney embedding theorem for manifolds and the universal approximation theorem for neural networks.^[19]

To regularize the flow ${\displaystyle f}$, one can impose regularization losses. The paper ^[15] proposed the following regularization loss based on optimal transport theory:

where ${\displaystyle \lambda _{K},\lambda _{J}>0}$ are hyperparameters. The first term punishes the model for oscillating the flow field over time, and the second term punishes it for oscillating the flow field over space. Both terms together guide the model into a flow that is smooth (not "bumpy") over space and time.

Downsides

Despite normalizing flows success in estimating high-dimensional densities, some downsides still exist in their designs. First of all, their latent space where input data is projected onto is not a lower-dimensional space and therefore, flow-based models do not allow for compression of data by default and require a lot of computation. However, it is still possible to perform image compression with them.^[20]

Flow-based models are also notorious for failing in estimating the likelihood of out-of-distribution samples (i.e.: samples that were not drawn from the same distribution as the training set).^[21] Some hypotheses were formulated to explain this phenomenon, among which the typical set hypothesis,^[22] estimation issues when training models,^[23] or fundamental issues due to the entropy of the data distributions.^[24]

One of the most interesting properties of normalizing flows is the invertibility of their learned bijective map. This property is given by constraints in the design of the models (cf.: RealNVP, Glow) which guarantee theoretical invertibility. The integrity of the inverse is important in order to ensure the applicability of the change-of-variable theorem, the computation of the Jacobian of the map as well as sampling with the model. However, in practice this invertibility is violated and the inverse map explodes because of numerical imprecision.^[25]

Applications

Flow-based generative models have been applied on a variety of modeling tasks, including:

• Audio generation^[26]
• Image generation^[6]
• Molecular graph generation^[27]
• Point-cloud modeling^[28]
• Video generation^[29]
• Lossy image compression^[20]
• Anomaly detection^[30]

References

External links

• Flow-based Deep Generative Models
• Normalizing flow models