USPPROLOG

SAIL

- Predikat Kalkulus

- Program Simbolik

- Game

SEDERHANA

- Expert System

- Natural Language

- Planning Robotik

- Frames

TERSTRUKTUR

REPRESENTASI

STRATEGIKONTROL

FAKTA KAIDAH

SISTEMPRODUKSI

- Breath Search- Deep Search- Matching- Hill Climbing- Heuristics- Best first search or/graphs- Mean and Analysis- Minimax- Alpha Beta

PROBLEMREAL

PROBLEMA.I

Teknik Pemecahan Persoalan dengan Artificial Intelligence

2 8 3

1 6 4

7 5

1 2 3

8 4

7 6 5

Start Goal

Kelas Persoalan: Ignorable (mis pembuktian teorema) Recoverable (mis teja-teki-8) Irrecoverable (mis catur)

2 3

1 8 4

7 6 5

1 2 3

8 4

7 6 5

Initial State Goal State

2 3

1 84 3

7 6 5

2 8 3

1 4

7 6 5

2 3

1 8 4

7 6 5

(A) (B) (C)

Heuristic h1 = number of mismatched tiles h2 = sum of the (horizontal and vertical) disatancer of mismatched tiles h1(A) = 2, h1(B) = 3, h1(C) = 4 h2(A) = 2, h2(B) = 3, h2(C) = 4 The state A is the one closest to the goal.

4 liter 3 liter Bagaimana mendapatkan air sebanyak 2 liter pada bak 4 liter?

Pengisian Bak

Kaidah: 1. (X, Y | X<4) (4, Y) 2. (X, Y | Y<3) (X, 3) 3. (X, Y | X>0) (X – D, Y) 4. (X, Y | Y>0) (X, Y – D) 5. (X, Y | X>0) (0, Y) 6. (X, Y | Y<0) (X, 0) 7. (X, Y | X + Y> = 4 Y>0) (4, Y – (4 – x)) 8. (X, Y | X + Y> = 3 Y>0) (X – (3 – Y), 3) 9. (X, Y | X + Y< = 4 Y>0) (X + Y,0) 10. (X, Y | X + Y< = 3 X>0) (0, X + Y)

Mendefinisikan persoalan dalam ruang keadaan Permainan catur: Kaidah (Rule) : Bidak Putih (kolom f, baris 2) Kotak (kolom f, baris 3) kosong Pindahkan bidak dari kotak (kolom f,

baris 2) ke kotak (kolom f, baris 4) Kotak (kolom f, baris 4) kosong State Space:

- Definisi formal - Definisi proses penyelesaian persoalan

Forward search

Backward search

Initial states Goal states

Bidirectional Search

C

A B

ON(C, A)

B

C

A

ON(B, C) ON(A, B)

Non Decomposable

On (B, C) and on (A, B)

On (A, B)

Clear (A) On (A, B)

On (A, B)Clear (A)

On (B, C)

On (B, C)

Put B on C

Move Ato table

Put A on B

Operator 1. CLEAR (X) ON (X, Table) : Ambil X dan letakkan di atas meja 2. CLEAR (X) AND CLEAR (Y) ON (X, Y) : Letakkan X di atas Y Apakah langkah solusi dapat diabaikan/dibatalkan?

Karakteristik AI: - Symbolic Processing - Heuristik - Representasi Knowledge - Data yang tidak lengkap - Deduktif dan induktif Bahasa Pemrograman AI - Struktur Data + Algoritma = Program - Knowledge Base + Inference = System

1 4

8 2 3

7 6 5

1 2 3

8 4

7 6 5

Initial State Goal State

1. Representasikan search space dengan a. Tree b. Graph

2. Terapkan a. Depth first search b. Breadth first seach

Pada tree dan graph dan amati perubahan pada daftar “open” dan/atau “closed”

(0, 0)

(4, 0) (0, 3)

(1, 3) (4, 3)(0, 0)(4, 3) (0, 0) (3, 0)

Sistem Produksi Menstrukturkan program AI untuk mendeskripsikan proses pelacakan Sejumlah kaidah Basis data Control strategy

dxxxxx 222 cossin3

dxx2

3

3x

dxx3

2

3 2x

dxxx 22 cossin

dxxx 22 cos)cos1(

dxx2cos dxx4cos

dxx3

dxx)2cos1(21

dx121 dxx2cos

21

x21 x2sin

41

Karakteristik Persoalan 1. Apakah persoalan dapat dipilah-pilahkan (decomposable) ke dalam sub-sub

persoalan yang independen?

Bak 4 Liter Bak 3 Liter Kaidah yang diterapkan

0 0 2

0 3 9

3 0 2

3 3 7

4 2 5

0 2 9

2 0

Langkah membuat deskripsi formal:

1. Definisikan State Space (konfigurasi yang mungkin dari objek-objek yang relevan)

2. Definisikan Initial State 3. Definisikan Goal State 4. Tentukan kaidah/operator

KONTROL STRATEGI

Arah - Forward : dimulai dari state awal - Backward: dimulai dari state sasaran Kriteria - state awal < state sasaran Forward dan sebaliknya - Faktor percabangan (jumlah rata-rata simpul yang dapat dicapai

secara langsung dari sebuah simpul). Arah: menuju faktor percabangan yang lebih kecil

- Proses penalaran pemakai

Kontrol Strategi - Pelacakan (searching) - Dekomposisi - Contrtol of Problem Solving - Chaining

PELACAKAN Optimal

Sistematis - Depth-first search (Vertical) - Breadth-first search (Horizontal)

Trial & Error

Heuristik - Hill Climbing - Best-First Search - Algoritma A - Algoritma A*

MINIMAX

..........

Pemilihan Teknik Inferensi harus mempertimbangkan:

Arah pelacakan Topologi proses pelacakan Representasi simpul Pemilihan kaidah (rule) yang dapat diterapkan Penggunaan fungsi heuristik

Arah Pelacakan

Forward o dimulai dari initial state o matching dengan pola kiri kaidah pola kanan membentuk

simpul anak

Backward o dimulai dari goal state o matching dengan pola kiri kaidah pola kiri membentuk

simpul induk

Faktor-faktor

initisl state > goal state backward dan sebaliknya Faktor percabangan (jumlah rata-rata simpul yang dapat dicapai

secara langsung dari sebuah simpul). Arah pelacakan menuju faktor percabangan yang kecil

Proses penalaran

(0, 0)

(4, 0) (0, 3)

(1, 3) (4, 3)(0, 0)(4, 3) (0, 0) (3, 0)

(0, 0)

(4, 0) (0, 3)

(1, 3) (4, 3) (3, 0)

Pohon

Grafik

BidirectionalTopologi pelcakan

pohon (tree) grafik

Initial States Procedures Goals

ControlStrategy

Hubungan antara Initial states, Procedures dan Goal dalamProses penelusuran

ControlStrategy

Operators

Data Base- Initial States- Goal- Current Status- Record of previous transactions

Basic search process

For chess, typically linear weighted sum of features EVAL(s) = w1f1(s) + w2f2(s) + … + wnfn(s) e.g., w1 = 9 with f1(s) = (number of white queens) – (number of black queens) etc.

Evaluation functions

Romania with step cost in km

Oradea

Zerind

Arad

Timisora

Lugoj

Mehadia

Dobreta

Craiova

Sibiu Fagaras

Rimnicu Vilcea

Pitesti

Giurgiu

BucharestUrziceni

Neamt

lasi

Vaslui

Hirsova

Eforie

120

71

15175

118

111

70

75

140

99

80

97

146

138101

211

85

90

87

92

142

98

86

Straight-line distance to Bucharest Arad 366 Bucharest 0 Craiova 160 Dobreta 242 Eforie 161 Fagaras 178 Giurgiu 77 Hirsova 151 Iasi 226 Lugoj 226 Mehadia 241 Neamt 234 Oradea 380 Pitesti 98 Rimnicu Vilcea 193 Sibiu 253 Timisoara 329 Urziceni 80 Vaslui 199 Zerind 374

Pemrograman Konvensional

Algoritma + struktur data = program Algoritmik Manipulas numeric / prosedur sekuensial

Pemrograman Artificial Intelligence

Knowledge base + inference = system Pemilihan alternatif Representasi & manipulasi simbolik Pemisahan mekanisme “knowledge” dengan “control strategy”

S

B CA D

E F G

H I J

K L

(9) (7) (8) (9)

(6) (5) (6)

(4) (3) (2)

(1) (0)

Goal

Hill Climbing

TRIAL & ERROR Metode paling sederhana Prosedur Pelacakan

1. Ambil state sebagai keadaam awal 2. While state keadaan sasaran do 3. Begin 4. Pilih operator yang dapat diterapkan pada state, dan diset sebagai operator 5. State : = operator (state) 6. End

Penjelasan:

Pada langkah 4, operator dipilih secara acak Pada langkah 5, operator yang dipilih diterapkan pada state membentuk

state baru Stokastik, tidak menjamin dicapainya keadaan sasaran Tidak memperlihatkan karakteristik ‘intelegensi’

S

A BC D

E F

H

G

R 1

I

R 2 R 3

R 4

R 2R 5

R 4

R 1 R 2

TRIAL & ERROR

Pelacakan Depth-First Search

Representasi: Diagram pohon atau grafik Simpul yang lebih dalam diperiksa terlebih dahulu Penelusuran

simpul-simpul pada suatu cabang sampai kedalaman yang ditentukan. Prosedur

1. Berikan simpul awal pada daftar open 2. Loop: if open = kosong then exit (fail) 3. n : = first (open) 4. if goal (n) then exit (success) 5. Remove (n, open) 6. Ekspansikan n, berikan semua simpul anak pada kepala open dan

bubuhkan pointer dari simpul anak ke n 7. Kembali ke Loop

Penjelasan: - Pada langkah 3, elemen pertama daftar open diambil - Ekspansi simpul n = pembangkitan simpul-simpul anak dari suatu simpul n

S

A B

C D E F

H G

Urutan pelacakan:S, A, C, D, B, E, H, G

Goal

Pelacakan Depth-First Search

Perubahan daftar ‘open’: (S) (A B) (C D B) (D B) (B) (E F) (H G F) (G F) Dengan diagram grafik:

5. Remove (n, open) Add (n, closed)

6. Ekspansikan n. Berikan pada kepala open semua simpul anak yang belum muncul pada open atau closed dan bubuhkan pointer ke n.

Pelacakan Breadth-First Search - Bersifat horizontal - Evaluasi dilakukan terhadap simpul-simpul pada suatu level sebelum

dilanjutkan pada level berikutnya Prosedur

1. Berikan simpul awal pada open 2. Loop: if open = kosong then exit (fail) 3. n : = first (open) 4. if goal (n) then exit (success) 5. Remove (n, open) 6. Add (n, closed) 7. Ekspansikan n. Berikan pada ekonr open semua simpul anak yang belum

muncul pada open atau closed dan bubuhkan pointer ke n. 8. Kembali ke Loop

Pelacakan untuk memperoleh Solusi Optimal Mencari jejak dengan ‘cost’ (biaya) minimum ‘Cost’ untuk penerapan operator diberikan

Prosedur Pelacakan

1. Berikan simpul awal S pada open, g’(s) = 0 2. Loop : if open = kosong then exit (fail) 3. n : = first (open) 4. if goal (n) then exit (success) 5. Remove (n, open) 6. Ekspansikan n, hitung g’(ni) untuk semua simpul anak ni dan bubuhkan pointer dari

ni ke n. Berikan semua simpul anak pada open dan urutkan mulai biaya terendahnya

7. Kembali ke Loop Penjelasan

Pada langkah 6, jika fungsi biaya dari simpul n ke ni didefinisikan sebagai C(n, ni), maka fungsi biaya dari simpul ni adalah : g’(ni) = g’(n) + C(n, ni)

G1 & G2 = Goal

S

A B

C D E F

H G1 I G2

1

1

1

4

4

2 2 3

3 2

Pelacakan untuk memperoleh Solusi Optimal

S

A B

C

E G 2

G 1 D

2 3

5

22

21

313

Urutan daftar ‘open’: (S(0)) (B(1)A(4)) (E(3)A(4)F(4)) (A(4)F(4)G1(6)H(7)) (F(4)C(5)G1(6)D(6)H(7)) (G2(5)C(5)G1(6)D(6)I(6)H(7)) Pada representasi grafik

(S(0)) (A(2)B(3)) (B(3)C(5)G1(7)) (C(4)D(6)G(7)) (G2(6)D(6)E(6)G1(7))

Pelacakan dengan Informasi Heuristik

Heuristik adalah kriteria, metoda, atau prinsip-prinsip untuk menentukan pilihan dari sejumlah alternatif mencapai sasaran dengan efektif

Mekanisme Backtracking = kembali ke state sebelumnya jika suatu solusi gagal diperoleh

Heuristik dipergunakan untuk mempersempit ruang pelacakan.

Hill Climbing Memilih simpul-simpul suatu cabang yang diperkirakan lebih dekat terhadap sasaran (nilai heuristik terkecil)

Mirip “depth-first search” Prosedur: 1. Ambil n sebagai simpul awal 2. Loop: if goal(n) then exit(success) 3. Ekspansikan n, hitung h(ni) untuk semua simpul ni dan ambil simpul dengan nilai heuristik terkecil next n

4. If h(n) < h(next n) then exit (fail) 5. n := next n 6. Kembali ke Loop

Hill climbing tidak dapat diterapkan pada persoalan yang memiliki puncak-puncak local.

A

C DB E

F G H

M

I J

K L

(15) (13) (14) (14)

(11) (10) (8)

(5) (6)

(4) (2)

Initial

O P

(1)

Goal

(3)

(0)

HILL CLIMBING

Langkah 1

A

Langkah 2

A

B C D(5) (1)(3)

Langkah 3

A

B C D(5)(3)

E F(4) (6)

Langkah 4

A

B C D(5)

E F(4) (6)E F(6) (5)

Langkah 5

A

B C D(5)

E F(6)E F(6) (5)

I J(2) (1)

Best-First Search Gabungan Breadth-first & Depth-first Pada setiap langkah dipilih simpul yang diperkirakan lebih dekat terhadap sasaran

dari semua simpul yang dibangkitkan (tetapi belum diekspansikan)

Depth-First Search

1. Berikan simpul awal pada open 2. Loop : if open = kosong then exit (fail) 3. n : = first (open) 4. If goal (n) then exit (success) 5. Remove (n, open) 6. Ekspansikan n, berikan semua simpul anak pada kepala open. Bubuhkan

pointer dari simpul anak ke n 7. Goto loop

Langkah 1

A

Langkah 2

A

B C D(5) (1)(3)

Langkah 3

A

B C D(5)(3)

E F(4) (6)

Langkah 4

A

B C D(5)

E F(4) (6)E F(6) (5)

Langkah 5

A

B C D(5)

E F(6)E F(6) (5)

I J(2) (1)

Best-First Search

Bagaimana perubahan pada daftar “Open” ?

A* - algorithm : S C J G7 Optimal Search : S C J G7 (without heuristic) h = 0

(but all the nodes other than goal G1 – G8 are expanded)

A* - algorithm: no nodes are expanded other than those lying on the optimum path

(7)S

A B C

G 2

F H ID E J K

G 1 G 3 G 4 G 6G 5 G 7 G 8

(5) (4) (2)

(3) (3) (3) (3) (3) (1) (2)

4 6

33

3 22

2 11

1

4 4 4 4 4 4 4 4 4 4 2 1 3 3

(7)S

A B

2 3

C D

3 3

E

1 2

(6) (6)

(5) (3) (5)

F H

4 3

I

2 3

(3) (3) (2) J

4

(3)

4

K

3 4

L

4 3

(2) (2)

24

M

33

G 1 G 2

2 2 2 2

(2)goal goal

A-algorithm Find optimum solution when the cost to the goal can be inferred Use knowledge about the problem

Open-list (S(7)) (A(8)B(9)) (D(8)B(9)C(10)) (B(9)C(10)H(10)I(10)) (D(7)C(10)E(10)H(10)I(10) (H(9)I(9)C(10)E(10)) (I(9)G1(10)C(10)E(10)L(11)) (G2(9)G1(10)C(10)E(10)L(11)) Solution : S B D I G2

B C D(8)

maxA

(3) (-2) min

Static evaluation function : [-10, 10]

win for opponent win for us

Minimax

One-ply search

B C D(-6)

max

A

(-4)(-2) min

GF HE KJI

(-2)

(9) (-6) (0) (0) (-2) (-4) (-3)

max

Two-ply Search

B C D

A

GF HE KJI

7

P QN O R SL M V WT U X Y

6 8 5 2 3 0 -2 6 2 5 8 9 2

A = maximizing player

Question : What move should he choose

Representasi simpul 1. Bagaimana objek individual & fakta direpresentasikan 2. Bagaimana menggabungkan objek individual untuk membentuk representasi

yang lengkap 3. Bagaimana mempresentasikan secara efisien sekuens state persoalan

1 & 2 knowledge representation 3 frame problem Matching

Dengan index Dengan variable Menyaring hasil matching

o Revolusi konflik: pemilihan kaidah pada proses matching Misal: Pada pengisian bak air

a. (0, 2) (2, 0) b. (x, 2) x > 0 ) (0, 2)

Informasi Heuristik

Teknik menerima solusi Mekanisme ‘back-tracking’ Mempersempit ruang pelacakan

n

A B

n1

S

C D E F

n2

n11 n12 n21 n22

max

max

min

n = M a x n o d e n i = c h i l d o f m a x n o d e , i = 1 – m n i j = c h i l d n o d e o f e a c h m a x n o d e , j = 1 – i m f = e v a l u a t i o n f u n c t i o n M A X : f ( n i) =

imax f ( n i)

M IN : f ( n i j) = j

min f ( n i j)

M A X : f ( n i j) = i

max {j

min f ( n i j) }

k = d e p t h o f t h e t r e e M A X s h o u l d s e l e c t i 1 s . t : f )(n

k21 i ii = 1i

max2i

min … { f } )(nk21 i ii

Minimax

Irrevocable : Langkah (kaidah) yang diambil merupakan keputusan yang tidak dapat diperbaiki lagi

Tentative :

Memberi kesempatan untuk mempertimbangkan akibat dari langkah tersebut, dan menarik kembali bila tidak menguntungkan

Backtracking:

Titik backtrack dipilih ketika suatu kaidah diterapkan. Proses pelacakan dapat kembali ke titik backtrack dan mencoba kaidah lain

Graph Search:

Sejumlah kaidah diterapkan secara serentak dan dicatat seluruh calon jejak (path) ke solusi

Blind Search / Strategi Buta

Pemilihan kaidah tidak didasarkan pada informasi (knowledge) tentang domain masalah

Informed Search

Didasarkan pada ‘knowledge’ tentang domain persoalan

Konfigurasi o Komputer System

Diagnosa o Comp. Hardware, Comp. Network o Telephone Trouble o Medical o Electronics Instruments

Interpretasi & Analisa Pemantauan Planning Intelligent Interfaces

o Hardware Inst o Control Panels

Natural Language Sistems Design Systems

o VLSI, sintesa rangkaian Computer Vision Systems Software Development

o Automatic Programming

Aplikasi AI

Anteseden disjungtif Jika mobil yang diperiksa memiliki salah dari gejala berikut:

starter tidak memutar/mengengkol atau starter mengeluarkan suara tidak normal

Maka tinjauan kemungkinan kegagalan pada starter Konsekwen berupa ‘treatment’ Jika karburator banjir Maka tekan pedal gas sambil men-starter

Rekayasa Pengetahuan (Knowledge Engineering)

Akuisisi Pengetahuan (Knowledge Acquisition) Pengolahan Pengetahuan (Knowledge Processing)

PAKARKNOWLEDGEENGINEERING

Pertanyaan,masalah

Jawaban,solusi

EXPERTSYSTEM

strategirules of thumbdomain rules

Proses Akuisisi Pengetahuan

PembangunAlat bantu

Alat bantuPengembang

ExpertSystem

PAKAR

KNOWLEDGEENGINEERINGmenggunakan

membangunwawancara

EXPERTSYSTEM

Penggunakonsultasi

StafAdministrasi

menambah data

Komponen-komponen dalam Pembangunan E.S.

Masalah-masalah dalam Proses Akuisisi Pengetahuan Akuisisi pengetahuan merupakan proses yang sulit, karena:

Keahlian pakar mengalami proses “internalisasi” Keahlian pakar berbentuk “rule of thumb” dan intuisi Pakar terlatih untuk menyelesaikan masalah bukan menjelaskan

bagaimana konklusi “ill-structured problem”

Noknowledge

Surfaceknowledge

Deepknowledge

Domain-dependentfacts

Learning from mentors and experiencesHeuristics

Generaltheories

Domain-dependentdefinition

First pronciples,axiom and laws

Learning from school and books

Compiledknowledge

Domain andperformance

theories

Properti Expert System dalam Bidang Diagnosis

Persoalan jumlah

rule

kategori keterangan

diagnosis penyakit hati

34 diagnosis menentukan jenis penyakit hati berdasar gejala-gejala yang khas tanpa menggunakan uji laboratorium

analisis gangguan pada jaringan 70 KV se Bandung Raya

70 diagnosis & perbaikan

menentukan jenis gangguan, lokasi, nomor penghantar, nomor fasa pada jaringan ring 70 KV se Bandung Raya

diagnosis penyakit tropis (kedokteran umum)

53 diagnosis menentukan jenis penyakit daerah tropis dengan indikasi panas sebagai patokan utama. Penelusuran lebih lanjut dilakukan pada system pernapasan dan pencernaan

Properti Expert System dalam Bidang Diagnosis

Persoalan jumlah

rule

kategori keterangan

diagnosis penyakit gigi

48 diagnosis & pengobatan

membantu tenaga medis pemula untuk menentukan penyakit gigi dan tindakan perawatan berdasarkan gejala yang teramati dah hasil pengukuran

troubleshooting gangguan pada generator serempak

49 diagnosis menentukan komponen yang mengalami gangguan pada generator serempak berdasarkan gejala yang teramati dan suatu prosedur pengujian

Properti Expert System dalam Bidang Diagnosis

Persoalan jumlah

rule

kategori keterangan

diagnosis kerusakan pada radio transistor

18 diagnosis & perbaikan

menentukan komponen penting yang mengalami kerusakan dan cara perbaikannya

diagnosis masalah gizi balita

59 diagnosis mendeteksi status gizi balita (malnutrisi) berdasarkan gejala-gejala yang khas serta pemakaian ‘growth chart’, guna mengambil tindakan perawatan

troubleshooting komputer mikro IBM XT/Compatible

40 diagnosis & perbaikan

mulai dari saat start sampai komputer menjalankan counter RAM, serta upaya perbaikannya. Isolasi kesalahan didasarkan pada gejala yang teramati dan hasil pengukuran

A EG H

C B

FAKTA

ZB&F FD&C

DA

match

KAIDAH

A E G H C B D

FAKTA

ZB&F FD&C

DA

match

KAIDAH

eksekusi

A E G H C B D F

FAKTA

ZB&F FD&C

DA

match

KAIDAH

eksekusi

A E G H C F B D Z

FAKTA

eksekusi

FORWARD CHAIN

A D

C

F

B

Z

(KNOWLEDGE BASE)

FAKTA

ZB&F FD&C

DA

FAKTA

ZB&F FD&C

DA

FAKTA

ZB&F FD&C

DA

E A H G C B

Get F Get B

Need

Z not here

Want Z

Get C Get D

Need

F not here

Want F

E A H G C B

E A H G C B

C here

Want C

FAKTA

ZB&F FD&C

DA

FAKTA

ZB&F FD&C

DA

FAKTA

ZB&F FD&C

DA

E A H G C B

Get A

Need

D not here

Want D

A here

Want A

E A H G C B

E A H G C B

Have A

eksekusi

FAKTA

ZB&F FD&C

DA

FAKTA

ZB&F FD&C

DA

FAKTA

ZB&F FD&C

DA

Have CHave D

E A H G C B F D

E A H G C B F D Z

eksekusi

E A H G C B D

Have FHave B

eksekusi

Have Z

The PH ofthe spill

Less than 6

The spillmaterial

is an acid

Spill smellslike vinegar

The spillmaterial isacetic acid

e 1 e2 en

P

PENJELASAN GANDA

JARAK AKUISISI

CONTOH SUATU KONSEP

domainrules

domainfacts

goalconcept

RUANG PELACAKANTERLALU LUAS

e1 e2

P NOT P

Kontradiksi

KONTRADIKSI

"SMALL LINKS PROBLEM"

Expert System : Lamp Repair

1. IF the lamp does not work THEN check to see that power is on

2. IF the power is not on THEN check for blown fuse

3. IF the power is not on AND the fuse is good THEN check for a power failure

4. IF the power is not on AND there is no fuse THEN check for a tripped circuit breaker

5. IF the power is not on AND the circuit breaker is on THEN check for a power failure

6. IF there is a power failure THEN wait for power to come back on

7. IF the power is on THEN check the bulb

8. IF the bulb is bad THEN replace the bulb

9. IF the bulb is good THEN check the switch

Elektrik Mekanis

SistemElektrik

SistemMekanis

SubsistemLubrication

SubsistemGoveynov

SubsistemPembakaran

KomponenKomponen

Hipotesa

Hipotesa

Operator Transmisi

Kesalahan Lokomotif

JIKA kondisi 1 DAN kondisi 2 DAN kondisi 3 … …….. MAKA aksi 1 – probabilitas = P1 DAN aksi 2 – Probabilitas = P2 … …….. …………

FORMAT KAIDAH IF Kondisi 1 and Kondisi 2 and Kondisi 3

and Kondisi n THEN Kondisi m and Kondisi m +1 and Choice 1 and Choice 2

and Choice k NOTE: REFERENCE:

menentukan daerahkegagalan

EXPERT SYSTEM

menentukanpenyebab

kegagalan yangmungkin

menyarankantindakan perbaikan

menyarankanpengujian untukmencek apakahkerusakan telah

diperbaiki

memberikan saranakhir jika perbaikan

belum berhasil

indikasi kesalahan(printout, alarm)

pertanyaan

jawaban

tindakan perbaikan(penggantian unit yang rusak)

pengujian

hasil uji

saran akhir

USER

Prosedur Konsultasi antara pengguna dan expert systemPada persoalan diagnosis

RULE IF kondisi 1 AND kondisi 2 AND kondisi 3 THEN kondisi n kondisi n + 1 choice 1 choice 2 choice m Kondisi

Qualifier Value (s/d 30 value)

Suatu rule mungkin memiliki:

lebih dari 1 value OR lebih dari 1 qualifier AND

Kondisi

text/kalimat statement aljabar

MYCIN: Diagnosa Kedokteran JIKA

Infeksi penderita adalah bakteremia-primer dan Lokasi organisme adalah pada lokasi yang steril dan Cara masuk organisme melalui gastro-intestinal

MAKA

Dapat diduga (0.7) bahwa identitas organisme adalah bacteroid

INFERENSI

KNOWLEDGEBASE

USERINTERFACE

USER

EXPERTKNOWLEDGE

ENGINEEREXPERTSYSTEM

FUZZY REASONING Fuzzy logic: merumuskan ketidak pastian diantara nilai-nilai 0 s/d 1 P (tinggi(x)) = 0,75 Operator: P1 AND P2 = MIN (P1, P2) P1 OR P2 = MAX (P1, P2) NOT P1 = 1 – P1 Contoh: Rule 1: IF x drives a Volvo car …1,0 AND x reads the guardian newspaper …0,8 THEN x will vote for the Social Democratis Party (SDP) 0,8 Rule 2: IF x dislikes Thatcher 0,5 AND x supports UK membership of the EEC …0,25 THEN x will vote for the SDP 0,25

Pembobotan Evidence: Shortliffe: MB[h:e1,e2] = MB[h:e1] + MB [h:e2] (1 – MB[h:e1]) Pengaruh evidence e2 pada hipotesis h jika mula-mula diberikan eviden e1.

Komponen Expert System

Basis Pengetahuan (Knowledge Base) Inferensi Explanatory Interface Modul Akuisisi Pengetahuan

Pengetahuan

Deklaratif Prosedural

Inferensi

Forward Chaining Backward Chaining

Akuisisi Pengetahuan

Handcrafting Induksi (learning)

Rule 3 (Kredibilitas 0.64) IF x drives a Chevrolet (a) AND x reads Reader’s Digest (b) THEN x will vote Republican Rule 4 (Kredibilitas 0.8) IF x likes retired actors (a) OR x wants the us to invade Nicaragua (b) THEN x will vote Republican 3a 0,88 3b 0,5

AND 0,5

4a 0,5 4b 0,7

OR 0,7

Kredibilitas Rule 3 0,5 0,64 = 0,32 Rule 4 0,7 0,8 = 0,56 MB [Republican: R3, R4] = 0,32 + 0,56 0,68 = 0,7008

If : The car won’t start Then : Consider the possibility of electrical system problems If : The car won’t start and

the fuel gauge reads empty Then : The car has no fuel and

fuel should be placed in the gas tank - beberapa kaidah dapat memiliki konsekuen yang sama, tetapi dengan anteseden

berbeda

If : The car has either of these symptoms: the starter doesn’t crank or the starter makes odd (grinding) noises

Then : Consider the possibility of a starter malfunction - kaidah ini dapat dipecah 2 kaidah If : The carburettor is flooded Then : Depress accelerator to floor while starting - konsekuen treatment

If : A conclusion of battery discharged has been “tentatively” reached and the reasoning shows that the following rules were invoked in reaching the conclusion: Rule 106: using “car wont’s start” as an antecedent Rule 139: using “headlights dim” as an antecedent

Then : The conclusion has still not yet been confirmed by a battery-fluid tester.

If : The car has a battery discharged problem and the battery has just

been replaced Then : consider testing the charging system (alternator or regulator) - Antesedent hipotesis intermediate

JENIS PENGETAHUAN Struktur atau topologi

Misal: hubungan fisik komponen-komponen dalam VLSI, unit-unit pada sistem komputer

Fungsi dan perilaku Misal: karakteristik komponen dalam rangkaian & simulasi

Rancangan dan kendala yang teramati oleh perancang Misal: alasan yang mendasari digunakannya komponen-komponen tertentu dalam rangkaian dan hubungannya

Hukum-hukum fisik

Misal: hokum OHM Interpretasi perilaku

Misal: kemampuan trouble shooting Kasus-kasus sebelumnya (empirik) Metaknowledge

STRUKTUR PENGETAHUAN :

Pola-pola fakta Pola-pola hipotesis Macam rekomendasi Level kompleksitas pengetahuan hirarki Ketidakpastian Kaitan antar fakta dan hipotesis

Anteseden dapat berupa pengamatan atau hasil uji instrumen Perlu diperoleh informasi untuk mendukung dugaan yang coba-coba

Jika mobil tidak dapat distarter dan putaran starter lambat dan batere belum diuji Maka uji batere harus dilakukan

Jika hasil yang diharapkan tidak teramati:

alihkan konklusi cek keselamatan yang mungkin inkonsistensi pada data

KRITERIA

HANDCRAFTING INDUKSI

- pengetahuan telah diperoleh dalam bentuk handbook, instruksi dll.

- terdapat sejumlah contoh yang representatif

- akses kepada pakar selalu dimungkinkan

- pakar langka (akses tidak selalu dimungkinkan)

- pakar tidak mengalami kesulitan dalam menjelaskan mekanisme penalarannya

- pakar mengalami kesulitan dalam menjelaskan mekanisme penalarannya

- umumnya domain permasalahan luas - domain terbatas dan “well defined”

ALGORITMA CONCEPT LEARNING

1. Ambil sejumlah contoh

2. Berhenti jika seluruh contoh termasuk dalam kelas yang sama

3. Pilih satu atribut untuk memisahkan contoh-contoh

4. Pisahkan contoh-contoh ke dalam sebanyak mungkin subset berdasarkan nilai atribut

5. Untuk setiap subset, ulangi secara rekursif dari langkah 2

SUMBER-SUMBER PENGETAHUAN

Keahlian Pakar Kasus-kasus Dokumen Gambar-gambar Laporan Data lain

AKUISISI PENGETAHUAN

Proses menyerap pengetahuan dari sumber-sumber pengetahuan dan transformasinya kedalam bentuk representasi internal berdasarkan kerangka representasi pengetahuan.

Dalam wawancara Knowledge Engineer dapat mengemukakan pendapat dan memperhatikan bagaimana perubahan pendapat pakar terhadap perubahan situasi.

PEMANFAATAN “MACHINE LEARNING” PRINSIP-PRINSIP:

“Concept Learning”: pembentukan konsep berdasarkan contoh-contoh yang diberikan

pemisahan contoh ke dalam sejumlah subset didasarkan pada nilai atribut proses perampatan (generalization) dan klasifikasi contoh-contoh contoh-contoh yang representatif tersedia & lengkap? memperlihatkan

karakterisitk keahlian pakar memungkinkan interaksi langsung antara pakar dengan expert system yang

dibangun.

REPRESENTASI PENGETAHUAN

Deklaratif o Predicate logic o jaringan semantic o Frame

Prosedural pattern invoked program IF…THEN…

o Pattern matching o Backtracking

TERMINOLOGI :

1. Basis pengetahuan kumpulan knowledge

2. Kondisi

pernyataan sederhana dari fakta-fakta

3. Qualifier mencakup kata kerja

4. Value

kemungkinan yang melengkapi kalimat yang dimulai dengan Qualifier

5. Choice kemungkinan solusi dari masalah yang akan dipecahkan

6. Nilai kemungkinan

derajat kemungkinan kebenaran suatu konklusi

Rule 5 Jika hari kedatangan adalah Senin atau Selasa atau Rabu atau Kamis Dan waktu antara pukul 4.00 PM dan 9.00 AM Maka waktu datangnya terlambat Rule 6 Jika hari kedatangan adalah Jumat Dan waktu antara pukul 11.00 AM dan 4.00 PM atau antara 4.00 PM dan 9.00 AM Maka waktu datangnya terlambat Rule 7 Jika hari kedatangan adalah Sabtu atau Minggu Maka waktu datangnya terlambat Rule 8 Jika hari kedatangan adalah bukan Sabtu atau Minggu Dan waktu antara pukul 9.00 AM dan 11.00 AM Maka waktu datangnya tepat Rule 9 Jika hari kedatangan adalah Senin atau Selasa Dan waktu antara pukul 11.00 AM dan 4.00 PM Maka waktu datangnya terlambat Rule 10 Jika suara pasien serak Maka pasien dalam keadaan sakit

Rule 1 Jika pemanggil sakit Dan dokter sedang pergi Maka aspirin (P = 10/10) Dan panggil lagi besok pagi (P = 10/10) Rule 2 Jika mukanya pucat Maka pemanggil sakit Rule 3 Jika temperatur diatas 40o Maka pemanggil sakit Rule 4 Jika mukanya tidak pucat Dan temperatur dibawah 40o Maka pemanggil sehat

Rule 5 Jika hari ini Jumat Dan waktu antara pukul 2.00 PM dan 4.00 PM atau antara 4.00 PM dan

9.00 PM Maka dokter sedang pergi Rule 6 Jika hari ini Senin atau Selasa atau Rabu atau Kamis Dan waktu antara pukul 4.00 PM dan 9.00 AM Maka dokter sedang pergi Rule 7 Jika hari ini Sabtu atau Minggu Maka dokter sedang pergi Rule 8 Jika hari ini bukan Sabtu atau Minggu Dan waktu antara pukul 9.00 PM dan 2.00 PM Maka waktu terlalu dini

Rule 1 If . Then choice 1 : Probability = 0/10 Rule 2 If . Then choice 1 : Probability = 2/10 Rule 3 If . Then choice 1 : Probability = 8/10 Rule 4 If . Then choice 1 : Probability = 10/10 2 & 3 Benar : 5/10 1 & 2 & 3 Benar : 0/10 2 & 3 & 4 Benar : 10/10

CHOICE: solusi yang mungkin item, rekomendasi, saran, “treatment”, dll memiliki ‘probabilitas’

PROBABILITAS:

a. 0 atau 1 0 “no” 1 “yes” missal: memilih sejumlah itemd ari suatu daftar

b. 0 – 10 0 “absolutely no” 10 “absolutely yes” jika choice muncul pada beberapa rule rata-rata

3/10, 8/10, 4/10 5/10 3/10, 9/10, 0/10 0/10 3/10, 10/10, 4/10 10/10

c. 0 – 100

- rata-rata - dependent probabilities

60/100, 90/100 60/100 90/100 = 54% - independent probabilities

60/100, 90/100 1 – ((1 – 60%) * (1 – 90%)) = 96%

Rule 1 IF x drives a Volkswagen (a) AND x reads Washington Post (b) THEN x will vote Democrat Rule 2 IF x dislikes Ronald Reagan (a) OR x wants the US to pull out of EL. Salvador (b) THEN x will vote Democrat 1a 0,8 1b 0,75

AND MIN = 0,75

2a 0,4 2b 0,6

OR MAX = 0,6

Hipotesis bahwa x mendukung Democrat MB [Democrat: Rule 1, Rule 2] = MB [Democrat: Rule 1] + MB [Democrat: Rule 2] (1 - MB [Democrat: Rule 1]) = 0,75 + 0,6 0,25 = 0,9 Sebuah rule mungkin memiliki nilai kredibilitas diantara 0 s/d 1.

EXPERT SYSTEM UNTUK KEDOKTERAN Rule 1 Jika pasien dalam keadaan sakit Dan waktu datangnya terlambat Maka aspirin – probabilitas = 10/10 Dan dating lagi besok pagi – probabilitas = 10/10 Reduksi menjadi 2 masalah

- Menentukan bahwa pasien sakit - Menentukan bahwa kedatangannya terlambat

Rule 2 Jika raut mukanya pucat Maka pasien dalam keadaan sakit Rule 3 Jika temperatur tubuh diatas 40oC Maka pasien dalam keadaan sakit Rule 4 Jika raut mukanya tidak pucat Dan temperatur tubuh dibawah 40oC Maka pasien dalam keadaan sehat Rule 2, 3, 4 menguji apakah pasien sakit

Rule 5 Jika waktu kedatangan adalah hari Senin atau Selasa atau Rabu atau Kamis Dan waktunya antara pukul 21.00 – 6.00 Maka waktu datangnya terlambat Rule 6 Jika waktu kedatangan adalah hari Sabtu atau Minggu Maka waktu datangnya terlambat Rule 5,6 menguji waktu kedatangan Rule 7 Jika waktu kedatangan adalah hari Jumat Dan waktunya antara pukul 11.00 – 13.00 atau antara pukul 21.00 – 6.00 Maka waktu datangnya terlambat Rule 8 Jika waktu kedatangan adalah tidak hari Sabtu dan Minggu Dan waktunya antara pukul 6.00 – 19.00 Maka waktu datangnya cukup dini/tidak terlambat

Para pakar diagnostik sering menggunakan hipotesis antara (intermediate hypothesis) sebagai “batu loncatan”. komponen penting dalam penalaran (reasoning)

perlu pertimbangkan pola-pola hipotesis antara yang mungkin dalam basis pengetahuan.

Jika gejala pasien adalah

mata kuning atau urine coklat atau hati nyeri

Maka positip penyakit hati Jika positip penyakit hati dan

feses berdarah dan hati nyeri tekan

Maka abses hati karena ambuba : 9/10

10. IF the switch is bad THEN replace the switch 11. IF the bulb is good AND the switch is good THEN check the plug 12. IF the plug is bad THEN fix or replace the plug 13. IF the bulb is good AND the switch is good AND the plug is good THEN check the cord 14. IF the cord is bad THEN fix or replace the cord 15. IF the bulb is good AND the switch is good AND the plug is good AND the cord is good THEN check the wall outlet 16. IF the wall outlet is bad THEN fix or replace the outlet

STRUKTUR PENGETAHUAN & PENALARAN ES

1. Konklusi (advice) harus dapat dibangkitkan oleh sistem dari sejumlah elemen 2. Fakta teramati (evidence) harus dapat diperoleh oleh pengguna atau oleh sistem

itu sendiri 3. Asumsi awal harus membatasi lingkup masalah mengarahkan penalaran

sistem 4. Basis pengetahuan atau struktur kaidah harus dapat mengkaitkan fakta teramati

dengan konklusi kaidah logis kaidah probabilistik

5. Strategi kontrol penalaran harus dirancang untuk mengarahkan penalaran es menghasilkan output yang dapat diterima oleh respon pengguna

“Keahlian seorang expert terletak pada kemampuannya mempersempit scope solusi yang mungkin untuk setiap penambahan fakta (evidence)”

2. Konseptualisasi Knowledge engineer & expert menentukan:

konsep relasi & mekanisme kontrol solusi subtask, strategi & batasan jangan coba menganalisis masalah secara lengkap sebelum memulai implementasi

3. Formalisasi representasi pengetahuan secara formal (rule-based, frame-based dll) berdasarkan

expert system building tool

4. Implementasi mengimplementasi formalized knowledge ke program komputer struktur data, inference rules & control strategy

5. Pengujian

evaluasi performance & utilitas prototype es perbaikan

Prototipe

efektivitas uji definisi, scope & representasi 50 – 100 rule

If : The car won’t start and the starter cranks slowly and the battery has not been tested Then : A battery tes should be performed - konsekuen (jika benar memperbesar kepastian

Penyakit hati

Hepatitis akut

Hepatitis A Hepatitis B

Jenis Kronis

CirhosisHepatitis

HepatomaHepatitis

Kronis

HrpatitiskarenaAmuba

Hepatitisbawaan

MAMMAL

AND

EATSMEAT

AND

POINTEDTEETH

CLAWS

EYES POINTFORWARD

OR CARNIVORE AND

DARKSPOTS

BROWN

AND

BLACKSTRIPLES

BROWN

CHEETAH

TIGER

AND

DARKSPOTS

LONGNECK

GIRAFFE

BROWN

LONGLEGS

UNGULATEAND

HOOVES

AND

WHITE

BLACKSTRIPLES

ZEBRAUNGULATEEVEN-TOED

AND

CHEWSCUD

DOES NOT FLY

GOOG FLIER

AND

AND

OSTRICH

ALBATROSSLONG LEGS

AND

BLACK ANDWHITE

BIRDOR

HAIR

GIVESMILK

OR

LAYSEGGS

AND

FLIES

FEATHERS

FORWARD CHAINING

BACKWARD CHAINING

EXAMPLES RULES – TOY CASE

IF THE ANIMAL HAS HARI

OR

IF THE ANIMAL GIVES MILK

THEN

THE ANIMAL IS MAMMAL

IF THE ANIMAL HAS FEATHERS

OR

IF THE ANIMAL FLIES

AND THE ANIMAL LAYS EGGS

THEN

THE ANIMAL IS A BIRD

EXAMPLE RULES-REAL WORLD

IF THE TRAFFIC PER LINE IS NORMAL

AND THE TYPE OF LINE CIRCUIT IS ELC

THEN

THERE IS ONE SPARE LINE PER 479 LINES

AND THE NUMBER OF LINES PER ASM EQUALS 128

AND THE NUMBER OF LINES PER PGA EQUALS 6

IT IS A (CHEETAH) : - IT IS (MAMMAL), IT IS (CARNIVORE), HAS (TAWNY COLOUR), HAS (DARK SPOTS). IT IS A (TIGER) : - IT IS (MAMMAL), IT IS (CARNIVORE), HAS (TAWNY COLOUR), HAS (BLACK STRIPES).

IT IS (MAMMAL) : - HAS (HAIR). IT IS (MAMMAL) : - DOES (GIVE MILK). IT IS (BIRD) : - HAS (FEATHERS) IT IS (BIRD) : - DOES (FLY), DOES (LAY EGGS).

IT IS (UNGULATE) : - IT IS (MAMMAL), HAS (HOOFS). IT IS (UNGULATE) : - IT IS (MAMMAL) DOES (CHEW CUD).