Robert E. Schapire - US grants

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.

Computational Game Theory is a rapidly emerging discipline at the intersection of computer science, economics, and related fields. It is becoming a fundamental tool for understanding and designing complex multiagent environments such as the Internet, systems of autonomous agents, and electronic economies. The objective of this program is the development of powerful new representations for complex game-theoretic and economic reasoning problems, and strategic learning algorithms for adjusting their parameters.

Special emphasis is being given to models permitting the specification of natural network structure in the interactions within a large population of players, and models generalizing the spirit of financial markets, in which interactions take place via global intermediate quantities. Powerful recent machine learning methods such as boosting and exponential updates are also being applied to the more subtle and complex setting of learning in games.

The expected results of the program are a rich set of new modeling methods for game-theoretic applications, and computationally efficient algorithms for reasoning with them, including the computation of Nash, correlated, and other equilibria, as well as efficient learning methods with known convergence properties. Special emphasis will be given to formal analysis, and the resulting methods will provide a new toolbox for researchers in economics, social science, evolutionary biology, and other fields in which game-theoretic approaches are common. The findings of the program will be widely disseminated through international conferences and journals, as well as more specialized workshops deliberately bringing together researchers from the different relevant disciplines.

WordNet is an important lexical resource for research in areas including NLP and AI. This project initiates the development of a radically enhanced version of WordNet. Constructing WordNet+ involves a novel combination of empirical methods: human annotation, corpus analysis, and machine learning. WordNet+ specifically addresses some of WordNet's limited ability to identify word senses, stemming from the sparsity of Boolean arcs among sets of synonymous words ("synsets"). First, quantified, oriented arcs are to be added among a core set of 5,000 synsets. These arcs reflect evocation--the extent to which the meaning of one synset brings to mind another. Following the selection of the core synsets, a random subset of 250,000 arcs are to be elicited from annotators. The annotators, trained and tested for inter- and intra-reliability, record the strength of their mental associations using a specially designed and tested interface. The remaining arcs are to be extrapolated from the manually obtained arcs using machine learning algorithms.

All results will be made available to the research community: the core concepts, the indirect co-occurrence matrices, and all available ratings. Given WordNet's past contributions to a number of diverse disciplines, the initial stages of the construction of this research tool should stimulate great interest and have a significant impact on related work.

ABSTRACT

The objective of the proposed research is to develop a general and robust machine learning system for integrated analysis of high-throughput biological data for the purpose of prediction of gene function and protein-protein interactions. Achieving this goal requires addressing multiple challenges that include data heterogeneity, variable data quality, high noise levels in data, and a paucity of training samples. These challenges have prevented the successful application of traditional machine learning methods to diverse biological data. The research team will leverage diverse bioinformatics, machine learning, and biology expertise of the co-PIs and collaborators to develop accurate and effective approaches optimized for integrated analysis of genomic data. For prediction of protein-protein interactions, this investigation will focus on Bayesian approaches based on successful preliminary research. For gene function prediction, the focus will be on developing novel machine learning methods. These learning methods will use heterogeneous biological data as well as protein-protein interactions predicted by the system. The proposed research will lead to development of a general bioinformatics system that will utilize diverse large-scale biological data, including gene expression microarrays, physical and genetic interactions datasets, sequence and literature data, to produce an accurate map of protein-protein interactions and predictions of function for each of the proteins. This system will address the critical need in genomics to extract accurate biological information from disparate high-throughput
data sources, enabling the first step in accurate and comprehensive study of cellular processes
on a whole-genome level. Additionally, the proposed analysis will provide genomics researchers with quantitative rankings of the relative reliability of high-throughput experimental technologies, thereby providing biologists with data on which high-throughput technologies are more accurate than others. A significant advantage of this plan is that the research team will work closely with biologists to evaluate the predictions and feed the information back into the investigation to further improve the system and the quality of the resulting predictions.

The proposed system will provide predictions that will drive biological experimentation, enabling genome-wide annotation of unknown genes. The system will be publicly available to genomics researchers through its integration with the Saccharomyces Genome Database, a model organism database for yeast, and also via distribution of this integrated framework to other model databases. The interdisciplinary approach of this proposal will further the impact of advanced
computer science on biology and will precipitate further interactions between the two fields, both through research and through interdisciplinary education.

Boosting is a machine-learning method based on combining many
carefully trained weak prediction rules into a single, highly accurate
classifier. Boosting has both a rich theory and a record of empirical
success, for instance, to face detection and spoken-dialogue systems.

The theory of boosting is broadly connected to other research fields,
but has only been fully developed for the simplest learning problems.
Nevertheless, in practice, boosting is commonly applied in settings
where the theory lags well behind. We do not know if such practical
methods are truly best possible; even for binary classification, it is
not clear how to best exploit what is known about how boosting
operates. New challenges will demand an even greater widening of the
foundations of boosting.

The goal of this project is to develop broad theoretical insights and
versatile algorithmic principles. The aim is to study
game-theoretically how to design the most efficient and effective
boosting algorithms possible.

Research on boosting is spread over many years. across multiple
publications and disciplines. To organize this body of work, a
significant activity of this project is the completion of a book on
boosting which will provide a valuable resource for students and
researchers of diverse backgrounds and interests.

Boosting has historically had a major impact on areas outside machine
learning, such as statistics, computer vision, and speech and language
processing. Thus, there is a strong potential for work at its
foundations to have a broad impact on these other research and
application areas as well.