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

在學習排名的方法中,有別於一般的基於分數得到排名的方法,一類基於偏好學習排名的模型先是利用二元分類模型去預測兩個待排序物件之間的偏好關係,再利用物件兩兩之間的偏好關係去產生排名。許多先前提出的偏好學習排名方法的共同問題便是在預測階段的時間效率不彰。為此,在這篇文章中,我們提出一新的分治方法 "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.

並列關鍵字

machine learning ； learning to rank ； preference-based ； divide-and-conquer

參考文獻

[1] Tie-Yan Liu. Learning to rank for information retrieval. Foundations and Trends in Information Retrieval, 3(3):225–331, 2009.

[2] Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, and Hang Li. Learning to rank: from pairwise approach to listwise approach. In Proceedings of the 24th international conference on Machine learning, pages 129–136. ACM, 2007.

[15] Nir Ailon and Mehryar Mohri. Preference-based learning to rank. Machine Learning, 80(2-3):189–211, 2010.

[16] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent infor- mation: Ranking and clustering. J. ACM, 55(5):23:1–23:27, November 2008.

[19] Sahand Negahban, Sewoong Oh, and Devavrat Shah. Iterative ranking from pair-wise comparisons. In NIPS, pages 2483–2491, 2012.

國際替代計量

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

全文下載

主題瀏覽