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.