RI: Small: Integrating Learning and Search for Structured Prediction

机器学习领域在解决分类问题方面非常成功，其中输入是固定大小的特征向量，输出是少量固定数量的类。然而，自然语言理解和视觉场景解释等许多应用涉及具有丰富内部结构的可变大小的输入和输出。本项目将研究此类结构化预测问题的新方法。例如，输入可能是自然语言文档或视觉场景，输出可能是其语义内容的正式表示，例如推断或观察到的实体以及它们之间的关系。大多数结构化预测方法学习成本函数来对潜在的结构化输出进行评分。为给定的结构化输入寻找正确的输出包括推断成本最低的输出。不幸的是，这种推理的计算成本对于表达成本函数来说是令人望而却步的；这迫使使用更简单的成本函数或近似推理。在任何一种情况下，预测的准确性都会受到影响。当前的项目旨在通过在一个新的框架中集成学习和搜索来解决这个问题，该框架允许开发用于结构化预测的新算法。特别是，该项目将解决三个主题：(1)通过模仿训练数据上的最优限时搜索过程的决策，将开发用于成本函数学习的通用框架。这将允许广泛的最先进的搜索算法被用于结构化预测。(2)将发展一种理论和框架来学习如何通过将搜索压缩到更短的时间框架内来加快对全局最优的搜索。这将允许学习不仅解决准确性问题，而且解决预测器的计算效率问题。(3)代价函数学习和加速学习都将在多种搜索算法中实例化，并在不同的应用中进行评估。该项目旨在为各种具有广泛影响的应用做出贡献，包括自然语言理解、视频对象跟踪和个性化调度。用于学习搜索和结构化预测的框架、算法和测试平台将集成到Weka工具箱中，以便它们可以轻松地与不同的监督学习算法相结合，并在进一步的研究中使用。结果和基准域名将通过该项目的网页公开发布。俄勒冈州立大学将以本提案为主题开设一门专题研究生课程。

The field of machine learning is extremely successful in solving classification problems where the inputs are fixed size feature vectors and the outputs are a small fixed number of classes. However, many applications such as natural language understanding and visual scene interpretation involve inputs and outputs of variable size that have rich internal structure. This project will study new approaches for such structured prediction problems. For example, the inputs may be natural language documents or visual scenes and the outputs may be formal representations of their semantic content, such as entities inferred or observed and the relationships between them. Most approaches to structured prediction learn a cost function to score potential structured outputs. Finding the correct output for the given structured input then consists of inferring the least cost output. Unfortunately, the computational cost of this inference is prohibitive for expressive cost functions; this forces the use of either simpler cost functions or approximate inference. In either case, prediction accuracy can suffer.The current project aims to address this issue by integrating learning and search in a new framework that allows for the development of novel algorithms for structured prediction. In particular, this project will address three topics: (1) A generic framework will be developed for cost function learning by imitating the decisions of an optimal time-bounded search procedure on the training data. This will allow for a wide range of state-of-the-art search algorithms to be leveraged for structured prediction. (2) A theory and framework will be developed to learn to speed up the search for a global optimum by compressing the search into a shorter time-frame. This will allow for learning to address not only accuracy but also the computational efficiency of the predictor. (3) Both the cost function learning and speedup learning will be instantiated in multiple search algorithms and evaluated in different applications.The project seeks to make contributions to a variety of applications of broad impact including natural language understanding, tracking objects in video, and personalized scheduling. The frameworks, algorithms and testbeds for learning to search and structured prediction will be integrated into the Weka tool-box so that they can be easily combined with different supervised learning algorithms and used in further research. The results and benchmark domains will be publicly distributed through the project's web pages. A special topics graduate course will be taught on the topic of this proposal at Oregon State University.