优化近似计数算法参数，提速1.6至2.4倍
Systematic Parameter Decision in Approximate Model Counting
- 将参数选择建模为可优化问题，突破传统启发式方法
- 实验显示在不同误差容忍下运行速度提升1.6到2.4倍
- 适合关注模型计数效率与理论可解释性的研究者
本文提出一种新方法，用于确定基于哈希的近似模型计数算法 $ exttt{ApproxMC}$ 的内部参数。该问题要求所选参数在保证算法概率近似正确（PAC）的前提下尽可能高效。现有方法依赖启发式策略；本文通过将 $ exttt{ApproxMC}$ 的正确性证明推广至任意参数值，将其形式化为一个优化问题。该方法分离了算法正确性与最优性的问题，避免重复的逐例论证，同时为最优性提供清晰框架。优化问题经简化后具有极简形式，支持基础搜索算法求解，并揭示参数对性能的影响机制。实验表明，使用优化参数后，最新版 $ exttt{ApproxMC}$ 的运行时间在不同误差容忍度下提升1.6至2.4倍。
原文摘要 · Abstract (English)
This paper proposes a novel approach to determining the internal parameters of the hashing-based approximate model counting algorithm $\mathsf{ApproxMC}$. In this problem, the chosen parameter values must ensure that $\mathsf{ApproxMC}$ is Probably Approximately Correct (PAC), while also making it as efficient as possible. The existing approach to this problem relies on heuristics; in this paper, we solve this problem by formulating it as an optimization problem that arises from generalizing $\mathsf{ApproxMC}$'s correctness proof to arbitrary parameter values. Our approach separates the concerns of algorithm soundness and optimality, allowing us to address the former without the need for repetitive case-by-case argumentation, while establishing a clear framework for the latter. Furthermore, after reduction, the resulting optimization problem takes on an exceptionally simple form, enabling the use of a basic search algorithm and providing insight into how parameter values affect algorithm performance. Experimental results demonstrate that our optimized parameters improve the runtime performance of the latest $\mathsf{ApproxMC}$ by a factor of 1.6 to 2.4, depending on the error tolerance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。