论文标题
测试采样器
On Testing of Samplers
论文作者
论文摘要
给定一组项目$ \ MATHCAL {F} $和权重函数$ \ MATHTT {wt}：\ Mathcal {f} \ Mapsto（0,1）$，采样的问题旨在采样与其重量成比例的项目。抽样是机器学习中的基本问题。采样对正式保证的艰巨的计算复杂性导致设计师提出基于启发式方法的技术，而该技术不存在严格的理论分析来量化生成的分布的质量。 这在设计测试方法方面构成了一个挑战，以测试下正在测试的采样器是否会根据给定的分布生成样品。直到最近，Chakraborty and Meel（2019）才设计了第一个可扩展的验证者，称为Barbarik1，在特殊情况下，当重量函数$ \ mathtt {wt} $是常数时，也就是说，当采样器应该从$ \ nathcal {f} $均匀地采样时。但是，Barbarik1中的技术无法处理一般的重量功能。 本文的主要贡献是对上述挑战的肯定答案：由barbarik1动机，但是使用不同的技术和分析，我们设计了barbarik2算法来测试采样器产生的分布是$ \ varepsilon $ close $ close $ -close还是$η$ - $ far。与黑盒抽样技术形成鲜明对比的是需要多个样本与$ | \ | \ nathcal {f} | $，barbarik2仅需要$ \ tilde {o}（tilt（\ mathtt {wt {wt}，φ），φ）^2/η（η-6 \ varepsilon）$ sampe令人满意的作业。 Barbarik2可以处理任何任意重量功能。我们提出了Barbarik2的原型实现，并使用它来测试三个最先进的采样器。
Given a set of items $\mathcal{F}$ and a weight function $\mathtt{wt}: \mathcal{F} \mapsto (0,1)$, the problem of sampling seeks to sample an item proportional to its weight. Sampling is a fundamental problem in machine learning. The daunting computational complexity of sampling with formal guarantees leads designers to propose heuristics-based techniques for which no rigorous theoretical analysis exists to quantify the quality of generated distributions. This poses a challenge in designing a testing methodology to test whether a sampler under test generates samples according to a given distribution. Only recently, Chakraborty and Meel (2019) designed the first scalable verifier, called Barbarik1, for samplers in the special case when the weight function $\mathtt{wt}$ is constant, that is, when the sampler is supposed to sample uniformly from $\mathcal{F}$ . The techniques in Barbarik1, however, fail to handle general weight functions. The primary contribution of this paper is an affirmative answer to the above challenge: motivated by Barbarik1 but using different techniques and analysis, we design Barbarik2 an algorithm to test whether the distribution generated by a sampler is $\varepsilon$-close or $η$-far from any target distribution. In contrast to black-box sampling techniques that require a number of samples proportional to $|\mathcal{F}|$ , Barbarik2 requires only $\tilde{O}(tilt(\mathtt{wt},φ)^2/η(η- 6\varepsilon)^3)$ samples, where the $tilt$ is the maximum ratio of weights of two satisfying assignments. Barbarik2 can handle any arbitrary weight function. We present a prototype implementation of Barbarik2 and use it to test three state-of-the-art samplers.
