Ilmu Perpustakaan & Informasi

diskusi dan ulasan ringkas

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.

7 Tanggapan to “Language Model”

  1. aik said

    dari tulisannya saya belum melihat perhitungan probabilitasnya, please tulis juga hitungannya.

  2. putubuku said

    @Aik – saya memang menyederhanakan tulisan tentang LM karena (dalam persepsi saya) khalayak yang dituju oleh blog ini memang hanya memerlukan pengetahuan umum. Jika perlu artikel yang lebih spesifik dan berisi hitungan (rumus), silakan ambil langsung di:

    http://citeseer.ist.psu.edu/cache/papers/cs/1619/http:zSzzSzcobar.cs.umass.eduzSzpubfileszSzir-120.pdf/ponte98language.pdf

    atau di:

    http://citeseer.ist.psu.edu/cache/papers/cs/22989/http:zSzzSzciir.cs.umass.eduzSzpubfileszSzir-171.pdf/song99general.pdf

    keduanya langsung berkaitan dengan penerapan LM di information retrieval.

    Thanks for stopping by!

  3. minda_malau said

    maaf numpang nanya..
    untuk nilai transisi antar statenya gimana?? soalnya yg pernah saya baca markov kan pake state2 gitu, klo untuk mode peramalan, nilai transisi ke next statenya gimana gitu??
    bisa kasih liat contoh gambar state untuk bentuk peramalannya?
    trus untuk proses searchingnya, pada dokumen dilakukan clustering ato klasifikasi terlebih dulu ga??
    ada iterasi?di bagian mananya??
    maaf ya banyak tanya,,hehehe,,
    terima kasih banyakkk…..

  4. minda_malau said

    maaf sekali lagi nanya (dan mungkin berkali2)
    ada referensi yang menyangkut model peramalan pake markov ini??
    makasihh..

  5. putubuku said

    @ Minda – maaf baru buka blog lagi, aksesnya lagi lemot banget. Saya akan coba carikan referensi yang kamu maksud, tapi harus buka-buka jurnal lagi. Kadang-kadang malesss..hehehehehe. So be patience.

  6. mei said

    mau nanya, dalam language model yang menjadi model apa ? bentuk model nya seperti apa ya..

    Terima Kasih

  7. […] 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) […]

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

 
%d blogger menyukai ini: