Off-the-shelf Learning Algorithms for Structural Supervised Learning

该项目将开发机器学习算法，软件工具和支持理论，以解决结构监督学习问题。现有的理论和算法集中在从训练示例中学习未知函数，其中未知函数从特征向量映射到少量类中的一个。科学和工业中的新兴应用需要学习从复杂输入空间映射的复杂得多的函数（例如，2-维映射、时间序列、序列和图形）到复杂的输出空间（例如，其它二维图、时间序列、序列和图形）。示例包括检测交易序列中的欺诈性交易、分配词性（名词、动词等）、对句子中的每个单词进行分类，识别DNA序列中的基因，并为遥感图像中的每个像素分配土地覆盖类别。然而，现有的统计、机器学习和数据挖掘软件包并没有为这些复杂的任务提供任何支持，也没有开发出机器学习理论来分析这些任务。本项目将开发结构监督学习（SSL）问题的一般公式，设计和测试解决SSL问题的算法集合，并开发一个原型系统，为从业者提供“现成”的工具来开发SSL应用程序。该项目将产生广泛的影响。首先，社会面临的许多重要问题都涉及在序列、空间或结构数据中发现模式。这些挑战包括：（a）执法挑战，如检测信用卡盗窃和医疗保险欺诈;（B）安全挑战，如检测恐怖分子企图用集装箱发送炸弹;（c）健康和安全应用，如根据急诊室入院的时间和空间数据检测疾病爆发;以及（d）生态应用，例如通过分析遥感图像序列来监测生态系统的健康状况。在这项工作中开发的工具和技术可以解决所有这些问题。第二，该项目将培训研究生，包括妇女（在计算机科学领域人数不足），并为她们提供参加科学会议和讲习班的机会。

This project will develop machine learning algorithms, software tools, and supporting theory for solving structural supervised learning problems. Existing theory and algorithms have focused on learning an unknown function from training examples, where the unknown function maps from a feature vector to one of a small number of classes. Emerging applications in science and industry require learning much more complex functions that map from complex input spaces (e.g., 2-dimensional maps, time series, sequences, and graphs) to complex output spaces (e.g., other 2-dimensional maps, time series, sequences, and graphs). Examples include detecting fraudulent transactions in a transaction sequence, assigning parts of speech (noun, verb, etc.) to each word in a sentence, identifying genes in DNA sequences, and assigning a land cover class to each pixel in a remote-sensed image. However, existing statistical, machine learning, and data mining packages do not provide any support for these complex tasks, nor has machine learning theory been developed to analyze these tasks. This project will develop a general formulation of the structural supervised learning (SSL) problem, design and test a collection of algorithms for solving SSL problems, and develop a prototype system that will provide "off -the-shelf " tools for practitioners to develop SSL applications. This project will have several broader impacts. First, many important problems confronting society involve finding patterns in sequential, spatial, or structural data. These include (a) law enforcement challenges, such as detecting theft of credit cards and health insurance fraud, (b) security challenges, such as detecting attempts by terrorists to send bombs in shipping containers, (c) health and safety applications, such as detecting outbreaks of diseases from temporal and spatial data about emergency room admissions, and (d) ecological applications, such as monitoring the health of ecosystems by analyzing sequences of remote-sensed images. The tools and techniques developed in this work can address all of these problems. Second, the project will train graduate students, including women (who are underrepresented in computer science), and provide them opportunities to attend scientific conferences and workshops.