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