research-article

Figuring out the User in a Few Steps: Bayesian Multifidelity Active Search with Cokriging

Authors:

Nikita Klyuchnikov,

Georgia Koutrika,

Emmanuel Müller,

Panagiotis KarrasAuthors Info & Claims

KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

Pages 686 - 695

https://doi.org/10.1145/3292500.3330893

Published: 25 July 2019 Publication History

Abstract

Can a system discover what a user wants without the user explicitly issuing a query? A recommender system proposes items of potential interest based on past user history. On the other hand, active search incites, and learns from, user feedback, in order to recommend items that meet a user's current tacit interests, hence promises to offer up-to-date recommendations going beyond those of a recommender system. Yet extant active search methods require an overwhelming amount of user input, relying solely on such input for each item they pick. In this paper, we propose MF-ASC, a novel active search mechanism that performs well with minimal user input. MF-ASC combines cheap, low-fidelity evaluations in the style of a recommender system with the user's high-fidelity input, using Gaussian process regression with multiple target variables (cokriging). To our knowledge, this is the first application of cokriging to active search. Our empirical study with synthetic and real-world data shows that MF-ASC outperforms the state of the art in terms of result relevance within a budget of interactions.

References

[1]

Natalia M. Alexandrov, John E Dennis Jr, Robert Michael Lewis, and Virginia Torczon. 1998. A Trust Region Framework for managing the use of approximation models in optimization. Structural Optimization, Vol. 15, 1 (1998), 16--23.

[2]

Evgeny Burnaev and Maxim Panov. 2015. Adaptive design of experiments based on Gaussian processes. SLDS. 116--125.

[3]

Apostolos N. Burnetas and Michael N. Katehakis. 1997. Optimal adaptive policies for Markov decision processes. Math. Operations Research, Vol. 22, 1 (1997), 222--255.

Digital Library

[4]

Jason V. Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit S. Dhillon. 2007. Information-theoretic metric learning. In ICML. 209--216.

Digital Library

[5]

Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer, and Richard Harshman. 1990. Indexing by latent semantic analysis. Journal of the American Society for Information Science, Vol. 41, 6 (1990), 391--407.

[6]

Gideon Dror, Noam Koenigstein, Yehuda Koren, and Markus Weimer. 2012. The Yahoo! music dataset and KDD-Cup '11. In Proc. KDD Cup 2011. 8--18.

Digital Library

[7]

Alexander I. J. Forrester, András Sóbester, and Andy J. Keane. 2007. Multi-fidelity optimization via surrogate modelling. Proc. R. Soc. A, Vol. 463, 2088 (2007), 3251--3269.

[8]

Shawn E. Gano, John E. Renaud, and Brian Sanders. 2005. Hybrid variable fidelity optimization by using a kriging-based scaling function. AIAA Journal, Vol. 43 (11 2005), 2422--2433.

[9]

Roman Garnett, Yamuna Krishnamurthy, Xuehan Xiong, Jeff G. Schneider, and Richard P. Mann. 2012. Bayesian optimal active search and surveying. In ICML .

Digital Library

[10]

Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. KDD. 855--864.

Digital Library

[11]

Yoshiharu Ishikawa, Ravishankar Subramanya, and Christos Faloutsos. 1998. MindReader: Querying databases through multiple examples. In VLDB. 218--227.

Digital Library

[12]

Kirthevasan Kandasamy, Gautam Dasarathy, Junier B Oliva, Jeff Schneider, and Barnabás Póczos. 2016a. Gaussian process bandit optimisation with multi-fidelity evaluations. In NIPS . 992--1000.

Digital Library

[13]

Kirthevasan Kandasamy, Gautam Dasarathy, Barnabas Poczos, and Jeff Schneider. 2016b. The multi-fidelity multi-armed bandit. In NIPS. 1777--1785.

Digital Library

[14]

Remi R. Lam, Karen E. Willcox, and David H. Wolpert. 2016. Bayesian optimization with a finite budget: an approximate dynamic programming approach. In NIPS. 883--891.

Digital Library

[15]

Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. 2010. A Contextual-bandit Approach to Personalized News Article Recommendation. In WWW .

Digital Library

[16]

Yifei Ma, Tzu-Kuo Huang, and Jeff G. Schneider. 2015. Active search and bandits on graphs using sigma-optimality. In UAI . 542--551.

Digital Library

[17]

Andrew March, Karen Willcox, and Qiqi Wang. 2011. Gradient-based multifidelity optimisation for aircraft design using bayesian model calibration. Aeronautical Journal, Vol. 115, 1174 (2011), 729.

[18]

Roderick P McDonald. 2013. Test theory: A unified treatment . Psychology Press.

[19]

Mark E. J. Newman. 2006. Modularity and community structure in networks. PNAS, Vol. 103, 23 (2006), 8577--8582.

[20]

Matthias Poloczek, Jialei Wang, and Peter Frazier. 2017. Multi-information source optimization. In NIPS. 4288--4298.

Digital Library

[21]

Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Physical review E, Vol. 76, 3 (2007), 036106.

[22]

Carl Edward Rasmussen and Christopher K. I. Williams. 2006. Gaussian Processes for Machine Learning ., Vol. 1. The MIT Press.

Digital Library

[23]

Paul Resnick and Hal R. Varian. 1997. Recommender Systems. Commun. ACM, Vol. 40, 3 (1997), 56--58.

Digital Library

[24]

Matthew Schultz and Thorsten Joachims. 2003. Learning a distance metric from relative comparisons. In NIPS. 41--48.

Digital Library

[25]

Burr Settles. 2012. Active Learning . Morgan & Claypool Publishers.

[26]

Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. 2012. Information-theoretic regret bounds for gaussian process optimization in the bandit setting. IEEE Trans. Information Theory, Vol. 58, 5 (2012), 3250--3265.

Digital Library

[27]

Simon Tong and Edward Chang. 2001. Support vector machine active learning for image retrieval. In MULTIMEDIA . 107--118.

Digital Library

[28]

Laurens J. P. van der Maaten and Geoffrey E. Hinton. 2008. Visualizing data using t-SNE. JMLR, Vol. 9 (2008), 2579--2605.

[29]

Hastagiri P. Vanchinathan, Andreas Marfurt, Charles-Antoine Robelin, Donald Kossmann, and Andreas Krause. 2015. Discovering valuable items from massive data. In KDD. 1195--1204.

Digital Library

[30]

Xuezhi Wang, Roman Garnett, and Jeff Schneider. 2013. Active search on graphs. In KDD. 731--738.

Digital Library

[31]

Alexey Zaytsev and Evgeny Burnaev. 2017a. Large scale variable fidelity surrogate modeling. Annals of Mathematics and Artificial Intelligence, Vol. 81, 1 (2017), 167--186.

Digital Library

[32]

Alexey Zaytsev and Evgeny Burnaev. 2017b. Minimax approach to variable fidelity data interpolation. In AISTATS . 652--661.

[33]

Hao Zhang and Wenxiang Cai. 2015. When doesn't cokriging outperform kriging? Statist. Sci., Vol. 30, 2 (2015), 176--180.

[34]

Yehong Zhang, Trong Nghia Hoang, Bryan Kian Hsiang Low, and Mohan Kankanhalli. 2017. Information-based multi-fidelity Bayesian optimization. In NIPS Workshop on Bayesian Optimization .

Cited By

Trofimov IKlyuchnikov NSalnikov MFilippov ABurnaev E(2023)Multi-Fidelity Neural Architecture Search With Knowledge DistillationIEEE Access10.1109/ACCESS.2023.323481011(59217-59225)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3234810
Loster MMottin DPapotti PEhmüller JFeldmann BNaumann F(2021)Few-Shot Knowledge Validation using RulesProceedings of the Web Conference 202110.1145/3442381.3450040(3314-3324)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3442381.3450040
Tan YYang CWei XMa YZheng X(2021)Multi-Facet Recommender Networks with Spherical Optimization2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00135(1524-1535)Online publication date: Apr-2021
https://doi.org/10.1109/ICDE51399.2021.00135

Index Terms

Recommendations

You are what you consume: a bayesian method for personalized recommendations
RecSys '13: Proceedings of the 7th ACM conference on Recommender systems

In this paper, we propose a novel Bayesian approach for personalized recommendations. In our approach, we model both user preferences and items under recommendation as multivariate Gaussian distributions; and make use of Normal-Inverse Wishart priors to ...
Recommending ephemeral items at web scale
SIGIR '11: Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval

We describe an innovative and scalable recommendation system successfully deployed at eBay. To build recommenders for long-tail marketplaces requires projection of volatile items into a persistent space of latent products. We first present a generative ...
User Personality and User Satisfaction with Recommender Systems

In this study, we show that individual users' preferences for the level of diversity, popularity, and serendipity in recommendation lists cannot be inferred from their ratings alone. We demonstrate that we can extract strong signals about individual ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

July 2019

3305 pages

ISBN:9781450362016

DOI:10.1145/3292500

General Chairs:
Ankur Teredesai
KenSci
,
Vipin Kumar
University of Minnesota
,
Program Chairs:
Ying Li
EV Analysis Corporation
,
Rómer Rosales
LinkedIn
,
Evimaria Terzi
Boston University
,
George Karypis
University of Minnesota

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

AUFF

Conference

KDD '19

Sponsor:

KDD '19: The 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 4 - 8, 2019

AK, Anchorage, USA

Acceptance Rates

KDD '19 Paper Acceptance Rate 110 of 1,200 submissions, 9%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
459
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Trofimov IKlyuchnikov NSalnikov MFilippov ABurnaev E(2023)Multi-Fidelity Neural Architecture Search With Knowledge DistillationIEEE Access10.1109/ACCESS.2023.323481011(59217-59225)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3234810
Loster MMottin DPapotti PEhmüller JFeldmann BNaumann F(2021)Few-Shot Knowledge Validation using RulesProceedings of the Web Conference 202110.1145/3442381.3450040(3314-3324)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3442381.3450040
Tan YYang CWei XMa YZheng X(2021)Multi-Facet Recommender Networks with Spherical Optimization2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00135(1524-1535)Online publication date: Apr-2021
https://doi.org/10.1109/ICDE51399.2021.00135

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents