Life must go on~

Rangkuman Pertemuan 22 mengenai Natural Language Processing : 

1. Text Classification 

Text Classification atau Text Categorization adalah suatu proses pengelompokan dokumen, yang dalam tugas akhir ini adalah konten web page, ke dalam beberapa kelas yang telah ditentukan. Jika tidak ada overlap antar kelas, yaitu setiap dokumen hanya dikelompokan kedalam satu kelas maka text categorization ini disebut single label text categorization . Text categorization bertujuan untuk menemukan model dalam mengkategorisasikan teks natural language. Model tersebut akan digunakan untuk menentukan kelas dari suatu dokumen.

Beberapa metode text categorization yang sering dipakai antara lain : k- Nearest Neighbor, Naïve Bayes, Support Vektor Machine, Decision Tree, Neural Networks, Boosting.

Dalam pengaplikasian text categorization terdapat beberapa tahap, yaitu : 

>>Preprocessing

Tahap pertama dalam text categorization adalah dokumen preprocessing adalah :

1. Ekstrasi Term

Ekstrasi term dilakukan untuk menentukan kumpulan term yang mendeskripsikan dokumen. Kumpulan dokumen di parsing untuk menghasilkan daftar term yang ada pada seluruh dokumen. Daftar term yang dihasilkan disaring dengan membuang tanda baca, angka, simbol dan stopwords. Dalam tugas akhir ini akan dibahas juga mengenai pengaruh stopwords removal terhadap hasil klasifikasi. Berikut ini merupakan penjelasan singkat mengenai stopwords.

Kebanyakan bahasa resmi di berbagai negara memiliki kata fungsi dan kata sambung seperti artikel dan preposisi yang hampir selalu muncul pada dokumen teks. Biasanya kata-kata ini tidak memiliki arti yang lebih di dalam memenuhi kebutuhan seorang searcher di dalam mencari informasi. Kata-kata tersebut (misalnya a, an, dan on pada bahasa Inggris) disebut sebagai Stopwords.

Sebuah sistem Text Retrieval biasanya disertai dengan sebuah Stoplist. Stoplist berisi sekumpulan kata yang ‘tidak relevan’, namun sering sekali muncul dalam sebuah dokumen. Dengan kata lain Stoplist berisi sekumpulan Stopwords.

Stopwords removal adalah sebuah proses untuk menghilangkan kata yang ‘tidak relevan’ pada hasil parsing sebuah dokumen teks dengan cara membandingkannya dengan Stoplist yang ada.

2. Seleksi Term

Jumlah term yang dihasilkan pada feature ekstrasi dapat menjadi suatu data yang berdimensi cukup besar. Karena dimensi dari ruang feature merupakan bag-of-words hasil pemisahan kata dari dokumennya. Untuk itu perlu dilakukan feature selection untuk mengurangi jumlah dimensi.

3. Representasi Dokumen

Supaya teks natural language dapat digunakan sebagai inputan untuk metode klasifikasi maka teks natural language diubah kedalam representasi vektor. Dokumen direpresentasikan sebagai vektor dari bobot term, dimana setiap term menggambarkan informasi khusus tentang suatu dokumen. Pembobotan dilakukan dengan melakukan perhitungan TFIDF. Term beserta bobotnya kemudian disusun dalam bentuk matrik.

>>Training Phase

Tahap kedua dari text categorization adalah training. Pada tahap ini system akan membangun model yang berfungsi untuk menentukan kelas dari dokumen yang belum diketahui kelasnya. Tahap ini menggunakan data yang telah diketahui kelasnya (data training) yang kemudian akan dibentuk model yang direpresantasikan melalui data statistik berupa mean dan standar deviasi masing-masing term pada setiap kelas.

>>Testing Phase

Tahap terakhir adalah tahap pengujian yang akan memberikan kelas pada data testing dengan menggunakan model yang telah dibangun pada tahap training. Tujuan dilakukan testing adalah untuk mengetahui performansi dari model yang telah dibentuk. Dengan beberapa parameter pengukuran yaitu akurasi, precision, recall, dan f-measure.

 

2. Information Retrieval

Information Retrieval digunakan untuk menemukan kembali informasi-informasi yang relevan terhadap kebutuhan pengguna dari suatu kumpulan informasi secara otomatis. Salah satu aplikasi umum dari sistem temu kembali informasi adalah search-engine atau mesin pencarian yang terdapat pada jaringan internet. Pengguna dapat mencari halaman-halaman Web yang dibutuhkannya melalui mesin tersebut.

Ukuran efektifitas pencarian ditentukan oleh precision dan recall. Precision adalah rasio jumlah dokumen relevan yang ditemukan dengan total jumlah dokumen yang ditemukan oleh search-engine. Precision mengindikasikan kualitas himpunan jawaban, tetapi tidak memandang total jumlah dokumen yang relevan dalam kumpulan dokumen.

Recall adalah rasio jumlah dokumen relevan yang ditemukan kembali dengan total jumlah dokumen dalam kumpulan dokumen yang dianggap relevan.

Dalam Information Retrieval, mendapatkan dokumen yang relevan tidaklah cukup. Tujuan yang harus dipenuhi adalah bagaimana mendapatkan doukmen relevan dan tidak mendapatkan dokumen yang tidak relevan. Tujuan lainnya adalah bagaimana menyusun dokumen yang telah didapatkan tersebut ditampilkan terurut dari dokumen yang memiliki tingkat relevansi lebih tingi ke tingkat relevansi rendah. Penyusunan dokumen terurut tersebut disebut sebagai perangkingan dokumen. Model Ruang Vektor dan Model Probabilistik adalah 2 model pendekatan untuk melakukan hal tersebut.

Model ruang vektor dan model probabilistik adalah model yang menggunakan pembobotan kata dan perangkingan dokumen. Hasil retrieval yang didapat dari model-model ini adalah dokumen terangking yang dianggap paling relevan terhadap query.

Dalam model ruang vektor, dokumen dan query direpresentasikan sebagai vektor dalam dalam ruang vektor yang disusun dalam indeks term, kemudian dimodelkan dengan persamaan geometri. Sedangkan model probabilistik membuat asumsi-asumsi distribusi term dalam dokumen relevan dan tidak relevan dalam orde estimasi kemungkinan relevansi suatu dokumen terhadap suatu query.

 

3. HITS Algorithm

Hyperlink-Induced Topic Search (HITS) adalah sebuah algoritma analisis link halaman Web, yang merupakan pendahulu dari PageRank. Ide di balik Dengan kata lain, sebuah hub baik mewakili halaman yang menunjuk ke halaman lain, dan otoritas yang baik mewakili halaman yang dihubungkan oleh banyak hub berbeda.

Algoritma ini melakukan serangkaian iterasi, masing-masing terdiri dari dua langkah dasar, yaitu :

1. Authority Update :
   Memperbarui skor Authority setiap node untuk menjadi sama dengan jumlah dari Hub Skor dari setiap node yang menunjuk ke itu. Artinya, node diberi skor otoritas tinggi dengan menjadi terhubung ke halaman yang dikenali sebagai hub untuk informasi.

2. Hub Update :
   Memperbarui setiap node Hub Skor menjadi sama dengan jumlah dari Otoritas Skor dari setiap node yang menunjuk ke. Artinya, node diberi skor tinggi hub dengan menghubungkan ke node yang dianggap otoritas pada subjek.

Algoritma Hyperlink Induced Topic Search (HITS) Kleinberg memberikan gagasan baru tentang hubungan antara hubs dan authorities. Dalam algoritma HITS, setiap simpul (situs) p diberi bobot hub (xp) dan bobot authority (yp).

Pada akhirnya, algoritma HITS ini menghasilkan sebuah daftar singkat yang terdiri dari situs-situs dengan bobot hub terbesar serta situs-situs dengan bobot authority terbesar. Yang menarik dari algoritma HITS adalah: setelah memanfaatkan kata kunci (topik yang dicari) untuk membuat himpunan akar (root) R, algoritma ini selanjutnya sama sekali tidak mempedulikan isi tekstual dari situs-situs hasil pencarian tersebut.

Dengan kata lain, HITS murni merupakan sebuah algoritma berbasis link setelah himpunan akar terbentuk. Walaupun demikian, secara mengejutkan HITS memberikan hasil pencarian yang baik untuk banyak kata kunci.

Sebagai contoh, ketika dites dengan kata kunci “search engine”, lima authorities terbaik yang dihasilkan oleh algoritma HITS adalah Yahoo!, Lycos, AltaVista, Magellan, dan Excite – padahal tidak satupun dari situs-situ tersebut mengandung kata “search engine”.

 

4. Prolog

Prolog  adalah singkatan daripada PROgramming in LOGic. Prolog merupakan  satu ide yang dicetuskan pada awal 1970an untuk menggunakan logika  sebagai bahasa pemprograman. Mereka yang bertanggungjawab dalam  pengembangan ide ini ialah Robert Kowalski dari Edinburgh dalam aspek  teori dan Colmerauer dari Marseilles dalam aspek implementasi.

Prolog biasanya dikaitkan dengan berlogika dan merupakan bahasa pemprograman untuk  perhitungan simbolik dan tak-berangka. Prolog paling sesuai untuk  menyelesaikan masalah yang berkaitan dengan objek dan hubungan  antara objek, masalah persamaan corak, masalah penjejakan ke  belakang dan masalah yang informasinya tidak lengkap.

Algoritma dalam Prolog terdiri dari logika dan kontrol. Logika merupakan  fakta dan peraturan yang menerangkan apa yang seharusnya dilakukan  oleh algoritma. Sedangkan kontrol merupakan cara algoritma bisa Munir: Pengenalan Bahasa Prolog 2
diimplementasikan dengan menggunakan peraturan. Sintaks yang  dibentuk dalam Prolog adalah dalam bentuk klausa atau formula First  Order Predicate Logic.

Prolog adalah bahasa pemrograman logika atau di sebut juga sebagai bahasa non-procedural. Namanya diambil dari bahasa Perancis programmation en logique (pemrograman logika).  Bahasa ini diciptakan oleh Alain Colmerauer dan Robert Kowalski sekitar tahun 1972 dalam upaya untuk menciptakan suatu bahasa pemrograman yang memungkinkan pernyataan logika alih-alih rangkaian perintah untuk dijalankan komputer.

Berbeda dengan bahasa pemrograman yang lain, yang menggunakan algoritma konvensional sebagai teknik pencariannya seperti pada Delphi, Pascal, BASIC, COBOL danbahasa pemrograman yang sejenisnya, maka prolog menggunakan teknik pencarian yang di sebut heuristik (heutistic) dengan menggunakan pohon logika.

http://www.binus.ac.id/

1. Apa yang dimaksud supervised learning, unsupervised learning dan reinforcement learning?berikan contoh masing-masing?

Jawaban : 

Supervised learning merupakan suatu pembelajaran yang terawasi dimana jika output yang diharapkan telah diketahui sebelumnya. Biasanya pembelajaran ini dilakukan dengan menggunakan data yang telah ada. Pada metode ini, setiap pola yang diberikan kedalam jaringan saraf tiruan telah diketahui outputnya. Satu pola input akan diberikan ke satu neuron pada lapisan input. Pola ini akan dirambatkan di sepanjang jaringan syaraf hingga sampai ke neuron pada lapisan output. Lapisan output ini akan membangkitkan pola output yang nantinya akan dicocokkan dengan pola output targetnya. Apabila terjadi perbedaan antara pola output hasil pembelajaran dengan pola output target, maka akan muncul error. Dan apabila nilai error ini masih cukup besar, itu berarti masih perlu dilakukan pembelajaran yang lebih lanjut.

Contoh algoritma jaringan saraf tiruan yang menggunakan metode supervised learning adalah :

– Hebbian (Hebb rule)

– Perceptron

– Adaline

– Boltzman

– Hapfield

– Backpropagation.

Unsupervised learning merupakan pembelajaran yang tidak terawasi yang tidak memerlukan target output. Pada metode ini tidak dapat ditentukan hasil seperti apa yang diharapkan selama proses pembelajaran. Nilai bobot yang disusun dalam proses range tertentu tergantung pada nilai output yang diberikan. Tujuan metode uinsupervised learning ini agar kita dapat mengelompokkan unit-unit yang hampir sama dalam satu area tertentu. Pembelajaran ini biasanya sangat cocok untuk klasifikasi pola.

Contoh algoritma jaringan saraf tiruan yang menggunakan metode unsupervised ini adalah :

– Competitive

– Hebbian

– Kohonen

– LVQ(Learning Vector Quantization) 

– Neocognitron

Reinforcement Learning adalah salah satu paradigma baru di dalam learning theory. RL  dibangun dari proses mapping (pemetaan) dari situasi yang ada di environment (states)  ke bentuk aksi (behavior) agar dapat memaksimalkan reward. Agent yang bertindak  sebagai sang learner tidak perlu diberitahukan behavior apakah yang akan sepatutnya  dilakukan, atau dengan kata lain, biarlah sang learner belajar sendiri dari  pengalamannya. Ketika ia melakukan sesuatu yang benar berdasarkan rule yang kita
tentukan, ia akan mendapatkan reward, dan begitu juga sebaliknya.

RL secara umum terdiri dari 4 komponen dasar, yaitu :
1. Policy : kebijaksanaan
2. Reward function
3. Value function
4. Model of environment

Policy adalah fungsi untuk membuat keputusan dari agent yang menspesifikasikan  tindakan apakah yang mungkin dilakukan dalam berbagai situasi yang ia jumpai. Policy  inilah yang bertugas memetakan perceived states ke dalam bentuk aksi. Policy bisa  berupa fungsi sederhana, atau lookup table. Policy ini merupakan inti dari RL yang  sangat menentukan behavior dari suatu agent.

Reward function mendefinisikan tujuan dari kasus atau problem yang dihadapi. Ia  mendefinisikan reward and punishment yang diterima agent saat ia berinteraksi dengan  environment. Tujuan utama dari rewar d function ini adalah memaksimalkan total  reward pada kurun waktu tertentu setelah agent itu berinteraksi.

Value function menspesifikasikan fungsi akumulasi dari total reward yang didapatkan  oleh agent. Jika reward function berbicara pada masing-masing partial time dari proses  interaksi, value function berbicara pada long-term dari proses interaksi.

Model of environment adalah sesuatu yang menggambarkan behavior dari environment.  Model of environment ini sangat berguna untuk mendesain dan merencanakan behavior  yang tepat pada situasi mendatang yang memungkinkan sebelum agent sendiri  mempunyai pengalaman dengan situasi itu. Saat masa-masa awal RL dikembangkan,  model of environment yang ada berupa trial and error. Namun modern RL sekarang  sudah mulai menjajaki spektrum dari low -level, trial and error menuju high-level,
deliberative planning.

2. Apa yang dimaksud dengan Learning Decision Tree dan berikan contohnya?

Learning Decision Tree adalah salah satu  metode belajar yang sangat populer dan banyak digunakan secara praktis. Metode ini  merupakan metode yang berusaha  menemukan fungsi-fungsi pendekatan yang  bernilai diskrit dan tahan terhadap data-data  yang terdapat kesalahan (noisy data) serta  mampu mempelajari ekspresi-ekspresi  disjunctive (ekspresi OR). Iterative  Dychotomizer version 3 (ID3) adalah salah  satu jenis Decision tree yang sangat populer.

Konsep Decision Tree adalah mengubah data menjadi pohon keputusan  (decision tree) dan aturan-aturan keputusan  (rule).

DATA >> DECISION TREE >> RULE

Decision tree adalah struktur flowcart  yang mempunyai tree(pohon), dimana setiap  simpul internal menandakan suatu tes  atribut,setiap cabang merepresentasikan hasil  tes, dan simpul daun merepresentasikan kelas  atau distribusi kelas. Alur pada decision tree  ditelusuri dari simpul ke akar ke simpul daun  yang memegang prediksi kelas untuk contoh  tersebut. Decision tree mudah untuk dikonversi  ke aturan klasifikasi (classification rule).  Konsep data dalam decision tree dinyatakan  dalam bentuk tabel dengan atribut dan record.

Contoh :

1. DATA SAMPLE

Ada 10 variabel yang digunakan  untuk dasar mengambil keputusan. Kelas keputusan ada dua yaitu Menunggu/Tidak di sebuah restoran

Alt : Alternate ;

Bar : ada bar atau tidak ;

Fri : Weekend ;

Hun : Hungry ;

Pat:  pengunjung ;

Price : harga ;

Rain;

Res : Reservation ;

Type : tipe restoran ;

Est : estimated time

2. DECISION TREE RESULT

Kotak yang diarsir adalah daun . Kotak tanpa arsiran adalah akar atau cabang . Pola untuk mengubah menjadi RULE adalah :

1)      Akar/Cabang adalah proposisi pembentuk frase IF

2)      Daun adalah proposisi pembentuk Frase THEN

Contoh :

1)      IF Patron = None THEN Wait = False

2)      IF Patron = Full and Hungry = Yes and Type = French Then  wait = true

3)      IF Patron = Full and Hungry = Yes and Type = Thai and Fri/Sat = yes  Then  wait = true

dst.

www.binus.ac.id