The 118th RCKC Colloquium "Search Result Diversification via Filling up Multiple Knapsacks"

Title "Search Result Diversification via Filling up Multiple Knapsacks"
Speaker Yu Haitao (Assistant Professor Faculty of Library, Information and Media Science University of Tsukuba)
Date Friday, December 19th, 2014. 11:00-12:00
Location Meeting Room for Joint Research 1 on the 3rd floor of ULIS bldg. in Kasuga Area
Abstract Result diversification is a topic of great value for enhancing user experience in many fields, such as web search and recommender systems. Many existing methods generate a diversified result in a sequential manner, but they work well only if the preceding choices are optimal or close to the optimal solution. Moreover, a manually tuned parameter (say, λ) is often required to trade off relevance and diversity. This makes it difficult to know whether the failures are caused by the optimization criterion or the setting of λ. In context of web search, we formulate the result diversification task as a 0-1 multiple subtopic knapsack problem (MSKP), where a subset of documents are optimally chosen like filling up multiple subtopic knapsacks. This formulation yields no trade-off parameters to be specified beforehand. Solving the 0-1 MSKP is NP-hard, we treat the optimization of 0-1 MSKP using a graphical model over latent binary variables as a maximum posterior inference problem, and tackle it with the max-sum belief propagation algorithm.
Participation The seminar will be presented in English. No charge to participate and no reservation is needed.