Mengukur Recall@k

Penyetelan pencarian vektor hanya bermakna bila kualitasnya diukur dengan metrik yang tetap, dan ukuran yang paling umum untuk itu adalah recall@k. Topik ini membahas dari mana himpunan ground truth, yaitu jawaban acuan yang dianggap benar, dapat diperoleh, bagaimana recall@k dihitung melalui prosedur yang dapat diulang, dan batasan apa yang melekat pada recall sebagai satu angka. Simulasi di dalam topik ini menghitung recall@10 untuk dua pengaturan pencarian pada dataset uji yang sama, lengkap dengan cara membaca hasilnya.

Dari mana ground truth berasal#

Recall@k mengukur kesetiaan hasil pencarian terhadap jawaban acuan, sehingga pengukurannya memerlukan himpunan ground truth untuk setiap query uji. Jika $E$ adalah himpunan $k$ jawaban acuan dan $A$ adalah himpunan $k$ hasil sistem, maka:

Sumber ground truth pertama adalah jawaban eksak yang dihitung melalui pemindaian penuh. Untuk dataset uji berukuran sedang, seluruh vektor dipindai sekali untuk setiap query uji, dan sepuluh vektor dengan jarak terkecil disimpan sebagai jawaban eksak. Pemindaian ini mahal saat dijalankan, tetapi biayanya dibayar sekali karena jawabannya digunakan berulang untuk menilai banyak pengaturan. Apabila dataset produksi terlalu besar untuk dipindai penuh, jawaban eksak dapat dihitung pada subhimpunan yang mewakili keseluruhan data, misalnya seratus ribu vektor terpilih acak, dan perbandingan antar pengaturan tetap sah selama subhimpunan yang sama digunakan untuk semuanya.

Sumber kedua adalah penilaian manusia. Jawaban eksak hanya menjamin kesetiaan terhadap jarak terkecil pada satu model embedding, sedangkan relevansi semantik bagi pengguna tidak selalu jatuh pada jarak terkecil. Untuk kebutuhan seperti pencarian dokumen panduan, sekelompok penilai dapat menandai dokumen mana yang sungguh menjawab query, dan himpunan tanda tersebut menjadi ground truth kedua. Kedua sumber menjawab pertanyaan yang berbeda, yaitu kesetiaan geometris dan relevansi isi, sehingga keduanya saling melengkapi alih-alih saling menggantikan.

Prosedur mengukur recall@k#

Pengukuran yang dapat dibandingkan antar waktu memerlukan prosedur yang dijaga tetap. Langkahnya berurutan sebagai berikut:

1. Pilih sekumpulan query uji yang mencerminkan query nyata, dengan jumlah yang cukup agar rata-ratanya stabil, misalnya 20 hingga 100 query.
2. Tetapkan nilai k yang sama dengan nilai k yang digunakan aplikasi, karena recall@10 tidak memberi tahu apa pun tentang perilaku recall@1.
3. Hitung jawaban eksak atau susun penilaian manusia untuk setiap query uji, lalu simpan hasilnya sebagai ground truth.
4. Jalankan sistem pencarian dengan satu pengaturan parameter, catat hasil top-k untuk setiap query, dan hitung $|A \cap E|/k$ per query.
5. Rata-ratakan recall per query, catat angkanya bersama biayanya, lalu ulangi langkah sebelumnya untuk pengaturan berikutnya pada data yang sama.

Dua langkah yang sering tidak dikerjakan dengan sungguh-sungguh adalah pemilihan query uji dan penyimpanan jawaban acuan. Pemilihan query uji yang condong ke kasus mudah menghasilkan recall tinggi yang menyesatkan, sedangkan jawaban acuan yang tidak disimpan memaksa pemindaian penuh diulang setiap kali pengaturan baru dinilai. Kedua langkah tersebut adalah pekerjaan sekali jalan yang menopang seluruh pengukuran berikutnya, sehingga waktu yang dihabiskan pada kedua langkah biasanya kembali dalam bentuk keputusan penyetelan yang lebih dapat dipercaya.

Simulasi: dua pengaturan pada dataset uji#

Simulasi berikut mengukur recall@10 untuk dua pengaturan pencarian pada dataset yang sama. Dataset ujinya berisi 800 vektor berdimensi 16 yang berasal dari delapan klaster saling menembus, ditambah 20 query uji. Ground truth-nya adalah jawaban eksak top-10 dari pemindaian penuh. Dua pengaturan pencarian disimulasikan sebagaimana perilaku parameter nprobe pada indeks IVF, yaitu hanya klaster yang pusatnya terdekat ke query yang disapu, dengan empat klaster untuk pengaturan A dan dua klaster untuk pengaturan B.

"""Mengukur recall@10 dua pengaturan pencarian dibanding jawaban eksak."""
import numpy as np

rng = np.random.default_rng(7)

# Dataset uji: 800 vektor 16 dimensi dalam 8 klaster yang saling menembus,
# ditambah 20 query uji dari populasi yang sama
pusat = rng.standard_normal((8, 16)) * 3.0
X = np.concatenate(
    [pusat[c] + 2.0 * rng.standard_normal((100, 16)) for c in range(8)])
Q = rng.standard_normal((20, 16)) * 3.0
k = 10

# Ground truth: jawaban eksak top-10 dari pemindaian penuh seluruh dataset
jarak_penuh = np.linalg.norm(X[None, :, :] - Q[:, None, :], axis=2)
urut_eksak = np.argsort(jarak_penuh, axis=1)

# Dua pengaturan pencarian disimulasikan sebagaimana parameter nprobe pada
# indeks IVF: hanya klaster yang pusatnya terdekat ke query yang disapu
def hasil_ann(qi, nprobe):
    jarak_klaster = np.linalg.norm(pusat - Q[qi], axis=1)
    terpilih = np.sort(np.argsort(jarak_klaster)[:nprobe])
    kandidat = np.concatenate(
        [np.arange(c * 100, (c + 1) * 100) for c in terpilih])
    jarak_kandidat = np.linalg.norm(X[kandidat] - Q[qi], axis=1)
    urut = kandidat[np.argsort(jarak_kandidat)]
    return set(urut[:k].tolist())

for label, nprobe in (("A", 4), ("B", 2)):
    recall = []
    for qi in range(Q.shape[0]):
        irisan = hasil_ann(qi, nprobe) & set(urut_eksak[qi, :k].tolist())
        recall.append(len(irisan) / k)
    recall = np.array(recall)
    print(f"Pengaturan {label} (nprobe={nprobe}): recall@{k} per query")
    print("  " + " ".join(f"{r:.2f}" for r in np.round(recall, 2)))
    print(f"  rata-rata = {np.round(np.mean(recall), 3):.3f}")
    print()

Pengaturan A (nprobe=4): recall@10 per query
  1.00 1.00 0.90 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 0.90 0.90 1.00 1.00 1.00 1.00 1.00 0.90
  rata-rata = 0.980

Pengaturan B (nprobe=2): recall@10 per query
  1.00 0.90 0.70 1.00 1.00 0.80 1.00 0.90 0.90 0.90 1.00 1.00 0.80 0.90 1.00 0.80 0.80 1.00 0.50 0.90
  rata-rata = 0.890

Dua hal terbaca dari keluaran tersebut. Pertama, rata-rata kedua pengaturan: pengaturan A menemukan 196 dari 200 posisi jawaban eksak sehingga rata-ratanya 0,980, sedangkan pengaturan B menemukan 178 dari 200 posisi sehingga rata-ratanya 0,890. Dengan k = 10, pengaturan A kehilangan rata-rata 0,2 tetangga per query, sedangkan pengaturan B kehilangan 1,1 tetangga per query. Kedua, sebaran per query: nilai pengaturan B bergerak dari 0,50 hingga 1,00, dan satu query hanya menemukan lima dari sepuluh tetangganya. Rata-rata menyembunyikan kasus terburuk tersebut, sehingga nilai minimum atau jumlah query di bawah ambang yang ditetapkan layak dicatat bersama rata-ratanya.

Batas recall sebagai satu angka#

Recall@k memadatkan banyak aspek menjadi satu angka, dan pemadatan itu menghilangkan sebagian informasi. Rumusnya hanya menghitung keanggotaan himpunan tanpa melihat urutan, sehingga tetangga eksak yang hilang dari peringkat pertama dan yang hilang dari peringkat kesepuluh sama-sama mengurangi recall sebesar $1/k$. Satu angka rata-rata juga menyamarkan sebaran antar query, sebagaimana terlihat pada pengaturan B yang rata-ratanya 0,890 padahal ada query dengan nilai 0,50. Recall juga tidak menyatakan relevansi, karena angkanya dihitung terhadap jawaban acuan yang sudah ditetapkan, bukan terhadap kepuasan pengguna yang sesungguhnya.

Batas-batas tersebut bukan alasan untuk membuang recall@k, melainkan alasan untuk melengkapinya. Angka rata-rata dilaporkan bersama sebaran per query, ground truth geometris dipasangkan dengan penilaian manusia untuk kasus yang relevansinya dipertanyakan, dan pengaturan yang dibandingkan selalu mencantumkan biayanya. Dengan pelengkap tersebut, satu angka recall menjadi titik awal pembacaan yang lengkap, bukan kesimpulan tunggal.

Kesalahan umum#

Kesalahan pertama adalah membandingkan recall dua pengaturan yang diukur pada dataset uji yang berbeda, baik ukurannya maupun isinya. Recall bergantung pada data, karena jawaban eksak dan sebaran klaster ikut menentukan berapa banyak tetangga yang terlewat. Perbandingan yang sah menggunakan dataset uji yang sama, nilai k yang sama, dan prosedur yang sama, sebagaimana dilakukan oleh proyek ANN-Benchmarks pada dataset publiknya.

Kesalahan kedua adalah menyamakan recall tinggi dengan hasil yang pasti relevan. Recall@10 sebesar 1,00 berarti sistem menemukan sepuluh vektor terdekat menurut metrik jarak, bukan sepuluh dokumen yang paling menjawab pertanyaan. Ketidaksesuaian antara kedekatan geometris dan relevansi semantik baru terlihat melalui penilaian manusia, sehingga keduanya perlu dijalankan bersama sebelum sistem dinyatakan siap.

Kesalahan ketiga adalah menilai recall dengan jawaban eksak yang dihitung dengan metrik jarak yang berbeda dari metrik pencarian. Jawaban eksak untuk jarak Euclidean dan untuk cosine tidak selalu berisi anggota yang sama, sehingga recall terhadap jawaban acuan yang salah menghasilkan angka yang rapi tetapi tidak menjelaskan perilaku sistem. Metrik pada pembuatan ground truth harus sama dengan metrik pada pencarian yang dinilai.

Ringkasan#

• Ground truth diperoleh dari dua sumber, yaitu jawaban eksak hasil pemindaian penuh atau subhimpunan mewakili, dan penilaian manusia untuk relevansi semantik.
• recall@k dihitung sebagai $|A \cap E|/k$ per query lalu dirata-ratakan atas sekumpulan query uji, dengan nilai k yang sama dengan yang digunakan aplikasi.
• Recall sebagai satu angka menyembunyikan urutan hasil, sebaran antar query, dan relevansi semantik, sehingga dilaporkan bersama sebaran, biaya, dan penilaian manusia.

Referensi#

• ANN-Benchmarks — GitHub — Proyek benchmark yang menilai algoritma ANN dengan kurva recall terhadap kecepatan query pada dataset publik.