Computational Learning

Santosh Venkatesh

Computational Learning Theory
The complexity of learning has attracted substantial interest in recent years and diverse questions in this burgeoning area are being investigated ranging from an information-theoretic characterization of the learning process to the development of algorithms for learning in particular structures.

Randomized Algorithms: Learning in discrete structures, such as weight-constrained neural networks, may be intractable in the worst case, but nevertheless be tractable on average. The focus is on the development of efficient randomized procedures which reduce the average time complexity of learning.

Pattern Recognition: Classical paradigms in pattern recognition use labeled examples with data labeled according to the pattern class of origin. While many learning procedures are provably efficient in the limit of an infinite number of examples, there is a relative paucity of results on their finite-sample performance. Recent collaborative work with faculty at the University of Vermont and California Institute of Technology has focused on the classical nearest neighbor algorithm for pattern classification to characterize the intrinsic information-theoretic limitations caused by finite-sample effects.

On another tack, while the classical learning paradigms utilize labeled examples, in practice, unlabeled or unidentified data are frequently more abundant and cheaper to acquire. Recent investigations have been directed toward characterizing the information content of labeled and unlabeled examples and identifying mechanisms by which expensive labeled examples can be traded off for (a large number of) inexpensive unlabeled examples. In this context, it is also sought to quantify the importance of side information to the learning process.

Learning Complexity and Regularization: Given a finite amount of data, how does one determine the computational model or network that generated it? Using new methods in statistics, investigations in progress seek to determine how to optimally fit models to data and how to determine the optimal duration of training.

Applications: Learning theory has a variety of applications in pattern classification, game theory, decision theory, finance, and econometrics. A typical application under investigation in finance casts the auditing and accounting problems in a learning setting and seeks to provide a definitive answer to the question, Should auditors be responsible for detecting management fraud? This problem was motivated by the recent savings and loan association debacle.