information retrievalEvaluation in Information Retrieval

Deddy Wijaya Suliantoro, S.Kom.

Kita sudah melihat beberapa metode retrieval dimulai dari boolean model, TCM, VSM, EBM sampai ke language modeling.

Masalah 1 Bagaimana kita tahu metode mana yang sesuai dengan masalah mana.

Masalah 2 Perlukah memakai stemming? Perlukah memakai stopwordlist? Perlukah normalisasi token?

review [1]

Masalah 3 Apakah perlu kita memakai nilai idf yang dinormalisasi? Atau tidak?

Kuliah hari ini membicarakan bagaimana mengukur keefektifan suatu sistem IR, termasuk metode-metode evaluasi hasil IR.

review [2]

Untuk mengukur keefektifan ad-hoc IR, kita memerlukan test collection yang terdiri dari 3 macam: koleksi dokumen tes information needs (yang diekspresikan sebagai

query) Sebuah set penentuan relevansi

Pendekatan standar dalam mengevaluasi sebuah sistem IR adalah relevansi sebuah dokumen

Dengan pengecekan seluruh isi dokumen, semua koleksi dokumen akan diklasifikasi menjadi 2: dokumen relevan dan tidak relevan.

Evaluasi Sistem IR [1]

Penentuan relevansi yang hanya membagi dokumen menjadi 2 ini (relevan dan non-relevan) disebut sebagai binary relevance judgement.

Pengecekan tersebut dilakukan secara manual dan sering disebut sebagai gold standard atau ground truth judgement

Pengecekan ini harus dilakukan dalam jumlah yang besar dan beragam karena hasil retrieval akan berbeda untuk dokumen berbeda dan information needs yang berbeda.

Evaluasi Sistem IR [2]

Bagaimana suatu dokumen ditentukan relevan atau tidak? Ditentukan dari information needs-nya, bukan dari query-nya.

Tidak berarti suatu dokumen yang memuat semua isi query adalah dokumen yang relevan.

Evaluasi Sistem IR [3]

Berikut ini adalah beberapa test collection dan evaluasi-evaluasi yang sudah dilakukan oleh beberapa lembaga.

Cranfield pioner, tahun 1950an TREC dilakukan oleh NIST, sejak

1992 CLEF European Language Reuters Text Classification

Standard Test Collection

2 pengukuran dasar dan paling sering digunakan adalah precision dan recall Precision adalah: Bagian dari dokumen

te-retrieve yang relevan. Recall adalah: bagian dari dokumen

relevan yang te-retrieve.

Evaluation dari Unranked Retrieval

Precision & Recall

Gambar di atas adalah merupakan gambar tabel ketergantungan untuk menghitung nilai precision dan recall.

Rumusnya:

Precision & Recall

Jumlah dokumen (N) yang dipakai di dalam korpus dihitung dari tp + fp + tn + fn.

Alternatif yang dapat digunakan untuk mengevaluasi adalah menghitung accuracy.

Accuracy didapat dari (tp+tn)/N.

Precision, Recall, & Accuracy

Latihan: Sebuah sistem IR mengembalikan 8 dokumen

relevan dan 10 dokumen non-relevan dari total 20 dokumen relevan yang ada dari 60 dokumen dalam korpus.

Hitung precision, recall, dan accuracy-nya! (Gunakan tabel ketergantungan untuk mempermudah Anda)

Precision, Recall, & Accuracy

Muncul anggapan yang mengatakan bahwa precision, recall, serta accuracy belum merupakan pengukur yang baik untuk evaluasi

Alasannya: Nilai precision dan recall memiliki trade-off. Nilai

accuracy tidak mempertimbangkannya. Perbedaan kebutuhan user akan precision dan

recall. Perhitungan lain selain accuracy yang

memperhitungkan trade-off dari precision dan recall adalah F measure

Precision, Recall, & Accuracy

Rumus di atas adalah rumus perhitungan F Measure yang mempertimbangkan precision, recall, dan nilai ß sebagai pemberat.

Nilai ß =0.5 berarti pemberat untuk precision 2x lipat

Nilai ß = 2 berarti pemberat untuk recall 2x lipat

F Measure

Nilai ß = 1 berarti precision dan recall dianggap setara.

Nilai ß = 1 ini sering ditulis menjadi F1, singkatan dari Fß=1 . Hasil perhitungannya sering disebut juga sebagai balanced F-score

Jadi Apa keuntungan menggunakan F Measure dibandingkan dengan accuracy?

F Measure

Precision dan Recall di atas dapat dipakai saat kita hanya mengevaluasi sebuah sistem tanpa mempertimbangkan tingkat relevansi suatu dokumen (ranked retrieval)

Kita bisa menggunakan precision-recall curve untuk mengevaluasi hasil dari sebuah ranked retrieval. (Mempertimbangkan ranking dari dokumen hasil retrieval)

Evaluation dari Ranked Retrieval

Misalkan ada 10 dokumen relevan untuk query q:

Rq = {d3, d5, d9, d25, d39, d44, d56, d71, d89, d123} Setelah diberikan query q kepada sistem, maka

sistem itu mengembalikan 15 dokumen dengan urutan ranking sebagai berikut:

Evaluation dari Ranked Retrieval

Dokumen d123 ada di tingkat recall 10%, dan berada di peringkat pertama.

(1 dokumen relevan dan 0 dokumen non-relevan).

Berarti, precision di recall 10% adalah 100%

Evaluation dari Ranked Retrieval

Dokumen d56 ada di tingkat recall 20%, dan berada di peringkat ketiga.

(2 dokumen relevan dan 1 dokumen non-relevan).

Berarti, precision di recall 20% adalah 2/3 = 66%

Evaluation dari Ranked Retrieval

Dokumen d9 ada di tingkat recall 30%, dan berada di peringkat keenam.

(3 dokumen relevan dan 3 dokumen non-relevan).

Berarti, precision di recall 30% adalah 3/6 = 50%

Evaluation dari Ranked Retrieval

Hitung precision untuk tingkat recall 40% dan 50%!

Evaluation dari Ranked Retrieval

Ini adalah precision-recall curve yang didapat dari perhitungan interpolated precision

Evaluation dari Ranked Retrieval

Bagaimana kalau ada 100 dokumen relevan dalam korpus?

Apakah kita harus menghitung precision dari tiap dokumen relevan yang ditemukan? (tingkat recall 1%, 2%, 3%, …, 100%)

eleven-point interpolated average precision tingkat recall 0%, 10%, 20%, 30%, …, 100%

Bagaimana untuk 3 dokumen relevan saja?

Evaluation dari Ranked Retrieval

Contoh: Rq = {d3, d56, d129} Kembalian sistem misalkan sama

dengan contoh di atas:

Evaluation dari Ranked Retrieval

Berarti ada 3 tingkat recall 33,3%, 66,6%, dan 100%.

Silahkan hitung untuk masing-masing tingkat recall!

Evaluation dari Ranked Retrieval

Tingkat recall 33,3% precision 33,3% Tingkat recall 66,6% precision 25% Tingkat recall 100% precision 20%

Evaluation dari Ranked Retrieval

Ada 5 dokumen relevan Hasil retrieved seperti gambar di atas Buat curve-nya!

Evaluation dari Ranked Retrieval

Dalam pengevaluasian, tidak dilakukan dengan satu set query saja, maka akan dihitung rata-rata precision untuk tiap level recall.

Dari dua contoh di atas, average precision untuk tingkat recall 20% adalah:(66,6%+33,3%)/2 = 49.95%

Evaluation dari Ranked Retrieval

Any Questions ??Evaluation in Information Retrieval

Deddy Wijaya Suliantoro, S.Kom.

Jangan lupa, minggu depan adalah presentasi Project-2.

Presentasi akan dibagi dalam 2 pertemuan (seperti project 1)

Urutan akan sekali lagi diacak Harap disiapkan sebaik-baiknya. Perlu diingat, mini 2 juga dikumpul

paling lambat Selasa depan (9 November 2010)

( ! ) notification

Project 3 IR: Presentasi Metode Klasifikasi n Clustering (Kelompok)

pertemuan terakhir dan satu pertemuan tambahan.

Silahkan cari salah satu metode klasifikasi/clustering yang akan dipresentasikan, kumpulkan paling lambat hari Selasa depan.

Bisa mengumpulkan via sms, e-mail, ataupun bertemu langsung.

( ! ) notification