MAKALAH SISTEM BERBASIS PENGETAHUAN
METODE INFERENSI
Disusun Oleh :
1. Elian Sandy (12113859)
2. Mochammad Panji Purnama (15113564)
3. Yuditya Dwi Saputra (12345678)
SISTEM INFORMASI
FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI
UNIVERSITAS GUNADARMA
2015
KATA PENGANTAR
Puji syukur kami ucapkan kehadirat Allah SWT, yang telah memberikan
Rahmat dan HidayahNya, sehingga penyusun dapat menyelesaikan makalah yang
berjudul “Metode Inferensi”. Makalah ini dibuat dengan tujuan untuk
menambah pengetahuan penyusun dan untuk memenuhi tugas mata kuliah Sistem
Berbasis Pengetahuan. Demi kesempurnaan makalah ini, penyusun mohon kritik dan
saran dari pembaca yang bersifat membangun.
Demikianlah makalah ini saya buat semoga dapat bermanfaat bagi para
pembaca semua, apabila ada kekurangan mohon maaf sebesar-besarnya.
Bekasi, 13 November 2015
Hormat Kami,
Penyusun
Metode
Inferensi
I.
TREES. LATTICE dan GRAPH
Tree
(pohon) adalah suatu hierarki struktur yang terdiri dari Node (simpul/veteks) yang menyimpan informasi atau pengetahuan dan
cabang (link/edge) yang menghubungkan node. Binary tree mempunyai 0,1 atau 2
cabang per-node.
o
Node tertinggi disebut root
o
Node terendah disebut daun
Tree merupakan tipe khusus dari jaringan semantic, yang setiap nodenya
kecuali akar, mempunyai satu node orang tua dan mempunyai nol atau lebih node
anak. Tree adalah kasus khusus dalam Graph. Graph dapat mempunyai nol atau
lebih link di antara node dan tidak ada perbedaan antara orangtua dan anak.
Dalam graph, link dapat ditunjukkan berupa panah atau arah yang
memadukan node dan bobot yang merupakan karakteristik beberapa aspek dari link.
Beberapa
contoh graph sederhana:
II.
SPASI STATA dan SPASI PERMASALAHAN
STATE SPACE
State
adalah kumpulan karakteristik yg dapat digunakan untuk menentukan status.
State
Space adalah rangkaian pernyataan yg menunjukkan transisi antara state dimana
objek dieksprerimen
III.
AND-OR TREE dan GOALS
Dalam
SP, untuk menemukan solusi problem dapat menggunakan rangkaian backward yaitu
dengan tree AND-OR dan AND-OR-NOT
-
Banyak tipe system pakar
menggunakan backward chaining untuk
mendapatkan solusi dari permasalahan.
-
Salah satu tipe dari tree atau lattice
yang digunakan dalam masalah representasi backward
chaining adalah Pohon AND-OR.
- LOGIKA DEDUKTIF DAN SYLLOGISMS
Tipe-tipe
Inferensi
a.
Deduction
Pemberian alasan logikal dimana kesimpulan harus mengikuti premis
b.
Induction
Inferensi dari khusus ke umum
c.
Intuition
Tidak
ada teori yg menjamin. Jawabannya hanya muncul, mungkin dengan penentuan pola
yg ada secara tidak disadari.
d.
Heuristic
Aturan yg didasarkan pada pengalaman
e.
Generate
& Test
Trial dan error. Digunakan dgn perencanaan.
f.
Abduction
Pemberian alasan kembali dari kesimpulan yg benar ke premis .
g.
Default
Diasumsikan pengetahuan umum sebagai default
h.
Autoepistemic
Self-knowledge
i.
Nonmonotonic
Pengetahuan yg sebelumnya mungkin tdk benar jika bukti baru didapatkan
j.
Analogy
Kesimpulan yg berdasarkan pada persamaan untuk situasi yg lainnya.
Suatu
logika argument adalah kumpulan dari pernyataan-pernyataan yang dinyatakan
untuk dibenarkan sebagai dasar dari rantai penalaran. Salah satu jenis logika
argunen adalah Silogisme.
Penalaran
deduktif umumnya terdiri dari tiga bagian : premis mayor, premis minor
dan konklusi. Premis disebut juga antecedent Konklusi/kesimpulan disebut juga consequent. Silogisme dapat direpresentasikan ke
dalam bentuk aturan JIKA…..MAKA….. (IF…THEN…..),
Contoh
:
JIKA siapapun yang dapat membuat Robot adalah pintar
DAN Jono dapat membuat robot
MAKA Jono adalah pintar
Silogisme
klasik disebut categoricall syllogism (silogisme yang pasti). Premis dan
konklusi didefinisikan sebagai statement yang pasti dari empat bentuk berikut :
Bentuk
|
Skema
|
Arti
|
A
|
Semua S adalah P
|
Universal
Afirmative
|
E
|
Tidak S adalah P
|
Universal
Negative
|
I
|
Beberapa S adalah
P
|
Particular
Afirmative
|
O
|
Beberapa S bukan
P
|
ParticularNegative
|
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 P
Premis
minor : Semua S adalah M
Konklusi : Semua S adalah P
Silogisme
di atas adalah bentuk standar karena premis mayor dan minor sudah diketahui.
Contoh
:
“Semua
mikrokomputer adalah computer”
Subjeknya (objek yang digambarkan) adalah mikrokomputer.
Predikatnya
(beberapa sifat subjek) adalah computer
M
(middle term) adalah hal yang penting karena silogisme didefinisikan sedemikian
sehingga konklusi tidak dapat disimpulkan dengan mengambil salah satu premis.
Q
(quantifier) menggambarkan porsi dari kelas yang diketahui.
o
Quantifier “semua” dan “tidak”
adalah universal karean menunjukkan keseluruhan kelas.
o
“beberapa” adalah khusus
(particular) karena hanya menunjukkan satu bagian dari kelas yang diketahui.
Mood
dari silogisme didefinisikan sebagai tiga huruf yang memberikan bentuk
masing-masing premis mayor, minor dan konklusi.
Contoh
:
Semua M
adalah P
Semua S adalah M
\Semua S
adalah P
menunjukkan
suatu mood AAA-1
Figure
1
|
Figure
2
|
Figure
3
|
Figure
4
|
|
Premis Mayor
|
MP
|
PM
|
MP
|
PM
|
Premis Minor
|
SM
|
SM
|
MS
|
MS
|
Tidak
selalu argument yang mempunyai bentuk silogisme merupakan silogisme yang valid.
Contoh
: Silogisme tidak valid berbentuk AEE-1
Semua
M adalah P
Tidak
S adalah M
\Tidak S
adalah P
Semua
mikrokomputer adalah computer
Bukan
mainframe adalah mikrokomputer
\Bukan
mainframe adalah computer
Diperlukan
prosedur keputusan (decision procedure)
untuk pembuktian validitas. Prosedur keputusan untuk silogisme dapat dilakukan
menggunakan diagram venn tiga lingkaran yang saling berpotongan yang
merepresentasikan S,P, M.
Contoh
: Prosedur Keputusan untuk AEE-1
Semua
M adalah P
Tidak
S adalah M
\Tidak S
adalah P
|
a. Diagram Venn
|
|
b. Setelah Premis Mayor
|
|
c. Setelah Premis Minor
|
-
Contoh : Prosedur Keputusan untuk
EAE-1
Tidak
M adalah P
Semua S adalah M
\Tidak S
adalah P
|
a. Diagram Venn
|
|
b. Setelah Premis Mayor
|
|
c. Setelah Premis Minor
|
V.
ATURAN DARI INFERENSI
Diagram Venn tidak sesuai untuk argumen yang lebih kompleks karena
sulit dibaca pada decision tree untuk silogisme. ogika proposisi memberikan
pengertian lain dari penggambaran argumen.
Contoh :
Jika ada
daya listrik, komputer akan bekerja
A = ada
daya listrik
B =
komputer akan bekerja
Sehingga dapat ditulis :
AÃ B
A
Bentuk umum Ponens / direct reasoning / law of detachment / assuming the
antecedent
pà q
p atau pà q, p; \ q
Bentuk
tersebut valid, karena argumen tersebut dapat ditunjukkan sebagai suatu tautologi.
((pà q)Ùp) à q
Tabel Kebenaran Ponens :
p
|
q
|
pà q
|
((pà q)Ùp)
|
((pà q)Ùp) à q
|
T
|
T
|
T
|
T
|
T
|
T
|
F
|
F
|
F
|
T
|
F
|
T
|
T
|
F
|
T
|
F
|
F
|
T
|
F
|
T
|
Terdapat
argumen yang menyerupai ponens namun perlu dibuktikan validitasnya.
Contoh
:
Jika tidak
kesalahan maka program dapat mengkompile
Program
dapat mengkompile
\ Tidak ada
kesalahan
pà q
q atau pà q, q; \ p
Tabel Kebenaran:
p
|
q
|
pà q
|
((pà q)Ùq)
|
((pà q)Ùq) à p
|
T
|
T
|
T
|
T
|
T
|
T
|
F
|
F
|
F
|
T
|
F
|
T
|
T
|
T
|
F
|
F
|
F
|
T
|
F
|
T
|
(Bukan
Pones karena tidak bersifat Tautology)
Skema
argumen lain :
pà q
~q
Tabel Kebenaran:
p
|
q
|
pà q
|
~q
|
(pà q)Ù~q)
|
~p
|
((pà q)Ù~q) à ~p
|
T
|
T
|
T
|
F
|
F
|
F
|
T
|
T
|
F
|
F
|
T
|
F
|
F
|
T
|
F
|
T
|
T
|
F
|
F
|
T
|
T
|
F
|
F
|
T
|
T
|
T
|
T
|
T
|
Argumen
di atas disebut Tollens / indirect reasoning / law of contraposition.
VI.
LOGIKA PEMBATASAN DARI PROPORSIONAL
Perhatikan argument klasik yang kita
kenal ini :
Semua Pria
adalah Ayah
Roni adalah Pria______________
Roni adalah
AYah
Kita tahu
bahwa argument tersebut adalah argumen
valid jika berupa syllogism valid. Dapatkah kita membuktikan ke-valid-an
tersebut dengan menggunakan logika proporsional?
Untuk menjawab pertanyaan ini, pertama
kali kita menuliskan argument sebagian skema
Sehingga skema argument adalah :
Perhatikan
bahwa tidak ada hubungan di dalam premises atau kesimpulan sehingga setiap
premises dan setiap kesimpulan harus mempunyai variable logical yang berbeda.
Juga , logika preposisional tidak mempunyai provisi untuk quantifier sehingga
tidak ada cara untuk menunjukkan
quantifier “semua“ di dalam premise pertama. Satu-satunya representasi argument
ini di dalam logoka proporsional adalah di atas dari tiga variable yang bebas.
Untuk
menentukan argument tersebut valid, erhatikan table kebenaran dari tiga
variable bebas untuk keseluruhan kemungkinan kombinasi dari T dan F yang
ditunjukkan dalam table berikut :
Tabel Kebenaran untuk skema p,q;
p
|
q
|
r
|
T
T
T
T
F
F
F
F
|
T
T
F
F
T
T
F
F
|
T
F
T
F
T
F
T
F
|
Baris kedua dari table benar ini
menunjukkan argumen untuk tidak valid karena premises benar sementara
kesimpulan salah.
Validitas
dari argumen ini harus “tidak” diinteprestasikan seperti arti kesimpulan yang
tidak benar. Seseorang akan menentukannya sebagai argumen yang benar,
Ketidak-valid-an sederhana berarti bahwa “argument tidak dapat dibuktikan
dibawah logika proporsional”. Misalnya, kita akan memberi atribut pada beberapa
arti “semua” dan mempertimbangkan “men” sebagai bentuk jaman dari “man”. Namun
demikian, syllogism dan kalkulus proporsional tidak memungkinkan struktur
preposisi internal untuk diuji. Batasan ini dibatasi oleh logika predikat dan
argumen valid di bawah logika predikat. Kenyataannya, seluruh logika
syllogistic merupakan subset yang valid
dari order pertama logika predikat dana dapat dibuktikan dengan valid
dibawahnya.
Satu-satunya bentuk syllogistic yang
valid dari preposisi adalah :
Jika roni
adalah Pria, kemudian Roni adalah Ayah.
Roni adalah Pria__________
Roni adalah Ayah
Lihat :
p = Roni adalah Pria
q = Roni adalah Ayah
Argumen ini akan menjadi :
VII.
LOGIKA PREDIKAT ORDER PERTAMA KALI
Representasi
4 kategori silogisme menggunakan logika predikat
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))
|
Kaidah
Universal Instatiation merupakan state dasar, dimana suatu individual dapat
digantikan (disubsitusi) ke dalam sifat universal.
Contoh
:
Misal,
f merupakan fungsi proposisi :
("x) f(x)
merupakan
bentuk yang valid, dimana a menunjukkan spesifik individual, sedangkan x adalah
suatu variabel yang berada dalam jangkauan semua individu (universal)
Contoh
lain : ("x) H(x)
Berikut
ini adalah contoh pembuktian formal silogisme:
Semua Pria
adalah Ayah
Roni adalah
Pria
VIII.
SISTEM LOGIKA
Sistem
logika adalah kumpulan objek seperti kaidah (rule), aksioma, statement dan
lainnya yang diatur dalam cara yang konsisten.
Sistem logika mempunyai beberapa tujuan :
1.
Menentukan bentuk argumen.
Awalnya
argumen logika tidak memiliki arti dalam semantic sense, bentuk yang valid pada
dasarnya dapat dicapai jika validitas dari argumen tersebut dapat ditentukan.
Fungsi
terpenting dari logika sistem adalah menentukan well formed formulas (wffs) dari argumen yang digunakan.
All S is P …..
merupakan wffs
tapi…. All
All is S P ….. bukan wffs
Is S all
2.
Menunjukkan kaidah inferensi yang
valid.
3.
Mengembangkan dirinya sendiri
dengan menemukan kaidah baru inferensi dan memperluas jangkauan argumen yang
dapat dibuktikan.
Sistem
logika dibangun melalui Sentential atau kalkulus proposisi, kalkulus predikat
dst.
Setiap
sistem disandarkan pada aksioma atau
postulat, yang merupakan definisi mendasar
dari sistem. Suatu aksioma merupakan fakta sederhana atau assertion yang tidak dapat
dibuktikan dalam sistem. Terkadang, kita menerima aksioma dikarenakan ada
sesuatu yang menarik atau melalui pengamatan.
Sistem
formal membutuhkan :
1.
simbol alfabet.
2.
suatu set finite string dari
simbol tertentu, wffs
3.
aksioma, definisi dari sistem
4.
kaidah inferensi, yang
memungkinkan wffs, A untuk dikurangi sebagai kesimpulan dari set finite G wff lain
dimana G = {A1,A2,…An}. Wffs harus berupa aksioma atau teori lain dari sistem
logis. Sebagai contoh : sistem logika dapat didefinisikan menggunakan modus
pones untuk diturunkan menjadi teorema baru.
Jika
terdapat argumen :
A1, A2, ……., AN; \ A
A1, A2,
……., AN A
Contoh
: teorema silogisme tentang Socrates yang ditulis dalam bentuk logika predikat.
("x) (H (x)Ã M(x)), H(s)
M(s)
M(s)
dapat dibuktikan dari aksioma di sisi kiri, hal tersebut menunjukkan aksioma
Teorema
dengan tautology ditulis dengan symbol , misalnya
A.
Contoh
:
Jika A º p Ú ~p maka p Ú ~p
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.
IX.
RESOLUSI, SISTEM RESOLUSI dan DEDUKSI
Refutation adalah pembuktian teorema dengan menunjukkan negasi atau pembuktian
kontradiksi melalui reductio ad absurdum. Melakukan refute berarti membuktikan
kesalahan.
Contoh
:
A Ã B
B Ã C
C Ã D
Untuk
membuktikan konklusi A Ã D adalah suatu teorema melalui
resolusi refutation, hal yang dilakukan :
p à q º ~p Ú q
sehingga
Aà D º ~A Ú D
dan
langkah terakhir adalah melakukan negasi
~(~A Ú D) º A Ù ~D
Penggunaan
konjungsi dari disjunctive form pada premis dan negasi pada konsklusi,
memberikan conjuctive normal form yang cocok untuk resolusi refutation.
Dari
contoh di atas, penulisannya menjadi :
(~A Ú B) Ù (~B Ú C) Ù (~C Ú D) Ù A Ù ~D
Akar
bernilai nill, menunjukkan kontradiksi. Sehingga melalui refutation dapat
ditunjukkan konklusi asli (awal) adalah teorema
dengan peran kontradiksi.
X.
SHALLOW DAN CASUAL REASONING
Sistem pakar menggunakan rantai inferensi, dimana rantai yang panjang merepresentasikan
lebih banyak causal atau pengetahuan
yang mendalam. Sedangkan shallow
umumnya menggunakan kaidah tunggal atau inferensi yang sedikit.
Kualitas inferensi juga faktor utama dalam penentuan
kedalaman dan pendangkalan dari penalaran.
Shallow knowledge disebut juga experiment
knowledge.
IF a car
has
a good battery
good sparkplugs conditional elements
gas
good tires
THEN the
car can move
Pada
penalaran shallow, tidak ada atau hanya terdapat sedikit pemahaman dari subjek,
dikarenakan tidak ada atau hanya terdapat sedikit rantai inferensi.
Keuntungan
dari penalaran shallow :
ü Kemudahan dalam pemograman, yang berarti waktu pengembangan program
menjadi singkat,
ü program menjadi lebih kecil,
ü lebih cepat
ü biaya pengembangan menjadi murah.
XI.
RANGKAIAN FORWARD DAN BACKWARD
Chain
(rantai) : perkalian inferensi yang menghubung-kan suatu permasalahan dengan
solusinya.
Forward chaining :
ü
Suatu rantai yang dicari atau
dilewati/dilintasi dari suatu permasalahan untuk memperoleh solusi.
ü
Penalaran dari fakta menuju
konklusi yang terdapat dari fakta.
Backward chaining :
ü
Suatu rantai yang dilintasi dari
suatu hipotesa kembali ke fakta yang mendukung hipotesa tersebut.
ü
Tujuan yang dapat dipenuhi dengan
pemenuhan sub tujuannya.
Contoh
rantai inferensi :
gajah(x) Ã mamalia (x)
mamalia(x) Ã binatang(x)
·
Causal (sebab-akibat) Forward chain
gajah(clyde)
binatang(clyde)
·
Explicit Causal chain
unifikasi
Karakteristik Forward dan
Backward chaining
Forward chaining
|
Backward chaining
|
Perencanaan,
monitoring, kontrol
|
Diagnosis
|
Disajkan untuk
masa depan
|
Disajikan untuk
masa lalu
|
Antecedent ke
konsekuen
|
Konsekuen ke
antecedent
|
Data memandu,
penalaran dari bawah ke atas
|
Tujuan memandu,
penalaran dari atas ke bawah
|
Bekerja ke depan
untuk mendapatkan solusi apa yang mengikuti fakta
|
Bekerja ke
belakang untuk mendapatkan fakta yang mendukung hipotesis
|
Breadth first search
dimudahkan
|
Depth first search dimudahkan
|
Antecedent menentukan
pencarian
|
Konsekuen menentukan pencarian
|
Penjelasan tidak
difasilitasi
|
Penjelasan
difasilitasi
|
ü
Forward Chaining
ü
Backward Chaining
XII.
METODE LAIN DARI INFERENSI
ANALOGI
Mencoba
dan menghubungkan situasi lama sebagai penuntun ke situasi baru.
Contoh
: diagnosis medical (gejala penyakit yang diderita oleh seorang pasien ternyata
sama dengan gejala yang dialami pasien lain).
Pemberian
alasan analogis berhubungan dgn induksi. Bila induksi membuat inferensi dari
spesifik ke umum pada situasi yang sama, maka analogy membuat inferensi dari
situasi yang tidak sama.
GENERATE AND TEST
Pembuatan
solusi kemudian pengetesan untuk melihat apakah solusi yg diajukan memenuhi
semua persyaratan. Jika solusi memenuhi maka berhenti yg lain membuat sollusi
yg baru kemudian test lagi dst.
Contoh
: Dendral, prog AM ( artificial Mathematician), Mycin
ABDUCTION/PENGAMBILAN
Metodenya mirip dengan modus ponens
Abduction Modus
ponens
p
à q p à q
q p
\ p \ q
Bukan
argument deduksi yang valid. Berguna untuk kaidah inferensi heuristik. Analogi,generate and test, abduction adalah
metode bukan deduksi. Dari premise yg benar, metode ini tidak dapat membuktikan
kesimpulan yg benar
Perbedaan Forward Chaining,
Backward Chaining dan Abduction
Inference
|
Start
|
Tujuan
|
FORWARD
BACKWARD
ABDUCTION
|
Fakta
Kesimpulan tdk
pasti
Kesimpulan benar
|
Kesimpulan yang
harus mengikuti
Fakta pendukung
kesimpulan
Fakta yang dapat
mengikuti
|
NONMONOTONIC REASONING
Adanya
tambahan aksioma baru pada sistem logika berarti akan banyak teorema yang dapat
dibuktikan. Peningkatan teorema dengan peningkatan aksioma dikenal dengan sistem
monotonik. Suatu masalah dapat terjadi, jika diperkenalkan aksioma
parsial atau komplit baru yang kontradikasi dengan aksioma sebelumnya. Pada sistem nonmonotonik, tidak perlu adanya
peningkatan teorema yang sejalan dengan peningkatan aksioma.
XIII.
METAKNOWLEDGE
Program
meta-DENDRAL menggunakan induksi untuk menyimpulkan baris baru dari struktur
kimia.
Contoh : TEIRESIAS yg menambah pengetahuan
secara interaktif dari expert
