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.
PengolahanBahasa 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 kalimatatau 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-Machinedigunakan 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(H_i|E) =
probabilitas bahwa dugaan H_i benar jika diberikan evidence E,

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

P(H_i) =
probabilitasutama bahwa dugaan i benar
dengan tidak ada evidence khusus.
Probabilitasini disebut
probabilitasprior.

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ⁿ 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₁] = 0 sehingga CF[h,
s₁] = 0.3 . Jika observasi kedua, juga memberikan
kepercayaan terhadap h dengan MB[h, s₂] = 0.2, maka :

MB(h, s₁ s₂] = 0.3 + 0.2 . 0.7 = 0.44

MD(h, s₁ s₂] = 0.0

CF(h, s₁ s₂] = 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[h₁ h₂ , e] = min(MB[h₁ ,e], MB[h₂ ,e])

MB[h₁ h₂ , e] = max(MB[h₁ ,e], MB[h₂ ,e])

 

MD[h₁ h₂ , e] = min(MD[h₁ ,e], MD[h₂ ,e])

MD[h₁ h₂ , e] = max(MD[h₁ ,e], MD[h₂ ,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ⁿ . 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₁ sebagai fungsi densitas dan Y merupakan subset dari
θ dengan m₂ sebagai fungsi densitasnya maka fungsi kombinasi m₃
dari m₁ dan m₂ :

 

Contoh, Gejala panas

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

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

m₁{ θ }= (0.2)

 

Gejala hidung tersumbat

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

m₂{All,flu, �Cold}�� = (0.9)

m₂{ θ }�� = (0.1)

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

 

	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