Natural Language Processing

1. Text Classification / Text Categorization
Text classification adalah proses pengklasifikasian dokumen menjadi beberapa kategori yang telah ditetapkan, berdasarkan muatan masing-masing. Text classification merupakan syarat awal dari sistem text retrieval yang mengambil teks-teks yang ada sebagai respon dari masukan (query) user, dan sistem text understanding yang mengubah teks menjadi kesimpulan, jawaban dari pertanyaan, atau makna dari data. Algoritma supervised learning untuk pengklasifikasian teks yang ada saat ini membutuhkan dokumen yang cukup agar bisa belajar dan berkembang secara akurat.
Banyak algoritma yang telah dikembangkan untuk menangani text classification secara otomatis. Yang paling umum digunakan adalah Naive Bayes classifier, association rule mining, genetic algorithm, dan decision tree.

Bayesian Classifier dijalankan berdasarkan Bayes theorem. Sebuah Bayesian classification sederhana yang dinamakan naive classification dinilai memiliki performa setara dengan decision tree dan neural network classifier. Naive Bayes classification mengasumsikan bahwa efek dari nilai sebuah atribut dari kelas yang diberikan bersifat independen terhadap nilai atribut lain. Asumsi ini dinamakan class conditional independence. Bayes classifier adalah yang paling populer dan memiliki performa terbaik. Klasifikasi yang dilakukan terhadap data baru kurang lebih dengan cara memilih kelas yang dirasa paling mirip dengan contoh sebelumnya. Akurasi dari algoritma ini berkisar antara 41 % hingga 74 %.

Association rule mining mencari dan menemukan hubungan atau korelasi diantara himpunan data yang besar. Singkat kata, association rule mining berdasarkan pengasosiasian hubungan. Algoritma ini dijalankan berdasarkan 2 faktor utama yang disebut minumum support threshold dan minimum confidence threshold.
Association rule mining diterapkan bersamaan dengan Bayes classifier, untuk pengklasifikasian teks. Association rule mining bergantung pada Bayes classifier. Namun, metode ini menerapkan perhitungan secara negatif terhadap setiap penentuan kelas khusus pada beberapa kasus, sehingga akurasinya hanya mampu mencapai 60 %.

Genetic algorithm adalah bagian dari komputasi yang evolusioner yang bertumbuh cepat di bidang AI ini. Algoritma ini dibuat berdasarkan teori evolusi Darwin. Dengan kata lain, sebuah masalah diselesaikan melalui proses evolusi yang menghasilkan hasil terbaik yang paling mampu bertahan, atau singkat kata solusi itu sendiri berevolusi. Tingkat keberhasilannya bisa mencapai 69 %, namun butuh waktu yang lama mengingat waktu evolusi yang dibutuhkan tidaklah sebentar.

2. Information Retrieval (Temu Kembali Informasi)
Information Retrieval adalah seni dan ilmu mencari informasi dalam dokumen, mencari dokumen itu sendiri, mencari metadata yang menjelaskan dokumen, atau mencari dalam database, apakah relasional database itu berdiri sendiri atau database hypertext jaringan seperti Internet atau intranet, untuk teks , suara, gambar, atau data

Secara prinsip, penyimpanan informasi dan penemuan kembali informasi adalah hal yang sederhana. Misalkan terdapat tempat penyimpanan dokumen-dokumen dan seseorang (user) merumuskan suatu pertanyaan (request atau query) yang jawabannya adalah himpunan dokumen yang mengandung informasi yang diperlukan yang diekspresikan melalui pertanyaan user. User bisa saja memperoleh dokumen-dokumen yang diperlukannya dengan membaca semua dokumen dalam tempat penyimpanan, menyimpan dokumen-dokumen yang relevan dan membuang dokumen lainnya. Hal ini merupakan perfect retrieval, tetapi solusi ini tidak praktis. Karena user tidak memiliki waktu atau tidak ingin menghabiskan waktunya untuk membaca seluruh koleksi dokumen, terlepas dari kenyataan bahwa secara fisik user tidak mungkin dapat melakukannya.

Information Retrieval merupakan bagian dari computer science yang berhubungan dengan pengambilan informasi dari dokumen-dokumen yang didasarkan pada isi dan konteks dari dokumen-dokumen itu sendiri. Information Retrieval merupakan suatu pencarian informasi (biasanya berupa dokumen) yang didasarkan pada suatu query (inputan user) yang diharapkan dapat memenuhi keinginan user dari kumpulan dokumen yang ada. Sedangkan, definisi query dalam Information Retrieval menurut referensi merupakan sebuah formula yang digunakan untuk mencari informasi yang dibutuhkan oleh user, dalam bentuk yang paling sederhana, sebuah query merupakan suatu keywords (kata kunci) dan dokumen yang mengandung keywords merupakan dokumen yang dicari dalam IRS.

Proses yang terjadi di dalam Information Retrieval System terdiri dari 2 bagian utama, yaitu Indexing subsystem, dan Searching subsystem (matching system). Proses indexing dilakukan untuk membentuk basisdata terhadap koleksi dokumen yang dimasukkan, atau dengan kata lain, indexing merupakan proses persiapan yang dilakukan terhadap dokumen sehingga dokumen siap untuk diproses. Proses indexing sendiri meliputi 2 proses, yaitu document indexing dan term indexing. Dari term indexing akan dihasilkan koleksi kata yang akan digunakan untuk meningkatkan performansi pencarian pada tahap selanjutnya. Tahap-tahap yang terjadi pada proses indexing ialah:

1. Word Token, yaitu mengubah dokumen menjadi kumpulan term dengan cara menghapus semua karakter dalam tanda baca yang terdapat pada dokumen dan mengubah kumpulan term menjadi lowercase.
2. Stopword Removal. Proses penghapusan kata-kata yang sering ditampilkan dalam dokumen seperti: and, or, not dan sebagainya.
3. Stemming. Proses mengubah suatu kata bentukan menjadi kata dasar.
4. Term Weighting. Proses pembobotan setiap term di dalam dokumen.

Model IR ada tiga jenis, yaitu :
– Model Boolean : merupakan model IR sederhana yang berdasarkan atas teori himpunan dan aljabar boolean
– Model Vector Space : merupakan model IR yang merepresentasikan dokumen dan query dalam bentuk vektor dimensional
– Model Probabilistic : merupakan model IR yang menggunakan framework probabilistic

3.HITS Algorithm (Hyperlink-Induced Topic Search)
Hal ini hampir sama dengan algoritma PageRank, tapi HITS tidak menghitung jumlah link di halaman, tapi melihat-lihat link yang ditemukan, jika sesuai dengan tujuan link, kata-kata yang lebih tepat antara link asal ke link tujuan akan semakin tinggi nilai otoritas nya dalam halaman.
Ide dasar dibalik algoritma ini adalah bahwa semua halaman web di internet dikategorikan ke dalam dua kelompok yang disebut Hub dan Authoritas. Hub menentukan halaman web yang telah keluar ke suatu link yang merupakan halaman web penting lainnya dan authoritas menentukan halaman web yang memiliki link masuk dari halaman web penting lainnya. Pengaplikasian algoritma hits adalah search engine querying (Kecepatan merupakan suatu masalah, mencari komunitas web, mencari halaman web terkait, mengisi kategori dalam direktori web, dan menganalisis suatu kutipan.

4. Prolog (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.

www.binus.ac.id

Pembahasan dari soal GSLC 2

1. Apa yang dimaksud Supervised Learning, Unsupervised Learning dan Reinforcement Learning ? Berikan contoh masing-masing.

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

Jawab :

1. Supervised Learning adalah suatu model pembelajaran dimana antara input yang diuji dan output yang diharapkan sudah saling berkaitan dengan pasti, berdasarkan data pengalaman yang sudah ada sebelumnya. Dengan kata lain, jika kita memaskukkan suatu input, maka sebelum dieksekusi untuk diuji, kita telah mengetahui output apa yang diharapkan berdasarkan pengalamana yang telah ada. Pengalaman yang dimaksud disini adalah kumpulan data percobaan dengan pola input dan output yang hampir atau bahkan sama dengan apa yang akan diujikan. Dalam Supervised Learning, antara input dan output bisa dikatakan berpasangan. .
Metode ini umumnya berjalan dengan cepat dan akurat, dan memiliki kemampuan “generalize“ yaitu kemampuan untuk menarik kesimpulan dengan tepat ketika suatu input yang berbeda diujikan ke sistem tanpa memiliki data output yang diharapkan, atau input yang dimasukkan belum pernah ditemui.
Contoh penggunaannya adalah pada hebbian (hebb rule), perceptron, adaline, boltzman, hapfield, dan backpropagation.

Unsupervised Learning merupakan metode pembelajaran dimana ketika kita menguji suatu input, kita belum memiliki data mengenai output yang diharapkan sama sekali. Dengan kata lain, kita meminta sistem untuk melakukan suatu hal yang sama sekali kita tidak ketahui hasilnya sebelumnya. Jika digambarkan dengan tree, model dari unsupervised learning, ukurannya akan lebih besar dan mendalam dibandingkan dengan supervised learning sebab supervised learning hanya mencoba mencari hubungan antara dua himpunan percobaan. Dalam unsupervised learning, tingkat kesulitan dari pembelajaran masalah meningkat secara eksponensial seiring dengan jumlah langkah antara 2 himpunan. Selain itu, unsupervised learning umum digunakan untuk mengelompokkan input ke dalam kelas-kelas berdasarkan properti/atribut dari inputan tersebut.
2 macam pendekatan pada unsupervised learning yaitu dengan mengajarkan sistem bukan dengan memberi klasifikasi secara eksplisit namun dengan sistem penilaian positif untuk mengindikasikan suatu keberhasilan, dan sebaliknya untuk suatu kegagalan. Seolah-olah mengajarkan anak kecil mana yang benar dan mana yang tidak tanpa memberi aturan yang eksplisit kepada si anak. Pendekatan ini lebih sukses pada penerapan di dunia nyata.Pendekatan lainnya dikenal sebagai clustering, yang bertujuan untuk menemukan persamaan yang ada dari data sebelumnya (input sebelumnya) dan dimasukkan ke dalam kelas-kelas. Contoh penggunaannya adalah pada metode competitive, hebbian, kohonen, Learning Vector Quantization, dan neocognitron.

Recognition Learning adalah metode pembelajaran dengan mempertimbangkan langkah mana yang akan diambil ketika suatu input diberi agar menghasilkan output yang lebih baik. Sistem tidak akan diberi tahu langkah apa yang harus diambil, namun lebih kepada aksi mana yang lebih menguntungkan. Hasil yang diperoleh sistem dengan pembelajaran ini akan mempengaruhi hasil yang akan diperoleh selanjutnya ketika suatu input diberikan. Pembelajaran ini memiliki sifat exploitation yaitu mempertimbangkan langkah terbaik berdasarkan pengalaman yang sudah ada, dan exploration yaitu mencoba langkah baru untuk mencari tahu apakah langkah tersebut mampu membawa hasil yang optimal.
Ada 4 sub-elemen dari Recognition Learning, yaitu :
– Policy (“Apa yang harus dilakukan sekarang ?”)
– Fungsi Reward (“Seberapa bagus aksi ini ?”)
– Fungsi Value (“Seberapa bagus tahap ini ?”)
– Dinamika Lingkungan (“Apa yang terjadi jika saya mengambil aksi ini ?”)

2. Decision Tree adalah representasi yang mudah dalam mengelompokkan contoh-contoh yang disediakan, dimana tiap node yang bukan leaf diberi tanda sebagai sebuah fitur inputan. Secara sederhana, tiap kali mencoba mengambil keputusan, sistem diarahkan pada data input yang tersedia dengan label yang spesifik, dan setelah mengambil aksi, sistem bisa saja sudah memperoleh hasil atau tiba pada cabang pemilihan lainnya dengan fitur spesifik yang berhubungan dengan aksi yang telah diambil.
Contohnya seperti pada gambar berikut :

Length, Thread, dan Author adalah fitur yang dimaksud, leaf adalah output yang diperoleh.

Referensi :
> www.astro.caltech.edu/~george/aybi199/Donalek_Classif.pdf
> users.ics.aalto.fi/harri/thesis/valpola_thesis/node34.html
> www.aihorizon.com/essays/generalai/supervised_unsupervised_machine_learning.htm
> ungkapkandengankata.wordpress.com/2011/06/19/supervised-dan-unsupervised-learning/
> lecturer.eepis-its.edu/~entin/Machine%20Learning/Minggu%2012/Minggu%2012%20Reinforcement%20Learning.pdf
> sonoku.com/education/lectures-education/reinforcement-learning-intro/
> artint.info/html/ArtInt_177.html#dt-example

Pembahasan dari soal GSLC 1

1. Apa yang dimaksud Adversarial Search & Constraint Satisfaction Problems ? Berikan contoh.
2. Apa itu Propositional Logic ? Berikan contoh.

Jawab :

1. Secara sederhana, adversarial search lebih dikenal sebagai sebuah game (permainan) yangg umumnya diaplikasikan dalam permainan-permainan dimana membutuhkan dua pihak yang akan saling mengalahkan satu sama lain. Umumnya, permainan yang dititikberatkan disini adalah permainan yang melibatkan 2 orang atau lebih dan secara bergiliran mengambil keputusan.
Permainan yang dimaksud disini bisa dikategorikan ke permainan bersifat deterministik dan permainan berdasarkan kesempatan. Untuk masing-masing kategori, bisa memiliki sifat perfect information (kedua pemain sama-sama tahu keadaan yang pasti) dan imperfect information (kedua pemain memiliki informasi terbatas yang tergantung pada langkah yang diambil). Contohnya catur (deterministik-perfect information), monopoly (kesempatan-perfect information), bridge (deterministik-imperfect information), dan poker (kesempatan-imperfect information).
Sebuah game dapat didefinisikan melalui initial state (status awal permainan/bagaimana set awal sebelum permainan dimulai), legal actions (tindakan2 sah), hasil tiap tindakan, terminal test (status ketika permainan dinyatakan selesai), dan sebuah utility function (pemberi hasil numerik) yang dijalankan ketika permainan selesai.
Dalam penerapannya, adversarial search umumnya menggunakan pencarian minimax dan alpha-betha pruning (pemangkasan alpha-beta).
Constrain Satisfaction Problem merupakan sebuah masalah khusus yang memenuhi beberapa sifat tambahan diluar persyaratan dasar dari masalah secara umum. Pada CSP, tahap/state didefinisikan sebaga nilai dari himpunan variabel dan tahap goal mewakili himpunan pembatas/constrain dimana nilai-nilai yang ada harus berpatokan pada pembatas ini.
Sebagai contoh, pada n-queen problem, dapat dilihat sebagai CSP dimana variabel adalah lokasi dari ratu-ratu yang ada (sebanyak n ratu), dan pembatas menegaskan bahwa tidak boleh ada 2 ratu yang berada pada kolom, baris, atau posisi diagonal yang sama. Solusi dari CSP ini adalah nilai dari variabel yang memenuhi batasan yang ada, dan juga tujuan yang dimaksud tercapai.
Contoh masalah lain yang dapat dilihat dengan sudut pandang CSP adalah teka-teki silang, kriptografi, dan map coloring.

2. Proporsitional Logic umumnya kita kenal sebagai logika matematika. Proporsitional Logic membahas mengenai hubungan dari 2 atau lebih pernyataan dalam kata-kata, namun tetap berdasarkan asas-asas logika yang jelas.
Komponen-komponen dari proporsitional logic antara lain syntax, semantic, dan evaluation. Syntax membahas mengenai istilah-istilah yang digunakan, semantic adalah aturan-aturan penggunaannya, dan evaluasi mengenai hasil akhir.

Penerapan dari proporsitional logic salah satunya adalah untuk menentukan apakah sebuah pernyataan yang merupakan hasil hubungan dari 2 atau lebih pernyataan bernilai valid terhadap pernyataan-pernyataan tersebut dengan menggunakan tabel kebenaran.

Sumber :
http://web.cs.swarthmore.edu/~meeden/cs63/f11/russell-norvig-ch5.pdf
http://www.cs.sfu.ca/CourseCentral/310/oschulte/mychapter5.pdf
http://www.ics.uci.edu/~smyth/courses/cs271/topic6_adversarial_search.ppt
http://logic.stanford.edu/classes/cs157/2007/notes/chap02.html
http://www.iep.utm.edu/prop-log/#SH3a
Artificial Intelligence – A Modern Approach – Russel, Peter And Norvig, Stuart

Welcome to Binusian blog.
This is the first post of any blog.binusian.org member blog. Edit or delete it, then start blogging!
Happy Blogging 🙂