Active Search and Bandits on Graphs using Sigma-Optimality
Active Search and Bandits on Graphs using Sigma-Optimality
复制标题
使用西格玛最优的图上的主动搜索和强盗
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Schneider
中科院分区：
文献类型：
--
作者：
Yifei Ma;Tzu;J. Schneider
许多现代信息访问问题涉及高度复杂的模式，而传统的基于关键字的搜索无法处理这些模式。主动搜索是一种新兴的搜索范式，它通过有效地收集和学习用户反馈来帮助用户快速找到相关信息。我们考虑图上的主动搜索，其中节点代表用户想要搜索的实例集，边编码实例之间的成对相似性。现有的主动搜索算法要么缺乏理论上的保证，要么不能很好地处理图形数据。受图的主动学习的最新进展，即Σ最优性选择准则的启发，我们提出了适用于图的新的主动搜索算法，并在几个实际数据集上证明了它们的有效性。
我们将我们的主动搜索设置与多武装强盗相关联，这些强盗的奖励是二进制值，表示搜索命中或未命中，并且手臂不能被多次拉动。我们还讨论了将Σ-最优性作为图上强盗的探索项的理论保证。
Many modern information access problems involve highly complex patterns that cannot be handled by traditional keyword based search. Active Search is an emerging paradigm that helps users quickly find relevant information by efficiently collecting and learning from user feedback. We consider active search on graphs, where the nodes represent the set of instances users want to search over and the edges encode pairwise similarity among the instances. Existing active search algorithms are either short of theoretical guarantees or inadequate for graph data. Motivated by recent advances in active learning on graphs, namely the Σ-optimality selection criterion, we propose new active search algorithms suitable for graphs with theoretical guarantees and demonstrate their effectiveness on several real-world datasets.
We relate our active search setting to multi-armed bandits whose rewards are binary values indicating search hits or misses and arms cannot be pulled more than once. We also discussed theoretical guarantees for applying Σ-optimality as the exploration term for bandits on graphs.