INTELEGENSI BUATAN Pertemuan 4,5 Representasi Pengetahuan
M. Miftakul Amin, M. Eng. e-mail: e mail:
[email protected] mmiftakulamin@gmail com website : http://mafisamin.web.ugm.ac.id
Jurusan Teknik Komputer Politeknik Negeri Sriwijaya Palembang 2014
Representasi p Pengetahuan g z
z
AI memiliki komponen pokok: 1 B 1. Basis i Pengetahuan, P t h d dan 2. Mesin Inferensi Basis p pengetahuan g merupakan p fakta-fakta suatu objek dalam domain yang telah ditentukan dan saling berhubungan satu dengan yang lain. Berisi: 1. Ide/gagasan, 2. Prosedur praktis dan saling berhubungan
Representasi p Pengetahuan g z
z
Mekanisme Inferensi adalah suatu rangkaian presedur (cara fikir) yang digunakan untuk menguji basis pengetahuan dengan cara yg sistematis dalam rangka menjawab pertanyaan, memecahkan persoalan (solusi) d atau dan t membuat b t keputusan. k t Basis Pengetahuan direpresentasikan dengan berbagai cara: Logika, Logika logika proposional, proposional Jaringan Semantik, Frame dan Skrip.
Model Representasi Pengetahuan z
Logika z Script z Frame F z Jaringan Semantik z Kaidah Produksi
Logika g z Logika
adalah serangkaian presedur yang membantu proses penalaran. l
Input Premis Fakta
Output
Prose Logika
Inferensi Konklusi
Logika g Proposisi p z
z z
Logika yang hanya mempunyai nilai benar dan salah. Pernyataan apa saja yang mempunyai nilai BENAR dan SALAH disebut proposisi. Logika proposisi disebut juga dengan Propositional Calculus. Proposisi dapat digabung menggunakan perangkai k i ((connectives) i ) sehingga hi di disebut b proposisi majemuk (Compound Propositions)
Perangkai g Logika g atau Operator p z
Dan (And) ^ z Atau (Or) V z Tidak/Bukan Tid k/B k (N (Not) t) ¬ z Jika …Maka…(If … then …) Æ z Jika dan hanya jika (if and only if) ÅÆ
Konjungsi j g ((^)) A
B
A^B
F
F
F
F
T
F
T
F
F
T
T
T
Disjungsi j g ((V)) A
B
AVB
F
F
F
F
T
T
T
F
T
T
T
T
Negasi g ((¬)) A
¬A A
¬¬A A
F
T
F
T
F
T
Implikasi p ((Æ)) A
B
AÆB
F
F
T
F
T
T
T
F
F
T
T
T
Ekuivalensi (ÅÆ) ( ) A
B
A ÅÆ B
F
F
T
F
T
F
T
F
F
T
T
T
Contoh z
A = Dewi Rajin Belajar z B = Dewi Lulus Ujian zC=D Dewii mendapat d th hadiah di h iistimewa ti Dalam ekspresi logika: AÆB^C (AÆ(B ^ C)) ((AÆB) ^ C)
Hirarki Simbol Perangkai g Hirarki Simbol Perangkai g Nama Perangkai g 1.
¬
Negasi
2.
^
Konjungsi
3 3.
V
Di j Disjungsi i
4.
Æ
Implikasi p
5.
ÅÆ
Ekuivalensi
Validitas Argumen g z
z z
Tautologi, jika pada tabel kebenaran untuk semua pasangan nilai variabel-variabel proposisional yang ada bernilai benar atau T, maka disebut tautologi. Kontradiksi, jika semua pasangan nilai dari tabel kebenaran menghasilkan nilai F. Contingent/mixed formulae, jika pasangan nilai d l dalam tabel b l kkebenaran b terdapat d nilai il i T d dan F F.
Reasoning/Penalaran g z
z
Jika ruang g masalah sangat g besar p penggunaan gg logic dan teknik penalaran akan lebih efisien dibanding penggunaan teknik searching. P d bagian Pada b i ini i i dibahas dib h teknik k ik penalaran l (reasoning), yakni teknik penyelesaian masalah dengan cara merepresentasikan masalah ke dalam basis pengetahuan (knowledge base) menggunakan logic atau b h bahasa fformall (b (bahasa h yang di dipahami h i oleh l h komputer).
Reasoning/Penalaran g z
Sistem akan mencoba untuk memberikan output berupa solusi dari suatu masalah berdasarkan kumpulan pengetahuan yang ada
Reasoning/Penalaran g z
z
Pembahasan difokuskan p pada tiga g buah logic g untuk merepresentasikan pengetahuan dan melakukan penalaran, yaitu: z Proportional P i lL Logic i z First Order Logic z Fuzzy F Logic L i Dua logic pertama digunakan untuk masalah yang memiliki kepastian kepastian, sedangkan fuzzy logic digunakan untuk menyelesaikan masalah yang memiliki ketidakpastian.
First Order Logic g ((FOL)) z Proportional
Logic mengalami masalah serius ketika menghadapi h d i masalah l h yang kompleks. p z First-Order Logic dapat merepresentasikan pengetahuan dengan lebih efisien.
Komponen p Penting g FOL z
Objects: sesuatu dengan identitas individual (people, houses, colors, …) z Properties: sifat yang membedakan dengan object yang lain (red, circle, …) z Relations: R l ti h b hubungan antar t object bj t (brother of, bigger than, part of, …) z Functions: relation yang mempunyai satu nilai (father of, best friend, …)
Tata bahasa FOL z
z z
z z z z z z
Sentence → AtomicSentence | Sentence S C Connective i Sentence S | Quantifier Variable, … Sentence | ¬ Sentence | (Sentence) AtomicSentence → Predicate(Term, …) | Term=Term Term → Function(Term, …) | Constant | Variable Connective → ∧ | ∨ | ⇔ | ⇒ Quantifier → ∀ | ∃ C t t → A | X1 | John Constant J h |… Variable → a | x | s | … Predicate → Before | HasColor | Raining | … Function → MotherOf | LeftLegOf | …
Penjelasan j FOL z z
z
Constant biasanya y dituliskan dalam huruf besar seperti: A, X1, Budi. Variable biasanya dituliskan dalam huruf kecil seperti: i a, x, s. Varibel V ib l iinii menyatakan k simbol i b l yang dapat digantikan oleh konstanta apapun. Predicate menyatakan relasi khusus dalam suatu model. Misalnya Berwarna adalah suatu predicate yang memiliki beberapa nilai. z
Contoh: Berwarna(Tasku, Hijau), Berwarna(Tasmu, Putih).
Penjelasan j z
Function menyatakan y relasi yyang g hanya y mempunyai p y satu nilai. z z
z
z
Karena setiap orang hanya punya satu ibu kandung, maka IbuKandung adalah suatu function. Misalnya, IbuKandung(Anawati, Budi).
Terms merupakan ekspresi logika yang mengacu pada sebuah objek. p j Terms bisa berupa p constant,, variable, atau function. Atomic sentences dapat dibentuk dari Predicate(Term …)) atau Term=Term. Predicate(Term, Term=Term z
Misalnya: Sepatu(Budi), Saudara(Andi, Budi), Memberi(Andi, Budi, KueCoklat), Saudara(Andi)=Budi.
Penjelasan j z
Complex p sentences merupakan p sentence yyang g dibangun dengan menggunakan connective. z
z
Contoh: Saudara(Andi, Budi) ⇒ Memberi(Andi, Budi, KueCoklat).
Universal quantifier (∀) menyatakan sesuatu yang bersifat umum. Simbol ∀ (huruf A terbalik) dibaca ‘For All’ ((untuk semua atau untuk setiap) p) z
z
Kalimat “Untuk setiap objek x, jika x adalah anak kecil maka x suka permen” dapat dituliskan sebagai: ∀x AnakKecil(x) ⇒ Suka(x, Permen). Kalimat ini benar jika dan hanya jika kalimat tersebut benar untuk semua konstanta di dalam Knowledge Base yang menggantikan variable x.
Penjelasan j z
Existential q quantifier (∃) ( ) menyatakan y sesuatu yyang g berlaku sebagian. Simbol ∃ (huruf E menghadap ke kiri) dibaca ‘There Exist’ (ada satu atau beberapa). z
z
Kalimat “Ada objek j x,, jjika x adalah anak kecil maka x suka permen” dapat ditulis sebagai: ∃x AnakKecil(x) ⇒ Suka(x, Permen).
Nested q quantifier digunakan g untuk menyatakan y kalimat kompleks yang menggunakan quantifier ganda. z
Misalkan: “Untuk Untuk semua x dan semua y, jika x adalah orang tua y maka y adalah anak dari x” dapat dinyatakan sebagai: ∀x,y OrangTua(x,y) ⇒ Anak(y,x)
Inferensi FOL z
z
Ketujuh aturan inferensi yang digunakan oleh proportional ti l llogic i d dapatt di digunakan k pada d Fi First-Order tOd Logic. Selain itu ada tiga aturan tambahan yang digunakan pada d Fi First-Order t O d Logic, L i yaitu: it 1.
Univeral Elimination: untuk setiap sentence α, variabel v, dan ground term (atau term yang tidak berisi variabel) g:
z
Dari ∀x Suka(x, Permen), dapat digunakan substitusi {x /Andi} dan melakukan inferensi Suka(Andi,Permen)
Inferensi FOL 2.
2. Existential Elimination: untuk setiap p sentence α, variabel v, dan simbol konstanta k yang tidak ada dalam basis pengetahuan:
z
Dari ∃x Saudara(x, Budi), dapat disimpulkan Saudara(Andi, Budi), selama Andi tidak ada di dalam basis pengetahuan.
Inferensi FOL 3.
3. Existential Introduction: untuk setiap sentence α, variabel v yang tidak terjadi pada α, dan ground term g yang terjadi pada α:
z
Dari Suka(Budi, Permen) dapat disimpulkan ∃x Suka(x,Permen)
Script p z
Script merupakan skema representasi pengetahuan yang menggambarkan urutan kejadian. kejadian Script merepresentasikan situasi, pengetahuan ataupun pengalaman pengetahuan, pengalaman.
Script p z 1.
2 2. 3.
4. 5. 6.
Script mempunyai beberapa elemen yang tipikal: Kondisi masukan menggambarkan situasi yang harus dipenuhi sebelum terjadi atau berlaku suatu peristiwa yang ada dalam script. Prop mengacu kepada objek yang digunakan dalam urutan peristiwa yang terjadi. Role mengacu kepada orang-orang yang terlibat dalam script. Hasilnya adalah kondisi yang ada sesudah peristiwa dalam script berlangsung. Track mengacu kepada variasi yang mungkin terjadi dalam script tertentu. Scene menggambarkan urutan peristiwa aktual yang terjadi. Hasil merupakan kondisi setelah urutan peristiwa dalam script terjadi terjadi.
Contoh Script p z
Jalur (track) : Restoran swalayan (fast food) z Peran (Roles) : Tamu pelayan z Pendukung (Prop) : counter, baki, makanan, k uang, serbet, b t garam, merica, i kecap, pipet, dll. z Kondisi : tamu lapar – tamu punya uang
Contoh Script p z z -
Adegan g ((Scene)) 1 : Masuk Tamu parkir mobil Tamu masuk restoran T Tamu antrii Tamu baca menu, dan memesan makanan Adegan 2 : Pesanan Tamu memberikan pesanan kepada pelayan Pelayan e aya mengambil e ga b pesa pesanan a da dan meletakkan e eta a makanan di atas baki Tamu membayar
Contoh Script p z z z -
Adegan g 3 : Makan Tamu mengambil serbet Tamu makan dengan g lahap p Adegan 4 : Pulang Tamu meninggalkan restoran Tamu naik mobil dan pulang Hasil Tamu kenyang Tamu senang
Frame/Bingkai g z
z
z
Bingkai merupakan kumpulan slot-slot yang berisi atribut untuk t k mendeskripsikan d k i ik pengetahuan. t h P Pengetahuan t h yang termuat dalam slot dapat berupa kejadian, lokasi, situasi ataupun elemen-elemen lainnya. Bingkai digunakan untuk representasi pengetahuan deklaratif. Bingkai memuat deskripsi sebuah objek dengan menggunakan tabulasi informasi yang berhubungan dengan obyek. Dengan demikian bingkai membantu menir kan cara seseorang mengorganisasikan informasi menirukan tentang sebuah obyek menjadi kumpulan data. Representasi pengetahuan menggunakan bingkai sesuai untuk jenis pengetahuan yang memiliki subyek sempit sempit, lebih bersifat pasti dan jarang berubah-ubah isinya kecuali terdapat kondisi khusus.
Contoh Frame
Jaringan g Semantic z
Jaringan semantik adalah teknik representasi pengetahuan yang digunakan untuk informasi proposisional proposisional, sedangkan yang dimaksud dengan informasi proposisional adalah pernyataan yang mempunyai nilai benar atau salah salah.
Jaringan g Semantic z
Representasi p jjaringan g semantik merupakan p penggambaran grafis dari pengetahuan yang memperlihatkan hubungan hirarkis dari obyekobyek. y Komponen p dasar untuk merepresentasikan pengetahuan dalam bentuk jaringan semantik adalah simpul (node) dan penghubung (link) (link). Obyek direpresentasikan oleh simpul. Hubungan antar obyek-obyek dinyatakan oleh penghubung yang diberi label untuk menyatakan hubungan yang direpresentasikan.
Contoh Jaringan g Semantic
Kaidah Produksi z
Kaidah menyediakan cara formal untuk merepresentasikan rekomendasi, arahan atau strategi. arahan, strategi Kaidah produksi dituliskan dalam bentuk jika – maka (ifthen) Kaidah if-then then). if then menghubungkan anteseden dengan konsekuensi yang diakibatkannya. diakibatkannya
Struktur Kaidah Produksi z z z z z z z z z
IF p premis THEN konklusi IF masukan THEN keluaran IF kondisi THEN tindakan IF anteseden THEN konsekuen IF data THEN hasil IF tindakan THEN tujuan IF aksi THEN reaksi IF sebab THEN akibat IF gejala THEN diagnosa
Contoh Kaidah Produksi IF mencari jadwal yang cocok AND peserta = jumlah peserta kuliah AND h harii = h harii kkuliah li h AND jam = jam kuliah THEN CALL jadwal AND SEND peserta peserta, hari hari, jam AND RETURN jadwal
