2015 DiscoveringValuableItemsfromMas

• (Vanchinathan et al., 2015) ⇒ Hastagiri P. Vanchinathan, Andreas Marfurt, Charles-Antoine Robelin, Donald Kossmann, and Andreas Krause. (2015). “Discovering Valuable Items from Massive Data.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783360

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Discovering+Valuable+Items+from+Massive+Data
• http://dl.acm.org/citation.cfm?id=2783258.2783360&preflayout=flat#citedby

Quotes

Author Keywords

• Active learning; active search; data mining; design of experiments; experimental design; kernel methods; recommender systems

Abstract

Suppose there is a large collection of items, each with an associated cost and an inherent utility that is revealed only once we commit to selecting it. Given a budget on the cumulative cost of the selected items, how can we pick a subset of maximal value? This task generalizes several important problems such as multi-arm bandits, active search and the knapsack problem. We present an algorithm, GP-SELECT, which utilizes prior knowledge about similarity between items, expressed as a kernel function. GP-SELECT uses Gaussian process prediction to balance exploration (estimating the unknown value of items) and exploitation (selecting items of high value). We extend GP-SELECT to be able to discover sets that simultaneously have high utility and are diverse. Our preference for diversity can be specified as an arbitrary monotone submodular function that quantifies the diminishing returns obtained when selecting similar items. Furthermore, we exploit the structure of the model updates to achieve an order of magnitude (up to 40X) speedup in our experiments without resorting to approximations. We provide strong guarantees on the performance of GP-SELECT and apply it to three real-world case studies of industrial relevance: (1) Refreshing a repository of prices in a Global Distribution System for the travel industry, (2) Identifying diverse, binding-affine peptides in a vaccine design task and (3) Maximizing clicks in a web-scale recommender system by recommending items to users.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 DiscoveringValuableItemsfromMas	Andreas Krause Hastagiri P. Vanchinathan Andreas Marfurt Charles-Antoine Robelin Donald Kossmann			Discovering Valuable Items from Massive Data				10.1145/2783258.2783360		2015