Online Rank Aggregation
Online Rank Aggregation
复制标题
DOI：
--
复制
发表时间：
2012-12
期刊：
影响因子：
--
通讯作者：
Shota Yasutake;Kohei Hatano;Eiji Takimoto;M. Takeda
中科院分区：
文献类型：
--
作者：
Shota Yasutake;Kohei Hatano;Eiji Takimoto;M. Takeda
我们考虑一个在线学习框架，该框架是预测代表N XED对象排名的排列。在每个试验中，学习者均会造成损失，因为肯德尔·塔（Kendall tau）的肯德尔·塔（Kendall tau）距离与对手给予的真实排列之间的距离。在许多情况下，例如信息检索和建议任务，这种设置是很自然的。我们证明了累积损失和硬度结果的下限。然后，我们为此问题提出了一种算法，并证明其相对损耗结合，该算法显示我们的算法接近最佳。
We consider an online learning framework where the task is to predict a permutation which represents a ranking of n xed objects. At each trial, the learner incurs a loss dened 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.