Near-Optimal Data Source Selection for Bayesian Learning
Near-Optimal Data Source Selection for Bayesian Learning
复制标题
DOI：
--
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Lintao Ye;A. Mitra;S. Sundaram
中科院分区：
文献类型：
--
作者：
Lintao Ye;A. Mitra;S. Sundaram
我们研究了贝叶斯学习中的一个基本问题，目标是根据所选择的数据源提供的数据流，选择一组代价最小的数据源，同时获得一定的学习性能。首先，我们证明了贝叶斯学习的数据源选择问题是NP难的。然后，我们证明了数据源选择问题可以转化为文献中所研究的子模集合覆盖问题的一个实例，并给出了一个标准的贪婪算法来解决数据源选择问题，并且具有可证明的性能保证。接下来，我们提出了一种快速贪婪算法，改进了标准贪婪算法的运行时间，同时获得了与标准贪婪算法相当的性能保证。通过分析这类特殊的问题，我们对贪婪算法的性能保证提供了深入的见解。最后，通过数值算例对理论结果进行了验证，结果表明贪婪算法在实际应用中效果良好。
We study a fundamental problem in Bayesian learning, where the goal is to select a set of data sources with minimum cost while achieving a certain learning performance based on the data streams provided by the selected data sources. First, we show that the data source selection problem for Bayesian learning is NP-hard. We then show that the data source selection problem can be transformed into an instance of the submodular set covering problem studied in the literature, and provide a standard greedy algorithm to solve the data source selection problem with provable performance guarantees. Next, we propose a fast greedy algorithm that improves the running times of the standard greedy algorithm, while achieving performance guarantees that are comparable to those of the standard greedy algorithm. We provide insights into the performance guarantees of the greedy algorithms by analyzing special classes of the problem. Finally, we validate the theoretical results using numerical examples, and show that the greedy algorithms work well in practice.