A Pairwise Ranking Algorithm for Information Retrieval

Abstract

One of the main problems in machine learning is the determination of preference relations between interested units. In this context, ranking can be defined as learning a function with the ability to organize units according to a given preference relation. This type of problem is often treated as a classification problem where the examples are formed by pairs. In this study, an approach based on pairwise comparisons is presented for an estimation of a general ordering. This ranking problem that minimizes the pairwise ranking error is represented by a system of linear equations. An improved version of the gradient-descent algorithm is proposed to learn the ranking functions for solving this system of linear equations. In addition, Tikhonov regularization is also used to control the generalization performance of the ranking model. The developed rapid gradient descent algorithm converges to the solution in a very short time, regardless of the regularization level.

Özet

Yapay öğrenmede temel problemlerden biri, ilgilenilen birimler arasındaki tercih ilişkilerinin belirlenmesidir. Bukapsamda sıralama, verilen bir tercih ilişkisine göre birimleri düzenleme yeteneğine sahip bir fonksiyonuöğrenmek olarak tanımlanabilir. Bu tip problemler genellikle örneklerin çiftler olduğu sınıflandırma problemiolarak ele alınır. Bu çalışmada ise genel sıralamanın bir tahmini için eşli karşılaştırmalara dayanan bir yaklaşımsunulmuştur. Eşli sıralama hatasını minimize eden bu sıralama problemi, bir doğrusal eşitlikler sistemi ile temsiledilmiştir. Bu doğrusal eşitlik sisteminin çözülmesiyle sıralama fonksiyonlarının öğrenilmesi için gradyan düşümüalgoritmasının geliştirilmiş bir versiyonu önerilmektedir. Ayrıca, oluşturulan sıralama modelinin genelleştirmeperformansını kontrol edebilmek için Tikhonov düzeltmesi de bu çalışma kapsamında kullanılmıştır. Geliştirilenhızlı gradyan düşümü algoritması, düzeltme seviyesinden bağımsız olarak çok kısa bir sürede çözümeyakınsamıştır.