pertemuan 6
TRANSCRIPT
Sistem Berbasis Pengetahuan
3 SKSEka Dyar W
Outline
Inferensi II Forward chaining Backward chaining
Forward chaining
disebut data-driven Rule akan dieksekusi jika premis (bagian dari
IF) terpenuhi Penalaran berawal dari semua fakta yang
diketahui untuk menuju ke satu konklusi Baik digunakan jika tree melebar dan tidak
dalam, memudahkan pencarian breadth first (pencarian konklusi berproses level ke level)
Backward chaining
Disebut juga goal-driven Pilih konklusi dan coba buktikan
kebenarannya dengan menganalisa evidence / premis yang mendukung konklusi tersebut berdasarkan fakta yang diberikan
Memudahkan pencarian depth first, tree yang baik untuk depth first adalah yang menyempit dan dalam
Pengkodean yang diperoleh saat knowledge acquisition• A1 = suhu tubuh >=
38°C• A2 = pusing • A3 = pilek• A4 = batuk• A5 = batuk yang terus
menerus dimalam hari• A6 = nafas berbunyi
• P1 = demam biasa• P2 = batuk biasa• P3 = influensa/infeksi
virus• P4 = batuk rejan• P5 = infeksi saluran
nafas
Rule yang ada pada knowledge base R1 : IF A1 THEN P1 R2 : IF A4 THEN P2 R3 : IF (P1 or A2) and (P2 or A3) THEN P3 R4 : IF P3 and A5 THEN P4 R5 : IF P3 and A6 THEN P5
Fakta-fakta yang diperoleh dari user adalah demam, pusing, batuk dan batuk tersebut lebih sering di malam hari (A1, A2, A4, A5 benar
A1 A4
P1 P2A2 A3
P3A6
P5
A5
P4
Tree untuk rule tersebut
Algoritma Forward chaining1. Catat semua fakta yang diinputkan oleh user2. Catat semua rule yang bagian premisnya menggunakan fakta yang
sesuai ke dalam queue Q3. Sampai tidak ada rule pada Q :
a. Analisa rule pertama pada Qb. Jika premis tidak terpenuhi, hapus rule dari Q dan kembali ke ac. Jika premis terpenuhi :
- eksekusi rule, catat konklusi dari rule- Cari rule yang menggunakan konklusi tersebut sebagai premis- Jika rule belum ada pada Q, catat rule tersebut meskipun premis
tidak sepenuhnya terpenuhi.- Hapus rule awal dari Q
4. Konklusi akhir diperoleh
Penyelesaian dengan forward chaining1. Fakta dari user A1, A2, A3, A4, A52. Rule yang sesuai = R1, R2, R3, R43. Sampai tidak ada rule pada Q
Q R K
Iterasi 1 R1, R2, R3, R4 R1 P1
Iterasi 2 R2, R3, R4 R2 P2
Iterasi 3 R3, R4 R3 P3
Iterasi 4 R4 R4 P4
Algoritma backward chaining1. Catat GOAL pada TOS (top of stack)2. Catat semua rule yang memenuhi GOAL3. Untuk setiap rule :
a. Jika semua premis terpenuhi, maka eksekusi rule untuk mendapat konklusi, proses selesai
b. Jika sebuah premis tidak terpenuhi, cari rule yang menurunkan nilai dari parameter premis tsb. Maka Jika ada, maka asumsi parameter tsb adalah SUBGOAL, letakkan pada TOS.
c. Jika tidak ada, maka tanyakan kepada user apa nilai dari parameter tsb. Jika nilai ini sesuai premis, lanjutkan pada premis berikutnya. Jika premis tidak sesuai lanjutkan ke rule berikutnya.
4. Jika semua rule sudah dianalisa dan semuanya gagal, maka GOAL tidak ada. Hapus GOAL dari stack dan kembali ke langkah 2. Jika stack kosong, proses selesai
Penyelesaian dengan backward chaining1. Goal pada TOS adalah P4 (batuk rejan) atau P5 (infeksi
saluran pernapasan) 2. Rule yang memenuhi goal = R4 dan R53. Eksekusi untuk R4
Known fact ()a. –b. premis 1 P3 menjadi goal baru pada TOS
a. rule yang memenuhi goal P3 R3 premis 1 P1 or A2 A2 (T) premis 2 P2 or A3 P2 menjadi goal baru
pada TOS
a. rule yang memenuhi goal P2 R2
premis A4 (T) eksekusi R2 didapatkan premis 2 (T)
eksekusi R3 didapatkan P3 (T)Premis 2 tidak ada rule yang menurunkan A5, tanyakanke user nilai dari A5 TEksekusi R4 T&T P4Stack kosongProses selesaiKesimpulan P4(batuk rejan)
Forward atau backward ?
Cek hubungan antara rule dengan fakta utk menghasilkan konklusi Sekumpulan fakta banyak konklusi backward
chaining Sekumpulan hipotesis banyak pertanyaan forward
chaining Banyak cara utk mendapatkan sedikit konklusi
forward chaining Sedikit cara untuk mendapatkan banyak konklusi
backward chaining
Latihan
Z1 IF x has hair THEN X is a mammal Z2 IF x gives milk THEN x is a mammal Z3 IF x has feathers THEN x is a bird Z4 IF x flies AND x lays eggs THEN x is a bird Z5 IF x is a mammal AND x eats meat THEN x
is a carnivore Z6 IF x is a mammal AND x has pointed teeth
AND x has claws AND x has forward pointing eyes THEN x is a carnivore
Z7 IF x is a mammal AND x has hoofs THEN x is an ungulate
Z8 IF x is a mammal AND x chews end THEN x is an ungulate
Z9 IF x is carnivore AND x has tawny color AND x has dark spots THEN x is a cheetah
Z10 IF x is a carnivore AND X has tawny color AND x has black strips THEN x is a tiger
Z11 IF x is an ungulate AND x has long neck AND x has long legs AND x has tawny color AND x has dark spots THEN x is a giraffe
Z12 IF x is an ungulate AND x has white color AND x has black strips THEN x is a zebra
Z13 IF X is a bird AND x does not fly AND x has long legs AND x has long neck AND x
has black and white THEN x is a ostrich Z14 IF x is a bird AND x does not fly AND x
swims AND x has black and white THEN x is a penguin
Z15 IF x is a bird AND x is a good flyer THEN x is albatross
Fakta dari user x : Gives milk Chews Has white color Has black strips
Penyelesaian dengan forward dan backward chaining ?
Minggu depan
Implementasi forward dan backward chaining
