Dari Kemiripan ke Peringkat

Pengambilan top-k sebagai primitif query pada pencarian vektor.

Daftar isi

Mesin pencari vektor tidak mengembalikan seluruh koleksi yang telah diurutkan. Yang dikembalikan adalah sejumlah kecil hasil teratas beserta skornya, dan pola top-k itulah primitif query pencarian vektor, yaitu bentuk pertanyaan paling dasar yang ditawarkan mesin. Topik ini membahas bentuk primitif tersebut, peran k terhadap hasil dan biaya, skor yang menyertai setiap hasil, serta penanganan skor yang sama.

Primitif top-k#

Sebuah query pencarian vektor terdiri atas dua bagian, yaitu vektor query dan angka k. Mesin menghitung skor kemiripan antara vektor query dan vektor yang tersimpan, mengurutkan hasilnya, lalu mengembalikan k vektor teratas beserta skornya. Pola inilah yang disebut pengambilan top-k, dan angka k menentukan panjang daftar jawabannya.

Pada pencarian eksak, skor dihitung terhadap seluruh koleksi sehingga hasilnya persis sama dengan peringkat lengkap atas seluruh vektor. Indeks aproksimatif, yaitu struktur indeks yang menaksir hasil alih-alih menghitung semuanya, mempercepat langkah tersebut dengan mengorbankan kepastian penuh. Meski begitu, bentuk primitifnya tetap sama, yaitu masukan vektor dan k lalu keluaran k hasil teratas. Perbedaan antar mesin berada pada cara langkah itu dipercepat, bukan pada bentuk pertanyaannya.

Bentuk primitif ini juga menjelaskan pembagian kerja pada aplikasi nyata. Penyimpanan dan indeks menyiapkan vektor beserta struktur peringkatnya, sedangkan aplikasi hanya menyusun vektor query, menetapkan nilai k, dan membaca daftar hasil beserta skornya. Keluaran berupa daftar terurut menetapkan kontrak yang jelas antara mesin dan aplikasi, yaitu urutan hasil, skor setiap hasil, dan pengenal objek yang dirujuknya. Sisa topik ini membahas dua keputusan yang menyertai bentuk tersebut, yaitu nilai k dan perlakuan terhadap skornya.

Peran k terhadap hasil dan biaya#

Nilai k menentukan banyaknya hasil yang dikembalikan sekaligus beban komputasinya. Nilai k yang kecil menghasilkan jawaban yang ringkas, sedangkan nilai k yang besar mengharuskan mesin menyimpan lebih banyak kandidat sementara, mengirim lebih banyak data, dan pada indeks aproksimatif menelusuri struktur indeksnya lebih dalam. Hasil yang dikirim juga membawa skor dan pengenal, sehingga k yang terlalu besar menambah beban jaringan tanpa menambah nilai bagi aplikasinya. Pengaruhnya terasa pada latensi dan bandwidth, bukan hanya pada panjang daftar hasil.

Pemilihan k mengikuti kegunaan hasilnya. Untuk jawaban ringkas kepada pengguna, k bernilai 5 sudah lazim. Apabila hasil pencarian menjadi kandidat untuk tahap penyaringan atau pengurutan berikutnya, k bernilai 20 hingga 50 memberi ruang lebih besar bagi tahap tersebut. Apabila ambang batas diterapkan di sisi aplikasi, jumlah hasil yang benar-benar digunakan dapat lebih sedikit dari k, tetapi biaya pengambilannya tetap dibayar penuh. Angka-angka tersebut adalah contoh, bukan aturan baku, dan nilai k yang tepat ditemukan melalui kebutuhan aplikasi dan pengukuran pada data yang sesungguhnya.

Skor yang menyertai hasil#

Setiap hasil top-k dibawa bersama skornya, dan skor itu bukan pelengkap kosong. Skor menjadi dasar ambang batas, yaitu hasil dengan skor di bawah nilai tertentu ditolak meskipun masuk dalam k teratas. Skor juga menjadi indikator kualitas, karena seluruh skor teratas yang rendah menandakan koleksi tidak memuat jawaban yang benar-benar mirip dengan query. Pada koleksi catatan sensor, misalnya, skor teratas 0,31 langsung memberi tahu bahwa tidak ada catatan yang benar-benar mirip dengan query. Selain itu, skor menjaga informasi peringkat agar pengurutan lanjutan di sisi aplikasi dapat dilakukan tanpa menghitung ulang kemiripan. Nilai skor mengikuti metrik yang dipilih, sehingga pembacaannya mengikuti konvensi skor kemiripan atau konvensi jarak yang bersangkutan.

Skor yang sama dapat terjadi, misalnya ketika dua vektor tersimpan identik atau simetris terhadap query. Mesin menentukan urutan antar hasil dengan skor sama menurut aturan internalnya, sedangkan kode yang menyusun pengurutannya sendiri sebaiknya menetapkan aturan pemutus urutan (tie-breaking) secara eksplisit, misalnya skor menurun lalu pengenal menaik. Aturan eksplisit membuat keluaran dapat diprediksi dan mudah diuji ulang.

Simulasi top-k dengan NumPy#

Skrip berikut menyusun tujuh vektor dokumen tiga dimensi dan satu vektor query, menghitung cosine similarity terhadap query, lalu mengambil tiga hasil teratas dengan pengurutan yang stabil, yaitu pengurutan yang menjaga urutan awal ketika dua skor sama.

python top-tiga.py

import numpy as np

vektor = {
    "d1": np.array([0.9, 0.2, 0.1]),
    "d2": np.array([0.7, 0.5, 0.0]),
    "d3": np.array([0.6, 0.1, 0.5]),
    "d4": np.array([0.5, 0.4, 0.3]),
    "d5": np.array([0.3, 0.3, 0.3]),
    "d6": np.array([0.2, 0.6, 0.4]),
    "d7": np.array([0.1, 0.2, 0.2]),
}
q = np.array([1.0, 0.0, 0.0])
k = 3

id_urut = list(vektor)
matriks = np.vstack([vektor[i] for i in id_urut])
skor = (matriks @ q) / (np.linalg.norm(matriks, axis=1) * np.linalg.norm(q))

urutan = np.argsort(-skor, kind="stable")
print(f"top-{k} untuk query q:")
for pos in range(k):
    i = urutan[pos]
    print(f"{pos + 1}. {id_urut[i]}  skor={skor[i]:.4f}")

text Keluaran

top-3 untuk query q:
1. d1  skor=0.9705
2. d2  skor=0.8137
3. d3  skor=0.7620

Tiga hasil teratas adalah d1, d2, dan d3 dengan skor 0,9705, 0,8137, dan 0,7620. Skrip ini memindai seluruh koleksi, menghitung semua skor, mengurutkan hasilnya, lalu memotongnya pada k, dan pola kerja itulah yang disebut pencarian eksak. Mesin pencari vektor menyelesaikan pola yang sama dengan struktur data yang lebih cepat, sedangkan bentuk pertanyaannya tidak berubah, yaitu k hasil teratas beserta skornya. Apabila ambang batas diterapkan pada contoh ini, misalnya skor minimal 0,8000, hanya d1 dan d2 yang lolos, sehingga jumlah hasil akhirnya lebih sedikit dari k. Pengenal d1 hingga d7 pada skrip berperan sebagai kunci yang menghubungkan vektor dengan objek asalnya, sama seperti pengenal baris pada tabel basis data.

Kesalahan umum#

Tiga kesalahan berikut muncul ketika primitif top-k baru diterapkan pada aplikasi nyata.

Mengurutkan skor dengan arah yang salah membalik seluruh hasil, karena skor kemiripan diurutkan menurun sedangkan jarak diurutkan menaik. Contoh kecil dua pasang vektor sudah cukup untuk menampakkan arah yang keliru. Perbaikannya, uji pengurutan dengan contoh kecil yang jawabannya sudah diketahui.
Memilih k tanpa memperhitungkan penggunaan hasilnya membuat daftar terlalu pendek bagi tahap berikutnya atau terlalu panjang untuk dibaca. Daftar yang terlalu panjang juga memperbesar respons yang dikirim ke aplikasi tanpa menambah nilai. Perbaikannya, mulai dari kebutuhan tahap aplikasi berikutnya lalu ukur dampaknya pada latensi.
Mengabaikan skor yang dikembalikan menyembunyikan kasus tidak ada jawaban yang mirip. Nilai ambangnya ditentukan dari distribusi skor pada koleksi, bukan dari tebakan. Perbaikannya, tampilkan atau periksa skor teratas sebelum hasil digunakan lebih lanjut, misalnya dengan menolak hasil di bawah nilai ambang yang ditetapkan.

Ringkasan#

Query pencarian vektor berbentuk vektor query ditambah k, dan mesin mengembalikan k hasil teratas beserta skornya.
Nilai k menentukan banyaknya hasil sekaligus biaya penyimpanan kandidat, pengiriman data, dan kedalaman penelusuran indeks.
Skor pada setiap hasil digunakan untuk ambang batas, indikator kualitas, dan pengurutan lanjutan.
Skor yang sama memerlukan aturan pemutus urutan yang eksplisit, misalnya skor menurun lalu pengenal menaik.

Referensi#

Pencarian — Qdrant — Parameter jumlah hasil pada pencarian vektor beserta skor yang menyertainya.
Dokumentasi Milvus — Milvus — Parameter pencarian dan skor yang dikembalikan pada hasil query Milvus.