ARTIFICIAL INTELLIGENCE

Andri Pranolo

W : apranolo.tif.uad.ac.id

M : 081392554050

E : andri.pranolo@tif.uad.ac.id

Informatics Engineering, Universitas Ahmad Dahlan, Yogyakarta - 2014

Team teaching: Sri Winiarti, Andri Pranolo, dan Anna Hendri SJ

POKOK BAHASAN 1. Masalah, Ruang Keadaan, dan

Pencarian

2. Refresentasi Pengetahuan

3. Metode Inferensi

4. Penalaran (Penentuan Ketidakpastian

dan Keyakinan)

5. Sistem Pakar

6. Pengolahan Bahasa Alami

7. Jaringan Syaraf Tiruan

8. Logika Fuzzy

9. Algoritma Genetika

PERTEMUAN 4, 25 SEPTEMBER 2014

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

seorang agen bisa

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: 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: 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: 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: menggunakan logika formal. Digunakan pada PROLOG

Representasi Prosedural: menggambarkan prosedur sebagai kumpulan instruksi untuk memecahkan masalah. Digunakan dalam pemrograman: IF-THEN

Representasi Network: menggambarkan pengetahuan sebagai Graph dan Tree

Representasi 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: Deduktif (umum-khusus)

Induktif (khusus-umum)

Logika (disebut logika komputasional): 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

T T T

T F F

F T F

F F F

P Q P Q

T T T

T F F

F T T

F F T

P Q P OR Q

T T T

T F T

F T T

F F F

P Q P Q

T T T

T F F

F T F

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 Gejala pendukung Tanda

G1 G2 G3 G4 G5 G6 G7 G8 G9 G10 T1 T2 T3

1. Embun tepung

2. Damping off

3. Embun Jelaga

4. Karat puru

5. Antraknosa

6. Busuk akar x x x x x x

7. Madu x x x x X 8. Kanker

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. Kondisi input kondisi yang harus dipenuhi

2. Track variasi yang mungkin terjadi

3. Prop berisi objek-objek pendukung

4. Role peran yang dimainkan oleh seseorang

5. Scene adegan yang dimainkan

6. 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

Pengawas menyiapkan lembar soal

Pengawas menyiapkan lembar jawab

Pengawas menyiapkan lembar 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 mengerjakan soal ujian

Mahasiswa menuliskan identitas di lembar jawab

Mahasiswa menandatangai lembar jawab

Mahasiswa mengerjakan soal

Mahasiswa 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 merasa senang dan lega

Mahasiswa merasa kecewa

Mahasiswa pusing

Mahasiswa memaki – maki

Mahasiswa sangat bersyukur

SCHEMAS: SCRIPTS

5.9. ATURAN PRODUKSI

Paling populer (sejak tahun 1943-Post, 1957-Chomsky, 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