III: Small: Sampling Techniques in Computational Logic

III：小：计算逻辑中的采样技术

• 批准号: 1527668
• 负责人: Moshe Vardi
• 金额: $ 40.73万
• 依托单位: William Marsh Rice University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1527668&HistoricalAwards=false
• 关键词: III; Small; Sampling; Techniques; Computational

Constrained sampling and counting are two fundamental problems in data analysis. In constrained sampling the task is to sample randomly from among possible solutions to a Boolean formula. A related problem is that of constrained counting, determining the number of possible solutions to a Boolean formula. These problems have applications in machine learning, probabilistic reasoning, and planning, among other areas In particular, te project looks at the electronic-design-automation industry to determine what practical solutions to the problems require. Both problems can be viewed as aspects of one of the most fundamental problems in artificial intelligence, which is to understand the structure of the solution space of a given set of constraints.This project focuses on the development of new algorithmic techniques for constrained sampling and counting, based on a universal hashing - a classical algorithmic technique in theoretical computer science. Many of the ideas underlying the proposed approach go back to the 1980s, but they have never been reduced to practice. This project builds on recent progress in Boolean reasoning to develop methods to reduce these algorithmic ideas to practice. Methods for approximations with formal guarantees provide opportunities to scale what is fundamentally a computationally intractable problem. Pruning techniques can also reduce "waste" in hashed solutions, but introduce challenges in ensuring samples are independently distributed. This work has potential for breakthrough results in constrained sampling and counting, providing a new algorithmic toolbox in machine learning, probabilistic reasoning, and the like.

约束抽样和计数是数据分析中的两个基本问题。在约束抽样中，任务是从布尔公式的可能解中随机抽样。一个相关的问题是约束计数，确定布尔公式的可能解决方案的数量。 这些问题在机器学习、概率推理和规划等领域都有应用。特别是，该项目着眼于电子设计自动化行业，以确定这些问题需要哪些实用的解决方案。这两个问题都可以看作是人工智能最基本问题之一的一个方面，即理解给定一组约束的解空间的结构。该项目侧重于开发基于通用散列（理论计算机科学中的经典算法技术）的约束采样和计数的新算法技术。所提出的方法的许多基本思想可以追溯到20世纪80年代，但从未付诸实践。这个项目建立在布尔推理的最新进展，以开发方法来减少这些算法的想法，以实践。方法近似与正式的保证提供了机会，规模从根本上是一个计算上棘手的问题。修剪技术也可以减少散列解决方案中的“浪费”，但在确保样本独立分布方面存在挑战。这项工作有可能在约束采样和计数方面取得突破性成果，为机器学习，概率推理等提供新的算法工具箱。