Distribution learning theory

Basic Definitions

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

There are two possible representations of a probability distribution D over X .

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

Let C X a class of distribution over X, that is C X is a set such that every D ∈ C X is a probability distribution with support X . The C X can also be written as C for simplicity.

Before defining learnability its necessary to define good approximations of a distribution D . There are several ways to measure the distance between two distribution. The three more common possibilities are

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 D , D ′  :

Therefore, for example if D and D ′ are close with respect to Kullback-Leibler divergence then they are also close with respect to all the other distances.

Next definitions hold for all the distances and therefore the symbol d ( D , D ′ ) denotes the distance between the distribution D and the distribution 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 an 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 G E N ( D ) that returns a sample from the distribution 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 D in class of distributions 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. In this framework of statistical learning theory a training set S = { ( x 1 , y 1 ) , … , ( x n , y n ) } and the goal is to find a target function f : X → Y that minimizes some loss function, e.g. the square loss function. More formally f = arg ⁡ min g ∫ V ( y , g ( x ) ) d ρ ( x , y ) , where V ( ⋅ , ⋅ ) is the loss function, e.g. V ( y , z ) = ( y − z ) 2 and ρ ( x , y ) the probability distribution according to which the elements of the training set are sampled. If the conditional probability distribution ρ x ( y ) is known then the target function has the closed form f ( x ) = ∫ y y d ρ x ( y ) . So the set S is a set of samples from the probability distribution ρ ( x , y ) . Now the goal of distributional learning theory if to find ρ given S which can be used to find the target function f .

Definition of learnability

A class of distributions C is called efficiently learnable if for every ϵ > 0 and 0 < δ ≤ 1 given access to G E N ( D ) for an unknown distribution D ∈ C , there exists a polynomial time algorithm A , called learning algorithm of C , that outputs an generator or an evaluator of a distribution D ′ such that

If we know that D ′ ∈ C then A is called proper learning algorithm, otherwise is called improper learning algorithm.

In some settings the class of distributions C is a class with well known distributions which can be described by set a set of parameters. For instance C could be the class of all the Gaussian distributions N ( μ , σ 2 ) . In this case the algorithm A should be able to estimate the parameters μ , σ . In this case 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 A is described in term of a finite polynomial sized circuit and they proved the following for some specific classes of distribution

ϵ − {displaystyle extstyle epsilon -} Covers

One very common technique in order to find a learning algorithm for a class of distributions C is to first find a small ϵ − cover of C .

Definition

A set C ϵ is called ϵ -cover of C if for every D ∈ C there is a D ′ ∈ C ϵ such that d ( D , D ′ ) ≤ ϵ . An ϵ − cover is small if it has polynomial size with respect to the parameters that describe D .

Once there is an efficient procedure that for every ϵ > 0 finds a small ϵ − cover C ϵ of C then the only left task is to select from C ϵ the distribution D ′ ∈ C ϵ that is closer to the distribution D ∈ C that has to be learned.

The problem is that given D ′ , D ″ ∈ C ϵ it is not trivial how we can compare d ( D , D ′ ) and d ( D , D ″ ) in order to decide which one is the closest to D , because D is unknown. Therefore, the samples from 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 This algorithm sets up a fast tournament between the elements of C ϵ where the winner D ∗ of this tournament is the element which is ϵ − close to D (i.e. d ( D ∗ , D ) ≤ ϵ ) with probability at least 1 − δ . In order to do so their algorithm uses O ( log ⁡ N / ϵ 2 ) samples from D and runs in O ( N log ⁡ N / ϵ 2 ) time, where N = | C ϵ | .

Learning Sums of Random Variables

Learning of simple well known distribution is a well studied field and there are a lot of estimators that can be used. One more complicated class of distributions is the distributions of sum of variables that follow simple distributions. These learning procedure have a close relation with limit theorems like the central limit theorem because they tent to examine the same object when the sum tends to an infinite sum. Recently there are two interesting results that we will describe here 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 n independent Bernoulli random variables X 1 , … , X n with probabilities of success p 1 , … , p n . A Poisson Binomial Distribution of order n is the distribution of the sum X = ∑ i X i . For learning the class P B D = { D : D    is a Poisson binomial distribution } . The first of the following results deals with the case of improper learning of P B D and the second with the proper learning of P B D .

Theorem

Let D ∈ P B D then there is an algorithm which given n , ϵ > 0 , 0 < δ ≤ 1 and access to G E N ( D ) finds a D ′ such that Pr [ d ( D , D ′ ) ≤ ϵ ] ≥ 1 − δ . The sample complexity of this algorithm is O ~ ( ( 1 / ϵ 3 ) log ⁡ ( 1 / δ ) ) and the running time is O ~ ( ( 1 / ϵ 3 ) log ⁡ n log 2 ⁡ ( 1 / δ ) ) .

Theorem

Let D ∈ P B D then there is an algorithm which given n , ϵ > 0 , 0 < δ ≤ 1 and access to G E N ( D ) finds a D ′ ∈ P B D such that Pr [ d ( D , D ′ ) ≤ ϵ ] ≥ 1 − δ . The sample complexity of this algorithm is O ~ ( ( 1 / ϵ 2 ) ) log ⁡ ( 1 / δ ) and the running time is ( 1 / ϵ ) O ( log 2 ⁡ ( 1 / ϵ ) ) O ~ ( log ⁡ n log ⁡ ( 1 / δ ) ) .

One very interesting part of the above results is that the sample complexity of the learning algorithm doesn't depend on n , although the description of D is linear in n . Also the second result is almost optimal with respect to the sample complexity because there is also a lower bound of O ( 1 / ϵ 2 ) .

The proof uses a small ϵ − cover of P B D that has been produced by Daskalakis and Papadimitriou, in order to get this algorithm.

Learning Sums of Independent Integer Random Variables

Consider n independent random variables X 1 , … , X n each of which follows an arbitrary distribution with support { 0 , 1 , … , k − 1 } . A k − sum of independent integer random variable of order n is the distribution of the sum X = ∑ i X i . For learning the class

k − S I I R V = { D : D is a k-sum of independent integer random variable  }

there is the following result

Theorem

Let D ∈ k − S I I R V then there is an algorithm which given n , ϵ > 0 and access to G E N ( D ) finds a D ′ such that Pr [ d ( D , D ′ ) ≤ ϵ ] ≥ 1 − δ . The sample complexity of this algorithm is poly ( k / ϵ ) and the running time is also poly ( k / ϵ ) .

Again one interesting part is that the sample and the time complexity does not depend on n . Its possible to conclude this independence for the previous section if we set k = 2 .

Learning Mixtures of Gaussians

Let the random variables X ∼ N ( μ 1 , Σ 1 ) and Y ∼ N ( μ 2 , Σ 2 ) . Define the random variable Z which takes the same value as X with probability w 1 and the same value as Y with probability w 2 = 1 − w 1 . Then if F 1 is the density of X and F 2 is the density of Y the density of Z is F = w 1 F 1 + w 2 F 2 . In this case Z is said to follow a mixture of Gaussians. Pearson 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 w 1 , w 2 , μ 1 , μ 2 , Σ 1 , Σ 2 .

The first attempt to solve this problem was from Dasgupta. 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 | | μ 1 − μ 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 μ i , Σ i can be computed from simple statistical estimators and w i by comparing the magnitude of the clusters.

If G M is the set of all the mixtures of two Gaussians, using the above procedure theorems like the following can be proved.

Theorem

Let D ∈ G M with | | μ 1 − μ 2 | | ≥ c n max ( λ m a x ( Σ 1 ) , λ m a x ( Σ 2 ) , where c > 1 / 2 and λ m a x ( A ) the largest eigenvalue of A , then there is an algorithm which given ϵ > 0 , 0 < δ ≤ 1 and access to G E N ( D ) finds an approximation w i ′ , μ i ′ , Σ i ′ of the parameters such that Pr [ | | w i − w i ′ | | ≤ ϵ ] ≥ 1 − δ (respectively for μ i and Σ i . The sample complexity of this algorithm is M = 2 O ( log 2 ⁡ ( 1 / ( ϵ δ ) ) ) and the running time is O ( M 2 d + M d n ) .

The above result could also be generalized in k − mixture of Gaussians.

Interestingly 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 F ∈ G M then there is an algorithm which given ϵ > 0 , 0 < δ ≤ 1 and access to G E N ( D ) finds w i ′ , μ i ′ , Σ i ′ such that if F ′ = w 1 ′ F 1 ′ + w 2 ′ F 2 ′ , where F i ′ = N ( μ i ′ , Σ i ′ ) then Pr [ d ( F , F ′ ) ≤ ϵ ] ≥ 1 − δ . The sample complexity and the running time of this algorithm is poly ( n , 1 / ϵ , 1 / δ , 1 / w 1 , 1 / w 2 , 1 / d ( F 1 , F 2 ) ) .

It is very interesting in the above result that the distance between F 1 and F 2 doesn't affect the quality of the result of the algorithm but just the sample complexity and the running time.