Download - 5 - Inference (1)
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