Online Rank Aggregation

Shota Yasutake, Kohei Hatano, Eiji Takimoto, Masayuki Takeda
Proceedings of the Asian Conference on Machine Learning, PMLR 25:539-553, 2012.

Abstract

We consider an online learning framework where the task is to predict a permutation which represents a ranking of n fixed objects. At each trial, the learner incurs a loss defined as Kendall tau distance between the predicted permutation and the true permutation given by the adversary. This setting is quite natural in many situations such as information retrieval and recommendation tasks. We prove a lower bound of the cumulative loss and hardness results. Then, we propose an algorithm for this problem and prove its relative loss bound which shows our algorithm is close to optimal.

Cite this Paper

BibTeX
@InProceedings{pmlr-v25-yasutake12, title = {Online Rank Aggregation}, author = {Yasutake, Shota and Hatano, Kohei and Takimoto, Eiji and Takeda, Masayuki}, booktitle = {Proceedings of the Asian Conference on Machine Learning}, pages = {539--553}, year = {2012}, editor = {Hoi, Steven C. H. and Buntine, Wray}, volume = {25}, series = {Proceedings of Machine Learning Research}, address = {Singapore Management University, Singapore}, month = {04--06 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v25/yasutake12/yasutake12.pdf}, url = {https://proceedings.mlr.press/v25/yasutake12.html}, abstract = {We consider an online learning framework where the task is to predict a permutation which represents a ranking of n fixed objects. At each trial, the learner incurs a loss defined as Kendall tau distance between the predicted permutation and the true permutation given by the adversary. This setting is quite natural in many situations such as information retrieval and recommendation tasks. We prove a lower bound of the cumulative loss and hardness results. Then, we propose an algorithm for this problem and prove its relative loss bound which shows our algorithm is close to optimal.} }
Endnote
%0 Conference Paper %T Online Rank Aggregation %A Shota Yasutake %A Kohei Hatano %A Eiji Takimoto %A Masayuki Takeda %B Proceedings of the Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2012 %E Steven C. H. Hoi %E Wray Buntine %F pmlr-v25-yasutake12 %I PMLR %P 539--553 %U https://proceedings.mlr.press/v25/yasutake12.html %V 25 %X We consider an online learning framework where the task is to predict a permutation which represents a ranking of n fixed objects. At each trial, the learner incurs a loss defined as Kendall tau distance between the predicted permutation and the true permutation given by the adversary. This setting is quite natural in many situations such as information retrieval and recommendation tasks. We prove a lower bound of the cumulative loss and hardness results. Then, we propose an algorithm for this problem and prove its relative loss bound which shows our algorithm is close to optimal.
RIS
TY - CPAPER TI - Online Rank Aggregation AU - Shota Yasutake AU - Kohei Hatano AU - Eiji Takimoto AU - Masayuki Takeda BT - Proceedings of the Asian Conference on Machine Learning DA - 2012/11/17 ED - Steven C. H. Hoi ED - Wray Buntine ID - pmlr-v25-yasutake12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 25 SP - 539 EP - 553 L1 - http://proceedings.mlr.press/v25/yasutake12/yasutake12.pdf UR - https://proceedings.mlr.press/v25/yasutake12.html AB - We consider an online learning framework where the task is to predict a permutation which represents a ranking of n fixed objects. At each trial, the learner incurs a loss defined as Kendall tau distance between the predicted permutation and the true permutation given by the adversary. This setting is quite natural in many situations such as information retrieval and recommendation tasks. We prove a lower bound of the cumulative loss and hardness results. Then, we propose an algorithm for this problem and prove its relative loss bound which shows our algorithm is close to optimal. ER -
APA
Yasutake, S., Hatano, K., Takimoto, E. & Takeda, M.. (2012). Online Rank Aggregation. Proceedings of the Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 25:539-553 Available from https://proceedings.mlr.press/v25/yasutake12.html.

Related Material