Ilmu Perpustakaan & Informasi

diskusi dan ulasan ringkas

Posts Tagged ‘Markov Process’

Statistical Language Modeling

Posted by putubuku pada Mei 21, 2008

Sekali-sekali, kita berhitung yuk! 🙂 Salah satu kandidat hitung-hitungan itu adalah penggunaan statisik dalam temu kembali. Sebagaimana diuraikan oleh Liu dan Croft (2005), statistical language modeling atau biasa disebut language modeling (LM) termasuk pendatang baru dalam kerangka pemikiran yang menggunakan teori probabilitas (probabilistic framework). Sama halnya dengan model-model probabilistik, LM memang bermaksud menangkap ketidakteraturan statistis yang menjadi ciri dari ketidakteraturan penggunaan bahasa. (uraian ringkas tentang LM sudah ada di sini)

Sebagai aplikasi statistik, LM memang merupakan penerapan dari teori-teori Markov yang antara lain juga sudah dipakai oleh Zipf dalam bibliometrika dan Shannon yang berupaya menerapkan teori informasi dalam penggunaan bahasa manusia. Kini LM dipakai untuk pengenal bahasa lisan (automatic speech recognition). Sejak 1980, LM menjadi komponen penting dalam penerjemahan otomatis (machine traslation) dan pelacakan kesalahan eja (error spelling). Bahkan kemudian juga dipakai untuk mengembangkan perangkat lunak pengolah bahasa alamiah (natural language processing task), dan pembuatan ringkasan teks otomatis (summarization). Di penghujung era1990an teori dan aplikasi LM diperkenalkan ke bidang information retrieval  (IR) dan kini menjadi salah satu cabang penting penelitian di bidang ini.

Dalam bentuk rumus matematika, LM mengasumsikan S sebagai kata-kata (words) yang beruntaian: 

Untuk sejumlah k kata-kata, maka S mencerminkan Markov process dengan hitungan probabilitas:

Ketika n = 2, kita mengatakannya sebagai biagram language model, yang kemudian dapat diestimasi menggunakan informasi tentang keberadaan-bersama (co-occurance) pasangan kata-kata. Jika n = 1 maka kita menamakannya unigram language model, yang menggunakan hanya probabilitas dari kata-kata secara sendiri-sendiri (individual). Dalam bidang penelitian IR, orang lebih banyak menggunakan unigram model karena urut-urutan kata tidak terlalu dipermasalahkan, tidak seperti dalam pengenal suara otomatis (speech recognition) yang sangat bergantung kepada kemampuan mesin memahami urutan kata-kata.

Salah satu model IR yang menggunakan LM adalah Query-Likelihood Model yang pertama diusulkan oleh Ponte dan Croft (1998). Dalam model ini diasumsikan bahwa para pemakai sistem sudah memiliki gambaran yang cukup tentang istilah-istilah yang akan ada di dokumen “ideal” yang akan memenuhi kebutuhan informasi mereka.  Lalu, diasumsikan pula bahwa istilah yang digunakan untuk mencari dokumen itu (atau biasa disebut query) dapat memisahkan yang “ideal” dari yang tidak.

Jadi, query dianggap sebagai perwakilah dari dokumen “ideal” itu. Tugas sistem dengan demikian adalah memperkirakan, bagi setiap dokumen di dalam koleksi, dokumen mana yang paling ideal, atau dalam bentuk rumus:

di mana Q adalah query dan D adalah dokumen. Probabilitas P(D) biasanya diasumsikan seragam atau universal, dan  P(Q|D) diestimasikan untuk setiap dokumen. Dengan kata lain, kita menduga sebaran probabilitas kata-kata di setiap dokumen dan menghitung probabilitas query sebagai sampel dari sebaran itu. Dokumen kemudian diurutkan sesuai nilai probabilitas ini.

Dalam artikelnya, Ponte dan Croft menggunakan Bernoulli multivariat untuk menghitung P(Q|D). Mereka menganggap sebuah query sebagai sebuah vektor dari atribut biner, masing-masing atribut untuk sebuah istilah yang unik di dalam kosakata indeks, dan menandakan ada-tidaknya istilah tersebut di dalam query. Jumlah kemunculan istilah tersebut di dalam query sendiri tidaklah diperhitungkan. Ada dua asumsi yang mendasari model ini, yaitu: 

  1. Semua atribut bernilai biner. Jika sebuah istilah ada di query, maka atribut yang mewakili istilah tersebut bernilai 1. Jika tidak, bernilai 0.
  2. Istilah dianggap tidak berkaitan (independen) di dalam sebuah dokumen. Asumsi ini mirip dengan asumsi yang digunakan dalam teori-teori IR probabilistrik.

Berdasarkan dua asumsi di atas, maka query likelihood P(Q|D) dapat dirumuskan sebagai hasil dari dua probabilitas, yaitu probabilitas kemunculan istilah pada query dan probabilitas ketidak-munculan istilah itu. Atau dalam rumus formal:  

P(w|D) dihitung dengan metode non-parametrik yang memanfaatkan probabilias rata-rata dari w (words, kata-kata) di dalam dokumen yang mengandungnya. Untuk istilah-istilah yang tidak muncul, maka probabilitas umum di dalam koleksi lah yang digunakan. Juga perlu diketahui bahwa statistik tentang koleksi, seperti frekuensi kemunculan istilah (term frequency) dan frekuensi dokumen merupakan bagian integral dari LM, walaupun tidak digunakan secara menyeluruh/heuristik seperi halnya di dalam teori-teori probabilitas.

LM juga dipakai untuk model relevansi, seperti yang diusulkan oleh Lavrenko dan Croft (2001). Secara konseptual, model ini merupakan gambaran tentang kebutuhan informasi. Dengan kata lain, model ini merupakan deskripsi tentang topik yang berkaitan dengan kebutuhan informasi seseorang. Diasumsikan bahwa di dalam sekumpulan dokumen dan query Q, maka ada sebuah model relevansi yang belum diketahui, kita sebut saja sebagai R. Model relevansi ini memakai probabilitas P(w|R) terhadap kemunculan kata di dokumen-dokumen yang dianggap relevan.  Dalam hal ini, dokumen yang relevan adalah sampel acak dari distrbiutsi P(w|R). Baik query maupun dokumennya merupakan sampel dari R.

Esensi dari model Lavrenko dan Croft adalah dalam mengestimasikan  P(w|R). Katakanlah  P(w|R) merupakan probabilitas bahwa sebuah kata yang secara acak diambil dari dokumen yang relevan adalah kata w. Jika kita tahu dokumen-dokumen mana saja yang relevan, kita dapat melakukan estimasi probabilitas secara otomatis. Persoalannya, di dalam lingkungan yang sebenarnya, kita seringkali tidak punya contoh tentang dokumen yang relevan. Maka diusulkan cara yang masuk akal untuk memperkirakan  P(w|R) dengan menggunakan probabilitas bersama (joint probability) terhadap kata w dan kata-kata dalam query  , sehingga menghasilkan rumus:

 

Model-model di atas menimbulkan gerakan baru dalam tradisi penelitian IR yang berbasis probabilitas. Sepanjang akhir tahun 1990an sudah ada berbagai upaya untuk membandingkan LM dengan teori probabilitas dalam IR. Perkembangan eksperimen menggunakan LM juga semakin banyak dalam berbagai aplikasi IR.

Bacaan:

Lavrenko, V. dan Croft, W.B. (2001), “Relevance-based language models” dalam roceedings of th 24th ACM SIGIR Annual International Conference on Research and Development in Information Retrieval, hal. 120-127.

Liu, X. dan W.B. Croft (2005), “Statistical language modeling for information retrieval” dalam Annual Review of Information Science and Technology, Cronin, B. (ed.), vol. 39, Medford, NJ : Information Today Inc, hal. 3-31.

Ponte, J. dan Croft, W.B. (1998), “A language modeling approach to information retrieval” dalam Proceedings of th 21st ACM SIGIR Annual International Conference on Research and Development in Information Retrieval, hal. 275 – 281.

 

 

Iklan

Posted in Information Retrieval, Teori | Dengan kaitkata: | 1 Comment »

Language Model

Posted by putubuku pada Maret 29, 2008

Bahasa manusia mengandung ketidakteraturan, walau sudah ada tata bahasa dan berbagai kesepakatan tentang penggunaan kata. Dalam konteks information retrieval (IR), ketidakaturan ini memang paling memusingkan. Selain manusia pencari informasi itu sendiri memiliki beragam keperluan, cara mereka menyampaikan keinginan atau pertanyaannya pun tidak beraturan. Belum lagi variasi dokumen yang akan disimpan dan dicari juga sangat beragam. Maka, sejak lama para ilmuwan mengimpikan cara mudah untuk MENEBAK apa yang ingin ditemukan oleh seorang pencari informasi.

Tebak-tebakan di sini, tentu saja, bukan sembarang tebak. Bukan seperti peramal menebak kapan ada gempa berdasarkan wangsit, atau seorang cenayang menebak siapa pemenang FA Cup tahun ini dengan membaca raut muka David Bechkam. Bukan pula seperti menebak kucing dalam karung, melainkan menebak dengan perhitungan matematik, atau yang lebih dikenal dengan menebak memakai teori probabilitas. Seorang ilmuwan Rusia bernama Markov pada awal abad 20 mengeluarkan sebuah rumus yang akhirnya dikenal dengan nama Markov Process.

Markov Process adalah  model matematik untuk menduga atau meramalkan keadaan atau kondisi di satu titik di masa depan dalam rangkaian proses tertentu. Dalam suatu proses, tentu ada kejadian-kejadian sebelumnya. Nah, kejadian atau keadaan ini dapat menjadi pola atau konteks untuk menentukan kemungkinan kejadian berikutnya. Jumlah dari kejadian sebelumnya yang akan digunakan untuk penentuan ini disebut sebagai “order”. Dalam “first order process”, maka kemungkinan tentang kejadian berikutnya hanya dipengaruhi oleh satu kejadian terakhir sebelumnya. Dalam “second order Markov process”, probabilitas itu tergantung pada dua kejadian terakhir. Demikian seterusnya.

Apa hubungannya Markov Process dan information retrieval? Sabar dulu….

Orang-orang linguistik, terutama yang tertarik menggunakan teori bahasa dalam komputerisasi , menggunakan Markov process untuk mengembangkan apa yang disebut Language Model (atau disingkat LM). Ini adalah model tentang distribusi kondisional dari identitas kata yang kesekian dalam sebuah rangkaian, yang ditentukan oleh identitas dari semua kata-kata sebelumnya. Dalam trigram model, bahasa tertulis diandaikan dengan memakai model matematik “second-order Markov process” . Dengan model ini, komputer dapat diprogram untuk memperkirakan kata yang akan muncul berikutnya, jika diketahui dua kata sebelumnya.

Dengan membatasi “tebak-tebakan” berdasarkan dua kata sebelumnya, trigram model tentu saja menggunakan asumsi bahwa penggunaan bahasa manusia mengikuti hukum “a second-order Markov process”. Misalnya, jika seseorang berkata “saya mau makan, lalu mau …. “, maka LM dapat digunakan untuk menebak apa kata berikutnya setelah “mau” yang kedua di kalimat tak lengkap tersebut. Tentu saja, tebakan ini akan sangat akurat jika komputer sudah diprogram sangat baik, sehingga mengenali pola atau konteks dua kata sebelum kata “mau” yang terakhir, yaitu kata “makan”. Kata apa yang biasanya dekat berhubungan dengan “makan”? Mungkin saja “minum”, atau mungkin juga “ke kamar kecil”, dan bahkan mungkin juga “tidur”, tetapi sangat jarang “merampok”. Jadi, komputer bisa saja membuat empat tebakan:

  • “saya mau makan, lalu mau minum “
  • “saya mau makan, lalu mau ke kamar kecil “
  • “saya mau makan, lalu mau tidur “
  • “saya mau makan, lalu mau merampok bank “

 Tebakan terakhir tentu lebih kecil kemungkinannya. Dalam kenyataannya, penggunaan lebih dari dua kata sebelumnya akan lebih meningkatkan akurasi perkiraan penggunaan kata berikutnya. Namun, model yang lebih tinggi dari “second order” sangatlah menyulitkan komputer dalam mengkalkulasi, sebab hitungan n-gram yang menyertai model ini bersifat eksponensial. Jika n > 3, maka sumberdaya komputasi yang diperlukan untuk melakukan kalkulasi dan prediksi menjadi amat sangat besar.

Nah, dengan hitung-hitungan matematis menggunakan sumberdaya komputer yang sekarang ada, maka dapatlah dibuat (secara teoritis, lho!) sebuah sistem IR yang memanfaatkan LM. Secara teoritis kita mengasumsikan bahwa setiap orang yang mencari informasi sebenarnya sudah punya punya bayangan ideal tentang istilah-istilah yang akan ada di dokumen yang mereka cari. Kemudian, istilah yang mereka gunakan dalam pertanyaan/permintaan (query) bisa memisahkan mana dokumen yang “tepat” dari yang tidak. Jadi, query memang dianggap sebagai “sekeping teks yang mewakili dokumen ideal”. Tugas sebuah sistem IR dengan demikian adalah memperkirakan, bagi setiap dokumen di dalam koleksi, dokumen mana yang paling ideal untuk query tertentu.

Sesuai dengan LM dan teori probabilitas Markov, maka sistem IR dapat membuat perkiraan distribusi kata-kata di setiap dokumen dan membuat model untuk setiap dokumen tersebut. Lalu, dengan cara yang sama, sistem IR juga membuat perkiraan distribusi kata-kata di dalam query yang diajukan oleh seorang pencari. Nah, akhirnya dokumen diurut-urutkan (ranking) menurut kemungkinan (probabilitas) kecocokan antara model query dan model dokumen. Ini disebut sebagai query likelihood retrieval model, alias model berdasarkan kemungkinan-kecocokan.

Penggunaan LM dalam sistem IR masih di tahap laboratorium atau hitung-hitungan teoritis, tetapi setidaknya menimbulkan harapan baru. Ahh…., namanya juga.. U s a h a.

Catatan tambahan: jika ingin tahu penggunaan statistik dalam LM, baca artikel pengantarnya di sini.

Posted in Information Retrieval, Teori | Dengan kaitkata: , , | 7 Comments »