Representasi Pengetahuan

1.       Arti Pengetahuan

Pengetahuan adalah Informasi yang telah diproses dan diorganisasikan untuk memperoleh pemahaman, pembelajaran dan pengalaman yang terakumulasi sehingga bisa diaplikasikan ke dalam masalah/proses bisnis tertentu .

Informasi yang diproses untuk mengekstrak implikasi kritis dan merefleksikan pengalaman masa lampau menyediakan penerima dengan pengetahuan yang terorganisasi dengan nilai yang tinggi.

Pengetahuan dapat juga diartikan sebagai gejala yang ditemui dan diperoleh manusia melalui pengamatan akal. Pada saat seseorang memakai akal budinya untuk mengenali suatu kejadian tertentu yang belum pernah dirasakan sebelumnya itu dapat meunculkan sebuah Pengetahuan. Contoh Pengetahuan: Seseorang yang mencicipi buah yang belum pernah dimakannya, maka orang tersebut akan memperolah pengetahuan yaitu tentang rasa, bentuk, ukuran, nama buah.

Pada dasarnya pengetahuan mempunyai kemampuan prediktif/ perkiraan terhadap sesuatu sebagai hasil dari pengenalan suatu bentuk/ pola. Data dan Informasi terkadang dapat membingungkan seseorang, maka pengetahuanlah yang mengarahkan tindakan.

2.       Produksi

Pengetahuan dalam kaidah produksi direpresentasikan dalam bentuk

       JIKA [kondisi] MAKA [Aksi]

       JIKA [premis] MAKA [Konklusi]

Aturan Produksi (kaidah produksi) adalah salah satu representasi pengetahuan yang menghubungkan premis dengan konklusi.

Bentuknya: If Premis Then Konklusi

Konklusi pada bagian then bernilai benar jika premis pada bagian if bernilai benar.

Contoh:

If  hari ini hujan then saya tidak kuliah.

3.       Jaringan Semantik

Jaringan semantik merupakan model memori manusia yang dibangun oleh M. R. Quillian sebagai representasi grafis dari informasi proposisional. Informasi proposisional adalah pernyataan yang dapat bernilai benar atau salah. Jaringan semantik ini disajikan dalam bentuk graf berarah.

Berikut ini adalah contoh sebuah jaringan semantik :

Informasi proposisional  yang membentuk  jaringan semantik di atas adalah :

a.       Dessi makan donat

b.      Donat bentuknya bulat

c.       Dessi punya adik namanya sendi

d.      Sendi pergi sekolah naik motor

e.      Sendi pergi sekolah membawa bola

f.        Dessi bermain bola

g.       Bola bentuknya bulat

h.      Motor membutuhkan bensin

i.         Pom bensin menyediakan bensin

j.        Sendi punya rumah dekat pom bensin

4.       Triple Obyek-Atribut-Nilai

Bentuk object-attribute-value triple daapat digunakan untuk mempresentasikan semua karakteristik pengetahuan dalam semantic net dan digunakan pada sistem pakar MYCIN untuk mendiagnosa penykit infeksi.

5.       Schemata : Frame dan Script

Frame :

·         Frame (Minsky, 1975) dipandang sebagai struktur data static yang digunakan untuk merepsentasi-kan situasi-situasi yang telah dipahami dan stereotype.

·         Frame digunakan untuk merepresentasikan pengetahuan stereotype atau pengetahuan yang didasarkan kepada karakteristik yang sudah dikenal yang merupakan pengalaman masa lalu.

·         Frame berupa kumpulan slot-slot (representasi entitas sebagai struktru objek) yang merupakan atribut untuk mendeskripsikan pengetahuan berupa kejadian, lokasi, situasi ataupun elemen-elemen lain. Frame digunakan untuk representasi pengetahuan deklaratif.

Contoh :

-          Frame Pohon

Spesialisasi dari: Tumbuhan

Jumlah batang: integer (default 1)

Jenis kulit: halus

Model daun: jenis pohon jarum, berganti daun

Bentuk daun: sederhana, berlekuk, campuran

-          Frame Pohon Perdu

Spesialisasi dari: Pohon

Jumlah batang: 3

Jenis kulit: halus

Model daun: berganti daun

Bentuk daun: sederhana, berlekuk

·         Setiap frame individual dapat dipandang sebagai struktur data yang mirip record, berisi informasi yang relevan dengan entitas-entitas stereotype. Slot-slot dalam frame dapat berisi:

-          Informasi identifikasi frame

-          Hubungan frame dengan frame lain

-          Penggambaran persyaratan yang dibutuhkan frame

-          Informasi procedural untuk menggunakan struktur yang digambarkan

-          Informasi default frame

-          Informasi terbaru.

Script :

-          Script (Schank & Abelson, Yale univ) merupakan representasi terstruktur yang menggambarkan urutan stereotip dari kejadian-kejadian dalam sebuah konteks khusus.

-          Script mirip dengan frame, perbedaannya : Frame menggambarkan objek, sedangkan Script menggambarkan urutan peristiwa.

-          Dalam menggambarkan urutan peristiwa, script menggunakan serangkaian slot yang berisi informasi tentang orang, objek dan tindakan-tindakan yang terjadi dalam suatu peristiwa.

-          Elemen script yang tipikal :

Kondisi masukan : menggambarkan situasi yang harus dipenuhi sebelum terjadi satu peristiwa yang ada dalam script

o   Prop : mengacu kepada objek yang digunakan dalam urutan peristiwa yang terjadi.

o   Role : mengacu kepada orang-orang yang terlibat dalam script.

o   Hasil : kondisi yang ada sesudah peristiwa dalam script berlangsung.

o   Track : mengacu kepada variasi yang mungkin terjadi dalam script tertentu.

o   Scene : menggambarkan urutan peristiwa aktural yang terjadi.

o   Contoh : Script pergi ke restoran

-          SCRIPT Restoran

Jalur (track): fast food restoran

Peran (roles): tamu, pelayan

Pendukung (prop): conter, baki, makanan, uang,serbet, garam, merica, kecap,sedotan, dll

Kondisi masukan: tamu lapar – tamu punya uang

Adegan (scene) 1: Masuk

§  Tamu parkir mobil

§  Tamu masuk restoran

§  Tamu mantri

§  Tamu baca menu di list menu dan mengambil keputusan tentang apa yang akan diminta.

Adegan (scene) 2 : Pesanan

§  Tamu memberikan pesanan pada pelayan

§  Pelayan mengambil pesanan dan meletakkan makanan di atas baki

§  Tamu membayar

Adegan (scene) 3 : Makan

§  Tamu mengambil serbet, sedotan, garam, All

§  Tamu makan dengan cepat

Adegan (scene) 4 : Pulang

§  Tamu membersihkan meja

§  Tamu membuang sampah

§  Tamu meninggalkan restoran

§  Tamu naik mobil dan pulang

Hasil

§  Tamu merasa kenyang

§  Tamu senang

§  Tamu kecewa

§  Tamu sakit perut

-          Keistimewaan Script :

§  Script menyediakan beberapa cara yang sangat alami untuk merepresentasikan “suatu inforamsi” yang lazim” dengan masalah yang bersumber dari sistem AI dari mula.

§  Script menyediakan struktur hirarki untuk merepresentasikan inforamsi melalui inklusi subscript dengan sript.

Sumber:

-          http://slideplayer.info/slide/2569504/

-          https://redblacksquad.wordpress.com/2010/10/25/119/

-          http://slideplayer.info/slide/4873378/

-          http://kiteklik.blogspot.co.id/2011/06/jaringan-semantik-kecerdasan-buatan.html

-          https://aij1004.wordpress.com/2010/06/27/representasi-pengetahuan/

Read More

Metode Pencarian dan Pelacakan 2 (Heuristik)

1.      Best First Search

Best-First Search merupakan sebuah metode yang membangkitkan simpul dari simpul sebelumnya. Best-first search memilih simpul baru yang memiliki biaya terkecil diantara  semua leaf nodes (simpul-simpul pada level terdalam) yang pernah dibangkitkan. Penentuan simpul terbaik dilakukan dengan menggunakan sebuah fungsi yang disebut fungsi evaluasi f(n).fungsi evaluasi best-first search dapat berupa biaya perkiraan dari suatu simpul menuju ke goal atau gabungan antara biaya sebenarnya dan biaya perkiraan tersebut.

Pada setiap langkah proses pencarian terbaik pertama, kita memilih node - node dengan menerapkan fungsi heuristik yang memadai pada setiap node/simpul yang kita pilih dengan menggunakan aturan-aturan tertentu untuk menghasilkan penggantinya. Fungsi heuristic merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan sepanjang jalur yang memiliki kemungkinan sukses paling besar.

Ada beberapa istilah yang sering digunakan pada metode best-first search, yaitu:

1.            Start node adalah sebuah terminology untuk posisi awal sebuah pencarian

2.            Curret node adalah simpul yang sedang dijalankan dalam algoritma pencarian jalan terpendek

3.            Suksesor adalah simpul-simpul yang yang akan diperiksa setelah current node

4.            Simpul (node) merupakan representasi dari area pencarian

5.            Open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting node maupun simpul yang sedang dijalankan

6.            Closed list adalah tempat menyimpan data simpul yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan

7.            Goal node yaitu simpul tujuan

8.            Parent adalah curret node dari suksesor.

Algoritma best-first search

Pertama kali, dibangkitkan node A. Kemudian semua suksesor A dibangkitan, dan dicari harga paling minimal. Pada langkah 2, node D terpilih karena harganya paling rendah, yakni 1. Langkah 3, semua suksesor D dibangkitkan, kemudian harganya akan dibandingkan dengan harga node B dan C. Ternyata harga node B paling kecil dibandingkan harga node C, E, dan F. Sehingga B terpilih dan selanjutnya akan dibangkitkan semua suksesor B. Demikian seterusnya sampai ditemukan node tujuan. Ilustrasi algoritma best-first search dapat dilihat pada gambar dibawah ini.

Untuk mengimplementasikan algoritma pencarian ini, diperlukan dua buah senarai, yaitu: OPEN untuk mengelola node-node yang pernah dibangkitkan tetapi belum dievaluasi dan CLOSE untuk mengelola node-node yang pernah dibangkitkan dan sudah dievaluasi. Algoritma selengkapnya adalah sebagai berikut.

·      OPEN berisi initial state dan CLOSED masih kosong.

·      Ulangi sampai goal ditemukan atau sampai tidak ada di dalam OPEN

a.    Ambil simpul terbaik yang ada di OPEN

b.    Jika simpul tersebut sama dengan goal, maka sukses

c.    Jika tidak, masukkan simpul tersebut ke dalam CLOSED

d.   Bangkitkan semua aksesor dari simpul tersebut

e.    Untuk setiap suksesor kerjakan:

·      Jika suksesor tersebut belum pernah dibangkitkan, evaluasi suksesor tersebut, tambahkan ke OPEN, dan catat parent.

·      Jika suksesor tersebut sudah pernah dibangkitkan, ubah parent-nyajika jalur melalui parent ini lebih baik daripada jalur melalui parent yang sebelumnya. Selanjutnya perbarui biaya untuk suksesor tersebut dn nodes lain yang berada di level bawahnya.

Algoritma yang menggunakan metode best-first search, yaitu:

a.   Greedy Best-First

Greedy Best-First adalah algoritma best-first yang paling sederhana dengan hanya memperhitungkan biaya perkiraan (estimated cost) saja, yakni f(n) = h(n). Biaya yang sebenarnya (actual cost) tidak diperhitungkan. Dengan hanya memperhitungkan biaya perkiraan yang belum tentu kebenarannya, maka algoritma ini menjadi tidak optimal.

b.   A*

A* adalah algoritma best-first search yang menggabungkan Uniform Cost Search dan Greedy Best-First Search. Biaya yang diperhitungkan didapat dari biaya sebenarnya ditambah dengan biaya perkiraan. Dalam notasi matematika dituliskan sebagai f(n)= g(n) + h(n). Dengan perhitungan biaya seperti ini, algoritma A* adalah complete dan optimal.

2.      Problem Reduction

Problem reduction adalah dasar teknik pemecahan masalah AI dimana dilakukan dengan cara mengurangi masalah dalam satu set sub masalah yang lebih mudah pemecahannya. Intinya adalah berusaha mengurangi masalah dengan harapan masalah yang bersangkutan menjadi lebih mudah diselesaikan. Ide utama teknik problem reduction adalah mendekomposisi masalah ke dalam skala yang lebih kecil. 

Problem Reduction dibagi dalam dua metode yaitu :

a)      Graf AND OR Graf AND OR atau tree merupakan graf yang digunakan untuk memperlihatkan solusi dari permasalahan yang dapat diselesaikan dengan cara mendekomposisikan masalah tersebut menjadi sekumpulan masalah yang lebih kecil, dimana semuanya harus dapat diselesaikan. Pereduksian ini membangkitkan arc(busur) AND. Satu busur AND akan menghasilkan beberapa nomor dari simpul setelahnya dimana semua simpul harus diselesaikan supaya pancaran menghasilkan solusi. Hanya saja pada graf OR banyak pancaran akan muncul dari beberapa node, mengindikasikan beberapa jalan yang dapat menyelesaikan masalah.  Untuk menemukan solusi dari sebuah graf AND OR kita memerlukan sebuah algoritma yang serupa dengan algoritma BFS(Best First Search) tetapi dengan kemampuan untuk menangani pancaran AND dengan tepat. Algoritma ini harus menemukan bagian dari simpul awal dari graf untuk menghimpun simpul-simpul yang menggambarkan state solusi. Perlu diketahui bahwa  hal ini mungkin diperlukan untuk mendapatkan lebih dari solusi dalam setiap pancaran AND.  Untuk mendeskripsikan algoritma Graph AND-OR kita menggunakan nilai F_UTILITY, yaitu biaya solusi. Algoritma :

·         Inisialisasi graph ke node awal.

·         Kerjakan langkah-langkah di bawah ini hingga node awal SOLVED atau sampai biayanya lebih tinggi dari F_UTILITY

Pada Gambar di atas, pada langkah-1 semula hanya ada satu node yaitu A. Node A diekspansi hasilnya adalah node B, C, dan D.  Node D memiliki biaya yang lebih rendah (6) jika dibandingkan dengan B dan C (9). Pada langkah-2 node D terpilih untuk diekspansi, menjadi E dan F dengan biaya estimasi sebesar 10. Sehingga kita harus memperbaiki nilai f’ dari D menjadi 10. Kembali ke level sebelumnya, node B dan C memiliki biaya yang lebih rendah daripada D (9 < 10). Pada langkah-3, kita menelusuri arc dari node A, ke B dan C bersama-sama. Jika B dieksplore terlebih dahulu, maka akan menurunkan node G dan H. Kita perbaiki nilai f’ dari B menjadi 6 (nilai G=6 lebih baik daripada H=8), sehingga biaya AND-arc B-C menjadi 12 (6+4+2). Dengan demikian nilai node D kembali menjadi lebih baik (10 < 12). Sehingga ekspansi dilakukan kembali terhadap D. Demikian seterusnya.

b)      Graf AO*(Algorithm Optimized) Algoritma AO* menggunakan struktur Graph dimana tiap-tiap node pada graph tersebut akan memiliki nilai h’ yang merupakan biaya estimasi jalur dari node itu sendiri sampai suatu solusi. Algoritma

§  Diketahui GRAPH yang hanya berisi  node awal (sebut saja node INIT). Hitung h’(INIT).

§  Kerjakan langkah-langkah di bawah ini hingga INI bertanda SOLVED atau samoai nilai h’(INIT) menjadi lebih besar daripada F_UTILITY:

o   Ekspand INIT dan ambil salah satu node yang belum pernah diekspand (sebut NODE).

o   Bangkitkan successor-successor NODE. Jika tida memiliki successor maka set FUTULITY dengan nilai h’(NODE). Jika ada successor, maka untuk setiap successor (sebut sebagai SUCC) yang bukan merupakan ancestor dari NODE

o   Kirimkan informasi baru tersebut ke graph, dengan cara: tetapkan S adalah node yang ditandai dengan SOLVED atau node yang nilai h’-nya baru saja diperbaiki, dan sampaikan nilai ini ke parent-nya. Inisialisasi S = NODE. Kerjakan langkah-langkah berikut ini hingga S kosong.

§  Jika mungkin, seleksi dari S suatu node yang tidak memiliki descendant dalam GRAPH yang terjadi pada S. Jika tidak ada, seleksi sebarang node dari S (sebut: CURRENT) dan hapus dari S.

§  Hitung biaya tiap-tiap arc yang muncul dari CURRENT. Biaya tiap-tiap arc ini sama dengan jumlah h’ untuk tiaptiap node pada akhir arc ditambah dengan biaya arc itu sendiri. Set h’(CURRENT) dengan biaya minimum yang baru saja dihitung dari stiap arc yang muncul tadi.

§  Tandai jalur terbaik yang keluar dari CURRENT dengan menandai arc yang memiliki biaya minimum.

§  Tandai CURRENT dengan SOLVED jika semua node yang dihubungkan dengannya hingga arc yang baru saja ditandai tadi telah ditandai dengan SOLVED.

§  Jika CURRENT telah ditandai dengan SOLVED atau jika biaya CURRENT telah berubah, maka status baru ini harus disampaikan ke GRAPH. Kemudian tambahkan semua ancestor dari CURRENT ke S.

Sebagai contoh, pada Gambar di atas, jelas bahwa jalur melalui C selalu lebih baik daripada melalui B. Tetapi jika biaya node E muncul, dan pengaruh perubahan yang diberikan ke node B tidak sebesar pengaruhnya terhadap node C, maka jalur melalui B bisa jadi lebih baik. Sebagai contoh, hasil expand node E, misalkan 10, maka biaya node C menjadi 11 (10+1), dengan demikian biaya node A apabila memilih jalur lewat C adalah 12 (11+1). Tentu saja akan lebih baik memilih jalur melalui node B (11). Tapi tidak demikian halnya apabila kemudian node D diekspan. Bisa jadi jalur dengan melalui node B akan lebih buruk lagi ketimbang jalur dengan melalui node C.

3.      Constraint Satisfaction

·         Problem search standard  :

State adalah "black box“ setiap struktur data yang mendukung fungsi successor, fungsi heuristik dan tes goal.

·         CSP :

State didefinisikan sebagai variabel Xi dengan nilai dari domain, di Tes goal adalah sekumpulan constraint yang menspesifikasikan kombinasi dari nilai subset variabel. Contoh sederhana adalah bahasa representasi formal

CSP ini merupakan algoritma general-purpose dengan kekuatan lebih daripada algoritma pencarian standar.

Contoh : Pewarnaan Peta

·         Variabel WA, NT, Q, NSW, V, SA, T

·         Domain Di = {red,green,blue}

·         Constraints : daerah yang bertetangga dekat harus memiliki warna yang berbeda.

·         Contoh WA ≠ NT, atau (WA,NT) {(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green)}

·         Solusi lengkap dan konsisten, contoh : WA = red, NT = green,Q = red,NSW = green,V = red,SA = blue,T = green

4.      Means End Analysis(MEA)

MEA adalah strategi penyelesaian masalah yang diperkenalkan pertama kali dalam GPS (General Problem Solver) [Newell & Simon, 1963]. Proses pencarian berdasarkan ruang masalah yang menggabungkan aspek penalaran forward dan backward. Perbedaan antara state current dan goal digunakan untuk mengusulkan operator yang mengurangi perbedaan itu. Keterhubungan antara operator dan perbedaan tsb disajikan sebagai pengetahuan dalam sistem (pada GPS dikenal dengan Table of Connections) atau mungkin ditentukan sampai beberapa pemeriksaan operator jika tindakan operator dapat dipenetrasi.

Contoh OPERATOR first-order predicate calculus dan operator2 tertentu mengijinkan perbedaan korelasi task-independent terhadap operator yang menguranginya. Kapan pengetahuan ada tersedia mengenai pentingnya perbedaan, perbedaan yang paling utama terpilih pertama lebih lanjut meningkatkan rata-rata capaian dari MEA di atas strategi pencarian Brute-Force. Bagaimanapun, bahkan tanpa pemesanan dari perbedaan menurut arti penting, MEA meningkatkan metode pencarian heuristik lain (di rata-rata kasus) dengan pemusatan pemecahan masalah pada perbedaan yang nyata antara current state dengan goal-nya.

Sumber :

-          http://deisyamalia.blogspot.co.id/2012/03/best-first-search.html

-          http://www.academia.edu/4865567/Teknik_Pencarian_Heuristik_1_25_Pengantar_Kecerdasan_Buatan_AK045218_Generate_and_Test_Hill_Climbing_Best_First_Search_Problem_Reduction_Constraint_Satisfaction_Means_End_Analysis

-          http://nailil-hidayah.blogspot.co.id/2013/11/kecerdasan-buatan.html

Read More