2 Resume Kuliah Sistem Cerdas Lanjut (EC6040) DR. Ir. Bambang Riyanto
7.
Definisi-definisi
Tanggal 25 Agustus 2006
1.
Intelligence Kecerdasan Intelejensia Kepintaran
Advanced Intelligent System dengan 2 (dua) topik utama : a.
Artificial Intelligence (AI) → Kecerdasan Tiruan/Buatan (60%)
b.
Artificial Neural Networks (ANN) → Jaringan Syarat Tiruan (40%)
8.
Ciri-ciri “CERDAS” adalah : a.
2.
Artificial Buatan Semu Artifisial
Mampu merespons input secara rasional, memberi tanggapan terhadap stimulus dengan
Evaluasi :
tepat (proper).
a.
UAS (1x – 70%).
b.
Mampu menyimpan pengetahuan.
b.
Tugas pengganti UTS (kecil – individu dan besar – kelompok, 30%) mengenai
c.
Mampu melakukan pembelajaran (learning) dari pengalaman.
d.
Mampu menyelesaikan masalah (problem solving) secara heuristic melalui searching
programming konsep searching pada AI.
(penelusuran). 3.
Topik-topik spesifik sebagai berikut :
e.
Mampu mengenali pola (pattern recognition).
a.
Pengertian dan Konsep AI.
f.
Mengenali fitur (feature matching, feature extraction).
b.
Strategi kontrol.
g.
Mampu berpikir dan menalar (reasoning).
c.
Metoda Searching (Penelusuran).
d.
Heuristik (ciri penting AI).
9.
e.
Basis Pengetahuan (Knowledge-base).
untuk memilih dari sejumlah alternatif yang terbaik dengan cara yang efektif.
Heuristic adalah prinsip-prinsip atau informasi atau pengetahuan yang dapat dipakai
f.
Mesin Inferensi (Inference Engine).
g.
Konsep “Agen Cerdas”.
h.
Persepsi dan Aksi.
a.
Bagaimana otak manusia bekerja ?
i.
Mesin Belajar (Machine Learning).
b.
Bagaimana meniru otak manusia ?
j.
Jaringan Neural.
c.
Apa itu kecerdasan ?
k.
Representasi Pengetahuan.
d.
Bagaimana kita membangun kecerdasan ?
e.
Who cares ? Let’s do something interesting and useful !
10.
Beberapa pertanyaan mengenai AI. Apa itu AI ?
4.
Inferensi adalah kemampuan menalar.
5.
Paradigma-paradigma Intelligence
a.
Apakah meneliti otak ?
a.
Artificial Intelligence.
b.
Apakah meniru otak ?
11.
6.
Klasifikasi AI ditentukan atas dasar apa ?
b.
Computational Intelligence (Artificial Neural Network).
c.
Apakah mesin itu cerdas ?
c.
Fuzzy Logic.
d.
Does it investigate intelligence ?
d.
Komputasi evolutif.
e.
Jika kita tak mengetahui kegunaan sesuatu bekerja → AI, bila sebaliknya → bukan AI.
Bahasa pemrograman AI adalah Prolog (PROgramming LOGic).
Arwin@23206008
Arwin@23206008
3
12.
4
AI adalah suatu disiplin ilmu yang mempelajari bagaimana atau untuk membuat
Contoh : 8-box puzzle (kotak-8)
komputer agar mampu mendekati kecerdasan sebagaimana makhluk hidup. a. 13.
Wikipedia menuliskan bahwa AI adalah “a branch of computer science that deals with
Fakta → Initial State (IS) adalah [x11 = 7, x12 = 1, ......., x33 = 6] dengan x ij dimana i
adalah baris dan j adalah kolom. IS dapat diubah ke bentuk :
intelligent behavior, learning and adaptation in machines”. Vektor
[7
Tanggal 1 September 2006
1.
2.
Matriks
1 4 ............. 6]
dengan konvensi tertentu
Pemecahan masalah (problem solving) dengan AI → game.
⎡7 1 4 ⎤ ⎢ 2 3 5⎥ ⎢ ⎥ ⎣⎢8 0 6⎥⎦ array 2-dimensi
Komponen AI dimana AI dianggap sebagai Sistem Produksi (production system) adalah : a.
Fakta (facts) → dekripsi tentang obyek yang menjadi perhatian.
b.
Kaidah (rule) → aturan yang bila diterapkan pada suatu keadaan (state) (dari fakta) akan
b.
Kaidah → pada umumnya dalam bentuk IF …. THEN ….. (IF = prakondisi; THEN =
aksi). 4 kaidah yakni gerakan ke kiri, kanan, atas dan bawah.
menghasilkan keadaan (state) baru. Di dalam kaidah terdapat dua kondisi yakni :
1)
Prakondisi (antecedent) → persyaratan agar suatu kaidah tertentu dapat
Ki :
Prakondisi (IF)
Aksi (THEN)
x ij = 0;
temp = xi −i , j
j ≠1
xi −i , j = xij
diterapkan pada suatu state. 2)
Aksi (consequence) → hasil yang diperoleh bila kaidah yang bersangkutan
dieksekusi.
c.
Inferensi atau penalaran (inference) → untaian (chain) dari kaidah untuk bergerak dari
keadaan awal (Initial State – IS) menuju keadaan sasaran (Goal State – GS).
3.
xij = temp Ka : At : Bw : c.
………… ………… …………
Inferensi → ]
INGAT : salah satu metode problem solving AI adalah HEURISTIC.
1)
a.
Prinsip atau informasi atau knowledge (bersifat problem-specific) yang dapat digunakan
menghasilkan kaidah yang dapat diterapkan dan dilakukan setiap saat atau active
sebagai panduan (guidance) dalam penelusuran untuk mencapai goal states dengan cara
(applicable) rule.
Matching current state (fakta) dengan basis kaidah (rule-based) untuk
yang efektif. b.
Merupakan estimasi seberapa dekat current state dengan goal state.
c.
Membedakan penelusuran yang bersifat “intelligence” dengan yang tidak.
d.
Tidak unik, gabungan dari beberapa prinsip atau informasi.
e.
Tidak menjamin (secara penuh) dicapainya goal states.
2)
Arwin@23206008
Control strategy → memilih satu di antara active rule yang ada untuk diterapkan.
Arwin@23206008
5
6
6. Representasi dengan Diagram Pohon (Tree Diagram)
7.
Searching ditentukan oleh 3 (tiga) faktor yakni : a.
Branching factor.
b.
Jumlah goal state.
c.
Model penalaran manusia.
Topologi searching dapat direpresentasikan secara Graph (unik) atau Tree Diagram. Pada
Graph, node yang sama hanya dapat muncul satu kali; sedangkan pada Tree Diagram node yang sama dapat muncul lebih dari satu kali.
Tanggal 8 September 2006
1.
o
Pruning adalah pemotongan penelusuran yang kompromi dengan goal state
AI as search didefinisikan dalam : a.
Initial States (IS).
b.
Goal States (GS).
c.
Operator/Rule/Prosedur.
d.
Control Strategy.
(terdekat). Memperhatikan sebagian dari tree yang compromising dengan goal state. o
Searching adalah penelusuran untuk mendapatkan langkah terdekat (minimal)
dengan goal state dari initial state dengan menggunakan kaidah (rule). Arah searching ditujukan kepada jumlah goal state terbesar. 9
Rule harus GENERAL (Rule = operator).
9
Searching Forward → matching dengan Prakondisi.
Dilakukan bila
branching factor kecil.
4.
5.
9
Searching Backward → matching dengan Aksi (mencari node induk).
9
Arah penalaran manusia (forward atau backward).
Basic search process adalah sebagai berikut :
Brancing factor adalah : a.
Menyatakan jumlah rata-rata node yang dapat dicapai oleh node induk secara langsung.
b.
Menyatakan jumlah rata-rata rule untuk mencapai state berikutnya.
c.
Menyatakan seberapa luas state space tree diagram. Contoh : Catur rata-rata 40 node.
Intelligent Search diterapkan bila Branching Factor meledak secara eksponensial.
Arwin@23206008
Arwin@23206008
7
2.
8
Metode Trial & Error (the simplest method) → blind search
9
Kedalaman ditentukan (ada batasan).
Searching diterapkan pada satu cabang
tertentu saja pada kedalaman yang telah ditentukan. Prosedur pelacakan → pseudo code
9
(1)
Ambil state sebagai keadaan awal (IS is given or we define it).
simpul sebelumnya.
(2)
While state ≠ keadaan sasaran (GS is given or we define it as well).
9
(3)
Begin
sebagai berikut :
(4)
Pilih Operator yang dapat diterapkan pada state dan set sebagai Operator.
(5)
state := Operator(state)
(6)
End
Backtrack dilakukan bila pada satu cabang GS tidak dicapai dan untuk kembali ke
Modifikasi Depth-First Search sesuai Graph yang representasinya unik adalah
o
Step (5); Remove(n, open) dan Add(n, closed)
o
Step (6); ekspansikan n. Berikan pada kepala “open” semua simpul anak
yang belum muncul pada “open” atau “closed” dan bubuhkan pointer pada n.
Penjelasan : a.
Step (4); operator dipilih acak.
b.
Step (5); operator yang dipilih diterapkan pada state membentuk state baru.
c.
Sifat stokastik; tidak mencapai sasaran.
[S] [AB] [CDB] [DB] [B] [EF] [HGF] [GF]
S R1 R2
A
R4
R3
B
C
R5
D
R7
Urutan pelacakan : S, A, C, D, B, E, F, H, G
R6
E
F
G R8
H
3.
Fungsi pointer untuk solution path
R9
Tree Diagram
I
Metode Depth-First Search → simpul yang lebih dalam diperiksa lebih dulu.
Berikan simpul awal pada daftar “open” → (list, data structure)
(2)
Loop : if open = kosong then exit(fail).
(3)
n := first(open)
(4)
if goal(n) then exit(success)
(5)
Remove(n, open)
(6)
Ekspansikan n, berikan semua simpul anak pada kepala “open” dan bubuhkan pointer dari
simpul anak ke-n. (7)
Metode Breadh-First Search → Horisontal (cek semua node ke arah horisontal) Prosedur pelacakan → pseudo code
Prosedur pelacakan → pseudo code (1)
4.
Urutan Searching
(1)
Berikan simpul awal pada daftar “open” → (list, data structure)
(2)
Loop : if open = kosong then exit(fail).
(3)
n := first(open)
(4)
if goal(n) then exit(success)
(5)
Remove(n, open) dan Add(n, closed)
(6)
Ekspansikan n, berikan semua simpul anak pada ekor “open” dan bubuhkan pointer dari
simpul anak ke-n. (7)
Kembali ke Loop.
Kembali ke Loop. Arwin@23206008
Arwin@23206008
9
10
[S] [AB] [BCD] [CDEF] [DEF] [EF] [FHG] [HG] [G]
Parameternya adalah : a.
Branching factor (b).
b.
Depth (d).
depth 0
IS b
Urutan pelacakan : S, A, B, C, D, E, F, H, G
depth 1
node b
b
node
node
Fungsi pointer untuk solution path Tree Diagram
5.
depth 2
Urutan Searching
( )
Breadth-Fisrt Search (BFS) memenuhi measurement Completeness dan Optimality.
Computational complexity O b d dirumuskan sebagai berikut :
Search Performance Measure (Russel, Norvig)
1 + b + b 2 + b 3 + ...... + b d = O(b d )
a.
Time Complexity → waktu yang diperlukan untuk mencapai sasaran (cpu time dan
2.
Perbandingan DFS dan BFS methods
berkaitan dengan branching factor). b.
Space Complexity → jumlah memory yang dibutuhkan untuk implementasi search
(besar byte). c.
Completeness → jaminan bahwa GS dicapai oleh search (metode yang dipakai).
d.
Optimality → jaminan bahwa solution path adalah paling minimum.
( )
a.
DFS → C (tidak), O (tidak), S ( O(bd ) dan T ( O b d )
b.
BFS → C (ya), O (ya), S ( O b
( ) dan T ( O(b )) d
d
1 + b + 2b + ...... + bd = O(bd ) 3.
Tanggal 15 September 2006
Metode Depth-limited Search → sama dengan DFS namun menggunakan batasan untuk
menghindari search tak terhingga. Pertanyaannya adalah : bagaimana memilih batasan tersebut ? Kesimpulan : C (ya, bila solusi ditemukan pada kedalaman < atau = batas), O (tidak), S ( O(bd ) dan T
1.
( )
Evaluating search srategies
a.
Completeness → Is it guaranteed that a solution will be found ?
b.
Optimality → Is the best solution found when several solution exist ?
( O b d ).
4.
c.
Space Complexity → How much memory is needed to perform a search ?
d.
Time Complexity → How long does it take to find a solution ?
Metode Deepening Search → ambil kebaikan dari BFS dan DFS
Abbreviated as COST ……….. ??
Arwin@23206008
Arwin@23206008
11
12
Contoh : 5.
Metode Optimal Search (Dijkstra’s Algorithm) → mencari jejak dengan ‘cost’ (biaya)
minimum. ‘Cost’ untuk penerapan operator diberikan (performance index). Prosedur pelacakan → pseudo code (1)
Berikan simpul awal S pada “open”, g’(s)
(2)
Loop : if open = kosong then exit(fail).
(3)
n := first(open)
(4)
if goal(n) then exit(success) G1 dan G 2 adalah Goal states.
(5)
Remove(n, open) dan Add(n, closed)
(6)
Ekspansikan n, hitung g’(ni) untuk semua simpul anak ni dan bubuhkan pointer dari ni ke-
n. Berikan semua simpul anak pada “open” dan urutkan mulai dari biaya terendahnya.
Apply Dijkstra’s Algorithm sebagai berikut :
(7)
Open (ascending)
Kembali ke Loop.
[ S(0) ] [ B(1), A(4) ] [ E(3), A(4), F(4) ] [ A(4), F(4), G1(6), H(7) ] [ F(4), C(5), G1(6), D(6), H(7) ] [ C(5), G2(5), G1(6), D(6), I(6), H(7) ] [ G2(5), G1(6), D(6), I(6), H(7) ]
G2(5) adalah goal dengan cost paling minimal. 6.
Implementasi pada Graph
[ S(0) ]
S 2
g ' (ni ) = g ' (n ) + c(n, ni ) dimana c(n, ni ) adalah cost dari n ke ni.
3
A
[ B(3), G1(5), C(5) ]
B 1
3
5
G1
3
C 2
2
G2
Graph
[ C(4), D(6), G1(7) ] D
1
2
E
Arwin@23206008
[ A(2), B(3) ]
[ G2(6), D(6), E(6), G1(7) ] Hanya membutuhkan 5 step untuk mendapatkan G2(6) sebagai goal dengan cost paling minimal Urutan searching Arwin@23206008
13
7.
14
Tugas Individu I → terapkan Metode BFS, DFS dan Optimal Search untuk penelusuran dari
Initial State
Goal State
2
3
1
Arad ke Bucharest menggunakan topologi Tree Diagram dan Graph. Rule :
2
1
8
4
8
7
6
5
7
8
3
2
3
4
1
8
4
5
7
6
5
3 4
6
5
a. Boleh memotong jalur. b. BFS dan DFS kemungkinan tidak optimal namun algoritma harus benar. c. BFS dan DFS → solution path, Optimal Search → rute terderkat.
2
3
2
1
8
4
1
7
6
5
7
(A)
6
(B)
(C)
Tanggal 22 September 2006 Heuristiknya adalah : 1.
Heuristic search (informed search) → estimasi cost dari node ke GS-nya.
2.
Heuristik dapat dianggap sebagai pruning (memotong pohon) dengan mempertimbangkan
h (1) = Jumlah kotak yang tidak tepat (match). h ( 2 ) = Jumlah jarak horisontal dan vertikal kotak yang tidak tepat (Manhattan distance)
node yang promising (menjanjikan atau lebih pasti menuju GS). Seyogyanya fungsi heuristik tidak
h1 ( A ) = 2; h1 ( B ) = 3; h1 ( C ) = 4
terlalu rumit (sederhana dan mudah untuk dihitung) karena akan diaplikasikan ke setiap node.
h2 ( A ) = 2; h2 ( B ) = 4; h2 ( C ) = 4
maka state A adalah yang terdekat dengan GS.
Kadang dinotasikan dengan penjumlahan berbobot h yang menunjukkan seberapa (relatif) penting satu heuristik terhadap heuristik lainnya.
h = w1 h1 + w2 h2 + ............. + wn hn dimana wn = weighting. 4.
Metode Hill Climbing (Menuju puncak) → Hitung fungsi heuristik terkecil sebagai tujuan
berikutnya (next n ).
Nilai heuristik terkecil dianggap sebagai yang paling dekat dengan GS.
Constarint adalah local optimum (puncak-puncak lokal) → nature-nya. Filosofi →
3.
Heuristic function → Suatu cara untuk mengkuantifikasi heuristik sehingga fungsi tersebut
dapat digunakan untuk estimasi seberapa dekat current state terhadap goal state. Contoh : Kotak-8.
Bila nilai heuristik node anak = nilai heuristik node induk, proses tetap berjalan selama tidak < dari nilai heuristik node anak (path akan flat).
Arwin@23206008
Arwin@23206008
15
5.
16
Complexity → seberapa baik heuristiknya (kurang atau tidak akurat) atau seberapa baik
9.
Perbedaan Optimal Search dan Best First Search a.
heuristik memperkirakan current state terhadap goal state-nya.
Optimal search → menghitung real cost dari IS ke node dengan cost yang terkecil
(accumulative cost). 6.
Tugas Individu 2 (290906) → Terapkan Hill Climbing dan Best First Search (open list) untuk
b.
Best First search → menghitung estimated cost dari node n ke GS yang terkecil.
mencari solution path dari Arad ke Bucharest. 10. 7.
Metode Best First Search → Membandingkan nilai heuristik tiap node yang di-expand. Node
Tugas Besar → Terapkan DFS, BFS dan Best First Search untuk Kotak-8 menggunakan
bahasa pemrograman. Aturan :
dengan nilai heuristik terkecil akan di-expand terlebih dulu. Bila goal belum ditemukan, periksa node berikutnya dengan nilai heuristik terkecil pada depth yang sama kemudian di-expand dan periksa
a.
apakah ada goal pada cabang-cabangnya. Bila belum ditemukan, lakukan proses yang sama hingga
b.
Utamakan algoritma → bagaiman node-node di-generate dari node induknya.
goal ditemukan.
c.
Tampilkan struktur datanya → bagaimana open list diimplementasikan (queue, linked-
Initial
GUI tidak penting,
list, dll) dan bagaiman ke-8 angka direpresentasikan (array atau vektor dll).
S
d.
Optimal Search g’(n) = cummulative cost dari IS ke n
Bahasa pemrograman bebas.
e.
Boleh ambil resource di Internet → harus paham algoritmanya.
f.
Presentasi di akhir kuliah semester.
g.
Hati-hati → setengah konfigurasi langkah kotak-8 tidak akan capai GS.
h.
Petunjuk → start dari GS dan diacak beberapa langkah agar ada solution path-nya.
n c(n,ni)
h Tanggal 13 Oktober 2006
Best First Search
1.
Goal
h ( ni ) = c ( n, ni ) dimana c(n, ni ) adalah cost dari n ke ni. 8.
Penggunaan search bukan hanya sekedar untuk game sebagaimana yang dicontohkan. Aplikasi
lainya adalah :
Pertanyaan : Optimality ? Completeness ? Pseudo code ? Prosedur pelacakan → pseudo code
a.
Assembly line (manufacturing).
b.
Pattern recognition.
c.
Speech recognition.
(1)
Berikan simpul awal S pada “open”, h(s)
(2)
Loop : if open = kosong then exit(fail).
d.
Planning/control/optimization.
(3)
n := first(open)
e.
Finance.
(4)
if goal(n) then exit(success)
(5)
Remove(n, open) dan Add(n, closed)
(6)
Ekspansikan n, hitung h ( ni ) untuk semua simpul anak ni dan bubuhkan pointer dari ni
2.
ke-n. Berikan semua simpul anak pada “open” dan urutkan mulai dari biaya terendahnya. (7)
Kembali ke Loop. Arwin@23206008
Expert System (Sistem Pakar) → major branches of AI :
a.
Vision system.
b.
Robotic.
Arwin@23206008
18
17
3.
c.
Natura al language processing. p
d.
Learning system.
e.
al networks. Neura
f.
Expert system.
a.
Knowledge base - contains the domain specific problem-solving knowledge.
b.
Facts - represent what we know at any time about the problem we are working at.
c.
Rules - represent relationships between the facts.
d. Inference engine - is a general program that activates the knowledge in the knowledge base.
Expert system m → softwaare komputer yang mengaandung knowlledge. Seseoorang bisa meenjadi
e.
expert karena peng galaman berttahun-tahun ddari pola/faktta/data/fenom mena/kasus yang dialami yang
Interface enables the user to communicate with the expert system.
d pola yang y dialami sebelumnya. s mirip dengan
6. 4.
Perbedaan antara Expert System dengan searching terletak pada fokus metodenya. ES berkaitan
dengan bagaimana membangun knowledge-base-nya dan searching terletak pada bagaimana control
Aplikasi ES
strategy-nya dilakukan. a.
Contro ol (air traffic)).
b.
Debug gging (software).
c.
Designn (computer configuration) c n).
7.
d.
Mediccal diagnosis.
a.
Domain expert.
e.
Instruction/trainingg.
b.
Knowledge engineer.
f.
Interppretation (speeech).
c.
Knowledge user.
g.
Monitoring (nucleaar plant).
h.
Planning (mission planning). p
8.
i.
Factorry schedulingg.
paramedis dalam mendiagnosa penyakit. Ia memiliki 500 rule yang diadopsi dari kepakaran ahli
j j.
Predicction (weatheer).
kedokteran.
k.
Repairr (telephone)..
9. 5.
ES dikembangkan oleh :
MYCIN → software yang dikembangkan pada tahun 1970-an di MIT untuk membantu
ES tidak dibangun dari buku-buku troubleshooting namun dari kepakaran, insting, heuristic,
knowledge, intuisi dan lain sebagainya.
Architecture of Expert Sysstem
10.
ES technology → components of rule-based system are
a.
Working memory.
b.
Knowledge base.
c.
Inference engine.
Rule-based ES → biasanya dinyatakan dalam natural language, namun dibedakan dalam :
A Arwin@2320 06008
a.
Quantifier.
b.
Values.
Arwin@23206008
19
20
Antecedent dibagi atas dua komponen ini. Consequence tertentu dapat digunakan sebagai
2.
Bentuk program Prolog
antecedent rule yang lain (proses chaining). ο
predicate logic
conclusion). Kesimpulan-kesimpulan antara ini yang diekstraksi dari human expert oleh knowledge
ο
Hubungan antara obyek dinyatakan dalam bentuk predicate.
engineer.
ο
Kaidah (rule) mampu melakukan deduksi fakta baru dari fakta yang ada.
ο
Ada contol strategy dan proses matching.
ο
Predicate logic harus konsisten.
ο
Rule dapat didefinisikan secara rekursif.
11.
12.
ES sebelum mendapatkan kesimpulan akhir, perlu kesimpulan-kesimpulan antara (intermediate
Dalam beberapa ES, perlu memasukkan fakta ketidak pastian yang akan dipropagasi ke dalam
conclusion yang diambil ES.
13.
Automated Knowledge Acquisition → membangun knowledge secara otomatis melalui
penyampaian fenomena, data dan lain-lainnya.
14.
Semantic web → didasarkan pada Ontology (suatu knowledge).
predicate calculus
⇒
predicate(object1, object2, ..... , objectn) IF .... THEN ....
ο
Matching dari arah backward; query menjadi goal (root) atau query menjadi consquence.
ο
Fakta-fakta harus di-assign dulu dan kemudian kaidah dituliskan.
ο
Fakta dan rule adalah clause.
ο
Prolog → digunakan di ES.
Membangun sebuah
knowledge base melalui komunitas di Internet.
15.
Knowledge-based system ⇔ Expert System.
16.
Cara representasi knowledge ada beberapa cara :
Tanggal 17 Nopember 2006
1.
a.
If … then … rule.
b.
Frame.
c.
Semantic net.
d.
Predicate calculate/logic.
Yang telah dipelajari sejauh ini dibagi menjadi 2 (dua) bagian besar yang disebut dengan
symbolic atau classical AI yakni :
2.
a.
Intelligent search.
b.
Knowledge representation.
Teknik AI mempunyai keterbatasan dalam beberapa hal tertentu seperti pattern recognition
(data, sinyal, image, dll). Tanggal 10 Nopember 2006
1.
3.
Bahasa AI → bisa gunakan high-level programming language. Phyton language (object-
oriented namun lebih sederhana daripada Java).
a.
LISP (LISt Programming) → obyek-obyek disusun dalam suatu list untuk diproses.
Contoh : emacs. Yang sedang berkembang adalah Common LISP. b.
Prolog (PROgramming LOGic) → penalaran logika dan bukan untuk komputasi
(Artificial) Neural Network → computational model inspired from neurobiological model of
brain. Human brain computer in different way from digital computer (von Neumann machine).
a.
Highly complex, non-linear and parallel computing.
b.
Many times faster than d-computer in pattern recognition, perception, motor control.
c.
Has great structure and ability to build up its own rules by experience. Dramatic
development within 2 years after birth. Continues develop afterward (language learning device before 13 years old).
numerik. Kemudahan representasi rule (kaidah). Arwin@23206008
Arwin@23206008
21
d.
22
Platicity → ability to adapt to its environment.
4.
Rule yang disimpan dalam bentuk fitur-fitur dari obyek yang dilihat.
5.
Definisi ANN tergantung dari perspektifnya :
a.
Machine designed to model the way in which brain performs tasks (learning).
b.
Masssively parallel distributed processor (knowledge acquired thru learning process).
ο
1011 neurons in human cortex
ο
60 x 1012 synaptic connections
ο
104 synapses per neuron
ο
10-3 sec cycle time (computer : 10-9 sec)
ο
energetic efficiency : 10-16 joules operation per second. (computer : 10-6 joules)
Neuron → simple (basic) processing unit.
6.
c.
Learning machine (modify synaptic weights and topology).
d.
Connectionist machine.
a.
b.
x2
wk 2
bk
∑
vk
∑w
+ bk
ϕ ( .)
yk
Generalization → ability to produce reasonable output fro inputs not encountered xm
wkm
Complex problem decompossed into simple tasks and assigned to a NN.
Sifat-sifat :
a. b.
8.
wk 1
Benefits :
during training.
7.
x1
Non-linearity → non-linear mapping (asosiasi antara input dan output).
vk =
I/O mapping.
c.
Adaptivity → adapt synaptic weight to changes of environment.
d.
Evidential response → confidence.
e.
Contextual information processing.
f.
Fault tolerance.
g.
VLIS implementability.
h.
Uniformity if analysis and design.
i.
Neurobiological analogy.
m
kj x j
j =1
yk = ϕ ( v k )
Human brain (nervous system)
9.
Axon → activation function (threshold
10.
Metode pembelajaran → supervised dan unsupervised.
atau sigmoid
).
Tanggal 24 Nopember 2006
1.
Arwin@23206008
Terdapat 2 (dua) macam output, yakni :
a.
Target.
b.
Sesungguhnya (actual). Arwin@23206008
23
24
ο
×
ο
5.
Link → transfer function (hubungan antara input dan output). )
Synaptic link → linear input-output relation where x j * wkj
)
Activation link → non-linear input-output relation via an activation unit.
Bobot tidak digambarkan secara eksplisit, namun secara implisit adalah nilai bobotnya.
Recurrent network → mempunyai umpan balik dari satu sinyal ke sinyal yang lain. x 'j ( n )
x j ( n)
2.
3.
4.
w
Terdapat 2 (dua) fase penggunaan neural network :
z −1 yk ( n ) =
a.
Fase training.
b.
Fase Recognition (execution).
∞
∑w
6.
Inhibitiry (deaktif, off).
x j (n − l )
Konvensi notasi node dan link adalah : (bebas, yang penting konsisten).
j
Excitatory (aktif, on).
b.
l +1
i =0
Sifat axon
a.
yk ( n )
k
wkj
7.
Neural network as a directed graph (SFG)
Network architecture → how neurons are interconnected each other. )
x0 = +1
Single layer feedforward network → single computation layer.
wk 0 = bk x1
x2
wk 1
wk 2
vk
ϕ ( .)
yk
wkm
xm
ο
Node → signal.
Arwin@23206008
Arwin@23206008
25
)
26
Multilayer feedforward network → hidden layers. 10.
Setiap input akan menghasilkan actual output dan dibandingkan dengan target yang harus
dicapai dan dilakukan secara berulang (iteratif) hingga error membentuk kurva yang menuju nol seiring dengan berjalannya waktu.
Fungsi tidak diketahui sehingga harus dicari
df =0 dx
gradien dari fungsi tersebut.
Untuk
mendapatkan
nilai
minimum,
diperlukan ribuan epoch (representasi pola yang dilatihkan)
11.
massive interconnections (parallel computations)
Perceptron → Gender classification
computation
input layer
output layer
h
w1
w0 y
w2
fully connected
v
hidden layer
Jumlah neuron di input layer dan output layer tergantung pada problem yang akan
⎧ 1 if male y = signum ( hw1 + vw2 + w0 ) = ⎨ ⎩ −1 if female
diselesaikan. Jumlah hidden layer ditentukan melalui trial-error untuk mendapatkan hw1 + vw2 + w0 = 0 → v = −
performa terbaik. Cara komputasi sama, menggunakan rumus standar. 8.
Bias adalah operating condition (demo gunakan toolbox neural network Matlab).
9.
Learning → aktivitas meningkat pada jaringan sinapsis yang bertujuan untuk adjustment nilai
bobot. Diberikan pada fase latihan dengan menerapkan data training dan data targetnya. Error yang
w w1 h− 0 w2 w2
⇓ y = mx + c
)
Persamaan garis (decision boundary) dengan gradien garis −
w w1 dan bias − 0 w2 w2
Decision boundary akan berubah-ubah sesuai dengan adjustment w1 dan w 2 , proses
tetap berlangsung hingga error minimal atau 0.
timbul digunakan untuk adjustment nilai bobot-bobotnya karena parameter yang bisa dirubah adalah bobot neural network melalui algoritma tertentu.
Arwin@23206008
Arwin@23206008
27
12.
28
)
Bias diperlukan agar decision boundary tidak melewati origin atau titik (0,0).
)
Masalah di atas disebut dengan Linearly Separable Classification Problem.
2.
Beberapa contoh aplikasi neural network (thesis)
a.
Face recognition.
b.
Estimasi – dengan akurasi tertentu – kebutuhan BBM pada SPBU dengan mempelajari
Training algorithm
o
If the pattern is correctly classified, no change is made to weight vector.
o
If the pattern is not correctly classified, then :
pola suplai pada masa lalu sebagai bahan pelatihan neural network. c.
Klasifikasi bentuk kapal perang.
1
if
is in class1 but a = 0
1
if
is in class2 but a = 1
d.
Maintenance.
e.
Hand recognition.
Output can only be -1 and 1 (or 0 and 1).
f.
Noise cancelation.
Can only solve linearly separable problems (creates a straight decision
g.
Klasifikasi noise knalpot mobil.
boundary which divides samples into two separate classes).
h.
Robotic.
Limitations
o
Contoh : AND function problem 13.
Neural network efektif pada aplikasi-aplikasi yang berkenaan dengan :
a.
Prediction (forecasting, valas, weather).
b.
Optimization (routing).
c.
Recognition (face, character).
d.
Classification.
p1 0 0 1 1
p2 0 1 0 1
a 0 0 0 1
p2
Class2 Class1 p1
Tanggal 1 Desember 2006 o
1.
Perceptron training 1,
, ,
Choose a weight vector that is orthogonal (tegak lurus) to the decision surface. In this
case, choose
,……….., ,
,………..,
2 . 2 0.
o
Find the bias to satisfy the equation :
o
Pick a point on the decision surface :
o
Solve the equation : 2
o
Test the equation with the original inputs. Compare the result with the rule above to
2
1.5 0
1.5 3
0 . 0, so the bias b = -3.
determine if weight updating is necessary.
dimana : 3.
0, class1, output = 1
Single-layer perceptron is unable to solve the XOR problem because of its unique input-
output mapping.
0, class2, output = 0
Arwin@23206008
Arwin@23206008
29
p1 0 0 1 1
p2 0 1 0 1
a 0 1 1 0
30
4.
x2
Jumlah layer
menentukan kemampuan neural network dalam melakukan klasifikasi data.
Dengan 3-layer pada umumnya sudah cukup untuk menyelesaikan problem serumit apapun (kinerja tidak berbeda dengan yang menggunakan 4 atau 5-layer). Untuk jumlah class > 2, tambahkan jumlah
Class1
Class2
neuron output. x1
5.
Setiap 2 minggu, selalu ditemukan arsitektur baru neural network berikut algoritma
belajarnya.
x1
y
XOR problem not solved and Interwined problem also not solved. Decision boundary is half-pane.
x2
Tanggal 8 Desember 2006
1.
Multi Layer Perceptrons J Multi Layer Feedforward ANNs
2.
Hidden layer of computation nodes min. 1 layer. Jumlah node pada input dan output layer
sangat ditentukan oleh tipe problem yang akan diselesaikan atau tergantung pada tingkat kompleksitas Untuk menyelesaikan problem XOR yang non-linearly separable problem, digunakan Multilayer Perceptrons (MLPs) sebagai berikut :
problem.
3.
Input propagates in a forward direction, layer-by-layer basis.
4.
Terdapat 2 (dua) macam learning, yakni : supervised (ada target, teacher) dan unsupervised.
5.
Mode supervised learning
x1
y
XOR problem solved but Interwined problem not solved. Decision boundary is convex shape.
Error dihasilkan dari perbandingan antara actual output dengan target. x2
×
x1
y
XOR problem solved but Interwined problem also solved but must be with a proper algorithm. Decision boundary is complex (arbitrary) shape.
Error di-back-propagate-kan unutk meng-update parameter NN. Proses dilakukan untuk semua pola input hingga error adalah minimal atau dengan kata lain NN telah “pintar” dalam mengenali inputoutput pattern.
x2
Arwin@23206008
Arwin@23206008
31
Error back-propagation algorithm
c.
•
Supervised learning algorithm.
(difference).
•
Error-correction learning algorithm.
d.
•
Forward bias.
weights to minimize the error.
•
6.
32
o
Input vector is applied to input nodes.
o
Its effects propagate through the network layer-by-layer.
o
With fixed synaptic weights.
e.
10.
Synaptic weights are adjusted in accordance with error signal.
o
Error signal propagates backward, layer-by-layer fashion.
Backward Computation: Backpropagate the error through the network and adjust the
Iteration: Repeat steps 2-4 until a desired error goal is reached.
Salah satu cara menghitung error BP menggunakan rumus average squared error energy atau
average error all training samples.
Backward pass. o
Error Computation: Compare the output with the desired output and compute the error
Eav =
1 N
N
adalah training sample
Dimana
∑ E ( n)
adalah iterasi ke-n.
n =1
MLP distinctive characteristics •
Non-linear activation function must be differentiable and in form of sigmoidal or logistic
11.
Konvensi penulisan notasi berdasarkan ada tidaknya hidden layer, sebagai berikut :
function. Example :
•
a.
Tanpa hidden layer
One or more hidden layers of hidden neurons can progressively extracting more
meaningful features from input patterns.
7.
Terdapat 2 (dua) sinyal yang berperan yakni :
j
w ji
8.
a.
Function signal J input signals which propagate to output nodes.
b.
Error signal J propagated backward to input nodes.
dj
yj
2 (dua) komputasi pelatihan yang berlaku adalah : b.
a.
Computations of function signals.
b.
Computations of an estimate gradient vector J gradient descent atau gradient of error
Dengan hidden layer
surface with respect to the weights. j k
9.
Summary of BP Algorithm is as followed : (devised by Rumelhart)
w ji
wkj
yk
dk
i
a.
Initialization: Randomize the weights to small values.
b.
Presentation: Apply a pattern to the input and calculate the network output.
δj
Arwin@23206008
δk
Arwin@23206008
33
12.
Delta rule, gradient descent dan weights
w ji ( n + 1) = w ji ( n ) + Δw ji ( n ) Gradient, gunakan chain rule derivative
Δw ji ( n ) = −η
∂E ( n ) ∂w ji ( n )
Learning rate J [0, 1]. Nilai lebih kecil akan menghasilkan path error surface yang lebih landai (smooth) 13.
Dalam beberapa konteks, bisa ditambahkan momentum term,
, agar tidak terjebak pada local
minima. Nilai antara [0, 1].
14.
Hidden layer yang terlalu banyak dapat membuat generalisasi buruk. Belum ada panduan yang
pasti mengenai jumlah neuron pada hidden layer. 15.
This is the end of the bloody lecture ………………………..
Arwin@23206008
