Temu-Kembali Informasi2017

02: Temu-Kembali Boolean

Husni

Husni@Trunojoyo.ac.id

Modifikasi dari slide kuliah Stanford CS276

Temu-Kembali InformasiInformation Retrieval

• Information Retrieval (IR) adalah menemukan materi (biasanya dokumen) dari suatu yang sifatnya tak-terstruktur (biasanya teks) yang memenuhi kebutuhan informasi dari dalam koleksi besar (yang biasanya disimpan pada beberapa komputer).

2

Data Tak-Terstruktur (Teks) vs. Terstruktur (Database) pada 1996

3

Data Tak-Terstruktur (Teks) vs. Terstruktur (Database) pada 2009

4

Data Tak-Terstruktur pada 1620

• Sandiwara Shakespeare mana yang mengandung kata Brutus ANDCaesar tetapi NOT Calpurnia?

• Kita dapat mengambil semua sandiwara Shakespeare yang mengandung Brutus dan Caesar, kemudian mengeluarkan yang mengandung Calpurnia?

• Mengapa itu bukan jawabannya?• Lambat pemrosesannya (untuk corpora besar)

• NOT Calpurnia itu tidak sepele (non-trivial)

• Operasi lain (misal, carilah kata Romans dekat countrymen) tidak mudah dikerjakan

• Temu-kembali teranking (dokumen-dokumen terbaik yang dikembalikan)• Kuliah-kuliah berikutnya

5

Sec. 1.1

Pengaruh Term-DocumentHubungan Kata dan Dokumen

Antony and Cleopatra Julius Caesar The Tempest Hamlet Othello Macbeth

Antony 1 1 0 0 0 1

Brutus 1 1 0 1 0 0

Caesar 1 1 0 1 1 1

Calpurnia 0 1 0 0 0 0

Cleopatra 1 0 0 0 0 0

mercy 1 0 1 1 1 1

worser 1 0 1 1 1 0

1 jika sandiwara mengandung kata, 0 jika tidak

Brutus AND Caesar BUTNOT Calpurnia

Sec. 1.1

Vektor Pengaruh (Hubungan)

• Sehingga diperoleh suatu vektor 0/1 untuk setiap term.

• Untuk menjawab query: ambil vektor Brutus, Caesar dan Calpurnia(di-komplemen-kan) bitwise AND.

• 110100 AND 110111 AND 101111 = 100100.

7

Sec. 1.1

Jawaban untuk Query

•Antony and Cleopatra, Act III, Scene iiAgrippa [Aside to DOMITIUS ENOBARBUS]: Why, Enobarbus,

When Antony found Julius Caesar dead,

He cried almost to roaring; and he wept

When at Philippi he found Brutus slain.

•Hamlet, Act III, Scene iiLord Polonius: I did enact Julius Caesar I was killed i' the

Capitol; Brutus killed me.

8

Sec. 1.1

Asumsi Dasar dalam Temu-Kembali Informasi

• Koleksi (corpus): Himpunan tetap dokumen

• Sasaran (goal): Menemukan-kembali (memperoleh) dokumen-dokumen yang mengandung informasi yang relevan dengan kebutuhan informasi pengguna dan membantu pengguna tersebut menyelesaikan suatu tugas

9

Sec. 1.1

Model Pencarian Klasik

Corpus

Task

Info Need

Query

Verbal

form

Results

Search

Engine

Query

Refinement

Singkirkan tikus dengan cara yang benar secara politis

Info tentang cara menghapus tikus tanpa membunuhnya

Bagaimana cara memerangkap tikus hidup?

perangkap tikus

Misconception?

Mistranslation?

Misformulation?

Seberapa Baik Dokumen yang Diperoleh?

• Ketepatan (Presisi, Precision): Bagian (persentase) dari dokumen-dokumen yang diperoleh yang relevan dengan kebutuhan informasi pengguna

• Penarikan-Kembali (Recall): Persentase dari dokumen-dokumen yang relevan dari dalam koleksi yang diperoleh (diterima pengguna)

• Definisi dan ukuran yang lebih tepat akan dijelaskan pada kuliah-kuliah berikutnya...

11

Sec. 1.1

Koleksi Lebih Besar

• Anggap N = 1 juta dokumen, masing-masing mengandung 1000 kata.

• Rerata 6 byte per kata termasuk spasi dan tanda baca• 6GB data di dalam dokumen-dokumen tersebut.

• Katakanlah di sana ada M = 500K term-term berbeda di antaranya.

12

Sec. 1.1

Dapatkan Dibuatkan Matriksnya

• Matriks 500K x 1M yang mempunyai setengah triliun 0 dan 1.

• Tetapi mempunyai tidak lebih dari satu milyar 1.• Matriksnya sangat jarang (sparse, lihat nilai 1).

• Seperti apa representasi yang lebih baik?• Kita hanya merekam yang posisi 1.

13

Mengapa?

Sec. 1.1

Inverted IndexIndeks Terbalik

• Untuk setiap term t, kita harus menyimpan daftar (list) semua dokumen yang mengandung term t tersebut.• Setiap dokumen diidentifikasi dengan docID, suatu nomor seri dokumen

• Dapatkah digunakan larik berukuran tetap (fixed-size array)?

14

Brutus

Calpurnia

Caesar 1 2 4 5 6 16 57 132

1 2 4 11 31 45 173

2 31

Apa yang terjadi jika kata Caesarditambahkan ke dokumen 14?

Sec. 1.2

174

54 101

Inverted index

• Diperlukan daftar posting berukuran tak-tetap (variable-size postings list)• Pada disk, a continuous run of postings is normal and best

• Dalam memory, dapat menggunakan linked list atau array yang panjangnya tak-tetap• Ada tarik-ulur dalam ukuran/kemudahan penyisipan

15

Dictionary(Kamus)

Postings

Diurutkan berdasarkan docID (mengapa?).

Posting

Sec. 1.2

Brutus

Calpurnia

Caesar 1 2 4 5 6 16 57 132

1 2 4 11 31 45 173

2 31

174

54 101

Tokenizer

Token stream. Friends Romans Countrymen

Konstruksi Inverted Index

Modul-modul Linguistik

Token termodifikasi. friend roman countryman

Indexer

Inverted index.

friend

roman

countryman

2 4

2

13 16

1

Lebih lanjut nanti...

Dokumen yang diindeks. Friends, Romans, countrymen.

Sec. 1.2

Tahapan Indexer: Rentetan Token

• Rentetan dari pasangan (Token Termodifikasi, Document ID).

I did enact Julius

Caesar I was killed

i' the Capitol;

Brutus killed me.

Doc 1

So let it be with

Caesar. The noble

Brutus hath told you

Caesar was ambitious

Doc 2

Sec. 1.2

Tahapan Indexer: Urutkan

• Urutkan berdasarkan term-term...dan kemudian berdasarkan docID

Langkah Indexing Inti

Sec. 1.2

Tahapan Indexer: Dictionary & Postings

• Beberapa entri term dalam satu dokumen digabungkan

• Bagi ke dalam dictionarydan postings

• Informasi frekuensi dokumen ditambahkan.

Mengapa frekuensi?Lihat diskusi selanjutnya!

Sec. 1.2

Biaya Penyimpanan?

20Pointer

Term dan jumlah

kemunculannya Nanti dalam kuliah berikutnya:

▪ Bagaimana mengindeks secara efisien?

▪ Berapa banyak storage (disk) yang diperlukan?

Sec. 1.2

Daftar dari docID

Indeks Telah Terwujud!

• Bagaimana kita memroses suatu query?• Kemudian: Jenis query apa yang dapat diproses?

21

Fokus

hari ini

Sec. 1.3

Pemrosesan Query: AND

• Seandainya query yang akan diproses adalahBrutus AND Caesar

• Temukan Brutus di dalam dictionary;

• Dapatkan (retrieve) posting-postingnya.

• Temukan Caesar di dalam dictionary;

• Retrieve posting-postingnya.

• “Merge” (gabungkan) dua posting tersebut:

22

128

34

2 4 8 16 32 64

1 2 3 5 8 13 21

Brutus

Caesar

Sec. 1.3

Gabungannya

• Kunjungi dua posting itu secara bersamaan, waktunya sebanding dengan jumlah total dari entri posting-posting

23

34

1282 4 8 16 32 64

1 2 3 5 8 13 21

128

34

2 4 8 16 32 64

1 2 3 5 8 13 21

Brutus

Caesar2 8

Jika panjang daftar adalah x dan y, maka gabungannya memerlukan operasi O(x+y).Penting sekali: posting telah diurutkan berdasarkan docID.

Sec. 1.3

Irisan Dua Daftar Posting(Algoritma “merge”)

24

Query Boolean: Cocok Pasti Tepat

• Model Temu-Kembali Boolean: agar mampu menangani query berbentuk ekspresi Boolean:• Query Boolean: menggunakan operator AND, OR dan NOT untuk

menggabungkan term-term query• Menampilkan setiap dokuen sebagai sehimpinan kata-kata

• Apakah tepat (presisi): dokumen sesuai kondisi atau tidak.

• Mungkin model paling simpel untuk membangun suatu sistem IR

• Perangkat retrieval komersil utama selama 3 dekade.

• Banyak sistem pencarian masih menggunakan model Boolean:• Pencarian di Gmail, katalog perpustakaan, Pencarian file di Windows Explorer,

Mac OS X Spotlight

25

Sec. 1.3

Contoh: WestLaw http://www.westlaw.com/

• Layanan pencarian legal komersial terbesar (anggota berbayar) (dimulai 1975; ranking ditambahkan pada 1992)

• Puluhan terabytes data; 700,000 pengguna

• Mayaritas pengguna masih menggunakan query boolean

• Contoh query:• Apa undang-undang pembatasan dalam kasus-kasus yang melibatkan

tindakan gugatan tort federal?

• LIMIT! /3 STATUTE ACTION /S FEDERAL /2 TORT /3 CLAIM• ! = wildcard, /3 = dalam 3 kata, /S = dalam kalimat yang sama

26

Sec. 1.4

Contoh: WestLaw http://www.westlaw.com/

• Contoh query lain:• Persyaratan bagi penyandang cacat untuk dapat mengakses tempat kerja

• disabl! /p access! /s work-site work-place (employment /3 place)

• Catatan: SPACE adalah disjunction, bukan conjunction!

• Pertanyaan yang panjang dan tepat; operator kedekatan; dikembangkan secara bertahap; tidak seperti pencarian web

• Banyak pencari professional masih menyukai pencarian Boolean• Dia tahu secara pasti apa yang diperolehnya

• Tetapi itu bukan berarti sesungguhnya ia bekerja lebih baik….

Sec. 1.4

Query Boolean: Gabungan Lebih Umum

• Latihan: Sesuaikan algoritma merge untuk query:

Brutus AND NOT Caesar

Brutus OR NOT Caesar

Dapatkah kita masih menjalankan merge itu dalam waktu O(x+y)?

Apa yang dapat kita capai?

28

Sec. 1.3

Penggabungan

Bagaimana dengan suatu formula Boolean berubah-ubah?

(Brutus OR Caesar) AND NOT (Antony OR Cleopatra)

• Dapatkah kita selalu me-merge-kan itu dalam waktu “linier”?• Linier dalam apa?

• Dapatkah dilakukan dengan cara lebih baik?

29

Sec. 1.3

Optimisasi Query

• Apakah urutan terbaik dalam pemrosesan query?

• Anggap suatu query yang meng-AND-kan n term.

• Untuk masing-masing dari n term, ambil postingnya, kemudian AND-kan bersama-sama.

Brutus

Caesar

Calpurnia

1 2 3 5 8 16 21 34

2 4 8 16 32 64 128

13 16

Query: Brutus AND Calpurnia AND Caesar

Sec. 1.3

Contoh Optimisasi Query

• Proses mengikuti naiknya frekuensi:• Mulai dengan himpunan terkecil, kemudian lanjutkan ke lebih besar.

31

Inilah mengapa frekuensi dokumen disimpan dalam kamus

Eksekusi query sebagai (Calpurnia AND Brutus) AND Caesar.

Sec. 1.3

Brutus

Caesar

Calpurnia

1 2 3 5 8 16 21 34

2 4 8 16 32 64128

13 16

Optimisasi Lebih Umum

• Misalnya (madding OR crowd) AND (ignoble OR strife)

• Dapatkan frekuensi dokumen untuk semua term.

• Estimasikan ukuran dari setiap OR dengan menjumlahkan frekuensi dokumennya (konservatif).

• Proses mengikuti kenaikan ukuran OR.

32

Sec. 1.3

Latihan

• Rekomendasikan suatu urutan pemrosesan query untuk

Term Frekuensi

eyes 213312

kaleidoscope 87009

marmalade 107913

skies 271658

tangerine 46653

trees 316812

33

(tangerine OR trees) AND

(marmalade OR skies) AND

(kaleidoscope OR eyes)

Latihan Pemrosean Query

• Latihan: Jika query-nya adalah friends AND romans AND (NOT countrymen), bagaimana kita dapat menggunakan frekuensi dari countrymen?

• Latihan: Perluas merge untuk query Boolean berubah-ubah (sembarang). Dapatkah kita selalu menjamin eksekusi dalam waktu linier dalam ukuran posting total?

• Hint: Mulai dengan kasus query boolean: setiap term query hadir hanya sekali dalam query tersebut.

34

Latihan• Coba fitur-fitur pencarian pada

http://www.rhymezone.com/shakespeare/

• Tuliskan lima fitur pencarian yang anda pikirkan dapat melakukan lebih baik.

35

Apa yang ada di Depan IR?Lebih dari Pencarian Term

• Bagaimana dengan frasa?• Universitas Trunojoyo Madura

• Kedekatan: Temukan Gates DEKAT Microsoft.• Perlu indeks untuk menangkap informasi posisi dalam dokumen.

• Zona dalam dokumen: Temukan dokumen dengan (author = Ullman)AND (teks tersebut mengandung automata).

36

Akumulasi Fakta

• 1 vs. 0 kemunculan dari suatu term pencarian• 2 vs. 1 kemunculan

• 3 vs. 2 kemunculan, dll.

• Biasanya lebih banyak terlihat lebih baik

• Diperlukan informasi frekuensi term di dalam dokumen.

37

Perankingan Hasil Pencarian

• Query boolean memberikan inklusi atau eksklusi dokumen.

• Sering kita ingin meranking/mengelompokkan hasil• Perlu mengukur kedekatan dari query ke setiap dokumen.

• Perlu memutuskan apakah dokumen yang disajikan kepada pengguna adalah singletons (tunggal), atau sekelompok dokumen yang mencakup berbagai aspek dari query.

38

IR vs. Databases:Data Terstruktur vs. Tak-Terstruktur

• Data terstruktur cenderung merujuk kepada informasi di dalam “table”

39

Karyawan Manajer Gaji

Smith Jones 50000

Chang Smith 60000

50000Ivy Smith

Khasnya memungkinkan query pencocokan eksakta dan range numeris (untuk teks), misal:

Salary < 60000 AND Manager = Smith.

Data Tak-Terstruktur

• Khasnya merujuk kepada teks bebas

• Memungkinkan• Query kata kunci (keyword) termasuk operator-operator

• Query “konsep” yang lebih canggih, misal:

• Temukan semua halaman web yang berkaitan erat dengan drug abuse

• Model klasik untuk pencarian dokumen teks.

40

Data Semi-Terstruktur

• Faktanya,hampir tidak ada data yang “Tak-Terstruktur”

• Misalnya, slide ini mempunyai zona-zona yang dikenali secara berbeda seperti Title dan Bullets

• Memudahkan pencarian “semi-terstruktur” seperti• Title mengandung data AND Bullets mengandung pencarian

... untuk tidak mengatakan apapun tentang struktur linguistik

41

Pencarian Semi-Terstruktur Lebih Canggih

• Title tentang Object Oriented Programming AND Author sesuatu seperti stro*rup

• Dimana * adalah operator wild-card

• Persoalan:• Bagaimana kita memroses “tentang”?

• Bagaimana kita merangking hasil?

• Merupakan fokus dari pencarian XML (lihat buku IIR bab 10)

42

Clustering, Classification dan Ranking

• Clustering (Klasterisasi): • Diberikan sehimpunan dokumen, kelompokkan dokumen-dokumen tersebut

ke dalam klaster-klaster berdasarkan pada isinya.

• Classification (Klasifikasi): • Diberikan sehimpunan topik, ditambahkan suatu dokumen baru D, putuskan

topik mana yang akan ditempati oleh D.

• Ranking (Pemeringkatan): • Dapat kita pelajari bagaimana urutan terbaik dari sehimpunan dokumen,

misalnya sehimpunan hasil pencarian.

43

Web dan Tantangannya

• Dokumen-dokumen beragam dan tak-biasa

• Query dan kebutuhan informasi pengguna beragam dan tak-biasa

• Lebih dari term-term, mengeksploitasi gagasan dari jejaring sosial• Analisa link (tautan), clickstreams ...

• Bagaimana search engines bekerja? Dan bagaimana kita dapat membuatnya lebih baik?

44

Temu-Kembali Informasi Lebih Canggih

• Temu-Kembali Informasi lintas Bahasa

• Question answering

• Summarization

• Text mining

• …

45

Sumber Daya Kuliah Hari ini

• Introduction to Information Retrieval, Bab 1

• Shakespeare:• http://www.rhymezone.com/shakespeare/

• Coba jelajah murni dengan fitur deretan keyword!

• Managing Gigabytes, sub-bab 3.2

• Modern Information Retrieval, sub-bab 8.2

Ada Pertanyaan?

46