We give a highly efficient "semi-agnostic" algorithm for learning univariate probability distributions that are well approximated by piecewise polynomial density functions. Let @math be an arbitrary distribution over an interval @math which is @math -close (in total variation distance) to an unknown probability distribution @math that is defined by an unknown partition of @math into @math intervals and @math unknown degree- @math polynomials specifying @math over each of the intervals. We give an algorithm that draws @math samples from @math , runs in time @math , and with high probability outputs a piecewise polynomial hypothesis distribution @math that is @math -close (in total variation distance) to @math . This sample complexity is essentially optimal; we show that even for @math , any algorithm that learns an unknown @math -piecewise degree- @math probability distribution over @math to accuracy @math must use @math samples from the distribution, regardless of its running time. Our algorithm combines tools from approximation theory, uniform convergence, linear programming, and dynamic programming. We apply this general algorithm to obtain a wide range of results for many natural problems in density estimation over both continuous and discrete domains. These include state-of-the-art results for learning mixtures of log-concave distributions; mixtures of @math -modal distributions; mixtures of Monotone Hazard Rate distributions; mixtures of Poisson Binomial Distributions; mixtures of Gaussians; and mixtures of @math -monotone densities. Our general technique yields computationally efficient algorithms for all these problems, in many cases with provably optimal sample complexities (up to logarithmic factors) in all parameters.
We work in a PAC-type model similar to that of @cite_5 and to well-studied statistical frameworks for density estimation. The learning algorithm has access to i.i.d. draws from an unknown probability distribution @math . which is assumed to belong to a (known) class @math of possible target distributions. Well, we do not really need to assume this, since our results are quasi-agnostic. We explain the agnostic view of our algorithms later -- I think it's simpler to start off with this as the initial explanation. It must output a hypothesis distribution @math such that with high probability the total variation distance @math between @math and @math is at most @math (Recall that the total variation distance between two distributions @math and @math is @math for continuous distributions, and is @math for discrete distributions.) We shall be centrally concerned with obtaining learning algorithms that both use few samples and are computationally efficient.
@cite_5
2095374884
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-