Let @math be a class of probability distributions over the discrete domain @math We show that if @math satisfies a rather general condition -- essentially, that each distribution in @math can be well-approximated by a variable-width histogram with few bins -- then there is a highly efficient (both in terms of running time and sample complexity) algorithm that can learn any mixture of @math unknown distributions from @math We analyze several natural types of distributions over @math , including log-concave, monotone hazard rate and unimodal distributions, and show that they have the required structural property of being well-approximated by a histogram with few bins. Applying our general algorithm, we obtain near-optimally efficient algorithms for all these mixture learning problems.
Unimodal distributions: The problem of learning a single unimodal distribution is well-understood: Birg ' e @cite_10 gave an efficient algorithm for learning continuous unimodal distributions (whose density is absolutely bounded); his algorithm, when translated to the discrete domain @math , requires @math samples. This sample size is also known to be optimal (up to constant factors) @cite_43 . In recent work, @cite_16 gave an efficient algorithm to learn @math -modal distributions over @math . We remark that their result does not imply ours, as even a mixture of two unimodal distributions over @math may have @math modes. We are not aware of prior work on efficiently learning mixtures of unimodal distributions.
@cite_43 @cite_16 @cite_10
2952993179 2095374884 1763164889 2014277097
A @math -modal probability distribution over the discrete domain @math is one whose histogram has at most @math "peaks" and "valleys." Such distributions are natural generalizations of monotone ( @math ) and unimodal ( @math ) probability distributions, which have been intensively studied in probability theory and statistics. In this paper we consider the problem of (i.e., performing density estimation of) an unknown @math -modal distribution with respect to the @math distance. The learning algorithm is given access to independent samples drawn from an unknown @math -modal distribution @math , and it must output a hypothesis distribution @math such that with high probability the total variation distance between @math and @math is at most @math Our main goal is to obtain algorithms for this problem that use (close to) an information-theoretically optimal number of samples. We give an efficient algorithm for this problem that runs in time @math . For @math , the number of samples used by our algorithm is very close (within an @math factor) to being information-theoretically optimal. Prior to this work computationally efficient algorithms were known only for the cases @math Birge:87b,Birge:97 . A novel feature of our approach is that our learning algorithm crucially uses a new algorithm for as a key subroutine. The learning algorithm uses the property tester to efficiently decompose the @math -modal distribution into @math (near-)monotone distributions, which are easier to learn. We introduce and investigate a new model of learning probability distributions from independent draws. Our model is inspired by the popular Probably Approximately Correct (PAC) model for learning boolean functions from labeled examples [24], in the sense that we emphasize efficient and approximate learning, and we study the learnability of restricted classes of target distributions. The dist ribut ion classes we examine are often defined by some simple computational mechanism for transforming a truly random string of input bits (which is not visible to the learning algorithm) into the stochastic observation (output) seen by the learning algorithm. In this paper, we concentrate on discrete distributions over O, I n. The problem of inferring an approximation to an unknown probability distribution on the basis of independent draws has a long and complex history in the pattern recognition and statistics literature. For instance, the problem of estimating the parameters of a Gaussian density in highdimensional space is one of the most studied statistical problems. Distribution learning problems have often been investigated in the context of unsupervised learning, in which a linear mixture of two or more distributions is generating the observations, and the final goal is not to model the distributions themselves, but to predict from which distribution each observation was drawn. Data clustering methods are a common tool here. There is also a large literature on nonpararnetric density estimation, in which no assumptions are made on the unknown target density. Nearest-neighbor approaches to the unsupervised learning problem often arise in the nonparametric setting. While we obviously cannot do justice to these areas here, the books of Duda and Hart [9] and Vapnik [25] provide excellent overviews and introductions to the pattern recognition work, as well as many pointers for further reading. See also Izenman’s recent survey article [16]. Roughly speaking, our work departs from the traditional statistical and pattern recognition approaches in two ways. First, we place explicit emphasis on the comput ationrd complexity of distribution learning. It seems fair to say that while previous research has provided an excellent understanding of the information-theoretic issues involved in dis- Let @math be a class of probability distributions over the discrete domain @math We show that if @math satisfies a rather general condition -- essentially, that each distribution in @math can be well-approximated by a variable-width histogram with few bins -- then there is a highly efficient (both in terms of running time and sample complexity) algorithm that can learn any mixture of @math unknown distributions from @math We analyze several natural types of distributions over @math , including log-concave, monotone hazard rate and unimodal distributions, and show that they have the required structural property of being well-approximated by a histogram with few bins. Applying our general algorithm, we obtain near-optimally efficient algorithms for all these mixture learning problems. We give an algorithm for learning a mixture of unstructured distributions. This problem arises in various unsupervised learning scenarios, for example in learning topic models from a corpus of documents spanning several topics. We show how to learn the constituents of a mixture of k arbitrary distributions over a large discrete domain [n]= 1, 2, ...,n and the mixture weights, using O(n polylog n) samples. (In the topic-model learning setting, the mixture constituents correspond to the topic distributions.) This task is information-theoretically impossible for k > 1 under the usual sampling process from a mixture distribution. However, there are situations (such as the above-mentioned topic model case) in which each sample point consists of several observations from the same mixture constituent. This number of observations, which we call the "sampling aperture", is a crucial parameter of the problem. We obtain the first bounds for this mixture-learning problem without imposing any assumptions on the mixture constituents. We show that efficient learning is possible exactly at the information-theoretically least-possible aperture of 2k-1. Thus, we achieve near-optimal dependence on n and optimal aperture. While the sample-size required by our algorithm depends exponentially on k, we prove that such a dependence is unavoidable when one considers general mixtures. A sequence of tools contribute to the algorithm, such as concentration results for random matrices, dimension reduction, moment estimations, and sensitivity analysis.