Divide and Conquer Methods for Machine Learning

该项目将开发机器学习算法、原型工具和支持理论，以解决复杂的机器学习问题。现有的理论和算法都集中在学习简单的分类器上，这些分类器对一个对象进行描述，并将其分配到少数几个类中的一个（例如，取一个字符的图像并将其分类为字母表中的26个字母之一）。科学和工业中的新兴应用需要学习从复杂输入（例如，2D地图，时间序列和字符串）映射到复杂输出（例如，其他2D地图，时间序列和字符串）的更复杂的功能。尽管缺乏涵盖此类情况的理论，但已经建立了许多在特定应用中工作良好的实际系统。这些系统都采用某种分而治之的方法，将输入和输出分成更小的部分（“窗口”），进行分类，然后将结果合并以产生整体解决方案。该项目将开发用于分而治之问题的机器学习的一般公式，用于解决这些问题的算法集合，以及用于通过分而治之方法解决新学习问题的原型工具包。此外，将开发理论模型来理解影响分治系统设计的权衡。由此产生的算法和理论将扩展可以通过机器学习方法解决的问题范围，并使构建新的分而治之的机器学习应用变得更容易。这将提高现有机器学习应用程序的性能，例如，在文本处理，入侵检测和传感器数据分析以发出警报。

This project will develop machine learning algorithms, prototype tools, and supporting theory for solving complex machine learning problems. Existing theory and algorithms have focused on learning simple classifiers that take a description of an object and assign it to one of a small number of classes (e.g., taking an image of a character and classifying it as one of the 26 letters of the alphabet). Emerging applications in science and industry require learning much more complex functions that map from complex inputs (e.g., 2D maps, time series, and strings) to complex outputs (e.g., other 2D maps, time series, and strings). Despite the lack of theory covering such cases, many practical systems have been built that work well in particular applications. These systems all employ some form of divide-and-conquer, where the inputs and outputs are divided into smaller pieces ("windows"), classified, and then the results are merged to produce an overall solution. This project will develop a general formulation of machine learning for divide-and-conquer problems, a collection of algorithms for solving these problems, and a prototype tool kit for solving new learning problems via the divide-and-conquer approach. In addition, theoretical models will be developed to understand the tradeoffs that affect the design of divide-and-conquer systems. The resulting algorithms and theory will extend the range of problems that can be solved via machine learning methods and make it easier to construct new divide-and-conquer machine learning applications. This will lead to improved performance of existing machine learning applications, for example, in text processing, intrusion detection, and the analysis of sensor data to signal alarms.