Jaringan Syaraf Tiruan Back-Propagation

Jaringan Syaraf Tiruan Back-Propagation

Jaringan Syaraf Tiruan Back-Propagation merupakan salah satu model jaringan yang populer pada jaringan syaraf tiruan. Model jaringan ini banyak digunakan untuk diaplikasikan pada penyelesaian suatu masalah berkaitan dengan identifikasi, prediksi, pengenalan pola dan sebagainya. Pada latihan yang berulang–ulang, algoritma ini akan menghasilkan unjuk kerja yang lebih baik. Hal ini berarti bahwa “bobot interkoneksi” JST semakin mendekati bobot yang seharusnya.(Penelitian Jaringan Syaraf Tiruan,1993). Kelebihan lain yang dimiliki JST ini adalah kemampuannya untuk belajar (bersifat adaptif) dan kebal terhadap adanya kesalahan (Fault Tolerance) dengan kelebihan tersebut JST dapat mewujudkan sistem yang tahan akan kerusakan (robust) dan konsisten bekerja dengan baik.

Metode Backpropagation ini pertama kali diperkenalkan oleh Paul Werbos pada tahun1974, kemudian dikemukakan kembali oleh David Parker di tahun 1982 dan kemudian dipopulerkan oleh Rumelhart dan McCelland pada tahun 1986. Pada Algoritma BackPropagationini, arsitektur jaringan menggunakan jaringan banyak lapis. Secara garis besar proses pelatihan pada jaringan saraf tiruan dikenal beberapa tipe pelatihan, yaitu Supervised Training, Unsupervised Training, Fixed-Weight Nets.

Metode pelatihan BackPropagation atau dikenal dengan Generalize Delta Rule (GDR) ini merupakan supervised training dimana untuk tiap pola input terdapat pasangan target output untuk masing-masing pola input. Sebenarnya adalah metode gradient descent untuk meminimasi total square error pada keluaran hasil perhitungan jaringan. Ide dasarnya dapat dideskripsikan dengan pola hubungan yang sederhana yaitu : jika output memberikan hasil yang tidak sesuai dengan target yang tidak diinginkan, maka pembobot akan dikoreksi agarerrornya dapat diperkecil dan selanjutnya respon jaringan diharapkan akan lebih mendekati harga yang sesuai. Pada umumnya tujuan jaringan syaraf tiruan melakukan proses pelatihan adalah untuk mendapatkan balancing antara kemampuan jaringan untuk menanggapi secara benar pola-pola input pada saat pelatihan (dapat dikatakan kemampuan mengingat) dan kemampuan untuk memberikan penilaian yang layak dari suatu pola masukkan lain yang serupa. Sehingga dari proses pelatihan tersebut akan dibentuk suatu harga pembobot yang akan digunakan sebagai faktor penggali dari pola masukkan yang lain.

Pada metode ini, terdapat tiga tahapan dalam proses pelatihan, yaitu: proses umpan maju dari pola input pelatihan, perhitungan dan propagasi balik dari error yang terjadi dan penyesuaian nilai bobot.

Pada tahap pelatihan ini merupakan langkah bagaimana suatu jaringan syaraf itu berlatih, yaitu: proses umpan maju dari pola input pelatihan, perhitungan, dan propagasi balik dari error yang terjadi dari penyesuaian nilai pembobot.

Pada tahap pelatihan ini merupakan langkah bagaimana suatu jaringan syaraf itu berlatih, yaitu dengan cara melakukan perubahan bobot sambungan, baik bobot sambungan antar input layer dan hidden layer maupun antara hidden layer dan output layer, bila terdapat lebih dari satu hidden layer maka juga terdapat pembobot antar hidden layer itu sendiri. Sedangkan penyelesaian masalah baru akan dilakukan jika proses pelatihan tersebut selesai, fase tersebut adalah proses pemakaian/testing tentunya dengan menggunakan pembobot yang telah dihasilkan dari proses pelatihan yang telah dilakukan.

A. Fase pelatihan umpan mundur (backpropagation)

Jaringan BackPropagation terdiri atas beberapa layer yang masing-masing unit pada satu layer terhubung penuh dengan masing-masing unit pada lapisan diatasnya atau dibawahnya, kecuali pada bias hanya terkoneksi penuh dengan unit layer diatasnya yang ditunjukkan pada gambar 7.

Pada gambar 7 tersebut menunjukkan jaringan yang memiliki satu hidden layer dengan input layer X, hidden layer Z dan output layer Y, serta pemberian nilai bias, yaitu suatu masukkan dengan nilai tetap sama yaitu 1.

Gambar 5. Jaringan Syaraf Tiruan dengan satu hidden layer

Algoritma belajar BackPropagation terdiri dari dua proses, feed foward dan back propagation dari errornya. Selama feed foward masing-masing unit masukkan menerima (X) atau sinyal masukkan dari luar, kemudian sinyal tersebut disebarkan masing-masing unit pada hidden layer (Z), masing-masing hidden unit menghitung sesuai dengan fungsi aktifasinya. Dan kemudian mengirim sinyal itu kemasing-masing unit pada output layer akan menghitung sesuai dengan fungsi aktifasinya juga, yang akan menghasilkan sinyal keluaran sebagai respon jaringan dengan adanya pemberian pola input tersebut.

Pada propagasi baliknya, masing-masing output unit dibandingkan dengan hasil perhitungan aktivasi Y dengan nilai target t untuk mendapatkan error, berdasarkan error inilah akan dihitung nilai δk, selanjutnya harga error pada output unit akan disebarkan mundur ke masing-masing uni pada hidden layer. Selanjutnya error tersebut digunakan untuk memperbaiki faktor pembobot antara unit output dengan unit hidden demikian selanjutnya dicari error dari keluaran hidden untuk memperbaiki faktor pembobot antara unit input. Untuk jelasnya dapat dijelaskan sebagai berikut :

Langkah 1 : Pemberian inisialisasi faktor penimbang (diberi nilai kecil secara random)

Langkah 2 : Ulangi step 2 hingga 9 hingga kondisi stop terpenuhi

Langkah 3 : Untuk masing-masing pasangan pelatihan lakukan langkah 3 hingga 8

Feedforward

Langkah 3 : Masing-masing unit input (Xi, i =1,…n) menerima sinal input X_i dan sinyal tersebut disebarkan ke unit bagian atas lapisan tersembunyi (hidden units)

Langkah 4 : Masing – masing hidden menjumlahkan fakor penimbang :

(3)

Dan menghitung sesuai dengan fungsi aktivasi :

(4)

karena yang digunakan fungsi sigmoid maka :

(5)

Kemudian mengirim sinyal tersebut ke semua unit di atasnya (output unit).

Langkah 5 : Masing-masing unit output (Y_k, k=1,2,3…..m) dijumlahkan faktor penimbang

(6)

Menghitung sesuai dengan fungsi aktivasi

(7)

Back Propagation dari errornya

Langkah 6 : Masing-masing unit output (Y_k, k=1,…….,m) menerima pola target sesuai dengan pola masukan saat pelatihan dan menghitung errornya

(8)

karena f’(y _in_k) = y_k dengan menggunakan fungsi sigmoid, maka :

(9)

Menghitung pembetulan faktor penimbang (kemudian memperbaiki W_jk ).

(10)

Menghitung pembetulan koreksi :

(11)

Dan mengirim nilai δ_k ke unit layer dibawahnya.

Langkah 7 : masing-masing unit hidden (Z_j , j=1……,p) menjumlah delta inputnya (dari unit layer di atasnya).

(12)

Selanjutnya dikalikan dengan turunan dari fungsi akifasinya untuk menghitung error.

(13)

Menghitung pembetulan penimbang (digunakan untuk memeperbaiki V_ij .

(14)

Kemudian menghitung pembetulan bias (untuk memperbaiki V_oj)

(15)

Memperbaiki penimbang dan bias

Langkah 8 : Masing –masing output unit (Y_k , k=1,…,m) diperbaiki bias dan penimbangnya (j = 0,…,n)

(16)

Langkah 9 : Uji kondisi pemberhentian. 

Materi kuliah Analisis dan Perancangan Algoritma : Pencarian Binnary Search Pada Array Yang Sudah Terurut

Pencarian Biner (Binary Search) pada array yang sudah terurut

Pencarian Biner (Binary Search) dilakukan untuk :

♪   memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.

♪   Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).

♪   Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

ALGORITMA  

Kamus

      Const N : integer = 8  { misalkan jumlah elemen array maksimum = 8 }

      Type A = array [ 1 ..... N ] of integer

      Cari, BatasAtas, BatasBawah, Tengah : Integer

      Ketemu : boolean

ALGORITMA

         Input (cari) { meminta nilai data yang akan dicari}

         BatasAtas     ¬  1 { indeks array dimulai dari 1 }

         BatasBawah     ¬   N    

         Ketemu   ¬  False

         While (BatasAtas < BatasBawah) and (not ketemu) do

               Tengah ¬   (BatasAtas  + BatasBawah) div 2

               If A [Tengah] = cari then

                  Ketemu ¬ true

                           Else

                                 If ( A [Tengah]  < cari ) then { cari di bagian kanan }

                                       BatasAtas ¬ Tengah + 1

                                 Else

                                       BatasBawah ¬ Tengah – 1 { cari di bagian kiri }

                                 Endif

                           Endif

         EndWhile

         If (ketemu) then

                     Output ( ‘Data berada di index nomor’, Tengah )

         Else     Output ( ‘Data tidak ditemukan’ )

         Endif

Contoh Nilai-Nilai data yang sudah terurut :

A	2	5	8	12	15	25	37	57
	1	2	3	3	5	6	7	8

Kasus 1  : cari = 12

Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4

                           A [Tengah] = A [4] = 12, berarti loop pertama data langsung ditemukan

Kasus 2  : cari = 15

Loop pertama :Tengah = (BatasAtas + BatasBawah) div 2 = (1 +  8) div 2 = 4

                          A [Tengah] = A [4] = 12 < cari = 15, berarti BatasAtas = Tengah + 1 = 4 + 1 = 5

Loop kedua :     Tengah = (BatasAtas + BatasBawah) div 2 = (5 +  8) div 2 = 6

                           A [Tengah] = A [6] = 25 > cari = 15, berarti BatasBawah = Tengah - 1 = 6 - 1 = 5

Loop ketiga :     Tengah = (BatasAtas + BatasBawah) div 2 = (5 +  5) div 2 = 5

                           A [Tengah] = A [5] = 15, berarti  setelah loop ketiga, data ditemukan

Kasus 3  : cari = 10

Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 +  8) div 2 = 4

                           A [Tengah] = A [4] = 12 > cari = 10, berarti BatasBawah = Tengah - 1 = 4 - 1 = 3

Loop kedua :     Tengah = (BatasAtas + BatasBawah) div 2 = (1 +  3) div 2 = 2

                           A [Tengah] = A [2] = 5 < cari = 10, berarti BatasAtas = Tengah + 1 = 2 + 1 = 3

Loop ketiga :     Tengah = (BatasAtas + BatasBawah) div 2 = (3 +  3) div 2 = 3

                           A [Tengah] = A [3] = 8, berarti  setelah loop ketiga, data tidak ditemukan

Untuk jumlah data sebanyak n, maka proses pembandingan maksimal sebanyak ( log n ) kali. Untuk contoh di atas, jumlah data 8, maka proses pembandingan maksimal sebanyak 3 kali.

ALGORITMA SORTING

Algoritma Sorting

Dalam matematika dan komputasi, algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.

Desain dan analisis algoritma adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama.

Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal, algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.

Sedangkan sorting adalah sebuah proses merangkai benda dalam urutan tertentu dan/atau dalam himpunan yang berbeda, dan oleh karena itu dia memiliki dua arti umum yang berbeda:

1. pengurutan: merangkai benda yang sejenis, sekelas, dll, dalam urutan yang teratur.
2. kategorisasi: pengelompokan dan pemberian label kepada benda dengan sifat yang serupa.

algoritma sorting terdiri dari beberapa algoritma seperti Bubble sort, Quick sort, Selection Sort, Insertion Sort, dan Merge Sort yang dimana setiap jenis sorting ini memiliki perbedaan satu sama lainnya. berikut ini merupakan pembahasan umum mengenai jenis-jenis atau algoritma sorting yang telah dijelaskan diatas :

Bubble Sort

Bubble Sort merupakan cara pengurutan yangsederhana. Konsep dari ide dasarnya adalah seperti“gelembung air” untuk elemen struktur data yangsemestinya berada pada posisi awal. Cara kerjanyaadalah dengan berulang-ulang melakukan traversal (proses looping) terhadap elemen-elemen struktur datayang belum diurutkan. Di dalam traversal tersebut,nilai dari dua elemen struktur data dibandingkan. Jikaternyata urutannya tidak sesuai dengan “pesanan”,maka dilakukan pertukaran (swap). Algoritma sortingini disebut juga dengan comparison sort dikarenakanhanya mengandalkan perbandingan nilai elemen untukmengoperasikan elemennya.

Algoritma Bubble Sort

Algoritma bubble sort dapat diringkas sebagaiberikut, jika N adalah panjang elemen struktur data, dengan elemen-elemennya adalah T1, T2, T3, …, TN-1,TN, maka:

1. Lakukan traversal untuk membandingkan dua elemen berdekatan. Traversal ini dilakukan dari belakang.
2. Jika elemen pada TN-1 > TN , maka lakukan pertukaran (swap). Jika tidak, lanjutkan ke proses traversal berikutnya sampai bertemu dengan bagian struktur data yang telah diurutkan.
3. Ulangi langkah di atas untuk struktur data yang tersisa.

Selection Sort

Algoritma sorting sederhana yang lain adalahSelection Sort. Ide dasarnya adalah melakukan beberapa kali pass untuk melakukan penyeleksianelemen struktur data. Untuk sorting ascending(menaik), elemen yang paling kecil di antara elemenelemenyang belum urut, disimpan indeksnya,kemudian dilakukan pertukaran nilai elemen denganindeks yang disimpan tersebut dengan elemen yangpaling depan yang belum urut. Sebaliknya, untuksorting descending (menurun), elemen yang paling. besar yang disimpan indeksnya kemudian ditukar.

Algoritma Selection Sort

Algoritma selection sort dapat dirangkum sebagaiberikut:

1. Temukan nilai yang paling minimum (atau sesuaikeinginan) di dalam struktur data. Jika ascending, maka yang harus ditemukan adalah nilai yang paling minimum. Jika descending, maka temukan nilai yang paling maksimum.
2. Tukar nilai tersebut dengan nilai pada posisipertama di bagian struktur data yang belum diurutkan.
3. Ulangi langkah di atas untuk bagian struktur datayang tersisa.

Insertion Sort

Cara kerja insertion sort sebagaimana namanya.Pertama-tama, dilakukan iterasi, dimana di setiap iterasi insertion sort memindahkan nilai elemen,kemudian menyisipkannya berulang-ulang sampai ketempat yang tepat. Begitu seterusnya dilakukan.  Dariproses iterasi, seperti biasa, terbentuklah bagian yang telah di-sorting dan bagian yang belum di-sorting.

Algoritma Insertion Sort

Algoritma Insertion Sort dapat dirangkum sebagai berikut:

1. Simpan nilai Ti kedalam variabel sementara, dengan i = 1.
2. Bandingkan nilainya dengan elemen sebelumnya.
3. Jika elemen sebelumnya (Ti-1) lebih besar nilainya daripada Ti, maka tindih nilai Ti dengan nilai Ti-1 tersebut. Decrement i (kurangi nilainya dengan 1).
4. Lakukan terus poin ke-tiga, sampai Ti-1 ≤ Ti.
5. Jika Ti-1 ≤ Ti terpenuhi, tindih nilai di Ti dengan variabel sementara yang disimpan sebelumnya.
6. Ulangi langkah dari poin 1 di atas dengan i di-increment (ditambah satu).

Merge Sort

Algoritma Merge Sort ditemukan oleh John vonNeumann di tahun 1945. Merge Sort termasuk paradigma algoritma divide and conquer (kurang lebih berarti: bagi dan atasi). Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelum kemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide utama sebagai berikut,

1. Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.
2. Untuk membentuk sebuah list terurut dari duabuah list terurut membutuhkan langkah yangl ebih sedikit daripada membentuk sebuah list terurut dari dua buah list tak terurut. Contoh:hanya diperlukan satu kali traversal untuk masing-masing list jika keduanya sudahterurut.

Algoritma Merge Sort

Algoritma Merge Sort sederhananya, dapat ditulis berikut:

1. Bagi list yang tak terurut menjadi dua sama panjang atau salah satunya lebih panjang satu elemen.
2. Bagi masing-masing dari 2 sub-list secara rekursif sampai didapatkan list dengan ukuran 1.
3. Gabung 2 sublist kembali menjadi satu list terurut.

Quick Sort

Quick Sort adalah algoritma sorting yang terkenal yang dirancang oleh C.A.R. Hoare pada tahun 1960 ketika bekerja untuk perusahaan manufaktur komputer saintifik kecil, Elliott Brothers. Algoritma ini rekursif, dan termasuk paradigma algoritma divide and conquer.

Algoritma Quick Sort

Algoritma ini terdiri dari 4 langkah utama:

1. Jika struktur data terdiri dari 1 atau 0 elemen yang harus diurutkan, kembalikan struktur data itu apa adanya.
2. Ambil sebuah elemen yang akan digunakansebagai pivot point (poin poros).  (Biasanya elemen yang paling kiri.)
3. Bagi struktur data menjadi dua bagian – satu dengan elemen-elemen yang lebih besar daripada pivot point, dan yang lainnya dengan elemen-elemen yang lebih kecil dari pada pivot point.
4. Ulangi algoritma secara rekursif terhadap kedua paruh struktur data.

KESIMPULAN

Algoritma yang mudah dalam hal implementasi adalah Bubble Sort, Selection Sort, dan Insertion Sort. Ketiganya memiliki kompleksitas O(n2). Di antara algoritma ini, yang paling effisien adalah Insertion Sort.  Algoritma yang lebih mangkus adalah MergeSort dan Quick Sort dengan kompleksitasnya adalah O(n log n). Adapun yang paling mangkus dari lima algoritma ini adalah Quick Sort.