[DB Seminar] Fall 2015: Yifei Ma

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 Sigma-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 Sigma-optimality as the exploration term for
bandits on graphs.