Algoritma Learning - April Fatmasari-Catatan Mom Blogger

Ini merupakan penugasan kelompok yang pertama untuk machine learning dan penugasan pertama yang ditolak. Sebagai pembelajaran dari dosen yang mengatakan, "Selesaikanlah sebelum deadline waktu pengumpulan. TEPAT WAKTU! Terlambat beberapa detik pun, saya tidak akan terima."

***

Sejauh ini, learning memiliki makna memilih representasi terbaik, misalkan decision tree yang terbaik atau nilai untuk parameter dalam NN yang paling baik. atau memprediksi nilai target feature dari sebuah kasus yang baru dari database kasus" sebelumnya. Namun ada ide lain yang berbeda tentang learning. yaitu learning sebagai proses menentukan formula dari hipotesis yang konsisten dengan  training example. dibandingkan untuk memilih sebuah hipotesis, tujuan proses ini lebih pada menemukan hipotesis-hipotesis yang konsisten. proses investigasi ini akan menjelaskan peran dari bias dan menyediakan mekanisme analisis teoritis mengenai masalah learning.

Pendekatan yang dapat dilakukan adalah menggunakan algoritma candidate  elimination. algoritma ini bekerja dengan menjaga agar representasi sekumpulan hipotesis  konsisten dengan training examples.

Algoritma learning candidate-elimination mengkomputasi version space (subset dari semua  hipotesis yang konsisten dengan semua training example yang diamati). 

Dimulai dengan menginisialisasi version space dalam set G yang merupakan hipotesis paling umum (general)

Go ß {(?, ?, ?, ?, ?, ?)}

Dan menginisialisasinya dalam set S yang merupakan hipotesis paling spesifik

So ß {(ᴓ, ᴓ, ᴓ, ᴓ, ᴓ, ᴓ)}

Dua batasan ini, G dan S, memberikan batasan diantara space hipotesis, karena setiap hipotesis dalam H lebih general dari  So dan lebih spesifik dari Go. Setiap training example dicek, S dan G digeneralisasi dan dispesifikasi dan sebaliknya untuk mengeliminasi hipotesis yang tidak konsisten pada training example yang baru. Setelah semua training example diproses, didapatkan hipotesis yang konsisten.

Algoritma CE telah diterapan pada permasalahan learning regularities dalam spektrokopi kimia masal (MItchel 1979) dan learning control rules untuk heuristic search (Mitchell et al 1983). namun keterbatasan dari CE (dan find-S juga) adalah kinerjanya  buruk ketika  diberikan data training yang ada noisenya.

Apa yang terjadi ketika training data mengendung eror? misalkan training example yang kedua salah dalam representasinya, seharusnya positive example, bukan negative example. maka lagoritma ini akan menghapus correct target concept dari version space.  dikarenakan ia akan meremove setiap hipotesis yang tidak konsisten dengan dengan  training example, ia akan mengeliminasi true target concept dari version space segera setelah negative example yang salah ini masuk. ketika diberi tambahan training data maka ka terdeteksi adanya ketidakkonsistenan dengan terjadinya konvergensi pada S dan G menghasilkan version space kosong. adanya empty space mngindikasikan bahwa tidak ada hipotesis dalam H yang konsisten dengan semua training example yang diobservasi.

>> Seperti apa training example yang di-request learner selanjutnya?

Sampai di poin ini, kita dapat mengasumsikan bahwa training examples yang diberikan learner oleh beberapa external teacher. Anggaplah learner diperbolehkan untuk memimpin experiment yang memilih instance selanjutnya, kemudian mendapatkan klasifikasi yang benar untuk instance ini dari external oracle.

Skenario ini meliputi situasi yang seorang learner dapat melakukan percobaan dalam alam (seperti membangun jembatan baru dan mengikuti alam untuk mengklasifikasikan apakah jembatan tersebut stabil atau tidak), atau seorang guru yang menyediakan klasifikasi yang benar (seperti mengusulkan jembatan baru dan mengikuti seorang guru yang menyarankan apakah itu akan stabil atau tidak). Kita menggunakan istilah query untuk merujuk beberapa instance dibangun oleh learner yang diklasifikasikan oleh external oracle.

Pertimbangkan lagi version space dipelajari dari empat training example dari konsep Enjoy Sport dan diilustrasikan pada gambar 1.1.

Gambar 1.1

Oleh karena itu, bagaimana query yang baik bagi learner sesuai pada poin di atas? Apakah strategi umum query yang baik? Learner seharusnya dapat memebedakan anternatif hipotesis dalam version space. Oleh karena itu , learner harus memilih sebuah instance yang akan diklasifikasikan positif dari beberapa hipotesis tetapi negatif untuk yang lain.

                Kita perhatikan bahwa instance diatas memenuhi tiga dari enam hipotesis dalam version space yang sekarang. Jika trainer menngklsifikasikan instance ini sebagai example positive, S dalam version space dapat digeneralisasikan. Namun jika trainer mengindikasikan instance ini negative, maka G akan dispesifikkan atau dispesialisasikan. Dengan demikian,  learner berhasil mempelajari lebih banyak mengenai true identity target konsep, mengurangi  version space menjadi setengahnya.

Referensi:

Artificial Intelligence, 2010, David Poole and Alan Mackworth

Tom Mitchell, 1997, Machine Learning