Minggu 10 - Artificial Neural Network (Part-1) PDF

Artificial Neural Network (Part 1) Inteligensi Buatan – IF3111 Program Studi Teknik Informatika Jurusan Teknologi Produksi dan Industri Institut Teknologi Sumatera 2022 1 Pokok Bahasan Introduction: neuron, topology, perceptron Neuron, Perceptron, m-...

Artificial Neural Network (Part 1) Inteligensi Buatan – IF3111 Program Studi Teknik Informatika Jurusan Teknologi Produksi dan Industri Institut Teknologi Sumatera 2022 1 Pokok Bahasan Introduction: neuron, topology, perceptron Neuron, Perceptron, m-of-n function Perceptron Training Rule: threshold neuron Gradient descent : unthresholded neuron 2  Biological Neuron Sebuah neuron memiliki ü Input bercabang (dendrites) ü Keluaran bercabang (axon) Informasi beredar dari dendrite ke axon melalui badan sel Axon terhubung ke dendrite melalui synapses ü Synapses bervariasi dalam kekuatan http://www.chemistry.ucsc.edu/~lokey/108A_10/images/neuron.png 3  Visualisasi Sederhana dari Neuron Artificial Neural Networks - Introduction Peter Andras ([email protected]) Soma (cell body) Axon The information transmission happens Dendrites at the synapses. synapses axon dendrites 4 Model Konektivitas Pertimbangan pada manusia: Waktu peralihan antara neuron: 0,001 detik Jumlah neuron: 1010 Koneksi per neuron: 104 - 5 Waktu pengenalan suatu tampilan/scene: 0,1 detik 100 langkah inferensi sepertinya tidak cukup banyak komputasi paralel 5 Gambaran Umum ANN Neuron, node, sel, unit, neurode (neuron & node) buatan Jenis neuron: ü input neuron: menerima input eksternal dari luar jaringan; ü hidden neuron: tidak memiliki interaksi langsung dengan 'outside world'; ü output neuron: menghasilkan beberapa output dari jaringan. 6 Karakteristik Masalah yang Sesuai Output fungsi target mungkin bernilai diskrit, bernilai real/float, atau vektor dari beberapa atribut bernilai real atau diskrit Training examples mungkin mengandung kesalahan Waktu pelatihan yang lama dapat diterima Evaluasi yang cepat dari fungsi target yang dipelajari mungkin diperlukan Examples: Kemampuan manusia untuk memahami Speech phoneme recognition [Waibel] Image classification [Kanade, Baluja, Rowley] fungsi target yang dipelajari adalah tidak Financial prediction Information extraction penting 7 ANN for Self Driving Car 8 Artificial Neuron Fungsi parameter dengan rentang keluaran terbatas Memiliki topologi yang bervariasi Topologi: struktur, arsitektur ü Neural framework q Jumlah Lapisan/Layer q Jumlah Neuron per Layer ü Interconnection structure q Interlayer Connection q Intralayer Connection q Self-Connection q Supralayer Connection 9 ANN Topology: Single Unit 10 A Layer of Neurons S neurons Input : vektor p (R dimensi) Weight : matrix S x R Output : vektor a (S dimensi) Common rule: R≠S Activation function bisa berbeda antar neuron. Input kadang dianggap layer khusus, tetapi tidak pada Hagan et al. 11 Multiple-Layers of Neurons Topologi: output layer (layer 3), hidden layer (layer 1 and 2) Input: vektor p (R dimensi) Weight: matrix SxR Output: vektor a (S dimensi) 12 Perceptron 13 Perceptron Perceptron: ANN yang berbasis pada satu unit neuron Input: real-valued vector. X0=1 (bias) Output: 1 or -1 (Activation function: sign) Learning output: weight vector w0..wn Hypotesis space: 𝐻= 𝑤 𝑤∈ℜ !"# } 14 Perceptron Mewakili permukaan keputusan hyperplane dalam ruang n-dimensi dari instance yang diberikan. Sumber: http://images.slidepl ayer.com/5/1579281 /slides/slide_32.jpg 15 Decision Surface of a Perceptron Beberapa surface/permukaan merupakan sesuatu yang tidak dapat dipisahkan secara linier 16 m-of-n function (Mitchell, 1999) Fungsi yang mana terdapat paling sedikit m dari n input boolean pada perceptron yang harus bernilai benar, agar pernyataan bernilai benar: ü Pada fungsi OR menggunakan pertimbangan m = 1 ü Dan pada fungsi AND menggunakan pertimbangan m = n Maka dapat digunakan suatu m-of-n function, dengan pengaturan: ü Semua bobot input diberikan nilai yang sama (contoh 0,5) dan lalu mengatur nilai ambang batas w0 ü Activation function menggunakan sign function 17 Perceptron : Contoh 1 Bayangkan kita memiliki 2 atribut input x1 dan x2 ∈ {-1,1} dan 1 atribut output o ∈ {-1,1}. Diberikan training set berikut: x1 x2 o(x1, x2) 1 1 +1 1 -1 -1 Kemudian masalah pembelajarannya adalah menemukan -1 1 -1 bobot w1 dan w2 dan nilai ambang (atau bias) sedemikian -1 -1 -1 rupa sehingga keluaran yang dihitung dari jaringan yang dibuat (yang diberikan oleh fungsi ambang linier) sama dengan keluaran yang diinginkan untuk semua contoh. 18 AND Perceptron: Dengan m-of-n function X0=1 -0.8 AND: m=n=2 x1 0.5 x0 x1 x2 S sign S | sign 1 1 1 0.2 +1 1 1 -1 -0.8 -1 0.5 x2 1 -1 1 -0.8 -1 1, 𝑛𝑒𝑡 > 0 1 -1 -1 -1.8 -1 𝑠𝑖𝑔𝑛 𝑛𝑒𝑡 = { −1, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 Atur semua bobot input dengan nilai yang sama dan atur nilai ambang batas dari w0 Sebagai contoh : e.g., w1=w2=0.5 → w0=-0.8 19 AND Perceptron x0 x1 x2 S sign 0.5 x1 + 0.5 x2 = 0.8 1 1 1 0.2 +1 1 1 -1 -0.8 -1 1 -1 1 -0.8 -1 1 -1 -1 -1.8 -1 x1 X0=1 -0.8 x1 0.5 x2 S | sign 1, 0.5𝑥1 + 0.5𝑥2 > 0.8 o(x1, x2) = { 0.5 −1, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 x2 20 Perceptron : Contoh 2 Bayangkan kita memiliki 2 atribut input x1 dan x2 ∈ {-1,1} dan 1 atribut output o ∈ {-1,1}. Diberikan training set berikut: x1 x2 o(x1, x2) 1 1 +1 1 -1 +1 -1 1 +1 -1 -1 -1 21 OR Perceptron x0 x1 x2 S sign 1 1 1 1.8 +1 0.5 x1 + 0.5 x2 = -0.8 1 1 -1 0.8 +1 1 -1 1 0.8 +1 x1 1 -1 -1 -0.2 -1 X0=1 0.8 x1 x2 0.5 S | sign 1, 0.5𝑥1 + 0.5𝑥2 > −0.8 o(x1, x2) = { 0.5 −1, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 x2 22 Perceptron : Contoh 3 Bayangkan kita memiliki 3 atribut input x1, x2, x3 ∈ ℜ dan 1 atribut output o ∈ {-1,1}. Diberikan training set berikut: x1 x2 x3 o(x1, x2, x3) 1 0 1 -1 Kemudian masalah pembelajarannya adalah 0 -1 -1 +1 menemukan bobot w1, w2, w3, dan nilai ambang -1 -0.5 -1 +1 (atau bias) sedemikian rupa sehingga keluaran yang dihitung dari jaringan yang dibuat (yang diberikan oleh fungsi ambang linier) sama dengan keluaran yang diinginkan untuk semua contoh. 23 Perceptron: Perceptron Learning Rule (PLR) 1. Inisialisasi random w (berdimensi n+1) 2. Ambil data , hitung actual output (o) perceptron. x berdimensi n. 3. Bandingkan actual output dengan desired target (y). If output=target then do nothing, X0=1 else lakukan perubahan w0 x1 𝑤! ⟵ 𝑤! + ∆𝑤! degan ∆𝑤! = 𝜂(𝑦 − 𝑜)𝑥! w1 𝜂: learning rate, konstanta [0,1] S | sign 4. Hitung error kumulatif: E = E + (y-o)2/2 wn xn 5. Kembali ke 2. 6. Akhir epoch: If E=0 (terminate), else set E←0 dan ulangi langkah 2 mulai dari data 1. 24  Perceptron: Example 3 dengan PLR (𝜼=0.1) x0 x1 x2 x3 o(x) X0=1 1 1 0 1 -1 w0 x1 1 0 -1 -1 +1 w1 x2 1 -1 -0.5 -1 +1 w2 S | sign x3 w3 1. Inisialisasi random w:. E=0 2. x= à o(x)=sign(0*1+0*1+0*1+0*1)=-1 3. output=target: do nothing 4. E=0+(-1-(-1))2/2=0 5. x= à o(x)=sign(0*1+0*0+0*-1+0*-1)=-1 6. output¹target: wi¬wi+0.1(1-(-1))xi w= = 7. E=0+(+1-(-1))2/2=2 Lanjutkan sendiri … 25 Perceptron Learning Rule: Example 3 terminate 26 Convergence Aturan pembelajaran Perceptron terbukti konvergen Jika data pelatihan dapat dipisahkan secara linier ü Fungsi XOR adalah salah satu contoh yang tidak dapat dipisahkan secara linier Learning Rate (𝜂) cukup kecil 27 Gradient Descent Fungsi kuadrat membuat kesalahan menjadi positif dan akan memberikan efek yang lebih besar ketika terjadi kesalahan 1/2 hanya membuat fungsi matematika menjadi lebih mudah Perlu mengubah bobot untuk meminimalkan kesalahan – Bagaimana caranya? Gunakan prinsip Gradient Descent 28 Gradient Descent (2) Gradient Descent adalah algoritma optimasi yang mendekati minimum lokal suatu fungsi dengan mengambil langkah-langkah yang sebanding dengan negatif dari gradien fungsi sebagai titik saat ini. 29 Gradient Descent (3) Gradient-Descent(training_example, 𝜼) Setiap training example merupakan pasangan dari bentuk ⃗ 𝑡 >, dimana 𝑥⃗ merupakan vektor dari nilai input dan t < 𝑥, merupakan nilai output target. Sedangkan 𝜂 merupakan learning rate (contoh 0,05) 30 Gradient Descent (4) Menginisialisasi setiap wi menggunakan beberapa nilai random yang kecil Lakukan hal berikut hingga memenuhi kondisi pemberhentian: ü Menginisialisasi setiap ∆𝑤! dengan nilai nol (0) ü Untuk setiap < 𝑥,⃗ 𝑡 > pada training_example, lakukan q Proses data masukan 𝑥⃗ pada suatu unit dan hitung nilai output o q Untuk setiap bobot dari unit linier wi, lakukan ∆𝑤! ⟵ ∆𝑤! + 𝜂(𝑡 − 𝑜)𝑥! ü Untuk setiap bobot dari unit linier wi, lakukan 𝑤! ⟵ 𝑤! + ∆𝑤! 31 Gradient Descent v.s. Perceptron Learning Rule Delta rule / gradient descent ü Mampu menghadapi data pelatihan yang tidak dapat dipisahkan secara linier ü Kombinasi input linier tanpa batas ü Kesalahan tidak terbatas pada nilai 0, 1, atau -1 (seperti pada PLR), tetapi mungkin memiliki nilai apa pun 32 Gradient Descent Jenis penerapan Gradient Descent adalah ü Batch Gradient Descent : menghitung dahulu jumlah delta/error dari keseluruhan data training, selanjutnya dilakukan pembaharuan bobot mempertimbangkan delta yang telah dijumlahkan tadi ü Incremental/Stochastic Gradient Descent : menghitung delta/error dari setiap data training, selanjutnya dilakukan pembaharuan bobot dengan pertimbangan delta tersebut pada setiap data training secara langsung. 33 Gradient Descent (Batch): Example 3 34 Incremental Gradient Descent: Example 3 35 Kesimpulan Perceptron Training Rule dijamin berhasil jika Training examples dapat dipisahkan secara linier Learning rate (𝜂) yang cukup kecil Linear unit training rule menggunakan gradient descent Dijamin konvergen ke hipotesis dengan minimum squared error Diberikan learning rate (𝜂) yang cukup kecil Bahkan ketika data pelatihan mengandung noise Bahkan ketika data pelatihan tidak dapat dipisahkan oleh H 36 TERIMA KASIH Ada pertanyaan ??? Next Week → Multi Layer Perceptron (ANN) 37