Machine Learning Department
School of Computer Science, Carnegie Mellon University


Mathematical Theories of Interation with Oracles

Liu Yang

October 2013

Ph.D. Thesis


Keywords: Property Testing, Active Learning, Computational Learning Theory, Learning DNF, Statistical Learning Theory, Transfer Learning, Prior Estimation, Bayesian Theory, Surrogate Losses, Preference Elicitation, Concept Drift, Algorithmic Mechanism Design, Economies of Scale

The key insight underlying this thesis is that the right kind of interaction is the key to making the intractable tractable. This work specifically investigates this insight in the context of learning theory. While much of the learning theory literature has traditionally focused on protocols that are either non-interactive or involving unrealistically strong forms of interaction, there have recently been several exciting advances in the design and analysis of methods for realistic interactive learning protocols.

Perhaps one of the most interesting of these is active learning. In active learning, a learning algorithm is given access to a large pool of unlabeled examples, and is allowed to sequentially request their labels so as to learn how to accurately predict the labels of new examples. This thesis contains a number of interesting advances in our understanding of the capabilities of active learning methods. Specifically, I summarize the main contributions below.

335 pages

SCS Technical Report Collection
School of Computer Science