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 informationtheoretic
characterization of the learning process to the development of
algorithms for learning in particular structures.
Randomized Algorithms: Learning in
discrete structures, such as weightconstrained 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 finitesample 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 informationtheoretic limitations caused by
finitesample 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.
