Learning from Subsampled Data: Active and Randomized Strategies

In modern statistical applications, we are often faced with situationswhere there is either too little or too much data. Both extremes canbe troublesome: Interesting models can only be learnt when sufficientamounts of data are available, yet these models tend to becomeintractable when data is abundant. An important thread of researchaddresses these difficulties by subsampling the data prior to learninga model. Subsampling can be active (i.e. active learning) orrandomized. While both of these techniques have a long history, adirect application to novel situations is in many casesproblematic. This dissertation addresses some of these issues.We begin with an active learning strategy for spectral clustering whenthe cost of assessing individual similarities is substantial orprohibitive. We give an active spectral clustering algorithm whichiteratively adds similarities based on information gleaned from apartial clustering and which improves over common alternatives.Next, we consider active learning in Bayesian models. Complex Bayesianmodels often require an MCMC-based method for inference, which makes anaive application of common active learning strategiesintractable. We propose an approximate active learning method whichreuses samples from an existing MCMC chain in order to speed up thecomputations.Our third contribution looks at the effects of randomized subsamplingon Gaussian process models that make predictions about outliers andrare events. Randomized subsampling risks making outliers evenrarer, which, in the context of Gaussian process models, can lead tooverfitting. We show that Heavy-tailed stochastic processes can beused to improve robustness of regression and classification estimatorsto such outliers by selectively shrinking them more strongly in sparseregions than in dense regions.Finally, we turn to a theoretical evaluation of randomized subsamplingfor the purpose of inferring rankings of objects. We present twosimple algorithms that predict a total order over n objects from arandomized subsample of binary comparisons. In expectation, thealgorithms match an &Omega(n) lower bound on the sample complexityfor predicting a permutation with fixed expected Kendall taudistance. Furthermore, we show that given O(nlog(n)) samples, onealgorithm recovers the true ranking with uniform quality, while theother predicts the ranking more accurately near the top than thebottom. Due to their simple form, the algorithms can be easilyextended to online and distributed settings