Google+ Followers

06 November 2009

Artificial Intelligence, VI, VII, VIII



Diktat



 



Kecerdasan Artifisial



 



Ken Ratri Retno



The Houw Liong



 



 



Bab 6



PengolahanBahasa Alami



Tugas
penting yang dapat dipecahkan oleh AI adalah Natural Processing Language.
Pengolahan
Bahasa Alami membuka jalan
antara komputer dan manusia untuk berdialog langsung menghindari prosedur
konvensional dan protocol system operasi.



NLP
mencoba membuat komputer dapat memahami perintah yang ditulis dalam bahasa
standar manusia. Tugas penting NLP mencoba agar komputer dapat memberi respon
(membangun bahasa alami) kemudian selanjutnya membangkitkan respon.



 



Pendekatan Pada Pengolahan Bahasa Alami



Inti dari sistem Pengolahan Bahasa Alami adalah Parser.
Parser adalah bagian dari kode yang secara aktual membaca setiap kalimat, kata
demi kata, lalu memutuskan sesuatu.
Tiga macam parser :



1.      State-Machine Parser



2.      Context-free
recursive-descent parser



3.      Noise-disposal parser



 



Membatasi Bahasa



Aspek tersulit pada pembangunan system Pengolahan Bahasa Alami
adalah mengakomodasi kerumitan dan kefleksibelan dari bahasa manusia ke dalam
system ketika kita mengimplementasikan dengan membatasi tipe dari kalimat
atau tata bahasa (grammar) yang diterima oleh prosesor misalnya dengan menganggap
semua kalimat adalah dideklarasikan mengikuti bentuk standar :



 



Subjek, verb, objek.



 



Contohnya untuk aturan bahasa Inggris, dengan menganggap
bahwa :




  • Semua adjective mendahului noun,

  • Adverb diikuti verb,

  • Kalimat harus mengandung tanda . (titik)



 



Contoh kalimat menurut aturan di atas dalam bahasa
inggris yang sah (
valid ):



The small
child runs quickly to the windows.



Contoh kalimat dalam bahasa inggris menurut aturan di
atas yang taksah (
invalid), karena keterangan kata kerja (adverb) quickly
mendahului kata kerja (
verb) runs :



The child quickly runs
to the house.



 



 



State-Machine Parser



Parser
State-Machine
digunakan pada kalimat untuk memprediksi jenis kata yang
digunakan.





 



Gambar diatas menampilkan Mesin Keadaan (State-Machine)yaitu suatu graph yang menunjukkan transisi
yang valid dari satu pernyataan ke pernyataan lain. Contohnya kata benda
(noun) dapat diikuti kata kerja (verb) atau preposition.
State-Machine menggambarkan tata bahasa (grammar) digunakan untuk menentukan apakah sebuah kalimat sesuai
dengan aturan
grammar atau tidak atau
pelaksanaannya di dalam Prolog digunakan untuk memenggal komponen-komponen
kalimat.



 



 



 



Analisis State-Machine Parser



Kerugian State-Machine
Parser
adalah terlampau kompleks untuk diterapkan pada suatu bahasa. Untuk
contoh pada tata bahasa (
grammar) di
atas diperlukan 14 klausa terpisah untuk menjalankan transisi keadaan (
state).



Masalah lain adalah parser
tidak tahu bagaimana mendapatkan
state
tertentu, tidak dapat dihubungkan dengan modifikasi frasa (
phrase) dari kata benda (noun)
tertentu.



Keuntungannya ideal untuk aplikasi seperti system operasi job-control language dan beberapa
aplikasi basis data. Di lingkungan ini user memasukkan perintah dengan format
yang sah (
valid) yang setiap katanya
sudah dikenal oleh komputer.



 



Context-free recursive ( CFR )- Descent parser



Untuk memahaminya lihat konstruksi kalimat tingkat
berbeda dari model
State machine.
Untuk CFR kita asumsikan sebuah kalimat yang disusun dari berbagai item hingga
dipenggal menjadi elemen-elemen atom kata benda
(noun),
kata kerja (verb), kata sifat (adjective) dan lain-lain. Aturan
yang mengatur susunan bagian-bagian ini disebut kaidah produksi tata bahasa (
production rules of grammar), digunakan
untuk menganalisis kalimat.



Production rules ini membentuk satu pohon yang berurutan (sort of tree). Pohon ini menunjukkan pohon parser (parser tree) karena menampilkan cara parser melihat kalimat. Parser yang menghasilkan parser tree ini disebut Context-Free karena pohon ini tidak
berdasarkan pada konteks setiap elemen, artinya peraturan berlaku untuk setiap
kalimat yang sesuai
grammar G1 tanpa kesesuain konteks setiap frasa
(
phrase).



 



SENTENCE NP + VP



NP determiner + noun



NP determiner + adjective + noun



NP preposition + NP



 



VP verb + NP



VP verb + adverb + NP



VP verb + adverb



VP verb



 



Pada aturan produksi untuk grammar
di atas, bagian kanan panah sebagai hasil. NP untuk noun phrase dan VP
untuk verb phrase.
Noun phrase
adalah definisi rekursif untuk klausa
prepositional
dan verb phrase adalah tidak
langsung rekursif karena menimbulkan sebuah
noun
phrase
. CF parsing tidak hanya
digunakan pada program AI tapi juga pada semua bahasa parse seperti Pascal,
Basic, C dan lain-lain.



 



 



 



Contoh :



 





Analisis Context-free recursive ( CFR )- Descent parser



Keuntungan CFR mudah untuk mengimplementasikan di dalam bahasa prolog, selain itu dapat
berhubungan langsung dengan tingkat kata dan tingkat frasa
(phrase). Kerugiannya jika diimplementasikan di dalam bahasa Inggris
tidak dapat menangani semua cara di dalam menyusun kalimat.



 



 



Noise-Disposal Parser



Aplikasi tertentu yang berhubungan dengan beberapa kata kunci
yang dimiliki satu kalimat dan tidak berhubungan dengan semua kata yang
membentuk kalimat/bahasa. Tipe aplikasi ini hanya mengarah pada informasi yang
ada pada suatu kalimat. Semua kata yang tidak diperlukan atau tidak diketahui
dianggap sebagai bising (
noise) atau
dibuang. Semua kalimat harus mengikuti format yang kaku serupa dengan bahasa
alami.



Tipe parser ini
umumnya digunakan pada aplikasi tipe basis data inteligen. Contohnya basis data
yang terdiri dari nama perusahaan dan harga saham. Kita anggap bahwa basis data
akan menerima
query seperti berikut
ini :



 



Show me all companies with stock price
>100



Show me all



Show me xyz



Show me one with stock price <100



 



Tipe
dari semua
query mengikuti basic template :



Command<modifier><name><operator><value>



 



Disini
Command selalu ada tetapi empat
elemen lainnya bersifat optional.



Dari
contoh di atas kata dan symbol yang valid untuk
command :



 











































Word



Tipe



Show



Command



xyz



name



abc



name



ucl



name



all



modifier



one



modifier





operator





operator






 



Analisis Noise-Disposal
Parser



Satu
kerugian
Noise-Disposal
Parser
adalah tidak berguna di luar
situasi yang dibatasi karena kalimat mengikuti format yang seksama/teliti
selain itu hanya sedikit kata kunci atau symbol yang penting.



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



Bab 7



Penalaran
Dengan Ketidakpastian (
uncertainty)



Pengenalan
Penalaran
Nonmonotonic



Ketidakpastian
merupakan suatu permasalahan yang dapat menghalangi
untuk membuat suatu keputusan yang terbaik.
Ketidakpastian dapat dianggap sebagai suatu kekurangan informasi yang memadai
untuk membuat suatu keputusan. Beragamnya kerangka kerja, logika, dan metode
penghitungan telah diajukan untuk menangani masalah yang tidak pasti.




  • alasan nonmonotonik , dimana aksioma
    dan/atau aturan-aturan dari inferensi diperluas sehingga menjadi beralasan
    dengan informasi yang tidak lengkap.


  • Alasan statistical, dimana
    representasi diperluas untuk membuat ukuran numerik secara pasti (
    true
    atau
    false) diasosiasikan dengan setiap pernyataan.



Pendekatan
lain yang dapat diajukan dan digunakan dalam system, contohnya kadang-kadang
satu masalah tidak mempunyai satu dasar pengetahuan yang menangkap keyakinan
semua bagian yang terlibat dalam pemecahan masalah.



Sedangkan
Sistem penalaran
monotonic, first-order predicate logic dibuat
untuk menangani informasi yang mempunyai 3 karakteristik/
property.




  • Pengetahuannya lengkap dengan kata
    lain semua fakta untuk memecahkan masalah yang ada pada sistem atau dapat
    diambil dengan aturan konvensional dari
    first-order logic.

  • Konsisten



o       
Satu-satunya cara yang dapat dirubahnya
yaitu fakta baru dapat ditambahkan, jika fakta baru ini konsisten dengan semua
fakta yang sudah dinyatakan, maka tidak akan ditarik kembali dari set fakta
yang sudah dianggap benar.
Property
ini disebut
Monotonicity.



System
penalaran
nonmonotonic dibuat untuk dapat memecahkan masalah suatu
penalaran dimana adanya penambahan fakta baru mengakibatkan ketakkonsistenan.



Ciri-ciri
penalaran
nonmonotonic :



o       
Mengandung ketakpastian



o       
Adanya perubahan pada pengetahuan



o       
Adanya penambahan fakta baru dapat
mengubah konklusi yang sudah terbentuk



o       
Misalkan S adalah konklusi dari D bias
jadi S tidak dibutuhkan sebagai konklusi D + fakta-fakta baru.



 



Untuk
dapat melakukannya penalaran
nonmonotonic, hal-hal yang harus
dipertimbangkan sebagai berikut ini:




  • bagaimana
    landasan pengetahuan dengan kurangnya pengetahuan dapat diperluas untuk
    membuat kesimpulan misalnya kita perlu untuk membedakan antara diketahui
    bahwa ini P dan tidak diketahui sebagai

    P. Kita perlu memperluas
    sistem
    untuk membuat penalaran yang
    kedua. Membuat beberapa penalaran mempunyai pengaruh kuat pada dasar
    pengetahuan. Pada system penalaran nonmonotonic kesimpulan tergantung pada
    kurangnya pengetahuan, dasar pengetahuan tidak akan tumbuh secara
    monotonically
    sebagai satu masukan yang dibuat.

  • bagaimana
    dasar pengetahuan bisa diperbaharui dengan baik ketika fakta baru ditambah
    pada sistem? ( atau ketika fakta lama dipindahkan)? Dalam system
    nonmonotonic
    ketika menambahkan satu fakta, fakta lama tertutupi menjadi invalid,
    bagaimana fakta dan semua kesimpulan yang tergantung pada fakta lama
    tersebut dapat ditemukan? Solusinya ialah dengan melacak trek fakta lama
    atau
    disebut justification.
    Untuk menemukan
    justification tergantung pada ketaktersediaan fakta
    baru.

  • Bagaimana
    pengetahuan digunakan untuk membantu memecahkan konflik ketika ada
    beberapa kesimpulan
    nonmonotonic yang tak konsisten. Dalam system
    nonmonotonic, ada bagian dasar pengetahuan yang secara lokal konsisten
    tapi secara global inkonsisten.




Karena
monotonicity adalah first-order predicate logic, kita harus menemukan beberapa
alternatif untuk mendukung penalaran nonmonotonik, menetapkan sistem yang
memungkinkan untuk
dapat menghadirkan
fakta yang diberikan, menyediakan cara untuk beberapa model, dan menyediakan
dasar untukmengimplementasikan jenis penalaran ini.





 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



 



BAB 8



 



Penalaran Statistical



 



Probabilitas
Dan Teorema Bayes



Tujuan utama dari system pemecahan masalah adalah mengumpulkan bukti
saat sistem berjalan dan merubah perilaku berdasarkan bukti. Untuk membuat
model pada perilaku ini, diperlukan teori statistik untuk membuktikannya.
Statistik Bayesian adalah salah satu teori yang digunakan untuk mengatasi
ketidakpastian data dengan gagasan utamanya adalah :



probabilitas hipotesis H dengan evidence E yang diamati, untuk menghitungnya kita perlu masukkan
probabilitas
prior dari H (H digunakan
jika kita tak punya bukti/
evidence)
dan ektensi dimana E menyediakan
evidence
H. untuk melakukannya, kita perlu menetapkan satu semesta/universe yang
lengkap.



P(Hi|E) =
probabilitas bahwa dugaan H
i benar jika diberikan evidence E,



P(E| Hi) = probabilitas
munculnya evidence E jika
diketahui dugaan i
benar,



P(Hi) =
probabilitas
utama bahwa dugaan i benar
dengan tidak ada
evidence khusus.
Probabilitas
ini disebut
probabilitas
prior.



K= jumlah dugaan yang mungkin.



 



Teorema Bayes :





 



contohnya diterapkan dalam memeriksa bukti
geologis pada satu area tertentu untuk menentukan apakah ditempat ini
mengandung mineral. Jika kita tahu probabilitas

prior untuk menemukan lokasi mineral tersebut dan tahu probabilitas jika memang terdapat mineral maka
karakteristik fisik tertentu akan diamati, rumusan Bayes dapat digunakan untuk
menghitung dari bukti yang
dikumpulkan,
bagaimana mineral yang ada. Hal ini yang dilakukan oleh program PROSPECTOR
(Duda at al., 1979), telah digunakan dengan baik untuk membantu lokasi
tersimpannya beberapa mineral, termasuk
copper
dan uranium.



 



Contoh lainnya ketika memecahkan masalah
diagnosa kesehatan. Pertimbangkan kesimpulan berikut ini:



S : pasien mempunyai bintik-bintik



M : pasien kena campak



F : pasien demam tinggi.



Tanpa ada evidence tambahan, adanya bintik-bintik dianggap sebagai evidence berhubungan dengan campak.
Keadaan bahwa karena campak bisa mengakibatkan pasien demam. Kemudian
evidence tambahan bahwa dia mempunyai
bintik-bintik bahwa tak berhubungan dengan demam. Alternatifnya, baik
bintik-bintik ataupun demam menunjukkan
evidence
berhubungan dengan campak. Jika keduanya ada, maka perlu mempertimbangkan
keduanya dalam menentukan jumlah
evidence
. Tapi karena bintik-bintik dan demam bukan kejadian yang independen, maka
tak dapat hanya menjumlahkan efeknya. Kita perlu menampilkan kemungkinan
kondisional yang timbul dari hubungan ini dengan jelas.



 



Jika setelah dilakukan pengujian terhadap
hipotesis muncul satu atau lebih
evidence
atau observasi baru, maka :





 



Dalam dunia kompleks yang berubah-ubah,
ukuran probabilitas
gabungan set yang
diperlukan untuk menghitung fungsi ini berkembang menjadi 2
n jika
ada proposisi n berbeda yang harus dipertimbangkan. Hal ini menyebabkan
penggunaan teorema Bayes tetap untuk beberapa alasan:




  • masalah mendapatkan pengetahuan tak dapat dibatasi; terlalu banyak
    probabilitas
    yang harus disediakan.

  • Tempat yang dibutuhkan untuk menyimpan semua probabilitas terlalu
    besar.

  • Waktu yang diperlukan untuk menghitung probabilitas terlalu besar.



 



 



Faktor
Kepastian (
Factor Certainty)



Satu cara praktis memahami system
Bayesian, pendekatan yang telah dipelopori oleh system MYCIN (shortliffe, 1976;
Buchanan dan shortliffe, 1984; shortliffe dan Buchanan, 1975) ; mencoba untuk
merekomendasikan terapi yang tepat untuk pasien infeksi bakteri. Kita
berinteraksi dengan dokter untuk memperoleh
data klinis. MYCIN adalah contoh system pakar (
expert system), melakukan tugas seperti yang dilakukan oleh para
ahli manusia.





Factor certainty (CF[h,e]) menunjukkan ukuran kepastian terhadap suatu
fakta atau aturan, ditetapkan dalam dua komponen:




  • MB(h,e) ; ukuran kepercayaan terhadap hipotesis h dipengaruhi oleh
    evidence e. (antara 0 dan 1). MB
    mengukur ektensi dimana
    evidence
    mendukung hipotesis. Akan nol jika
    evidence gagal mendukung hipotesis.

  • MD(h,e) ; ukuran ketidakpercayaan terhadap hipotesis h dipengaruhi
    oleh
    evidence e (antara 0 dan
    1). MD mengukur ektensi dimana
    evidence
    mendukung negasi dari hipotesis. Akan nol jika
    evidence mendukung
    hipotesis.



 



Konsep ini kemudian diformulasikan dalam
rumusan
faktor kepastian berikut ini:



CF[h,e] = MB[h,e] - MD[h,e]



 
















 


Kombinasi Aturan
Ketidakpastian




 




 



Gambar di atas menggambarkan 3 kombinasi; gambar (a) beberapa
aturan yang semuanya menyediakan
evidence
yang berhubungan dengan satu hipotesis. Gambar (b) kita perlu mempertimbangkan
keyakinan di dalam pengumpulan beberapa proposisi, gambar (C) output dari satu
aturan menyediakan input untuk lainnya.



 



Di dalam gambar (a) beberapa evidence dikombinasikan untuk menentukan CF dari suatu
hipotesis. Jika s1 dan s2 adalah observasi maka :



 







 



Contoh, Andaikan suatu observasi memberikan
kepercayaan terhadap h dengan MB = 0.3, MD[h, s
1] = 0 sehingga CF[h,
s
1] = 0.3 . Jika observasi kedua, juga memberikan
kepercayaan terhadap h dengan MB[h, s
2] = 0.2, maka :



MB(h, s1 s2] = 0.3 + 0.2 . 0.7 = 0.44



MD(h, s1 s2] = 0.0



CF(h, s1 s2] = 0.44



 



kita lihat dari contoh ini bagaimana
konfirmasi
evidence dapat
berakumulasi untuk menghasilkan factor Kepastian yang menaik.



Gambar (b), dimana kita perlu menghitung
faktor Kepastian dari kombinasi hipotesis. Hal ini penting saat kita perlu
mengetahui factor Kepastian dari aturan antecedent yang mempunyai beberapa
klausa. Kombinasi faktor Kepastian dapat dihitung dari MB dan MD-nya.



MB[h1 h2 , e] = min(MB[h1 ,e], MB[h2 ,e])



MB[h1 h2 , e] = max(MB[h1 ,e], MB[h2 ,e])



 



MD[h1 h2 , e] = min(MD[h1 ,e], MD[h2 ,e])



MD[h1 h2 , e] = max(MD[h1 ,e], MD[h2 ,e])



 



 



Selanjutnya gambar (c), dimana aturan
menjadi kesatuan rangkaian dengan hasil
uncertain
dari satu aturan yang harus menyediakan input untuk yang lainnya. Solusi untuk
masalah ini juga akan menangani masalah dimana kita menugasi ukuran
uncertainty untuk menginisial input.
Maka:



MB[h , s] = MB[h ,s]
*max(0,CF[s,e])



Dengan MB[h
,s] adalah ukuran kepercayaan h berdasarkan keyakinan penuh terhadap
validitas s.



 





 



Teori
Dempster-Shafer



Secara umum Teori Dempster-Shafer ditulis
dalam suatu interval :



[Belief,
Plausibility
]



Belief (Bel) adalah ukuran kekuatan
evidence dalam mendukung suatu himpunan proposisi, Jika bernilai 0 maka
mengindikasikan bahwa tidak ada evidence, dan jika bernilai 1 menunjukkan
adanya kepastian.



Plausability (PI) dinotasikan sebagai :



PI(s) = 1 Bel(�s)



Plausability juga bernilai 0 sampai 1.
Jika kita yakin akan �s, maka dapat dikatakan bahwa Bel((�s)=1 dan PI((�s) = 0.
Pada teori Dempster kita akan mengenal adanya frame of discernment yang
dinotasikan dengan θ. Frame ini merupakan semesta pembicaraan dari
sekumpulan hipotesis.



Contohnya θ = {All, Flu, Cold, Pneu}, dimana



All : allergy



Flu : Flu



Cold : Cold



Pneu : pneumonia



Tujuan kita adalah mengaitkan ukuran
kepercayaan elemen-elemen θ. Tidak semua evidence secara langsung
mendukung tiap-tiap elemen. Sebagai contoh, panas mungkin hanya mendukung {
Flu, Cold,Pneu}.



Untuk itu perlu adanya probabilitas
densitas (m). Nilai m tidak hanya mendefinisikan elemen-elemen θ saja
namun semua subsetnya. Sehingga jika θ berisi n elemen maka subset dari
θ semuanya berjumlah 2
n . Kita harus menunjukkan bahwa jumlah
semua m dalam subset
θ sama dengan
1. Jika tidak ada informasi apapun untuk memilih keempat hipotesis tersebut
maka nilai :



M{ θ} = 1.0



Jika kemudian diketahui bahwa panas
merupakan gejala dari flu, cold, pneumonia dengan m=0.8 maka :



{Flu,
Cold,Pneu
}�� (0.8)



{ θ } (0.2)



 



Andaikan diketahui X adalah subset dari
θ dengan m
1 sebagai fungsi densitas dan Y merupakan subset dari
θ dengan m
2 sebagai fungsi densitasnya maka fungsi kombinasi m3
dari m
1 dan m2 :



 





Contoh, Gejala panas



Apabila diketahui nilai kepercayaan setelah dilakukan observasi panas
sebagai gejala flu, cold, dan pneumonia adalah :



m1{Flu, Cold,Pneu}�� = (0.8)



m1{ θ }= (0.2)



 



Gejala hidung tersumbat



Jika dilakukan observasi diketahui
penyakit yang baru yaitu hidung tersumbat sebagai gejala dari allergy ,flu, dan
cold adalah



m2{All,flu, Cold}�� = (0.9)



m2{ θ }�� = (0.1)



Munculnya gejala baru mengharuskan kita untuk
menghitung densitas baru untuk beberapa kombinasi m
3



 




















 



m2{All, Cold,Pneu}�� = (0.9)



� ��= (0.1)



{Flu, Cold,Pneu}�� = (0.8)



{Flu, Cold}��
��= (0.72)



{Flu,Cold,Pneu}=(0/08)



{ θ }= (0.2)



{All, Flu,Cold}��= (0.18)



��
= (0.02)




 



{Flu,
Cold
}diperoleh dari irisan�� {All,
Flu,Cold
}dan�� {Flu,Cold,Pneu}.
Nilai 0.72 diperoleh dari perkalian 0.9 X 0.8 dan {
Flu,Cold,Pneu} merupakan irisan dari θ dan {Flu,Cold,Pneu}.
Hasil 0.08 perkalian dari 0.1 X 0.8 sehingga dapat dihitung :



m3 {Flu,Cold} = 0.72/ 1 � 0 = 0.72



m3 {All,Flu,Cold} = 0.18/ 1 � 0 =
0.18



m3 {Flu,Cold,Pneu} = 0.08/ 1 � 0 =
0.08



m3 { θ }= 0.02/ 1 � 0 = 0.02



 



Di sini bisa dilihat bahwa hanya ada gejala awal panas m{Flu, Cold,Pneu}�� = (0.8) namun setelah ada gejala baru hidung
tersumbat maka nilai m{
Flu,Cold,Pneu}=(0.08).



Demikian pula pada mulanya hanya dengan
hidung tersumbat m{
All,flu, Cold}�� = (0.9), namum setelah ada gejala baru panas
maka nilai m{
All,Flu,Cold} = 0.18/ 1 � 0 = 0.18, dengan adanya 2 gejala
tersebut nilai densitas yang paling kuat adalah m{
Flu,Cold} = 0.72/ 1 �
0 = 0.72



 






No comments: