13. Budi Susanto

4/9/13

Text & Web Mining - Budi Susanto - TI UKDW

1

RETRIEVAL STRATEGIES Budi Susanto


2

Tujuan •  Memahami model probabilitistic retrieval dengan metode

Simple Term Weights. •  Memahami model Extended Boolean untuk IR. •  Memahami language model dengan metode query likelihood untuk IR.

1

4/9/13


3

Diskusi Latihan •  Terdapat 3 dokumen •  D1 = Manajemen Sistem Informasi •  D2 = Sistem Sumber Daya Manusia •  D3 = Manajemen Informasi Penggajian •  Q = informasi daya manusia •  Hitunglah rangking dari semua dokumen terhadap query

dengan pendekatan vector space model!


4

Contoh VSM •  Matrik Term Frekuensi d1 d2 d3

Manajemen 1 0 1

Q

0

Sistem Informasi Sumber Daya Manusia 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0

1

Manajemen Sistem Informasi d1 d2 d3 Q

0.176091 0.176091 0.176091

0 Sumber -‐

-‐

0.176091

-‐

0.176091

-‐

0.176091

-‐

-‐

-‐

0.176091

-‐

=1/1*idf

1

1

Penggajian 0 0 1 0

Daya Manusia Penggajian -‐

-‐

0.477121 0.477121 0.477121 -‐

-‐

0.477121 0.477121

-‐ -‐ 0.477121 -‐

=1/1*idf =1/1*idf

2

4/9/13


5

Contoh VSM •  Length of Document + Query •  D1 = sqrt(3*(0.18^2)) = 0.304999007 •  D2 = sqrt(0.18^2 + 3*(0.48^2)) = 0.844951008 •  D3 = sqrt(2*(0.18^2) + 0.48^2) = 0.538201593 •  Q = qrt(0.18^2 + 2*(0.48^2)) = 0.697350353 •  Kemiripan D dengan Q •  cosSim(D1, Q) = (0.176091 * 0.176091)/(0.304999*0.697350) •  cosSim(D2, Q) = (0.477121* 0.477121+ 0.477121* 0.477121)/ (0.84495*0.69735) •  cosSim(D3, Q) = (0.176091* 0.176091)/(0.5382*0.69735) •  Sehingga urutan ranking: •  D2, D1, D3


6

1. Probabilistic Retrieval •  Model probabilitas menghitung koefisien kemiripan antara

sebuah query dan dokumen sebagai sebuah probabilitas bahwa dokumen tersebut akan relevan dengan query. •  Semua penelitian terhadap probabilitic retrieval berakar pada konsep perkiraan bobot term berdasar seberapa sering term muncul atau tidak dalam dokumen relevan dan non-relevan.

3

4/9/13


7

Simple Term Weights •  Term dalam query dapat dilihat sebagai indikator bahwa

dokumen relevan. •  Sehingga ada atau tidaknya term query dapat digunakan untuk

memprediksi apakah dokumen relevan atau tidak.

•  Operasi dot product semua bobot dapat digunakan untuk

menghitung probabilitas relevansi. •  Sebagian besar model probabilitic mengasumsikan independensi tiap term. •  Karena untuk memperhatikan dependensi tiap term membutuhkan

komputasi lebih mahal dan membutuhkan adanya pelatihan ke sistem.


8

Simple Term Weights q = { t1, t2 } Dokumen Terambil

t1

t1

t2

t1 t2

t2

P(t1 | Di relevan) = ½ P(t1 | Di non relevan) = 2/3 P(t2 | Di relevan) = 1 P(t2 | Di non relevan ) = 1/3

4

4/9/13


9

Simple Term Weights •  Metode Robertson dan Sparck Jones (1976)

menyediakan mekanisme perhitungan probabilitas relevan dan tidak relevan untuk sebuah term. •  Definisi asumsi mutually exclusive independence: •  I1 = distribusi term dalam dokumen relevan adalah independen dan

distribusi term dalam seluruh dokumen juga independen •  I2 = distribusi term dalam dokumen relevan adalah independen dan distribusi term dalam dokumen non-relevan juga independen.

•  Definisi dua metode untuk presentasi hasil: •  O1 = kemungkinan relevan didasarkan hanya pada kemunculan term yang dicari dalam dokumen •  O2 = kemungkinan relevan didasarkan baik pada kemunculan atau ketidakmunculan term yang dicari dalam dokumen


10

Simple Term Weights •  Empat bobot diturunkan dari kombinasi prinsip rankings

dan asumsi independensi

5

4/9/13


11

Simple Term Weights •  N = jumlah dokumen dalam koleksi •  R = jumlah dokumen relevan untuk query q •  n = jumlah dokumen yang mengandung term t •  r = jumlah dokumen relevan yang memiliki term t


12

Simple Term Weights I1 I2

O1 w1 w2

O2 w3 w4

•  W4 merupakan hasil terbaik •  W3 dan w4 adalah hasil lebih baik dari pada w1 dan w2.

6

4/9/13


13

Simple Term Weights •  Jika dalam suatu perhitungan bobot diketahui adanya

inifiniti, maka perhitungan keempat bobot dapat diubah menjadi:

! (r + 0.5) $ # (R +1) & & w1 = log # # (n +1) & #" (N + 2) &% ! (r + 0.5) $ # (R +1) & & w2 = log # # (n − r + 0.5) & #" (N − R +1) &%

" (r + 0.5) % $ (R − r + 0.5) ' ' w3 = log $ $ (n +1) ' $# (N − n +1) '& " % (r + 0.5) $ ' (R − r + 0.5) ' w4 = log $ (n − r + 0.5) $ ' $# (N − n − (R − r) + 0.5) '&


14

Contoh •  Q: “gold silver truck” •  D1 = “Shipment of gold damaged in a fire” •  D2 = “Delivery of silver arrived in a silver truck” •  D3 = “Shipment of gold arrived in a truck” •  Oleh karena dalam model probabilistik diperlukan

dokumen pelatihan, maka ketiga dokumen diasumsikan adalah dokumen pelatihan. •  D1 dan D2 adalah relevan terhadap query.

7

4/9/13


15

Simple Term Weights gold 3 2 2 1

N n R r

silver 3 1 2 1

truck 3 2 2 1


16

Simple Term Weights •  Hitunglah bobot tiap term dalam query untuk w1, w2, w3,

dan w4. •  Secara ringkas dapat ditunjukkan pada tabel berikut:

w1

w2

w3

w4

gold

-0.079

-0.176

-0.176

-0.477

silver

0.097

0.301

0.176

0.477

truck

0.143

0.523

0.523

1.176

8

4/9/13


17

Simple Term Weights •  Selanjutnya, hitung koefisien kemiripan dengan cara

menjumlahkan bobot term query yang dimiliki masingmasing dokumen. w1

w2

w3

w4

D1

-0.079

-0.176

-0.176

-0.477

D2

0.240

0.824

0.699

1.653

D3

0.064

0.347

0.347

0.699

•  Rangking dokumen: D2, D3, D1.


18

Latihan Simple Term Weight •  Terdapat 3 dokumen •  D1 = Manajemen Sistem Informasi •  D2 = Sistem Sumber Daya Manusia •  D3 = Manajemen Informasi Penggajian •  Q = informasi daya manusia •  Tampilkan urutan dokumen yang ditampilkan dengan

menggunakan strategi Simple Term Weight.

9

4/9/13


19

2. Extended Boolean •  Ide dasar adalah memberikan bobot term untuk setiap

term dalam query dan untuk tiap term dalam dokumen. •  Bobot-bobot term dikaitkan dengan perangkingan dokumen. •  Misal diberikan query (t1 OR t2) yang akan mengembalikan dokumen yang berisi t1 dengan bobot w1 dan t2 dengan bobot w2. •  Jika baik w1 dan w2 adalah 1, sebuah dokumen yang berisi kedua term tersebut diberikan kemungkinan ranking paling tinggi. •  Dengan menggunakan Eucledian distance, dari titik (w1, w2) dari titik asal, kita dapat mendapatkan koefisien kemiripan.


20

Extended Boolean – 2 dimensi •  Untuk sebuah

dokumen berisi term t1 dan t2 dengan bobot w1 dan w2, maka koefisien kemiripan dapat dihitung sebagai: sc(Q, di ) = (w1 )2 + (w2 )2 •  Nilai SC tertinggi

adalah 1.414

10

4/9/13


21

Extended Boolean – 2 dimensi •  Jika t1 ∨ t2 dinormalisasikan:

sc(Qt1∨t2 , di ) =

(w1 )2 + (w2 )2 2

•  Jika t1 ∧ t2 dinormalisasikan :

sc(Qt1∧t2 , di ) = 1−

(1− w1 )2 + (1− w2 )2 2


22

Extended Boolean – p-Norm •  Untuk sembarang term, m, kita mendapatkan ekspresi

yang tergantung pada parameter-p.

11

4/9/13


23

Extended Boolean – normalisasi TF-IDF •  Oleh karena nilai bobot term harus bernilai [0, 1], maka

nilai bobot TF-IDF tiap term dalam dokumen harus dinormalisasikan.

•  Dimana: •  tfmax i,j = maksimum frekuensi term I dalam dokumen j •  idfmax g = maksimum idf dari sebuah term dalam koleksi c


24

Latihan #2 •  D1 = “Shipment of gold damaged in a fire” •  D2 = “Delivery of silver arrived in a silver truck” •  D3 = “Shipment of gold arrived in a truck” •  Q1: “gold OR silver OR truck” •  Q2: “gold AND silver AND truck” •  Q3: “gold OR silver AND truck”

12

4/9/13


25

3. Query Likelihood Language Model •  Statistical language model adalah sebuah mekanisme

probabilistik untuk menghasilkan sebuah deretan teks. •  Language model untuk IR dimulai tahun 1998 oleh Ponte dan Croft. •  Idenya adalah dokumen dapat dirangking terhadap kemungkinan (likelihood) dari generating query. •  Koefisien kemiripan Q dan Di adalah:

SC(Q, Di ) = P(Q | M Di ) •  Dimana MDi adalah language model dalam dokumen Di.


26

Language Model •  Generating sebuah query memerlukan sebuah model

probabilistik untuk query. •  Ponte dan Croft menghitung probabilitas query sebagai product probabilitas baik terhadap adanya term dalam query atau tidak.

SC(Q, Di ) = ∏ P(t j | M Di )∏ (1− P(t j | M Di )) t j ∈Q

t∉Q

13

4/9/13


27

Language Model •  Model p(tj|MDi) dapat diperkirakan dengan model:

p(t j | M D j ) = pml (t j | M Di ) •  Dimana pml (t j | M D ) adalah perkiraan maximum likelihood i

dari distribusi term, yang diberikan dengan:

pml (t j | M Di ) =

tf (t j , Di ) dlDi

•  Dimana dlDi adalah panjang dokumen Di.


28

Language Model Koleksi Dokumen

D1

MD1

P(Q |M

D1 )

D2

D3

P(Q|MD2)

Query (Q)

MD2

MD3

P

|M D (Q

)

3

Model Dokumen

14

4/9/13


29

Contoh Perkiraan Maximum Likelihood •  D1 = “Shipment of gold damaged in a fire” •  D2 = “Delivery of silver arrived in a silver truck” •  D3 = “Shipment of gold arrived in a truck” •  Q1: “gold silver truck”

Pml (silver | M Di ) =

tf (silver, Di ) =0 dlDi


30

Smoothing untuk ML •  Untuk menghindari masalah karena term query tidak ada

dalam dokumen, perlu diterapkan smoothing.

# (1−R(t,d )) R(t,d ) p (t, d) × p (t) ml avg % p(t | M Di ) = $ cft % cs &

Jika tf(t,d)>0

Selain itu

•  dimana

pavg (t) =

∑

d (t∈d )

pml (t | M D ) dft

! 1.0 $ ! ft R(t,d ) = # &×# 1.0 + f " t % " 1.0 +

tft,d

$ & ft %

ft = pavg (t) × dld

15

4/9/13

31


Contoh •  cs = 22 token •  Total jumlah token dalam tiap dokumen (dld) •  D1 = 7, D2 = 8, D3 = 7 •  Jumlah dokumen dari tiap term t, dft, adalah a

dft

3

arrived

2

damaged

1

delivery

1

fire

gold

in

of

shipment

silver

truck

1

2

3

3

2

1

2

•  Jumlah kemunculan token dalam koleksi, cft : a

cft

3

arrived

2

damaged

1

delivery

1

fire

gold

in

of

shipment

silver

truck

1

2

3

3

2

2

2

32


Contoh •  Jumlah kemunculan tiap term di tiap dokumen, tft,d : a

arrived

damaged

delivery

fire

gold

in

of

shipment

silver

truck

D1

1

0

1

0

1

1

1

1

1

0

0

D2

1

1

0

1

0

0

1

1

0

2

1

D3

1

1

0

0

0

1

1

1

1

0

1

16

4/9/13


33

Contoh •  Pertama, kita hitung perkiraan maximum likelihood dari

kemungkinan term t untuk dokumen d. Pml(t|Md)

D1

D2

D3

a

0.143

0.125

0.143

arrived

0

0.125

0.143

damaged

0.143

0

0

delivery

0

0.125

0

fire

0.143

0

0

gold

0.143

0

0.143

in

0.143

0.125

0.143

of

0.143

0.125

0.143

shipment

0.143

0

0.143

silver

0

0.250

0

truck

0

0.125

0.143


34

Contoh •  Kedua, kita hitung rata-rata kemungkinan term t dalam

dokumen yang berisi term tersebut. a

Pavg(t)

arrived

0.137 in

Pavg(t)

damaged

0.134 of

0.137

0.137

0.143 shipment

0.143

delivery

0.125 silver

0.250

fire

gold

0.143

0.143

truck

0.134

17

4/9/13


35

Contoh •  Ketiga, kita hitung resiko sebuah term t dalam sebuah

dokumen d. Sebelumnya kita hitung rata-rata kemunculan term dalam dokumen ( f ). a

ft

arrived

Damaged

delivery

fire

gold

D1

0.958

0.938

1

0.875

1

1

D2

1.096

1.071

1.143

1

1.143

1.143

D3

0.958

0.938

1

0.875

1

1

In

ft

Of

Shipment

Silver

truck

D1

0.958

0.958

1

1.750

0.938

D2

1.096

1.096

1.143

2

1.071

D3

0.958

0.958

1

1.750

0.938


36

Contoh •  Nilai resiko tiap term di tiap dokumen ( R(t,d) ) Rt,d

D1

D2

D3

a

0.250

0.249

0.250

arrived

0.516

0.250

0.250

damaged

0.250

0.467

0.500

delivery

0.533

0.250

0.533

fire

0.250

0.467

0.500

gold

0.250

0.467

0.250

in

0.250

0.249

0.250

of

0.250

0.249

0.250

shipment

0.250

0.467

0.250

silver

0.364

0.148

0.364

truck

0.516

0.249

0.250

18

4/9/13


37

Contoh •  Keempat, kita hitung probabilitas bentuk query untuk

sebuah model dokumen. p(t|Md)

D1

D2

D3

A

0.141

0.128

0.141

arrived

0.091

0.127

0.141

damaged

0.143

0.045

0.045

delivery

0.045

0.125

0.045

fire

0.143

0.045

0.045

gold

0.143

0.091

0.143

in

0.141

0.128

0.141

of

0.141

0.128

0.141

shipment

0.143

0.091

0.143

silver

0.091

0.250

0.091

truck

0.091

0.127

0.141


38

Contoh •  Kelima, kita hitung kemiripan Query dengan model

dokumen.

P(Q|Md)

D1

D2

D3

0.000409

0.001211

0.000743

19

4/9/13


39

Latihan Query Likelihood •  Terdapat 3 dokumen •  D1 = Manajemen Sistem Informasi •  D2 = Sistem Sumber Daya Manusia •  D3 = Manajemen Informasi Penggajian •  Q = informasi daya manusia •  Tampilkan urutan dokumen yang ditampilkan dengan

menggunakan strategi Query Likelihood.


40

TERIMA KASIH Budi Susanto

20

13. Budi Susanto

Recommend Documents