More Web Proxy on the site http://driver.im/

article

Graph bandit for diverse user coverage in online recommendation

Authors:

Mahmuda Rahman,

Jae C. OhAuthors Info & Claims

Applied Intelligence, Volume 48, Issue 8

Pages 1979 - 1995

https://doi.org/10.1007/s10489-017-0977-1

Published: 01 August 2018 Publication History

Abstract

We study a recommendation system problem, in which the system must be able to cover as many users' preferences as possible while these preferences change over time. This problem can be formulated as a variation of the maximum coverage problem; specifically we introduced a novel problem of Online k-Hitting Set, where the number of sets and elements within the sets can change dynamically. When the number of distinctive elements is large, an exhaustive search for even a fixed number of elements is known to be computationally expensive. Even the static problem is known to be NP-hard (Hochba, ACM SIGACT News 28(2):40---52, 1997) and many known algorithms tend to have exponential growth in complexity. We propose a novel graph based UCB1 algorithm that effectively minimizes the number of elements to consider, thereby reducing the search space greatly. The algorithm utilizes a new rewarding scheme to choose items that satisfy more users by balancing coverage and diversity as it construct a relational graph between items to recommend. Experiments show that the new graph based algorithm performs better than existing techniques such as Ranked Bandit (Radlinski et al. 2008) and Independent Bandits (Kohli et al. 2013) in terms of satisfying diverse types of users while minimizing computational complexity.

References

[1]

Agrawal S (2011) Optimization under uncertainty: bounding the correlation gap. Ph D Thesis. Stanford University

[2]

Auer P, Cesa-Bianchi N, Fischer P (2002) Finite-time analysis of the multiarmed bandit problem. Mach Learn 47(2-3):235---256

Digital Library

[3]

Ausiello G, Boria N, Giannakos A, Lucarelli G, Paschos VT (2011) Online maximum k-coverage. In: International symposium on fundamentals of computation theory. Springer, pp 181---192

Digital Library

[4]

Azizi N, Zolfaghari S (2004) Adaptive temperature control for simulated annealing: a comparative study. Comput Oper Res 31(14):2439---2451

Digital Library

[5]

Bnaya Z, Puzis R, Stern R, Felner A (2013) Volatile multi-armed bandits for guaranteed targeted social crawling. In: Late-breaking developments in the field of artificial intelligence. Bellevue, Washington, USA, p 2013

Digital Library

[6]

Burke R (2007) The adaptive web. In: Brusilovsky P, Kobsa A, Nejdl W (eds) Hybrid web recommender systems. Springer, Berlin, Heidelberg, pp 377---408

Digital Library

[7]

Chakrabarti D, Kumar R, Radlinski F, Upfal E (2008) Mortal multi-armed bandits. In: Advances in neural information processing systems 21, proceedings of the 22nd annual conference on neural information processing systems. Vancouver, British Columbia, Canada, pp 273---280

Digital Library

[8]

Cohen R, Katzir L (2008) The generalized maximum coverage problem. Inf Process Lett 108(1):15---22

Digital Library

[9]

Diriye A, White R, Buscher G, Dumais S (2012) Leaving so soon?: understanding and predicting web search abandonment rationales. In: Proceedings of the 21st ACM international conference on information and knowledge management. ACM, CIKM'12, New York, pp 1025---1034

Digital Library

[10]

Ekstrand MD, Riedl JT, Konstan JA (2011) Collaborative filtering recommender systems. Foundation and Trends in Human Computer Interaction 4(2):81---173

Digital Library

[11]

Goldberg K, Roeder T, Gupta D, Perkins C (2001) Eigentaste: a constant time collaborative filtering algorithm. Inf Retr 4(2):133---151

Digital Library

[12]

Harper FM, Konstan JA (2015) The movielens datasets: history and context. ACM Trans on Interactactive Intell Syst 5(4):19:1---19:19

Digital Library

[13]

Hochba DS (1997) Approximation algorithms for np-hard problems. ACM SIGACT News 28(2):40---52

Digital Library

[14]

Hochbaum DS, Pathria A (1998) Analysis of the greedy approach in problems of maximum k-coverage. Nav Res Logista (NRL) 45(6):615---627

[15]

Joachims T (2002) Optimizing search engines using clickthrough data. In: Proceedings of the eighth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, KDD'02, New York, pp 133---142

Digital Library

[16]

Kohli P, Salek M, Stoddard G (2013) A fast bandit algorithm for recommendations to users with heterogeneous tastes. In: Proceedings of the 27th AAAI conference on artificial intelligence. AAAI AAAI'13, Press, pp 1135---1141

Digital Library

[17]

Lee K, Lee K (2015) Escaping your comfort zone: a graph-based recommender system for finding novel recommendations among relevant items. Expert Syst Appl 42(10):4851---4858

Digital Library

[18]

Pandey S, Chakrabarti D, Agarwal D (2007) Multi-armed bandit problems with dependent arms. In: Proceedings of the 24th international conference on machine learning. ACM, ICML'07, New York, pp 721---728

Digital Library

[19]

Park W, Oh JC, Blowers MK, Wolf MB (2006) An open-set speaker identification system using genetic learning classifier system. In: Proceedings of the 8th annual conference on genetic and evolutionary computation. ACM, GECCO'06, New York, pp 1597---1598

Digital Library

[20]

Pazzani MJ, Billsus D (2007) Content-based recommendation systems. In: The adaptive web: method and strategies of web personalization. Vol 4321 of lecture notes in computer science. Springer, pp 325---341

Digital Library

[21]

Radlinski F, Kleinberg R, Joachims T (2008) Learning diverse rankings with multi-armed bandits. In: Proceedings of the 25th international conference on machine learning. ACM, ICML'08, New York, pp 784---791

Digital Library

[22]

Rahman M, Oh JC (2015a) Fast online learning to recommend a diverse set from big data. In: The 28th international conference on industrial, engineering and other application of applied intelligent systems IEA/AIE'15. Springer, Switzerland, pp 361---370

Digital Library

[23]

Rahman M, Oh JC (2015b) Parallel and synchronized UCB2 for online recommendation systems. In: IEEE/WIC/ACM international conference on web intelligence and intelligent agent technology, WI-IAT 2015. Singapore, December 6---9, 2015, vol I, pp 413---416

Digital Library

[24]

Robertson SE (1997) In: Sparck Jones K, Willett P (eds) Readings in information retrieval. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, pp 281---286

Digital Library

[25]

Shani G, Gunawardana A (2011) Evaluating recommendation systems. In: Recommender systems handbook. Springer, pp 257---297

[26]

Sviridenko M (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper Res Lett 32(1):41---43

Digital Library

[27]

Tekin C, Liu M (2012) Online learning of rested and restless bandits. IEEE Trans Inf Theory 58(8):5588---5611

Digital Library

[28]

Vermorel J, Mohri M (2005) Multi-armed bandit algorithms and empirical evaluation. In: Proceedings of the 16th european conference on machine learning ECML'05. Springer, Berlin, Heidelberg, pp 437---448

Digital Library

[29]

Vinterbo SA, Øhrn A (2000) Minimal approximate hitting sets and rule templates. Int J Approx Reason 25:123---143

[30]

Zhang M, Hurley N (2008) Avoiding monotony: improving the diversity of recommendation lists Proceedings of the 2008 ACM conference on recommender systems. ACM, RecSys'08, New York, pp 123---130

Digital Library

Cited By

Losada DElsweiler DHarvey MTrattner C(2022)A day at the racesApplied Intelligence10.1007/s10489-021-02719-252:5(5617-5632)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10489-021-02719-2
Jannach DJugovac M(2019)Measuring the Business Value of Recommender SystemsACM Transactions on Management Information Systems10.1145/337008210:4(1-23)Online publication date: 10-Dec-2019
https://dl.acm.org/doi/10.1145/3370082
Zare AMotadel MJalali A(2019)Presenting a hybrid model in social networks recommendation system architecture developmentAI & Society10.1007/s00146-019-00893-z35:2(469-483)Online publication date: 18-May-2019
https://dl.acm.org/doi/10.1007/s00146-019-00893-z

Graph bandit for diverse user coverage in online recommendation
1. Computing methodologies

Recommendations

Fast Online Learning to Recommend a Diverse Set from Big Data
Proceedings of the 28th International Conference on Current Approaches in Applied Artificial Intelligence - Volume 9101

Building a recommendation system to withstand the rapid change in items' relevance to users is a challenge requiring continual optimization. In a Big Data scenario, it becomes a harder problem, in which users get substantially diverse in their tastes. ...
A framework for diversifying recommendation lists by user interest expansion

Recommender systems have been widely used to discover users' preferences and recommend interesting items to users during this age of information overload. Researchers in the field of recommender systems have realized that the quality of a top-N ...
Preference-based user rating correction process for interactive recommendation systems

In most of the recommendation systems, user rating is an important user activity that reflects their opinions. Once the users return their ratings about items the systems have suggested, the user ratings can be used to adjust the recommendation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Applied Intelligence

Applied Intelligence Volume 48, Issue 8

August 2018

634 pages

ISSN:0924-669X

Issue’s Table of Contents

Copyright © Copyright © 2018 Springer Science+Business Media, LLC, part of Springer Nature.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 August 2018

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Losada DElsweiler DHarvey MTrattner C(2022)A day at the racesApplied Intelligence10.1007/s10489-021-02719-252:5(5617-5632)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10489-021-02719-2
Jannach DJugovac M(2019)Measuring the Business Value of Recommender SystemsACM Transactions on Management Information Systems10.1145/337008210:4(1-23)Online publication date: 10-Dec-2019
https://dl.acm.org/doi/10.1145/3370082
Zare AMotadel MJalali A(2019)Presenting a hybrid model in social networks recommendation system architecture developmentAI & Society10.1007/s00146-019-00893-z35:2(469-483)Online publication date: 18-May-2019
https://dl.acm.org/doi/10.1007/s00146-019-00893-z

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents