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.