EAGER: Discrete Algorithms in NLP

能够理解人类语言的算法必须能够识别该语言的底层结构(例如，主语-动词-宾语)。在自然语言处理社区中开发的计算方法通常会构建特别的、一次性的算法来解决在此类任务中出现的困难的组合优化问题。大多数大型系统都是使用复杂的启发式组合来构建的，这些启发式应用试图使近似搜索技术变得更好。与此同时，算法界已经开发出可扩展的精确算法和近似算法来解决许多此类困难的组合优化问题。这一早期的探索性研究拨款调查了这两个极端之间的联系：语言处理社区和算法社区，前者具有他们需要解决的困难问题，后者具有可证明是正确的算法来解决这些困难问题。这种探索解决的最大技术挑战是如何将构建有效语言应用程序所需的统计学习算法与使高效算法成为可能的抽象类型结合起来。这个项目特别探索了“逆优化”在机器学习中的应用。例如，如果一个人可以使用一种有效的算法来解决特定的离散优化问题，那么如何学习使该特定算法尽可能高精度的参数？该项目的成功将为学习解决复杂的语言任务带来理论上原则性的、高效的算法，这些算法可以转化为下游应用，如机器翻译、自动问答和信息检索。该项目的主要技术创新是将逆优化问题与在线学习技术相结合。例如，假设最终目标是找到某个特定的结构。对这种结构的搜索通常可以被归结为一种特定形式的动态规划问题，而这又常常成为超图中的最短路径问题。因此，机器学习的挑战是学习一种模型，在该模型下，最短路径搜索的解实际上是所需的结构。从算法的角度来看，这需要找到一组输入，在这组输入下，给定的结构是最优的：反向优化。然而，一个给定的结构是最优的还不够：它还必须以一定的幅度超过所有其他(非最佳)结构。该项目将开发在线学习算法和反向优化公式的组合，以实现这种进步。

Algorithms that can understand human language must be able to recognize the underlying structure (e.g., subject-verb-object) of that language. Computational approaches developed in the natural language processing community typically have build ad hoc, one-off algorithms for solving the hard, combinatorial optimization problems that arise in such tasks. Most large-scale systems are built using complex combinations of heuristics applied to try to make approximate search techniques better. Concurrently, the algorithms community has developed scalable exact algorithms and approximation algorithms for solving many of these hard combinatorial optimization problems. This EArly Grant for Exploratory Research investigates the connection between these two extremes: the language processing community with the hard problems they need solved, and the algorithms community with the provably correct algorithms for solving such hard problems. The biggest technical challenge this exploration addresses is how to couple the statistical learning algorithms necessary to build effective language applications with the types of abstractions that make efficient algorithms possible. In particular, this project explores the application of "inverse optimization" to machine learning. For example, if one has access to an efficient algorithm for solving a particular discrete optimization problem, how can one learn parameters that make that particular algorithm as high accuracy as possible? Success in this project will give rise to theoretically principled, efficient algorithms for learning to solve complex linguistic tasks, which can transform to downstream applications like machine translation, automatic question answering and information retrieval.This project's main technical innovation is the coupling of "inverse optimization" problems with online learning techniques. For instance, suppose that the end goal is to find some particular structure. The search for this structure can often be cast as a particular form of dynamic programming problem, which in turn often becomes a shortest path problem in a hypergraph. The machine learning challenge then is to learn a model under which the solution to this shortest path search is actually the desired structure. From an algorithmic perspective, this requires finding a set of inputs under which a given structure is optimal: inverse optimization. However, it is not enough for a given structure to be optimal: it must also beat all other (non-optimal) structures by some given margin. This project will develop a combination of online learning algorithms and inverse optimization formulations that enable such advances.