EAGER: An Exploratory System for Inverse Parametric Optimization

EAGER：逆参数优化的探索性系统

• 批准号: 1050293
• 负责人: John Kececioglu
• 金额: $ 6万
• 依托单位: University of Arizona
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1050293&HistoricalAwards=false
• 关键词: EAGER; Exploratory; System; Inverse; Parametric

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.

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