expert system

Expert System

Definisi Sistem Pakar (Expert System)

• Program komputer yang dirancang untuk memodelkan kemampuan menyelesaikan masalah seperti layaknya seorang pakar (human expert).

APA ITU PAKAR/AHLI (EXPERT) ?

Seorang pakar/ahli (human expert) adalah seorang individu yang memiliki kemampuan pemahaman yang superior terhadap suatu masalah tertentu.

Beberapa Definisi tentang Sistem Pakar

• Menurut DurkinSistem pakar adalah suatu program komputer yang dirancang untuk memodelkan kemampuan penyelesaian masalah yang dilakukan oleh seorang pakar.

• Menurut ignizioSistem pakar adalah suatu model dan prosedur yang berkaitan dalam suatu domain tertentu yang mana tingkat keahliannya dapat dibandingkan dengan keahlian seorang pakar.

• Menurut Giarratano dan RileySistem pakar adalah suatu sistem komputer yang bisa menyamai atau meniru kemampuan seorang pakar.

TUJUAN

Tools perangkat lunak yang dikembangkan memberikan keleluasaan pada perekayasa pengetahuan yang dibangun dari keseluruhan komponen Sistem Pakar dengan tujuan agar tools yang dibuat dapat digunakan untuk memecahkan persoalan yang spesifik.

Sejarah Sistem Pakar• Sistem pakar pertama kali dikembangkan oleh komunitas AI

pada pertengahan tahun 1960. Sistem pakar yang muncul pertama kali adalah General-purpose Problem Solver (GPS) yang dikembangkan oleh Newel and Simon. GPS (dan program-program yang serupa) ini mengalami kegagalan karena cakupannya terlalu luas sehingga terkadang justru meninggalkan pengetahuan-pengetahuan penting yang seharusnya disediakan.

Sistem Pakar yang terkenalSistem Pakar Kegunaan

Mycin Diagnosa penyakit

Dendral Mengidentifikasi struktur molekular campuran yang tak dikenal

Xcon & Xsel Membantu konfigurasi sistem komputer besar

Sophie Analisis sirkit elektronik

Prospector Digunakan di dalam geologi untuk membantu, mencari dan menemukan deposit

Folio Membantu memberikan keputusan bagi seorang manajer dalam hal stok broker dan investasi

Delta Pemeliharaan lokomotif listrik disel.

MYCIN• MYCIN was an early expert system developed over five or six years in

the early 1970s at Stanford University. It was written in Lisp as the doctoral dissertation of Edward Shortliffe under the direction of Bruce Buchanan, Stanley N. Cohen and others. It arose in the laboratory that had created the earlier Dendral expert system, but emphasized the use of judgmental rules that had elements of uncertainty (known as certainty factors) associated with them. This expert system was designed to identify bacteria causing severe infections, such as bacteremia and meningitis, and to recommend antibiotics, with the dosage adjusted for patient's body weight — the name derived from the antibiotics themselves, as many antibiotics have the suffix "-mycin". The Mycin system was also used for the diagnosis of blood clotting diseases.

Human Expert VS Expert System

Faktor Human Expert Expert SystemTime Availability Hari Kerja Setiap Saat

Geografis Lokal/Tertentu Dimana Saja

Keamanan Tidak Tergantikan Dapat Diganti

Dapat Habis Ya Tidak

Performa Variabel Konsisten

Kecepatan Variabel Konsisten & Cepat

Biaya Tinggi Terjangkau

Mengapa Sistem Pakar?

• Dapat menyediakan kepakaran setiap waktu dan lokasi

• Mampu bekerja secara otomatis tugas-tugas rutin yang tidak dapat dipenuhi setiap saat yang tidak dapat dilakukan oleh seorang pakar

• Lebih cepat, murah, efisien, dan handal dalam memecahkan masalah.

Human Expert Problem Solving

Expert System Problem Solving

• KNOWLEDGE BASE– Definisi : Bagian dari sistem pakar yang berisi domain

pengetahuan– Berisi pengetahuan yang dibutuhkan untuk memahami,

merumuskan dan menyelesaikan masalah.• WORKING MEMORY– Definisi : bagian dari sistem pakar yang berisi fakta-fakta

masalah yang ditemukan dalam suatu sesi– Berisi fakta-fakta tentang suatu masalah yang ditemukan

dalam proses konsultasi

• INFERENCE ENGINE– Definisi : Processor pada sistem pakar yang

mencocokan fakta-fakta yang ada pada working memori dengan domain pengetahuan yang terdapat pada knowledge base, untuk menarik kesimpulan dari masalah yang dihadapi.

– Proses berpikir pada manusia dimodelkan dalam sistem pakar pada modul yang disebut Inference Engine.

Sistem Pakar secara umum terdiri dari 3 bagian utama yaitu:• Knowledge Base = berisi informasi data,

aturan (rule), relasi antara data dan aturan dalam pengambilan kesimpulan.

· Inference Engine = berfungsi menganalisa data yang ada dan menarik kesimpulan berdasarkan aturan yang ada. · User Interface = berfungsi sebagai alat atau media komunikasi antara pemakai (user) dengan program.

Bagian-bagian Expert System

Knowledge Base

• Description of problem domain• Rules: A knowledge representation

technique– such as ‘IF:THEN’ logic– networks of rules

• Lowest levels provide evidence• Top levels produce 1 or more conclusions• A conclusion is called a Goal variable.

Evidence

Conclusion

Conclusion

Evidence Evidence Evidence Evidence

Evidence Evidence Evidence

Conclusion

A Rule Set That Produces One Final

Conclusion

Cheetah Tiger Giraffe Zebra Ostrich Penguin Albatross

And And And And And And And And

Tawnycolor Dark

spots legs Long Black

strips Long neck

Can’t fly

Black&White

Swims FliesWell

Ungulate Bird

Mammal Carnivore

Or Or And And FeathersAnd

Or Or

Hair milk milk Hoofs

Flies Lays

eggsChews Gives

And

teeth Pointed Forward

Eyes

LEGEND:

Rules

ConditionsAction

(conclusions)Claws

Eats milk cud

R1 R2 R5 R6

R9 R10 R11 R12 R14R13 R15

R7 R8 R3 R4

A Rule Set That Can Produce More Than One Final Conclusion

A small ES for diagnosing automotive problems

Ifthe engine is getting gas, andthe engine will turn over,thenthe problem is spark plugs

Ifthe engine does not turn over, andthe lights do not come onthen the problem is battery or cables

Ifthe engine does not turn over, andthe lights do come on,thenthe problem is the starter motor

Ifthere is gas in the fuel tank, andthere is gas in the carburetorthen the engine is getting gas

1

2

3

4

The and/or graphsearched in the car diagnosis example

The production system at the start of a consultation (it will be DFS)

The production system after Rule 1 has fired

The system after Rule 4 has fired. Note the stack-based approach to goal reduction

Explanation: Answering “why” questions• ES - Gas in fuel tank?

U- yesES- Gas in carburetor?U- yesES- Engine will turn over?U- why

• ES- It has been established that1. The engine is getting gas,therefore if2. The engine will turn over,then the problem is spark plugs.

• The user is asking “why is this information important?”

Explanation: Answering “how” questions

• U- how the engine is getting gas• ES- This follows from rule 4:

ifgas in fuel tank, andthere is gas in the carburetorthenthe engine is getting gas

gas in fuel tank was given by the usergas in the carburetor was given by the user

• The user is asking “How did the system come up with this conclusion?”

Forward chaining• Forward chaining merupakan grup dari multipel inferensi

yang melakukan pencarian dari suatu masalah kepada solusinya.

• Jika klausa premis sesuai dengan situasi (bernilai TRUE), maka proses akan meng-assert konklusi·

• Forward Chaining adalah data driven karena inferensi dimulai dengan informasi yg tersedia dan baru konklusi diperoleh

• Pendekatan goal-driven, dimulai dari ekspektasi apa yang diinginkan terjadi (hipotesis), kemudian mengecek pada sebab-sebab yang mendukung (ataupun kontradiktif) dari ekspektasi tersebut.

• Jika suatu aplikasi menghasilkan tree yang sempit dan cukup dalam, maka gunakan backward chaining.

BACKWARD CHAINING

Forward chaining

Match FireKnowledge Base

Database

A B C D E

X


Database

A B C D E

LX


Database

A C D E

YL

B

X


Database

A C D E

ZY

B

LX

Cycle 1 Cycle 2 Cycle 3

X & B & E YZY & D

LCL & M

A X

N

X & B & E YZY & D

LCL & M

A X

N

X & B & E YZY & D

LCL & M

A X

N

X & B & E YZY & D

LCL & M

A X

N

Rule 1

Rule 3

Rule 2

Rule 4

Rule 5

Rule 6

Rule 7

Rule 8

Rule 9

Rule 10

Rule 11

Rule 12

IF ATHEN B

IF CTHEN D

IF MTHEN E

IF KTHEN F

IF GTHEN H

IF ITHEN J

IF B OR DTHEN K

IF ETHEN L

IF K AND L THEN N

IF M THEN O

IF N OR OTHEN P

F

IF (F AND H)OR JTHEN M

The Forward

ReasoningProcess

T

TT

T

T

T

T

TT

F

T

Legend: First pass

Second pass

Third pass

Backward chaining


Database

A B C D E

X


Database

A C D E

YX

B

Sub-Goal: X Sub-Goal: Y

Knowledge Base

Database

A C D E

ZY

B

X

Match Fire

Goal: Z

Pass 2

Knowledge Base

Goal: Z

Knowledge Base

Sub-Goal: Y

Knowledge Base

Sub-Goal: X

Pass 1 Pass 3

Pass 5Pass 4 Pass 6

Database

A B C D E

Database

A B C D E

Database

B C D EA

YZ

?

X

?

X & B & E Y

LCL & M

A X

N

ZY & DX & B & E Y

ZY & D

LCL & M

A X

NLC

L & M N

X & B & E YZY & D

A X

X & B & E YZY & D

LCL & M

A X

N

X & B & E Y

LCL & M

A X

N

ZY & DX & B & E Y

ZY & D

LCL & M

A X

N

Conflict resolution• Rule 1:

IF the ‘traffic light’ is greenTHENthe action is go

• Rule 2:IF the ‘traffic light’ is redTHENthe action is stop

• Rule 3:IF the ‘traffic light’ is redTHENthe action is go

Rule 2 and Rule 3, with the same IF part. Thus both of them can be set to fire when the condition part is satisfied. These rules represent a conflict set. The inference engine must determine which rule to fire from such a set. A method for choosing a rule to fire when more than one rule can be fired in a given cycle is called conflict resolution.

• In forward chaining, BOTH rules would be fired. Rule 2 is fired first as the top most one, and as a result, its THEN part is executed and linguistic object action obtains value stop. However, Rule 3 is also fired because the condition part of this rule matches the fact ‘traffic light’ is red, which is still in the database. As a consequence, object action takes new value go.

Conflict resolution strategies• Use first rule whose condition is satisfied– Ordering is important

• Assign priorities to rules & use one with highest priority– How to decide on priority

Pemain utama dalam suatu proyek sistem pakar adalah:

• Domain Expert• Knowledge engineer• End-user

Domain expert

Definisi : orang yang memiliki ketrampilan(skill) dan pengetahuan (knowledge) untuk menyelesaikan masalah khusus dengan cara-cara yang superior dibanding orang kebanyakan.

Knowledge Engineer

Definisi : orang yang melakukan proses disain, mengembangkan dan menguji suatu sistem pakar

End-User

• Dapat membantu mendefinisikan spesifikasi interface

• Dapat membantu proses akuisisi pengetahuan

• Dapat membantu proses pengembangan sistem

Perbedaan pemrograman konvensional denganpengembangan Sistem Pakar

Inference Engine (Forward Chaining)• Forward Chaining : Pencocokan fakta atau pernyataan dimulai dari bagian

sebelah kiri (IF dulu). Dengan kata lain penalaran dimulai dari fakta terlebih dahulu untuk menguji kebenaran hipotesis.

No AturanR-1 IF A & B Then CR-2 IF C Then DR-3 IF A & E Then FR-4 IF A Then GR-5 IF F & G Then DR-6 IF G & E Then HR-7 IF C & H Then IR-8 IF I & A Then JR-9 IF G Then J

R-10 IF J Then K

Inference Engine (Forward Chaining)

• Terdapat 10 aturan yang tersimpan dalam basis pengetahuan.

• Fakta awal yang diberikan hanya A dan E (artinya A dan E bernilai benar). Ingin dibuktikan apakah K bernilai benar (hipotesis : K) ?

Inference Engine (Forward Chaining)• Langkah-langkah inferensi sbb :

– Dimulai dari R-1. A merupakan fakta sehingga bernilai benar, sedangkan B belum bisa diketahui kebenarannya, sehingga C-pun juga belum bisa diketahui kebenarannya. Oleh karena itu kita tidak mendapatkan informasi apapun pada R-1 ini. Sehingga kita menuju ke R-2.

– Pada R-2, kita tidak mengetahui informasi apapun tentang C, sehingga kita juga tidak bisa memastikan kebenaran D. Oleh karena itu kita tidak mendapatkan informasi apapun pada R-1 ini. Sehingga kita menuju ke R-3.

– Pada R-3, baik A maupun E adalah fakta sehingga jelas benar. Dengan demikian F sebagai konsekuen juga ikut benar. Sehingga sekarang kita mempunyai fakta baru yaitu F. Karena F bukan hipotesis yang hendak kita buktikan (=K), maka penelusuran kita lanjutkan ke R-4.

– Pada R-4, A adalah fakta sehingga jelas benar. Dengan demikian G sebagai konsekuen juga benar. Sehingga sekarang kita mempunyai fakta baru yaitu G. Karena G bukan hipotesis yang hendak kita buktikan (=K), maka penelusuran kita lanjutkan ke R-5.


– Pada R-5, baik F maupun G bernilai benar berdasarkan aturan R-3 dan R-4. Dengan demikian D sebagai konsekuen juga ikut benar. Sehingga sekarang kita mempunyai fakta baru yaitu D. Karena D bukan hipotesis yang hendak kita buktikan (=K), maka penelusuran kita lanjutkan ke R-6.

– Pada R-6, baik A maupun G adalah benar berdasarkan fakta dan R-4. Dengan demikian H sebagai konsekuen juga ikut benar. Sehingga sekarang kita mempunyai fakta baru yaitu H. Karena H bukan hipotesis yang hendak kita buktikan (=K), maka penelusuran kita lanjutkan ke R-7.

– Pada R-7, meskipun H benar berdasarkan R-6, namun kita tidak tahu kebenaran C, sehingga I-pun juga belum bisa diketahui kebenarannya. Oleh karena itu kita tidak mendapatkan informasi apapun pada R-7 ini. Sehingga kita menuju ke R-8.

– Pada R-8, meskipun A benar karena fakta, namun kita tidak tahu kebenaran I, sehingga J-pun juga belum bisa diketahui kebenarannya. Oleh karena itu kita tidak mendapatkan informasi apapun pada R-8 ini. Sehingga kita menuju ke R-9.


– Pada R-9 bernilai benar karena G benar berdasarkan R-4. Karena J bukan hipotesis yang hendak kita buktikan (=K), maka penelusuran kita lanjutkan ke R-10.

– Pada R-10, K bernilai benar karena J benar berdasarkan R-9. Karena H merupakan hipotesis yang hendak kita buktikan (=K) maka terbukti bahwa K adalah benar.

• Fakta baru Aturan Fakta BaruR-3 F

R-4 G

R-5 D

R-6 H

R-9 J

R-10 K

Inference Engine (Forward Chaining)

A

E

F

G

DH

J K

R-3

R-4

R-5

R-6

R-9 R-10

Inference Engine (Backward Chaining)

• Backward ChainingPencocokan fakta atau pernyataan di mulai dari bagian sebelah kanan (Then dulu). Dengan kata lain, penalaran dimulai dari hipotesis dahulu dan untuk menguji kebenaran hipotesis tersebut harus dicari fakta-fakta yang ada dalam basis pengetahuan.

• Contoh :Fakta awal yang diberikan hanya A dan E (artinya A dan E bernilai benar). Ingin dibuktikan apakah K bernilai benar (hipotesis : K) ?


• Langkah-langkah inferensi :– Pertama-tama kita cari terlebih dahulu mulai dari R-1 aturan mana

yang memiliki konsekuen K. Ternyata setelah ditelurusi, aturan dengan konsekuen K baru ditemukan pada R-10. Untuk membuktikan K benar, maka perlu dibuktikan bahwa J benar.

– Kita cari aturan yang memiliki konsekuen J. Kita mulai dari R-1 dan ternyata R-8 memiliki konsekuen J. Untuk membuktikan bahwa J benar, maka perlu dibuktikan bahwa I dan A benar. Untuk membuktikan kebenaran I, kita perlu cari aturan dengan konsekuen I ternyata ada di R-7.

– Untuk membuktikan I benar di R-7, kita perlu buktikan bahwa C dan H benar. Untuk itu kitapun perlu mencari aturan dengan konsekuen C dan ada di R-1.

Inference Engine (Backward Chaining)• Langkah-langkah inferensi :

– Untuk membuktikan C benar di R-1, kita perlu buktikan bahwa A dan B benar. A jelas benar karena A merupakan fakta. Sedangkan B tidak bisa dibuktikan kebenarannya karena selain bukan fakta, didalam basis pengetahuan juga tidak ada aturan dengan konsekuen B. Dengan demikian maka dari penalaran ini kita tidak bisa buktikan kebenaran dari hipotesis K. Namun demikian kita masih punya alternatif lain untuk melakukan penalaran.

– Kita lakukan backtracking lagi dengan mencari aturan dengan konsekuen I, ternyata juga tidak ada.

– Kita lakukan backtracking lagi dengan mencari aturan dengan konsekuen J, ternyata kita temukan pada R-9. Sehingga kita perlu buktikan kebenaran G.


• Kita mendapatkan R-4 dengan konsekuen G. Kita perlu buktikan kebenaran A. Karena A adalah fakta, maka terbukti bahwa G benar. Dengan demikian berdasarkan penalaran ini bisa dibuktikan bahwa K bernilai benar.


K

B

A

A H

J IR-10

R-1R-7

Fakta

CR-8

Tidak diketahui

K J GR-10R-4

Fakta

AR-9

Contoh• Diketahui sistem pakar dengan aturan-aturan sbb :

– 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, maka untuk memutuskan apakah akan membeli obligasi atau tidak dapat ditunjukkan sbb:

Forward Chaining• Dari fakta dolar turun, berdasarkan aturan 5 diperoleh konklusi suku

bunga naik. Dari aturan 2, suku bunga naik menyebabkan harga obligasi turun. Dengan aturan 6, jika harga obligasi turun maka kesimpulan yang diambil adalah membeli obligasi.

Dollar turun

Suku bunga naik

Harga obligasi turun

Beli obligasi

Backward Chaining• Berangkat dari solusi yaitu membeli obligasi dengan menggunakan aturan

6 diperoleh anteseden harga obligasi turun. Dari aturan 2 akan dibuktikan harga obligas turun bernilai benar jika suku bunga naik bernilai benar. Dari aturan 5 suku bunga naik memang bernilai benar karena diketahui fakta dollar turun.

Dollar turun

Suku bunga naik

Harga obligasi turun

Beli obligasi

Contoh Aplikasi(Diagnosis infeksi sistem gastro-usus)

Keterangan Gambar

Studi Kasus Bird

Studi Kasus Animal

• /* hypotheses to be tested */• hypothesize(cheetah) :- cheetah, !.• hypothesize(tiger) :- tiger, !.• hypothesize(giraffe) :- giraffe, !.• hypothesize(zebra) :- zebra, !.• hypothesize(ostrich) :- ostrich, !.• hypothesize(penguin) :- penguin, !.• hypothesize(albatross) :- albatross, !.• hypothesize(unknown). /* no diagnosis */

Studi Kasus Animal/* animal identification rules */cheetah :- mammal, carnivore, verify(has_tawny_color), verify(has_dark_spots).tiger :- mammal, carnivore, verify(has_tawny_color), verify(has_black_stripes).giraffe :- ungulate, verify(has_long_neck), verify(has_long_legs).zebra :- ungulate, verify(has_black_stripes).

ostrich :- bird, verify(does_not_fly), verify(has_long_neck).penguin :- bird, verify(does_not_fly), verify(swims), verify(is_black_and_white).albatross :- bird, verify(appears_in_story_Ancient_Mariner), verify(flys_well).

Studi Kasus Animal/* classification rules */mammal :- verify(has_hair), !.mammal :- verify(gives_milk).bird :- verify(has_feathers), !.bird :- verify(flys), verify(lays_eggs).carnivore :- verify(eats_meat), !.carnivore :- verify(has_pointed_teeth), verify(has_claws), verify(has_forward_eyes).ungulate :- mammal, verify(has_hooves), !.ungulate :- mammal, verify(chews_cud).

expert system

Documents