一基於偏好學習排名的分治方法

Abstract

在學習排名的方法中,有別於一般的基於分數得到排名的方法,一類基於偏好學習排名的模型先是利用二元分類模型去預測兩個待排序物件之間的偏好關係,再利用物件兩兩之間的偏好關係去產生排名。許多先前提出的偏好學習排名方法的共同問題便是在預測階段的時間效率不彰。為此,在這篇文章中,我們提出一新的分治方法 'Fuzzy Sort' 來解決偏好學習排名在預測階段的效率問題。我們的方法能在 O(W·N lg N) 的時間內完成預測,其中 W 是一可調整的參數,在一般的狀況下不超過 50。我們提出的演算法相對於其他偏好學習排名的方法,大幅改善了預測效率,並且在準確度勝過了大多數傳統基於分數得到排名的模型。

In preference-based learning to rank (LTR), rather than training a score- based prediction model, a binary prediction model (with probabilistic output) is trained over pairs of instances as a preference function. The ranking is then produced using the pairwise preference outputs in the prediction stage. In this paper we study the preference-based LTR problem and presents a practical approach we called the “Fuzzy Sort” which runs in O(W·N lg N), where W is typically no larger than 50 in practice. The algorithm shows promising results compared with other conventional ranking methods, and is query-efficient when competing against other preference-based LTR approaches.