Integral probability metric

Last updated

In probability theory, integral probability metrics are types of distance functions between probability distributions, defined by how well a class of functions can distinguish the two distributions. Many important statistical distances are integral probability metrics, including the Wasserstein-1 distance and the total variation distance. In addition to theoretical importance, integral probability metrics are widely used in areas of statistics and machine learning.

Contents

The name "integral probability metric" was given by German statistician Alfred Müller; [1] the distances had also previously been called "metrics with a ζ-structure." [2]

Definition

Integral probability metrics (IPMs) are distances on the space of distributions over a set , defined by a class of real-valued functions on as

here the notation Pf refers to the expectation of f under the distribution P. The absolute value in the definition is unnecessary, and often omitted, for the usual case where for every its negation is also in .

The functions f being optimized over are sometimes called "critic" functions; [3] if a particular achieves the supremum, it is often termed a "witness function" [4] (it "witnesses" the difference in the distributions). These functions try to have large values for samples from P and small (likely negative) values for samples from Q; this can be thought of as a weaker version of classifers, and indeed IPMs can be interpreted as the optimal risk of a particular classifier. [5] :sec. 4

The choice of determines the particular distance; more than one can generate the same distance. [1]

For any choice of , satisfies all the definitions of a metric except that we may have we may have for some PQ; this is variously termed a "pseudometric" or a "semimetric" depending on the community. For instance, using the class which only contains the zero function, is identically zero. is a metric if and only if separates points on the space of probability distributions, i.e. for any PQ there is some such that ; [1] most, but not all, common particular cases satisfy this property.

Examples

All of these examples are metrics except when noted otherwise.

Relationship to f-divergences

The f-divergences are probably the best-known way to measure dissimilarity of probability distributions. It has been shown [5] :sec. 2 that the only functions which are both IPMs and f-divergences are of the form , where and is the total variation distance between distributions.

One major difference between f-divergences and most IPMs is that when P and Q have disjoint support, all f-divergences take on a constant value; [17] by contrast, IPMs where functions in are "smooth" can give "partial credit." For instance, consider the sequence of Dirac measures at 1/n; this sequence converges in distribution to , and many IPMs satisfy , but no nonzero f-divergence can satisfy this. That is, many IPMs are continuous in weaker topologies than f-divergences. This property is sometimes of substantial importance, [18] although other options also exist, such as considering f-divergences between distributions convolved with continuous noise. [18] [19]

Estimation from samples

Because IPM values between discrete distributions are often sensible, it is often reasonable to estimate using a simple "plug-in" estimator: where and are empirical measures of sample sets. These empirical distances can be computed exactly for some classes ; [5] estimation quality varies depending on the distance, but can be minimax-optimal in certain settings. [14] [20] [21]

When exact maximization is not available or too expensive, another commonly used scheme is to divide the samples into "training" sets (with empirical measures and ) and "test" sets ( and ), find approximately maximizing , then use as an estimate. [22] [12] [23] [24] This estimator can possibly be consistent, but has a negative bias [22] :thm. 2. In fact, no unbiased estimator can exist for any IPM [22] :thm. 3, although there is for instance an unbiased estimator of the squared maximum mean discrepancy. [4]

Related Research Articles

In probability theory and statistics, a Gaussian process is a stochastic process, such that every finite collection of those random variables has a multivariate normal distribution, i.e. every finite linear combination of them is normally distributed. The distribution of a Gaussian process is the joint distribution of all those random variables, and as such, it is a distribution over functions with a continuous domain, e.g. time or space.

<span class="mw-page-title-main">Nonlinear dimensionality reduction</span> Summary of algorithms for nonlinear dimensionality reduction

Nonlinear dimensionality reduction, also known as manifold learning, refers to various related techniques that aim to project high-dimensional data onto lower-dimensional latent manifolds, with the goal of either visualizing the data in the low-dimensional space, or learning the mapping itself. The techniques described below can be understood as generalizations of linear decomposition methods used for dimensionality reduction, such as singular value decomposition and principal component analysis.

<span class="mw-page-title-main">Mutual information</span> Measure of dependence between two variables

In probability theory and information theory, the mutual information (MI) of two random variables is a measure of the mutual dependence between the two variables. More specifically, it quantifies the "amount of information" obtained about one random variable by observing the other random variable. The concept of mutual information is intimately linked to that of entropy of a random variable, a fundamental notion in information theory that quantifies the expected "amount of information" held in a random variable.

In mathematical statistics, the Fisher information is a way of measuring the amount of information that an observable random variable X carries about an unknown parameter θ of a distribution that models X. Formally, it is the variance of the score, or the expected value of the observed information.

<span class="mw-page-title-main">Total variation distance of probability measures</span> Concept in probability theory

In probability theory, the total variation distance is a distance measure for probability distributions. It is an example of a statistical distance metric, and is sometimes called the statistical distance, statistical difference or variational distance.

In statistics, the Bhattacharyya distance measures the similarity of two probability distributions. It is closely related to the Bhattacharyya coefficient, which is a measure of the amount of overlap between two statistical samples or populations.

In mathematical statistics, the Kullback–Leibler divergence, denoted , is a type of statistical distance: a measure of how one probability distribution P is different from a second, reference probability distribution Q. A simple interpretation of the KL divergence of P from Q is the expected excess surprise from using Q as a model when the actual distribution is P. While it is a measure of how different two distributions are, and in some sense is thus a "distance", it is not actually a metric, which is the most familiar and formal type of distance. In particular, it is not symmetric in the two distributions, and does not satisfy the triangle inequality. Instead, in terms of information geometry, it is a type of divergence, a generalization of squared distance, and for certain classes of distributions, it satisfies a generalized Pythagorean theorem.

<span class="mw-page-title-main">Bernhard Schölkopf</span> German computer scientist

Bernhard Schölkopf is a German computer scientist known for his work in machine learning, especially on kernel methods and causality. He is a director at the Max Planck Institute for Intelligent Systems in Tübingen, Germany, where he heads the Department of Empirical Inference. He is also an affiliated professor at ETH Zürich, honorary professor at the University of Tübingen and the Technical University Berlin, and chairman of the European Laboratory for Learning and Intelligent Systems (ELLIS).

In information theory, the cross-entropy between two probability distributions and over the same underlying set of events measures the average number of bits needed to identify an event drawn from the set if a coding scheme used for the set is optimized for an estimated probability distribution , rather than the true distribution .

In information theory, perplexity is a measurement of how well a probability distribution or probability model predicts a sample. It may be used to compare probability models. A low perplexity indicates the probability distribution is good at predicting the sample. Perplexity was originally introduced in 1977 in the context of speech recognition by Frederick Jelinek, Robert Leroy Mercer, Lalit R. Bahl, and James K. Baker.

In mathematics, the Wasserstein distance or Kantorovich–Rubinstein metric is a distance function defined between probability distributions on a given metric space . It is named after Leonid Vaseršteĭn.

<span class="mw-page-title-main">Autoencoder</span> Neural network that learns efficient data encoding in an unsupervised manner

An autoencoder is a type of artificial neural network used to learn efficient codings of unlabeled data. An autoencoder learns two functions: an encoding function that transforms the input data, and a decoding function that recreates the input data from the encoded representation. The autoencoder learns an efficient representation (encoding) for a set of data, typically for dimensionality reduction.

Energy distance is a statistical distance between probability distributions. If X and Y are independent random vectors in Rd with cumulative distribution functions (cdf) F and G respectively, then the energy distance between the distributions F and G is defined to be the square root of

In machine learning, the kernel embedding of distributions comprises a class of nonparametric methods in which a probability distribution is represented as an element of a reproducing kernel Hilbert space (RKHS). A generalization of the individual data-point feature mapping done in classical kernel methods, the embedding of distributions into infinite-dimensional feature spaces can preserve all of the statistical features of arbitrary distributions, while allowing one to compare and manipulate distributions using Hilbert space operations such as inner products, distances, projections, linear transformations, and spectral analysis. This learning framework is very general and can be applied to distributions over any space on which a sensible kernel function may be defined. For example, various kernels have been proposed for learning from data which are: vectors in , discrete classes/categories, strings, graphs/networks, images, time series, manifolds, dynamical systems, and other structured objects. The theory behind kernel embeddings of distributions has been primarily developed by Alex Smola, Le Song , Arthur Gretton, and Bernhard Schölkopf. A review of recent works on kernel embedding of distributions can be found in.

<span class="mw-page-title-main">Generative adversarial network</span> Deep learning method

A generative adversarial network (GAN) is a class of machine learning framework and a prominent framework for approaching generative AI. The concept was initially developed by Ian Goodfellow and his colleagues in June 2014. In a GAN, two neural networks contest with each other in the form of a zero-sum game, where one agent's gain is another agent's loss.

<span class="mw-page-title-main">Variational autoencoder</span> Deep learning generative model to encode data representation

In machine learning, a variational autoencoder (VAE) is an artificial neural network architecture introduced by Diederik P. Kingma and Max Welling. It is part of the families of probabilistic graphical models and variational Bayesian methods.

<span class="mw-page-title-main">Neural network Gaussian process</span> The distribution over functions corresponding to an infinitely wide Bayesian neural network.

A Neural Network Gaussian Process (NNGP) is a Gaussian process obtained as the limit of a sequence of neural networks, and provide a closed form way to evaluate many kinds of neural networks.

The Fréchet inception distance (FID) is a metric used to assess the quality of images created by a generative model, like a generative adversarial network (GAN). Unlike the earlier inception score (IS), which evaluates only the distribution of generated images, the FID compares the distribution of generated images with the distribution of a set of real images.

A Stein discrepancy is a statistical divergence between two probability measures that is rooted in Stein's method. It was first formulated as a tool to assess the quality of Markov chain Monte Carlo samplers, but has since been used in diverse settings in statistics, machine learning and computer science.

<span class="mw-page-title-main">Wasserstein GAN</span> Proposed generative adversarial network variant

The Wasserstein Generative Adversarial Network (WGAN) is a variant of generative adversarial network (GAN) proposed in 2017 that aims to "improve the stability of learning, get rid of problems like mode collapse, and provide meaningful learning curves useful for debugging and hyperparameter searches".

References

  1. 1 2 3 Müller, Alfred (June 1997). "Integral Probability Metrics and Their Generating Classes of Functions". Advances in Applied Probability. 29 (2): 429–443. doi:10.2307/1428011. JSTOR   1428011. S2CID   124648603.
  2. Zolotarev, V. M. (January 1984). "Probability Metrics". Theory of Probability & Its Applications. 28 (2): 278–302. doi:10.1137/1128025.
  3. Arjovsky, Martin; Chintala, Soumith; Bottou, Léon (2017-07-17). "Wasserstein Generative Adversarial Networks". International Conference on Machine Learning. PMLR: 214–223.
  4. 1 2 Gretton, Arthur; Borgwardt, Karsten M.; Rasche, Malte J.; Schölkopf, Bernhard; Smola, Alexander (2012). "A Kernel Two-Sample Test" (PDF). Journal of Machine Learning Research. 13: 723–773.
  5. 1 2 3 Sriperumbudur, Bharath K.; Fukumizu, Kenji; Gretton, Arthur; Schölkopf, Bernhard; Lanckriet, Gert R. G. (2009). "On integral probability metrics, φ-divergences and binary classification". arXiv: 0901.2698 [cs.IT].
  6. Fukumizu, Kenji; Gretton, Arthur; Sun, Xiaohui; Schölkopf, Bernhard (2007). "Kernel Measures of Conditional Dependence". Advances in Neural Information Processing Systems .
  7. Sejdinovic, Dino; Sriperumbudur, Bharath; Gretton, Arthur; Fukumizu, Kenji (2013). "Equivalence of distance-based and RKHS-based statistics in hypothesis testing". The Annals of Statistics. 41 (5): 2263–2291. arXiv: 1207.6076 . doi:10.1214/13-aos1140. S2CID   8308769.
  8. Mroueh, Youssef; Li, Chun-Liang; Sercu, Tom; Raj, Anant; Cheng, Yu (2018). "Sobolev GAN". International Conference on Learning Representations .
  9. Uppal, Ananya; Singh, Shashank; Póczos, Barnabás (2019). "Nonparametric Density Estimation & Convergence Rates for GANs under Besov IPM Losses". Advances in Neural Information Processing Systems . arXiv: 1902.03511 .
  10. Uppal, Ananya; Singh, Shashank; Póczos, Barnabás (2020). "Robust Density Estimation under Besov IPM Losses". Advances in Neural Information Processing Systems . arXiv: 2004.08597 .
  11. Kim, Ilmun; Ramdas, Aaditya; Singh, Aarti; Wasserman, Larry (February 2021). "Classification accuracy as a proxy for two-sample testing". The Annals of Statistics . 49 (1). arXiv: 1703.00573 . doi:10.1214/20-AOS1962. S2CID   17668083.
  12. 1 2 Lopez-Paz, David; Oquab, Maxime (2017). "Revisiting Classifier Two-Sample Tests". International Conference on Learning Representations . arXiv: 1610.06545 .
  13. 1 2 Arora, Sanjeev; Ge, Rong; Liang, Yingyu; Ma, Tengyu; Zhang, Yi (2017). "Generalization and Equilibrium in Generative Adversarial Nets (GANs)". International Conference on Machine Learning . arXiv: 1703.00573 .
  14. 1 2 Ji, Kaiyi; Liang, Yingbin (2018). "Minimax Estimation of Neural Net Distance". Advances in Neural Information Processing Systems . arXiv: 1811.01054 .
  15. Stanczuk, Jan; Etmann, Christian; Lisa Maria Kreusser; Schönlieb, Carola-Bibiane (2021). "Wasserstein GANs Work Because They Fail (To Approximate the Wasserstein Distance)". arXiv: 2103.01678 [stat.ML].
  16. Mallasto, Anton; Montúfar, Guido; Gerolin, Augusto (2019). "How Well do WGANs Estimate the Wasserstein Metric?". arXiv: 1910.03875 [cs.LG].
  17. Sutherland, Danica J. "Computing Jensen-Shannon Divergence between discrete and continuous distribution". Stack Exchange Network. Retrieved 18 July 2023.
  18. 1 2 Arjovsky, Martin; Bettou, Léon (2017). "Towards Principled Methods for Training Generative Adversarial Networks". International Conference on Learning Representations . arXiv: 1701.04862 .
  19. Sønderby, Casper Kaae; Caballero, Jose; Theis, Lucas; Shi, Wenzhe; Huszár, Ferenc (2017). "Amortised MAP Inference for Image Super-resolution". International Conference on Learning Representations . Appendix C. arXiv: 1610.04490 .
  20. Tolstikhin, Ilya O.; Sriperumbudur, Bharath K.; Schölkopf, Bernhard (2016). "Minimax Estimation of Maximum Mean Discrepancy with Radial Kernels". Advances in Neural Information Processing Systems .
  21. Singh, Shashank; Póczos, Barnabás (2018). "Minimax Distribution Estimation in Wasserstein Distance". arXiv: 1802.08855 [math.ST].
  22. 1 2 3 Bińkowski, Mikołaj; Sutherland, Danica J.; Arbel, Michael; Gretton, Arthur (2018). "Demystifying MMD GANs". International Conference on Learning Representations . arXiv: 1801.01401 .
  23. Liu, Feng; Xu, Wenkai; Lu, Jie; Zhang, Guangquan; Gretton, Arthur; Sutherland, Danica J. (2020). "Learning Deep Kernels for Non-Parametric Two-Sample Tests". International Conference on Machine Learning . arXiv: 2002.09116 .
  24. Kübler, Jonas M.; Jitkrittum, Wittawat; Schölkopf, Bernhard; Muandent, Krikamol (2021). "A Witness Two-Sample Test". International Conference on Artificial Intelligence and Statistics. arXiv: 2102.05573 .