CAREER: Perfect sampling techniques for high dimensional integration

职业：高维集成的完美采样技术

• 批准号: 0968878
• 负责人: Mark Huber
• 金额: $ 11.93万
• 依托单位: Claremont McKenna College
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2011-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0968878&HistoricalAwards=false
• 关键词: CAREER; Perfect; sampling; techniques; dimensional

This project will develop and analyze new computational methodologies for generating random variates from high dimensional distributions where the normalizing constant is unknown. These random variates are then used to obtain approximations for problems involving high dimensional integrations. Algorithms employing random variates are known as Monte Carlo methods. Direct methods often suffer from running times that are exponential in the dimension of the problem, whereas Monte Carlo approaches can have a polynomial or even linear running time. Applications include estimate of parameters arising from probabilistic models, approximation of exact p-values in statistics, and efficient algorithms for approximate solutions to NP complete and \#P complete problems. The new algorithms are in a class of methods known as perfect sampling algorithms. Existing perfect samplers such as Coupling From the Past have made an impact on Monte Carlo methods, but suffer from certain flaws that limit their applicability. Here new methodologies such as the Randomness Recycler and other modifications and generalizations of acceptance rejection approaches will be used to solve these problems. As part of this project, new classes will be developed and undergraduates and graduate students will have opportunities to work on problems arising in this area.Today our data collection abilities are better than at any point in history, but the time needed to analyze data can grow exponentially in the amount collected. The use of randomness in designing algorithms for analysis of data can result in enormous benefits in speed and accuracy. These techniques have been a cornerstone of computational methodology for the last fifty years. Statistics, finance, signal processing, physics, and genetics are but some of the areas that have benefited from the injection of randomness into the design of algorithms. However, existing methods are not without difficulties. A new class of algorithms called perfect sampling methods solves many of these problems in specific cases, but their applicability is limited. The goal of this project is to extend the reach of these methods by introducing new types of perfect sampling algorithms. The result will be faster, more accurate algorithms of the type used by practitioners every day in a wide variety of fields.

该项目将开发和分析新的计算方法，用于从标准化常数未知的高维分布中生成随机变量。然后使用这些随机变量来获得涉及高维积分问题的近似值。采用随机变量的算法被称为蒙特卡罗方法。直接方法的运行时间通常是问题维度的指数级，而蒙特卡罗方法的运行时间可能是多项式甚至线性。应用包括由概率模型引起的参数估计，统计中精确P值的近似值，以及NP完全和\#P完全问题近似解的有效算法。新算法属于一类被称为完美抽样算法的方法。现有的完美采样器，如过去的耦合，对蒙特卡罗方法产生了影响，但存在某些缺陷，限制了它们的适用性。在这里，新的方法，如随机回收和其他修改和推广的接受拒绝方法将被用来解决这些问题。作为该项目的一部分，将开设新的课程，本科生和研究生将有机会研究这一领域出现的问题。今天，我们的数据收集能力比历史上任何时候都要好，但分析数据所需的时间也会以指数级增长。在设计数据分析算法时使用随机性可以在速度和准确性方面带来巨大的好处。在过去的50年里，这些技术一直是计算方法的基石。统计学、金融学、信号处理、物理学和遗传学只是从将随机性注入算法设计中受益的一些领域。然而，现有的方法并非没有困难。一种称为完美抽样方法的新算法在特定情况下解决了许多这些问题，但它们的适用性有限。这个项目的目标是通过引入新型的完美采样算法来扩展这些方法的范围。结果将是更快、更准确的算法，这种算法每天都在各种领域被从业者使用。