Masalah Approximate Nearest Neighbor

Definisi pencarian tetangga terdekat aproksimatif dan komprominya antara recall dan kecepatan.

Daftar isi

Pencarian eksak mengembalikan tetangga terdekat yang benar-benar terbaik, tetapi harganya bertumbuh linear terhadap jumlah vektor. Pencarian tetangga terdekat aproksimatif, yang dikenal sebagai approximate nearest neighbor (ANN), menawarkan jalan keluar dengan mengizinkan sebagian tetangga terlewat. Topik ini mendefinisikan masalahnya, memperkenalkan recall sebagai ukuran kesetiaan hasil, dan menghitung recall@5 melalui simulasi hasil ANN yang kehilangan satu tetangga.

Definisi pencarian aproksimatif#

Pencarian ANN mengembalikan $k$ vektor yang sebagian besar memang terdekat, tanpa jaminan bahwa seluruhnya adalah yang terbaik. Mekanismenya bukan pemindaian penuh, melainkan penelusuran struktur ringkas yang dibangun sebelumnya, misalnya pembagian klaster atau graf tetangga, sehingga hanya sebagian kecil vektor yang diperiksa. Karena vektor yang tidak diperiksa tidak pernah dihitung jaraknya, ada kemungkinan salah satu tetangga terbaik berada di bagian yang terlewat.

Definisi ini menempatkan ANN sebagai masalah kompromi, bukan masalah benar atau salah. Hasil yang memuat sembilan dari sepuluh tetangga terbaik dan satu pengganti yang mirip dapat dinilai cukup baik untuk kebutuhan seperti pencarian dokumen serupa. Yang dituntut bukan kebenaran penuh, melainkan kecepatan yang konsisten dengan kesetiaan yang masih dapat diterima. Kesetiaan itu kemudian diukur dengan recall@k, yang selalu dihitung terhadap jawaban eksak pada sekumpulan query uji.

Recall@k sebagai ukuran kesetiaan#

Recall@k membandingkan hasil pencarian ANN dengan hasil pencarian eksak untuk query yang sama. Jika $E$ adalah himpunan $k$ hasil eksak dan $A$ adalah himpunan $k$ hasil ANN, maka:

\text{recall@}k = \frac{|A \cap E|}{k}

Nilainya berada antara 0 dan 1. Nilai 1,00 berarti seluruh $k$ hasil ANN identik dengan jawaban eksak, sedangkan nilai 0,60 berarti enam dari sepuluh tetangga terbaik ditemukan. Rumus ini hanya melihat keanggotaan himpunan, bukan urutan di dalamnya, sehingga hasil ANN yang menemukan tetangga yang sama tetapi dengan peringkat berbeda tetap dihitung penuh. Karena pembandingnya adalah jawaban eksak, pengukurannya memerlukan pemindaian penuh pada query uji, yang mahal saat dijalankan tetapi hanya dilakukan sekali saat indeks dinilai.

Simulasi: hasil ANN yang kehilangan satu tetangga#

Efek satu tetangga yang hilang paling jelas terlihat ketika dihitung langsung. Berkas berikut membangun 500 vektor berdimensi 8, menghitung jawaban eksak untuk satu query melalui pemindaian penuh, lalu membentuk hasil ANN buatan dengan menghapus tetangga pada peringkat kedua. Simulasi ini sengaja dibuat deterministik agar angka recall@5 dapat diperiksa ulang di mana pun.

python recall_ann.py

"""Mengukur recall@5: hasil ANN yang kehilangan satu tetangga dibanding jawaban eksak."""
import numpy as np

rng = np.random.default_rng(11)

# Dataset kecil: 500 vektor dengan 8 dimensi dan satu query
X = rng.standard_normal((500, 8))
q = rng.standard_normal(8)
k = 5

# Jawaban eksak: seluruh 500 vektor dipindai, lalu diambil k terbaik
jarak = np.linalg.norm(X - q, axis=1)
eksak = [int(t) for t in np.argsort(jarak)[:k]]

# Hasil ANN buatan: tetangga pada peringkat kedua sengaja tidak dikembalikan
peringkat_hilang = 1
hasil_ann = eksak[:peringkat_hilang] + eksak[peringkat_hilang + 1:]

irisan = len(set(hasil_ann) & set(eksak))
recall = irisan / k

print(f"{'Jawaban eksak':<15}: {eksak}")
print(f"{'Hasil ANN':<15}: {hasil_ann}")
print(f"{'Tetangga hilang':<15}: {eksak[peringkat_hilang]} (peringkat ke-{peringkat_hilang + 1})")
print(f"{'Irisan':<15}: {irisan} dari {k} -> recall@{k} = {irisan}/{k} = {recall:.2f}")

text Keluaran

Jawaban eksak  : [383, 23, 66, 62, 284]
Hasil ANN      : [383, 66, 62, 284]
Tetangga hilang: 23 (peringkat ke-2)
Irisan         : 4 dari 5 -> recall@5 = 4/5 = 0.80

Keluaran menunjukkan lima indeks jawaban eksak dan empat indeks hasil ANN, dengan tetangga pada indeks 23 yang tidak dikembalikan. Irisan keduanya berisi empat anggota, sehingga recall@5 bernilai 0,80. Pola ini berlaku umum: setiap tetangga eksak yang terlewat menurunkan recall sebesar $1/k$ , yaitu 0,20 untuk $k = 5$ . Kesetiaan hasil ANN dapat dibaca langsung dari berapa banyak posisi jawaban eksak yang tidak terisi.

Kompromi antara kecepatan dan ketepatan#

Hubungan antara kecepatan dan recall bukan garis lurus yang bebas diatur, melainkan kompromi yang digerakkan oleh parameter indeks. Mempersempit parameter membuat pencarian memeriksa lebih sedikit struktur, sehingga selesai lebih cepat tetapi lebih sering melewatkan tetangga. Melonggarkannya bekerja sebaliknya, yaitu recall naik dengan biaya perhitungan yang lebih besar per query. Kedua ujungnya jelas: pengaturan paling hemat menghasilkan recall terendah, sedangkan pengaturan paling longgar mendekati perilaku pemindaian penuh.

Kompromi ini biasanya digambarkan sebagai kurva, bukan satu angka tunggal. Proyek ANN-Benchmarks mengukur banyak algoritma ANN pada dataset publik dan menyajikan hasilnya sebagai kurva recall terhadap kecepatan query dalam satuan queries per second. Setiap titik pada kurva adalah satu pengaturan parameter, sehingga pemilihan titik kerja dapat disesuaikan dengan kebutuhan aplikasi. Kurva juga memperlihatkan keluarga indeks mana yang memberi recall lebih baik pada kecepatan yang sama, sehingga pilihan antara klaster, graf, atau kompresi dapat ditimbang dengan data yang sama.

Kesalahan umum#

Kesalahan pertama adalah mengukur recall pada satu query saja. Satu query dapat menghasilkan recall 1,00 karena kebetulan atau recall yang rendah karena jatuh di perbatasan klaster, sehingga satu angka tidak mewakili perilaku indeks. Rata-rata pada sekumpulan query uji yang beragam memberi perkiraan yang jauh lebih stabil.

Kesalahan kedua adalah menilai hasil ANN sebagai kegagalan total karena recall di bawah 1,00. Skala penilaian yang tepat adalah kebutuhan aplikasi: banyak kebutuhan pencarian tetap layak ketika sembilan dari sepuluh tetangga terbaik ditemukan, selama peringkat teratasnya tetap relevan. recall@k yang rendah perlu diperbaiki dengan melonggarkan parameter pencarian, tetapi nilainya sendiri bukan angka kegagalan mutlak.

Kesalahan ketiga adalah membandingkan recall@k antara dua dataset yang berbeda ukuran atau berbeda dimensi, lalu menyimpulkan indeks mana yang lebih baik. Perbandingan yang adil menggunakan dataset yang sama, nilai k yang sama, dan pengaturan parameter yang setara, sebagaimana diterapkan oleh proyek ANN-Benchmarks.

Ringkasan#

Pencarian ANN mengembalikan sebagian besar tetangga terbaik tanpa jaminan kebenaran penuh karena hanya sebagian dataset yang diperiksa melalui struktur indeks.
recall@k mengukur kesetiaan hasil ANN terhadap jawaban eksak dengan rumus $|A \cap E|/k$ , dihitung pada sekumpulan query uji.
Kecepatan dan recall bergerak berlawanan melalui parameter indeks, dan komprominya dibaca sebagai kurva recall terhadap kecepatan query, bukan sebagai satu angka.

Referensi#

ANN-Benchmarks — GitHub — Proyek benchmark yang membandingkan algoritma ANN dengan kurva recall terhadap kecepatan query.
Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs — arXiv — Artikel Malkov dan Yashunin yang memperkenalkan HNSW dan membahas kompromi pencarian aproksimatif.