Distribution learning theory explained

The distributional learning theory or learning of probability distribution is a framework in computational learning theory. It has been proposed from Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert Schapire and Linda Sellie in 1994 ^[1] and it was inspired from the PAC-framework introduced by Leslie Valiant.^[2]

In this framework the input is a number of samples drawn from a distribution that belongs to a specific class of distributions. The goal is to find an efficient algorithm that, based on these samples, determines with high probability the distribution from which the samples have been drawn. Because of its generality, this framework has been used in a large variety of different fields like machine learning, approximation algorithms, applied probability and statistics.

This article explains the basic definitions, tools and results in this framework from the theory of computation point of view.

Definitions

Let

style X be the support of the distributions of interest. As in the original work of Kearns et al.^[1] if style X is finite it can be assumed without loss of generality that style X = \{ 0 , 1 \} ^{n} where style n is the number of bits that have to be used in order to represent any style y \in X . We focus in probability distributions over style X .

There are two possible representations of a probability distribution

style D over style X .

• probability distribution function (or evaluator) an evaluator

style E _{D} for style D takes as input any style y \in X and outputs a real number style E _{D[y]} which denotes the probability that of style y according to style D , i.e. style E _{D[y]} = \Pr [Y = y] if style Y \sim D .

• generator a generator

style G _{D} for style D takes as input a string of truly random bits style y and outputs style G _{D[y]} \in X according to the distribution style D . Generator can be interpreted as a routine that simulates sampling from the distribution style D given a sequence of fair coin tosses.

A distribution

style D is called to have a polynomial generator (respectively evaluator) if its generator (respectively evaluator) exists and can be computed in polynomial time.

Let

style C _{X} a class of distribution over X, that is style C _{X} is a set such that every style D \in C _{X} is a probability distribution with support style X . The style C _{X} can also be written as style C for simplicity.

Before defining learnability, it is necessary to define good approximations of a distribution

style D . There are several ways to measure the distance between two distribution. The three more common possibilities are

• Kullback-Leibler divergence
• Total variation distance of probability measures
• Kolmogorov distance

The strongest of these distances is the Kullback-Leibler divergence and the weakest is the Kolmogorov distance. This means that for any pair of distributions

style D , style D' :KL-distance (D, D') \ge TV-distance (D, D') \ge Kolmogorov-distance (D, D')

Therefore, for example if

style D and style D' are close with respect to Kullback-Leibler divergence then they are also close with respectto all the other distances.

Next definitions hold for all the distances and therefore the symbol

style d(D, D') denotes the distance between the distribution style D and the distribution style D' using one of the distances that we describe above. Although learnability of a class of distributions can be defined using any of these distances, applications refer to a specific distance.

The basic input that we use in order to learn a distribution is a number of samples drawn by this distribution. For the computational point of view the assumption is that such a sample is given in a constant amount of time. So it's like having access to an oracle

style GEN(D) that returns a sample from the distribution style D . Sometimes the interest is, apart from measuring the time complexity, to measure the number of samples that have to be used in order to learn a specific distribution style D in class of distributions style C . This quantity is called sample complexity of the learning algorithm.

In order for the problem of distribution learning to be more clear consider the problem of supervised learning as defined in.^[3] In this framework of statistical learning theory a training set

style S = \{(x _{1,} y _{1),} ... , (x _{n,} y _{n)} \} and the goal is to find a target function style f : X → Y that minimizes some loss function, e.g. the square loss function. More formally f = \arg min _{g} \int V(y, g(x)) d\rho(x, y) , where V( ⋅ , ⋅ ) is the loss function, e.g. V(y, z) = (y - z) ^{2} and \rho(x, y) the probability distribution according to which the elements of the training set are sampled. If the conditional probability distribution \rho _{x(y)} is known then the target function has the closed form f(x) = \int _{y} y d\rho _{x(y)} . So the set S is a set of samples from the probability distribution \rho(x, y) . Now the goal of distributional learning theory if to find \rho given S which can be used to find the target function f .

Definition of learnability

A class of distributions

style C is called efficiently learnable if for every style \epsilon > 0 and style 0 < \delta \le 1 given access to style GEN(D) for an unknown distribution style D \in C , there exists a polynomial time algorithm style A , called learning algorithm of style C , that outputs a generator or an evaluator of a distribution style D' such that\Pr[ d(D, D') \le \epsilon ] \ge 1 - \delta

If we know that

style D' \in C then style A is called proper learning algorithm, otherwise is called improper learning algorithm.

In some settings the class of distributions

style C is a class with well known distributions which can be described by a set of parameters. For instance style C could be the class of all the Gaussian distributions style N(\mu, \sigma ^{2)} . In this case the algorithm style A should be able to estimate the parameters style \mu, \sigma . In this case style A is called parameter learning algorithm.

Obviously the parameter learning for simple distributions is a very well studied field that is called statistical estimation and there is a very long bibliography on different estimators for different kinds of simple known distributions. But distributions learning theory deals with learning class of distributions that have more complicated description.

First results

In their seminal work, Kearns et al. deal with the case where

style A is described in term of a finite polynomial sized circuit and they proved the following for some specific classes of distribution.

style OR gate distributions for this kind of distributions there is no polynomial-sized evaluator, unless style \#P \subseteq P/ poly . On the other hand, this class is efficiently learnable with generator.

• Parity gate distributions this class is efficiently learnable with both generator and evaluator.
• Mixtures of Hamming Balls this class is efficiently learnable with both generator and evaluator.
• Probabilistic Finite Automata this class is not efficiently learnable with evaluator under the Noisy Parity Assumption which is an impossibility assumption in the PAC learning framework.

style \epsilon - Covers

One very common technique in order to find a learning algorithm for a class of distributions

style C is to first find a small style \epsilon - cover of style C .

Definition

A set

style C _{\epsilon} is called style \epsilon -cover of style C if for every style D \in C there is a style D' \in C _{\epsilon} such that style d(D, D') \le \epsilon . An style \epsilon - cover is small if it has polynomial size with respect to the parameters that describe style D .

Once there is an efficient procedure that for every

style \epsilon > 0 finds a small style \epsilon - cover style C _{\epsilon} of C then the only left task is to select from style C _{\epsilon} the distribution style D' \in C _{\epsilon} that is closer to the distribution style D \in C that has to be learned.

The problem is that given

style D', D'' \in C _{\epsilon} it is not trivial how we can compare style d(D, D') and style d(D, D'') in order to decide which one is the closest to style D , because style D is unknown. Therefore, the samples from style D have to be used to do these comparisons. Obviously the result of the comparison always has a probability of error. So the task is similar with finding the minimum in a set of element using noisy comparisons. There are a lot of classical algorithms in order to achieve this goal. The most recent one which achieves the best guarantees was proposed by Daskalakis and Kamath^[4] This algorithm sets up a fast tournament between the elements of style C _{\epsilon} where the winner style D ^{*} of this tournament is the element which is style \epsilon - close to style D (i.e. style d(D ^{*,} D) \le \epsilon ) with probability at least style 1 - \delta . In order to do so their algorithm uses style O( log N / \epsilon ^{2)} samples from style D and runs in style O(N log N / \epsilon ^{2)} time, where style N = |C _{\epsilon} | .

Learning sums of random variables

Learning of simple well known distributions is a well studied field and there are a lot of estimators that can be used. One more complicated class of distributions is the distribution of a sum of variables that follow simple distributions. These learning procedure have a close relation with limit theorems like the central limit theorem because they tend to examine the same object when the sum tends to an infinite sum. Recently there are two results that described here include the learning Poisson binomial distributions and learning sums of independent integer random variables. All the results below hold using the total variation distance as a distance measure.

Learning Poisson binomial distributions

Consider

style n independent Bernoulli random variables style X _{1,} ... , X _{n} with probabilities of success style p _{1,} ... , p _{n} . A Poisson Binomial Distribution of order style n is the distribution of the sum style X = \sum _{i} X _{i} . For learning the class style PBD = \{ D : D ~ isaPoissonbinomialdistribution \} . The first of the following results deals with the case of improper learning of style PBD and the second with the proper learning of style PBD .^[5]

Theorem

Let

style D \in PBD then there is an algorithm which given style n , style \epsilon > 0 , style 0 < \delta \le 1 and access to style GEN(D) finds a style D' such that style \Pr[ d(D, D') \le \epsilon ] \ge 1 - \delta . The sample complexity of this algorithm is style \tilde{O}( ( 1 / \epsilon ^{3} ) log ( 1 / \delta) ) and the running time is style \tilde{O}( ( 1 / \epsilon ^{3)} log n log ^{2} ( 1 / \delta) ) .

Theorem

Let

style D \in PBD then there is an algorithm which given style n , style \epsilon > 0 , style 0 < \delta \le 1 and access to style GEN(D) finds a style D' \in PBD such that style \Pr[ d(D, D') \le \epsilon ] \ge 1 - \delta . The sample complexity of this algorithm is style \tilde{O}( ( 1 / \epsilon ^{2} ) ) log ( 1 / \delta) and the running time is style ( 1 / \epsilon) ^{O( log ^{2} ( 1 / \epsilon))} \tilde{O}( log n log ( 1 / \delta) ) .

One part of the above results is that the sample complexity of the learning algorithm doesn't depend on

style n , although the description of style D is linear in style n . Also the second result is almost optimal with respect to the sample complexity because there is also a lower bound of style O( 1 / \epsilon ^{2)} .

The proof uses a small

style \epsilon - cover of style PBD that has been produced by Daskalakis and Papadimitriou,^[6] in order to get this algorithm.

Learning Sums of Independent Integer Random Variables

Consider

style n independent random variables style X _{1,} ... , X _{n} each of which follows an arbitrary distribution with support style \{ 0 , 1 , ... , k - 1 \} . A style k - sum of independent integer random variable of order style n is the distribution of the sum style X = \sum _{i} X _{i} . For learning the classstyle k - SIIRV = \{ D : D isak-sumofindependentintegerrandomvariable \}

there is the following result

Theorem

Let

style D \in k - SIIRV then there is an algorithm which given style n , style \epsilon > 0 and access to style GEN(D) finds a style D' such that style \Pr[ d(D, D') \le \epsilon ] \ge 1 - \delta . The sample complexity of this algorithm is style poly (k / \epsilon) and the running time is also style poly (k / \epsilon) .

Another part is that the sample and the time complexity does not depend on

style n . Its possible to conclude this independence for the previous section if we set style k = 2 .^[7]

Learning mixtures of Gaussians

Let the random variables

style X \sim N(\mu _{1,} \Sigma _{1)} and style Y \sim N(\mu _{2,} \Sigma _{2)} . Define the random variable style Z which takes the same value as style X with probability style w _{1} and the same value as style Y with probability style w _{2} = 1 - w _{1} . Then if style F _{1} is the density of style X and style F _{2} is the density of style Y the density of style Z is style F = w _{1} F _{1} + w _{2} F _{2} . In this case style Z is said to follow a mixture of Gaussians. Pearson ^[8] was the first who introduced the notion of the mixtures of Gaussians in his attempt to explain the probability distribution from which he got same data that he wanted to analyze. So after doing a lot of calculations by hand, he finally fitted his data to a mixture of Gaussians. The learning task in this case is to determine the parameters of the mixture style w _{1,} w _{2,} \mu _{1,} \mu _{2,} \Sigma _{1,} \Sigma _{2} .

The first attempt to solve this problem was from Dasgupta.^[9] In this work Dasgupta assumes that the two means of the Gaussians are far enough from each other. This means that there is a lower bound on the distance

style ||\mu _{1} - \mu _{2||} . Using this assumption Dasgupta and a lot of scientists after him were able to learn the parameters of the mixture. The learning procedure starts with clustering the samples into two different clusters minimizing some metric. Using the assumption that the means of the Gaussians are far away from each other with high probability the samples in the first cluster correspond to samples from the first Gaussian and the samples in the second cluster to samples from the second one. Now that the samples are partitioned the style \mu _{i,} \Sigma _{i} can be computed from simple statistical estimators and style w _{i} by comparing the magnitude of the clusters.

If

style GM is the set of all the mixtures of two Gaussians, using the above procedure theorems like the following can be proved.

Theorem ^[9]

Let

style D \in GM with style ||\mu _{1} - \mu _{2||} \ge c \sqrt{n max ( λ _{max} (\Sigma _{1),} λ _{max} (\Sigma _{2))}} , where style c > 1 / 2 and style λ _{max} (A) the largest eigenvalue of style A , then there is an algorithm which given style \epsilon > 0 , style 0 < \delta \le 1 and access to style GEN(D) finds an approximation style w' _{i,} \mu' _{i,} \Sigma' _{i} of the parameters such that style \Pr[ ||w _{i} - w' _{i||} \le \epsilon ] \ge 1 - \delta (respectively for style \mu _{i} and style \Sigma _{i} . The sample complexity of this algorithm is style M = 2 ^{O( log ^{2} ( 1 / ( \epsilon \delta ) ))} and the running time is style O(M ^{2} d + M d n) .

The above result could also be generalized in

style k - mixture of Gaussians.^[9]

For the case of mixture of two Gaussians there are learning results without the assumption of the distance between their means, like the following one which uses the total variation distance as a distance measure.

Theorem

Let

style F \in GM then there is an algorithm which given style \epsilon > 0 , style 0 < \delta \le 1 and access to style GEN(D) finds style w' _{i,} \mu' _{i,} \Sigma' _{i} such that if style F' = w' _{1} F' _{1} + w' _{2} F' _{2} , where style F' _{i} = N(\mu' _{i,} \Sigma' _{i)} then style \Pr[ d(F, F') \le \epsilon ] \ge 1 - \delta . The sample complexity and the running time of this algorithm is style poly (n, 1 / \epsilon, 1 / \delta, 1 / w _{1,} 1 / w _{2,} 1 / d(F _{1,} F _{2))} .

The distance between

style F _{1} and style F _{2} doesn't affect the quality of the result of the algorithm but just the sample complexity and the running time.^[10]

References

1. M. Kearns, Y. Mansour, D. Ron, R. Rubinfeld, R. Schapire, L. Sellie On the Learnability of Discrete Distributions. ACM Symposium on Theory of Computing, 1994 http://dl.acm.org/citation.cfm?id=195155
2. http://dl.acm.org/citation.cfm?id=1972 L. Valiant A theory of the learnable. Communications of ACM, 1984
3. Lorenzo Rosasco, Tomaso Poggio, "A Regularization Tour of Machine Learning — MIT-9.520 Lectures Notes" Manuscript, Dec. 2014 https://www.mit.edu/~9.520/fall14/
4. C. Daskalakis, G. Kamath Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians. Annual Conference on Learning Theory, 2014 https://arxiv.org/abs/1312.1054
5. C. Daskalakis, I. Diakonikolas, R. Servedio Learning Poisson Binomial Distributions. ACM Symposium on Theory of Computing, 2012 http://dl.acm.org/citation.cfm?id=2214042
6. C. Daskalakis, C. Papadimitriou Sparse Covers for Sums of Indicators. Probability Theory and Related Fields, 2014 https://link.springer.com/article/10.1007%2Fs00440-014-0582-8
7. C. Daskalakis, I. Diakonikolas, R. O’Donnell, R. Servedio, L. Tan Learning Sums of Independent Integer Random Variables. IEEE Symposium on Foundations of Computer Science, 2013 http://dl.acm.org/citation.cfm?id=2570450.2570592
8. K. Pearson Contribution to the Mathematical Theory of Evolution. Philosophical Transactions of the Royal Society in London, 1894 https://www.jstor.org/discover/10.2307/90649?sid=21104909080371&amp;uid=4&amp;uid=2
9. S. Dasgupta Learning Mixtures of Gaussians. IEEE Symposium on Foundations of Computer Science, 1999 http://dl.acm.org/citation.cfm?id=796496
10. A. Kalai, A. Moitra, G. Valiant Efficiently Learning Mixtures of Two Gaussians ACM Symposium on Theory of Computing, 2010 http://dl.acm.org/citation.cfm?id=1806765