论文标题
使用重量查询近似目标分布
Approximating a Target Distribution using Weight Queries
论文作者
论文摘要
我们考虑了一个新的挑战：近似分布而无需从该分布中随机采样的能力。我们研究如何使用 *重量查询 *获得这样的近似值。给定一些示例的数据集，权重查询将其中一个示例提交给Oracle，该示例根据目标分布返回类似于提出的示例的示例的概率。例如，该甲骨文可以表示将查询计数到目标总体数据库，也可以代表搜索引擎的接口，该搜索引擎返回符合给定搜索的结果数。我们提出了一种交互式算法，迭代选择数据集示例并执行相应的权重查询。该算法使用有限数量的权重查询发现了根据目标分布近似权重的数据集的重新加权。我们得出了一个近似结合在算法和最佳可实现重新加权的重新加权之间的总变化距离上的结合。我们的算法从多武器匪徒问题中常见的UCB方法中汲取灵感，并将其与新的差异估计器和贪婪的迭代程序相结合。除了我们的理论保证外，我们还在实验中证明了所提出算法比几个基准的优势。可以在https://github.com/nadav-barak/awp上找到拟议算法和所有实验的Python实现。
We consider a novel challenge: approximating a distribution without the ability to randomly sample from that distribution. We study how such an approximation can be obtained using *weight queries*. Given some data set of examples, a weight query presents one of the examples to an oracle, which returns the probability, according to the target distribution, of observing examples similar to the presented example. This oracle can represent, for instance, counting queries to a database of the target population, or an interface to a search engine which returns the number of results that match a given search. We propose an interactive algorithm that iteratively selects data set examples and performs corresponding weight queries. The algorithm finds a reweighting of the data set that approximates the weights according to the target distribution, using a limited number of weight queries. We derive an approximation bound on the total variation distance between the reweighting found by the algorithm and the best achievable reweighting. Our algorithm takes inspiration from the UCB approach common in multi-armed bandits problems, and combines it with a new discrepancy estimator and a greedy iterative procedure. In addition to our theoretical guarantees, we demonstrate in experiments the advantages of the proposed algorithm over several baselines. A python implementation of the proposed algorithm and of all the experiments can be found at https://github.com/Nadav-Barak/AWP.
