Sıralama öğrenmesi

**Sıralama öğrenmesi** (Learning to Rank) ya da **makine öğrenimiyle sıralama** (Machine-Learned Ranking – MLR), bilgi erişim sistemleri için sıralama modellerinin oluşturulmasında **makine öğrenmesi**nin – genellikle **denetimli**, **yarı denetimli** ya da **pekiştirmeli öğrenme** (reinforcement learning) – uygulanmasıdır.

Eğitim verileri, örneğin, her bir liste içindeki öğeler arasında belirli bir kısmi sıralama belirtilmiş olan öğe listelerinden oluşabilir. Bu sıralama genellikle, her bir öğeye verilen **sayısal** ya da **sırasal** bir puanlama ya da **ikili bir değerlendirme** (örneğin “ilgili” veya “ilgisiz”) yoluyla elde edilir.

Sıralama modelinin oluşturulmasındaki amaç, yeni ve daha önce görülmemiş listeleri, eğitim verilerindeki sıralamalara benzer şekilde sıralayabilmektir.

## Uygulamalar

### Bilgi Erişimde
**Sıralama**, belge getirme, işbirlikli filtreleme, duygu analizi ve çevrim içi reklamcılık gibi birçok bilgi erişim problemi için merkezî bir bileşendir.

Makine öğrenimi tabanlı bir arama motorunun olası bir mimarisi, ekteki şekilde gösterilmiştir.

**Eğitim verisi**, sorgular ile onlara eşleşen belgelerden ve her bir eşleşmenin **ilişkililik derecesinden** oluşur. Bu veriler, bazı sorgular için elde edilen sonuçları kontrol eden ve her bir sonucun ilişkililiğini belirleyen **değerlendiriciler** (Google bu kişilere “değerlendirici” – *rater* – demektedir) tarafından elle hazırlanabilir. Ancak, tüm belgelerin ilişkililiğini değerlendirmek mümkün olmadığından, genellikle **pooling** adı verilen bir teknik kullanılır — yalnızca mevcut sıralama modelleri tarafından getirilen en üstteki birkaç belge kontrol edilir. Bu teknik, **seçim yanlılığına (selection bias)** neden olabilir. Alternatif olarak, eğitim verisi otomatik şekilde de elde edilebilir; örneğin **tıklama kayıtları** (kullanıcıların tıkladığı arama sonuçları) , sorgu zincirleri ya da Google’ın sonradan kaldırılan **SearchWiki** gibi arama motoru özelliklerinin analiz edilmesiyle.

Tıklama kayıtları da kullanıcıların üst sıralarda çıkan sonuçlara “zaten iyi sıralanmıştır” varsayımıyla tıklama eğiliminde olması nedeniyle yanlı olabilir.

Eğitim verisi, bir **öğrenme algoritması** tarafından kullanılarak, gerçek sorgular için belgelerin ilişkililik derecelerini hesaplayan bir **sıralama modeli** üretmek amacıyla kullanılır.

Kullanıcılar genellikle bir arama sorgusunun çok kısa sürede (örneğin web aramalarında birkaç yüz milisaniye içinde) tamamlanmasını bekler. Bu nedenle, veri kümesindeki her belge üzerinde karmaşık bir sıralama modelinin değerlendirilmesi mümkün değildir. Bu sebeple **iki aşamalı bir yaklaşım** benimsenir.

İlk aşamada, **vektör uzayı modeli**, **Boole modeli**, **ağırlıklı AND** ya da **BM25** gibi hızlı sorgu değerlendirmesine imkân tanıyan daha basit erişim modelleri kullanılarak, potansiyel olarak ilişkili **az sayıda belge** belirlenir. Bu aşamaya **ilk k belge getirme (top-k retrieval)** adı verilir. Bu süreci hızlandırmak amacıyla, belgelerin **statik kalite puanları** ve **katmanlı indeksleme (tiered indexing)** gibi çeşitli sezgisel yöntemler önerilmiştir.

İkinci aşamada ise, daha doğru ancak hesaplama açısından daha maliyetli olan bir **makine öğrenimi tabanlı sıralama modeli**, bu belgelerin yeniden sıralanması için kullanılır.

### Diğer alanlarda
Sıralama öğrenme (Learning to Rank) algoritmaları, bilgi erişiminin dışında kalan alanlarda da uygulanmıştır:

* **Makine çevirisi** alanında, öne sürülen çeviri adaylarının sıralanmasında;
* **Hesaplamalı biyoloji** alanında, protein yapı tahmini problemlerinde aday 3 boyutlu yapıların sıralanmasında;
* **Tavsiye sistemlerinde**, bir haber makalesi okunduktan sonra kullanıcıya önerilecek ilgili haberlerin sıralı bir listesinin belirlenmesinde.

### Özellik vektörleri
MLR (Sıralama Öğrenme) algoritmalarının kolaylığı açısından, sorgu-belge çiftleri genellikle "özellik vektörleri" olarak adlandırılan sayısal vektörlerle temsil edilir. Bu yaklaşım bazen "özellik torbası" (bag of features) olarak adlandırılır ve belgelerin temsilinde kullanılan "kelime torbası" (bag of words) ve "vektör uzayı modeli" (vector space model) ile benzerlik gösterir.

Bu vektörlerin bileşenlerine özellik (feature), faktör (factor) ya da sıralama sinyali (ranking signal) denir. Bu özellikler üç gruba ayrılabilir (belge getirme örnekleri üzerinden):

* **Sorgudan bağımsız (statik) özellikler:** Sadece belgeye bağlı olan, sorguya bağlı olmayan özelliklerdir. Örneğin, PageRank değeri veya belgenin uzunluğu. Bu tür özellikler, indeksleme sırasında çevrimdışı (off-line) olarak önceden hesaplanabilir. Bu özellikler genellikle belgenin statik kalite puanını (static quality score) veya statik sırasını (static rank) hesaplamakta kullanılır ve bu sayede arama sorgularının değerlendirilmesi hızlandırılabilir.
* **Sorguya bağlı (dinamik) özellikler:** Hem belge içeriğine hem de sorguya bağlı olan özelliklerdir. Örneğin, TF-IDF skoru veya diğer makine öğrenmesi tabanlı olmayan sıralama fonksiyonları bu gruba girer.
* **Sorgu düzeyinde özellikler:** Sadece sorguya bağlı olan özelliklerdir. Örneğin, sorgudaki kelime sayısı.

**[https://www.microsoft.com/en-us/research/project/letor-learning-rank-information-retrieval/ LETOR]** veri setinde kullanılan bazı özellik örnekleri:

* Belgenin farklı bölgeleri (başlık, gövde, bağlantı metni, URL) için verilen sorguya göre hesaplanan TF, TF-IDF, BM25 ve dil modeli skorları;
* Belge bölgelerinin uzunlukları ve IDF toplamları;
* Belgenin PageRank değeri, HITS sıralamaları ve bunların türevleri.

**İyi özellikleri seçmek ve tasarlamak, makine öğrenmesinde "özellik mühendisliği" (feature engineering) olarak bilinen önemli bir çalışma alanıdır.**

### Değerlendirme metrikleri
Bir algoritmanın eğitim verisi üzerindeki başarımını değerlendirmek ve farklı Sıralama Öğrenme (MLR) algoritmalarını karşılaştırmak için yaygın olarak kullanılan çeşitli ölçüm metrikleri vardır. Genellikle, sıralama öğrenme problemleri bu metriklerden birine göre optimize edilecek şekilde yeniden biçimlendirilir.

Sıralama kalitesini ölçmede kullanılan bazı örnek metrikler şunlardır:

* Ortalama ortalama kesinlik (Mean Average Precision - MAP);
* DCG (Discounted Cumulative Gain) ve normalize edilmiş hali olan NDCG;
* Precision@n, NDCG@n – burada "@n", metriklerin yalnızca en üstteki n belge üzerinden hesaplandığını belirtir;
* Ortalama karşılıklı sıra (Mean Reciprocal Rank - MRR);
* Kendall’ın tau katsayısı;
* Spearman’ın rho katsayısı.

DCG ve onun normalize edilmiş versiyonu NDCG, birden fazla alaka düzeyinin kullanıldığı akademik araştırmalarda genellikle tercih edilir. Diğer metrikler — örneğin MAP, MRR ve precision — yalnızca ikili (binary) yargıların (yani belge alakalı mı değil mi gibi) olduğu durumlarda tanımlanmıştır.

Son zamanlarda, kullanıcının arama sonuçlarından aldığı memnuniyeti DCG'den daha iyi modellediği iddia edilen bazı yeni değerlendirme metrikleri önerilmiştir:

* Beklenen karşılıklı sıra (Expected Reciprocal Rank - ERR);
* Yandex'in pfound metriği.

Bu iki metrik de, kullanıcının daha alakalı bir belgeyi gördükten sonra arama sonuçlarına bakmayı bırakma olasılığının daha az alakalı bir belgeye göre daha yüksek olduğu varsayımına dayanır.

## Yaklaşımlar
Sıralama öğrenme (Learning to Rank) yaklaşımları genellikle üç ana kategori altında sınıflandırılır:

* **Noktasal yaklaşım (pointwise):** Her belge tek başına değerlendirilir ve puanlanarak sıralanır.
* **Çiftli yaklaşım (pairwise):** Belge çiftleri karşılaştırılır ve göreli sıraları belirlenir.
* **Liste tabanlı yaklaşım (listwise):** Tüm belge listesi birlikte değerlendirilir ve doğrudan sıralanır.

Microsoft Research Asia'dan Tie-Yan Liu, bilgi erişim için sıralama öğrenme problemlerine yönelik mevcut algoritmaları *Learning to Rank for Information Retrieval* adlı kitabında incelemiştir. Liu, bu algoritmaları giriş uzayları (input spaces), çıkış uzayları (output spaces), hipotez uzayları (modelin temel fonksiyonu) ve kayıp fonksiyonlarına (loss functions) göre üç grupta sınıflandırmıştır: noktasal (pointwise), çiftli (pairwise) ve liste tabanlı (listwise) yaklaşımlar.Pratikte, liste tabanlı yaklaşımların genellikle çiftli ve noktasal yaklaşımlardan daha iyi performans gösterdiği görülmüştür. Bu görüş, farklı sıralama öğrenme yöntemlerinin büyük bir kıyaslama veri kümesi üzerinde yapılan geniş çaplı bir deneyle de desteklenmiştir.

**Bu bölümde, aksi belirtilmedikçe:**

* **x**: Değerlendirilecek nesneyi (örneğin bir belge veya görsel) temsil eder.
* **f(x)**: Tek değerli (skalar) bir hipotez fonksiyonunu temsil eder.
* **h(⋅)**: İki veya daha çok değişkenli bir fonksiyonu gösterir.
* **L(⋅)**: Kayıp fonksiyonunu ifade eder.

## Noktasal yaklaşım (Pointwise)
Bu durumda, eğitim verilerindeki her bir sorgu-belge çifti için sayısal ya da sıralı bir skor olduğu varsayılmaktadır. O zaman, öğrenmeye dayalı sıralama problemi bir regresyon problemi olarak yaklaşık bir şekilde ele alınabilir — tek bir sorgu-belge çifti verildiğinde, skorunu tahmin etmek. Matematiksel olarak, noktasal yaklaşım, bir belge **x**'in gerçek değeri ya da sıralı skorunu tahmin eden bir **f(x)** fonksiyonunu öğrenmeyi amaçlar ve bu öğrenme, **L(f; xₗ, yₗ)** kayıp fonksiyonu ile yapılır.

Mevcut birçok denetimli makine öğrenimi algoritması, bu amaçla kolayca kullanılabilir. Sıralı regresyon ve sınıflandırma algoritmaları, noktasal yaklaşımda tek bir sorgu-belge çiftinin skorunu tahmin etmek için kullanıldığında, küçük ve sonlu bir değerler kümesi alacak şekilde uygulanabilir.

### Sıralama için Çok Sınıflı Sınıflandırma (Multi-class Classification for Ranking)
Li ve arkadaşları tarafından McRank önerilmiştir ; burada sıralama modelleri oluşturmak için çok sınıflı sınıflandırma (multi-class classification) kullanılmıştır.

Diyelim ki, belge koleksiyonumuz X=\{x_j\}_{j=1}^m
 ve ilgili alaka etiketleri (relevance labels) Y=\{y_j\}_{j=1}^m
 sorgu q ile ilişkilendirilmiştir.

Bu durumda, x_j
 üzerinde \hat{y}_j
'yi tahmin eden birçok sınıflı sınıflayıcımız (multi-class classifier) olduğunu söyleyebiliriz.

Bu sınıflayıcı için kayıp fonksiyonu (loss function) şu şekilde tanımlanmıştır:

L(\hat{y}_j,y_j)=I

burada I gösterge fonksiyonudur (indicator function) .
Sınıflandırma sonuçlarını sıralama skorlarına (ranking scores) dönüştürmek için, sınıflayıcı çıktıları bir olasılık dağılımına (probability distribution) çevrilir. Bu dağılım, bir belgenin belirli bir kategoriye ait olma olasılığını gösterir.

Bu olasılığı şu şekilde tanımlayabiliriz:

P(\hat{y}_j=k),k=0,...,K-1


burada K, kategori sayısını (number of categories) ifade eder.

Sonrasında, nihai sıralama skoru fonksiyonu (final ranking score function) şöyle tanımlanır:

H(x_j)=\sum_{k=0}^{K-1}kP(\widehat{y}_j=k)

### Regresyon ile Alt Küme Sıralaması (Subset Ranking with Regression)
Cossock ve Zahn , sıralama (ranking) problemini bir regresyon (regression) problemine indirgeme yaklaşımını önermiştir. Varsayalım ki, bir skorlama fonksiyonu (scoring function) olan **f**, bir sorguya (**query**) ait belgeler kümesi X=\{x_j\}_{j=1}^m
 üzerinde sıralama yapmak için kullanılmaktadır ve bu belgeler, ilgili alaka etiketleri (**relevance labels**) **<math>Y=\{y_j\}_{j=1}^m
</math>** ile ilişkilidir. Bu yaklaşımda, kayıp fonksiyonu (loss function) bir regresyon kaybı (regression loss) olarak şu şekilde formüle edilmiştir:

L(f;x_j,y_j)=(y_j-f(x_j))^2

### Diğer Noktasal (Point-wise) Algoritmalar
Chu ve Ghahramani , sıralı regresyon (ordinal regression) için olasılıksal bir çekirdek (probabilistic kernel) yaklaşımı önermektedir; bu yaklaşım, Gaussian süreçleri (Gaussian process) üzerine kuruludur. İki çıkarım (inference) tekniği kullanmaktadırlar: Laplace yaklaşımı (Laplace approximation) ve beklenti yayılımı algoritması (expectation propagation algorithm). Bu teknikleri daha önceki sıralı regresyon modelleriyle karşılaştırmışlar ve kullandıkları veri kümeleri üzerinde yöntemlerinin faydalı olduğunu rapor etmişlerdir.

Cooper ve arkadaşları , istatistiksel bağımsızlık varsayımları (statistical independence assumptions) ile çoklu regresyon analizini (multiple regression analysis) ek bir hesaplama karmaşıklığına neden olmadan birleştirmiştir. Yaklaşımlarının en önemli unsuru, regresyon analizinin iki veya daha fazla düzeyde (stage) gerçekleştirilmesidir. Bu yöntem, bileşik (composite) veya gruplanmış (grouped) erişim ipuçlarının önce gruplar içinde, ardından gruplar arasında analiz edilmesine olanak sağlamaktadır.

Crammer ve Singer , sıralama (ranking) problemini ele almıştır. Kendi çerçevelerinde, her örnek (instance) bir sıralama (rank) veya derecelendirme (rating) ile ilişkilidir ve bu değerler 1'den **k**'ya kadar değişmektedir. Amaç, minimum kayıp değerine sahip bir sıralama tahmin kuralı (rank prediction rule) bulmaktır. Bu hedef için, PRank adlı çevrimiçi bir sıralama algoritması (online ranking algorithm) geliştirmişlerdir.

Gey , olasılıksal metin ve belge erişimi (probabilistic text and document retrieval) için bir model önermektedir ve bu model lojistik regresyon (logistic regression) tekniklerini kullanmaktadır. Bu modele "lojistik çıkarım" (logistic inference) adını vermektedirler. Her istatistiksel ipucunun dağılımı, ortalaması 0 ve standart sapması 1 olacak şekilde standartlaştırıldığında, eğitim kümesinden türetilmiş lojistik katsayıların (logistic coefficients) başka bir kümeye uygulanabileceği ilkesine dayanırlar. Modeli, bilinen veri kümeleri üzerinde uygulamışlar ve başarılı sonuçlar elde etmişlerdir.

Nallapati , ayrıştırıcı sınıflayıcıların (discriminative classifiers) bilgi erişimde uygulanabilirliğini araştırmıştır. En yüksek entropi (maximum entropy) ve destek vektör makineleri (support vector machines - SVM) gibi iki popüler ayrıştırıcı model ile dil modellemesini (language modeling) karşılaştırmıştır. Deneyler, en yüksek entropi yönteminin dil modelinden belirgin şekilde daha kötü performans gösterdiğini, destek vektör makinelerinin ise dil modelleme ile benzer düzeyde sonuçlar verdiğini göstermiştir.

## İkili yaklaşım (Çiftler bazında yaklaşım)
Nokta-tabanlı (point-wise) yaklaşımlarda her bir belgenin sorguya göre alaka düzeyini bulmaya çalışmak yerine, çiftler-tabanlı (pair-wise) yaklaşım iki belge arasındaki göreli sıralamayı bulmaya odaklanır. Bu sebeple, çiftler-tabanlı yaklaşımın sıralama kavramına nokta-tabanlı yaklaşımdan daha yakın olduğunu söyleyebiliriz. Sıralama problemi, belge çiftleri üzerinde bir sınıflandırma problemi olarak ele alınır. Öğrenmenin amacı, yanlış sınıflandırılan belge çiftlerinin sayısını en aza indirmektir. Dolayısıyla, eğer tüm belge çiftleri doğru şekilde sınıflandırılmışsa, bu durum sorgu q'ya ait tüm belge listesinin doğru şekilde sıralandığı anlamına gelir.

Çiftler-tabanlı yaklaşımda, giriş uzayı (input space), özellik vektörleri (feature vectors) ile temsil edilen belge çiftlerinden oluşur. Çıkış uzayı (output space) ise, çiftlerdeki belgeler arasındaki tercih etiketlerini (preference labels) içerir. Bu çıkış değerleri genellikle 1 ve -1 olarak alınır ve belgeler arasındaki tercih ilişkisini gösterir. Hipotez uzayı (hypothesis space), verilen belge çiftleri arasındaki göreli sıralamayı hesaplayan h fonksiyonlarından oluşur. Kayıp fonksiyonu (loss function) ise, h fonksiyonlarının çıktısı ile gerçek (ground truth) etiketler arasındaki tutarsızlığı ölçer.

### RankBoost
**RankBoost** , belge çiftleri (document pairs) üzerinde sınıflandırma yapmak için **AdaBoost**  algoritmasını temel alır. AdaBoost algoritması, her bir belgeyi (single document) ayrı ayrı sınıflandırırken, RankBoost algoritması belge çiftlerini sınıflandırır. RankBoost algoritması, belge çiftleri üzerinde bir dağılım (distribution) tanımlar ve bu dağılımı, mevcut seçilen zayıf sıralayıcıların (weak rankers) kayıp (loss) değerine göre günceller.

Bir belge çifti (x_{1}, x_{2}) için dağılım (distribution) D değeri şu şekilde tanımlanır:

D(x_1, x_2) = c \cdot \max(0,\varnothing f(x_1, x_2))


Burada ϕ, x_{1}
 ve x_{2}
 arasındaki gerçeğe uygun belge çiftleri tercih sırasını (ground truth pair-wise preference) çıktılar. Bu çıktı:

* Eğer x_{1}
,x_{2}
'ye tercih ediliyorsa −1,
* İkisi eşit tercih ediliyorsa 0,
* x_{2}
, x_{1}
'e tercih ediliyorsa +1 olarak tanımlanır.

c, bir normalizasyon katsayısıdır; çünkü aşağıdaki şartı sağlaması gerekir:

\sum_{(x_1, x_2)} D(x_1, x_2) = 1


Son sıralama (final ranking), eğitim (training) sırasında seçilen zayıf sıralayıcılar (weak rankers) ve onlara atanan ağırlıklar (weights) ile oluşturulur. RankBoost algoritması, sıralayıcıları, belgelerin özellik vektörleri (feature vector) içindeki her bir özelliğin doğrusal sıralamasını (linear ordering) çıktıladığı fonksiyonlar olarak tanımlar.

Her iterasyonda, bir zayıf sıralayıcı **hₜ** seçilir ve ona bir **t** ağırlığı atanır. Ağırlık **t**'yi atamak için üç yaklaşım vardır:

# **hₜ** için herhangi bir zayıf sıralayıcıda, normalizasyon faktörü **Zₜ** t'nin bir fonksiyonu olarak temsil edilebilir. Faktör değerinin benzersiz minimumu, **t**'nin değeri olarak verilir.
# Bu yaklaşım, **hₜ**'nin değeri [0, 1] aralığında olduğunda uygulanabilir. **Zₜ** şu şekilde minimize edilir: Her  {\displaystyle b \in \{-1, 0, 1\}}

  için        {\displaystyle 
\mathbf{W}_{t,b} = \sum_{i=1}^{n} \sum_{u,v: \, y_{u,v}^{(i)}=1} D_{t}(\mathbf{x}_{u}^{(i)}, \mathbf{x}_{v}^{(i)}) \, I_{\{h_{t}(\mathbf{x}_{u}^{(i)}) - h_{t}(\mathbf{x}_{v}^{(i)}) = b\}}
}

                                                                                                     daha sonra                                                                                                                                                    {\displaystyle \alpha_t = \frac{1}{2} \log\left( \frac{\mathbf{W}_{t,-1}}{\mathbf{W}_{t,1}} \right)}


# Bu yaklaşım, **Zₜ**'nin yaklaşık hesaplanmasına dayanmaktadır ve **fₜ**'nin değeri [0, 1] aralığında olduğunda uygulanabilir. Şu şekilde tanımlanır:

{\displaystyle
r_t = \sum_{i=1}^{n} \sum_{u,v: y_u^{(i)}, y_v^{(i)} = 1} D_t(\mathbf{x}_u^{(i)}, \mathbf{x}_v^{(i)}) \left( f_t(\mathbf{x}_u^{(i)}) - f_t(\mathbf{x}_v^{(i)}) \right)
}



Daha sonra

{\displaystyle
\alpha_t = \frac{1}{2} \log\left( \frac{1 + r_t}{1 - r_t} \right)
}



Algoritmanın tasarımcıları, t'yi bulmak için üçüncü yöntemi seçmiştir.

Bir sıralayıcı (ranker) için r değeri şu şekilde tanımlanır:

r=\sum_{x_o,x_1}D(x_o,x_1)(h(x_1)-h(x_0))
=\sum_{x}h(x)\pi(x)



burada:

\pi(x) = \textstyle \sum_{x'} \displaystyle(D(x,x')-D(x',x))



olarak tanımlanır ve belge x'in potansiyeli olarak adlandırılır. Potansiyel \pi(x)

, her iterasyonda mevcut dağılımdan hesaplanır.

Her iterasyon adımında, t'yi minimize etmek için, r'yi maksimize eden zayıf sıralayıcı (weak ranker) seçilir. İterasyonların sonunda, seçilen zayıf sıralayıcılar ve onlara ait ağırlıklar, nihai sıralama fonksiyonunu oluşturur.

### Ranking SVM
Ranking SVM , çiftli sınıflandırma için SVM kullanır. Verilen sorgu kümesi \{q_{i=1}^n\}

 biçiminde belge çiftleri üretilir. Dikkat edilmesi gereken nokta, belge çiftlerinin her bir sorgu için ayrı ayrı üretildiğidir. Yani, belgeler farklı sorgulardan çiftleştirilmez. (x_u^i,x_u^i)

çifti arasındaki çift yönlü tercihlerin gerçek etiket değeri y_{u,v}^i

olarak gösterilir.

Ranking SVM'in formülasyonu şu şekilde verilmiştir:

\min1/2{\|w\|}^2+C\sum_{i=1}^n\sum_{u,v;y_{u,v}^i=1}\xi_{u,v}^i

1/2 ||w||^2 terimi, model w'nun karmaşıklığını kontrol eder. Geleneksel SVM'den farklı olarak, kısıtlamalar belge çiftlerinden oluşturulur. Ranking SVM'deki kayıp fonksiyonu, belge çiftleri üzerinde tanımlanan hinge loss'tur.
Ranking SVM, SVM çerçevesinden birçok özelliği miras aldığı için, marjini maksimize etme yardımıyla iyi bir genelleme yeteneğine sahip olabilir. Ayrıca, Kernel (çekirdek) yöntemleri Ranking SVM'ye uygulanabilir, bu sayede karmaşık doğrusal olmayan problemler de çözülebilir.

### Diğer Çift-Yönlü (Pair-wise) Algoritmalar
Burges ve arkadaşları , sıralama fonksiyonlarını öğrenmek için gradyan iniş yöntemlerini incelemiştir. Bu çalışmada, basit bir olasılıksal maliyet fonksiyonu ile bu maliyet fonksiyonunu en aza indirmek amacıyla geliştirilmiş, sinir ağı tabanlı bir öğrenme algoritması olan RankNet'i önermektedirler.

Cohen ve arkadaşları , iyi bir sıralama uzmanları (ranking experts) birleşimi bulmak için Hedge algoritmasına dayalı çevrimiçi (online) bir öğrenme algoritması tanıtmışlardır. Ayrıca, bir tercih fonksiyonu ile en iyi uyumlu sıralamayı bulmanın NP-tam (NP-complete) olduğunu da göstermişlerdir.

Tsai ve arkadaşları , RankNet  üzerine daha ileri çalışmalar yapmış ve sıralama kaybını ölçmek için Fidelity adını verdikleri yeni bir kayıp fonksiyonu önermişlerdir. Fidelity kaybını verimli bir şekilde minimize etmek için FRank adlı bir öğrenme algoritması geliştirmişlerdir.

## Liste bazında yaklaşım
Belge düzeyinde veya belge çifti düzeyinde tahmin yapan diğer iki yaklaşımdan farklı olarak, liste-tabanlı yaklaşım, bir belgenin gerçek sıralama listesi ile sıralama modelinin ürettiği sıralama listesi arasındaki farkı en aza indirmeye çalışır.

Bu yaklaşımın giriş uzayı, sorgu *q*'ya ait tüm belgeler koleksiyonundan oluşur. Çıkış uzayı ise, bir sorguya ait belgelerin sıralanmış listesini içerir. Varsayım (hipotez) uzayı, verilen belgelerin sıralama düzenini tahmin eden sıralama fonksiyonları kümesini kapsar. Kayıp (loss) fonksiyonu, hipotezin ürettiği sıralama listesi ile giriş uzayındaki gerçek sıralama listesi arasındaki farkı hesaplar.

### RankCosine
Qin ve arkadaşları, kayıp fonksiyonu olarak kosinüs benzerliğini kullanan RankCosine  adlı liste bazlı (list-wise) bir öğrenme-sıralama (LTR) algoritması önermiştir.

Bir sorgu **q** için **n(q)** adet belge (doküman) olduğunu varsayalım. Bu sorgu için gerçek sıralama listesi **g(q)** ile gösterilir ve bu, **n(q)** boyutlu bir vektördür. Belgeler 1’den **n**’e kadar sıralanmıştır ve sıralama listesindeki **k**'nci eleman, listedeki **k**'nci belgenin puanıdır.

Örneğin, elimizde A, B, C, D gibi bir belge koleksiyonu varsa, bu koleksiyonun bir sıralama listesi örneği 2, 3, 1 ve 4 şeklinde olabilir.

RankCosine algoritmasında (ve çoğu diğer liste bazlı algoritmada) puanların mutlak değeri önemli değildir; yalnızca puanlar arasındaki fark önemlidir, yani belgelerin doğrusal sıralaması esas alınır.

Bir sorgu **q** için öğrenme algoritmasının çıktısı **H(q)** olarak tanımlanır. Bu çıktı da **g(q)** ile aynı şekilde **n(q)** boyutlu bir vektördür. Ayrıca çıktı listesindeki **k**'nci eleman, algoritmanın **k**'nci belgeye verdiği puandır.

Bir sorgu q için sıralama kaybı (ranking loss) aşağıdaki gibi tanımlanır:

L(g(p),H(q))={1\over2}(1-\cos(g(p),H(q)))={1\over2}\left(1-{g(q)^TH(q)\over \|g(q)\|\|H(q)\|}\right)



Burada ∥⋅∥ bir vektörün L-2 normunu ifade eder. Bu fonksiyonda kosinüs benzerliği (cosine similarity) kullanıldığı için, bu kayıp fonksiyonuna 'cosine loss' (kosinüs kaybı) adı verilir.

Bu ayarlamada öğrenmenin amacı, eğitim kümesi Q içindeki tüm sorgular üzerinde toplam kayıp fonksiyon değerini minimize etmektir:

L(H)=\sum_{q\in Q}L(g(p),H(q))



Son sıralama fonksiyonu için toplamsal (additive) bir model kullanılır:

H(q)=\sum_{t=1}^T\alpha_th_t(q)



Burada αt birleştirme ağırlığı, h_t(q)

 ise zayıf öğrenici (weak learner) olup, giriş olarak bir belgenin özellik vektörünün bulunduğu satırlardan oluşan bir matrisi alır ve her belgeye bir skor atayan bir çıktı vektörü üretir:

h_t(q):R^{n(q)xd}\rightarrow R^{n(q)}



(Burada d, özellik vektörünün boyutunu belirtir.)

Son sıralama fonksiyonunun parametrelerini eğitmek için aşamalı (stage-wise) açgözlü (greedy) bir arama stratejisi kullanılır. Her adımda, kosinüs kaybı (cosine loss) en küçük olan yeni bir zayıf öğrenici seçilir.

Yeni zayıf öğrenici seçildiğinde, daha önce seçilmiş olanlarla birleştirilir.

Son sıralama fonksiyonunu şöyle tanımlarsak:

H_k(q)=\sum_{t=1}^k\alpha_th_t(q)



(burada h_t(q)

, t adımında seçilen zayıf öğrenicidir),adım  t'deki kosinüs kaybı şu şekilde ifade edilir:

{\displaystyle
L(\mathbf{H}_k) = \sum_{q} \frac{1}{2} \left( 1 - 
\frac{
\mathbf{g}(q)^T \left( \mathbf{H}_{k-1}(q) + \alpha \mathbf{h}_k(q) \right)
}{
\sqrt{
\left( \mathbf{H}_{k-1}(q) + \alpha \mathbf{h}_k(q) \right)^T
\left( \mathbf{H}_{k-1}(q) + \alpha \mathbf{h}_k(q) \right)
}
}
\right)
}

Kayıp fonksiyonunu {\displaystyle \alpha_t}

'ye göre türevleyip sıfıra eşitlediğimizde, {\displaystyle \alpha_t}

'nin optimal değeri şu şekilde elde edilir:

{\displaystyle
\alpha_t = 
\frac{
\sum_{q} \mathbf{W}_{1,k}^T(q) \mathbf{h}_k(q)
}{
\sum_{q} \mathbf{W}_{2,k}^T(q) \left( \mathbf{h}_k(q) \mathbf{g}^T(q) \mathbf{h}_k(q) - \mathbf{g}(q) \mathbf{h}_k^T(q) \mathbf{h}_k(q) \right)
}
}



Burada W_1,_k(q)

 ve W_2,_k(q)

 şu şekilde tanımlanır:

{\displaystyle
\mathbf{W}_{1,k}(q) = 
\frac{
\mathbf{g}^T(q) \mathbf{H}_{k-1}(q) \mathbf{H}_{k-1}(q) - \mathbf{H}_{k-1}^T(q) \mathbf{H}_{k-1}(q) \mathbf{g}(q)
}{
\left\| \mathbf{H}_{k-1}(q) \right\|^{3/2}
}
}



{\displaystyle \mathbf{W}_{2,k}(q) = \frac{\mathbf{H}_{k-1}(q)}{\left\| \mathbf{H}_{k-1}(q) \right\|^{3/2}} }



Bu denklemleri kullanarak optimal {\displaystyle \alpha_t}

 ağırlığını hesaplarız, her zayıf öğrenici adayı için kosinüs kaybını değerlendirir ve en küçük kayba sahip olanı k'ıncı zayıf öğrenici olarak seçeriz.

Sonuç olarak, bir zayıf öğreniciler koleksiyonu ve bunların birleşim katsayıları elde edilir ve bu birleşim, son sıralama fonksiyonunu oluşturur.

### ListNet
**ListNet** , sıralama kaybını permütasyonlar üzerindeki olasılık dağılımına dayalı olarak hesaplayan bir başka LTR (Learning to Rank) algoritmasıdır. Permütasyonlar üzerindeki dağılım, olasılık teorisinde iyi bir şekilde incelenmiştir. **Luce modeli** ve **Mallows modeli** gibi ünlü dağılım modelleri bulunmaktadır. Sıralanmış bir listeyi belge listesinin bir permütasyonu olarak ele alabileceğimizden, bu modeller kolayca uygulanabilir. **ListNet**, **Luce modelini** LTR için uygular.

İlgililik puanları, h adlı puanlama fonksiyonu tarafından s = (s_j)_{j=1}^m
 şeklinde verilir; burada s_j = h(x_j)
 olur. Luce modeli, belgelerin her bir olası permutasyonuna bir olasılık atar.

{\displaystyle 
P(\pi \mid s) = \prod_{j=1}^{m} \frac{ \varphi(s_{\pi^{-1}(j)}) }{ \sum_{u=j}^{m} \varphi\left( s - 1_{\pi(u)} \right) } 
}



Burada 1(j), listedeki veya permütasyondaki j. sıraya yerleştirilen belgeyi gösterir.

φ bir dönüşüm fonksiyonudur.

Her bir öğe aşağıdaki örnekte gösterildiği gibi ifade edilir:

{\displaystyle 
\frac{ \varphi\left( s_{\pi^{-1}(j)} \right) }{ \sum_{u=1}^{m} \varphi\left( s_{\pi^{-1}(u)} \right) }
}



bu bir koşullu olasılığı temsil eder.

Şöyle varsayalım: elimizde bir sorgu q ile ilişkili üç belge var: **X, Y** ve **Z**.

Permütasyon olasılığı 
(XYZ)

, aşağıdaki üç olasılığın çarpımı olarak ifade edilir:

P = P_1 \times P_2 \times P_3



* **P1**: X belgesinin en üst sıraya yerleşme olasılığıdır.
* **P2**: X seçildikten sonra Y'nin ikinci sırada yer alma koşullu olasılığıdır.
* **P3**: X ve Y seçildikten sonra Z'nin üçüncü sırada yer alma koşullu olasılığıdır.

Bu örnekte, P3 doğrudan 1'e eşittir.

Verilen bir sorgu q için, ListNet, fonksiyon f ile puanlar üzerinden sıralama olasılık dağılımını hesaplar. Ayrıca, doğru listeye dayalı başka bir sıralama olasılık dağılımı P_y(\pi)

 tanımlar. Ardından, bu iki dağılım arasındaki K-L (Kullback-Leibler) diverjansını kullanır ve kayıp fonksiyonunu şu şekilde hesaplar:

{\displaystyle
L(f; \mathbf{x}, \pi_y) = D\left( P\left( \pi \mid \varphi(f(w, \mathbf{x})) \right) \,\|\, P_y(\pi) \right)
}



Daha sonra, algoritma K-L diverjansı kaybını minimize etmek için gradyan inişi tabanlı bir sinir ağı kullanır.

### Diğer Liste Bazlı Algoritmalar
**LambdaRank** , basit ve esnek algoritmalar sınıfıdır ve dolaylı maliyet fonksiyonları kullanır. Burges ve arkadaşları , bilgi erişiminde kalite ölçütlerinin optimize edilmesinin zor olduğunu belirtmektedir çünkü bunlar, verilen bir sorgu için döndürülen belgelerin sıralanmış sırasına yalnızca model puanları üzerinden bağlıdır. Maliyetlerin model parametrelerine göre türevleri ya sıfırdır ya da tanımlanmamıştır. Bu nedenle, elde edilen dolaylı maliyet fonksiyonunun konveks olabilmesi için gerekli koşulları vermektedirler.

Taylor ve arkadaşları , belgelerin sıralama dağılımlarından türetilen yeni bir eğitim hedefleri ailesi sunmaktadırlar. Bu yaklaşıma **SoftRank** adını vermektedirler. Çoğu bilgi erişimi uygulaması, yalnızca belgelerin sıralarına bağlı olan değerlendirme metriklerini kullanır. Ancak, çoğu sıralama fonksiyonu, sıralama üretmek için sıralanan belge puanlarını üretir. Bu nedenle bilgi erişimi metrikleri, sıralama nedeniyle puanlar açısından pürüzsüz değildir. Ayrıca, Normalized Discounted Cumulative Gain (NDCG) üzerine bir yaklaşık çözüm sunmuş ve **SoftNDCG**'yi önermişlerdir.

Yue ve arkadaşları , birkaç öğrenme tekniğinin doğrudan **mean average precision (MAP)** için optimize edilerek geliştirilmiş olduğunu ve mevcut yöntemlerin küresel optimal çözümü bulamadığını belirtmektedirler. Küresel bir optimal çözümü verimli bir şekilde bulan genel bir **SVM** öğrenme algoritması sunmuşlardır ve bu algoritma, MAP'in doğrudan bir gevşetilmesine yönelik bir çözüm sunmaktadır.

## Tarihçe
Norbert Fuhr, 1992 yılında MLR'nin genel fikrini tanıtarak bilgi getiriminde öğrenme yaklaşımlarını parametre tahmini bir genellemesi olarak açıklamıştır; bu yaklaşımdan belirli bir varyant (polinom regresyonu kullanarak) üç yıl önce kendisi tarafından yayımlanmıştır. Bill Cooper, aynı amaçla 1992'de lojistik regresyonu önermiş  ve bunu Berkeley araştırma grubu ile TREC için başarılı bir sıralama fonksiyonu eğitmek amacıyla kullanmıştır. Manning ve ark., bu erken çalışmaların, sınırlı eğitim verisi ve zayıf makine öğrenme teknikleri nedeniyle o dönemde sınırlı sonuçlar elde ettiğini belirtmişlerdir.

2000'lerin ortalarından itibaren NeurIPS, SIGIR ve ICML gibi çeşitli konferanslarda sıralama öğrenme (learning-to-rank) problemi üzerine atölye çalışmaları düzenlenmiştir.

### Arama motorları tarafından pratik kullanım
Ticari web arama motorları, 2000'lerin başından itibaren makine öğrenimi tabanlı sıralama sistemlerini kullanmaya başlamıştır. Bunlardan ilki, AltaVista'dır (sonrasında teknolojisi Overture tarafından satın alınmış ve ardından Yahoo'ya geçmiştir), bu arama motoru Nisan 2003'te gradyan artırma (gradient boosting) ile eğitilmiş bir sıralama fonksiyonu başlatmıştır.

Bing'in arama motorunun, 2005'te Microsoft Research'te icat edilen RankNet algoritması ile çalıştığı söylenmektedir.

Kasım 2009'da, Rusya'nın arama motoru Yandex, kendi yeni özel MatrixNet algoritmasını kullanmaya başladıktan sonra arama kalitesini önemli ölçüde artırdığını duyurmuştur. Bu algoritma, gradyan artırma yönteminin bir varyantıdır ve unutkan (oblivious) karar ağaçlarını kullanmaktadır. Son zamanlarda, Yandex kendi arama motorunun üretim verilerine dayanan makine öğrenimi tabanlı bir sıralama yarışması olan "Internet Mathematics 2009"u düzenlemiştir. Yahoo da 2010 yılında benzer bir yarışma düzenlemiştir.

2008 yılı itibarıyla, Google'dan Peter Norvig, arama motorlarının yalnızca makine öğrenimi tabanlı sıralama kullandığını reddetmiştir. Cuil'in CEO'su Tom Costello, ellerinde yapılmış modellerin, tıklama oranı (click-through rate) veya açılış sayfasında geçirilen süre gibi ölçütlerle ölçüldüğünde makine öğrenimi tabanlı modelleri geride bırakabileceğini öne sürmüştür. Bunun nedeni, makine öğrenimi tabanlı modellerin "insanların beğendiklerini söylediklerini, gerçek beğenilerini değil, öğrenmesidir."

Ocak 2017'de bu teknoloji, açık kaynak arama motoru Apache Solr'a dahil edilmiştir. Ayrıca açık kaynaklı OpenSearch ve Elasticsearch'te de mevcuttur. Bu uygulamalar, sıralama öğrenmenin kurumsal arama için yaygın olarak erişilebilir olmasını sağlamaktadır.

## Güvenlik Açıkları
**Benzer şekilde, bilgisayarla görme alanındaki tanıma uygulamalarına benzer olarak, son zamanlarda geliştirilen sinir ağı tabanlı sıralama algoritmalarının, hem adaylar hem de sorgular üzerinde gizli düşman saldırılarına karşı duyarlı olduğu bulunmuştur.** Küçük, insanlar tarafından fark edilemeyen bozulmalarla sıralama sırası keyfi bir şekilde değiştirilebilir. Ayrıca, modelden bağımsız ve aktarılabilir düşman örneklerinin mümkün olduğu keşfedilmiştir; bu da derin sıralama sistemlerine, alt yapılarının uygulanmalarına erişim gerektirmeden kara kutu düşman saldırılarının yapılmasını sağlar.

Buna karşılık, bu tür sıralama sistemlerinin dayanıklılığı, **Madry savunması** gibi düşman savunmalarıyla geliştirilebilir.

## Kaynakça


#