Online Boosting for Multilabel Ranking with Top-k Feedback

We present online boosting algorithms for multilabel ranking with top-k feedback, where the learner only receives information about the top k items from the ranking it provides. We propose a novel surrogate loss function and unbiased estimator, allowing weak learners to update themselves with limite...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-10
Main Authors: Raman, Vinod, Zhang, Daniel T, Jung, Young Hun, Tewari, Ambuj
Format: Article
Language:English
Subjects:
Algorithms
Feedback
Ranking
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present online boosting algorithms for multilabel ranking with top-k feedback, where the learner only receives information about the top k items from the ranking it provides. We propose a novel surrogate loss function and unbiased estimator, allowing weak learners to update themselves with limited information. Using these techniques we adapt full information multilabel ranking algorithms (Jung and Tewari, 2018) to the top-k feedback setting and provide theoretical performance bounds which closely match the bounds of their full information counterparts, with the cost of increased sample complexity. These theoretical results are further substantiated by our experiments, which show a small gap in performance between the algorithms for the top-k feedback setting and that for the full information setting across various datasets.
ISSN:2331-8422