Sebelumnya... • Sistem Pakar berbasis Aturan (Rule-Based Expert System, RBES) – Sistem Pakar – Representasi Pengetahuan – Penalaran • Forward chaining • Backward chaining – Resolusi Konflik
Contoh RBES (1) • Sistem pakar untuk... • Perhatikan sistem produksi berikut: – Rule 1 IF suhu <37 THEN tidak demam – Rule 2 IF suhu >37 AND suhu <38 THEN demam rendah – Rule 3 IF suhu > 38 THEN demam tinggi – Rule 4 IF hidung tersumbat ringan THEN Beringus – Rule 5 IF hidung tersumbat berat THEN pembengkakan selaput sinus
Contoh RBES (2) – Rule 6
– – – –
IF Demam rendah AND Sakit kepala AND Beringus AND Batuk THEN flu Rule 7 IF flu AND Tidak Radang tenggorokan THEN jangan diobati Rule 8 IF flu AND Radang tenggorokan THEN diobati Rule 9 IF Jangan diobati THEN Jangan berikan obat Rule 10 IF diobati THEN Berikan Obat
Contoh RBES (3) – Rule 11
– Rule 12
IF Berikan Obat AND Alergi Antibiotika THEN Berikan Tylenol IF Berikan Obat AND Tidak alergi Antibiotika THEN Berikan Antibiotika
Contoh RBES (4) • Pasien mengalami sakit kepala dan hidung tersumbat. Demamnya 37.5 dan batuk. • Pasien menolak dikatakan alergi antibiotika. • Hasil lab. menunjukkan bahwa orang tersebut juga mengalami radang tenggorokan. 1) Gunakan forward chaining untuk mengetahui apakah pasien boleh diberikan Antibiotika. 2) Gunakan backward chaining untuk mengetahui secara terbalik, jika diberikan antibiotika, apa gejala-gejalanya?
Bagaimana dengan ini? (1) Aturan Produksi: • Rule 1 IF shape is long AND color is yellow THEN fruit is banana • Rule 2 IF shape is round AND color is red AND size is medium THEN then fruit is apple • Rule 3 IF shape is round AND color is red AND size is small THEN then fruit is cherry • Rule 4 IF skin smell THEN perfumed
Bagaimana dengan ini? (2) • Rule 5
• Rule 6
• Rule 7
• Rule 8
IF fruit is lemon OR fruit is orange OR fruit is pomelo OR fruit is grapefruit THEN citrus fruit IF size is medium AND color is yellow AND perfumed THEN then fruit is lemon IF size is medium AND color is green THEN fruit is kiwi IF size is big AND perfumed AND color is orange AND citrus fruit THEN fruit is grapefruit
Bagaimana dengan ini? (3) • Rule 9
• Rule 10
• Rule 11 • Rule 12
• Rule 13
IF perfumed AND color is orange AND size is medium THEN fruit is orange IF perfumed AND color is red AND size is small AND no seeds THEN fruit is strawberry IF diameter <2 cm THEN size is small IF diameter >10 cm THEN size is big IF diameter >2 cm AND diameter <10 cm THEN size is medium
Bagaimana dengan ini? (4) Premis/Fakta/Kondisi dalam database: • The fruit has no seed, a 7 cm diameter, smelling skin, orange color Tugas? 1) Gunakan forward chaining untuk membuktikan bahwa fruit adalah citrus fruit. 2) Gunakan backward chaining untuk mengetahui sebaliknya, jika citrus fruit, apa saja ciri-cirinya?.
Latihan (Praktik) • Buatkan suatu basis pengetahuan dan basis data yang terdiri sekitar 10 rules dan 15 fakta: 1) 2) 3) 4) 5)
Lakukan penalaran forward chaining Lakukan penalaran backward chaining Buatkan rantai inferensinya. Gambarkan chaining-nya dalam suatu diagram. Gunakan kreatifitas anda dan pengetahuan pakar dalam domain pilihan tersebut.
Bagi yang Tidak Ikut UTS • Kerjakan soal UTS, dan kumpulkan • Waktu: 1 Minggu (Deadline: 28 November 2013)
Perbaikan UTS • Telah ada tugas, merangkum paper, tujuan: memperbaiki hasil UTS • Apakah tugas tsb telah dikerjakan dengan baik? • Contoh yang SALAH: – Paper tidak terkait / berbasis WEB – Tidak ada unsur kecerdasan buatan
• Silakan diperbaiki (bagi yang merasa salah) dan dikumpulkan 2 minggu kemudian.
Tugas Sebelum UAS • Mirip dengan tugas sebelumnya. • Hanya paper mulai 2011 s.d 2013 • Dikumpulkan minggu terakhir kuliah, sebelum minggu tenang. • Kata kunci umum: Web Intelligent system • Web, dapat diwakili (lebih fokus): personalization, recommender system, social network (sentiment analysis & opinion mining), web retrieval/web mining, search engine • Intelligent dapat diwakilkan dengan: expert system, machine learning, fuzzy system, genetic algorithm, neural network, swarm intelligent, ant algorithm, bio-inspired.
Kecerdasan Buatan Pertemuan 07
Ketidakpastian dalam RBES ...
Husni
[email protected] http://Komputasi.wordpress.com S1 Teknik Informatika, STMIK AMIKOM, 2013
Outline • • • • •
Pendahuluan Teori Bayes Faktor-faktor Kepastian Rangkuman Latihan
Ketidakpastian (uncertainty) • Esensi: Kurangnya informasi untuk merumuskan keputusan. • Sumber ketidakpastian: – Bahasa yang tidak tepat: kesalahan translasi dari bahasa pakar ke bentuk IF-THEN – Data/Informasi/Pengetahuan: Tidak lengkap, salah, hilang, tidak dapat diandalkan. – Terminologi tidak jelas/berubah-ubah – Pengetahuan berubah-ubah – Data tak tepat: satu istilah banyak makna, banyak istilah satu makna – Kombinasi pandangan para pakar berbeda. – Error-error.
Metode & Teori Terkait Ketidakpastian • Penyelesaian masalah ketidakpastian dapat berbasis: – Peluang (Statistika): objective probability, experimental probability & subjective probability – Heuristik, mencakup Faktor Kepastian dan Logika Samar
• Teori yang banyak digunakan: – – – – – –
Bayesian Probability Hartley Theory Shannon Theory Dempster-Shafer Theory Markov Models Fuzzy Theory
Probabilitas/Peluang • Probabilitas adalah proporsi atau persentase terjadinya suatu kejadian. • Diekspresikan dalam bilangan ril antara [0, 1]. Nilai 0 berarti ketidakmungkinan absolut, 1 menunjukkan kepastian absolut. • P(A(t)) memberikan nilai dalam range [0, 1] untuk setiap kemungkinan terjadinya t dalam domain A, dimana jumlah semua nilai itu adalah 1. • Contoh:
Sukses dan Gagal • Suatu kejadian setidaknya punya 2 keluaran: sukses atau gagal. Peluang sukses:
Peluang gagal:
Diperoleh P(sukses) + P(gagal) = 1 • Contoh: peluang munculnya nilai pada dadu (6 sisi) P(sukses(1) )= P(sukses(2))= ... = P(sukses(6)) = 1/6 P(gagal(1) )= P(gagal(2))= ... = P(gagal(6)) = 5/6 P(sukses(2)) + P(gagal(2)) = 1/6 + 5/6 = 1
Sifat Kejadian • Independen dan mutually exclusive: kejadian-kejadian tidak dapat terjadi secara simultan (bersamaan). Misal: sisi dadu bernilai 5 tidak dapat muncul bersamaan dengan sisi dadu bernilai 3. • Tidak independen = terikat: satu atau lebih kejadian mempengaruhi terjadinya kejadian lain. • Teori peluang: – 0 ≤ P(E) ≤ 1 –
– P(E1∪E2)=P(E1) + P(E2) dimana E1 dan E1 mutually exclusive.
Jika Lebih Satu Kejadian • Pada kejadian-kejadian Independen: P(A∩B) = P(A) P(B) P(A∪B) = P(A) +P(B) - P(A∩B) P(A∪B∪C) = P(A) + P(B) + P(C) - P(A∩B) - P(A∩C) - P(B∩C) + P(A∩B∩C) • Pada kejadian tidak independen, muncul Peluang kondisional: Kejadian A terjadi jika kejadian B telah terjadi, P(A|B).
• Jumlah kali A dan B dapat terjadi dinamakan joint /compound probability dari A dan B, ditulis P(A∩B)
Aturan Bayes
• Dengan deduksi diperoleh P(A∩B) = P(A|B) P(B) • Joint probability bersifat kumutatif, diperoleh P(A∩B) = P(B∩A) • Dari P(B∩A) = P(B|A) P(A), diperoleh:
Rumus ini dinamakan Aturan Bayes (Bayesian Rule).
Aturan Bayes • P(A|B): peluang terjadinya kejadian A setelah (dikarenakan) terjadinya kejadian B; • P(B|A): Peluang terwujudnya kejadian B setelah berlakunya kejadian A; • P(A): peluang berlakunya kejadian A; • P(B): peluang berlakunya kejadian B. • Aturan jumlah: P(A|B) + P(￢A|B) = 1
Generalisasi Aturan Bayes 1) Kejadian A bergantung pada himpunan kejadian B1, B2, …, Bn yang bersifat mutually exclusive.
2) Sehimpunan kejadian mutually exclusive A1, A2, …, An bergantung pada kejadian B.
Contoh • Seorang pasien ada Bintik2 di wajah, dokter menduga ia terkena Cacar, dengan: – P(Bintik2|Cacar) = 0,8 – P(Cacar) = 0,4 – P(Bintik2|Alergi) = 0,3 – P(Alergi) = 0,7 – P(Bintik2|Jerawatan) = 0,9 – P(Jerawatan) = 0,5
Generalisasi Aturan Bayes 3) Himpunan kejadian mutually exclusive A1, A2, …, Am bergantung pada sehimpunan kejadian B1, B2,…, Bn yang bersifat mutually exclusive.
dapat pula ditulis:
Contoh • Pakar membuat 3 hipotesis: A1, A2 dan A3 (mutually exclusive) bergantung pada 3 fakta independen B1, B2 dan B3. • Pakar juga menyediakan peluang kondisional.
• Hipotesis dirangking: A1, A2, A3. A1 paling dipercaya (probabilitas tertinggi). • Gunakan penalaran Bayes untuk memeriksa apakah ranking tersebut tetap pada akhir proses!
Contoh • Pertama, hitung P(Ai|B1), i= 1, 2, 3, dengan rumus:
Contoh • Hitung P(Ai|B2B1), i=1, 2, 3 dengan rumus:
Diperoleh P(A1|B2B1) = 0.52, P(A2|B2B1) = 0.36, P(A3|B2B1) = 0.10. • Terakhir, hitung P(Ai|B3B2B1), i=1, 2, 3, dengan rumus:
• Diperoleh hasil 0, 0.814, dan 0.186.
Jaringan Bayes (Bayes Net) • Tool untuk mengetahui/mengevaluasi hubungan antar variabel dalam jumlah besar. • Elemen dari jaringan bayes: – Struktur jaringan yang memperlihatkan independensi kondisional – Distribusi peluang untuk setiap variabel • P(Cloudy, Sprinkler_on, Rain, Grass_wet) = P(Cloudy) * P(Sprinkler_on|Cloudy) * P(Rain|Cloudy,Sprinkler_on) * P(Grass_wet|Cloudy,Sprinkler_on,Rain) Dapat disederhanakan menjadi: P(Cloudy, Sprinkler_on, Rain, Grass_wet) = P(Cloudy) * P(Sprinkler_on|Cloudy) * P(Rain|Cloudy) * P(Grass_wet| Sprinkler_on, Rain)
Contoh
Faktor Kepastian • Teori Certainty factors (CF) merupakan alternatif bagi penalaran Bayes. • Menggunakan pendekatan heuristik dalam penalaran dengan ketidakpastian. • Pakar membobot keyakinan dari kesimpulannya dan langkah-langkah penalarannya dengan istilah “tidak mungkin”, “hampir pasti”, “sangat mungkin”, “mungkin”. • Bukan peluang tetapi heuristik yang diturunkan dari pengalaman. Juga bukan nilai kebenaran. • CF digunakan untuk mengekspresikan berapa akurat, sungguh dan handal suatu dugaan.
Faktor Kepastian • CF dapat diterapkan terhadap: – Fakta/premis; – Rules (aturan, kesimpulan dari rule); – Fakta dan rules.
• Saat diterapkan terhadap fakta (evidence, premis) : mewakili derajat kepercayaan (ketidakpercayaan) dari fakta. • Saat diberlakukan terhadap rules: mewakili derajat konfirmasi(diskonfirmasi) suatu hipotesis. • Arti CF bernilai -1 dan 1: – CF mendekati 1, fakta semakin kuat bagi suatu hipotesis – Cf mendekati -1, kepercayaan berlawanan hipotesis semakin kuat. – CF sekitar 0, ada fakta yang mendukung dan juga melawan hipotesis.
KB pada ES dengan CF • IF Evidence THEN Hypothesis {CF} • Dimana CF mewakili kepercayaan terhadap hipotesis jika evidence/fakta terjadi.
Menghitung Faktor Kepastian • Untuk suatu hipotesis H dan fakta/evidence E, ukuran kepercayaan MB(H,E) dan ketidakpercayaan MD(H,E) adalah
• Dimana: – P(H) peluang (sebelumnya) hipotesis H bernilai True; – P(H|E) peluang hipotesis H bernilai True jika terdapat evidence E.
Faktor Kepastian (CF)?
• Dengan range nilai [-1, 1]
Faktor Kepastian Kombinasi • Banyak rules merepresentasikan fakta/evidence E untuk kesimpulan sama.
• Contoh: IF E1 THEN H {CF=0.6} IF E2 THEN H {CF= -0.3}
Rule dengan ketidakpastian Evidence • Contoh: Rule 1: IF A THEN B {CF=0.4} Rule 2: IF B THEN C {CF=0.3} Berapa kepastian A? B setelah A? • Satu Premis Rule 1: IF A THEN B {CF=0.4} Rule 2: IF B THEN C {CF=0.3} CF(C) = CF(B) * CF(Rule 2)
Jika CF dari A bernilai True adalah 0.9 maka: CF(B) = CF(A)*CF(Rule 1) = 0.9*0.4 = 0.36, dan CF(C) = CF(B)*CF(Rule 2) = 0.36*0.3 = 0.108
Rule dengan ketidakpastian Evidence • Evidence Negatif. IF E THEN H {CF=0.6} Jika CF(E)=-0.2 (negatif), maka tidak ada yang dapat disimpulkan.
Rule dengan ketidakpastian Evidence • Banyak Premis. Digabungkan dengan AND: IF E1 AND E2 ... AND En THEN H {CF}
• Banyak Premis. Digabungkan dengan OR: IF E1 OR E2 ... OR En THEN H {CF} CF(H) = max{CF(E1), CF(E2), …, CF(En)} * CF(Rule)
Contoh • IF E1 {CF = 0.8} AND E2 {CF = 0.7} AND E3 {CF = 0.5} AND E4 {CF = 0.3} AND E5 {CF = 0.9} THEN H {CF = 0.65}
AND
• CF(H) = min{CF(E1), CF(E2), CF(E3), CF(E4), CF(E5)} * CF(Rule) = 0.3*0.65 = 0.195.
Contoh • IF E1 {CF = 0.8} OR E2 {CF = 0.7} OR E3 {CF = 0.5} OR E4 {CF = 0.3} OR E5 {CF = 0.9} THEN H {CF = 0.65}
OR
• CF(H) = max{CF(E1), CF(E2), CF(E3), CF(E4), CF(E5)} * CF(Rule) = 0.9*0.65 = 0.585.
Contoh • Sistem pakar untuk diagnosa flu (cold). Database terdiri dari fakta: demam pasien 37.4, batuk kurang 24 jam, bersin-bersin, sakit kepala dengan CF = 0.4 dan hidung tersumbat dengan CF = 0.5 Rule base mengandung: • Rule 1 IF demam < 37.5 THEN Gejala Flue = true {CF = 0.5} • Rule 2 IF demam > 37.5 THEN Gejala Flu = true {CF = 0.9} • Rule 3 IF batuk lebih dari 24 jam THEN sakit tenggorokan = true {CF = 0.5}
Contoh • Rule 4 • Rule 5
• Rule 6 • Rule 7
IF batuk lebih dari 48 jam THEN sakit tenggorokan = true {CF = 1} IF Gejala flue AND Bersin-bersin THEN Terkena flu {CF = -0.2} IF sakit tenggorokan THEN Terkena flu {CF = 0.5} IF sakit kepala AND hidung tersumbat THEN Terkena flu {CF = 0.7}
Pohon Inferensi
Terkena Flu
• x
Gejala Flu
Demam < 37.5
Demam > 37.5
Bersin bersin
Sakit Tenggorokan
Batuk > 24 jam
Batuk > 48 jam
Sakit Kepala
Hidung Tersumbat
Proses Penalaran • Pasien demam kurang dari 37.5, jadi CF dari fakta demam <37.5 adalah 1.0 dan CF dari fakta demam >37.5 adalah -1.0. • Pasien batuk kurang dari 24 jam. Fakta batuk > 24 jam dan 48 jam, memberikan CF = -1.0 • CF dari gejala flu sebagai kesimpulan dari Rule 1 dihitung sebagai CF dari premis Rule 1 (bernilai 1.0) dikalikan dengan CF dari rule tersebut. Diperoleh: 1.0*0.5 = 0.5. • Karena premis Rule 2 negatif, Rule 2 tidak berpengaruh terhadap CF dari fakta gejala flu. • Karena premis dari Rule 3 dan Rule 4 bernilai negatif, CF sakit tenggorakan bernilai 0.
Proses Penalaran • CF dari Terkena flue sebagai kesimpulan Rule 5 merupakan hasil AND dua premis. Jadi, minimum antara CF gejala flu (0.5) dan bersin (1.0) dikalikan dengan CF Rule 5; CF1 = min{0.5, 1.0}*(-0.2) = 0.5*(-0.2)= -0.1 • Rule 7 juga mempunyai 2 premis. CF dari Rule 7menjadi CF2 = min{0.4, 0.5}*0.7 = ).4*0.7 = 0.28. • Berapa tingkat kepercayaan pasien terkena flu?
Pohon Inferensi & CF Terkait
Gejala Flu
Demam < 37.5
Demam > 37.5
Terkena Flu
Bersin bersin
Sakit Tenggorokan
Batuk > 24 jam
Batuk > 48 jam
Sakit Kepala
Hidung Tersumbat
Latihan • Diketahui bahwa hari ini Hujan, Curah hujan hari ini rendah (dengan CF 0.8), Temperatur hari ini dingin (dengan CF 0.9). Pakar harus memprediksi apakah cuaca besok. Basis pengetahuan berisi rules berikut: • Rule 1: IF Hari ini Hujan THEN Besok Hujan {CF=0.5} • Rule 2: IF Hari ini Kering THEN Besok Kering {CF=0.5} • Rule 3: IF Hari ini Hujan AND Curah Hujan Rendah THEN Besok Kering {CF=0.6}
Latihan • Rule 4:
• Rule 5:
• Rule 6:
IF Hari ini Hujan AND Curah Hujan Rendah AND Temperatur Dingin THEN Besok Kering {CF=0.7} IF Hari ini Kering AND Temperatur panas THEN Besok Hujan {CF=0.65} IF Hari ini Hujan AND Temperatur Panas AND Langit Mendung THEN Besok Hujan {CF=0.55}
