Sampling is a fundamental technique, and sampling without replacement is often desirable when duplicate samples are not beneficial. Within machine learning, sampling is useful for generating diverse outputs from a trained model. We present an elegant procedure for sampling without replacement from a broad class of randomized programs, including generative neural models that construct outputs sequentially. Our procedure is efficient even for exponentially-large output spaces. Unlike prior work, our approach is incremental, i.e., samples can be drawn one at a time, allowing for increased flexibility. We also present a new estimator for computing expectations from samples drawn without replacement. We show that incremental sampling without replacement is applicable to many domains, e.g., program synthesis and combinatorial optimization.
翻译:取样是一种基本技术,在重复样品不有益的情况下,取样而不替换往往比较可取。在机器学习中,取样有助于从经过训练的模型中产生各种产出。我们提出了一个优雅的取样程序,而没有从广泛的随机程序类别中取代,包括基因神经模型,这些模型按顺序构造产出。我们的取样程序甚至对指数性巨大的产出空间也是有效的。与以前的工作不同,我们的方法是递增式的,即样品可以一次抽取,这样可以增加灵活性。我们还为计算从未经更换而提取的样品的预期值提供了一个新的估计值。我们表明,没有替换的递增抽样适用于许多领域,例如方案合成和组合优化。