People Innovation Excellence

Learning: Candidate Elimination

Version Space dapat didefinisikan sebagai kumpulan hipotesa yang valid dari sebuah algoritma.

ce - rini 1

Di dalam concept space, version space direpresentasikan menjadi kumpulan set G (General)  dan S (Spesific), dimana G mengandung deskripsi yang paling general (umum) sedangkan S mengandung deskripsi yang paling spesifik, dan deskripsi tersebut konsisten dengan data pelatihan yang ada.

Data pelatihan yang positif akan membuat kelompok data S menjadi lebih umum sedangkan data pelatihan negative akan membuat kelompok data G menjadi lebih spesifik. Apabila didapatkan kelompok data S dan G yang konvergen, maka dapat diperoleh sebuah deskripsi konsep yang tunggal (single concept). Algoritma yang dapat digunakan untuk mencapai tujuan ini di dalam version space dikenal sebagai algoritma Candidate Elimination (CE).

Di dalam algoritma CE, diterapkan 2 algoritma mendasar:

  1. Specific to General Search Algorithm
    Algoritma ini bertujuan untuk men-general-kan kelompok data yang sangat spesifik. Dalam pseudocode, algoritma ini dapat didefinisikan sebagai:
    ce - rini 5
  2. General to Specific Search Algorithm

    Algoritma ini bertujuan untuk menspesifikan kelompok data yang sangat general. Dalam pseudocode, algoritma ini dapat didefinisikan sebagai:
    ce - rini 6Dengan menggabungkan kedua algoritma tersebut, maka algoritma dari CE dapat didefinisikan dengan:

    Diketahui:
    Representasi sebuah bahasa dan kumpulan data pelatihan positif dan negatif

    Carilah:
    Deskripsi konsep yang konsisten dengan semua data pelatihan positif dan tidak ada yang konsisten dengan data pelatihan negative

    Langkah-langkah:

    1. Inisialisasikan G agar mengandung 1 elemen, yakni deskripsi null untuk semua fitur yang direpresentasikan dalam variabel
    2. Inisialisasikan S agar mengandung 1 elemen, data pelatihan positif pertama
    3. Terimalah data pelatihan baru, dimana:
      1. Jika data positif :
        • Hapus semua member dari G yang tidak sesuai data pelatihan positif
        • Untuk setiap S, jika S tidak sesuai dengan data positif, maka gantikan S dengan generalisasi yang paling spesifik yang sesuai dengan data positif
      2. Jika data negative
        • Hapus semua member S yang sesuai dengan data pelatihan negative
        • Untuk setiap G yang sesuai dengan data negative, maka gantikan G dengan spesialisasi yang paling umum yang tidak sesuai dengan data negatif
    4. Jika S dan G pada akhirnya mencapai kondisi singleton, dan sama, maka selesai. Bila tidak sama, maka kemungkinan ada ketidakkonsistenan pada data pelatihan yang ada.

    Contoh penerapannya dalam dilihat dalam kasus berikut ini:

    Diketahui data pelatihan, di bawah ini, carilah konsepnya:

    ce - rini 3ce - rini 2
    ce - rini 7

    Dengan demikian didapatkan konsep berupa: “Japan, Economy” car.

     References

    Stuart Russell, Peter Norvig,. 2010. Artificial intelligence : a modern approach. PE. New Jersey. ISBN:9780132071482, Chapter 19


Published at : Updated

Periksa Browser Anda

Check Your Browser

Situs ini tidak lagi mendukung penggunaan browser dengan teknologi tertinggal.

Apabila Anda melihat pesan ini, berarti Anda masih menggunakan browser Internet Explorer seri 8 / 7 / 6 / ...

Sebagai informasi, browser yang anda gunakan ini tidaklah aman dan tidak dapat menampilkan teknologi CSS terakhir yang dapat membuat sebuah situs tampil lebih baik. Bahkan Microsoft sebagai pembuatnya, telah merekomendasikan agar menggunakan browser yang lebih modern.

Untuk tampilan yang lebih baik, gunakan salah satu browser berikut. Download dan Install, seluruhnya gratis untuk digunakan.

We're Moving Forward.

This Site Is No Longer Supporting Out-of Date Browser.

If you are viewing this message, it means that you are currently using Internet Explorer 8 / 7 / 6 / below to access this site. FYI, it is unsafe and unable to render the latest CSS improvements. Even Microsoft, its creator, wants you to install more modern browser.

Best viewed with one of these browser instead. It is totally free.

  1. Google Chrome
  2. Mozilla Firefox
  3. Opera
  4. Internet Explorer 9
Close