EAGER: An Exploratory System for Inverse Parametric Optimization

也许科学中最普遍的场景是用可测量的数据重建一个不能直接观察到的现象。例如，在生物学中，当计算同源蛋白质的进化排列，预测折叠RNA分子的二级结构，推断一组分类群的系统发育，恢复一组基因的调控网络，或组装基因组的DNA序列时，这种情况就会发生。这些任务几乎总是建模为优化问题，其中最优解旨在对应于正确的重建。在任何这样的模型中，一个至关重要的因素是目标函数，它的作用是选择出正确的解决方案，使目标函数最大化或最小化。该目标函数通常来自一系列参数化函数，模型的正确性可能严重依赖于函数参数值的选择。在实践中，如何确定模型参数的正确值的问题既困难又普遍存在：更好地反映潜在生物学的改进模型有许多参数，但除非将其参数设置为正确的值，否则结果会更差，然而，费力地探索高维参数空间以找到正确的设置很快就变得不可能。该团队希望在逆参数优化领域实现一种算法的新发现，该算法可以有效地学习任何线性问题的正确参数值，例如所提到的那些生物学问题。该系统易于生成具有可优化线性目标函数的逆最短路径、逆生成树、最大流、最大匹配和最大分支的高效软件，为众多计算机科学应用提供了高效的模型学习。我们提出的逆参数优化在计算机科学和计算生物学中具有极其广泛的科学影响，因为我们的技术有效地解决了具有线性目标函数的任何问题的逆优化。PI还将创建一门新的综合课程，作为新的跨学科学位课程的组成部分。

Perhaps the most prevalent scenario in science in general is reconstructing a phenomenon that is not directly observable using the data that can be measured. In biology, for example, this occurs when computing an evolutionary alignment of homologous proteins, predicting the secondary structure of a folded RNA molecule, inferring a phylogeny for a collection of taxa, recovering the regulatory network for a set of genes, or assembling the DNA sequence for a genome. These tasks are almost always modeled as optimization problems, where the optimal solution is intended to correspond to the correct reconstruction. A crucial ingredient in any such model is the objective function, whose role is to select out the correct solution as one that maximizes or minimizes the objective function. This objective function usually comes from a family of parameterized functions, and the correctness of the model can critically depend on the choice of parameter values for the function. In practice, the question of how to determine the right values for a model's parameters is both difficult and ubiquitous: improved models that better reflect the underlying biology have many parameters, but yield worse results unless their parameters are set to correct values, yet painstakingly exploring the high-dimensional parameter space to find a correct setting quickly becomes impossible. The team is looking to implement new finding of an algorithm in the area of inverse parametric optimization that can efficiently learn correct parameter values for any linear problem, such as those biology problems noted. The system readily yields efficient software for inverse shortest paths, inverse spanning trees, maximum flow, maximum matching and maximum branching, all of which have linear objective function can optimized, enabling efficient model learning for a multitude of computer science applications.The proposed work on inverse parametric optimization has extremely broad scientific impact in computer science and computational biology, as our techniques efficiently solve inverse optimization for any problem with a linear objective function. The PI will also create a new combined course that is an integral part of a new interdisciplinary degree program.