Active search on graphs
Active search on graphs
复制标题
图表上的主动搜索
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
J. Schneider
中科院分区：
文献类型：
--
作者：
Xuezhi Wang;R. Garnett;J. Schneider
主动搜索是一个越来越重要的学习问题，我们使用有限的标签查询预算来发现尽可能多的某个类的成员。许多现实世界的应用可以以这种方式进行，包括欺诈检测、产品推荐和药物发现。主动搜索具有与主动学习和强盗问题类似的模型学习和探索/利用特征，但这些问题的算法不适合主动搜索。先前关于主动搜索问题的工作[5]表明，最优算法需要对预期效用进行前瞻评估，该预期效用在要进行的选择数量中是指数的，并提出了截断前瞻启发式。受近视方法在主动学习和强盗问题上的成功启发，我们提出了一种近视方法用于图上的主动搜索。我们建议通过考虑选择节点的潜在影响来最大化分数来选择点，这意味着在避免指数搜索的同时模拟前瞻。我们测试所提出的算法在现实世界的图形经验，并表明它优于流行的方法，主动学习和强盗问题，以及截断前瞻的几个步骤。
Active search is an increasingly important learning problem in which we use a limited budget of label queries to discover as many members of a certain class as possible. Numerous real-world applications may be approached in this manner, including fraud detection, product recommendation, and drug discovery. Active search has model learning and exploration/exploitation features similar to those encountered in active learning and bandit problems, but algorithms for those problems do not fit active search. Previous work on the active search problem [5] showed that the optimal algorithm requires a lookahead evaluation of expected utility that is exponential in the number of selections to be made and proposed a truncated lookahead heuristic. Inspired by the success of myopic methods for active learning and bandit problems, we propose a myopic method for active search on graphs. We suggest selecting points by maximizing a score considering the potential impact of selecting a node, meant to emulate lookahead while avoiding exponential search. We test the proposed algorithm empirically on real-world graphs and show that it outperforms popular approaches for active learning and bandit problems as well as truncated lookahead of a few steps.