Temu-Kembali Informasi 2019...Pemeringkatan sering lebih disukai •Relevansi adalah masalah derajat...
Transcript of Temu-Kembali Informasi 2019...Pemeringkatan sering lebih disukai •Relevansi adalah masalah derajat...
Temu-Kembali Informasi 201904A: Model Boolean & Ruang Vektor
Husni
Husni.trunojoyo.ac.id
Pekan 07
Rekap: Uji interleave
• Prinsip desain dari analisis sensorik
– Tidak meminta peringkat absolut tetapi perbandingan relatifantara alternatif
• Contoh: apakah A lebih bagus daripada B?
– Eksperimen acak
• Interleave results dari (kedua) A dan B
• Memberikan interleaved results ke populasi yang sama dan menanyakanpreferensi mereke
• Uji hipotesis terhadap suara preferensi
2
Rekap: Korelasi Metriks IR dan interleaving
3
Rekap: Selain DCG: Perilaku User Sebagai Predictor Pencarian Sukses [Ahmed et al. WSDM’10]
• Memodelkan perilaku pencarian sekuensial pengguna denganmodel Markov
– Model untuk pola pencarian yang sukses
– Model untuk pola pencarian yang tak berhasil
ML untuk estimasi parameter pada data set beranotasi
4
Temu-Kembali Informasi 201904A: Model Boolean
Husni
Husni.trunojoyo.ac.id
Pekan 07
Abstraksi Arsitektur Search Engine
User
RankerIndexer
Doc Analyzer
Index results
Crawler
Doc Representation Query Rep
(Query)
EvaluationFeedback
Indexed corpus
Ranking procedure
6
Pencarian dengan Query Boolean
• Query boolean– Contoh: “obama” AND “healthcare” NOT “news”
• Prosedur– Cari term query di dalam kamus (dictionary)
– Ambil (retrieve) daftar postingan (posting lists)
– Operasi• AND: interseksi (irisan) daftar postingan
• OR: gabungan (union) daftar postingan
• NOT: bukan daftar postingan
7
Pencarian dengan Query Boolean
• Contoh: operasi AND
128
34
2 4 8 16 32 64
1 2 3 5 8 13 21
Term1
Term2
Memindai postings
Kompleksitas waktu: 𝑂( 𝐿1 +|𝐿2|)
Trik mempercepat: ketika mengerjakan multi-way join, mulai dari term berfrekuensi paling rendahmenuju yang berfrekuensi tertinggi.
8
Kekurangan Model Boolean
• Querynya tidak tepat– Query yang “over-constrained” (term terlalu spesifik): tidak dapat
diperoleh dokumen yang relevan– Query “under-constrained” (term terlalu umum): kebanyakan hasil (over
delivery)– Sulit menemukan posisi yang tepat di antara kedua ekstrem ini (sulit
bagi pengguna untuk menentukan batasan)
• Bahkan jika itu akurat– Tidak semua pengguna ingin menggunakan query seperti itu– Semua dokumen yang relevan tidak sama pentingnya
• Tidak ada yang akan menjelajah (memeriksa) semua hasil yang cocok
• Relevansi adalah masalah derajat!
9
Pemilihan vs. Pemeringkatan Dokumen
+
++ +
---
----
----
-
--+--
Pemeringkatan
Dokumen
rel(d,q)=?
0.98 d1 +
0.95 d2 +
0.83 d3 -
0.80 d4 +
0.76 d5 -
0.56 d6 -
0.34 d7 -
0.21 d8 +
0.21 d9 -
Rel’(q)
Pemilihan
Dokumen
f(d,q)=?
+
+++
--+
-
+--
---
---
1
0
Rel’(q)
True Rel(q)
10
Pemeringkatan sering lebih disukai
• Relevansi adalah masalah derajat
– Lebih mudah bagi pengguna untuk menemukan Query yang sesuai
• Pengguna dapat berhenti menjelajah di mana saja, sehingga batasnya dikendalikan oleh pengguna
– Pengguna yang lebih suka cakupan akan melihat lebih banyak item
– Pengguna yang lebih suka presisi akan melihat hanya sedikit
• Pembenaran Teoritis: Prinsip Peringkat Probabilitas
11
Prosedur Retrieval dalam IR Modern
• Model boolean menyediakan semua kandidat rankingnya
– Temukan dokumen yang memenuhi persyaratan Boolean
• Misal “obama healthcare” -> “obama” OR “healthcare”
• Lakukan perankingan kandidat berdasarkan relevansi
– Penting: notasi relevansi
• Pertimbangkan efisiensi
– Temu-kembali Top-k (Google)
12
Notasi Relevansi
Relevance
(Rep(q), Rep(d))
Similarity
P(r=1|q,d) r {0,1}Probability of Relevance
P(d →q) or P(q →d)
Probabilistic inference
Different
rep & similarity
Vector space
model
(Salton et al., 75)
Prob. distr.
model
(Wong & Yao, 89)
…
Generative ModelRegression
Model
(Fox 83)
Classical
prob. Model
(Robertson &
Sparck Jones, 76)
Doc
generation
Query
generation
LM
approach
(Ponte & Croft, 98)
(Lafferty & Zhai, 01a)
Prob. concept
space model
(Wong & Yao, 95)
Different inference system
Inference
network
model
(Turtle & Croft, 91)
Kuliah hari ini13
Pemahaman Intuitif dari Relevansi
• Mengisi angka ajaib untuk menggambarkan hubungan antara dokumen dan kata-kata
information retrieval retrieved is helpful for you everyone
Doc1 1 1 0 1 1 1 0 1
Doc2 1 0 1 1 1 1 1 0
Query 1 1 0 0 0 0 0 0
Misal 0/1 untuk model Boolean, probabilitas untuk model probabilitas
14
Beberapa Notasi
• Vocabulary V={w1, w2, …, wN} dari Bahasa (language)
• Query q = t1,…,tm, dimana ti V
• Dokumen di = ti1,…,tin, dimana tij V
• Koleksi atau Corpus C= {d1, …, dk}
• Rel(q,d): relevansi dari dokumen d dengan query q
• Rep(d): representasi dari dokumen d
• Rep(q): representasi dari query q
15
Temu-Kembali Informasi 201904A: Model Ruang Vektor
Husni
Husni.trunojoyo.ac.id
Pekan 07
Relevansi = Kemiripan(Relevance = Similarity)
• Asumsi
– Query dan dokumen direpresentasikan dalam bentuk yang sama
• Query dapat dianggap sebagai "dokumen"
– Relevance(d,q) similarity(d,q)
• R(q) = {dC|rel(d,q)>𝜃}, rel(q,d)=(Rep(q), Rep(d))
• Persoalan kunci
– Bagaimana merepresentasikan query/dokumen?
– Bagaimana mendefinisikan ukuran kemiripan (𝑥,𝑦)?
17
Model Ruang Vektor
• Mennampilkan dokumen dan query dengan konsep vektor
– Setiap konsep mendefinisikan satu dimensi
– K konsep mendefinisikan suatu ruang berdimensi tinggi
– Elemen dari vektor bersesuaian dengan bobot konsep
• Misal d=(x1,…,xk), xi adalah “kepentingan” dari konsep i
• Mengukur relevansi
– Jarak antara vektor query dan vektor dokumen dalam ruang konsepini
18
Model VS: Ilustrasi
• Dokumen mana yang lebih dekat ke query?
Olahraga
Pendidikan
Keuangan
D4
D2
D1D5
D3
Query
19
Model VS tidak mengatakan...
• Bagaimana mendefinisikan/memilih “konsep dasar”
– Konsep diasumsikan ortogonal
• Bagaimana menentukan bobot (weights)
– Bobot dalam query menunjukkan pentingnya konsep itu
– Bobot dalam dokumen mengindikasikan seberapa bagus konsepmencirikan dokumen tersebut
• Bagaimana mendefinisikan ukuran kemiripan/jarak.
20
Apa itu "konsep dasar" yang bagus?
• Orthogonal
– Vektor-vektor basis independent secara linier
• Maknanya “Non-overlapping” (tidak tumpang-tindih)
• Tidak ambigu
• Bobot dapat ditentukan secara otomatis dan akurat
• Solusi yang ada
– Terms atau N-grams, missal bag-of-words
– Topik, yaitu model topik
21
Bagaimana Menentukan Bobot?
• PENTING!
• Mengapa?– Sisi query: tidal seua term mempunyai kepentingan sama
– Sisi dokumen: beberapa term membawa lebih banyak informasitentang konten
• Bagaimana?
– Dua heuristik dasar
• TF (Term Frequency) = Within-doc-frequency
• IDF (Inverse Document Frequency)
22
Pembobotan TF
• Gagasan: suatu term lebih penting jika ia muncul lebih seringdi dalam suatu dokumen
• Rumus TF– Jika 𝑓(𝑡, 𝑑) adalah jumlah frekuensi dari term 𝑡 di dalam dok 𝑑
– TF mentah: 𝑡𝑓(𝑡, 𝑑) = 𝑓(𝑡, 𝑑)
23
Normalisasi TF
• Query: iphone 6s
– D1: iPhone 6s receives pre-orders on September 12.
– D2: iPhone 6 has three color options.
– D3: iPhone 6 has three color options. iPhone 6 has three color options. iPhone 6 has three color options.
24
Normalisasi TF
• Dua pandangan mengenai panjang dokumen– Dokumen panjang karena itu bertele-tele– Dokumen panjang karena memiliki lebih banyak konten
• TF mentahan tidak akurat– Variasi Panjang dokumen– “kemunculan berulang" kurang informatif dibandingkan " kemunculan
pertama"– Relevansi tidak meningkat secara proporsional dengan jumlah
kemunculan term
• Umumnya menghukum dokumen panjang, tetapi menghindarihukuman yang berlebihan– Normalisasi panjang berpivot
25
Normalisasi TF
• Penskalaan TF Sub linier
– 𝑡𝑓 𝑡, 𝑑 = ቊ1 + log 𝑓 𝑡, 𝑑 , 𝑗𝑖𝑘𝑎 𝑓 𝑡, 𝑑 > 0
0 , 𝑗𝑖𝑘𝑎 𝑡𝑖𝑑𝑎𝑘
TFNormal
TF Mentah
26
Normalisasi TF
• Penskalaan FT Maksimum
– 𝑡𝑓 𝑡, 𝑑 = 𝛼 + (1 − 𝛼)𝑓(𝑡,𝑑)
max𝑡
𝑓(𝑡,𝑑)
– Normalkan dengan kata berfrekuensi paling besar dalam dokumen
TFNormal
TF Mentah
𝛼
1
27
Frekuensi Dokumen: df
• Gagasan: suatu term lebih diskriminatif (pembeda) jika iamuncul hanya dalam sedikit dokumen
28
Pembobotan IDF
• Solusi
– Berikan bobot lebih tinggi untuk term-term yang jarang
– Formula
• 𝐼𝐷𝐹 𝑡 = 1 + log(𝑁
𝑑𝑓(𝑡))
– Properti yang spesifik corpus
• Independen dari suatu dokumen tunggal
Jumlah total dokumen dalam koleksi
Jumlah dokumen mengandung term 𝑡
Penskalaan Tidak Linier
29
Mengapa Frekuensi Dokumen
• Bagaimana dengan frekuensi term total?
– 𝑡𝑡𝑓 𝑡 = σ𝑑 𝑓(𝑡, 𝑑)
– Tidak dapat mengenali kata-kata yang sering muncul dalamkumpulan dokumen
Word ttf df
try 10422 8760
insurance 10440 3997
Contoh total frekuensi term v.s. frekuensidokumen dalam koleksi Reuters-RCV1.
30
Rekap: Pemilihan & Pemeringkatan Dokumen
+
++ +
---
----
----
-
--+--
Perankingan
Dokumen
rel(d,q)=?
0.98 d1 +
0.95 d2 +
0.83 d3 -
0.80 d4 +
0.76 d5 -
0.56 d6 -
0.34 d7 -
0.21 d8 +
0.21 d9 -
Rel’(q)
Pemilihan
Dokumen
f(d,q)=?
+
+++
--+
-
+--
---
---
1
0
Rel’(q)
True Rel(q)
31
Rekap: Prosedur Retrieval dalam IR Modern
• Model Boolean menyediakan semua kandidat ranking
– Temukan dokumen-dokumen yang memenuhi kondisi Boolean
• Misal “obama healthcare” -> “obama” OR “healthcare”
• Tentukan ranking kandidat berdasarkan relevansinya
– Penting: notasi relevansi
• Pertimbangkan efisiensi
– Temu-kembali Top-k (Google)
32
Pembobotan TF-IDF
• Mengkombinasikan TF dan IDF
– Sering di dalam dok→ tf tinggi→ bobot tinggi
– Jarang dalam koleksi→ idf tinggi→ bobot tinggi
– 𝑤 𝑡, 𝑑 = 𝑇𝐹 𝑡, 𝑑 × 𝐼𝐷𝐹(𝑡)
• Skema representasi dokumen paling terkenal di IR! (G Salton et al. 1983)
“Salton mungkin adalahilmuwan komputer terkemukayang bekerja di bidangpencarian informasi selamahidupnya.” - wikipedia
Gerard Salton Award– penghargaan prestasi tertinggi di IR
33
Mendefinisikan Ukuran Kemiripan yang Bagus
• Jarak Euclidean?
Olahraga
Pendidikan
Keuangan
D4
D2
D1D5
D3
Query
TF-IDF space
34
Mendifinisikan Ukuran Kemiripan yang Bagus
• Jarak Euclidean
– 𝑑𝑖𝑠𝑡 𝑞, 𝑑 = σ𝑡∈𝑉[𝑡𝑓 𝑡, 𝑞 𝑖𝑑𝑓 𝑡 − 𝑡𝑓 𝑡, 𝑑 𝑖𝑑𝑓 𝑡 ]2
– Dokumen yang lebih panjang akan dihukum oleh kata-kata tambahan
– Kita lebih peduli tentang bagaimana kedua vektor ini tumpang tindih
35
Dari Jarak ke Sudut
• Sudut: bagaimana vektor mengalami overlap
– Kemiripan kosinus (cosine similarity) – proyeksi sari satu vektorterhadap lainnya
Olahraga
Keuangan
D1
D2
Query
Ruang TF-IDF
Pilihan sudutPilihan jarakEuclidean
36
Kemiripan Cosinus
• Sudut antara dua vektor
– 𝑐𝑜𝑠𝑖𝑛𝑒 𝑉𝑞 , 𝑉𝑑 =𝑉𝑞×𝑉𝑑
𝑉𝑞 2× 𝑉𝑑 2
=𝑉𝑞
𝑉𝑞 2
×𝑉𝑑
𝑉𝑑 2
– Panjang dokumen dinormalisasiVektor Unit
Vektor TF-IDF
Olahraga
Keuangan
D1
D2
Query
Ruang TF-IDF
37
Komputasi Cepat Cosinus dalam Retrieval
• 𝑐𝑜𝑠𝑖𝑛𝑒 𝑉𝑞 , 𝑉𝑑 = 𝑉𝑞 ×𝑉𝑑
𝑉𝑑 2
– 𝑉𝑞 2akan sama untuk semua dokumen kandidat
– Normalisasi dari 𝑉𝑑 dapat dikerjakan pada waktu indexing
– Hanya melibatkan 𝑡 ∈ 𝑞 ∩ 𝑑
– Score accumulator untuk setiap term query saat menginterseksi(irisan) postingan dari inverted index
38
Komputasi Cepat Cosinus dalam Retrieval
• Menjaga score accumulator untuk setiap doc ketikamemindai daftar postingan
Query = “info security”S(d,q)=g(t1)+…+g(tn) [jumlah TF term-term yang cocok]Info: (d1, 3), (d2, 4), (d3, 1), (d4, 5)Security: (d2, 3), (d4, 1), (d5, 3)
Accumulators: d1 d2 d3 d4 d5(d1,3) => 3 0 0 0 0(d2,4) => 3 4 0 0 0(d3,1) => 3 4 1 0 0(d4,5) => 3 4 1 5 0(d2,3) => 3 7 1 5 0(d4,1) => 3 7 1 6 0(d5,3) => 3 7 1 6 3
info
security
Dapat dengan mudahditerapkan kepembobotan TF-IDF!
Pegang hanyaakumulator paling menjanjikan untukretrieval top K
39
Kelebihan Model Ruang Vektor
• Efektif secara empiris! (kinerja TREC teratas)
• Intuitif
• Mudah diimplementasikan
• Tekah dikaji dengan baik/paling banyak dievaluasi
• The Smart system– Dikembangkan di Cornell: 1960-1999
– Masih digunakan secara luas
• Peringatan: Banyak varian TF-IDF!
40
Kekurangan dari Model Ruang Vektor
• Asumsi independensi term (yaitu BoW)
• Asumsi query dan dokumen sama
• Kurangnya “kecukupan prediktif”
– Pembobotan term sembarang
– Ukuran kemiripan sembarang
• Banyak penyetelan parameter!
41
Yang harus diketahui
• Perankingan dan Pemilihan dokumen
• Gagasan dasar dari model ruang vektor
• Dua heuristic penting dalam model VS
– TF
– IDF
• Ukuran kemiripan untuk model VS
– Euclidean distance v.s. cosine similarity
42
Bacaan Hari Ini
• Chapter 1: Boolean retrieval
– 1.3 Processing Boolean queries
– 1.4 The extended Boolean model versus ranked retrieval
• Chapter 6: Scoring, term weighting and the vector space model
– 6.2 Term frequency and weighting
– 6.3 The vector space model for scoring
– 6.4 Variant tf-idf functions
43
PERTANYAAN?
Terimakasih!
44