Sistem Temu-Kembali Informasi Perhitungan Kemiripan (Pembobotan Term dan Penskoran dalam Model Ruang Vektor, Penskoran dalam Sistem Pencarian Lengkap)
Husni Program Studi Teknik Informatika Universitas Trunojoyo Madura
Semeter Gasal 2015 - 15 Okt. 2015
Outline • • • • • • • • •
Temu-kembali Teranking Penskoran dokumen Frekuensi term (dalam dokumen) Statistika koleksi (frekuensi dokumen) tf-idf Skema pembobotan Penskoran ruang vektor Percepatan ranking ruang vektor Sistem pencarian lengkap
Boolean Retrieval: Review • Sejauh ini, query pada pemrosesan boolean: – dokumen cocok atau tidak • Bagus bagi pengguna ahli (pakar) yang paham presisi dari kebutuhannya dan koleksi • Bagus juga buat aplikasi: dapat dengan mudah memperoleh dan menyajikan ribuan hasil • Tidak baik bagi mayoritas pengguna – Kebanyakan pengguna tak-mampu menuliskan query boolean (atau mampu tetapi dianggap merepotkan) – Kebanyakan pengguna tidak mau menjelajah ribuan hasil pemrosesan Query • Hal ini terutama berlaku pada pencarian web.
Masalah dengan Pencarian Boolean: pesta atau lapar • Query boolean sering mengakibatkan terlalu sedikit (=0) atau terlalu banyak (ribuan) hasil • Query 1: “standard user dlink 650” → 200,000 hits • Query 2: “standard user dlink 650 no card found”: 0 hits • Perlu banyak keahlian untuk membuat query yang menghasilkan jumlah hit tepat dan sangat berguna • AND memberikan terlalu sedikit; OR memberikan terlalu banyak.
Model Retrieval Berperingkat • Daripada sehimpunan dokumen yang memenuhi ekspresi query, dalam model retrieval berperingkat, sistem mengembalikan dokumen-dokumen berperingkat teratas (top k) dalam koleksi yang berkaitan dengan query • Query teks bebas: Daripada bahasa query operator dan ekspresi, query pengguna dapat hanya satu atau dua kata dalam bahasa manusia • Prinsipnya, ada dua pilihan di sini: – Bahasa query dan model retrieval – Tetapi praktisnya, model retrieval teranking telah diasosiasikan dengan query teks bebas.
Anda setuju?
Pesta atau Lapar: Tidak terjadi di Retrieval Berperingkat • Ketika sistem menyajikan himpunan hasil berperingkat, besarnya himpunan tersebut tidak jadi persoalan – Pegguna tidak perlu menjelajah semua hasil, mulai dari yang tertinggi rankingnya – Hanya menunjukkan top k ( ≈ 10) hasil – Tidak membanjiri pengguna – Alasan: algoritma ranking bekerja dengan baik 6
Penskoran: Basis Retrieval Berperingkat • Ingin mengembalikan urutan dokumen yang mungkin paling berguna bagi pencari • Bagaimana menentukan urutan ranking dokumen-dokumen dalam koleksi berkaitan dengan query? • Tentukan suatu skor misalya dalam [0, 1] untuk setiap dokumen • Skor ini mengukur seberapa "cocok" dokumen dengan query. 7
Skor Pencocokan Query-Dokumen • Perlu cara penentuan skor terhadap suatu pasangan query-dokumen • Kita mulai dengan query satu-term • Jika term query tidak hadir dalam dokumen: – Skor bernilai 0 – Mengapa? Dapat lebih baik? • Semakin sering term query hadir di dalam dokumen, semakin tinggi skornya (harusnya...) • Akan kita lihat sejumlah alternatif... 8
1: Koefisien Jaccard • Ukuran kesamaan dua himpunan A dan B sering digunakan • jaccard(A,B) = |A ∩ B| / |A ∪ B| • jaccard(A,A) = 1 • jaccard(A,B) = 0 jika A ∩ B = 0 • A dan B tidak harus berukuran sama • Selalu menetapkan nilai antara 0 dan 1 • Terlihat bahwa dalam konsteks k-gram terjadi overlap antara dua kata. 9
Koefisien Jaccard: Contoh Penskoran • Berapa skor kecocokan query-dokumen yang dihitung koefisien Jaccard untuk dua dokumen berikut? • Query: ides of march • Dokumen 1: caesar died in march • Dokumen 2: the long march • jaccard(Q,D) = |Q ∩ D| / |Q ∪ D| • jaccard(Query, Dokumen1) = 1/6 • jaccard(Query, Dokumen2) = 1/5 10
Persoalan Penskoran di Jaccard • Skor kecocokan menurun seiring bertambahnya panjang dokumen • Perlu normalisasi yang lebih canggih terhadap panjang dokumen • Gunakan normalisasi panjang menggantikan |A ∩ B|/|A ∪ B| (Jaccard) • 1) Tidak mempertimbangkan term frequency (berapa kali term muncul di dalam dokumen) – Pada J.C. dokumen merupakan himpunan kata, bukan tas kata (bag of words)
• 2) Term yang jarang hadir di dalam koleksi harusnya lebih informatif daripada term yang sering - Jaccard tidak melibatkan informasi ini. 11
Matriks kejadian term-dokumen biner: Review • Setiap dokumen direpresentasikan oleh suatu vektor biner∈ {0,1}|V|.
12
Matrisk Hitungan Term-Dokumen • Pertimbangkan jumlah kemunculan term di dalam dokumen: – Setiap dokumen adalah vektor hitungan dalam ℕv: [perhatikan kolom di bawah!]
13
Model Bag of words • Representasi vektor tidak melihat urutan (posisi) dari kata di dalam dokumen • “John is quicker than Mary” dan ”Mary is quicker than John” mempunyai vektor yang sama • Ini dinamakan model bag of words (tas kata) • Terlihat sebagai langkah mundur, padahal indeks posisional telah mampu membedakan dua dokumen ini 14
Term frequency tf • Term frequency tft,d dari term t dalam dokumen d didefinisikan sebagai jumlah (berapa kali) t hadir dalam d • tf digunakan saat perhitungan skor kecocokan querydokumen - caranya? • Frekuensi term mentah bukanlah apa yang diinginkan: – Dokumen dengan 10 kemunculan term adalah lebih relevan daripada dokumen dengan 1 kemunculan term tersebut – Tetapi bukan 10 kali lebih relevan • Relevansi tidak naik proporsional dengan term frequency. Frekuensi dalam IR = Hitungan
15
Proyek Fechner • Gustav Fechner (1801 - 1887) terobsesi dengan relasi mind dan matter • Variasi dari kuantitas fisik (misal energi cahaya) menyebabkan variasi dalam intensitas atau kualitas dari pengalaman subyektif • Fechner mengusulkan fungsi logaritmik untuk hal berdimensi banyak – Peningkatan intensitas stimulus dengan suatu faktor tertentu (katakanlah 10 kali) selalu menghasilkan kenaikan yang sama pada skala psikologis • Jika peningkatan frekuensi term dari 10 ke100 menaikkan relevansi sebesar1 maka peningkatan frekuensi dari 100 ke 1000 juga menaikkan relevansi sebesar 1. 16
Pembobotan Frekuensi Log • Bobot frekuensi log dari term t dalam d adalah
• 0 → 0, 1 → 1, 2 → 1.3, 10 → 2, 1000 → 4, dll. • Skor untuk pasangan dokumen-query: sum (jumlah total) terms t beririsan (ada dalam q dan d)
• Skor bernilai 0 jika term query tidak hadir dalam dokumen • Jika q' ⊆ q maka skor (d,q’) <= skor (d,q) masalah? 17
Pen-skala-an tf Normal vs. Sublinear
• Rumus di atas mendefinisikan penskalaan tf sublinier • Pendekatan paling simpel (normal) adalah menggunakan jumlah kemunculan term dalam dokumen (frekuensi) • Tetapi... sublinier tf harusnya lebih baik. 18
Properti dari Logaritma • • • • • • • • •
y = loga x iff x = ay loga 1 = 0 loga a = 1 loga (xy) = loga x + loga y loga (x/y) = loga x - loga y loga (xb) = b loga x logb x = loga x / loga b log x pada dasarnya log10 x ln x pada dasarnya loge x (e = 2.7182… Napier atau bilangan Euler) logaritma natural. 19
Document frequency -df • Term yang jarang dalam koleksi keseluruhan - lebih informatif daripada term yang sering muncul – ingat kembali stop words
• Perhatikan term dalam query yang jarang hadir dalam koleksi (misal: arachnocentric) • Dokumen yang mengandung term ini kemungkinan besar sangat relevan dengan query (kebutuhan informasi) arachnocentric • → Kita ingin bobot tinggi untuk term yang jarang seperti arachnocentric. 20
Document frequency: df • Secara umum term yang sering muncul menjadi kurang informatif daripada yang jarang • Perhatikan suatu term query yang sering dalam koleksi (seperti: high, increase, line) • Dokumen yang mengandung term tersebut kemungkinan besar lebih relevan daripada yang tidak • Tetapi bagaimana dengan query yang mengandung dua term, misal: high arachnocentric • Bagi term yang sering hadir dalam dokumen, misalnya high, kita inginkan bobot positif tetapi lebih rendah daripada terhadap term yang jarang dalam koleksi, seperti arachnocentric • Akan digunakan document frequency (df) untuk menangkap ini. • http://www.wordfrequency.info
21
Bobot idf • dft adalah frekuensi dokumen dari t atau jumlah dokumen yang mengandung t
– dft adalah ukuran inversi dari ke-informatif-an t (lebih kecil lebih baik) – dft ≤ N
• idf (inverse document frequency) dari t didefinisikan sebagai
Fungsi dari t saja, tidak bergantung pada dokumen
– Digunakan log (N/dft), bukan N/dft untuk “mengurangi” pengaruh dari idf. 22
Contoh idf: N = 1 juta Term calpurnia
dft
idft 1
6
animal
100
4
sunday
1000
3
10000
2
100000
1
1000000
0
fly under the
• idft = log ( N/dft ) • Ada satu nilai idf untuk setiap term t dalam koleksi 23
Frekuensi Koleksi vs. Dokumen • Frekuensi koleksi dari t adalah jumlah kemunculan t di dalam koleksi, termasuk jumlah kemunculan dalam dokumen yang sama • Contoh: Kata
Frekuensi Koleksi
Frekuensi Dokumen
insurance
10440
3997
try
10422
8760
• Kata mana yang merupakan term pencarian yang lebih baik (dan harus mendapatkan bobot lebih tinggi dalam query seperti "try insurance")? 24
Pembobotan tf-idf • Bobot tf-idf dari suatu term adalah perkalian dari bobot tf-nya dan bobot idf-nya: • Skema pembobotan yang paling terkenal dalam information retrieval: – Tanda “-” dalam tf-idf adalah strip, bukan pengurangan! – Alternatif penulisan: tf.idf, tf x idf • Bertambah mengikuti jumlah kemunculan term dalam dokumen • Bertambah mengikuti kejarangan term di dalam koleksi.
25
Ranking Akhir dari Dokumen untuk Query
• Masih ada pilihan lainnya ...
26
Pengaruh idf pada Ranking • Berpengaruhkah idf pada ranking hasil query satu term? misal Q: – iPhone
• idf tidak mempengaruhi perankingan query satu term - karena ada satu nilai idf untuk setiap term dalam koleksi.
– idf mempengaruhi ranking dokumen untuk query minimal dua term. – Untuk query capricious person, pembobotan idf menyebabkan hitungan capricious lebih besar dalam perankingan dokumen akhir daripada hitungan person. 27
Biner → Hitungan → Matriks Bobot
• Setiap dokumen direpresentasikan oleh vektor bobot tf-idf bernilai ril ∈ R|V| 28
Dokumen sebagai Vektor • Diperoleh ruang vektor berdimensi |V| – Terms adalah sumbu dari ruang – Dokumen adalah titik atau vektor di dalam ruang tersebut
• Dimensi terlalu tinggi: – 400,000 dalam RCV1 – puluhan juta dimensi ketika kita menerapkan ini pada web search engine
• Dinamakan vektor sangat jarang- sebagian besar entri bernilai nol. 29
Query sebagai Vektor • Ide kunci 1: lakukan yang sama terhadap query: tampilkan sebagai vektor dalam ruang tersebut • Ide kunci 2: Ranking dokumen sesuai dengan kedekatannya terhadap query dalam ruang ini – Kedekatan = kemiripan vektor-vektor – Kedekatan≈ inversi dari jarak
• Review: Ini dilakukan karena ingin mendapatkan yang lebih baik daripada model boolean • Gantinya: berikan peringkat lebih tinggi untuk dokumen yang lebih relevan. 30
Memformalkan Kedekatan pada Ruang Vektor • Pertama: Jarak antara dua titik – ( = jarak antara titik ujung dari dua vektor)
• Jarak euclidean? • Jarak euclidean merupakan ide yang tidak baik. . . • . . . karena jarak euclidean akan BESAR bagi vektor-vektor dengan panjang berbeda. 31
Mengapa Jarak Ide yang Buruk • Jarak euclidean antara q dan d2 adalah besar meskipun sebaran term dalam query q dan sebaran term dalam dokumen d2 sangat mirip.
32
Menggunakan Sudut (bukan Jarak) • Eksperimen sederhana – Ambil dokumen d dan tambahkan ke dirinya sendiri – Namakan dokumen ini d′ – “Secara semantik” d dan d′ mempunyai isi yang sama – Tetapi jarak euclidean antara dua dokumen dapat sangat besar • Jika representasi tft,d digunakan maka sudut antara dua dokumen adalah 0, sesuai dengan kemiripan maksimal • Ide kunci: Dokumen diranking mengikuti besarnya sudut dengan query. 33
Dari sudut ke Cosinus • Dua gagasan berikut sama: – Dokumen diranking urut naik mengikuti besarnya sudut antara query dan dokumen – Dokumen diranking urut turun mengikuti nilai cosinus (query, dokumen)
• Cosinus adalah fungsi yang secara monoton menurun pada interval [0o, 180o] 34
Dari sudut ke Cosinus
• Tetapi bagaimanan dan mengapa haruskah menghitung cosinus? 35
Normalisasi Panjang • Vektor dapat dinormalisasi panjangya dengan membagi setiap komponennya dengan panjangnya - digunakan norm L2:
• Pembagian vektor dengan norm L2 -nya menjadikannya suatu vektor satuan (panjang) • Pengaruh pada dua dokumen d dan d′ (d ditambahkan ke dirinya): keduanya punya vektor identik setelah normalisasi panjang – Akibat: dokumen panjang dan pendek mempunyai bobot yang dapat dibandingkan (comparable). 36
Cosinus(query,dokumen) Vektor satuan
qi : bobot tf-idf dari term i dalam query di : bobot tf-idf dari term i dalam dokumen cos(q,d) : kemiripan cosinus (cosim) antara q dan d … atau cosinus dari sudut antara q dan d. 37
Cosinus untuk Vektor Panjang Ternormalisasi • Untuk vektor length-normalized, cosine similarity merupakan dot product (atau scalar product):
38
Ilustrasi Cosine Similarity
39
Cosine Similarity Antara 3 Dokumen • Semirip apakah novel-novel tersebut – SaS: Sense and
Sensibility – PaP: Pride and Prejudice, and – WH: Wuthering Heights? Catatan: untuk menyederhanakan contoh ini, tidak dilakukan pembobotan idf
40
Cosine Similarity Antara 3 Dokumen Pembobotan Frekuensi Log
Setelah normalisasi panjang
• cos(SaS,PaP) ≈ • 0.789 × 0.832 + 0.515 × 0.555 + 0.335 × 0.0 + 0.0 × 0.0
• • • •
≈ 0.94 cos(SaS,WH) ≈ 0.79 cos(PaP,WH) ≈ 0.69 Mengapa cos(SaS,PaP) > cos(SaS,WH)? 41
Menghitung Skore Cosinus
42
Pengamatan • Inverted index yang digunakan pada pemrosesan query boolean masih penting bagi retrieval dokumen dengan penskoran teratas (top k) • Tidak tepat memeriksa semua dokumen untuk menghitung dokumen top K (lebih mirip) terhadap query input • Query normalnya adalah dokumen pendek Coba dengan Query panjang! 43
Varian Pembobotan tf-idf
• Kolom "n" merupakan singkatan dari skema pembobotan. • Mengapa basis dari log dalam idf tidak penting? 44
Pembobotan Berbeda untuk Query vs. Dokumen • Banyak search engines membolehkan pembobotan berbeda untuk Queries vs. Dokumen • Notasi SMART: menunjukkan kombinasi penggunaan dalam engine, dengan notasi ddd.qqq, menggunakan akronim dari tabel sebelumnya • Suatu skema pembobotan yang sangat standard adalah lnc.ltc Ide Jelek? • Dokumen: tf logaritmik (l sebagai karakter pertama), bukan idf, dan normalisasi cosinus • Query: tf logaritmik (l dalam kolom terkiri), idf (t dalam kolom kedua), normalisasi cosinus … 45
Contoh tf-idf : Inc.ltc • Dokumen: car insurance auto insurance • Query: best car insurance
Latihan: berapa nilai N, yaitu jumlah dokumen? Skor= 0+0+0.27+0.53 = 0.8 46
Rangkuman: Perankingan Ruang Vektor • Merepresentasikan query sebagai vektor tf-idf berbobot • Hitung skor kemiripan cosinus antara vektor Query dan setiap vektor dokumen • Meranking dokumen sesuai dengan skor kemiripan (menurun) • Kembalikan top K (misal: K = 10) kepada pengguna. 47
Pertanyaan •?
48
