BAB 2 LANDASAN TEORI
2.1
Machine Learning Sejak komputer ditemukan, para peneliti telah berpikir adakah kemungkinan agar
komputer dapat belajar. Jika kita mengerti bagaimana cara memprogram komputer agar mereka dapat belajar, dan berkembang dari pengalaman secara otomatis, hasilnya akan luar biasa dramatis. Bayangkan komputer belajar dari data-data medical untuk menemukan cara baru menangani suatu penyakit, belajar dari pengalaman untuk mengoptimumkan energi yang dibutuhkan untuk melakukan pekerjaan rumah tangga, dan lain-lain. Sejak tahun 1980-an, bidang ilmu soft computing mulai muncul dan berkembang berdampingan dengan bidang ilmu konvensional hard computing. Adapun yang membedakan antara kedua ilmu ini adalah setelah diprogram, hard computing akan memberikan hasil yang sama untuk input yang sama, sementara soft computing akan belajar dari input-input yang diberikan sebelumnya untuk memberikan hasil yang lebih akurat di masa depan. Dalam cabang machine learning, terdapat tiga bidang ilmu besar yang dikembangkan terus menerus untuk mencapai tujuan di atas: •
Neural Network (NN)
•
Support Vector Machines (SVM)
•
Fuzzy Logic System Pada penulisan ini tidak akan dibahas lebih lanjut mengenai neural network maupun fuzzy
logic system. Pada pembahasan selanjutnya, akan difokuskan pada support vector machines-viola jones. 6
7 2.2
Supervised Learning Supervised learning adalah teknik pembelajaran mesin dengan membuat suatu fungsi dari
data latihan. Data latihan terdiri dari pasangan nilai input (biasa dalam bentuk vektor), dan output yang diharapkan untuk input yang bersangkutan. Tugas dari mesin supervised learning adalah memprediksi nilai fungsi untuk semua nilai input yang mungkin, setelah mengalami sejumlah data latihan. Untuk mencapai tujuan ini, mesin harus dapat melakukan proses generalisasi dari data latihan yang diberikan, untuk memprediksikan nilai output dari input yang belum pernah diberikan sebelumnya dengan cara yang masuk akal. 2.3
Linear Learning Machines Dalam proses supervised learning, mesin diberikan kumpulan contoh data (disebut juga
input), dan label yang terasosiasi (disebut juga output), dan contoh input dalam bentuk vektor sehingga domain input merupakan subset
. Setelah contoh data dan label nya tersedia,
sejumlah metode dapat dipilih untuk melakukan proses generalisasi pada masalah tersebut. Salah satu metode yang paling dimengerti dan paling sederhana adalah menggunakan metode fungsi linier. Linear learning biasa digunakan untuk klasifikasi biner, yaitu kasus di mana domain outputnya hanya terdiri dari 2 kemungkinan saja (kelas positif dan kelas negatif). Klasifikasi ini biasanya dilakukan menggunakan fungsi input x, akan diberikan label kelas +, apabila . Karena
dengan aturan untuk sembarang , dan sebaliknya kelas –, apabila
adalah fungsi linear, maka dapat lebih lanjut ditulis sebagai:
8
= ( w1 x1 ) + ( w2 x 2 ) + ( w3 x3 ) + ... + ( wn x n ) + b Di sini,
merupakan vektor di ruang dimensi n, sehingga wi (w1 sampai wn) merupakan
komponen-komponen nilai penyusun vektor w di ruang dimensi n, dan nilai dari vektor w di sinilah yang akan menjadi classifier bagi support vector machines.
x
x x
o
x
o o
x
o o
Gambar 2.1 Sebuah vektor memisahkan bidang menjadi 2 daerah di mana
dan
merupakan parameter fungsi yang akan ditentukan dari proses pembelajaran
dari contoh-contoh data yang diberikan ke linear machine yang bersangkutan, dan hasilnya akan diberikan oleh
.
Para peneliti statistik dan neural network sangat sering menggunakan sistem pengklasifikasi yang sederhana seperti ini, yang sering dikenal juga dengan nama linear discriminants dan perceptrons. Teori linear discriminants dikembangkan oleh Fisher pada tahun 1936, sementara peneliti neural network mulai mengkaji perceptrons pada awal 1960.
2.3.1
Rosenblatt’s Perceptron
9 Algoritma iteratif pertama untuk klasifikasi linier dikembangkan oleh Frank Rosenblatt pada tahun 1956 yang mengundang banyak perhatian pada saat pertama kali dikenalkan. Algoritma ini dimulai dengan vektor awal
, dan mengubahnya setiap kali terjadi
kesalahan klasifikasi. Algoritma ini (yang dideskripsikan pada tabel 2.1) mengubah nilai vektor dan bias
secara langsung, yang disebut sebagai bentuk primal. Algoritma ini dijamin akan
konvergen apabila memang terdapat hyperplane yang dapat mengklasifikasi contoh data yang diberikan dengan benar (contoh data dapat dipisahkan secara linier).
Tabel 2.1 Algoritma perceptron (bentuk primal) Diberikan contoh data input
, label
, jumlah contoh data , dan kecepatan belajar η
Repeat for i = 1 to if
then
end if end for until no mistakes made within the for loop ) di mana adalah jumlah kesalahan yang terjadi. return , (
2.3.2
Dual dari Linear Machines Berdasarkan algoritma pada tabel 2.1, baris
berulang-ulang karena efek perulangan, sehingga hasil akhir dari vektor dengan
akan dijalankan (yang dinotasikan
) merupakan penjumlahan dari semua pengubahan yang dilakukan pada vektor
dan hasil akhir vektor
dapat dituliskan sebagai:
,
10
di mana
merupakan jumlah kesalahan saat mengklasifikasikan
yang merupakan dual dari
, dan fungsi penentu
dapat dituliskan sebagai berikut:
Tabel 2.2 Algoritma perceptron (bentuk dual) Diberikan contoh data input
, label
, jumlah contoh data
Repeat for i = 1 to if
then
end if end for until no mistakes made within the for loop ) untuk menentukan fungsi return (
2.4
Trik Kernel Batas kemampuan komputasi fungsi linier dibahas pada tahun 1960an oleh Minsky dan
Papert. Secara umum, pada kasus dunia nyata, pengklasifikasian domain permasalahan
11 memerlukan ekspresi yang lebih kompleks dibanding fungsi linier (misalnya fungsi polynomial, eksponensial, dan atau atau fungsi periodik). Trik kernel menawarkan solusi dengan memproyeksikan data ke dalam ruang dimensi yang lebih tinggi (disebut juga dengan feature space) untuk meningkatkan kemampuan komputasi fungsi linier. Yang dimaksud dengan dimensi di sini merupakan ruang dimensi vektor w berada, yang akan mempengaruhi besar nilai n atau N pada rumus. Adapun pemetaan ke ruang dimensi yang lebih tinggi dilakukan untuk memetakan input ke ruang dimensi yang baru, di mana diharapkan bahwa pada ruang dimensi yang baru, domain input dapat dipisahkan oleh suatu vektor sederhana, yang tidak dapat dilakukan sebelumnya pada ruang dimensi awal. Adapun salah satu pemetaan ulang data, dapat dicapai dengan memetakan fungsi penentu berubah menjadi:
, sehingga
12
X
x o
F
Φ Φ(x)
x x o
Φ(x) Φ(x)
Φ(o)
o x
Φ(x)
Φ(o) Φ(o)
Gambar 2.2 Ilustrasi fungsi kernel dalam menyederhanakan klasifikasi 2.5
Support Vector Machines Tujuan dari support vector machines adalah menemukan suatu cara yang efisien dalam
mengkalkulasi vektor pemisah dalam ruang dimensi tinggi. Dalam support vector machines sendiri memiliki beberapa teori generalisasi, di mana teori y ang berbeda akan berakhir dengan hasil yang berbeda pula. Misalnya terdapat teori yang mengutamakan margin maksimal, distribusi margin, jumlah vektor, dan lain sebagainya.
2.5.1
Sejarah Support Vector Machines Walau saat pertama kali diperkenalkan ke dunia sejak akhir tahun 1970-an (Vapnik,
1979), support vector machines tidak mendapat banyak perhatian oleh para peneliti. Hanya setelah Vladimir Vapnik kembali menerbitkan bukunya pada tahun 1990-an (Vapnik, 1995; Vapnik, 1998) dan dapat menunjukkan aplikasi nyata, support vector machines kemudian berkembang pesat. Salah satu yang menjadi penyebab adalah tersimpan teori matematika yang
13 mendalam di balik support vector machines di banding kedua kerabatnya di bidang soft computing: neural network dan fuzzy logic.
2.5.2
Maximal Margin Classifier Maximal margin classifier adalah model support vector machines yang paling sederhana,
yang juga merupakan model pertama yang dikenalkan pada dunia. Model ini hanya bekerja untuk data yang dapat dipisahkan secara linier pada feature space, dan oleh karena itu, tidak dapat digunakan pada kebanyakan kasus nyata. Namun bagaimana pun juga, model ini memiliki algoritma yang paling mudah dimengerti, dan juga membentuk dasar teori model-model lain yang lebih kompleks. Strategi maximal margin classifier adalah dengan mencari vektor yang akan memisahkan feature space dengan margin yang paling besar. Hal ini dilakukan dengan mengubah masalah model ini menjadi convex optimization problem: mencari fungsi kuadratik minimal dengan kondisi dari fungsi pertidaksamaan linier.
2.5.3
Soft Margin Optimisation Maximal margin classifier merupakan konsep yang penting, sebagai titik awal
perkembangan teori support vector machines yang lebih lanjut, namun tidak dapat digunakan pada kebanyakan kasus nyata. Hal ini dikarenakan maximal margin classifier berangkat dari hipotesis tanpa kesalahan pembelajaran. Mengingat bahwa pada banyak kasus nyata, feature space tidak dapat dipisahkan oleh vektor dengan sempurna, soft margin optimization memasukkan sebuah peubah slack dalam perhitungan margin.
14 2.6
Meta-Algoritma Meta-algoritma adalah algoritma yang menggunakan algoritma lain sebagai perwakilan,
dan juga merupakan algoritma yang memiliki sub-algoritma sebagai peubah dan parameter yang dapat diganti. Contoh-contoh yang termasuk meta-algoritma adalah boosting, simulated annealing, bootstrap aggregating, AdaBoost, dan random-restart hill climbing.
2.7
Algoritma Boosting Boosting merupakan meta-algoritma dalam machine learning untuk melakukan
supervised learning. Teori boosting dikenalkan berdasarkan pertanyaan yang diajukan Kearns (1988): Dapatkah sekumpulan weak learner menciptakan satu kesatuan strong learner? Weak learner adalah classifier yang hanya memiliki sedikit korelasi dengan klasifikasi yang sebenarnya, sementara strong learner adalah classifier yang memiliki korelasi kuat dengan klasifikasi yang sebenarnya. Kebanyakan algoritma boosting mengikuti sebuah rancangan. Secara umum boosting terjadi dalam iterasi, secara incremental menambahkan weak learner ke dalam satu strong learner. Pada setiap iterasi, satu weak learner belajar dari suatu data latihan. Kemudian, weak learner itu ditambahkan ke dalam strong learner. Setelah weak learner ditambahkan, data-data kemudian diubah masing-masing bobotnya. Data-data yang mengalami kesalahan klasifikasi akan mengalami penambahan bobot, dan data-data yang terklasifikasi dengan benar akan mengalami pengurangan bobot. Oleh karena itu, weak learner pada iterasi selanjutnya akan lebih terfokus pada data-data yang mengalami kesalahan klasifikasi oleh weak learner yang sebelumnya.
15 Dari banyak variasi algoritma boosting, AdaBoost merupakan yang paling terkenal dan dalam sejarah perkembangannya, merupakan algoritma pertama yang dapat beradaptasi dengan weak learner. Namun, terdapat beberapa contoh algoritma boosting lain seperti LPBoost, TotalBoost, BrownBoost, MadaBoost, LogitBoost, dan lain-lain. Kebanyakan algoritma boosting dapat dimasukkan ke dalam framework AnyBoost.
2.7.1
AdaBoost AdaBoost, singkatan dari Adaptive Boost, diformulasikan oleh Yoav Freund dan Robert
Schapire. AdaBoost merupakan meta-algoritma, yang bisa diterapkan ke dalam learning algorithm lain untuk meningkatkan performa.
2.8
Perancangan Software Di era informasi, jutaan software telah beredar di dunia, dan jutaan lainnya sedang dalam
pengembangan. Masing-masing pengembang, memiliki metode masing-masing dalam membuat softwarenya, dan masing-masing metode memiliki dampak secara langsung maupun tidak langsung terhadap proses pengembangan software itu sendiri. Proses tersebut dinamakan rekayasa piranti lunak atau software engineering. Beberapa definisi yang diberikan Pressman (2001) mengenai rekayasa piranti lunak tercantum di bawah: •
Penggunaan dan pemanfaatan prinsip-prinsip teknik, dalam upaya untuk memperoleh software yang ekonomis namun dapat diandalkan dan bekerja secara efisien pada mesin nyata.
•
Pendekatan
secara
sistematis,
disiplin,
dan
bertanggung
pengembangan, operasi, dan pemeliharaan dari sebuah software.
jawab
atas
proses
16 Langkah-langkah yang perlu dilakukan dalam mengembangkan software, beserta dengan prinsipprinsip tekniknya tertuang dalam topik system development life cycle.
2.8.1
System Development Life Cycle SDLC, atau System Development Life Cycle, adalah sekumpulan langkah-langkah,
prosedur, dan dokumen secara spesifik yang membimbing suatu proyek melalui pengembangan secara teknis. Fase-fase yang biasa terdapat dalam SDLC antara lain: initiation phase, planning phase, functional design phase, system design phase, development phase, integration and testing phase, installation and acceptance phase, dan maintenance phase. Dalam penerapannya, banyak model telah dibuat untuk mendukung SDLC, yaitu: waterfall, fountain, spiral, build and fix, rapid prototyping, incremental, synchronize and stabilize. Metode yang paling awal dikembangkan, dan yang paling terkenal, adalah waterfall: sekumpulan urutan tahap-tahap pengerjaan, di mana output dari satu tahap, menjadi input bagi tahap berikutnya. Tahap-tahap ini dibagi menjadi berikut: 1. Analisis Analisis problem domain, teknologi yang akan diterapkan, logika bisnis yang akan diimplementasi, dan lain-lain. 2. Requirements specification Pada tahap ini, disiapkan dokumen-dokumen mendetil mengenai kebutuhan software yang akan dibuat, seperti gambaran umum mengenai software, dan modul-modul yang akan dibuat.
17 3. Design Pada tahap ini, disediakan dokumen-dokumen seperti functional specification, yang berisikan analisis dari masing-masing modul dari tahap pertama, apa yang harus dibuat dalam masing-masing modul, rancangan layar, cara mengoperasikannya, serta output yang diharapkan dari masing-masing modul. Pada tahap ini juga, dibuat arsitektur dari software yang akan dibuat. Masalah-masalah mengenai arsitektur meliputi teknologi yang digunakan dalam membuat software (bahasa, komponen, dll), class diagram, ERD (apabila software melibatkan database), dan lain-lain. 4. Implementasi Pada tahap ini, program ditulis dalam bahasa pemrograman yang telah ditentukan, dan mengikuti rancangan yang telah disediakan pada tahap design. Penulisan program diharapkan menyertakan dokumentasi program (bila diperlukan). 5. Testing dan Integration Pada tahap ini, sistem yang telah diintegrasikan, diuji coba fungsionalitasnya, dan diperbaiki bila ada kesalahan. Dalam SDLC, dikenal dua jenis testing, yaitu black box testing dan white box testing. Black box testing mengamati karakteristik input dan output dari setiap proses yang ada. White box testing mengamati program internal, komponenkomponen yang digunakan, dan mencoba mendeteksi adanya kemungkinan cacat dari segi keamanan, atau yang lainnya. Kemudian potongan-potongan program dari tahap sebelumnya, digabungkan dan diintegrasikan dengan sistem lain (bila ada). Hasil akhir dari tahap ini diharapkan sistem utuh yang sudah siap dijalankan.
18 6. Operation dan Maintainance Setelah software selesai dibuat, software akan dipantau selama jangka waktu tertentu, dievaluasi secara berkala, dan diperbaiki bila ditemukan kesalahan.
Gambar 2.3 Waterfall Model (Sumber: [Anonim 1]) Dalam mengikuti model waterfall, pengembang software memulai SDLC dari tahap satu ke tahap yang lain murni secara berurutan. Oleh karena itu model waterfall menjaga agar proses pengembangan software bergerak ke tahap berikutnya hanya apabila tahap-tahap sebelumnya
19 telah diselesaikan secara sempurna. Tahapan-tahapan itu pun harus diselesaikan secara berurutan, tidak boleh melompati urutan tahapan yang ada. 2.9
Simulasi Komputer Yang dimaksud dengan simulasi komputer, model komputer, atau model komputasi,
adalah program komputer yang mencoba meniru proses dari suatu model abstrak dari suatu sistem. Simulasi komputer telah menjadi bagian penting dari pemodelan matematika dari banyak sistem alam di fisika, kimia, dan biologi, sistem buatan di ekonomi, psikologi, dan ilmu sosial. Biasanya, sistem pemodelan umumnya melalui model matematika, yang mencoba untuk mencari solusi analitik dari suatu masalah, yang memungkinkan peneliti untuk memprediksi cara kerja suatu sistem berdasarkan parameter-parameter dan suatu kondisi awal. Simulasi komputer berkembang terus dan menjadi sangat berguna di bidang ilmu pengetahuan, teknologi, dan hiburan. Simulasi komputer berkembang seiiring dengan pertumbuhan yang pesat di bidang komputer. Implementasi berskala besar yang pertama berlangsung saat perang dunia II, yang bernama Manhattan Project, yang bertujuan untuk memodelkan proses detonasi nuklir menggunakan algoritma Monte Carlo. Simulasi komputer sering digunakan sebagai pengganti model sistem, di mana tidak terdapat solusi analitik tertutup sederhana. Berdasarkan kriteria, model komputer dapat dikategorikan menjadi: •
Stokastik atau deterministik
•
Steady-state atau dinamis
•
Kontinu atau diskrit
•
Lokal atau terdistribusi
