Kata Kunci Bertemu Vektor

BM25 bersama pencarian vektor dan fusi peringkat dengan reciprocal rank fusion.

Daftar isi

Pencarian vektor menemukan dokumen yang dekat secara makna, tetapi tidak selalu menangkap kata kunci yang diminta secara harfiah. Topik ini menjelaskan jalur pengambilan kata kunci berbasis BM25 dan jalur pengambilan semantik berbasis vektor, alasan skor keduanya tidak dapat dijumlahkan langsung, serta reciprocal rank fusion yang memadukan kedua daftar peringkat hanya dari posisinya. Perhitungan fusi dijalankan sungguhan pada enam dokumen contoh.

Dua jalur pengambilan#

Jalur pertama adalah BM25, yaitu algoritma peringkat kata kunci yang menjadi tradisi mesin pencari berbasis indeks terbalik. Skor BM25 dihitung dari tiga hal, yaitu term frequency yang menghitung seberapa sering kata kunci muncul pada dokumen, inverse document frequency yang memberi bobot lebih pada kata yang jarang muncul di dokumen lain, dan normalisasi panjang dokumen agar dokumen panjang tidak otomatis menang. Jalur ini unggul pada permintaan yang menyebut istilah secara harfiah, misalnya kode error, nomor dokumen, atau nama yang spesifik.

Jalur kedua adalah pencarian kemiripan vektor dengan embedding yang telah dibahas sepanjang jalur ini. Query dan dokumen diubah menjadi vektor, kemudian dokumen yang vektornya berdekatan dikembalikan sebagai hasil. Jalur ini menangkap makna meskipun katanya berbeda, misalnya permintaan tentang cara menghitung rata-rata tetap menemukan dokumen yang membahas rumus statistik, tetapi lemah pada istilah spesifik yang jarang muncul pada data pelatihannya.

Kedua jalur saling menutupi kelemahan. Dokumen yang mengandung kata kunci tepat tetapi tidak mirip maknanya ditemukan oleh BM25, sedangkan dokumen yang mirip maknanya dengan redaksi berbeda ditemukan oleh vektor. Pada Qdrant, BM25 sejak versi 1.20 tersedia sebagai skor pada full-text index, sehingga kedua jalur dapat berjalan pada satu mesin, dan prinsip yang sama berlaku pada mesin pencari lain.

Contoh paling jelas ada pada permintaan yang menyebut penanda teknis. Pencarian vektor dapat melewatkan dokumen yang menyebut kode error secara tepat, karena kemiripan maknanya tersebar di banyak dokumen lain, sedangkan BM25 menemukannya langsung melalui kata yang cocok. Sebaliknya, permintaan yang berarti sama tetapi berbeda kata hanya ditemukan oleh jalur vektor, karena kata kuncinya tidak bertemu.

Skala skor yang tak sebanding#

Cara paling mudah untuk memadukan kedua jalur adalah menjumlahkan skornya, tetapi cara itu tidak bermakna karena skala keduanya berbeda. Skor BM25 tidak memiliki batas atas, sehingga nilainya dapat bernilai 2, 15, atau 40 tergantung kepadatan kata kunci dan ukuran collection, sedangkan skor cosine berada pada rentang yang terbatas, misalnya 0 sampai 1 untuk vektor ternormalisasi. Penjumlahan langsung membuat BM25 mendominasi pada collection dengan skor kata kuncinya tinggi, sedangkan vektor mendominasi pada collection lain.

Jawabannya adalah memadukan kedua jalur dari peringkat, bukan dari skor. Posisi peringkat bersifat universal, yaitu dokumen pertama selalu berarti yang terbaik pada jalur mana pun, sehingga dua daftar dengan skala skor yang berbeda dapat dibandingkan melalui posisinya. Fusi berbasis peringkat inilah yang digunakan reciprocal rank fusion.

Ilustrasi penjumlahan langsung memperlihatkan masalahnya. Dokumen dengan skor BM25 12,4 dan cosine 0,82 menghasilkan jumlah 13,22 yang hampir seluruhnya berasal dari BM25, sedangkan pada collection lain seluruh skor BM25 dapat berada di bawah 2 sehingga arah dominasinya berbalik. Karena dominasi itu bergantung pada data dan bukan pada relevansi, penjumlahan skor tidak dapat diandalkan.

Reciprocal rank fusion#

Reciprocal rank fusion, disingkat RRF, memberi skor pada setiap dokumen dengan menjumlahkan kontribusi dari setiap daftar peringkat yang memuatnya. Kontribusi tersebut dihitung dengan rumus berikut, dengan $d$ menyatakan satu dokumen dan $L$ himpunan daftar peringkat yang digabungkan.

\text{RRF}(d) = \sum_{l \in L} \frac{1}{k + \text{rank}_l(d)}

Posisi dokumen pada daftar l dinyatakan oleh $\text{rank}_l(d)$ , sedangkan $k$ adalah konstanta pelunakan yang umumnya bernilai 60. Dokumen dengan peringkat satu memperoleh kontribusi $1/61$ , peringkat sepuluh memperoleh $1/70$ , dan selisih yang relatif kecil ini mencegah juara satu jalur mana pun mendominasi fusi. Rumus yang sama berlaku untuk lebih dari dua daftar, karena penjumlahannya mencakup seluruh daftar pada $L$ , sehingga mesin yang menambah jalur baru cukup menjumlahkan kontribusinya tanpa mengubah mekanisme fusinya. Skrip berikut menghitung RRF pada enam dokumen arsip catatan dengan dua daftar peringkat, yaitu BM25 dan vektor, yang keduanya dibentuk dari skor ilustrasi.

python fusi-rrf.py

"""Fusi peringkat BM25 dan vektor dengan reciprocal rank fusion."""
import numpy as np

# Enam dokumen pada arsip catatan kelas. Skor di bawah adalah konstanta
# ilustrasi untuk membentuk peringkat, bukan keluaran model BM25 maupun
# model embedding. Skor BM25 tidak memiliki batas atas, sedangkan skor
# cosine berada pada rentang 0 sampai 1, sehingga keduanya tidak sebanding.
dokumen = ["d1 rekap nilai ujian", "d2 rumus statistik nilai",
           "d3 cara menghitung rata-rata", "d4 jadwal piket kelas",
           "d5 arsip pengumuman kelas", "d6 pengumuman ujian akhir"]
skor_bm25 = np.array([5.42, 4.85, 7.30, 1.62, 1.85, 2.97])
skor_cosine = np.array([0.88, 0.81, 0.79, 0.35, 0.41, 0.55])

n = len(dokumen)

# Peringkat tiap dokumen pada masing-masing daftar, 1 = paling atas.
peringkat_bm25 = np.empty(n, dtype=int)
peringkat_bm25[np.argsort(-skor_bm25)] = np.arange(1, n + 1)
peringkat_cosine = np.empty(n, dtype=int)
peringkat_cosine[np.argsort(-skor_cosine)] = np.arange(1, n + 1)

# Reciprocal rank fusion: 1/(k + peringkat) dijumlahkan dari kedua daftar.
k = 60
fusi = 1 / (k + peringkat_bm25) + 1 / (k + peringkat_cosine)

urutan = np.argsort(-fusi)
print(f"peringkat fusi (k = {k}):")
for pos, i in enumerate(urutan, start=1):
    print(f"{pos}. {dokumen[i]:<30} {np.round(fusi[i], 4):.4f}"
          f"  (bm25 #{peringkat_bm25[i]}, vektor #{peringkat_cosine[i]})")

text Keluaran

peringkat fusi (k = 60):
1. d1 rekap nilai ujian           0.0325  (bm25 #2, vektor #1)
2. d3 cara menghitung rata-rata   0.0323  (bm25 #1, vektor #3)
3. d2 rumus statistik nilai       0.0320  (bm25 #3, vektor #2)
4. d6 pengumuman ujian akhir      0.0312  (bm25 #4, vektor #4)
5. d5 arsip pengumuman kelas      0.0308  (bm25 #5, vektor #5)
6. d4 jadwal piket kelas          0.0303  (bm25 #6, vektor #6)

Keluaran memperlihatkan perilaku fusi yang diharapkan. Dokumen d1 berada di peringkat kedua pada BM25 dan peringkat pertama pada vektor, sehingga posisinya tinggi pada kedua daftar dan skor fusinya paling besar. Dokumen d3, juara pada jalur BM25, turun ke peringkat kedua karena pada jalur vektor hanya menempati peringkat ketiga. Peringkat fusi berbeda dari kedua daftar asalnya, dan itulah tujuannya, yaitu menghargai dokumen yang kuat pada lebih dari satu jalur.

Skor fusi pada bagian bawah daftar saling berdekatan, misalnya 0,0312 diikuti 0,0308 dan 0,0303, karena dokumen dengan posisi yang berdekatan menghasilkan kontribusi yang berdekatan pula. Urutan akhir tetap ditentukan oleh jumlah lengkapnya, dan perbedaan kecil semacam ini perlu disertai uji relevansi sebelum dijadikan dasar keputusan.

Ringkasan#

BM25 mengurutkan dokumen dari kata kunci dengan term frequency, inverse document frequency, dan normalisasi panjang, sedangkan vektor mengurutkan dari kemiripan makna.
Skor BM25 dan cosine tidak sebanding skalanya, sehingga fusi dilakukan dari peringkat dan bukan dari penjumlahan skor.
RRF menjumlahkan $1/(k + \text{rank}_l(d))$ dari setiap daftar dengan $k = 60$ , sehingga dokumen yang tinggi pada kedua jalur naik ke atas fusi.

Referensi#

Dokumentasi Qdrant — Qdrant — Dokumentasi resmi Qdrant yang memuat pencarian hibrida dan skor BM25 pada full-text index.
Konsep pencarian — Qdrant — Halaman konsep pencarian Qdrant yang menjelaskan bentuk query dan penyusunan peringkatnya.