Poster
Testing of Horn Samplers
ANSUMAN BANERJEE · Shayak Chakraborty · Sourav Chakraborty · Kuldeep S Meel · Uddalok Sarkar · Sayantan Sen
Auditorium 1 Foyer 146
[
Abstract
]
Abstract:
Sampling over combinatorial spaces is a fundamental problem in artificial intelligence with a wide variety of applications. Since state-of-the-art techniques heavily rely on heuristics whose rigorous analysis remains beyond the reach of current theoretical tools, the past few years have witnessed interest in the design of techniques to test the quality of samplers. The current state-of-the-art techniques, BarbarikBarbarik and Barbarik2Barbarik2, focuses on the cases where combinatorial spaces are encoded as Conjunctive Normal Form (CNF) formulas. While CNF is a general-purpose form, often techniques rely on exploiting specific representations to achieve speedup. Of particular interest are Horn clauses, which form the basis of the logic programming tools in AI. In this context, a natural question is whether it is possible to design a tester that can determine the correctness of a given Horn sampler. The primary contribution of this paper is an affirmative answer to the above question. We design the first tester, FlashFlash, which tests the correctness of a given Horn sampler: given a specific distribution II and parameters ηη, εε, and δδ, the tester FlashFlash correctly (with probability at least 1−δ1−δ) distinguishes whether the underlying distribution of the Horn-sampler is εε-close'' to II or ηη-far'' from II by sampling only ˜O(tilt3/(η−ε)4)˜O(tilt3/(η−ε)4) samples from the Horn-sampler, where the tilttilt is the ratio of the maximum and the minimum (non-zero) probability masses of II. We also provide a prototype implementation of FlashFlash and test three state-of-the-art samplers on a set of benchmarks.
Live content is unavailable. Log in and register to view live content