BM25 tam metin arama algoritmasını anlamak

 (emschwartz.me)
1 puan yazan GN⁺ 2024-11-21 | 1 yorum | WhatsApp'ta paylaş
  • BM25, kesin anahtar kelime eşleştirmesinin gerektiği tam metin aramada hâlâ yaygın olarak kullanılır ve vektör benzerliği aramasını tamamlayan hibrit aramanın bir ayağını oluşturur
  • BM25, olasılığı doğrudan hesaplamadan belgeleri sıralamak için, sorgu terimi bazındaki ağırlıkları toplayarak daha ilgili görünen belgeleri öne yerleştirir
  • Skor; IDF, belge içi terim sıklığı ve belge uzunluğu normalizasyonundan oluşur; nadir kelimeler daha güçlü yansıtılır, tekrar eden görünümler ise giderek daha az ödüllendirilir
  • k1 tekrar eden görünümlere verilen ödülün azalma hızını, b ise belge uzunluğu normalizasyonunun şiddetini ayarlar; genellikle k1=1.2~2, b=0.75 kullanılır
  • BM25 skoru gerçek ilgililik olasılığı olmadığından genel amaçlı bir karşılaştırma değeri gibi kullanılması zordur; aynı belge koleksiyonu içinde karşılaştırıldığında anlamlıdır

BM25’in çözmeye çalıştığı arama problemi

  • BM25 veya Best Match 25, tam metin aramada yaygın olarak kullanılan bir algoritmadır
    • Lucene/Elasticsearch ve SQLite gibi sistemlerde varsayılan olarak kullanılır
    • Son dönemde tam metin arama ile vektör benzerliği aramasını birleştiren hibrit arama yaygınlaştı
  • Kişiselleştirilmiş içerik akışlarında yalnızca vektör benzerliği araması, kesin anahtar kelime işlemeyi karşılamakta yetersiz kalabilir
    • İlgi alanı Solid.js ise, yalnızca vektör benzerliği araması kullanıldığında Solid’den çok React ile ilgili içerikler daha fazla çıkabilir
  • Temel soru, bir belgenin BM25 skorunu birden fazla sorgu arasında karşılaştırarak o belgenin hangi sorguya en iyi uyduğuna karar verilip verilemeyeceğidir

Olasılık sıralama ilkesi ve BM25’in yaklaşımı

  • Tam metin aramanın amacı, sorguya göre olası belge kümesi içinden en ilgili belgeleri bulmaktır
  • Gerçek ilgililik kesin olarak bilinemediği için arama, belgeleri sorguyla ilgili olma olasılığına göre sıralamaya çalışır
    • Bu fikir Probability Ranking Principle olarak adlandırılır
  • BM25 gibi sözlük tabanlı aramalar yalnızca sorguyu ve belge koleksiyonu içindeki belgelerin özelliklerini kullanır
    • Vektör benzerliği araması, harici metin derlemleriyle eğitilmiş embedding modellerini kullanarak sorgu ve belgelerin anlamını temsil edebilir

BM25 skorunu oluşturan bileşenler

  • BM25, sorgu ve belge koleksiyonundan gelen çeşitli sinyalleri birleştirerek skoru hesaplar

  • Sorgu terimi

    • Arama sorgusu birden fazla terimden oluşuyorsa, her terim için skor hesaplanır ve ardından toplanır

  • Ters belge sıklığı (IDF)

    • Belirli bir arama teriminin tüm belge koleksiyonunda ne kadar nadir olduğunu gösterir
    • the, and gibi yaygın kelimelerin bilgi değerinin düşük olduğu varsayılır ve nadir kelimelerin önemi artırılır

  • Belge içi terim sıklığı

    • Arama teriminin belirli bir belgede kaç kez geçtiğini yansıtır
    • Aynı terim daha çok tekrarlandıkça ilgili olma olasılığının arttığı kabul edilir; ancak BM25 tekrar eden görünümlere azalan getiri etkisi uygular

  • Belge uzunluğu

    • Uzun belgelerde, sırf uzun oldukları için arama terimleri daha çok geçebilir
    • BM25, uzun belgelerin haksız biçimde yüksek skor almamasını sağlamak için belge uzunluğunu ortalama belge uzunluğuyla karşılaştırarak normalize eder

BM25 formülünün her bir bölümü

  • BM25’in toplam skoru, belge D ve sorgu Q için her sorgu terimi q_inin skorlarını toplama biçimindedir
    • D: hedef belge
    • Q: tüm sorgu
    • n: sorgu terimi sayısı
    • q_i: her bir sorgu terimi

  • IDF: Koleksiyonda nadir kelimeleri daha güçlü yansıtma

    • IDF terimi, sorgu teriminin tüm belge koleksiyonunda ne kadar nadir olduğunu hesaplar
    • N: koleksiyondaki toplam belge sayısı
    • n(q_i): sorgu terimini içeren belge sayısı
    • N - n(q_i): sorgu terimini içermeyen belge sayısı
    • Yaygın terimler birçok belgede geçtiği için skora etkileri küçülür
    • Nadir terimler yalnızca az sayıda belgede geçtiği için skora daha güçlü yansıtılır
    • Formüldeki 0.5 ve 1, terim çok nadir ya da çok yaygın olduğunda sonucun aşırı dalgalanmasını yumuşatma rolü oynar

  • Terim sıklığı: Tekrarı yansıtır ama sınırsız ödüllendirmez

    • Belge içi terim sıklığı, belirli bir sorgu teriminin belirli bir belgede ne kadar sık geçtiğini yansıtır
    • f(q_i, D): sorgu terimi q_inin belge Dde geçme sıklığı
    • k1: genellikle 1.2 ile 2 arasında ayarlanan bir tuning parametresi
    • BM25, terim tekrarını skora yansıtır; ancak tekrar arttıkça ek skor artışının büyüklüğü azalır
    • k1, terim tekrarına verilen ödülün ne kadar hızlı azalacağını kontrol eder

  • Belge uzunluğu normalizasyonu: Uzun belgelerin avantajını ayarlama

    • Belge uzunluğu normalizasyonu, hedef belgenin uzunluğunu koleksiyonun ortalama belge uzunluğuyla karşılaştırır
    • |D|: hedef belgenin uzunluğu
    • avgdl: koleksiyonun ortalama belge uzunluğu
    • b: belge uzunluğu normalizasyonunun şiddetini kontrol eden bir tuning parametresi
    • Ortalamadan uzun belgelerde arama terimlerinin daha sık geçme olasılığı bulunduğundan, nihai formülün paydasında dezavantaj uygulanır
    • b=0 olduğunda belge uzunluğu normalizasyonu kapatılır; b=1 olduğunda tamamen uygulanır
    • b genellikle 0.75 olarak ayarlanır

BM25’in temel fikri

  • BM25, Probability Ranking Principle’a dayanır; ancak belge ilgililiğinin gerçek olasılığını hesaplamak neredeyse imkânsızdır
  • Aramada önemli olan kesin olasılık değerinden çok belgelerin sırası olduğundan, sıralamayı etkilemeyen terimler formülden çıkarılarak hesaplama pratik hâle getirilir
  • Bu nedenle BM25, olasılığın kendisini değil ağırlıkları hesaplar
  • Robertson/Sparck Jones Weight, ilgili belge sayısını ve sorgu terimini içeren belge sayısını kullanarak olasılığı tahmin etme yöntemidir
    • r: sorgu terimini içeren ilgili belge sayısı
    • N: koleksiyondaki toplam belge sayısı
    • R: koleksiyondaki ilgili belge sayısı
    • n: sorgu terimini içeren belge sayısı
  • Bu yöntemin en büyük sınırlaması, önce hangi belgelerin ilgili olduğunu bilmek zorunda olmasıdır

“Çoğu belge ilgili değildir” varsayımı

  • BM25’i geliştirenler, rastgele bir sorgu için belgelerin çoğunun ilgili olmadığını varsayar
  • İlgili belge sayısının ihmal edilecek kadar küçük olduğu kabul edilirse R = r = 0 olarak alınabilir
  • Bu değer Robertson/Sparck Jones Weight formülüne yerleştirildiğinde, BM25’te kullanılan IDF terimine çok benzer bir biçim ortaya çıkar
  • İlgililik bilgisini önceden gerektirmeden aynı teorik temeli koruduğu için BM25 çok daha pratik hâle gelmiştir
  • Victor Lavrenko bunu "very impressive leap of faith" diye ifade eder

BM25 skorlarını karşılaştırmanın kapsamı

  • BM25 skorlarını genel olarak doğrudan karşılaştırmak zordur
    • 0 ile 1 arasında bir olasılık skoru üretmez
    • Bir belgenin ilgili olma gerçek olasılığını tahmin etmeye çalışan bir algoritma da değildir
    • Belirli bir koleksiyon içinde, sorguya göre ilgili olma olasılığı sırasını yaklaşık olarak çıkarmaya odaklanır
  • Daha yüksek BM25 skoru, belgenin daha ilgili olma olasılığının yüksek olduğuna dair bir sinyaldir; ancak gerçek ilgililik olasılığı değildir
  • Aynı belge koleksiyonu içindeki aynı belge için birden fazla sorgunun BM25 skorları karşılaştırılabilir
    • BM25 her sorgu teriminin skorunu topladığı için, iki sorgu teriminin skorlarını karşılaştırmak ile iki tam sorgunun skorlarını karşılaştırmak arasında anlamsal bir fark olmadığı düşünülebilir
  • Önemli kısıt aynı belge, aynı koleksiyon olmasıdır
    • BM25, koleksiyon içindeki IDF’yi ve ortalama belge uzunluğunu kullanır
    • Koleksiyon değişirse skorlar da değişebilir; bu yüzden zaman içinde skor karşılaştırması garanti edilmez
  • Kişiselleştirilmiş içerik akışlarında, her kullanıcı ilgi alanı için tam metin arama çalıştırıp BM25 skorlarını karşılaştırarak hangi içeriğin hangi ilgi alanına daha iyi uyduğunu belirlemek için kullanılabilir

Daha fazla okuma

İlgili okumalar

1 yorum

 
GN⁺ 2024-11-21
Hacker News yorumları

  • Genel arama için https://typesense.org/ kullanıyorum; artık hibrit aramayı da desteklediği için deneyen var mı merak ediyorum

    • Hibrit aramada kullandım ve oldukça iyi çalışıyor
      Typesense’in burada anıldığını görmek güzel; küçük ölçekli RAG projeleri için çoğu zaman çok uygun olur ama nedense pek bilinmiyor
      Dağıtımı kolay, varsayılanları makul, dokümantasyonu iyi ve kümeleme de nispeten kolay; daha derine inmek gerektiğinde de yeterince performanslı ve güçlü
    • Biz de kullanıyoruz ve genel olarak memnunuz
      Ancak embedding modelini harici bir sağlayıcıdan kullanırsanız gecikme 500ms+ gibi saçma derecede yüksek oluyor; bu yüzden doğrudan küme içinde barındırmak daha iyi
      Hibrit arama kalitesi iyi, fakat ayar seçenekleri çok sınırlı ve skorlar da sonuç kümesi içindeki sıralama dışında epey opak

  • Son dönemde vektör tabanlı semantik arama gelişmişken, bugünlerde anahtar kelime + semantik arama hibriti için kullanılan güncel arama stack’inin ne olduğunu merak ediyorum

    • Genel amaçlı arama stratejisi, gerçekte hedeflediğiniz işe göre tamamen değişir
      Yakın zamanda, her birinde 10 serbest metin alanı bulunan yaklaşık 3 milyon anket aldık ve şirketin aksiyon alması gereken maddeleri bulmamız gerekiyordu
      Birkaç küçük sınıflandırıcı model kullandık; ilk 10 bin kayıtta ortaya çıkan gürültüye bakıp yaygın kelimeleri elle çıkardıktan ve model yanıtlarına ağırlık verdikten sonra neredeyse kusursuz çalıştı
      Bu tür işler “programlama”dan çok, çeşitli araçların kara kutu çıktılarını test vakalarına ve müşteriye iyi görününceye kadar ayarlamaya benziyor
      Bu arada küçük bir sunucuda Node.js ile birkaç küçük Hugging Face modelini birbirine bağlayarak işledik
    • Ticari ve açık kaynak hibrit arama ürünlerinin çoğu BM25 + embedding tabanlı vektör benzerlik araması kullanıyor gibi görünüyor
      Sonuçlar genellikle karşılıklı sıra füzyonu (RRF) ile birleştiriliyor
      RRF makalesi şaşırtıcı derecede basit olduğu için etkileyici; makale de yalnızca 2 sayfa: https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf
    • Tek bir stack’e odaklanmayın; her iş için en uygun aracı kullanmaya hazır olmak gerekir
      BM25 türü işler için Elasticsearch, basit ve hızlı vektör araması için Turbopuffer, belirli sorgu sonuçlarını önceden hesaplamak ya da fiyat gibi sık değişen dinamik özellikler için Redis de kullanılabilir
      Bunları scatter/gather yaklaşımıyla birleştirmenin iyi olduğunu düşünüyorum
      Arama stack’inin dışında neredeyse her zaman yeniden sıralama için bir çıkarım servisi katmanı olur; ideal durumda bu, diğer makine öğrenimi altyapılarına benzer basit bir servis haline gelir
      Kullanıcı sorgusunu anlayıp “ID ile getir”i bir sisteme, “bulanık semantik arama”yı başka bir sisteme yönlendirmek gibi routing de neredeyse her zaman gerekir
      Bunların veri yapıları çok farklıdır ve arama genelde birbirinden farklı kullanım senaryolarını genişçe kapsar
      Her şeyi tek bir sisteme tıkıştırmak bence bir antipattern
      Her sistem farklı iş yüklerine uygundur; yerleşik çıkarım özelliklerinin, makine öğrenimi mühendislerinin aşina olduğu genel makine öğrenimi araçlarının hızına yetişmesi zordur
      Elasticsearch Learning to Rank ile denedim ama umutsuz bir işti
      Yine de geniş kullanım senaryolarını tek bir stack ile çözme girişimleri arasında Vespa muhtemelen en iyisi
    • BM25’i ele alan harika bir yazı
      txtai’nin yazarı olarak, txtai Python’da arrays paketi aracılığıyla performanslı bir BM25 indeksi uygular ve terim frekansı vektörlerini SQLite’ta saklar
      txtai’nin hibrit indeksleme yaklaşımı, BM25 skorları normalize edilmişse konveks kombinasyonu, normalize edilmemişse karşılıklı sıra füzyonu (RRF) destekler
      [1] https://github.com/neuml/txtai
      [2] https://neuml.hashnode.dev/building-an-efficient-sparse-keyw...
      [3] https://neuml.hashnode.dev/benefits-of-hybrid-search
      [4] https://github.com/neuml/txtai/blob/master/src/python/txtai/...
    • Langroid[1] LLM kütüphanesinde, DocChatAgent[2] içinde temiz ve genişletilebilir bir RAG uygulaması var
      Kelime dağarcığı tabanlı arama (bm25, fuzzy search), semantik arama (embedding), yeniden sıralama (cross-encoder, karşılıklı sıra füzyonu), çeşitliliği sağlama ve lost-in-the-middle etkisini azaltmaya yönelik yeniden sıralama dahil olmak üzere çeşitli arama teknikleri kullanıyor
      [1] Langroid - CMU/UW-Madison araştırmacıları tarafından geliştirilen çok ajanlı LLM framework’ü https://github.com/langroid/langroid
      [2] DocChatAgent uygulaması -
      https://github.com/langroid/langroid/blob/main/langroid/agen...
      answer_from_docs metodundan başlayıp takip edebilirsiniz
      Ayrıca Kadoa’nın kurucusuysanız, Kadoa-snack LLM ile ilgili HN tartışmalarını bulmak için her gün severek kullandığım araçlardan biri

  • Güzel yazı.
    Bulması biraz daha zor bir arka plan bilgisi eklemek gerekirse, BM25, “Best Matching 25”in kısaltmasıdır; “best matching” de sorgudaki terimler ile belgedeki terimleri eşleştirerek sıralama ve terim ağırlığı veren bir formül anlamına gelir.
    25 ise sadece bir sıra numarasıdır; öncesinde formülün 24 varyasyonu vardı, sonrasında da varyasyonlar oldu ama en iyi çalışan 25 numaralı olduğu için yayımlandı.
    Stephen Robertson ve Karen Spärck Jones (IDF ile ünlüdür) tarafından tasarlandı ve ilk olarak Robertson’ın OKAPI bilgi erişim araştırma sisteminde uygulandı.
    OKAPI sistemi, ABD NIST’in her yıl düzenlediği TREC’te (Text Retrieval Conference) yıllarca kıyaslandı; bu etkinlik arama motoru metodolojisinin uluslararası bir “dünya şampiyonası”na oldukça yakındır.
    Ancak bu etkinliğin amacı kazanmaktan çok karşılaştırma ve karşılıklı öğrenmedir; her yıl kasım ayında Maryland, Gaithersburg’da düzenlenen, tavsiye edilesi bir etkinliktir.
    “Bag of words” vektör uzayı modeli (terimlerin seyrek vektörleri) ve BM25’in ait olduğu olasılıksal model dışında, bir sorgu verildiğinde belge kümesini sıralamaya yarayan teorik çerçeveler şaşırtıcı derecede çoktur ve artmaya devam etmektedir.
    Örneğin Divergence from Randomness, istatistiksel dil modelleme, Learning to Rank, kuantum bilgi erişimi, sinir ağı sıralaması gibi yaklaşımlar vardır.
    ICTIR veya SIGIR gibi konferanslarda bugün bile zaman zaman tamamen yeni arama paradigmaları ortaya çıkar.
    Buradaki “istatistiksel dil modelleme”, günümüzde popüler olan büyük dil modellerini ifade etmez; onlar “sinir ağı araması” kategorisine girer.
    Ayrıca “Quantum IR” diye ararsanız, kuantum bilgi erişimi eğitim materyali yerine kızılötesi spektroskopi ya da aynı adlı bir çimento şirketiyle karşılaşabilirsiniz.
    21. yüzyılda bile arama teknolojisinin böyle incelikleri var.
    BM25’i ve alternatiflerini doğrudan karşılaştırmak istiyorsanız, University of Glasgow’da geliştirilen açık kaynaklı arama motoru ve araştırma platformu Terrier’i öneririm.
    BM25, 25 yılı aşkın süredir var olmasına rağmen hâlâ aşılması zor bir temel çizgi olduğunu kanıtladı ve yeni yöntemler karşılaştırılırken sık sık referans noktası olarak kullanılıyor.
    Daha yakın tarihli bir varyant olan BM24F, başlık, gövde, hiperlink gibi birden fazla alanı ve hipermetni işleyebilir.
    Önerilen makale: Spärck Jones, K.; Walker, S.; Robertson, S. E. (2000). “A probabilistic model of information retrieval: Development and comparative experiments: Part 1”. Information Processing & Management 36(6): 779–808 ve devamındaki Part 2.
    Ne yazık ki açık erişimli değil.

    • Tesadüfen US NIST TREC şu anda düzenleniyor.
      18’inde başladı, 22’sinde sona eriyor.
      Ayrıntılar: https://trec.nist.gov/
    • BM24F hakkında daha fazla kaynak olup olmadığını merak ediyorum.
      Google ve Google Scholar’da aradım ama ilgili bir şey bulamadım.

  • Utanarak tanıtıyorum: https://github.com/jankovicsandras/plpgsql_bm25
    https://github.com/jankovicsandras/bm25opt

    • Hobi projelerini utanmadan tanıtma akımıysa, SearchArray, Google Colab’da bir şeyler kurcalarken tam metin (BM25) araması için kullanılan bir pandas eklentisidir.
      https://github.com/softwaredoug/searcharray
      Benzer bir amaçla, çok popüler olan Xing Han Lu’nun BM25S’ini de tanıtayım.
      https://github.com/xhluca/bm25s
    • Dün küçük bir yan projeye BM25 eklemeyi düşünüyordum; tanıtımın zamanlaması iyi oldu.
      Çok sayıda metin ve PDF belgesini yönetmek için saf Python sarmalayıcı projesi olup olmadığını merak ediyorum.
      Solr veya ElasticSearch’i düşündüm ama şu an yapmak istediğim iş için fazla ağır görünüyorlar.
      SQLite BM25 kullandığı için pysqlite3 ile PyPDF2’yi birlikte kullanma seçeneğini değerlendiriyorum.
      Konudan biraz sapıyor ama hibrit BM25 / vektör deposu / LLM uygulamaları geliştirmek için araç arayan çok kişi olacaktır diye düşünüyorum.

  • Belge uzunluğu normalleştirmesinde sözü edilen ortalama belge uzunluğunun medyan olup olmadığını merak ediyorum.
    Aşırı uzun belgelerin ağırlığını düzgün şekilde düşürmek için medyan olması gerekir gibi geliyor; aksi hâlde çok uzun belgeler ortalamayı haksız biçimde yukarı çekmez mi?

    • Lucene açısından bu aritmetik ortalamadır.
      Medyan kullanmak da ilginç bir deney olabilir.
      Belge uzunluğu farklarının çok büyük olduğu bir arama veri kümesi biliyor musunuz?
      Örneğin MSMarco’da uzunluklar oldukça düzenlidir.

  • Güzel yazı.
    Bu tür problemleri matematiksel biçimde düşünmeyi ve bunları test etmeyi gerçekten öğrenmek istiyorum; önerebileceğiniz kaynak var mı?

  • Hibrit arama, arama sonuçları alakalılığı konusundaki eski bir sorunu çözer.
    Anahtar kelimeler ile vektörler arasında sıralama füzyonu kullanarak çoğu durumda çalışan bir hibrit arama oluşturabilirsiniz.

  • BM25, 1970'lerde geliştirilmiş eski bir algoritma
    Temelde kaba bir istatistiksel model ve günümüz istatistikçileri bundan çok daha iyisini yapabilir
    Aramanın, öğrenme tabanlı yöntemlerin kesin biçimde hâkimiyeti altında olduğunu düşünüyorum
    Elbette öğrenme, aramayı girdi olarak kullanabilir
    Bunu hâlâ fark etmemiş ya da eski teknolojiyi mümkün olduğunca uzun süre korumak için teşviki olan çok kişi var; ama piyasa baskısı sonunda bunu değiştirecek

    • O piyasa baskısı, Google'ın iyi çalışan eski arama teknolojisini bırakmasına ya da amacını değiştirmesine ve parlak yeni makine öğrenimi tabanlı aramaya geçmesine yol açan baskıyla aynı mı?
      Düşmanca SEO savaşından kaçınmak için her arama sorgusuna “+reddit” eklememize neden olan teknoloji de bu değil mi?
      Eski olması kötü olduğu anlamına gelmez
      Bir icadın, keşfin ya da tekniğin yaşından çok faydasına bakmak gerekir; yaşa takılıp kalan bu tuhaf teknomerkezci tutum beni endişelendiriyor
    • BM25'in 1970–80'lerdeki erken dönem araştırmalardan, özellikle de olasılıksal sıralama ilkesinden çıktığı doğru; ama birkaç şeyi merak ediyorum
      Gerçek uygulamalarda BM25'in yerini alacak kadar üstün gördüğünüz somut modern istatistiksel yaklaşımlar hangileri?
      Özellikle BM25'in açıkça ele almaya çalıştığı nadir terimler ve belge uzunluğu normalizasyonu gibi uç durumları nasıl ele aldıklarını merak ediyorum
      Öğrenme tabanlı yaklaşımların etkileyici sonuçlar gösterdiğine katılıyorum; ancak aramanın öğrenme yöntemleri tarafından “kesin biçimde domine edildiği” ifadesinin tam olarak ne anlama geldiğini de daha fazla duymak isterim
      Belirli benchmark'lardan mı, yoksa gerçek üretim örneklerinden mi söz ettiğinizi merak ediyorum
    • Epey sert bir görüş
      Birçok arama uzmanının buna katılmayacağını düşünüyorum
      David Tippet (eski OpenSearch, şimdi Github) ve Nicolay Gerold'un harika podcast'inin başlığı şöyle:
      “BM25 is the workhorse of search; vectors are its visionary cousin”
      https://www.youtube.com/watch?v=ENFW1uHsrLM
    • “Yeni olanı” satma teşviki de kesinlikle var
      Arama alanında çalıştığım süre boyunca sayısız trend ve AI ile ilgili teknoloji oldu
      Şu anda devasa VC yatırımları almış vektör arama şirketleri, bir teknoloji evangelistleri ordusuyla belirli bir bakış açısını dayatıyor
      Öte yandan Google gibi yerlerde “anlamsal arama”yı gerçekten çalıştıran elle kürasyonun ve temel, sıkıcı, manuel sınıflandırma sistemlerinin miktarı muazzam
      Ancak bunlar seksi olmadığı için konferanslarda pek konuşulmuyor