Sıralama (bilgi erişim)

Sorgu sıralaması, arama motorlarının arkasındaki bilimsel/mühendislik disiplini olan bilgi alma (BA)  temel sorunlardan biridir ve sorguyla eşleşen bir belge koleksiyonu D verildiğinde , sorun , D' deki belgeleri bazı ölçütlere göre sıralamak, yani sıralamaktır; böylece "en iyi" sonuçlar, kullanıcıya gösterilen sonuç listesinde erken görünür. Bilgi alma açısından sıralama, bilgisayar biliminde önemli bir kavramdır ve arama motoru sorguları ve öneri sistemleri gibi birçok farklı uygulamada kullanılır. Arama motorlarının çoğu, kullanıcılara doğru ve alakalı sonuçlar sağlamak için sıralama algoritmaları kullanır.

Tarih

Sayfa sıralaması kavramı 1940'lara dayanır ve fikir ekonomi alanında ortaya çıkmıştır. 1941'de Wassily Leontief, bir ülkenin sektörünü, ona kaynak sağlayan diğer sektörlerin önemine göre değerlendirmenin yinelemeli bir yöntemini geliştirdi. 1965'te Kaliforniya Üniversitesi, Santa Barbara'dan Charles H Hubbell, onları destekleyen kişilerin önemine göre bireylerin önemini belirlemeye yönelik bir teknik yayınladı.

Gabriel Pinski ve Francis Narin dergileri sıralamak için bir yaklaşım geliştirdiler.  Kuralları, bir derginin diğer önemli dergiler tarafından atıf alması durumunda önemli olduğuydu. Cornell Üniversitesi'nde bilgisayar bilimcisi olan Jon Kleinberg, PageRank'e neredeyse aynı yaklaşımı geliştirdi ve buna Hypertext Induced Topic Search veya HITS adı verildi ve web sayfalarını "merkezler" ve "otoriteler" olarak ele aldı .

Google'ın PageRank algoritması, 1998 yılında Google'ın kurucuları Sergey Brin ve Larry Page tarafından geliştirilmiştir ve Google'ın arama sonuçlarında web sayfalarını sıralama yönteminin önemli bir parçasıdır. Yukarıdaki tüm yöntemler, bağlantıların yapısını kullandıkları ve yinelemeli bir yaklaşım gerektirdikleri için bir bakıma benzerdir.

Sıralama modelleri

Sıralama fonksiyonları çeşitli yollarla değerlendirilir; en basitlerinden biri, sabit bir k için ilk k en iyi sıralanmış sonucun hassasiyetini belirlemektir ; örneğin, birçok sorgu için ortalama olarak alakalı olan ilk 10 sonucun oranı.

IR modelleri genel olarak dört türe ayrılabilir: Boole modelleri veya BIR, Vektör Uzay Modelleri, Olasılıksal Modeller ve Öğrenerek Sıralama (LTR) modeli vardır.  Literatürde, geri alma modelleri arasında çeşitli karşılaştırmalar bulunabilir (örneğin,  ).

Boolean Modelleri

Boolean Modeli veya BIR, her sorgunun cebirsel ifadelerle ilişkisel cebirin temel prensiplerini izlediği ve belgelerin birbirleriyle tamamen eşleşmediği sürece getirilmediği basit bir temel sorgu modelidir. Sorgu ya belgeyi getir (1) ya da belgeyi getirmiyor (0) olduğundan, bunları sıralamak için bir metodoloji yoktur.

Vektör Uzay Modeli

Boolean Modeli yalnızca tam eşleşmeleri getirdiğinden, belgelerin kısmen eşleşmesi sorununu ele almaz. Vektör Uzay Modeli, her biri ağırlıklarla atanmış dizin öğelerinin vektörlerini tanıtarak bu sorunu çözer. Ağırlıklar, belgeler mevcutsa pozitif (tamamen veya bir dereceye kadar eşleşmişse) ile negatif (eşleşmemişse veya tamamen zıt şekilde eşleşmişse) arasında değişir. Terim Sıklığı - Ters Belge Sıklığı (tf-idf ), ağırlıkların terimler (örneğin kelimeler, anahtar kelimeler, ifadeler vb.) ve boyutların korpus içindeki kelime sayısı olduğu en popüler tekniklerden biridir.

Sorgu ve belge arasındaki benzerlik puanı, kosinüs benzerliği kullanılarak sorgu ağırlık vektörü ile belge ağırlık vektörü arasındaki kosinüs değeri hesaplanarak bulunabilir . İstenilen belgeler benzerlik puanına göre sıralanarak getirilebilir ve en yüksek puana sahip veya sorgu vektörüyle en alakalı olan ilk k belge getirilebilir.

Olasılıksal Model

Olasılıksal modelde, olasılık teorisi, geri alma sürecini matematiksel terimlerle modellemek için temel bir araç olarak kullanılmıştır. Bilgi geri alma olasılık modeli, 1960 yılında Maron ve Kuhns tarafından tanıtılmış ve Roberston ve diğer araştırmacılar tarafından daha da geliştirilmiştir. Spack Jones ve Willett'e (1997) göre: Olasılıksal kavramları tanıtmanın gerekçesi açıktır: IR sistemleri doğal dille ilgilenir ve bu, bir sistemin belirli bir sorgu için hangi belgenin alakalı olacağını kesin olarak belirtmesini sağlamak için çok belirsizdir.

Model, olasılık teorisini bilgi almaya uygular (Bir olayın gerçekleşme olasılığı %0 ile %100 arasındadır). Yani, olasılık modelinde, alaka olasılık cinsinden ifade edilir. Burada, belgeler azalan alaka olasılığına göre sıralanır. IR sürecindeki belirsizlik unsurunu dikkate alır. Yani, sistem tarafından alınan belgelerin belirli bir sorguyla alakalı olup olmadığı konusundaki belirsizlik.

Olasılık modeli, bir belgenin belirli bir sorguyla alakalı olma olasılığını bazı yöntemlere dayanarak tahmin etmeyi ve hesaplamayı amaçlar. Bilgi alma bağlamındaki "olay", bir sorgu ile bir belge arasındaki alakalı olma olasılığını ifade eder. Diğer IR modellerinden farklı olarak, olasılık modeli alakalılığı tam bir yanlış veya eşleşme ölçümü olarak ele almaz.

Model, sorgular ve belgeler arasındaki alaka olasılığını belirlemek için çeşitli yöntemler benimser. Olasılık modelindeki alaka, sorgular ve belgeler arasındaki benzerliğe göre değerlendirilir. Benzerlik yargısı ayrıca terim sıklığına bağlıdır.

Böylece, yalnızca bir terimden (B) oluşan bir sorgu için, belirli bir belgenin (Dm) alakalı olarak değerlendirilme olasılığı, sorgu terimini (B) gönderen ve belgeyi (Dm) alakalı olarak değerlendiren kullanıcıların, terimi (B) gönderen kullanıcı sayısına oranıdır. Maron ve Kuhn'un modelinde gösterildiği gibi, belirli bir sorgu terimini (B) gönderen kullanıcıların bireysel bir belgeyi (Dm) alakalı olarak değerlendirme olasılığı olarak gösterilebilir.

Gerard Salton ve Michael J. McGill'e göre, bu modelin özü, ilgili belgelerde çeşitli terimlerin bulunma olasılığına ilişkin tahminler hesaplanabiliyorsa, ilgili olması veya olmaması durumunda bir belgenin geri alınma olasılıklarının tahmin edilebileceğidir.

Birkaç deney, olasılıksal modelin iyi sonuçlar verebileceğini göstermiştir. Ancak, bu tür sonuçlar Boole veya Vektör Uzay modeli kullanılarak elde edilenlerden yeterince iyi olmamıştır.

Öğrenerek Sıralama (LTR)

Sıralama problemlerini çözmek üzere makine öğrenmesi tekniklerini kullanan algoritmaları ifade eder. Bu yaklaşımda genellikle sorgu-belge çiftleri özellik vektörleriyle temsil edilir ve bir makine öğrenmesi modeli bu vektörleri kullanarak her belgeye bir puan verir. Nihai sıralama, belgelerin bu puanlara göre dizilmesiyle elde edilir.

LTR algoritmaları, kullandıkları kayıp fonksiyonlarına göre yaygın olarak üç ana gruba ayrılır: noktasal (pointwise), ikili (pairwise) ve listesel (listwise). Geleneksel LTR yöntemlerinin çoğu, belgeleri genellikle alaka olasılıklarına göre tek tek değerlendiren tek değişkenli (uni-variate) bir puanlama yaklaşımını benimser. Ancak bu yaklaşım, belgeler arasındaki ilişkileri ve yerel bağlam bilgisini yakalamada yetersiz kalabildiği için alt-optimal olabilir.

Bu sınırlamayı aşmak amacıyla, bir belge listesini bütün olarak ele alan ve belgeler arası bağlamı modelleyebilen çok değişkenli (multivariate) puanlama yöntemleri geliştirilmiştir. Bu yeni yaklaşımlar, [kaynak makalede belirtildiği gibi] başlangıçtaki bir sıralamaya bağlı kalmadan doğrudan bir belge kümesine uygulanabilen permütasyondan bağımsız (permutation-invariant) modeller gibi yenilikçi çözümlere imkan tanımaktadır.

Değerlendirme Ölçütleri

Değerlendirmenin en yaygın ölçütleri kesinlik, geri çağırma ve f-puanıdır. Bunlar, sıralanmamış belge kümeleri kullanılarak hesaplanır. Modern arama motorlarında standart olan sıralı alma sonuçlarını değerlendirmek için bu ölçütlerin genişletilmesi veya yeni ölçütlerin tanımlanması gerekir. Sıralı alma bağlamında, uygun alınan belge kümeleri doğal olarak en iyi k alınan belge tarafından verilir. Bu tür kümelerin her biri için kesinlik ve geri çağırma değerleri çizilerek bir kesinlik-geri çağırma eğrisi elde edilebilir.

Kesinlik

Kesinlik, alma işleminin kesinliğini ölçer. İlgili belgelerin gerçek kümesi I ile ve alınan belgelerin kümesi O ile gösterilirse, kesinlik şu şekilde verilir:

$Precision={\frac {|\{I\}\cap \{O\}|}{|\{O\}|}}$

Hatırlamak

Geri çağırma, IR sürecinin tamamlanmışlığının bir ölçüsüdür. İlgili belgelerin gerçek kümesi I ile ve alınan belgelerin kümesi O ile gösterilirse, geri çağırma şu şekilde verilir:

$Recall={\frac {|\{I\}\cap \{O\}|}{|\{I\}|}}$

F1 Puanı

F1 Puanı, kesinlik ve geri çağırma ölçüsünü birleştirmeye çalışır. İkisinin harmonik ortalamasıdır. P kesinlik ve R geri çağırma ise F-Puanı şu şekilde verilir:

$F_{1}=2\cdot {\frac {P\cdot R}{P+R}}$

Sayfa Sıralaması Algoritması

PageRank algoritması, bağlantılara rastgele tıklayan bir kişinin belirli bir sayfaya ulaşma olasılığını temsil etmek için kullanılan bir olasılık dağılımı üretir. PageRank, herhangi bir boyuttaki belge koleksiyonları için hesaplanabilir. Birçok araştırma makalesinde, hesaplama sürecinin başında dağıtımın koleksiyondaki tüm belgeler arasında eşit olarak bölündüğü varsayılır. PageRank hesaplamaları, yaklaşık PageRank değerlerini teorik gerçek değeri daha yakından yansıtacak şekilde ayarlamak için koleksiyonda birkaç geçiş gerektirir. Formüller aşağıda verilmiştir:

yani bir sayfa u için PageRank değeri, B _u kümesinde (u sayfasına bağlantı veren tüm sayfaları içeren küme ) bulunan her bir sayfa v için PageRank değerlerinin, v sayfasından gelen bağlantı miktarı L (v )'ye bölünmesine bağlıdır .

HITS Algoritması

PageRank'e benzer şekilde, HITS sayfaların alakalılığını analiz etmek için Bağlantı Analizi kullanır ancak yalnızca küçük alt grafik kümeleri üzerinde çalışır (tüm web grafiği yerine) ve sorguya bağımlıdır. Alt grafikler, en yüksek sırada yer alan sayfaların getirildiği ve görüntülendiği merkezlerdeki ve yetkililerdeki ağırlıklara göre sıralanır.

Yeniden sıralama

Yeniden sıralama, birincil sıralama kriteri olan bilgi alaka düzeyini, bilgi tazeliği ve çeşitliliği gibi ek hedefler/kısıtlamalarla dengelemek için öğelerin orijinal sıralamasının ayarlanması anlamına gelir.

Son ürün sıralamasını oluştururken birden fazla hedefi hesaba katmak, zaman alıcı bir optimizasyon sorununa yol açar ve önemli araştırma çabaları, kullanıcının sıralamayı elde etmede algılanan gecikmeyi kontrol altında tutmak için optimizasyonu hızlandırmaya odaklanmıştır.

Ayrıca bakınız

• Sıralamayı öğrenme : Makine öğreniminin sıralama problemine uygulanması
• Anlamsal arama
• Kişiselleştirilmiş arama