LEARNING ARTIFICIAL INTELLIGENT

LEARNING

ARTIFICIAL INTELLIGENT

OUTLINE  Decision tree learning  Jaringan Syaraf Tiruan  K-Nearest Neighborhood  Naïve Bayes

JARINGAN SYARAF TIRUAN (JST) Intro     

Definisi ANN Model Matematis Neuron Fungsi Aktivasi Arsitektur ANN Proses Belajar (Learning)

Perceptron ANN dengan Supervised Learning

ANN dengan Unsupervised Learning Permasalahan pada ANN

JARINGAN SARAF TIRUAN (JST) o Otak terdiri dari neuron-neuron dan penghubung yang disebut sinapsis o Neuron bekerja berdasarkan sinyal/impuls yang diberikan pada neuron o Neuron memiliki 3 komponen penting yaitu dendrit, soma dan axon

Dendrit

Badan Sel

Treshold

Akson

o jaringan saraf tiruan adalah paradigma pengolahan informasi yang terinspirasi oleh sistem saraf secara biologis o JST dibentuk sebagai generalisasi model matematika dari jaringan syaraf biologi, dengan asumsi bahwa : 1. Pemrosesan informasi terjadi pada panyak elemen sederhana (neuron). 2. Sinyal dikirim diantara neuron-neuron melalui penghubung-penghubung. 3. Penghubung antar neuron memiliki bobot yang akan memperkuat atau memperlemah sinyal. 4. Untuk menentukan output, setiap neuron menggunakan fungsi aktivas. Besarnya output ini selanjutnya dibandingkan dengan suatu batas ambang. o JST juga ditentukan oleh 3 hal : a. Pola hubungan antar neuron (disebut aritektur jaringan).

b. Metode untuk menentukan training/learning).

bobot

penghubung

(disebut

metode

c. Fungsi aktivasi, yaitu fungsi yang digunakan untuk menentukan keluaran suatu neuron.

KOMPONEN JST oJaringan saraf tiruan memiliki komponen yang digunakan dalam membangun suatu arsitektur-arsitektur jaringan

oNeuron dikelompokkan ke dalam beberapa lapisan yang mana saling memiliki hubungan satu dengan yang lainnya yang disebut dengan lapisan (layer) 1. Lapisan Masukan (Input Layer), berisi menyimpan sebuah nilai masukan

node-node

yang masing-masing

2. Lapisan Tersembunyi (Hidden Layer), proses pada fase pelatihan dan fase pengenalan dijalankan di lapisan ini 3. Lapisan Keluaran (Output Layer), menampilkan hasil perhitungan sistem

ARSITEKTUR JST oJaringan dengan lapisan tunggal (single layer network)

oJaringan dengan banyak lapisan (Multi layer network)

PERCEPTRON Neuron: Sel syaraf biologis Perceptron: Sel syaraf buatan  Input function  Activation function  Output

Perceptron x1 x2 . . . xp

w

 w

y

PERCEPTRON Jika manusia punya 10 milyar neuron, apa yang bisa dilakukan? Sangat banyak hal bisa dilakukan Apalagi jika Multiple Intelligence Perceptron = MODEL SEDERHANA dari neuron Apa yang bisa dilakukan oleh satu perceptron? Klasifikasi Prediksi Optimasi, …

AND x2

1

x1

x2

y

0

0

0

0

1

0

1

0

0

1

1

1

x1 0

1

x1 + x2 – 1,5 = 0

w1.x1 + w2.x2 – 1,5 = 0

AND  (v)

1 if v   0 if v  

 (v )  

1

x1

x2

y

0

0

0

0

1

0

1

0

0

1

1

1

x1

p

0



i 1

w=1

 x2

v

v   wi xi

w=1

y θ = 1,5

y

OR x2

1

x1 0

1

x1 + x2 – 0,5 = 0

x1

x2

y

0

0

0

0

1

1

1

0

1

1

1

1

OR  (v)

x1

x2

y

0

0

0

0

1

1

1

0

1

1

1

1

x1

1 p

0

v



v   wi xi i 1

w=1

 x2

1 if v   0 if v  

 (v )  

w=1

y θ = 0,5

y

XOR x2

x1 - x2 + 0,5 = 0

1

x1 0

x1 - x2 - 0,5 = 0

1

x1

x2

y

0

0

0

0

1

1

1

0

1

1

1

0

XOR

θ = 0,5 x1

w = -1



y

x1

x2

y

0

0

0

0

1

1

1

0

1

1

1

0

w=1

w=1

 w=1 x2

w = -1



y

θ = 0,5

w=1

y θ = 0,5

y

PERCEPTRON NETWORK x1 x2 . . . xp

w

w



y



y



y

LEARNING Bagaimana menemukan weights yang tepat? Meminimumkan error

x2

x1

w1x1 + w2x2 - θ= 0

x2

x1

ACTIVATION FUNCTIONS Hard Limit Threshold Linear (Identity)

Sigmoid Radial Basis Function (RBF) …

HARD LIMIT  (v)

1 if v  0  (v )   0 if v  0

1

0

v

THRESHOLD  (v)

1 if v    (v )   0 if v  

1

0



v

SYMETRIC HARD LIMIT  (v)

1 if v  0   (v)  0 if v  0  1 if v  0 

1

0 -1

v

BIPOLAR THRESHOLD 1 if v     (v)  0 if v    1 if v   

 (v)

1

0 -1



v

LINEAR (IDENTITY)  (v)

 (v )  v

1

-1

0 -1

1

v

PIECEWISE-LINEAR  (v)

1   (v)  v  0,5 0 

1

-0,5

0

0,5

v

jika v  0,5 jika 0,5  v   0,5 jika v   0,5

SYMETRIC PIECEWISE-LINEAR  (v)

1   (v)  v  1 

1

-1

1

-1

v

jika v 1 jika 1  v   1 jika v   1

SIGMOID  (v)

1  (v )  1  e  av

1

0

v

SYMETRIC (BIPOLAR) SIGMOID  (v)

1  e  av  (v )  1  e  av

1

0

-1

v

RADIAL BASIS FUNCTION (RBF)  (v)

 (v )  e

1

0

v

 av 2

ARSITEKTUR ANN Para ahli memodelkan sel syaraf otak manusia ke dalam berbagai arsitektur ANN (susunan neuron) yang berbeda-beda. Masing-masing arsitektur menggunakan algoritma belajar khusus.

SINGLE-LAYER FEEDFORWARD NETWORKS

Input layer of source node

Output layer of neurons

MULTI-LAYER FEEDFORWARD NETWORKS

Input layer of source node

Layer of hidden neurons

Layer of output neurons

PROSES BELAJAR (LEARNING) Learning process

Learning algorithm (rules)

Error-correction learning

Bolzman learning

Thorndike's law of effect

Hebbian learning

Learning paradigms

Competitive learning

Supervised learning

Reinforcement learning

Self-organized (unsupervised) learning

PERCEPTRON: MODEL

PERCEPTRON: SIGNAL-FLOW GRAPH

p

v   wi xi   i 1 p

Decision boundary 

 w x   0 i 1

i i

x2

x1

w1x1 + w2x2 - θ= 0 Decision boundary

Pelamar

IPK

Psikologi

Wawancara

Diterima

P1

Bagus

Tinggi

Baik

Ya

P2

Bagus

Sedang

Baik

Ya

P3

Bagus

Sedang

Buruk

Ya

P4

Bagus

Rendah

Buruk

Tidak

P5

Cukup

Tinggi

Baik

Ya

P6

Cukup

Sedang

Baik

Ya

P7

Cukup

Sedang

Buruk

Ya

P8

Cukup

Rendah

Buruk

Tidak

P9

Kurang

Tinggi

Baik

Ya

P10

Kurang

Sedang

Buruk

Tidak

P11

Kurang

Rendah

Baik

Ya

Pelamar

IPK

Psikologi

Wawancara

Diterima

P1

3

3

2

1

P2

3

2

2

1

P3

3

2

1

1

P4

3

1

1

0

P5

2

3

2

1

P6

2

2

2

1

P7

2

2

1

1

P8

2

1

1

0

P9

1

3

2

1

P10

1

2

1

0

P11

1

1

2

1

Wawancara

3

2

1 4 0 0

3 2

1 2

1

3 4 IPK

0

Psikologi

Pola

Pix 1

Pix 2

Pix 3

Pix 4

Pix 5

…

Pix 100

E1

0

0

1

1

1

…

0

F1

0

0

1

1

1

…

0

G1

0

1

1

1

1

…

1

O1

0

1

1

1

1

…

1

0

1

1

1

1

…

1

.. O5

MULTI-LAYER PERCEPTRON (MLP)

ALGORITMA BELAJAR PROPAGASI BALIK Definisikan masalah  Matriks pola masukan (P)  matriks target (T)

Inisialisasi parameter jaringan    

Arsitektur jaringan (misalkan I-H-O) Synaptic weights  acak (atau dengan metode tertentu) Learning rate (lr)  laju belajar Threshold MSE  untuk menghentikan learning

ALGORITMA BELAJAR PROPAGASI BALIK Pelatihan Jaringan  Perhitungan Maju

A1 

1 1  e(W 1* P  B1)

A2  W 2 * A1  B2

E  T  A2 MSE 

2 E 

N

ALGORITMA BELAJAR PROPAGASI BALIK Pelatihan Jaringan  Perhitungan Mundur

D2  (1  A2 2 ) * E

D1  (1  A12 ) * (W 2 * D2)

dW1  dW1  (lr * D1 * P)

dB1  dB1  (lr * D1)

dW 2  dW 2  (lr * D2 * P)

dB2  dB2  (lr * D2)

ALGORITMA BELAJAR PROPAGASI BALIK Pelatihan Jaringan  Perhitungan Mundur

W1  W1  dW1

B1  B1  dB1

W 2  W 2  dW 2

B2  B2  dB2

ALGORITMA BELAJAR PROPAGASI BALIK Langkah-langkah di atas adalah untuk satu kali siklus pelatihan (satu epoch). Biasanya, pelatihan harus diulang-ulang lagi hingga jumlah siklus tertentu atau telah tercapai MSE yang diinginkan. Hasil akhir dari pelatihan jaringan adalah bobot-bobot W1, W2, B1 dan B2.

PENGENALAN KARAKTER E, F, G, O Matriks P

Matriks T

Pola

Pix 1

Pix 2

Pix 3

Pix 4

Pix 5

…

Pix 100

E1

0

0

1

1

1

…

0

1

0

0

0

E

F1

0

0

1

1

1

…

0

0

1

0

0

F

G1

0

1

1

1

1

…

1

0

0

1

0

G

O1

0

1

1

1

1

…

1

0

0

0

1

O

E2

0

0

1

1

1

…

0

1

0

0

0

E

…

…

…

…

…

…

…

…

…

…

…

…

…

O5

0

1

1

1

1

…

1

0

0

0

1

O

N1 N2

N3

N4 Kelas

Training F2, G2, O2, … dan seterusnya hingga pola O5

W1 & W2: Random

W1

W2

-0.54 0.71

A1

-0.21 0.15

0.7

-0.52 -0.21

A2 T

E

0.9

1

0.1

0.1

0 -0.1

0.4

0 -0.4

0.3

0 -0.3

-0.53 0.91 -0.49 0.33

0.68 0.87

0.97 0.68 -0.18 -0.24

0.29 0.58 0.3

0.97 0.32 -0.18 0.25

-0.95 0.62

-0.17 0.62 -0.37 0.55

-0.12 0.88 -0.93 0.55

-0.12 0.89

0.75 0.34

0.9

-0.12 0.45

Testing

W1 & W2: Trained

W1

W2

0.01 0.31 -0.83

A2

Kelas

0.8

1

0.2

0

0.1

0

0.2

0

-0.38 0.19

0.34 0.22 0.62

0.74 0.35

0.87 -0.18

0.30 0.60

0.98 0.03

-0.53

-0.38

-0.09

Metode Konvensional (Template Matching)

Memory besar Waktu lama !!!

PERMASALAHAN PADA MLP Bagaimana struktur ANN yang optimal?    

Jumlah hidden layer Jumlah neuron pada hidden layer Jumlah neuron pada output layer Fungsi aktivasi yang optimal

Learning Rate Kapan Menghentikan Learning

ALGORITMA BELAJAR PROPAGASI BALIK Pelatihan Jaringan  Perhitungan Mundur

D2  (1  A2 2 ) * E

D1  (1  A12 ) * (W 2 * D2)

dW1  dW1  (lr * D1 * P)

dB1  dB1  (lr * D1)

dW 2  dW 2  (lr * D2 * P)

dB2  dB2  (lr * D2)

PENGENALAN TANDA TANGAN MENGGUNAKAN METODE JARINGAN SARAF TIRUAN PERCEPTRON DAN BACKPROPAGATION

PENGUMPULAN DATA oJenis data yang digunakan pada penelitian ini adalah jenis data kuantitatif

oJumlah data sebanyak 500 data tanda tangan dari 10 orang yang terdiri dari 400 data training dan 100 data testing.

ARSITEKTUR PROGRAM

AKUISISI CITRA oAkuisisi citra digital merupakan proses menangkap (capture) atau memindai (scan) citra analog sehingga diperoleh citra digital.

oAlat yang dapat digunakan untuk mengakuisisi citra digital antara lain: kamera digital, web cam, smart phone, scanner, mikroskop digital, pesawat rontgen, pesawat sinar X, pesawat MRI, pesawat CT Scan, atau pesawat radiodiagnostik lainnya.

PREPROCESSING oPemotongan (Cropping) oResize oCitra keabuan (grayscale)

oCitra biner

PEMOTONGAN (CROPPING) oProses croping dilakukan untuk mendapatkan masing-masing citra digital dari hasil scanning

RESIZE oProses resize adalah merubah ukuran piksel pada semua citra

CITRA RGB o Inputan citra digital awal masih berbentuk citra RGB. RGB adalah suatu model warna yang terdiri dari merah, hijau, dan biru digabungkan dalam membentuk suatu susunan warna yang luas. Setiap warna memiliki range 0 – 255. Dengan cara ini, akan diperoleh warna campuran sebanyak 256 x 256 x 256 = 1677726 jenis warna.

CITRA KEBUAN

(GRAYSCALE)

CITRA BINER o Citra biner adalah citra digital yang hanya memiliki dua kemungkinan nilai pixel yaitu hitam dan putih. Hanya dibutuhkan 1 bit untuk mewakili nilai setiap pixel dari citra biner.

oSetelah nilai warna citra diubah dalam biner, nilai biner tersebut akan diubah yang sebelumnya bernilai 0 menjadi 1 dan 1 menjadi 0. Dengan tujuan mengubah latar gambar menjadi nilai 0 dan objek menjadi nilai 1, karena pola dari nilai 1 yang akan dipelajari nantinya.

LABELING o Setelah preprocessing selesai maka akan didapat nilai biner dalam bentuk matrix. Sebelum masuk proses pemberian label data matrix diubah menjadi vector (matrix satu baris).

o Proses pemberian label ini adalah proses klasifikasi pada setiap vector dari semua 400 citra latih yang sudah didapatkan

o Pemberian label ini bertujuan agar vector yang sudah dilatih dapat dikenali sebagai vector dari citra tanda tangan yang tepat Citra Tanda Tangan

Label

Target

1 – 40

Afi

0001

41 – 80

Andri

0010

81 – 120

Candra

0011

121 – 160

Damar

0100

161 – 200

Dian

0101

201 – 240

Enjang

0110

241 – 280

Rama

0111

281 – 320

Restu

1000

321 – 360

Riqza

1001

361 – 400

Rizki

1010

PROSES PELATIHAN oPerceptron oBackpropagation

PERCEPTRON o Model jaringan perceptron ditemukan oleh Rosenblatt (1926) dan Minsky – Papert (1969). Model tersebut merupakan model yang memiliki aplikasi dan pelatihan yang paling baik di era tersebut.

ARSITEKTUR JST oJaringan dengan lapisan tunggal (single layer network)

ACTIVATION FUNCTIONS (FUNGSI AKTIVASI) Hard Limit Threshold Linear (Identity)

Sigmoid Radial Basis Function (RBF) …

FUNGSI AKTIVASI PERCEPTRON

PROSES PEMBELAJARAN PERCEPTRON

Misalkan:

•s adalah vektor masukan dan t adalah target keluaran •α adalah laju pemahaman (learning rate) yang ditentukan. •Ɵ adalah threshold yang ditentukan.

ket: y_in = nilai output sebelum dimasukan ke dalam fungsi aktivasi y = nilai output

Ket : Δw = nilai pembaruan bobot Δb = nilai pembaruan bias

Ada beberapa hal yang perlu diperhatikan dalam algoritma tersebut : •Iterasi dilakukan terus hingga semua pola memiliki keluaran jaringan yang sama dengan targetnya (jaringan sudah memahami pola).

•Pada langkah 2(c), perubahan bobot hanya dilakukan pada pola yang mengandung kesalahan (output ≠ target). •Kecepatan iterasi ditentukan pula oleh laju pemahaman yang dipakai. Semakin besar harga α, semakin sedikit iterasi yang diperlukan. Akan tetapi jika α terlalu besar, makan akan merusak pola yang sudah benar sehingga pemahaman menjadi lambat.

BACKPROPAGATION o Kelemahan JST terdiri dari layer tunggal membuat perkembangan JST menjadi berhenti pada sekitar tahhun 1970-an. o JST dengan layer tunggal memiliki keterbatasan dalam pengenalan pola. o Kelemahan ini bisa ditanggulangi dengan menambahkan satu/beberapa layer tersembunyi diantara layer masukan dan keluaran.

o backpropagation melatih jaringan untuk mendapatkan keseimbangan antara kemampuan jaringan untuk mengenali pola yang digunakan selama pelatihan serta kemampuan jaringan untuk memberikan respon yang benar terhadap pola masukan yang serupa (tapi tidak sama) denga pola yang dipakai selama pelatihan.

ARSITEKTUR BACKPROPAGATION o Backpropagation adalah metode penurunan meminimalkan kuadrat error keluaran.

gradien

untuk

o Ada tiga tahap yang harus dilakukan dalam pelatihan jaringan, yaitu tahap perambatan maju (forward propagation), tahap perambatan balik, dan tahap perubahan bobot dan bias.

FUNGSI AKTIVASI Dalam backpropagation, fungsi aktivasi yang sering dipakai adalah : oFungsi sigmoid biner yang memiliki range (0 hingga 1). o Fungsi sigmoid bipolar yang memiliki range (1 hingga -1).

FUNGSI SIGMOID BINER

FUNGSI SIGMOID BIPOLAR

PROSES PEMBELAJARAN BACKPROPAGATION Proses ini menggambarkan contoh tiga lapisan dengan dua input dan satu output yang ditampilkan

Ket: x = input V = bobot yang menuju hidden layer Z = hidden layer W = bobot yang menuju output layer Y = output layer

Proses perambatan maju / feed forward (mecari nilai hidden layer)

Ket : z_net = nilai bayangan hidden layer/nilai hidden layer yang belum masuk fungsi aktivasi Z = nilai hidden layer

Proses perambatan maju / feed forward (mecari nilai output layer)

Ket : y_net = nilai bayangan output layer/nilai output layer yang belum masuk fungsi aktivasi y = nilai hidden layer

Proses perambatan mundur / backpropagation (mecari nilai titik pembaruan bobot output layer)

Proses perambatan mundur / backpropagation (mecari nilai titik pembaruan bobot hidden layer)

Proses pembaruan bobot

o Lakukan langkah-langkah tersebut hingga nilai kesalahan terpenuhi atau hingga jumlah iterasi telah mencai batas maksimum.

o Setelah pelatihan selesai dilakukan, jaringan dapat dipakai untutk pengenalan pola. o Apabila fungsi aktivasi yang dipakai bukan sigmoid biner, maka langkah” harus disesuaikan lagi.

MENGHITUNG MSE

Ket : e = error n = jumlah data

MODEL PENGETAHUAN oModel pengetahuan pada dasarnya adalah sebuah wadah yang menyimpan arsitektur jaringan dari kedua algoritma yang sudah dilatih dengan data latih hingga mendapakan akurasi tertentu. oDi dalam model pengetahuan disimpan pengetahuan berupa jumlah layer, banyaknya neuron, target, bobot, fungsi aktivasi dan error

PROSES PENGUJIAN oData uji akan melewati proses awal yang sama seperti pada data latih yaitu proses preprocessing (pemotongan, resize, citra keabuan, citra biner dan vector) oSetelah vector data uji di dapat,vector tersebut akan dimasukan ke dalam model pengetahuan dan selanjutnya akan dilihat seberapa akurat model pengetahuan yang sudah dibuat

HASIL oPelatihan oPengujian okebutuhan jaringan sebagai berikut :

1. Batas epoch / iterasi maksimal adalah 1000 epoch 2. Target error (MSE) sebesar 0,0001 3. Learning rate sebesar 0,1 hingga 0,9

4. Untuk bobot jaringan ditentukan secara acak oleh komputer dengan mengambil nilai acak yang cukup kecil

PELATIHAN

(desimal)

citra

0001

1

40

40

0

Andri

0010

2

40

40

0

Candra

0011

3

40

40

0

Damar

0100

4

40

40

0

Dian

0101

5

40

40

0

Enjang

0110

6

40

40

0

Rama

0111

7

40

40

0

Restu

1000

8

40

40

0

Riqza

1001

9

40

40

0

Rizky

1010

10

40

40

0

400

400

0

Target

afi1 – afi40

Afi

andri40

candra1 – candra40

damar1 – damar40

dian1 – dian40

enjang1 – enjang40

Berdasarkan evaluasi hasil latih terhadap data latih, didapatkan rata – rata akurasi untuk proses pelatihan menggunakan algoritma Perceptron sebesar 100%.

Jumlah

Label

andri1 –

Perceptron

Target

Citra

rama1 – rama40

restu1 – restu40

riqza1 – riqza40

rizki1 – rizki40

jumlah

Citra dikenali

Citra tidak dikenali

PELATIHAN Backpropagation

Jumlah

(desimal)

citra

0001

1

40

40

0

Andri

0010

2

40

40

0

Candra

0011

3

40

40

0

Damar

0100

4

40

40

0

Dian

0101

5

40

40

0

Enjang

0110

6

40

40

0

Rama

0111

7

40

40

0

Restu

1000

8

40

40

0

Riqza

1001

9

40

40

0

Rizky

1010

10

40

40

0

400

400

0

Label

Target

afi1 – afi40

Afi

andri1 – andri40

candra1 – candra40

damar1 – damar40

dian1 – dian40

enjang1 –

Berdasarkan evaluasi hasil latih terhadap data latih, didapatkan rata – rata akurasi untuk proses pelatihan menggunakan algoritma backpropagation sebesar 100%. Dengan rata – rata error akhir (MSE) adalah 0,000099966 pada epoch ke – 1225.

Target

Citra

enjang40

rama1 – rama40

restu1 – restu40

riqza1 – riqza40

rizki1 – rizki40

jumlah

Citra dikenali

Citra tidak dikenali

PENGUJIAN Perceptron

Citra

Jumlah

Citra dikenali

Citra tidak dikenali

Afi41 – afi50

10

10

0

Andri41 – andri50

10

7

3

10

10

0

10

6

4

10

10

0

10

4

6

Rama41 – rama50

10

8

2

Restu41 – restu50

10

9

1

Riqza41 – riqza50

10

2

8

Rizki41 – rizki50

10

10

0

jumlah

100

76

24

Candra41 – candra50

Damar41 – damar50

Dian41 – dian50

Enjang41 – enjang50

didapatkan rata – rata akurasi untuk proses pengujian terhadap hasil latih yang menggunakan algoritma Perceptron sebesar 76%. Dan rata- rata kesalahan untuk setiap 10 data uji adalah 2 data.

PENGUJIAN Backpropagation

Citra

Jumlah

Citra dikenali

Citra tidak dikenali

Afi41 – afi50

10

10

0

Andri41 – andri50

10

9

1

10

10

0

10

9

1

10

10

0

10

3

7

Rama41 – rama50

10

10

0

Restu41 – restu50

10

10

0

Riqza41 – riqza50

10

5

5

Rizki41 – rizki50

10

10

0

jumlah

100

86

14

Candra41 – candra50

Damar41 – damar50

Dian41 – dian50

Enjang41 – enjang50

didapatkan rata – rata akurasi untuk proses pengujian terhadap hasil latih yang menggunakan algoritma Backpropagation sebesar 86%. Dan rata- rata kesalahan untuk setiap 10 data uji adalah 1 data.

Referensi :  Suyanto. 2007. Artificial Intelligence: Searching, Reasoning, Planning and Learning. Informatika, Bandung Indonesia. ISBN: 979-1153-05-1.  Russel, Stuart and Norvig, Peter. 1995. Artificial Intelligence: A Modern Approach. Prentice Hall International, Inc.