Memahami Algoritme Pencarian Teks Penuh BM25

 (emschwartz.me)
1 poin oleh GN⁺ 2024-11-21 | 1 komentar | Bagikan ke WhatsApp
  • BM25 masih banyak digunakan dalam pencarian teks penuh yang membutuhkan pencocokan kata kunci yang presisi, dan menjadi salah satu pilar pencarian hibrida yang melengkapi pencarian kemiripan vektor
  • Untuk memberi peringkat dokumen tanpa menghitung probabilitas secara langsung, BM25 menjumlahkan bobot per istilah kueri dan menempatkan dokumen yang tampak lebih relevan di urutan depan
  • Skor terdiri dari IDF, frekuensi istilah dalam dokumen, dan normalisasi panjang dokumen; kata yang jarang muncul diberi bobot lebih besar, sementara kemunculan berulang diberi imbalan yang makin berkurang
  • k1 mengatur seberapa cepat imbalan untuk kemunculan berulang menurun, sedangkan b mengatur kekuatan normalisasi panjang dokumen; umumnya digunakan k1=1.2~2, b=0.75
  • Skor BM25 bukan probabilitas relevansi nyata, sehingga sulit dipakai sebagai nilai pembanding universal; skor ini bermakna saat dibandingkan di dalam koleksi dokumen yang sama

Masalah pencarian yang ingin diselesaikan BM25

  • BM25, atau Best Match 25, adalah algoritme yang banyak digunakan dalam pencarian teks penuh
    • Digunakan sebagai default di Lucene/Elasticsearch, SQLite, dan lainnya
    • Belakangan, pencarian hibrida yang menggabungkan pencarian teks penuh dan pencarian kemiripan vektor makin umum
  • Dalam feed konten yang dipersonalisasi, pencarian kemiripan vektor saja bisa kurang memadai untuk menangani kata kunci secara presisi
    • Jika minatnya adalah Solid.js, penggunaan pencarian kemiripan vektor saja bisa memunculkan lebih banyak konten terkait React daripada Solid
  • Pertanyaan intinya adalah apakah skor BM25 suatu dokumen bisa dibandingkan di antara beberapa kueri untuk menentukan kueri mana yang paling cocok dengan dokumen tersebut

Prinsip peringkat probabilitas dan pendekatan BM25

  • Tujuan pencarian teks penuh adalah menemukan dokumen yang paling relevan dari sekumpulan dokumen yang mungkin, berdasarkan kueri
  • Karena relevansi sebenarnya tidak bisa diketahui dengan pasti, pencarian berupaya mengurutkan dokumen berdasarkan probabilitas bahwa dokumen tersebut relevan terhadap kueri
    • Gagasan ini disebut Probability Ranking Principle
  • Pencarian berbasis leksikal seperti BM25 hanya menggunakan karakteristik kueri dan dokumen di dalam koleksi dokumen
    • Pencarian kemiripan vektor dapat menggunakan model embedding yang dilatih pada korpus teks eksternal untuk merepresentasikan makna kueri dan dokumen

Komponen pembentuk skor BM25

  • BM25 menghitung skor dengan menggabungkan berbagai sinyal dari kueri dan koleksi dokumen

  • Istilah kueri

    • Jika kueri pencarian terdiri dari beberapa istilah, skor dihitung untuk masing-masing istilah lalu dijumlahkan

  • Inverse Document Frequency (IDF)

    • Menunjukkan seberapa jarang sebuah istilah pencarian di seluruh koleksi dokumen
    • Kata umum seperti the dan and dianggap memiliki kandungan informasi rendah, sementara kata yang jarang muncul diberi bobot lebih tinggi

  • Frekuensi istilah dalam dokumen

    • Mencerminkan berapa kali istilah pencarian muncul dalam dokumen tertentu
    • Jika istilah yang sama muncul lebih sering, kemungkinan relevansinya dianggap lebih besar, tetapi BM25 menerapkan efek hasil yang menurun pada kemunculan berulang

  • Panjang dokumen

    • Dokumen yang panjang dapat memuat istilah pencarian lebih banyak hanya karena lebih panjang
    • BM25 menormalisasi panjang dokumen dengan membandingkannya terhadap rata-rata panjang dokumen, agar dokumen panjang tidak memperoleh skor tinggi secara tidak adil

Tiap bagian dalam rumus BM25

  • Skor keseluruhan BM25 untuk dokumen D dan kueri Q dihitung dengan menjumlahkan skor setiap istilah kueri q_i
    • D: dokumen target
    • Q: keseluruhan kueri
    • n: jumlah istilah kueri
    • q_i: tiap istilah kueri

  • IDF: memberi bobot lebih besar pada kata yang jarang di dalam koleksi

    • Komponen IDF menghitung seberapa jarang istilah kueri di seluruh koleksi dokumen
    • N: jumlah total dokumen dalam koleksi
    • n(q_i): jumlah dokumen yang memuat istilah kueri
    • N - n(q_i): jumlah dokumen yang tidak memuat istilah kueri
    • Istilah umum muncul di banyak dokumen, sehingga pengaruhnya terhadap skor menjadi kecil
    • Istilah yang jarang hanya muncul di sedikit dokumen, sehingga tercermin lebih besar dalam skor
    • 0.5 dan 1 dalam rumus berperan meredam agar hasil tidak berfluktuasi terlalu besar saat istilah sangat jarang atau sangat umum

  • Frekuensi istilah: mengakomodasi pengulangan, tetapi tidak memberi imbalan tanpa batas

    • Frekuensi istilah dalam dokumen mencerminkan seberapa sering istilah kueri tertentu muncul dalam dokumen tertentu
    • f(q_i, D): frekuensi kemunculan istilah kueri q_i dalam dokumen D
    • k1: parameter tuning yang biasanya ditetapkan antara 1.2 dan 2
    • BM25 memasukkan pengulangan istilah ke dalam skor, tetapi semakin banyak pengulangan, semakin kecil kenaikan skor tambahannya
    • k1 mengontrol seberapa cepat imbalan untuk pengulangan istilah berkurang

  • Normalisasi panjang dokumen: menyesuaikan keuntungan dokumen panjang

    • Normalisasi panjang dokumen membandingkan panjang dokumen target dengan rata-rata panjang dokumen dalam koleksi
    • |D|: panjang dokumen target
    • avgdl: rata-rata panjang dokumen dalam koleksi
    • b: parameter tuning yang mengontrol kekuatan normalisasi panjang dokumen
    • Dokumen yang lebih panjang dari rata-rata lebih mungkin memuat istilah pencarian lebih sering, sehingga mendapat penalti pada penyebut rumus akhir
    • Jika b=0, normalisasi panjang dokumen dimatikan; jika b=1, normalisasi diterapkan sepenuhnya
    • b biasanya ditetapkan ke 0.75

Gagasan inti BM25

  • BM25 didasarkan pada Probability Ranking Principle, tetapi menghitung probabilitas sebenarnya dari relevansi dokumen hampir mustahil
  • Dalam pencarian, yang penting adalah urutan dokumen, bukan nilai probabilitas yang presisi; karena itu, komponen yang tidak memengaruhi urutan dihapus dari rumus agar perhitungannya praktis
  • Karena itu, BM25 menghitung bobot, bukan probabilitas itu sendiri
  • Robertson/Sparck Jones Weight adalah cara memperkirakan probabilitas dengan menggunakan jumlah dokumen relevan dan jumlah dokumen yang memuat istilah kueri
    • r: jumlah dokumen relevan yang memuat istilah kueri
    • N: jumlah total dokumen dalam koleksi
    • R: jumlah dokumen relevan dalam koleksi
    • n: jumlah dokumen yang memuat istilah kueri
  • Keterbatasan besar dari pendekatan ini adalah perlu mengetahui terlebih dahulu dokumen mana yang relevan

Asumsi bahwa “sebagian besar dokumen tidak relevan”

  • Pengembang BM25 berasumsi bahwa untuk kueri apa pun, sebagian besar dokumen tidak relevan
  • Jika jumlah dokumen relevan dianggap sangat kecil hingga dapat diabaikan, R = r = 0 dapat ditetapkan
  • Jika nilai ini dimasukkan ke dalam rumus Robertson/Sparck Jones Weight, bentuk yang muncul hampir sama dengan komponen IDF yang digunakan dalam BM25
  • Karena tidak lagi membutuhkan informasi relevansi di muka sambil tetap mempertahankan landasan teoritis yang sama, BM25 menjadi jauh lebih praktis
  • Victor Lavrenko menyebutnya sebagai "very impressive leap of faith"

Cakupan perbandingan skor BM25

  • Skor BM25 umumnya sulit dibandingkan secara langsung
    • Tidak menghasilkan skor probabilitas antara 0 dan 1
    • Juga bukan algoritme yang berupaya memperkirakan probabilitas nyata bahwa sebuah dokumen relevan
    • Fokusnya adalah memperkirakan urutan kemungkinan relevansi terhadap kueri di dalam koleksi tertentu
  • Skor BM25 yang lebih tinggi adalah sinyal bahwa dokumen kemungkinan lebih relevan, tetapi bukan probabilitas relevansi sebenarnya
  • Untuk dokumen yang sama di dalam koleksi dokumen yang sama, skor BM25 dari beberapa kueri dapat dibandingkan
    • Karena BM25 menjumlahkan skor tiap istilah kueri, dapat dianggap tidak ada perbedaan makna antara membandingkan skor dua istilah kueri dan membandingkan skor dua kueri penuh
  • Batasan pentingnya adalah dokumen yang sama, koleksi yang sama
    • BM25 menggunakan IDF dan rata-rata panjang dokumen di dalam koleksi
    • Jika koleksi berubah, skor dapat berubah, sehingga perbandingan skor dari waktu ke waktu tidak dijamin
  • Dalam feed konten yang dipersonalisasi, ini dapat digunakan dengan menjalankan pencarian teks penuh untuk setiap minat pengguna dan membandingkan skor BM25 untuk menentukan konten mana yang paling cocok dengan minat mana

Bacaan lebih lanjut

Bacaan terkait

1 komentar

 
GN⁺ 2024-11-21
Opini Hacker News

  • Untuk pencarian umum saya memakai https://typesense.org/, dan sekarang sudah mendukung pencarian hybrid, jadi saya penasaran apakah ada yang sudah mencobanya

    • Saya sudah mencobanya untuk pencarian hybrid dan hasilnya cukup baik
      Senang melihat Typesense disebut di sini; untuk proyek RAG skala kecil, sering kali ini cocok, tapi entah kenapa kurang dikenal
      Mudah di-deploy, default-nya masuk akal, dokumentasinya bagus, clustering-nya juga relatif mudah, namun tetap cukup cepat dan kuat saat perlu didalami lebih jauh
    • Kami juga memakainya dan secara umum puas
      Namun jika memakai model embedding dari penyedia eksternal, latensinya 500ms+ yang sangat tidak masuk akal, jadi lebih baik di-host sendiri di dalam cluster
      Kualitas pencarian hybrid-nya bagus, tetapi opsi penyetelannya sangat terbatas, dan skornya juga cukup buram selain untuk pemeringkatan di dalam kumpulan hasil

  • Dengan kemajuan terbaru pada pencarian semantik berbasis vektor, saya penasaran stack pencarian modern apa yang sekarang dipakai untuk hybrid keyword + semantic search

    • Strategi pencarian serbaguna sebenarnya sangat bergantung pada tugas yang dituju
      Baru-baru ini kami menerima sekitar 3 juta survei dengan masing-masing 10 field isian bebas, dan harus menemukan hal-hal yang layak ditindaklanjuti perusahaan
      Kami memakai beberapa model classifier kecil, lalu setelah melihat noise yang muncul pada 10 ribu data pertama, menghapus kata-kata umum secara manual, kemudian memberi bobot pada respons model; hasilnya hampir sempurna
      Hal seperti ini lebih mirip menyetel output black box dari berbagai alat sampai terlihat bagus bagi test case dan pelanggan, daripada “pemrograman”
      Sebagai catatan, ini diproses di server kecil dengan merangkai beberapa model kecil Hugging Face di Node.js
    • Sebagian besar produk pencarian hybrid komersial maupun open source tampaknya memakai BM25 + pencarian kemiripan vektor berbasis embedding
      Hasilnya biasanya digabung dengan reciprocal rank fusion (RRF)
      Paper RRF mengesankan karena sangat sederhana, dan paper-nya pun hanya 2 halaman: https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf
    • Jangan terpaku pada satu stack saja; harus siap memakai alat yang paling cocok untuk tiap tugas
      Untuk pekerjaan ala BM25 bisa memakai Elasticsearch, untuk pencarian vektor yang sederhana dan cepat bisa memakai Turbopuffer, dan untuk hasil query tertentu yang diprakomputasi atau atribut dinamis yang sering berubah seperti harga, Redis juga bisa dipakai
      Menurut saya sebaiknya hal-hal ini digabungkan dengan pendekatan scatter/gather
      Di luar stack pencarian, hampir selalu ada lapisan layanan inferensi untuk reranking, dan idealnya ini menjadi layanan sederhana yang mirip dengan infrastruktur machine learning lainnya
      Routing seperti memahami query pengguna lalu mengirim “lookup berdasarkan ID” ke satu sistem dan “pencarian semantik fuzzy” ke sistem lain juga hampir selalu diperlukan
      Struktur data mereka sangat berbeda, dan pencarian pada umumnya mencakup berbagai use case yang berbeda
      Memaksakan semua hal ke dalam satu sistem menurut saya adalah antipola
      Tiap sistem cocok untuk beban kerja yang berbeda, dan fitur inferensi bawaan sulit mengejar kecepatan alat machine learning umum yang sudah familier bagi engineer machine learning
      Saya pernah mencobanya dengan Elasticsearch Learning to Rank, tetapi itu pekerjaan yang tidak ada harapannya
      Meski begitu, di antara upaya menyelesaikan use case yang luas dalam satu stack, Vespa mungkin yang terbaik
    • Ini tulisan yang sangat bagus tentang BM25
      Sebagai pembuat txtai, txtai mengimplementasikan indeks BM25 berkinerja baik di Python melalui paket arrays, dan menyimpan vektor frekuensi term di SQLite
      Metode indeks hybrid txtai mendukung kombinasi konveks jika skor BM25 dinormalisasi, dan reciprocal rank fusion (RRF) jika tidak dinormalisasi
      [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/...
    • Library LLM Langroid[1] memiliki implementasi RAG yang rapi dan dapat diperluas di dalam DocChatAgent[2]
      Ia menggunakan berbagai teknik pencarian: pencarian berbasis leksikal (bm25, fuzzy search), pencarian semantik (embedding), reranking (cross-encoder, reciprocal rank fusion), serta reranking untuk memastikan keberagaman dan mengurangi lost-in-the-middle
      [1] Langroid - framework LLM multi-agent yang dibuat oleh peneliti CMU/UW-Madison https://github.com/langroid/langroid
      [2] Implementasi DocChatAgent -
      https://github.com/langroid/langroid/blob/main/langroid/agen...
      Anda bisa mulai dari metode answer_from_docs lalu menelusurinya
      Sebagai tambahan, jika Anda pendiri Kadoa, Kadoa-snack adalah salah satu alat yang saya pakai setiap hari untuk menemukan diskusi HN terkait LLM

  • Tulisan yang bagus
    Jika menambahkan latar belakang yang agak lebih sulit ditemukan, BM25 adalah singkatan dari “Best Matching 25”, dan “best matching” berarti rumus untuk mencocokkan istilah dalam kueri dengan istilah dalam dokumen, lalu memberi peringkat dan bobot pada istilah
    Angka 25 hanyalah nomor urut; sebelumnya ada 24 variasi rumus, dan ada juga variasi sesudahnya, tetapi nomor 25 yang bekerja paling baik sehingga dipublikasikan
    Ini dirancang oleh Stephen Robertson dan Karen Spärck Jones (terkenal dengan IDF), dan pertama kali diimplementasikan dalam sistem riset temu balik informasi OKAPI milik Robertson
    Sistem OKAPI selama bertahun-tahun dibenchmark di TREC (Text Retrieval Conference) tahunan milik NIST AS, yang kurang lebih seperti “kejuaraan dunia” internasional untuk metodologi mesin pencari
    Namun acara ini lebih bertujuan untuk perbandingan dan saling belajar daripada mencari pemenang, dan merupakan acara yang layak direkomendasikan yang diadakan setiap November di Gaithersburg, Maryland
    Selain model ruang vektor “bag of words” (vektor sparse dari istilah) dan model probabilistik yang mencakup BM25, ada sangat banyak kerangka teoretis untuk memberi peringkat kumpulan dokumen berdasarkan kueri, dan jumlahnya terus bertambah
    Contohnya ada divergence from randomness, statistical language modeling, Learning to Rank, quantum information retrieval, neural ranking, dan sebagainya
    Di konferensi seperti ICTIR atau SIGIR, paradigma pencarian yang sepenuhnya baru kadang masih muncul hingga sekarang
    Di sini, “statistical language modeling” bukan berarti large language model yang sedang populer saat ini; yang itu masuk dalam kategori “neural search”
    Selain itu, jika mencari “Quantum IR”, Anda mungkin akan melihat spektroskopi inframerah atau perusahaan semen dengan nama yang sama, bukan tutorial quantum information retrieval
    Bahkan pada abad ke-21, teknologi pencarian masih punya nuansa seperti ini
    Jika ingin membandingkan langsung BM25 dengan alternatifnya, saya merekomendasikan Terrier, mesin pencari open source sekaligus platform riset yang dikembangkan di University of Glasgow
    BM25 sudah berusia lebih dari 25 tahun, tetapi masih terbukti sebagai baseline yang sulit dilampaui, dan sering dipakai sebagai titik acuan saat membandingkan metode baru
    Variasi yang lebih baru, BM24F, dapat menangani banyak field seperti judul, isi, hyperlink, serta hypertext
    Paper yang direkomendasikan adalah 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, serta Part 2 lanjutannya
    Sayangnya, itu bukan open access

    • Kebetulan US NIST TREC sedang berlangsung sekarang
      Dimulai tanggal 18 dan berakhir tanggal 22
      Detailnya: https://trec.nist.gov/
    • Saya penasaran apakah ada lebih banyak materi tentang BM24F
      Saya sudah mencari di Google dan Google Scholar, tetapi tidak menemukan hal terkait

  • Malu-malu, tapi sekalian promosi: https://github.com/jankovicsandras/plpgsql_bm25
    https://github.com/jankovicsandras/bm25opt

    • Kalau memang sedang tren mempromosikan proyek hobi tanpa malu-malu, SearchArray adalah ekstensi pandas untuk pencarian full-text (BM25) saat mencoba-coba berbagai hal di Google Colab
      https://github.com/softwaredoug/searcharray
      Saya juga sekalian mempromosikan BM25S milik Xing Han Lu yang sangat populer dan punya tujuan serupa
      https://github.com/xhluca/bm25s
    • Kemarin saya sedang berpikir untuk menambahkan BM25 ke sebuah side project kecil, jadi promosinya pas sekali waktunya
      Saya penasaran apakah ada proyek wrapper Python murni untuk mengelola banyak teks dan dokumen PDF
      Saya sempat mempertimbangkan Solr atau ElasticSearch, tetapi tampaknya terlalu berat untuk pekerjaan yang ingin saya lakukan sekarang
      Karena SQLite menggunakan BM25, saya sedang mempertimbangkan opsi memakai pysqlite3 bersama PyPDF2
      Sedikit melenceng dari topik, tetapi sepertinya ada banyak orang yang mencari alat untuk membuat aplikasi hybrid BM25 / vector store / LLM

  • Saya penasaran apakah panjang dokumen rata-rata yang dimaksud dalam normalisasi panjang dokumen adalah median
    Untuk benar-benar menurunkan bobot dokumen yang terlalu panjang dengan tepat, sepertinya harus median; kalau tidak, dokumen yang sangat panjang bisa menaikkan rata-rata secara tidak semestinya

    • Dalam Lucene, itu adalah rata-rata aritmetika
      Menggunakan median juga tampaknya bisa menjadi eksperimen yang menarik
      Saya penasaran apakah Anda tahu dataset pencarian dengan variasi panjang dokumen yang sangat besar
      Misalnya, MSMarco panjangnya cukup seragam

  • Tulisan yang bagus
    Saya benar-benar ingin belajar cara memikirkan masalah seperti ini dalam bentuk matematis dan cara mengujinya; adakah referensi yang bisa dijadikan rujukan?

  • Hybrid search menyelesaikan tantangan lama terkait relevansi hasil pencarian
    Dengan memakai rank fusion antara keyword dan vector, kita bisa membuat hybrid search yang bekerja di sebagian besar situasi

  • BM25 adalah algoritma lama yang dikembangkan pada 1970-an
    Pada dasarnya ini model statistik yang kasar, dan para ahli statistik saat ini bisa melakukan jauh lebih baik
    Menurut saya, pencarian secara ketat didominasi oleh metode berbasis pembelajaran
    Tentu saja, pembelajaran bisa menggunakan pencarian sebagai input
    Masih banyak orang yang belum menyadari hal ini, atau punya insentif untuk mempertahankan teknologi lama selama mungkin, tetapi tekanan pasar pada akhirnya akan mengubahnya

    • Apakah tekanan pasar yang dimaksud itu tekanan yang membuat Google meninggalkan atau mengubah peruntukan teknologi pencarian lama yang dulu bekerja dengan baik, lalu beralih ke pencarian berbasis machine learning baru yang berkilau itu?
      Bukankah karena teknologi itu kita jadi menambahkan “+reddit” pada setiap kueri pencarian untuk menghindari perang SEO yang adversarial?
      Sesuatu tidak buruk hanya karena sudah tua
      Yang perlu dilihat adalah kegunaan suatu penemuan, temuan, atau teknik, bukan usianya; saya khawatir dengan sikap teknosentris yang aneh dan terobsesi pada usia
    • Memang benar BM25 lahir dari riset awal tahun 1970–80-an, khususnya di atas prinsip pemeringkatan probabilistik, tetapi ada beberapa hal yang membuat saya penasaran
      Pendekatan statistik modern spesifik apa yang Anda anggap cukup unggul untuk menggantikan BM25 dalam aplikasi nyata?
      Saya terutama penasaran bagaimana pendekatan itu menangani kasus tepi seperti istilah langka dan normalisasi panjang dokumen, yang memang ingin ditangani BM25 secara eksplisit
      Saya setuju pendekatan berbasis pembelajaran telah menunjukkan hasil yang mengesankan, tetapi saya juga ingin mendengar lebih jauh apa tepatnya arti bahwa pencarian “secara ketat didominasi” oleh metode pembelajaran
      Apakah yang dimaksud benchmark tertentu, atau kasus operasional nyata?
    • Pandangan yang cukup pedas
      Saya rasa banyak pakar pencarian tidak akan setuju
      Judul podcast bagus dari David Tippet (mantan OpenSearch, kini Github) dan Nicolay Gerold berbunyi seperti ini:
      “BM25 is the workhorse of search; vectors are its visionary cousin”
      https://www.youtube.com/watch?v=ENFW1uHsrLM
    • Jelas ada juga insentif untuk menjual “hal baru”
      Selama saya bekerja di bidang pencarian, ada banyak sekali tren dan teknologi terkait AI
      Saat ini perusahaan-perusahaan pencarian vektor yang mendapat investasi VC besar mendorong sudut pandang tertentu dengan pasukan evangelist teknologi di garis depan
      Sementara itu, jumlah kurasi manual serta taksonomi manual dasar dan membosankan yang benar-benar menggerakkan “pencarian semantik” di tempat seperti Google sangatlah besar
      Hanya saja hal-hal seperti itu tidak seksi, jadi jarang dibicarakan di konferensi