pengantar temu-balik informasi

Pengantar Temu-Balik Informasi Pertemuan ke-2

Sistem Temu-BalikInformasi

2

•••••••

Information Retrieval (IR)Sistem IRIstilah dalam IRIR Berbasis TeksArsitektur Sistem IRSejarah IRArea Terkait

...akan dibahasPengantar Temu-Balik Informasi

3

• Karakterisasi kebutuhan informasi tidaklah mudah.Harus ditranslasi ke dalam suatu query terlebihdahulu.

Definisi IR

• Pencarian materi (biasanya dokumen) dari sesuatuyang sifatnya tak-terstruktur (unstructured, biasanyateks) untuk memenuhi kebutuhan informasi daridalam koleksi besar (biasanya disimpan dalamkomputer).

• Representasi, penyimpanan, organisasi, pencariandan akses ke item informasi untuk memenuhikebutuhan informasi pengguna.

• Penekanan pada proses retrieval informasi (bukandata).

Pengantar Temu-Balik Informasi

Motivasi

• Data retrieval– Dokumen mana yang mengandung himpunan

keyword?– Semantik didefinisikan dengan baik– Error dari suatu obyek mengakibatkan kegagalan!

• Information retrieval– Informasi mengenai suatu subyek atau topik– Semantik dapat bersifat lepas (longgar)– Error kecil ditoleransi

4


...Motivasi

• IR di tengah pertunjukan– IR dalam 20 tahun terakhir:

• Klasifikasi dan kategorisasi• Sistem dan bahasa• Antarmuka pengguna dan visualisasi

– Masih, area dilihat sebagai bidang yang sempit– Web mengubah persepsi ini

• Repository pengetahuan universal• Akses universal gratis (biaya rendah)• Volume raksasa dari informasi tanpa editorial board

terpusat• Meskipun banyak masalah: IR merupakan kunci untuk

menemukan solusi!

5


Sistem IR

• Menerima query pengguna yang mewakilikebutuhan informasi

• Mencari dan menginterpretasikan content(isi) dari item-item informasi

• Membangkitkan suatu ranking yangmencerminkan relevansi terhadapkebutuhan informasi tersebut

• Ide mengenai relevansi adalah sangatpenting

6


8

Kebutuhan IR

• WWW: lebih 25 milyar halaman web, 1.3 milyargambar dan lebih 1 milyar pesan Usenet yangdiindeks pada Google (2006)

• Berbagai kebutuhan informasi:–––––

Mencari dokumen yang masuk dalam topik tertentuMencari suatu informasi spesifikMencari jawaban dari suatu pertanyaanMencari informasi dalam bahasa berbeda...


Penjualan Software Text Retrieval

9


Information Retrieval (IR)

• Secara teknis: indexing (pembuatanindex) dan retrieval (pencarianketerangan) dokumen textual.

• Pencarian halaman pada WWW adalahaplikasi paling “ngetop” saat ini

• Fokus pertama: meretrieve dokumen-dokumen yang relevan dengan query.

• Fokus kedua: meretrieve himpunan besardokumen secara efisien.

10

Pengantar Temu-Balik Informasi Sistem Temu-Balik Komputer 2010 2010Keamanan Informasi

Information vs Data Retrieval

• Sistem data retrieval (seperti database) berurusan denganstructured data yang mempunyai semantik terdefinisidengan baik dan kebutuhan meretrieve hasil yang pasti(exact)

• Sistem IR berurusan dengan dokumen bahasa alami(natural language) dan error kecil dapat diabaikan.

• Sistem IR harus menginterpretasikan content kemudianmeranking daftar content sesuai dengan tingkatrelevansinya.

• Tujuan: Meretrieve semua dokumen yang relevansekaligus meretrieve sesedikit mungkin dokumenyang tidak relevan

11


Tugas IR Dasar

• Diberikan:– Suatu corpus dokumen bahasa alami

tekstual.– Suatu query pengguna dalam bentuk string

tekstual.

• Temukan:– Suatu himpunan dokumen terurut menurun

(ranking) yang relevan dengan querytersebut.

12


Sistem IR

13


Contoh Sistem IR• Conventional (katalog perpustakaan)

Pencarian dengan kata kunci, judul, penulis, dll.• Text-based (Google, Yahoo, ASK).

Pencarian dengan kata kunci (keyword). Pencarianterbatas menggunakan query dalam bahasa alami.

• Multimedia (QBIC, WebSeek, SaFe)Pencarian dengan penampilan visual (bentuk, warna,…)

• Sistem jawaban pertanyaan (AskJeeves, Answerbus)Pencarian dalam bahasa alami (terbatas)

• Lainnya:IR lintas-bahasa, music retrieval

14


Sistem IR di Web• Pencarian halaman web http://www.google.com• Pencarian gambar http://images.google.com• Pencarian isi (content) gambar

http://wang.ist.psu.edu/IMAGE/• Pencarian jawaban pertanyaan

http://www.askjeeves.com• Pencarian musik? Hari-hati, jangan melanggar

hukum.

15


Relevansi

• Relevansi merupakan suatu judgment(keputusan) subyektif dan dapat didasarkanpada:

––––

topik yang tepat.waktu (informasi terbaru).otoritatif (dari suatu sumber terpercaya).kebutuhan informasi dari pengguna.

• Kriteria relevansi utama: suatu sistem IRsebaiknya (harus) memenuhi kebutuhaninformasi pengguna.

16


Pencarian Keyword

• Ide paling sederhana dari relevansi:apakah string query ada di dalamdokumen (kata demi kata, verbatim)?

• Ide yang lebih fleksibel: Berapa seringkata-kata di dalam query muncul di dalamdokumen, tanpa melihat urutannya (bagof words)?

17


Masalah dengan Keyword

• Mungkin tidak meretrieve dokumen relevan yangmenyertakan synonymous terms.– “restaurant” vs. “café”– “NDHU” vs. “National Dong Hwa University”

• Mungkin meretrieve dokumen tak-relevan yangmenyertakan ambiguous terms.– “bat” (baseball vs. mamalia)– “Apple” (perusahaan vs. buah-buahan)– “bit” (unit data vs. perilaku menggigit)

18


Bukan Sekedar Keyword

• Kita akan mendiskusikan dasar-dasar IRberbasis keyword, tetapi…– Fokus pada perluasan dan pengembangan

terakhir untuk mendapatkan hasil terbaik.• Kita akan membahas dasar-dasar

pembangunan sistem IR yang efisien,tetapi…– Fokus pada algoritma dan kemampuan dasar,

bukan masalah sistem yang memungkinkanpengembangan ke database ukuran industri.

19


IR Cerdas

• Memanfaatkan pengertian atau makna dari katayang digunakan.

• Melibatkan urutan kata di dalam query.• Beradaptasi dengan pengguna berdasarkan

pada feedback, langsung atau tidak langsung.• Memperluas pencarian dengan term terkait.• Mengerjakan pemeriksaan ejaaan/perbaikantanda pengenal otomatis.

• Memanfaatkan Otoritas dari sumber informasi.

20


Indeks• Sistem IR jarang mencari koleksi dokumen

secara langsung. Berdasarkan pada koleksidokumen, dibangun sebuah index. Penggunamencari index tersebut.

21


Indexing Otomatis

• Tujuan dari automatic indexing adalahmembangun index dan meretrieve informasitanpa intervensi manusia.

• Ketika informasi yang dicari adalah teks,metode automatic indexing akan sangat efektif.

• Penelitian automatic indexing fundamentaldimulai oleh Gerald Salton, Professor ofComputer Science di Cornell & mahasiswaPasca-Sarjananya (Sistem SMART).

22


IR dari Koleksi Besar

• Information retrieval dari koleksi sangat besarbersandar pada:– Jumlah computer power yang besar untuk

mengerjakan algoritma sederhana terhadap jumlahdata yang sangat banyak.komputasi kinerja-tinggi

– Pemahaman pengguna terhadap informasi dankemampuan dari sistem.Interaksi manusia - komputer

• Machine-learning banyak digunakan untukmendapatkan kinerja terbaik.

23


Searching & Browsing

• Orang dalam perulangan

24


IR dari Koleksi Dokumen Teks

• Kategori utama dari metode:– Ranking kemiripan terhadap query (vector spacemodel).

– Pencocokan exact (Boolean).– Ranking berdasarkan tingkat kepentingan dokumen

(PageRank)– Kombinasi beberapa metode

• Contoh: Web search engine, seperti Google &Yahoo, menggunakan metode kombinasi,berdasarkan pada pendekatan pertama danketiga, dengan kombinasi exact dipilihmenggunakan machine learning.

25


Istilah Penting

• Information retrieval: sub-bidang ilmukomputer yang berurusan dengan penemuankembali dokumen (khususnya teks) terotomasiberdasarkan pada content dan contextnya.

• Searching: Pencarian informasi spesifik didalam badan informasi. Hasilnya adalahsehimpunan hit.

• Browsing: Eksplorasi tak-terstruktur dari badaninformasi.

• Linking: Berpindah dari satu item ke item lainmengikuti link (sambungan) seperti rujukan(referensi).

26


...Istilah

• Query: Suatu string teks, menggambarkaninformasi yang sedang dicari pengguna. Setiapkata dari query dinamakan search term.

• Query dapat berupa search term tunggal, string dariterm, frase atau ekspresi tertentu menggunakansimbol khusus, misalnya regular expression.

• Pencarian Full text: Metode yang membandingkanquery dengan setiap kata di dalam teks, tanpamembedakan fungsi dari berbagai kata.

• Pencarian Bidang : Metode pencarian pada bidangstruktural atau bibliografis spesifik, seperti penulisatau judul.

27


28

...Istilah• Corpus: Koleksi dokumen yang diindeks dan

dijadikan target pencarian.• Daftar kata: Himpunan semua term yang digunakan

dalam indeks untuk suatu corpus (dikenal sebagaivocabulary file).

• Pada pencarian full text, word list adalah semuaterm di dalam corpus, stop words dihapus. Term-term terkait dikombinasi dengan stemming.

• Controlled vocabulary: Metode indexing dimanaword list bersifat tetap. Term-term dari vocabularytersebut dipilih untuk mendeskripsikan setiapdokumen.

• Keyword: Nama untuk term-term dalam word list,terutama dengan controlled vocabulary.


Mengurutan & Ranking Hit

• Ketika pengguna men-submit suatu query kesistem IR, sistem mengembalikan sehimpunan hit.Pada koleksi dokumen besar, himpunan hit akansangat besar.

• Nilai untuk pengguna sering tergantung padaurutan hit ditampilkan.

• Tiga metode utama:– Mengurutkan hit, misal berdasarkan tanggal– Meranking hit berdasarkan kemiripan antara query

dan dokumen– Meranking hit berdasarkan kepentingan dari dokumen

29


IR Berbasis Teks

• Sebagian besar metode ranking didasarkan pada modelruang vektor (vector space model).

• Sebagian besar metode pencocokan (matching)didasarkan ada operator Boolean.

• Metode Web search mengkombinasikan model ruangvektor dengan ranking berdasarkan pada tingkatkepentingan dokumen.

• Banyak sistem (dalam praktek) menggabungkan fitur-fitur dari beberapa pendekatan.

• Pada bentuk dasar, semua pendekatan menganggapkata sebagai token terpisah, dengan usaha minimaluntuk memahami kata-kata secara linguistik.

30


Frekuensi Kata

• Observasi: Beberapa kata lebih umumdaripada yang lain.

• Statistika: Koleksi sangat besar daridokumen teks tak-terstruktur mempunyaikarakteristik statistik serupa. Statistik ini:– Mempengaruhi efektifitas dan efisiensi dari

struktur data yang digunakan untukmengindeks dokumen

– Banyak model retrieval memanfaatkannya.31


...Frekuensi Kata

• Contoh: Contoh berikut ini diambil dari :– Jamie Callan, Characteristics of Text, 1997– 19 Juta kata sampel– Slide berikut memperlihatkan 50 kata yang

paling umum, diranking (r) berdasarkanfrekuensinya (f).

32


...Frekuensi Kata

33


Distribusi Ranking Frekuensi• Untuk semua kata di dalam suatu dokumen,

untuk setiap kata w– f adalah frekuensi munculnya w– r ranking dari w disusun menurut frekuensi. (kata

yang paling umum muncul mempunyai rank =1)

34


Contoh Frekuensi Rank

• Slide berikut memperlihatkan kata-kata didalam data Callan yang telah dinormali-sasi. Dalam contoh ini:– r adalah ranking dari kata w dalam sampel.– f adalah frekuensi kata w di dalam sampel.– n adalah jumlah total kemunculan kata di

dalam sampel.

35


...Contoh Ranking Frekuensi

36


Hukum Zipf

• Jika kata-kata di dalam suatu koleksidiranking, r, berdasarkan frekuensinya, f,maka memenuhi relasi:r × (f/n) = cdimana n adalah jumlah kemunculan katadi dalam koleksi, 19 juta dalam contoh.

• Koleksi berbeda mempunyai konstanta cberbeda.

• Dalam teks bahasa Inggris, c sekitar 0.1.37


Metode pada Hukum Zipf

• Stop lists: Abaikan kata-kata yang sangatsering (upper cut-off). Digunakan oleh hampirsemua sistem.

• Significant words: Abaikan kata yang palingsering dan paling sedikit (upper and lower cut-off). Jarang digunakan.

• Term weighting: Berikan bobot berbeda untukterm-term berdasarkan pada frekuensinya, kata-kata yang paling sering dibobot kurang.Digunakan oleh hampir semua metodeperankingan.

38


Pandangan Logik Dokumen

• Representasi dokumen dipandangsebagai suatu continuum (rangkaiankesatuan).

39


Arsitektur Sistem IR

40


Arsitektur IR: Contoh

41


Komponen Sistem IR• Operasi Teks membentuk kata-kata indeks

(token)– Tokenization (pemisahan kata)– Penghapusan Stopword (seperti ‘the’, ‘of’, …)– Stemming (mengubah kata-kata berbeda ke bentuk

akarnya)• Indexing membangun suatu inverted index dari

kata ke penunjuk dokumen.– Pemetaan dari kata kunci ke Id dokumen.

42


...Komponen Sistem IR

• Searching meretrieve dokumen-dokumen yangmengandung token query yang diberikan dariinverted index.

• Ranking memberikan score kepada semuadokumen yang diretrieve sesuai denganrelevance metric.

• User Interface menangani interaksi denganpengguna:– Input query dan output dokumen.– Feedback relevansi– Visualisasi hasil.

43


...Komponen Sistem IR

• Operasi Query mentransformasi query untukmeningkatkan retrieval:– Query expansion menggunakan thesaurus.– Query transformation menggunakan feedbackrelevansi.

– Optimisasi query untuk meningkatkan kinerja. (kurangpenting daripada dalam sistem data retrieval)

• Pertanyaan: bagaimana menambahkan suatukomponen personalisasi ke sistem IR?

44


Pencarian Web

• Aplikasi IR terhadap dokumen pada WWW• Perbedaan:

– Ukuran – lebih dari 25 milyar dokumen diindeks padaGoogle, terus bertambah

– Perubahan dokumen tidak dapat dikendalikan.– Harus menghimpun corpus dokumen dengan

menjaring (spidering) web.– Dapat mengeksploitasi informasi layout struktural

dalam HTML (XML).– Dapat mengeksploitasi struktur link dari web.

45


Sistem Pencarian Web

46


47

Tugas lain terkait IR

•••••••••

Kategorisasi dokumen otomatisPenyaringan informasi (spam filtering)Perutean (routing) informasiClustering dokumen otomatisMerekomendasikan informasi atau produkEkstraksi informasiIntegrasi informasiJawaban pertanyaan...


TimelineSistemIR

48


Sejarah IR

• 1960-70-an:– Eksplorasi awal dari sistem text retrieval untukcorpora abstrak ilmiah “kecil”, dan dokumenhukum dan bisnis.

– Pengembangan model retrieval dasarBoolean dan ruang vektor.

– Prof. Salton dan mahasiswanya di CornellUniversity mengawali penelitian di bidang ini.

49


...Sejarah IR

• 1980-an:– Sistem database dokumen besar, banyak

dijalankan oleh perusahaan:• LexisNexis – arsip yang dapat dicari (searchable)

dari content surat kabar, majalah, dokumen legal(hukum) dan sumber tercetak lain.

• Dialog• MEDLINE

50


...Sejarah IR

• 1990-an:– Pencarian dokumen FTPable di Internet

• Archie• WAIS (Wide Area Information System)

– Pencarian World Wide Web• Lycos• Yahoo• Altavista

51


...Sejarah IR

• 1990-an (lanjutan):– Kompetisi Terorganisir

• NIST(National Institute of Standards andTechnology) TREC(Text REtrieval Conference)dimulai tahun 1992

– Sistem rekomendasi• Ringo (musik)• Amazon (buku)• NetPerceptions (collaborative filtering)

– Katagorisasi dan clustering teks otomatis

52


Sejarah IR Terakhir

• 2000-an– Analisis link untuk pencarian web

• Google– Ekstraksi informasi otomatis

• Whizbang• Fetch• Burning Glass

– Jawaban pertanyaan• TREC Q/A track

53


...Sejarah IR Terkini

• 2000-an (lanjutan):– IR Multimedia

• Image• Audio dan musik• Video

– IR lintas-bahasa• DARPA TIDES(Translingual Information Detection,

Extraction and Summarization)

– Perangkuman dokumen

54


55

Area Terkait

•••••

Manajemen Basis DataIlmu Perpustakaan dan InformasiKecerdasan BuatanPemrosesan bahasa alamaiPembelajaran Mesin


Manajemen Basis Data

• Fokus pada data terstruktur yang disimpandalam tabel-tabel relasional, bukan teksbentuk bebas.

• Fokus pada pemrosesan yang efisien dariquery yang terdefinisi baik dalam suatubahasa formal (SQL).

• Semantik lebih jelas bagi data dan query.• Terkini: bergerak ke data semi-structured

(XML) membawa ini lebih dekat ke IR.56


Ilmu Perpustakaan & Informasi

• Fokus pada apsek pengguna manusia dariinformation retrieval (interaksi manusia-komputer, antarmuka pengguna, visualisasi).

• Berurusan dengan efektifitas katagorisasi daripengetahuan manusia.

• Terkait dengan analisis kutipan (citation) danbibliometrics (struktur informasi).

• Terkini: kerja pada pustaka digital membawabidang ini dengan ke Ilmu Komputer dan IR.

57


Kecerdasan Buatan

• Fokus pada representasi pengetahuan,penalaran (reasoning) dan tindakan cerdas.

• Formalisasi representasi pengetahuan danquery:– First-order Predicate Logic– Bayesian Networks– ...

• Terkini: Kerja pada web ontology & agentinformasi cerdas membawa AI dekat ke IR.

58


Pemrosesan Bahasa Alami

• Natural Language Processing (NLP)• Difokuskan pada analisis sintaktis, semantik,

dan pragmatis dari teks dan percakapan bahasaalami.

• Kemampuan untuk menganalisa sintaks(struktur fase) dan semantik memungkinkanretrieval berdasarkan pada pengertian (makna)daripada keyword.

• Semua sistem IR membutuhkan berbagaiderajat NLP.

59


NLP: Arah IR

• Metode untuk menentukan makna darikata yang ambigu berdasarkan padacontext (word sense disambiguation).

• Metode untuk mengidentifikasi potonganspesifik dari informasi dalam suatudokumen (information extraction).

• Metode untuk menjawab pertanyaan NLspesifik dari document corpora.

60


Pembelajaran Mesin (Machine Learning)

• Fokus pada pengembangan sistemkomputasional yang meningkatkan kinerjanyadengan pengalaman (pembelajaran).

• Klasifikasi contoh secara otomatis berdasarkanpada konsep pembelajaran dari contoh trainingyang diberi label (supervised learning).

• Metode otomatis untuk meng-cluster contoh-contoh tak-berlabel dalam kelompok yangsesuai arti (unsupervised learning).

61


Machine Learning: Arah IR• Text Categorization (pengelompokan teks)

– Klasifikasi hirarki otomatis (Yahoo).– Rekomendasi, penyaringan, routing adaptif.– Penyaringan spam terotomasi.

• Text Clustering– Clustering dari hasil query IR.– Formasi hirarki otomatis (Yahoo).

• Pembelajaran pada ekstraksi informasi• Text Mining• Web Mining

62


pengantar temu-balik informasi

Documents