PaperlayerView exact revision on arXiv

Source-linked AI summary

Sum-of-Squares Polynomial Flow

Priyank Jaini, Kira A. Selby, Yaoliang Yu

arXiv:1905.02325v2cs.LGstat.ML

TL;DR

The paper addresses high-dimensional density estimation through a unified triangular-map framework that connects autoregressive and flow-based methods. It introduces SOS flows as universal, interpretable, and easy to train, and reports competitive performance in simulations and real-world datasets.

  • Problem

    High-dimensional density estimation needs a unified framework for understanding how autoregressive and flow-based methods represent target densities.

  • Method

    The paper specifies one-dimensional transformations and conditional densities within increasing triangular maps, using conditioner networks to extend them to high dimensions.

  • Results

    SOS flows are shown to be universal, interpretable, and easy to train, with competitive performance in simulations and several real-world datasets.

  • Takeaways & Limitations

    Triangular maps provide a unified way to analyze existing density-estimation methods and motivate SOS flows for stochastic simulation and density estimation.

  • Takeaways & Limitations

    Transformations for target densities with disjoint support may require sharp jumps or near-infinite slopes, and ordinary polynomial approaches can have monotonicity and multivariate-extension difficulties.

Abstract

from arXiv · show

Triangular map is a recent construct in probability theory that allows one to transform any source probability density function to any target density function. Based on triangular maps, we propose a general framework for high-dimensional density estimation, by specifying one-dimensional transformations (equivalently conditional densities) and appropriate conditioner networks. This framework (a) reveals the commonalities and differences of existing autoregressive and flow based methods, (b) allows a unified understanding of the limitations and representation power of these recent approaches and, (c) motivates us to uncover a new Sum-of-Squares (SOS) flow that is interpretable, universal, and easy to train. We perform several synthetic experiments on various density geometries to demonstrate the benefits (and short-comings) of such transformations. SOS flows achieve competitive results in simulations and several real-world datasets.

1. Introduction

The paper develops a triangular-map framework for high-dimensional density estimation, uses it to unify existing autoregressive and flow methods, and introduces SOS flows with competitive empirical performance.

  • 1. Introduction: Triangular maps provide a rigorous framework for relating one-dimensional transformations and conditional densities to multivariate density estimation.The framework studies increasing triangular maps and extends one-dimensional transformations to higher dimensions using conditioner networks.
  • 1. Introduction: SOS flows are universal, interpretable, and easy to train, while achieving competitive performance on simulations and real-world datasets.The paper motivates SOS flows from its triangular-map framework and evaluates them on synthetic and real-world data.
  • 1. Introduction: The paper uses synthetic experiments to examine SOS flows and reports experiments on real-world datasets.The experiments are intended to demonstrate the efficacy of SOS flows.
  • 1. Introduction: The framework exposes similarities and differences among existing autoregressive and flow-based models.It connects triangular-map decompositions to recent generative-modeling approaches.
  • 1. Introduction: The authors provide a unified understanding of the limitations and representational power of these density-estimation methods.This analysis motivates the proposed SOS flow construction.

2. Density estimation through triangular map

This section formulates density estimation through increasing triangular maps, which can represent arbitrary target densities while allowing efficient inversion and Jacobian computation.

  • 2. Density estimation through triangular map: The density-estimation problem is formulated as learning a deterministic transformation that pushes a source density onto a target density.The framework measures closeness between densities using KL divergence and estimates the map from data by maximum likelihood.
  • 2. Density estimation through triangular map: The map may use convenient source distributions such as a standard normal or a uniform distribution over the unit cube.The source density can be selected to facilitate estimation.
  • 2. Density estimation through triangular map: Increasing triangular maps can transform any source density into any target density, uniquely up to null sets of the source density.The result applies to densities on R^d and also to the unit cube [0,1]^d.
  • 2. Density estimation through triangular map: Triangular structure makes Jacobian evaluation and inversion efficient because both reduce to sequential univariate operations.The Jacobian uses products of diagonal partial derivatives, while inversion proceeds by sequentially inverting univariate functions.
  • 2. Density estimation through triangular map: For target densities with disjoint support, the transformation may require near-infinite slopes in regions where the target density has nearly zero mass.The paper notes that well-separated Gaussian mixtures can therefore require sharp jumps in the transformation.

3. Connection to existing works

The paper places triangular-map density estimation in the context of autoregressive models, normalizing flows, and related approaches. It shows how these methods specify conditional densities or triangular transformations, with differing computational structures and representation guarantees.

  • Iterative Gaussianization and Normalizing Flow: Iterative Gaussianization decomposes transformations into alternating diagonal and linear maps, but its linear-map computation has cubic complexity in dimension.Random rotations simplify the linear component but retain the cubic-complexity limitation.
  • Iterative Gaussianization and Normalizing Flow: Normalizing flows share the triangular-map perspective, although some approaches approximate the map through compositions rather than estimating a triangular map directly.The paper distinguishes these related ideas from bona fide triangular-map estimation.
  • (Bona fide) Triangular Approach: Bona fide triangular flows use computationally convenient block transformations, but the paper notes that their ability to approximate arbitrary increasing triangular maps may be unclear.The later extension adds element-wise scaling and shifting to the block transformation.
  • Unified Framework: The unified framework expresses autoregressive and flow-based methods through shared conditioner and transformation components, while tracking weight sharing, universality, and explicit versus implicit triangular learning.Table 1 organizes these method properties using a common notation.
  • Autoregressive Neural Models: Triangular density estimation is connected to autoregressive models because conditional densities can equivalently specify triangular transformations.Each univariate transformation depends on preceding variables through conditioner networks.
  • Autoregressive Neural Models: Autoregressive constructions range from affine transformations to univariate neural networks, with compositions used to increase the representational flexibility of affine maps.The paper identifies affine autoregressive maps as triangular and conditional-density specification as an equivalent formulation.

4. Sum-of-Squares Polynomial Flow

SOS flows parameterize triangular maps with increasing odd-degree polynomials whose coefficients come from conditioner networks. This construction addresses polynomial-flow limitations while supporting universal approximation, interpretability, and potentially simpler training.

  • Motivation: SOS flows overcome polynomial simulation’s limited distributional scope, monotonicity problems, and inefficient multivariate extension.Earlier degree-3 approaches could represent only a strict subset of non-normal distributions, might not be invertible, and extended inefficiently through linear composition.
  • SOS flow construction: Integrating a nonnegative sum-of-squares polynomial yields an increasing polynomial, providing the monotonicity required for invertible triangular transformations.Theorem 2 states that every increasing univariate real polynomial has this representation, with the auxiliary polynomial degree parameter k as small as 2.
  • Universality: As polynomial degree increases, SOS flows can approximate any triangular map; with universal conditioners, they can approximate any increasing continuous triangular map.The increasing-polynomial density theorem supports pointwise approximation, while the conditioner network supplies the required continuous coefficient functions.
  • SOS flow construction: SOS flows use increasing univariate polynomials for conditional densities and conditioner networks to generate their coefficients.The polynomial degree controls the transformation’s approximation order, while the conditioner supplies coefficients based on preceding variables.
  • Universality: The resulting transformed densities converge weakly to any desired target density, establishing SOS flow universality at the density level.The construction can obtain higher-degree approximations either by increasing the polynomial degree or by stacking SOS blocks.
  • Comparison and properties: SOS flows strictly generalize IAF, expose moment-related polynomial coefficients, and may be easier to train because their parameters need no nonnegativity constraint.IAF corresponds to r = 0; unlike NAF, SOS flows do not require nonnegative parameters, avoiding a constraint that may cause numerical overflows or underflows after exponential reparameterization.

5. Experiments

The experiments evaluate SOS flows on synthetic transformations and real-world density-estimation datasets, comparing them with alternative autoregressive and flow-based methods. SOS flows achieve competitive performance on real-world data, with results reported alongside experimental configurations and benchmark tables.

  • Synthetic Experiments: Synthetic experiments test SOS flows on multimodal Gaussian-mixture transformations, including well-connected and disjoint-support cases.The exact transformations are available for comparison, and deep, wide, and wide-deep SOS configurations are evaluated.
  • Real-World Datasets: The evaluation covers five real-world datasets, including four UCI datasets and BSDS300.
  • Experimental Setup: SOS transformations are trained by maximum likelihood from a standard normal source using stacked polynomial blocks.One reported configuration uses 8 blocks, 5 polynomials of degree 4, batch size 1000, learning rate 0.001, and 40 epochs.
  • Real-World Datasets: The experiments also report negative test log-likelihoods for density-estimation models on image datasets, with lower values preferred.
  • Real-World Datasets: SOS flows achieve competitive performance compared with MADE-MoG, MAF, MAF-MoG, TAN, and NAFs on real-world density-estimation datasets.Table 2 reports average held-out test log-likelihoods, with SOS results evaluated using 10-fold cross-validation.

6. Conclusion

The paper presents triangular maps as a unified framework for density estimation and introduces SOS flows within that framework. SOS flows are described as universal, interpretable, and easy to train, achieving competitive results on real-world datasets.

  • Conclusion: The paper unifies density estimation through monotone, bijective triangular maps built from one-dimensional transformations and conditioner networks.
  • Conclusion: SOS flows are presented as universal, interpretable, and easy to train within this triangular-map framework.
  • Conclusion: SOS flows achieve competitive results on real-world datasets after synthetic experiments exploring their transformation properties.

A. Simulated Experiments

Simulated experiments examine SOS flows across conditional-density geometries, transformation representations, and toy datasets. Deep and wide variants represent transformations similarly, while separated multimodal components can produce connecting artifacts.

  • Conditional-Density Geometries: The best performance for the tested conditional-density geometries is achieved by a deep SOS flow.A flat SOS flow captures nearly the target shape but still differs from the true density; more Gaussian-mixture components improve mixture-model estimates.
  • Representation Power: Deep and wide SOS variants perform equally well in representing simulated transformations, but wider flows take significantly longer to train.
  • Toy Datasets: SOS flows are evaluated on Funnel, Banana, Square, Mixture of Gaussians, and Mixture of Rings toy datasets using three blocks of degree-four polynomial sums.
  • Toy Datasets: For multimodal datasets with near-zero-mass regions, SOS transformations can form sharp jumps, while learned densities may contain artifacts connecting separated components.The paper states that clustering can address the separated-component issue in practice.

B. Transformation for Mixture of Gaussians

The transformation from a standard normal source to a Gaussian mixture develops jumps in low-target-density gaps and becomes approximately piecewise linear across mixture components. Its linear-piece slopes depend on component standard deviations, while jump heights depend on mixture separation and weights.

  • Mixture Transformations: The transformation slope is interpreted as a ratio of probability-density quantiles for the source and target variables.
  • Mixture Transformations: The transformation develops near-vertical jumps where the target Gaussian mixture has almost zero mass but the source has finite mass.The slope becomes large and approaches infinity in these gaps.
  • Mixture Transformations: Larger low-density gaps produce taller jumps, and multiple such gaps produce multiple jumps.
  • Mixture Transformations: The slopes of the linear pieces depend on the standard deviations of the corresponding mixture components.At the extremes, the slopes approach the standard deviations of the outer components.
  • Mixture Transformations: A Gaussian-mixture transformation is approximately piecewise linear, with one linear piece per mixture component.

C. Proofs

The section proves that increasing polynomials are dense in the cone of increasing continuous functions. The proof combines density of polynomials with a convexity argument, while a figure illustrates transformations from a standard Gaussian to a Gaussian mixture.

  • Increasing polynomials are dense in the cone of increasing continuous functions under compact-convergence topology.
  • Figure 7 depicts transformation curves from a standard Gaussian to a mixture of Gaussians.
  • The proof applies Weierstrass density within the convex set of increasing functions, using a nonempty interior and Lemma 1.Lemma 1 establishes that intersecting a dense subspace with a convex set having nonempty interior remains dense in that set.
Loading 1905.02325v2…