pengantar intelijensia buatan · forward chaining contoh kita mulai dengan kb yang mengandung...

50
Pengantar Intelijensia Buatan Pertemuan 14 FOL Reasoning & PROLOG

Upload: others

Post on 17-Dec-2020

4 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Pengantar Intelijensia Buatan

Pertemuan 14

FOL Reasoning & PROLOG

Page 2: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Previously on AI

Pengenalan FOL

Metode inferensi FOL

Masalah dengan inferensi ??

Page 3: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Topic for Today

Generalized Modus Ponens

Forward & backward Chaining

Resolution & Refutation

Introduction to PROLOG

Page 4: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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 :

),(

)..(,',....',' 2121

qSUBST

qpppppp nn

Page 5: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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)

Page 6: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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 pre-

compilation dengan menggubah semua kalimat di KB

dalam bentuk canonical form agar mudah untuk

diproses

Page 7: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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.

Page 8: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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.

Example : UNIFY(Knows(John, x), Knows(John, Jane) = {x/Jane}

),(),(,),( qSUBSTpwhereSUBSTqpUNIFY

Page 9: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Unification Algorithm

Page 10: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Sample proof revisited

erica)Country(Am

America),Enemy(Nono

no)Country(No

est)American(W

Hostile(x)America)Enemy(x,

Weapon(x)Missile(x)

x)Nono,,Sells(WestMissile(x)x)Owns(Nono,

)Missile(M1

M1)Owns(Nono,

)Criminal(xy)z,Sells(x, Country(z)Weapon(y))American(x

Page 11: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Constructing a reasoning program

Ada dua cara untuk menggunakan generalized modus ponens untuk membentuk reasoning program:

◦ Forward Chaining

◦ Backward Chaining

Page 12: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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

Page 13: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Forward chaining

Contoh

◦ Kita mulai dengan KB yang mengandung implikasi dalam

bentuk horn clause.

◦ Cari kemudian fakta yang dapat diunifikasikan ke

dalamnya.

Hostile(x)America)Enemy(x,

Weapon(x)Missile(x)

x)Nono,,Sells(WestMissile(x)x)Owns(Nono,

)Criminal(xy)z,Sells(x,Hostile(z) Country(z)Weapon(y))American(x

Page 14: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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)

Page 15: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Forward chaining Criminal(West)

Weapon(M1) Sells(West,Nono,M1)

Missile(M1) American(West)

Hostile(Nono)

Owns(Nono,M1) Enemy(Nono, America)

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))

Country(Nono)

Page 16: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Forward Chaining

Page 17: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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

Page 18: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Backward Chaining

Criminal(x)

American(x) Weapon(y) Country(z) Sells(x,z,y) Hostile(z)

Yes{x/West}

Missile(y)

Yes{y/M1t}

Enemy(z,America)

Yes{z/nono}

Yes{z/Nono}

Owns(Nono,M1) Missile(M1)

Yes{} Yes{}

Page 19: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Backward Chaining

Page 20: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Backward Chaining

Criminal(x)

Weapon(y) Country(z) Sells(x,z,y) Hostile(America)

Yes {x/West}

Missile(y)

Yes {y/M1t}

Yes {z/America} failed

American(x)

Page 21: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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.

Page 22: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Inference resolution rule ?

,

,

Page 23: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Resolution inference

Untuk mencari solusi menggunakan

resolusi kita harus mengubah KB menjadi

bentuk Conjunctive Normal Form (CNF)

atau Implicative Normal Form (INF).

Page 24: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Generalized resolution (disjunction)

nk

mj

qqq

ppp

.......

.......

1

1

)..............,( 111111 nkkmjj qqqqppppSUBST

Page 25: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Generalized resolution

(implication)

4nk13n1

2n11nj1

q....q...qs....s

r...rp....p...p

)..........

..........,(

11121

31111

nkkn

nmjj

qqqqrr

ssppppSUBST

Page 26: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Example of resolution

Anggaplah kita memiliki KB berikut :

Kita ingin membuktikan S(A) adalah true

S(x)R(x)x,

S(x)Q(x)x,

R(x)P(x)x,

Q(x)P(x)x,

Page 27: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Example of resolution

S(y)P(y)

S(y)P(y)

)()( xRxP

)()(

)()(

zSzR

zSzR

Q(w)P(w)

Q(w)P(w)

)()(

)()(

ySyQ

ySyQ

)()( xRxS

)(zStrue

Apply:

-elemination

Apply: elem

Apply: elem, resolution

Apply: Resolution

Page 28: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Refutation

Chaining dengan resolusi lebih baik dari GMP

namun tetap tidak complete

Cobalah menyelesaikan masalah ini dengan

resolution dalam sebuah KB kosong :

Prosedur inferensi yang totally complete adalah

refutation

)()( xPxP

Page 29: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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

PKBfalsePKB )(

Page 30: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Refutation example

falsezS )(

)()( ySyP )()( xRxPtrue

)()( zSzR

)()( wQwP )()( ySyQ

)()( xRxStrue

)(zStrue

falsetrue

Rules Facts

Page 31: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Conversion to Normal Form

Page 32: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Conversion to Normal Form

Page 33: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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 ?

Page 34: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

FOL

Animal(x)Cat(x)x,

Cat(Tuna)

Tuna)osity,Kills(CuriTuna),Kills(Jack

falsey)Kills(x,Animal(y)r(x)AnimalLovex,

r(y)AnimalLoveDog(x))x)Owns(y,x,(y,

Dog(x)x)Owns(Jack,x,

Page 35: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Implicative Normal Form

Animal(x)Cat(x)

Cat(Tuna)

Tuna)osity,Kills(CuriTuna),Kills(Jack

falsey)Kills(x,Animal(y)r(x)AnimalLove

r(x)AnimalLovey)Owns(x,Dog(y)

D)Owns(Jack,

Dog(D)

Page 36: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Refutation ?

Dog (D) Dog (y) Owns(x,y) AnimalLover(x)

Owns(x,D) AnimalLover(x) Owns(Jack,D)

AnimalLover(Jack)

Page 37: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Refutation

)(TunaCat )()( xAnimalxCat

falsexyKillsxAnimalyrAnimalLove ),()()(

)(TunaAnimal

falseTunaxKillsyrAnimalLove ),()(

Page 38: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Refutation

falseTunaxKillsyrAnimalLove ),()( )(JackrAnimalLove

falseTunaJackKills ),(

Page 39: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Refutation

False

falseTunaCuriosityKills ),(),(

),(

TunaCuriosityKills

TunaJackKills

falseTunaJackKills ),( ),( TunaJackKills

Page 40: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke
Page 41: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Another resolution example

Page 42: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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

Page 43: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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

student Name

Hans Tina Lars Frida

Prolog notation:

student(hans).

student(tina).

student(lars).

student(frida).

interest Name

Hans Tina Lars Frida

Prolog notation:

interest(hans,math).

interest(tina,datalogi).

interest(lars,physics).

interest(frida,math).

Math

Physics

Subject

Datalogi

Math

Prolog notation:

<predicate_name>(arg1, arg2…).

Page 44: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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).

Page 45: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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!

Page 46: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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: s(a).

2: s(b).

3: q(a).

4: p(X) :- s(X).

5: p(Y) :- q(Y).

?- p(Z).

p(Z)

s(Z) 4 5

1 2

Z=a Z=b Z=a

q(Z) 3

Page 47: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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:

HX

BC

EBH

CFH

CAE

facts

prove

BA,

X

X

H

F&C B&E

F C

B

B E

A C

B

OR

AND AND

AND

1

2

3

4

5

Page 48: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

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

Page 49: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke
Page 50: Pengantar Intelijensia Buatan · Forward chaining Contoh Kita mulai dengan KB yang mengandung implikasi dalam bentuk horn clause. Cari kemudian fakta yang dapat diunifikasikan ke

Latihan FOL (2)

Gunakan FOL ini menjadi bentuk CNF

Buktikan : Rich(Me) dengan refutation.

)()(,

)()(,

)()(,

)()(,

xRichxngEarlyEarnix

xRichxifiedHighlyQualx

xngEarlyEarnixPHDx

xQualifiedxPHDx