INFERENCE

Artificial IntelligenceJurusan Teknik Informatika

Universitas Komputer

---------------------------Nelly Indriani Widiastuti

Proses untuk menghasilkan informasi  dari  fakta  yang diketahui.

Merupakan◦ proses inferensi dilakukan dalam suatu modul

yang disebut inference  engine◦ Inference engine berisi program tentang

bagaimana mengendalikan proses reasoning.◦ bentuk untuk mengekstrak implikasi suatu

pengetahuan

Inference ?

3 jenis inferensi secara logik:

1) Deduksi 2) Induksi 3) Abduction (abduction)

Jenis inferensi yang lain◦ Intuisi ◦ Heuristik◦ Generate and Test

Types of Logic

Inferensi (penarikan kesimpulan) dengan penalaran dari yang umum ke yang khusus

Misal : Modus Ponen Contoh 1:

◦ A = Udara Cerah◦ B = Kita akan pergi ke pantai◦ A→B = Jika udara cerah, maka kita pergi ke pantai◦ Dengan menggunakan Modus Ponen, kesimpulan adalah

“Kita akan pergi ke Pantai” Contoh 2:

◦ Semua kucing merupakan anggota feline ◦ Bootsy adalah seekor kucing◦ Kesimpulan : Bootsy merupakan anggota feline

Deduksi

Inferensi dengan penalaran dari yang khusus (fakta-fakta) ke yang umum

Menebak dari yang sudah ada dan dari gejala yang terjadi Formatnya:

◦ X = {a,b,c,d,...}, if property P is true for a, and if P is true for b,

and if P is true for c,..., then P is true for all X

Contoh:◦ Semua kucing Siamese pada pertunjukan kucing 1986

mempunyai mata biru ◦ Semua kucing Siamese pada pertunjukan kucing 1987

mempunyai mata biru◦ Kesimpulan : Semua kucing Siamese pada pertunjukan

kucing 1988 mempunyai mata biru

Induksi

Bentuk deduksi yang hanya menghasikan inferensi yang masuk akal (plausible inference)

Plausible berarti bahwa konklusi mungkin bisa mengikuti informasi yang tersedia, tetapi juga bisa salah.

Formatnya:◦ if Y is true and X implies Y , then X is true ?

Contoh:◦ Implikasi : Tanah menjadi basah jika terjadi hujan◦ Aksioma : Tanah menjadi basah◦ Konklusi : Apakah terjadi hujan?

Abduksi

Tipe inferensi yang terjadi tanpa dilandasi oleh teori. Kesimpulan muncul karena pola yang ada secara tidak disadari.

Intuition

Kesimpulan yang diambil berdasarkan pengalaman

Contoh : ◦ Algoritma pencarian A*

Heuristik

Kesimpulan ditentukan dengan trial dan error. Solusi dibuat kemudian diuji untuk melihat apakah solusi yg diajukan memenuhi semua persyaratan. Jika solusi memenuhi maka berhenti yang lain membuat solusi yang baru kemudian test lagi dst.

Generate & Test

Sintak◦ Bagaimana membuat kalimat dalam bentuk logika◦ Simbol-simbol apa yang dapat digunakan (misal: huruf,

pemberian tanda baca, dll) Semantics

◦ Bagiamana menterjemahkan (membaca) kalimat yang berbentuk logika

◦ Apa makna dari kalimat yang berbentuk logika Prosedur inferensi

◦ Bagaimana mengambil kesimpulan. Contoh : “Semua mahasiswa adalah lulusan SMU”

◦ Dari bentuk kalimat benar (syntax)◦ Dapat diketahui maknanya (semantics)◦ Kalimat tersebut bisa bermakna salah.

Sintak dan Semantik

Logika argumen yang merupakan kumpulan pernyataan-pernyataan yang dinyatakan untuk dibenarkan sebagai dasar dari rantai penalaran.

Silogisme dapat direpresentasikan ke dalam bentuk aturan IF… THEN…

Contoh :IF siapapun yang dapat membuat program adalah

pintarAND John dapat membuat programMAKA John adalah pintar

Silogisme

Bentuk Skema Arti A Semua S adalah P Universal AfirmativeE Tidak S adalah P Universal NegativeI Beberapa S adalah P Particular AfirmativeO Beberapa S bukan P Particular Negative

Silogisme - bentuk

Subjek dari konklusi S disebut bagian minor bila predikat konklusi P adalah bagian mayor. Premis terdiri dari premis mayor dan premis minor.Contoh :

Premis mayor : semua M adalah PPremis minor : semua S adalah MKonklusi : semua S adalah P

Figure 1 Figure 2 Figure 3 Figure 4Premis Mayor MP PM MP PMPremis Minor SM SM MS MS

Silogisme - struktur S-P-M

Contoh :Semua M adalah PSemua S adalah M Semua S adalah PMenunjukkan suatu mood AAA-1

validitas suatu argumen diperlukan prosedur keputusan.

Prosedur keputusan untuk silogisme dapat dilakukan menggunakan diagram venn tiga lingkaran yang saling berpotongan yang merepresentasikan S,P dan M.

Silogisme - menentukan Validitas

Mengubah bentuk proposisi -> formula Contoh :

Jika ada daya listrik, komputer akan bekerjaAda dayakomputer akan bekerja

Jika : A = ada daya listrik B = komputer akan bekerja

Sehingga dapat ditulis :A→BA B

Kaidah Inferensi

Bentuk Skema Representasi Predikat

A Semua S adalah P (x) (S(x)P(x))

E Tidak S adalah P (x) (S(x)~P(x))

I Beberapa S adalah P (x) (S(x)P(x))

O Beberapa S bukan P (x) (S(x)~P(x))

First Order LogicRepresentasi 4 kategori silogisme menggunakan logika predikat

Contoh :Misal, merupakan fungsi proposisi :

(x) (x) (a)

a : menunjukkan spesifik individualX : variabel yang berada dalam jangkauan semua individu (universal)

All men are mortalSocrates is a manTherefore, Socrates is mortal

Misal : H = man, M = mortal, s = Socrates(x) (H (x) M(x))H(s) / M(s)H(s) M(s) 1 Universal

InstatiationM(s) Modus Ponens

Contoh pembuktian

kumpulan objek seperti kaidah (rule), aksioma, statement dan lainnya yang diatur dalam cara yang konsisten.

Tujuan :◦ Menentukan bentuk◦ Menunjukkan kaidah◦ Mengembangkan kaidah yang sesuai

Sistem Logika

Membutuhkan 1. simbol alfabet.2. suatu set finite string dari simbol tertentu, wff3. aksioma, definisi dari sistem4. kaidah inferensi, yang memungkinkan wff

sistem logika dapat didefinisikan menggunakan modus pones untuk diturunkan menjadi teorema baru.

Sistem Formal

Jika terdapat argumen : A1, A2, ……., AN; A

yang valid, maka A disebut teorema dari sistem logika formal dan ditulis dengan simbol (metasymbol) yang menunjukkan wff adalah suatu teorema .

A1, A2, ……., AN A

Contoh : teorema silogisme tentang Socrates yang ditulis dalam bentuk logika predikat.

(x) (H (x)M(x)), H(s) M(s)

Sistem Formal (cont’d)

Suatu wff disebut konsisten atau satifiable jika interpretasi yang dihasilkan benar, dan disebut inkonsisten atau unsatisfiable jika wff menghasilkan nilai yang salah pada semua interpretasi.

Sistem Formal (cont’d)

Lebih ekspresif daripada propositional logic

Sintak◦ konstanta, variabel, dan fungsi term◦ predikat, dan quantifier kalimat

Semantik◦ Bagaimana mengartikan kalimat◦ Bagaimana menterjemahkan ke bahasa lain◦ Bagaimana kebenaran kalimat

Jadi, dapat mengatakan sesuatu benar untuk semua objek (universal) Ataudapat mengatakan sesuatu benar untuk setidaknya satu objek (existential)

Predikat Logika (Predicate Logic)

Konstanta◦ Misal: A, B, C, Dessy, Abdul, dll◦ Menyatakan suatu objek tertentu

Predikat◦ Adalah Menyatakan suatu relasi diantara objek

(model: konstanta, variabel dan fungsi)◦ Argumen (argument) : sesuatu yang direlasikan◦ Aritas (arity) : banyaknya sesuatu yang

direlasikan◦ Misal : Ayah(Abdul,Dessy)

Sintak (konstanta dan Predikat)

Fungsi◦ Predikat khusus◦ Mempunyai input dan ouput◦ Jika aritasnya n, maka n-1 argumen pertama

adalah input, dan argumen yang terakhir adalah output

◦ Mempunyai sekumpulan input, dengan satu output uniq

◦ Gunakan tanda samadengan (=)◦ Misal : harga buku AI di Toga Mas adalah 50 ribu

harga(buku_AI, Toga_Mas,50000) Karena harga adalah fungsi, maka harga(buku_AI, Toga_Mas) = 50000

Sintak (Fungsi)

Untuk menyatakan beberapa objek sebagai satu simbol.

Contoh:◦ harga buku Fuzzy di Toga Mas adalah 70 ribu

harga(buku_Fuzzy, Toga_Mas,70000) misal buku-buku diberi simbol variabel X, maka harga(X, Toga_Mas) = 70000

◦ Ternyata menghasilkan kalimat yang salah, maka ∃ X (harga(X,Toga_Mas) = 70000)

◦ Ternyata masih kurang tepat

Sintak (Variabel)

Untuk menyatakan penegasan/penajaman suatu kalimat

∀ (universal quantifier)◦ Menyatakan keseluruhan, atau setiap objek◦ Contoh: semua mahasiswa mengerjakan soal AI

∀ X (mahasiswa(X) → mengerjakan(X,soal_ai))

∃ (existensial quantifier)◦ Menyatakan beberapa objek◦ Contoh: terdapat mahasiswa mengerjakan soal AI

∃ X (mahasiswa(X) → mengerjakan(X,soal_ai))

Sintak (Quantifier)

kaidah inferensi utama dalam bahasa PROLOG

“quantifier-free”. didasarkan pada logika predikat urutan

pertama wff harus berada dalam bentuk normal

atau standard. Tiga tipe utama bentuk normal :

conjunctive normal form, clausal form dan subset Horn clause.

Resolusi

conjunctive normal form(A B) (~B C)

Full clause formA1, A2, ……., AN B1, B2, ……., BM

Clause yang ditulis dalam notasi standard :A1 A2, ……., AN B1 B2, ……., BM

Untuk membuktikan benar, digunakan metode klasik reductio ad absurdum atau metode kontradiksi.

Contoh

Tujuan dasar resolusi adalah membuat infer klausa baru yang disebut “revolvent” dari dua klausa lain yang disebut parent clause.

Cont’d

Parent Clause Resolvent Arti

p q , p atau ~p q, p Q Modus Pones

p q , q r atau~p q, ~ q r

p r atau~p r

Chaining atau Silogisme Hipotesis

~p q, p q Q Penggabungan

~p ~q, p q ~p p atau ~q q TRUE (tautology)

~p, p Nill FALSE (kontradiksi)

Refutation adalah pembuktian teorema dengan menunjukkan negasi atau pembuktian kontradiksi melalui reductio ad absurdum. Melakukan refute berarti membuktikan kesalahan.

Sistem Resolusi Dan Deduksi

(~A B) (~B C) (~C D) A ~D Dituliskan menjadi

Akar bernilai nill, menunjukkan kontradiksi sehingga melalui refutation dapat ditunjukkan konklusi asli (awal) adalah teorema dengan peran kontradiksi.

Contoh :

~A V B

~B V C

~C V D

A

~D

~A V C

~A V D

D

nill

Pohon Resolusi Refutation

Suatu rantai yang dicari atau dilewati/dilintasi dari suatu permasalahan untuk memperoleh solusi.

Penalaran dari fakta menuju konklusi yang terdapat dari fakta.

Forward Chaining

Perencanaan, monitoring, kontrol

Disajkan untuk masa depan

Antecedent ke konsekuen

Data memandu, penalaran dari bawah ke atas

Bekerja ke depan untuk mendapatkan solusi apa yang mengikuti fakta

Breadth first search dimudahkan

Antecedent menentukan pencarian

Penjelasan tidak difasilitasi

Sifat forward chaining

Contoh Kasus Sistem Pakar: Penasihat Keuangan Kasus : apakah tepat jika dia berinvestasi pada

stock IBM? Variabel-variabel yang digunakan:

◦ A = memiliki uang $10.000 untuk investasi◦ B = berusia < 30 tahun◦ C = tingkat pendidikan pada level college◦ D = pendapatan minimum pertahun $40.000◦ E = investasi pada bidang Sekuritas (Asuransi)◦ F = investasi pada saham pertumbuhan (growth

stock)◦ G = investasi pada saham IBM

Setiap variabel dapat bernilai TRUE atau FALSE

FAKTA YANG ADA: Diasumsikan investor memiliki data:

◦ Memiliki uang $10.000 (A TRUE)◦ Berusia 25 tahun (B TRUE)

Apakah tepat jika berinvestasi pada IBM stock? RULES

◦ R1 : IF seseorang memiliki uang $10.000 untuk berinvestasi AND dia berpendidikan pada level college THEN dia harus berinvestasi pada bidang sekuritas

◦ R2 : IF seseorang memiliki pendapatan pertahun min $40.000 AND dia berpendidikan pada level college THEN dia harus berinvestasi pada saham pertumbuhan (growth stocks)

FAKTA YANG ADA: R3 : IF seseorang berusia < 30 tahun AND dia

berinvestasi pada bidang sekuritas THEN dia sebaiknya berinvestasi pada saham pertumbuhan

R4 : IF seseorang berusia < 30 tahun dan > 22 tahun THEN dia berpendidikan college

R5 : IF seseorang ingin berinvestasi pada saham pertumbuhan THEN saham yang dipilih adalah saham IBM.

Rule simplification: – R1: IF A and C, THEN E – R2: IF D and C, THEN F – R3: IF B and E, THEN F – R4: IF B, THEN C – R5: IF F, THEN G

Solusi dengan Forward Chaining

Solusi dengan Backward Chaining