Pengantar Intelijensia Buatan. Pertemuan 14 FOL Reasoning & PROLOG

Pengantar Intelijensia Buatan Pertemuan 14 FOL Reasoning & PROLOG

Previously on AI Pengenalan FOL  Metode inferensi FOL  Masalah dengan inferensi ?? 

Topic for Today Generalized Modus Ponens  Forward & backward Chaining  Resolution & Refutation  Introduction to PROLOG 

Generalized modus ponens Generalized modus ponens menggabungkan and introduction, universal elimination, dan modus ponens menjadi satu aksi.  Untuk setiap atomic sentence p1’,p2’, dan q , dimana terdapat subtitution Ө sehingga SUBST(Ө,p1’)=SUBST(Ө,p1), untuk semua i : 

p1 ' , p2 ' ,....pn ' , ( p1  p2  ..  pn  q) SUBST ( , q)

Generalized modus ponens 

Contoh : ◦ ◦ ◦ ◦

P1’ is Missile(M1)  P1 is Missile(x) P2’ is Owns(y,M1)  P2 is Owns(nono,x) Ө is {x/M1,y/nono}  q is Sells(west,nono,x) Then SUBST(Ө,q) is Sells (west,nono,M1)

Generalized modus ponens Generalized modus ponens adalah metode inferensi yang efisien karena 3 alasan :

1.

GMP mereduksi 3 langkah inferensi yang kecil menjadi satu langkah yang besar.

2.

Daripada menggunakan universal elimination GMP mengambil langkah yang masuk akal dengan menggunakan subtitusi yang dijamin menguntungkan

3.

Agar lebih efisien GMP menggunakan langkah precompilation dengan menggubah semua kalimat di KB dalam bentuk canonical form agar mudah untuk diproses

Canonical form Dalam GMP semua kalimat dalam KB harus berupa atomic sentence atau sebuah implikasi dengan konjungsi di sebelah kiri dan sebuah kalimat atomic di sebelah kanan  Bentuk seperti ini disebut juga horn sentences atau canonical form.  Kita harus menggubah semua kalimat yang masuk ke dalam KB ke dalam bentuk canonical. 

Unification 

Unification adalah bagian yang penting dalam GMP, unification mengambil dua kalimat dan mengembalikan sebuah subtitusi yang membuat dua kalimat itu sama apabila subtitusi seperti itu memungkinkan.

UNIFY ( p, q)   , whereSUBST ( , p)  SUBST ( , q) Example : UNIFY(Knows(John, x), Knows(John, Jane) = {x/Jane}

Unification Algorithm

Sample proof revisited American(x )  Weapon(y)  Country(z)  Sells(x, z, y)  Criminal(x ) Owns(Nono, M1) Missile(M1 ) Owns(Nono, x)  Missile(x)  Sells(West , Nono, x) Missile(x)  Weapon(x) Enemy(x, America)  Hostile(x) American(W est) Country(Nono) Enemy(Nono, America) Country(America)

Constructing a reasoning program 

Ada dua cara untuk menggunakan generalized modus ponens untuk membentuk reasoning program: ◦ Forward Chaining ◦ Backward Chaining

Forward Chaining. Forward Chaining dilakukan ketika sebuah fakta baru (anggap saja p1) dimasukan ke dalam KB  Idenya adalah mencari semua implikasi yang mungkin terjadi dengan p1 sebagai premis, ketika suatu implikasi sudah ditemukan, implikasi itu mentrigger kembali forward chaining, sampai akhirnya semua fakta yang bisa ditemukan dikeluarkan 

Forward chaining 

Contoh ◦ Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. ◦ Cari kemudian fakta yang dapat diunifikasikan ke dalamnya.

American(x )  Weapon(y)  Country(z)  Hostile(z)  Sells(x, z, y)  Criminal(x ) Owns(Nono, x)  Missile(x)  Sells(West , Nono, x) Missile(x)  Weapon(x) Enemy(x, America)  Hostile(x)

Forward chaining 



Forward chaining secara bertahap membentuk gambaran baru akan dunia bersamaan dengan penerimaan data, forward chaining tidak diarahkan untuk menyelesaikan suatu permasalahan tertentu, karenanya metoda ini disebut juga data-driven atau data-directed procedure. Forward chaining dapat menghasilkan banyak kesimpulan yang pada akhirnya tidak digunakan (sia-sia)

Forward chaining Criminal(West)

American(West)

Weapon(M1)

Sells(West,Nono,M1)

Missile(M1)

Owns(Nono,M1)

FOL-FC-ASK(KB, American(West)) FOL-FC-ASK(KB, Country(Nono)) FOL-FC-ASK(KB, Enemy(Nono, America)) FOL-FC-ASK(KB, Hostile(Nono)) FOL-FC-ASK(KB, Owns(Nono,M1)) FOL-FC-ASK(KB, Missile(M1)) FOL-FC-ASK(KB, Sells(West,Nono,M1)) FOL-FC-ASK(KB, Weapon(M1)) FOL-FC-ASK(KB, Criminal(West))

Hostile(Nono)

Enemy(Nono, America)

Country(Nono)

Forward Chaining

Backward Chaining Backward chaining di desain untuk menemukan semua jawaban atas pertanyaan yang diajukan kepada knowledge base.  Cara kerjanya adalah dengan memeriksa apakah jawaban dapat dihasilkan secara langsung dari knowledge base, lalu ia mencari semua implikasi yang kesimpulannya adalah jawaban dari pertanyaan dan kemudian berusaha untuk memenuhi semua premis yang membentuk implikasi tersebut 

Backward Chaining Criminal(x)

American(x)

Weapon(y)

Yes{x/West}

Country(z)

Hostile(z)

Sells(x,z,y)

Yes{z/nono} Missile(y)

Enemy(z,America)

Yes{y/M1t}

Yes{z/Nono}

Owns(Nono,M1) Yes{}

Missile(M1) Yes{}

Backward Chaining

Backward Chaining Criminal(x)

American(x)

Weapon(y)

Yes {x/West}

Country(z) Yes {z/America}

Missile(y) Yes {y/M1t}

Hostile(America) failed

Sells(x,z,y)

Resolution Generalized modus ponens tidak complete, masih ada beberapa kalimat benar yang tidak bisa diinferensi oleh prosedur ini.  Untuk mengatasi masalah ini kita menggunakan metode resolusi, prosedure inferensi yang lebih complete. 

Inference resolution rule ?

   ,         ,      

Resolution inference 

Untuk mencari solusi menggunakan resolusi kita harus mengubah KB menjadi bentuk Conjunctive Normal Form (CNF) atau Implicative Normal Form (INF).

Generalized resolution (disjunction) p1  ...  p j  .... pm q1  ...  qk  .... qn SUBST ( , p1  ... p j 1  p j 1  .... pm  q1  ... qk 1  qk 1  .... qn )

Generalized resolution (implication) p1  ...  p j  ....  pn1  r1  ...rn2 s1  ....  s n3  q1  ...  qk  ....  qn 4 SUBST ( , p1  ...  p j 1  p j 1  ....  pm  s1  ...  sn 3  r1  ...rn 2  q1  ...  qk 1  qk 1  .... qn )

Example of resolution 

Anggaplah kita memiliki KB berikut :

x, P(x)  Q(x) x, P(x)  R(x) x, Q(x)  S(x) x,R(x)  S(x) 

Kita ingin membuktikan S(A) adalah true

Example of resolution Q ( y )  S ( y ) Apply: -elemination Q ( y )  S ( y )

P(w)  Q(w) P(w)  Q(w)

Apply:  elem, resolution Apply:  elem

P(y)  S(y) P(y)  S(y)

P( x)  R( x)

S ( x)  R( x)

R( z )  S ( z ) R ( z )  S ( z )

Apply: Resolution

true  S (z )

Refutation Chaining dengan resolusi lebih baik dari GMP namun tetap tidak complete  Cobalah menyelesaikan masalah ini dengan resolution dalam sebuah KB kosong : 

P( x)  P( x) 

Prosedur inferensi yang totally complete adalah refutation

Refutation Refutation adalah pembuktian berdasarkan kontradiksi atau reductio ad absurdum  Idenya adalah untuk membuktikan P itu benar, maka kita asumsikan bahwa P itu salah (tambahkan ~P ke KB) dan buktikan bahwa suatu kontradiksi terjadi (true => false, false => true). Jika suatu kontradiksi terjadi maka P dikatakan terbukti benar 

( KB  P  false)  KB  P

Refutation example Rules

P( w)  Q( w)

P( y )  S ( y )

Q( y )  S ( y )

true  P( x)  R( x)

true  S ( x)  R( x)

R( z )  S ( z )

true  S (z )

S ( z )  false

true  false

Facts

Conversion to Normal Form

Conversion to Normal Form

Example proof of refutation 

   

Jack owns a dog Every dog owner is an animal lover No animal lover kills animal Either jack or curiosity killed the cat, who is named tuna Did “curiosity” kill the cat ? / Who kills the cat ?

FOL x, Owns(Jack, x)  Dog(x) y, (x, Owns(y, x)  Dog(x))  AnimalLove r(y) x, AnimalLove r(x)  Animal(y)  Kills(x, y)  false Kills(Jack , Tuna)  Kills(Curi osity, Tuna) Cat(Tuna) x, Cat(x)  Animal(x)

Implicative Normal Form Dog(D) Owns(Jack, D) Dog(y)  Owns(x, y)  AnimalLove r(x) AnimalLove r(x)  Animal(y)  Kills(x, y)  false Kills(Jack , Tuna)  Kills(Curi osity, Tuna) Cat(Tuna) Cat(x)  Animal(x)

Refutation ? Dog (D)

Dog (y)  Owns(x,y) AnimalLover(x)

Owns(x,D) AnimalLover(x)

Owns(Jack,D)

AnimalLover(Jack)

Refutation AnimalLover ( y)  Animal( x)  Kills( y, x)  false Cat (Tuna)

Cat ( x)  Animal( x) Animal(Tuna )

AnimalLover ( y)  Kills( x, Tuna )  false

Refutation AnimalLover ( y)  Kills( x, Tuna )  false

AnimalLover (Jack )

Kills( Jack , Tuna )  false

Refutation Kills( Jack , Tuna )  Kills(Curiosity, Tuna )

Kills( Jack , Tuna )  false

Kills(Curiosity, Tuna)  false

Kills( Jack , Tuna)

False

Another resolution example

Introduction to prolog PROLOG = “Programmation en logique” (Marseille, 1972) Declarative programming language with procedural elements Used for problems of AI / knowledge-based (expert) systems Motivation: reconcile use of logic as declarative knowledge representation with procedural representation of knowledge Strengths: Logical descriptions of problems, instead of HOW to solve them  let computer work out the solution Well-suited for problems involving search Simple programs can be understood by reading the code Limitations Flow of control / procedural semantics

Facts Prolog-program = collection of clauses Facts Rules Goals (queries), shaped liked facts Facts describe properties of objects and relations between objects; comparable to tables in a relational database Name

student

interest

Name

Hans Tina Lars Frida Prolog notation: student(hans). student(tina). student(lars). student(frida).

Prolog notation: interest(hans,math). interest(tina,datalogi). interest(lars,physics). interest(frida,math).

Hans Tina Lars Frida

Subject

Math Datalogi Physics Math

Prolog notation: <predicate_name>(arg1, arg2…).

Rules Simple IF-THEN statements “Every reasonable student is interested in math.” interest(X,math) :- student(X). head

body

All specified conditions in the body (all clauses) must be true to make the predicate in the head true. Conjunctions (AND connected): mother(X,Person) :- parent(X,Person),sex(X,female). Disjunctions (OR connected): interest(X,prolog) :- interest(X,artificial_intelligence). interest(X,prolog) :- interest(X,logic).

Goals Goals are queries One ore more subgoals ?- student(thomas). => no Pattern matching: a fact matches a goal if Same predicate Same corresponding arguments. Goals can contain variables: ?- student(X). => X = hans ; => X = tina ; => X = lars ; => X = frida ; => no. Variables are instantiated, but cannot be declared!

Prolog’s Inference mechanism Leftmost-depth-first search for solutions Matching: either two terms are identical, or they become identical by variable substitution (resolution based on pred.logic) Processing of subgoals from left to right Backtracking 1: 2: 3: 4: 5: ?- p(Z).

1 Z=a

s(Z)

s(a). s(b). q(a). p(X) :- s(X). p(Y) :- q(Y). p(Z) 5

4 2

Z=b

q(Z)

3 Z=a

Backward Chaining the Prolog interpreter uses backward chaining: starting from a goal (theorem) prove the goal by searching for rules whose ”head” (action part) matches the goal Given are the following rules: 1 E  AC X

2 H  F C 3 H BE

H

4 CB 5 X H

F&C

B&E

facts

AND

AND

prove

A, B X

OR

F

C

B

E AND

B

A

C B

Latihan Inferensi dan Refutasi FOL (1)  

Buktikan bahwa “Marcus membenci Caesar” Facts ◦ ◦ ◦ ◦



Marcus adalah seorang manusia Marcus orang Pompei Marcus mencoba membunuh Caesar Caesar adalah seorang penguasa

Rules

◦ Semua orang Pompei adalah orang Romawi ◦ Semua orang Romawi setia pada Caesar atau membenci Caesar ◦ Setiap orang setia pada minimal 1 orang ◦ Orang hanya mencoba membunuh penguasa yang kepadanya mereka tidak setia

Latihan FOL (2) Gunakan FOL ini menjadi bentuk CNF x, PHD( x)  Qualified( x) x, PHD( x)  EarlyEarning ( x) x, HighlyQualified( x)  Rich( x) x, EarlyEarning ( x)  Rich( x)

Buktikan : Rich(Me) dengan refutation.