ITR: Collaborative Research: New Directions in Predictive Learning: Rigorous Learning Machines

Princeton University, Princeton NJ

Investigators

Abstract

Constructing machines capable of learning from examples is a complex, cross-disciplinary problem that spans a wide spectrum of scientific endeavor. The central issue of learning is to understand the conditions under which a system trained to perform a task from a finite set of examples can generalize its behavior to previously unseen examples. This question is relevant to many areas of research, including epistemology (how can theories be derived from experimental data?), cognitive science, statistical analysis, machine perception, data mining, bioinformatics, time series prediction, and many other domains where laws and knowledge must be derived from empirical data. The most common setting is the supervised pattern recognition problem: find a function that can classify unknown objects into categories from a training set of examples with known categories. The development of Statistical Learning Theory over the last few decades has provided necessary and sufficient conditions for ensuring generalization. Learning algorithms are often categorized into linearly and non-linearly parameterized architectures. Two of the most successful linear machines of the last few years, Support Vector Machines and Boosting, possess good generalization bounds. They have become the state-of-the-art for many applications, particularly those where the dimensionality is very large. On the other hand, non-linear machines (such as multilayer nets, HMMs, graphical models, and many others) are not as well characterized theoretically. The first goal of this project will be to obtain better generalization bounds with the goal of producing better learning algorithms (linear and non-linear) that follow the SLT framework more rigorously. The second goal will be to understand the conditions under which non-linear machines generalize. A third goal will be to define and study new modes of inference such as on-line learning (in which examples are processed one by one) and transductive inference (in which test examples are available during training) that go beyond the usual inductive-deductive framework, and to find new learning algorithms (linear and non-linear) that implement those new modes of inference. The new algorithms and architectures will be applied to some of the most challenging and useful application domains of machine learning, possibly including bio-informatics, machine vision and information retrieval.