Machine learning has become one of the most active and exciting areas of computer science research, in large part because of its wide-spread applicability to problems as diverse as natural language processing, speech recognition, spam detection, search, computer vision, gene discovery, medical diagnosis, and robotics. At the same time, the growing popularity of the Internet and social networking sites like Facebook has led to the availability of novel sources of data on the preferences, behavior, and beliefs of massive populations of users. Naturally, both researchers and engineers are eager to apply techniques from machine learning in order to aggregate and make sense of this wealth of collective information. However, traditional theories of learning fail to capture the complex issues that arise in such settings, and as a result, many of the techniques currently employed are ad hoc and not well understood. The goal of this dissertation is to narrow this gap between theory and practice. To that end, we present a series of new learning models and algorithms designed to address and illuminate problems commonly faced when aggregating local information across large population. We build on the foundations of learning theory to examine the fundamental trade-offs that arise when aggregating preference data across many similar users to learn a model of a single user's tastes. We introduce and analyze a computational theory of learning from collective behavior, in which the goal of the algorithm is to accurately model and predict the future group behavior of a large population. We develop a forecaster that is guaranteed to perform reasonably well compared to best expert in a population but simultaneously never any worse than the average. Finally, we investigate the computational complexity of pricing in prediction markets, betting markets designed to aggregate individuals' opinions about the likelihood of future events, and propose an approximation technique based on the previously unexplored connection between prediction market prices and learning from expert advice.
