提出一种高效近似计算DNF模型计数的新算法，可处理百万变量级问题。
Scalable Algorithms for Approximate DNF Model Counting
- 基于自适应停止规则和短路求值的蒙特卡洛方法
- 理论证明达到PAC学习界，效率优于已有方法
- 实测性能提升数个数量级，适合大规模应用
DNF公式模型计数在概率推理和网络可靠性等应用中至关重要，常用于概率数据库的查询评估。由于精确计数计算上不可行，已有研究提出多种近似算法，包括蒙特卡洛方法（如Karp-Luby-Madras, 1989）、基于哈希的方法（Soos et al., 2023）以及神经网络启发的启发式近似（Abboud, Ceylan, & Lukasiewicz, 2020）。本文提出一种新的蒙特卡洛方法，结合自适应停止规则与短路公式求值。理论证明该方法满足概率近似正确（PAC）学习界，且渐近效率更高。实验表明，其性能相比先前算法提升数个数量级，可扩展至包含数百万变量的大规模问题。
原文摘要 · Abstract (English)
Model counting of Disjunctive Normal Form (DNF) formulas is a critical problem in applications such as probabilistic inference and network reliability. For example, it is often used for query evaluation in probabilistic databases. Due to the computational intractability of exact DNF counting, there has been a line of research into a variety of approximation algorithms. These include Monte Carlo approaches such as the classical algorithms of Karp, Luby, and Madras (1989), as well as methods based on hashing (Soos et al. 2023), and heuristic approximations based on Neural Nets (Abboud, Ceylan, and Lukasiewicz 2020). We develop a new Monte Carlo approach with an adaptive stopping rule and short-circuit formula evaluation. We prove it achieves Probably Approximately Correct (PAC) learning bounds and is asymptotically more efficient than the previous methods. We also show experimentally that it out-performs prior algorithms by orders of magnitude, and can scale to much larger problems with millions of variables.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。