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.

受限的采样和计数是数据分析中的两个基本问题。在约束采样中，任务是从可能的解决方案中随机采样到布尔公式。一个相关的问题是计数的约束，确定了布尔公式的可能解决方案数量。 这些问题在机器学习，概率推理和规划中具有应用，尤其是TE项目介绍了电子设计自动化行业，以确定问题所需的实际解决方案。这两个问题都可以看作是人工智能中最根本问题之一的方面，即了解给定的约束集的解决方案空间的结构。本项目的重点是开发新的算法技术来开发用于约束采样和计数的新算法技术，基于一种普遍的哈希（一种普遍的哈希） - 一种经典的算法算法，一种经典的算法技术。拟议方法的许多想法可以追溯到1980年代，但从未降级为实践。该项目以布尔推理的最新进展为基础，以开发减少这些算法思想实践的方法。具有正式保证的近似值的方法提供了扩展从根本上进行计算上棘手的问题的机会。修剪技术还可以减少哈希解决方案中的“废物”，但在确保样品分发时引入了挑战。这项工作具有突破性的潜力导致采样和计数的约束，从而在机器学习，概率推理等方面提供了一种新的算法工具箱。