Learning probability distributions
Sanjoy Dasgupta, Umesh V. Vazirani · 2000
The first part of this thesis presents an algorithm which takes data from an unknown mixture of Gaussians in arbitrarily high dimension and recovers the parameters of this mixture to within the precision desired by the user. There are two restrictions on the mixture: its component Gaussians must be “well-separated” in a precise sense, and they must have a common (though of course unknown) non-singular covariance matrix. The running time of the algorithm is linear in the dimension of the data and polynomial in the number of Gaussians. This algorithm is very simple, and relies crucially upon a particular procedure for dimensionality reduction. Data from a mixture of k Gaussians are projected to a randomly chosen O(log k)-dimensional subspace, regardless of the original dimension and the number of data points, and it is shown that not only does this retain enough information for clustering, but it also causes a drastic reduction in the eccentricity of the Gaussians. Experiments are performed to illustrate some of the promise of this random projection technique. The second half of this thesis studies the problem of learning the maximum-likelihood directed probabilistic net given data. Three combinatorial optimization tasks are distinguished: SL(k), learning the optimal probabilistic net in which each node has at most k parents PT, learning the optimal polytree; and PT(k), learning the optimal polytree with an indegree bound of k. It is well-known that SL(1) is efficiently solvable while SL(2) is an NP-hard optimization problem. We demonstrate an even more damaging hardness barrier, that for some constant c > 1, unless P = NP there is no polynomial-time algorithm which can c-approximate SL(2), that is, which can consistently return a solution whose log-likelihood is within a multiplicative factor c of optimal. We show a similar hardness result for PT(2), but at the same time prove that the optimal branching (or Chow-Liu tree), which can be found efficiently, constitutes a good approximation to the optimal polytree, regardless of indegree. The ratio between their log-likelihoods cannot be bounded by an universal constant but depends upon the nature of the individual attributes. For instance, if each attribute by itself has unit entropy then the ratio is at most two. An optimal structure over n nodes can have log-likelihood anywhere in the range [−O(n), 0] and therefore this approximation result is a significant guarantee.