Graph bandit for diverse user coverage in online recommendation

Mahmuda Rahman, Jae C Oh

Research output: Contribution to journalArticle

2 Citations (Scopus)

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.

Original languageEnglish (US)
Pages (from-to)1-17
Number of pages17
JournalApplied Intelligence
DOIs
StateAccepted/In press - Jun 16 2017

Fingerprint

Recommender systems
Computational complexity
Experiments

Keywords

  • Directed graph
  • Diversity
  • Multi armed bandit
  • Online learning
  • Recommendation system
  • Upper confidence bound

ASJC Scopus subject areas

  • Artificial Intelligence

Cite this

Graph bandit for diverse user coverage in online recommendation. / Rahman, Mahmuda; Oh, Jae C.

In: Applied Intelligence, 16.06.2017, p. 1-17.

Research output: Contribution to journalArticle

@article{b5559b8ccdb34ee899ba75c7236b745c,
title = "Graph bandit for diverse user coverage in online recommendation",
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.",
keywords = "Directed graph, Diversity, Multi armed bandit, Online learning, Recommendation system, Upper confidence bound",
author = "Mahmuda Rahman and Oh, {Jae C}",
year = "2017",
month = "6",
day = "16",
doi = "10.1007/s10489-017-0977-1",
language = "English (US)",
pages = "1--17",
journal = "Applied Intelligence",
issn = "0924-669X",
publisher = "Springer Netherlands",

}

TY - JOUR

T1 - Graph bandit for diverse user coverage in online recommendation

AU - Rahman, Mahmuda

AU - Oh, Jae C

PY - 2017/6/16

Y1 - 2017/6/16

N2 - 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.

AB - 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.

KW - Directed graph

KW - Diversity

KW - Multi armed bandit

KW - Online learning

KW - Recommendation system

KW - Upper confidence bound

UR - http://www.scopus.com/inward/record.url?scp=85020545434&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85020545434&partnerID=8YFLogxK

U2 - 10.1007/s10489-017-0977-1

DO - 10.1007/s10489-017-0977-1

M3 - Article

SP - 1

EP - 17

JO - Applied Intelligence

JF - Applied Intelligence

SN - 0924-669X

ER -