AF: Small: Identifying sampling problems with efficient algorithms

AF：小：用高效算法识别采样问题

• 批准号: 1318374
• 负责人: Daniel Stefankovic
• 金额: $ 39.97万
• 依托单位: University of Rochester
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1318374&HistoricalAwards=false
• 关键词: AF; Small; Identifying; sampling; problems

Sampling problems are fundamental in many areas of science and engineering, for example, statistics, artificial intelligence (machine learning and vision), and biology (phylogeny). Efficiency of sampling has impact on other important algorithms, for example, the speed of statistical tests and the reliability of estimators and classifiers. This project seeks to characterize combinatorial problems that admit efficient sampling algorithms. The research under this award addresses both sides of the characterization for a broad class of ubiquitous graphical models: 1) complexity theoretic obstacles to efficient sampling and 2) efficient sampling algorithms.Recent results established a useful characterization for antiferromagnetic 2-spin models (for example, weighted independent sets and Ising model) in terms of the behavior of the model on regular trees. This created a connection to problems and techniques studied in the statistical physics community. This project aims to use the connection to the statistical physics and its techniques (for example, belief propagation recurrences) to generalize the characterization to models with more than two spins (multi-spin models, such as the Potts model, frequently occur in the applications). As a first step towards this generalization a relation between the efficiency of commonly used Markov chains (Glauber dynamics, Swendsen-Wang algorithm) and the behavior of the models on regular trees will be explored. Beside Markov chains the PI will also investigate other approaches to sampling problems (for example, dynamic programming and utilizing strong spatial mixing).The product of the research will be efficient sampling algorithms and an improved understanding of obstacles to efficient sampling. The algorithmic problems, concepts, and techniques will be transferred to both undergraduate and graduate teaching (in the form of guided problems and implementation challenges). The award will support the training of two PhD students in the area of sampling and counting algorithms at the University of Rochester.

采样问题是许多科学和工程领域的基础，例如统计学、人工智能（机器学习和视觉）和生物学（系统发育）。采样效率会影响其他重要算法，例如统计测试的速度以及估计器和分类器的可靠性。该项目旨在描述允许有效采样算法的组合问题的特征。该奖项的研究解决了一大类普遍存在的图模型的表征的两个方面：1）高效采样的复杂性理论障碍和2）高效采样算法。最近的结果根据模型在规则树上的行为建立了反铁磁双自旋模型（例如，加权独立集和伊辛模型）的有用表征。这与统计物理学界研究的问题和技术建立了联系。该项目旨在利用与统计物理及其技术（例如置信传播递归）的联系将表征推广到具有两个以上自旋的模型（多自旋模型，例如 Potts 模型，在应用中经常出现）。作为实现这一概括的第一步，我们将探讨常用马尔可夫链（Glauber 动力学、Swendsen-Wang 算法）的效率与常规树上模型的行为之间的关系。除了马尔可夫链之外，PI 还将研究解决采样问题的其他方法（例如，动态规划和利用强空间混合）。研究的产品将是高效的采样算法以及对高效采样障碍的更好理解。算法问题、概念和技术将转移到本科生和研究生教学中（以引导问题和实施挑战的形式）。该奖项将支持罗切斯特大学采样和计数算法领域的两名博士生的培训。