6

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.

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 dengan aturan untuk sembarang

input x, akan diberikan label kelas +, apabila , dan sebaliknya kelas –, apabila

. Karena adalah fungsi linear, maka dapat lebih lanjut ditulis sebagai:

8

bxwxwxwxw nn +++++= )(...)()()( 332211

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.

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

x x

x x

x

o

o

o o o

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 return , ( ) di mana adalah jumlah kesalahan yang terjadi.

2.3.2 Dual dari Linear Machines

Berdasarkan algoritma pada tabel 2.1, baris akan dijalankan

berulang-ulang karena efek perulangan, sehingga hasil akhir dari vektor (yang dinotasikan

dengan ) merupakan penjumlahan dari semua pengubahan yang dilakukan pada vektor ,

dan hasil akhir vektor dapat dituliskan sebagai:

10

di mana merupakan jumlah kesalahan saat mengklasifikasikan , dan fungsi penentu

yang merupakan dual dari 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 return ( ) untuk menentukan fungsi

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 , sehingga

fungsi penentu berubah menjadi:

12

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

x

x

x

x

o

o o

Φ(x) Φ(x)

Φ(x)

Φ(x)

Φ(o)

Φ(o) Φ(o)

Φ X F

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 jawab atas proses

pengembangan, operasi, dan pemeliharaan dari sebuah software.

16

Langkah-langkah yang perlu dilakukan dalam mengembangkan software, beserta dengan prinsip-

prinsip 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, komponen-

komponen 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