Algorithmic approaches to statistical questions
Christos H. Papadimitriou, Gregory Valiant · 2012
In this dissertation, we apply the computational perspective to three basic statistical questions which underlie and abstract several of the challenges encountered in the analysis of today's large datasets. Estimating Statistical Properties Given a sample drawn from an unknown distribution, and a specific statistical property of the distribution that we hope to estimate, how should one compute that estimate, and what sample size is necessary to guarantee that with high probability, the computed estimate is accurate? We focus on a large and natural class of properties, which includes the number of distinct elements, entropy, and distance metrics between pairs of distributions, including total variational distance (also known as statistical distance or e1 distance). Such properties are easy to estimate if the sample size is large in comparison to the size or complexity of the underlying distribution, but what can be done given relatively few samples? We show that sublinear sample estimation is possible: for any constant e > 0, the above estimation tasks can be accomplished using samples of size O nlogn , with probability of success 1 – o(1). Additionally, we prove some results about the algorithmic structure of optimal estimators, and provide experimental evidence suggesting that our estimators perform very well in practice. Complementing these positive results, we prove matching information theoretic lower bounds, establishing the sample complexity of these tasks up to constant factors. Previously, no explicit sublinear sample estimators had been described for any of these tasks. Finding Correlations and Identifying Relevant Variables: Perhaps the most basic type of structure that can be present in a dataset is correlation. How much computation is required to find correlated variables? One can certainly brute-force search through all pairs of variables, and for each pair, the correlation can be estimated very efficiently. But is there a sub-quadratic time algorithm for finding correlated variables? More generally, suppose one has a data set where each data sample has a label which is given as some function of a small number of the variables. If we have n total variables, perhaps there is a small number, k = 3, 4, 5,..., of relevant variables which can be used to predict the labels. Such a function is termed a k-junta . How quickly can one find this set of k relevant variables? As above, one could simply perform a brute-force search over all possible subsets of size k, taking time roughly O(nk). Can one find the set of relevant variables significantly more efficiently? Learning Mixtures of Gaussians: A sample from a mixture model (with, for example, two components) is generated via the following process: for each data point, with some probability, w1, the point is drawn from one distribution, p1, and with the remaining probability, 1-w1 the point is drawn from a second distribution p2. Supposing one is given a large sample from such a mixture of distributions, can one efficiently deduce the components, p1 and p2 of the mixture? Can one accurately cluster the sample points according to the distribution from which they originated? In the special case in which each component, p1, p 2 is a Gaussian distribution, this is the problem of learning a Gaussian mixture model, and is, perhaps, the most natural (and practically relevant) starting point for tackling the question of recovering mixtures of more general families of distributions. We obtain a basic handle on the sample and computational complexity of this problem, and describe an algorithm which, given a sample from a GMM with any constant number of components, provably returns accurate estimates of the components, with runtime and sample size polynomial in the relevant parameters—the dimension of the space, and the inverse of the desired accuracy of the recovered components. Previously, no such algorithm was known, even in the special case of univariate mixtures with just two components. (Abstract shortened by UMI.)