ARTIFICIAL INTELLIGENCE Team teaching: Sri Winiarti, Andri Pranolo, dan Anna Hendri SJ
Andri Pranolo W : apranolo.tif.uad.ac.id M : 081392554050 E :
[email protected] Informatics Engineering, Universitas Ahmad Dahlan, Yogyakarta - 2015
POKOK BAHASAN 1.
2. 3. 4.
5. 6. 7. 8. 9.
Masalah, Ruang Keadaan, dan Pencarian Refresentasi Pengetahuan Metode Inferensi Penalaran (Penentuan Ketidakpastian dan Keyakinan) Sistem Pakar Pengolahan Bahasa Alami Jaringan Syaraf Tiruan Logika Fuzzy Algoritma Genetika
15 OKTOBER 2015 Pokok Bahasan : Representasi Pengetahuan Outcome: Mahasiswa memahami representasi pengetahuan yang umum digunakan dalam Kecerdasan Buatan Referensi: [1] Kusumadewi, S. Artificial Intelligence: Teknik dan Aplikasinya, Graha Ilmu, Yogyakarta, 2003 [2] Komputer Masa Depan, Pengenalan Artificial Intelligence, Suparman & Marlan, Andi Offset, 2007 [3] Konsep Kecerdasan Buatan: Anita Desiani & Muhammad Arhami, Andi Offset, 2006 [4] Artificial Intelligence, Searching, Reasoning, Planning, and Learning, Suyanto, Penerbit Informatika, 2007 [5] Bahan-bahan dari Internet
1. REPRESENTASI
Representasi secara umum: Deskripsi Dunia ideal (tidak hanya sekedar simbolik) Simbolis Representasi internal: memerlukan bahasa simbol yang umum, di mana kita dapat mengekspresikan dan memanipulasi proposisi tentang dunia Pilihan bagus untuk representasi simbolik dengan bahasa logika Namun, beberapa persiapan harus dibuat ...
2. PENGETAHUAN
Definisi umum : fakta atau kondisi sesuatu atau keadaan yang timbul karena suatu pengalaman.
Diklasifikasikan menjadi 3 Procedural Knowledge Declarative Knowledge Tacit Knowledge
2.1. Procedural knowledge : Bagaimana melakukan sesuatu Bagaimana mendidihkan air dalam mangkok Bagaimana memasak mie instan Bagaimana menjalankan mobil 2.2. Declarative knowledge : Mengetahui sesuatu itu benar atau salah Fakultas Teknologi Industri mempunyai 4 program studi. Dekan Fakultas Teknologi Informasi adalah Kartika Firdausy, S.T, M.T. 2.3. Tacit knowledge : Tidak dapat diungkapkan dengan bahasa Bagaimana kita menggerakkan tangan Bagaimana memejamkan mata
3. REPRESENTASI PENGETAHUAN
Metode yang digunakan untuk mengodekan pengetahuan dalam sebuah sistem cerdas (ex. sistem pakar) Dimaksudkan untuk Menangkap sifat-sifat penting problema Membuat informasi itu dapat diakses oleh prosedur pemecahan problema Karakteristik representasi pengetahuan Dapat diprogram dengan bahasa komputer dan disimpan dalam memori Fakta dan pengetahuan lain yang terkandung di dalamnya dapat digunakan untuk melakukan penalaran
Bagaimana merepresentasikan pengetahuan ke dalam basis pengetahuan dan menguji kebenaran penalaran Cara-cara lama: List, digunakan pada LISP Predicate Calculus, digunakan pada Prolog Tree, untuk heuristic search Harus terdiri dari struktur data dan prosedur untuk penafsiran Hal yang berhubungan dengan RP: Object pengetahuan itu sendiri Event: kejadian-kejadian dalam dunia nyata dan hubungannya Performa: bagaimana melakukan suatu tugas tertentu Meta knowledge: pengetahuan tentang pengetahuan yang direpresentasikan
4. PENGGUNAAN PENGETAHUAN
Acuisition: Acuisition mengintegrasikan informasi baru kedalam pengetahuan sistem. Dua level: Menyusun fakta ke dalam database Pembuatan fungsi untuk mengintegrasikannya dengan cara “belajar dan mengadaptasikannya” terlebih dahulu Retrieval: Retrieval mengingat kembali, menyusun ulang pengetahuan berdasarkan hubungan pengetahuan terhadap masalah Linking: mengekstrak informasi baru tersebut Lumping: mengelompokkan hasil ekstraksi pengetahuan baru tersebut kedalam struktur yang lebih besar seperti yang dibutuhkan dalam menyelesaikan masalah Reasoning: Reasoning pengetahuan digunakan untuk menalar suatu permasalahan Formal reasoning: menggunakan logika proporsional Procedural reasoning: menggunakan aturan produksi ( IF-THEN) Analogical reasoning: sangat sulit
5. MODEL/TEKNIK REPRESENTASI PENGETAHUAN
Pengetahuan dapat direpresentasikan dalam bentuk yang sederhana atau kompleks, tergantung dari masalahnya. (Schnupp, 1989) Beberapa model/teknik representasi pengetahuan 1. Logika (logic) 2. List 3. Jaringan semantik (semantic nets) 4. Bingkai (frame) 5. Tabel Keputusan (decision table) 6. Graph/Pohon Keputusan (decision tree) 7. Kaidah/aturan produksi (production rule) 8. Naskah (script)
Klasifikasi kategori representasi pengatahuan menurut Mylopoulus dan Levesque: Representasi Logika: Logika menggunakan logika formal. Digunakan pada PROLOG Representasi Prosedural: Prosedural menggambarkan prosedur sebagai kumpulan instruksi untuk memecahkan masalah. Digunakan dalam pemrograman: IF-THEN Representasi Network: Network menggambarkan pengetahuan sebagai Graph dan Tree Representasi Terstruktur: Terstruktur memperluas konsep Representsi Network dengan membuat node-nodenya menjadi struktur data yang kompleks. Contoh: script, frame, dan object
MODEL/TEKNIK REPRESENTASI PENGETAHUAN
5.1. LOGIKA
Adalah representasi pengetahuan yang paling tua. Proses menarik kesimpulan dari fakta yang sudah ada Input: premis-premis dan Ouput: kesimpulan Terdiri dari: sintaks (simbol), semantik (fakta), dan proses pengambilan keputusan (inferensi) Proses penalaran:
Logika (disebut logika komputasional):
Deduktif (umum-khusus) Induktif (khusus-umum) Logika Preposisi: and, or, not, implikasi, dan ekuivalensi Logika Predikat: representasi fakta dalam bentuk well formed formula
Lihat dibuku Artificial Intelligence (Sri Kusuma Dewi)
14
Suatu pengkajian ilmiah tentang serangkaian penalaran, sistem kaidah, dan prosedur yang membantu penalaran. Komputer harus dapat menggunakan proses penalaran deduktif dan induktif ke dalam bentuk yang sesuai dengan manipulasi komputer, yaitu logika simbolik atau matematika
15
5.1.1 PENALARAN DEDUKTIF
Bergerak dari penalaran umum menuju ke konklusi khusus Atau pernyataan premis dan inferensi Premis Mayor Premis Minor Konklusi Contoh
Premis mayor : Jika hujan turun saya tidak akan kuliah Premis minor : Pagi ini hujan turun Konklusi : Oleh karena itu pagi ini saya tidak akan kuliah
16
5.1.2 PENALARAN INDUKTIF Bergerak dari masalah khusus ke masalah umum Menggunakan sejumlah fakta atau premis yang mantap untuk menarik kesimpulan umum Contoh Premis 1 : Aljabar adalah pelajaran yang sulit Premis 2 : Geometri adalah pelajaran yang sulit Premis 3 : Kalkulus adalah pelajaran yang sulit Konklusi : Matematika adalah pelajaran yang sulit Konklusi tidak selalu mutlak, dapat berubah jika ditemukan fakta baru Contoh
Premis 4 : AI adalah pelajaran yang sulit
5.1.3 LOGIC: PROPOSITION LOGIC
P
Q
P AND Q
P
Q
P OR Q
T
T
T
T
T
T
T
F
F
T
F
T
F
T
F
F
T
T
F
F
F
F
F
F
P
Q
P → Q
P
Q
P⇔Q
T
T
T
T
T
T
T
F
F
T
F
F
F
T
T
F
T
F
F
F
T
F
F
T
18
5.2. LIST
Struktur sederhana untuk representasi pengetahuan Daftar dari rangkaian materi yang terkait List digunakan untuk objek yang dikelompokkan, dikategorikan atau digabungkan
19
5.3. TREE / POHON
Struktur sederhana untuk representasi pengetahuan Merupakan struktur grafik hirarki
20
5.4. JARINGAN SEMANTIK
Struktur sederhana untuk representasi pengetahuan grafis yang menunjukkan hubungan antar berbagai objek
21
5.5. FRAME
Frame kumpulan pengetahuan tentang suatu objek tertentu, peristiwa, lokasi, situasi, berdasarkan pengalaman
Frame memiliki slot yang menggambarkan rincian (atribut) dan karakteristik objek.
Hirarki Frame susunan hirarki dari frame mengijinkan pewarisan frame
22
HIRARKI FRAME
23
HIRARKI FRAME
24
5.6 TABEL KEPUTUSAN (DECISION TABLE)
Tabel keputusan dalam format tabel Tabel dibagi 2 bagian pertama untuk atribut & bagian kedua untuk nilai & kesimpulan
25
5.7. POHON KEPUTUSAN (DECISION TREE)
Pohon keputusan mudah dikonversi ke dalam bentuk aturan (rule)
Contoh : Gejala Utama : Daun Menguning (GU1)
No
Penyakit
1. 2.
Embun tepung
3. 4. 5. 6. 7. 8.
Embun Jelaga Karat puru Antraknosa Busuk akar Madu Kanker
G1
G2
G3
Gejala pendukung G4 G5 G6 G7
G8
G9
G10
T1
x x
x
Tanda T2
T3
x x
x X
Damping off
x x
x x
Kaidah 1. IF daun menguning AND daun pucat AND daun rontok AND layu AND terdapat tubuh buah AND terdapat miselium AND terdapat spora THEN busuk akar Kaidah 2. IF daun menguning AND daun pucat AND daun rontok AND layu AND terdapat miselium AND terdapat spora THEN madu
5.8. SCRIPT
Mirip dengan frame, merepresentasikan pengetahuan berdasarkan pengalaman-pengalaman Frame menggambarkan obyek, sedangkan script menggambarkan urutan peristiwa Elemen script:
Kondisi input: start, awal Track: variasi yang mungkin terjadi Prop: obyek pendukung Role: peran yang dimainkan oleh suatu obyek Scence: adegan yang terjadi Hasil (result): kondisi akhir yang terjadi
28
NASKAH (SCRIPT)
Naskah sama dengan frame, bedanya menggambarkan urutan peristiwa
Elemen script meliputi : 1. 2. 3. 4. 5. 6.
Kondisi input kondisi yang harus dipenuhi Track variasi yang mungkin terjadi Prop berisi objek-objek pendukung Role peran yang dimainkan oleh seseorang Scene adegan yang dimainkan Hasil kondisi yang ada setelah urutan peristiwa dalam script terjadi.
29
CONTOH NASKAH (SCRIPT)
Berikut ini adalah contoh script kejadian yang ada di “Ujian Akhir” Jalur (track) : ujian tertulis matakuliah Kecerdasan Buatan Role (peran) : mahasiswa, pengawas Prop (pendukung) : lembar soal, lembar jawab, presensi, pena, dll Kondisi input : mahasiswa terdaftar untuk mengikuti ujian
Adegan (scene) -1 : Persiapan Pengawas menyiapkan lembar Pengawas menyiapkan lembar Pengawas menyiapkan lembar
pengawas soal jawab presensi
Adegan-2 : Mahasiswa masuk ruangan Pengawas mempersilahkan mahasiswa masuk Pengawas membagikan lembar soal Pengawas membagikan lembar jawab Pengawas memimpin doa
30
Adegan – 3 : Mahasiswa Mahasiswa Mahasiswa Mahasiswa
Mahasiswa mengerjakan soal ujian menuliskan identitas di lembar jawab menandatangai lembar jawab mengerjakan soal mengecek jawaban
Adegan – 4 : Mahasiswa telah selesai ujian Pengawas mempersilahkan mahasiswa keluar ruangan Mahasiswa mengumpulkan kembali lembar jawab Mahasiswa keluar ruangan
31
Adegan – 5 : Mahasiswa mengemasi lembar jawab Pengawas mengurutkan lembar jawab Pengawas mengecek lembar jawab dan presensi Pengawas meninggalkan ruangan
Hasil : Mahasiswa Mahasiswa Mahasiswa Mahasiswa Mahasiswa
merasa merasa pusing memaki sangat
senang dan lega kecewa – maki bersyukur
SCHEMAS: SCRIPTS
5.9. ATURAN PRODUKSI
Paling populer (sejak tahun 1943-Post, 1957Chomsky, 1972-Alan Newell) Terdiri dari antecedent/premis/situasi dan konsekuen/kesimpulan/tindakan Digambarkan dalam IF-THEN rules Digunakan pada Sistem Pakar Contoh:
IF temp > 30 C THEN hidupkan AC IF permintaan meningkat AND persediaan menipis THEN pemesanan barang IF pelamar <= 25 OR lulusan komputer THEN bisa diterima menjadi pegawai
Memiliki 3 elemen: Global
Database: mulai dari matriks sederhana, list, atau basis data untuk menyimpan aturan produksi dan memory kerja Aturan Produksi: berisi aturan IF-THEN Sistem Kontrol: program pengkontrol urutan mana aturan kaidah-kaidah produksi yang harus dipilih dan menyelesaikan konflik pada saat pemilihan
35
2 metode penalaran yang menggunakan aturan : Forward Reasoning (penalaran maju) Pelacakan dimulai dari keadaan awal (informasi atau fakta yang ada) dan kemudian dicoba untuk mencocokkan dengan tujuan yang diharapkan Gunakan jika jumlah keadaan awal lebih kecil daripada tujuan & kejadian itu berupa fakta baru Backward Reasoning (Penalaran mundur) Penalaran dimulai dari tujuan atau hipotesa, baru dicocokkan dengan keadaan awal atau fakta-fakta yang ada. Jika jumlah keadaan awal lebih banyak daripada tujuan Jika kejadian itu berupa query
36
CONTOH FORWARD REASONING
R1 : IF suku bunga turun THEN harga obligasi naik R2 : IF suku bunga naik THEN harga obligasi turun R3 : IF suku bunga tidak berubah THEN harga obligasi tidak berubah R4 : IF dolar naik THEN suku bunga turun R5 : IF dolar turun THEN suku bunga naik R6 : IF harga obligasi turun THEN beli obligasi Apabila diketahui bahwa dolar turun, apa keputusan yang diambil, apakah akan membeli obligasi atau tidak
Forward Reasoning :
Dari fakta dolar turun, berdasarkan Rule 5, diperoleh konklusi suku bunga naik. Dari Rule 2, suku bunga naik menyebabkan harga obligasi turun. Dengan Rule 6, jika harga obligasi turun, maka kesimpulan yang diambil adalah membeli obligasi.
37
CONTOH BACKWARD REASONING
R1 : IF suku bunga turun THEN harga obligasi naik R2 : IF suku bunga naik THEN harga obligasi turun R3 : IF suku bunga tidak berubah THEN harga obligasi tidak berubah R4 : IF dolar naik THEN suku bunga turun R5 : IF dolar turun THEN suku bunga naik R6 : IF harga obligasi turun THEN beli obligasi
Apabila diketahui bahwa dolar turun, apa keputusan yang diambil, apakah akan membeli obligasi atau tidak
Backward Reasoning :
Dari solusi yaitu membeli obligasi dengan menggunakan Rule 6 diperoleh anteseden harga obligasi turun Dari Rule 2 dibuktikan harga obligasi turun bernilai benar jika suku bunga naik bernilai benar . Dari Rule 5 suku bunga naik memang bernilai benar karena diketahui fakta dolar turun.
RESOLUSI KONFLIK Urutkan aturan berdasarkan prioritas, kemudian pilih aturan pertama yang memiliki prioritas tertinggi Pilih aturan yang paling strict (ketat) Pilih aturan yang paling sering digunakan Pilih aturan yang paling akhir dimasukkan di dalam sistem Pilih semua aturan yang memungkinkan
METODE PENALARAN Forward reasoning (data driven): dimulai dari keadaan awal (dari fakta), kemudian menuju ke arah kesimpulan / tujuan Backward reasoning (goal driven): dimulai dari tujuan / hipotesa baru dicocokkan dengan keadaan awal / fakta-fakta
ALASAN PEMILIHAN METODE
Tergantung dari banyaknya keadaan awal dan tujuan. Jika
jml awal lebih kecil dari tujuan gunakan penalaran maju. Jika jml tujuan lebih banyak dari awal, gunakan penalaran mundur
