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

构建能够从实例中学习的机器是一个复杂的、跨学科的问题，涵盖了广泛的科学努力。学习的核心问题是理解在何种条件下，系统被训练从有限的一组示例中执行任务，并将其行为推广到以前未见过的示例中。这个问题与许多研究领域相关，包括认识论（理论如何从实验数据中得出？）、认知科学、统计分析、机器感知、数据挖掘、生物信息学、时间序列预测，以及许多其他必须从经验数据中得出规律和知识的领域。最常见的设置是监督模式识别问题：找到一个函数，该函数可以从具有已知类别的训练集示例中将未知对象分类。统计学习理论在过去几十年的发展为保证其泛化提供了必要和充分的条件。学习算法通常分为线性和非线性参数化体系结构。近年来最成功的两种线性机器，支持向量机和Boosting，都具有很好的泛化界限。它们已经成为许多应用的最先进技术，特别是那些维度非常大的应用。另一方面，非线性机器（如多层网络、hmm、图形模型等）在理论上没有很好地表征。这个项目的第一个目标是获得更好的泛化边界，目标是产生更好的学习算法（线性和非线性），更严格地遵循SLT框架。第二个目标是了解非线性机器泛化的条件。第三个目标是定义和研究新的推理模式，如在线学习（其中示例被一个接一个地处理）和转换推理（其中测试示例在训练期间可用），它们超越了通常的归纳演绎框架，并找到实现这些新推理模式的新学习算法（线性和非线性）。新的算法和架构将应用于一些最具挑战性和最有用的机器学习应用领域，可能包括生物信息学、机器视觉和信息检索。

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 otherdomains 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.