s_mat_0800266_chapter2

7/31/2019 s_mat_0800266_chapter2

1/29

Pujia Siti Balkist, 2012Aplikasi Algoritma bBaum-Welch ....Universitas Pendidikan Indonesia | repository.upi.edu

BAB II

LANDASAN TEORI

Pada bab ini akan dipaparkan teori-teori yang mendukung pembahasan

dalam penelitian DNA menggunakan HMM. Teori-teori tersebut di antaranya

teori peluang, peluang bersyarat, aturan Bayes, peubah acak, rantai Markov,

HMM dan DNA.

2.1 Teori Peluang

Definisi 2.1:

Misalkan S adalah suatu ruang sampel dari suatu eksperimen acak dan

adalah kumpulan semua peristiwa yang bisa dibentuk dari S. Peluang pada S

adalah fungsi P dengan domain A ke [0,1] yang memenuhi sifat-sifat sebagai

berikut:

1. 0, 2. = 1

3. Jika

1 ,

2 ,

,

adalah m buah peristiwa yang saling lepas dalam

,

(artinya =, , , = , 2,, ) maka =1 = ( )=1 ,

(Nar Herrhyanto dan Tuti Gantini, 2009).

7/31/2019 s_mat_0800266_chapter2

2/29

9

Teorema 2.1 :

Misalkan A adalah sebuah peristiwa yang merupakan bagian dari ruang

sampel diskrit (dapat terhitung) S. Bila suatu percobaan dapat menghasilkan

macam hasil yang mungkin dan bila tepat sebanyak menunjukan banyaknya

peristiwa A, maka peluang peristiwa A adalah

=


2.2 Peluang Bersyarat

Peluang bersyarat adalah peluang terjadinya peristiwa B bila diketahui A

terjadi, biasa dinyatakan dengan (Nar Herrhyanto dan Tuti Gantini, 2009). Definisi 2.2:Jika A dan B adalah dua buah peristiwa dalam ruang sampel S, maka

peluang bersyarat dari B bila diketahui A terjadi didefinisikan dengan :

=

(

)

(

)

, (

) > 0


Dari definisi tersebut, bila rumus dikalikan dengan ( ) , maka diperolehteorema perkalian yang penting.

Teorema 2.2:

Bila kejadian A dan B dapat terjadi pada suatu percobaan, maka

7/31/2019 s_mat_0800266_chapter2

3/29

10

= . ( | ) (Nar Herrhyanto dan Tuti Gantini, 2009).

Teorema 2.3 :

Bila dalam suatu percobaan, kejadian 1 , 2 , 3 ,dapat terjadi, maka 1 2 3 = 1 2 1 3 1 2 . (Nar Herrhyanto dan Tuti Gantini, 2009).

2.3 Aturan Bayes

Definisi 2.3:

Peristiwa-peristiwa 1 , 2 ,, dikatakan partisi dari ruang sampel S, jika:

a.

=

, untuk semua

b. =1 =

c. > 0 , untuk semua = 1,2, , (Nar Herrhyanto dan Tuti Gantini, 2009).

Teorema 2.4:

Jika peristiwa 1 , 2 ,

, merupakan partisi dari ruang sampel S, maka

peluang dari peristiwa A yang sembarang dari S adalah:

= . ( | )=1 (Nar Herrhyanto dan Tuti Gantini, 2009).

7/31/2019 s_mat_0800266_chapter2

4/29

11

Teorema 2.5:

Misalkan 1 , 2 ,

, suatu himpunan kejadian yang merupakan suatu

sekatan ruang sampel dengan ( ) > 0 untuk = 1,2, , . Misalkan A suatukejadian sembarang dalam S dengan > 0 . Maka untuk = 1,2, , ,

= ( )( )=1 = ( | )( | )=1 (Nar Herrhyanto dan Tuti Gantini, 2009).

2.4 Peubah Acak

Definisi 2.4:

Misal E adalah sebuah eksperimen dengan ruang sampelnya S. Sebuah

fungsi X yang memetakan setiap anggota dengan sebuah bilangan real ( ) dinamakan peubah acak (Nar Herrhyanto dan Tuti Gantini, 2009).

Definisi 2.5:

Jika suatu ruang sampel mengandung titik yang berhingga banyaknya atau

suatu deretan anggota yang banyaknya sama dengan banyaknya bilangan bulat

(terhitung), maka peubah acak yang didefinisikan pada ruang sampel tersebut

adalah peubah acak diskrit (Nar Herrhyanto, 1993).

Definisi 2.6:

Bila ruang sampel mengandung titik sampel yang tak berhingga

banyaknya dan sama banyaknya dengan banyak titik pada suatu garis (tak

terhitung), maka ruang sampel itu disebut ruang sampel kontinu dan peubah acak

7/31/2019 s_mat_0800266_chapter2

5/29

12

yang didefinisikan pada ruang sampel tersebut disebut peubah acak kontinu (Nar

Herrhyanto, 1993) .

Definisi 2.7:

Fungsi ( ) adalah fungsi densitas peluang atau distribusi peluang suatupeubah acak diskrit bila,berlaku:

1. 0 2.

= 1

3. = = ( ) (Nar Herrhyanto, 1993).

Definisi 2.8:

Distribusi kumulatif ( ) suatu peubah acak diskrit dengan distribusipeluang

( ) dinyatakan oleh: =

=

( )(Nar Herrhyantodan Tuti Gantini, 2009).

2.5 Proses Stokastik

Definisi 2.9:

Didefinisikan set indeks menyatakan 1 , 2 , 1 > 2 atau 1 = 2 .T dinamakan ruang parameter atau ruang indeks

, dimana t merupakan

parameter (Sheldon M. Ross, 1997).

Secara umum (dalam terapannya), t menyatakan waktu.

Definisi 2.10:

Untuk setiap

maka

dinamakan peubah acak pada saat t

(Sheldon M. Ross, 1997).

7/31/2019 s_mat_0800266_chapter2

6/29

13

Definisi 2.11:

Koleksi atau barisan peubah acak

=

( )

dinamakan proses

stokastik (Sheldon M. Ross, 1997).

Definisi 2.12:

Misalkan diketahui ruang parameter T dan barisan peubah acak merupakan suatu proses stokastik, sehingga:

1. Jika T terbilang, maka barisan peubah acak

disebut proses stokastik

dengan ruang parameter diskrit

2. Jika T tak terbilang, maka barisan peubah acak disebut proses stokastik dengan ruang parameter kontinu


Definisi 2.13:

Untuk setiap maka menyatakan peubah acak pada keadaan t,dengan range (himpunan hasil) ( ) atau ( ) yang dinamakan ruang keadaandari suatu proses stokastik.

1. Jika ( ) diskrit dan ( ) diskrit, maka ini dinamakan proses stokastik dengan ruang keadaan diskrit

2. Jika ( ) kontinu dan ( ) kontinu, maka ini dinamakan proses stokastik dengan ruang keadaan kontinu


7/31/2019 s_mat_0800266_chapter2

7/29

14

2.6 Rantai Markov

Rantai Markov adalah sebuah proses Markov dengan ruang parameter

yang diskrit yang berada pada suatu ruang keadaan yang diskrit (Sheldon M.

Ross, 1997) . Analisis rantai Markov merupakan suatu teknik peluang yang

menganalisis pergerakan peluang dari satu keadaan ke keadaan lainnya. Rantai

Markov dikenalkan oleh Andrey Markov, ahli matematika dari Rusia yang lahir

tahun 1856.

Dalam analisis rantai Markov ini, ( = ) menyatakan peluang dariproses pada saat ke berada pada keadaan . Selain itu dianalisis pula pergerakanprobabilitas dari satu keadaan ke keadaan lainnya.

Ada beberapa syarat yang harus dipenuhi agar suatu kasus dapat

diterapkan dalam analisis rantai Markov (O. C. Ibe, 2009), yaitu sebagai berikut:

1. Jumlah probabilitas transisi untuk suatu keadaan awal dari sistem bernilai

1.

2. Probabilitas-probabilitas tersebut berlaku untuk semua keadaan yang

disertakan dalam sistem.

3. Probabilitas transisi konstan sepanjang waktu.

4. Keadaan merupakan keadaan yang independen sepanjang waktu.

Misalkan terdapat n keadaan yang mungkin dalam suatu kasus rantai

Markov yaitu 1 , 2 , , dengan barisan keadaan dalam suatu kasus yaitu1 , 2, 1 , = , sehingga 1 = 1 , 2 = 2 , = . Terdapat sifat dari

rantai Markov yang harus selalu digunakan, yaitu keadaan sekarang tidak

dipengaruhi oleh keadaan pada masa lampau, namun hanya dipengaruhi oleh

7/31/2019 s_mat_0800266_chapter2

8/29

15

keadaaan terdekat sebelumnya (Sheldon M. Ross, 1997), dirumuskan sebagai

berikut:

+1 = = , 1 = 1 ,, 2 = 2 , 1 = 1 = +1 = = =

untuk semua keadaan 1 , 2 ,, 1 , , dan > 0 , dimana nilai yangmemungkinkan dari i adalah suatu himpunan terbatas yang sering disebut sebagai

ruang keadaan. Probabilitas di atas umumnya disebut dengan nama peluang

keadaan transisi yang sering dilambangkan dengan simbol yang memenuhi:

1. 0 1 .2. = 1, = 1,2, =0 , .

(Sheldon M. Ross, 1997)

2.6.1 Matriks Peluang Transisi

Matriks peluang transisi adalah matriks dimana elemen-elemennya

menyatakan peluang suatu keadaan bergerak atau berpindah ke keadaan lainnya

yang berukuran , dimana (menyatakan peluang transisi dari keadaaan

ke keadaan ) merupakan elemen matriks pada baris ke- i dan kolom ke- j (SheldonM. Ross, 1997).

=

11 12

21 22 12 1 2 Contoh 2.1:

Misalkan Viola seorang gadis yang sangat gemar bermain suatu permainan

komputer. Dalam sekali bermain, Viola dapat memainkan permainan komputer

7/31/2019 s_mat_0800266_chapter2

9/29

16

tersebut berkali-kali. Seorang peneliti melakukan serangkaian penelitian dalam

suatu periode permainan Viola. Ternyata suasana hati Viola saat bermain

permainan komputer saat ini dipengaruhi oleh suasana hati Viola saat bermain

permainan komputer tersebut dalam permainan sebelumnya dalam periode waktu

permainan yang sama. Suasana hatinya terdiri dari senang, sedih dan kesal.

Jika dalam permainan sebelumnya suasana hati Viola senang, maka

peluang suasana hati Viola dalam permainan selanjutnya senang, sedih, dan kesal

adalah 0,5, 0,23 dan 0,27. Adapun jika dalam permainan sebelumnya Viola

merasa sedih, maka peluang dalam permainan selanjutnya Viola merasa senang,

sedih dan kesal adalah 0,35, 0,35 dan 0,3. Sedangkan jika dalam permainan

sebelumnya Viola merasa kesal, maka peluang dalam permainan selanjutnya

Viola merasa senang, sedih dan kesal adalah 0,42, 0,35 dan 0,23.

Jika peristiwa muncul suasana hati senang dinyatakan sebagai keadaan 1,

peristiwa muncul suasana hati kesal dinyatakan sebagai keadaan 2 dan peristiwa

muncul suasana hati kesal dinyatakan sebagai keadaan 3, maka permasalahan

tersebut dapat dinyatakan dalam matriks peluang transisi dengan ordo 3x3 sebagai

berikut:

= 0,5 0,23 0,270,35 0,35 0,30,42 0,35 0,23

Analisis permasalahan tersebut juga dapat dinyatakan dalam diagram

keadaan transisi sebagai berikut:

7/31/2019 s_mat_0800266_chapter2

10/29

17

Gambar 2.1 Diagram Transisi Contoh 2.1

Probabilitas Transisi -Langkah

Misalkan menyatakan peluang bahwa jika suatu proses dimulai

pada keadaan -i, maka suatu saat proses akan berpindah ke keadaan -j setelah

melalui tepat langkah. Nilai dapat dihitung dengan persamaan Chapman-

Kolmogorov (Sheldon M. Ross, 1997):

=

,

0 < <

Sehingga dapat dinyatakan sebagai entri pada baris ke- i dan kolom

ke- j pada matriks . Sehingga untuk suatu rantai Markov dengan keadaan ,

adalah matriks:

senang kesal

sedih

0,5 0,27

0,23

0,42

0,23

0,3 50,35

0,3

0,35

7/31/2019 s_mat_0800266_chapter2

11/29

18

=

11 12 13

21 22 23

31 32 33

1

2

3

1 2 3

2.6.2 Klasifikasi keadaan

Keadaan -j dikatakan dapat dicapai dari keadaan -i jika, suatu proses

dimulai pada keadaan -i maka suatu saat proses tersebut akan berada pada

keadaan -j. Hal ini mengakibatkan bahwa > 0 untuk suatu > 0 . Sehingga

dari probabilitas n-langkah bisa diperoleh informasi ketercapaian dari sebarang

keadaan (Sheldon M. Ross, 1997) .

Dua buah keadaan yang saling dapat dicapai satu sama lain dikatakan

terhubung satu sama lain. Konsep keterhubungan membagi keadaan ke dalam

beberapa kelas. Dua buah keadaan yang saling terhubung dikatakan berada dalam

sebuah kelas yang sama. Semua anggota dari suatu kelas saling terhubung satu

sama lain. Jika suatu kelas tidak terhubung dari keadaan lain yang ada di luar

kelas tersebut, maka kelas tersebut dikatakan kelas yang tertutup dari

keterhubungan (Sheldon M. Ross, 1997).

Klasifikasi keadaan ini untuk memudahkan peneliti rantai Markov

memahami keterhubungan dari masing-masing keadaan. Sehingga peneliti lebih

teliti dalam mengaplikasikan rantai Markov pada suatu kasus.

Sebuah rantai Markov yang semua keadaan -nya terhubung atau hanya

terdiri dari satu kelas dinamakan rantai Markov yang irreducible (Sheldon M.

Ross, 1997) . Contoh rantai Markov irreducible ditunjukkan pada Gambar 2.1.

7/31/2019 s_mat_0800266_chapter2

12/29

19

2.7 Hidden Markov Models (HMM)

Dalam rantai Markov dianalisis pergerakan probabilitas keadaan yang

diteliti. Muncul permasalahan baru jika terdapat suatu keadaan dalam penelitian

yang dipengaruhi oleh keadaan lain namun keadaan lain tersebut tidak dapat

diobservasi. Sehingga para ahli mengembangkan teori yang lebih baik dari rantai

Markov untuk menyelesaikan permasalahan tersebut.

Sehingga pada tahun 1970 ahli Matematika yaitu Baum dan Petrie

memperkenalkan suatu teori pengembangan dari rantai Markov yang dipaparkan

oleh Andrei A. Markov pada tahun 1856 yaitu Model Markov Tersembunyi atau

Hidden Markov Model yang disingkat HMM untuk menyelesaikan suatu kasus

dimana suatu keadaan dalam kasus tersebut dipengaruhi oleh keadaan lain yang

tidak terobservasi, selanjutnya keadaan yang tidak terobservasi ini disebut

keadaan tersembunyi.

HMM adalah gabungan dari dua proses stokastik yang salah satu nya tidak

dapat diobservasi secara langsung, namun tetap dapat diobservasi dengan cara

menganalisis peluang dari salah satu proses stokastik yang dapat diobservasi (Nisa

Pandu, 2011).

Jika = 1 , 2 ,adalah sebuah rantai Markov, dan = 1 , 2 , adalah sebuah fungsi dari , dimana dan merupakan proses stokastik, maka adalah sebuah HMM yang dapat diobservasi melalui , atau dapat ditulis

= ( ) untuk suatu fungsi . Parameter menyatakan proses keadaan yang

7/31/2019 s_mat_0800266_chapter2

13/29

20

tersembunyi, sementara parameter menyatakan proses keadaan yang dapat

diobservasi. Untuk ilustrasi HMM dapat dilihat gambar 2.2 berikut:

Gambar 2.2 Ilustrasi HMM

2.7.1 Parameter-parameter dalam HMM

Pada rantai Markov dikenal 3 parameter yaitu banyaknya keadaan serta

himpunan dari keadaan tersebut, barisan keadaan dan matriks transisi yang

menyatakan peluang pergerakan/ perpindahan dari satu keadaan ke keadaan

lainnya. Namun dalam HMM dikenal 5 parameter yaitu sebagai berikut:

1. N menyatakan jumlah keadaan yang tersembunyi (tidak terobservasi,

namun dapat diobservasi melalui keadaan yang terobservasi).

2. M menyatakan jumlah keadaan yang terobservasi.

3. Matriks peluang transisi A , berukuran , dimana elemen-elemen

( ) dari matriks ini menyatakan peluang transisi (pergerakan/

perpindahan) dari keadaan tersembunyi ke- ke keadaan tersembunyi ke- ( 1

, 1

), dimana untuk

dan 1

dipenuhi

=1 = 1 , yaitu sebagai berikut:

7/31/2019 s_mat_0800266_chapter2

14/29

21

=

11 12

21 22

1

2

1 2

4. Matriks peluang emisi B , berukuran , dimana elemen-elemen ( )

dari matriks ini menyatakan peluang keadaan tersembunyi ke- berada

pada keadaan terobservasi ke- (1 , 1 ), dimana untuk dan 1

dipenuhi =1 = 1 , yaitu sebagai berikut:

=

11 12

21 22

1

2

1 2

5. Matriks peluang keadaan awal , berukuran 1 , dimana elemen-

elemen ( ) menyatakan peluang awal dari keadaan tersembunyi ke-

(1

), dimana =1 yaitu sebagai berikut:

=12

Penentuan matriks keadaan awal tidak secara sembarang. Jika peluang

awal untuk setiap keadaan tersembunyi tidak diketahui dan masing-masing

keadaan tersembunyi memiliki kesempatan muncul yang sama, maka peluang

awal dari masing-masing keadaan tersembunyi sama. Namun jika suatu barisan

keadaan tersembunyi sebelumnya pada suatu kasus dapat diketahui maka matriks

peluang keadaan awal dapat ditentukan dengan menghitung jumlah dari suatu

keadaan tersembunyi tertentu yang muncul dalam suatu barisan keadaan

tersembunyi dan membaginya dengan jumlah seluruh barisan keadaan

7/31/2019 s_mat_0800266_chapter2

15/29

22

tersembunyi. Sehingga HMM dinyatakan sebagai Model dengan N keadaan

tersembunyi, M keadaan terobservasi, dan parameter = (

, , ) .

2.7.2 Asumsi-asumsi pada HMM

Ada tiga asumsi pokok yang dibutuhkan dalam HMM (Nisa Pandu, 2011),

yaitu:

1. Asumsi Markov

Asumsi ini menyatakan bahwa keadaan (tersembunyi dan terobservasi)

berikutnya hanya dipengaruhi oleh keadaan (tersembunyi dan terobservasi)

saat ini. Model yang dihasilkan adalah HMM orde pertama. Pada beberapa

kasus di kehidupan nyata, keadaan (tersembunyi dan terobservasi)

selanjutnya mungkin dipengaruhi oleh k keadaan (tersembunyi dan

terobservasi) sebelumnya, yang akan menghasilkan HMM orde ke- k yang

lebih sulit untuk dianalisis dari pada HMM orde pertama.

2. Asumsi stasioneritas

Asumsi ini menyatakan bahwa pada dua buah rentang waktu tertentu yang

panjangnya sama, peluang transisi dari suatu keadaan tersembunyi ke

keadaan tersembunyi lainnya adalah sama. Sehingga untuk sembarang 1

dan 2 berlaku :

1 +1 = 1 = = 2 +1 = 2 = = (2.1)

7/31/2019 s_mat_0800266_chapter2

16/29

23

3. Asumsi independensi/kebebasan

Jika diketahui suatu barisan observasi dengan T menunjukkan panjang

barisan observasi, yaitu = 1 , 2 ,, dan suatu barisan keadaantersembunyi = 1 , 2 ,, . Maka pengamatan saat ini bersifatindependen secara statistik dengan pengamatan sebelumnya, atau dapat

dinyatakan:

, = ( |

, )=1 (2.2)

Contoh 2.2

Viola yang sangat gemar bermain suatu permainan komputer. Dalam satu

periode permainan, Viola dapat memainkan permainan komputer tersebut berkali-

kali. Dalam periode permainan tersebut Viola bisa menang dan kalah. Sehingga

menang dan kalah ini merupakan suatu barisan observasi. Namun terdapat suatu

hal yang sangat mempengaruhi dia menang atau kalah yaitu suasana hatinya yang

tidak terobservasi sehingga disebut keadaan tersembunyi yang terdiri dari senang,

sedih, dan kesal. Suasana hati tersebut muncul dan berubah-ubah sesuai dengan

status permainan sebelumnya (menang atau kalah).

Jika saat ini Viola senang maka peluang suasana hatinya dalam permainan

selanjutnya akan senang, sedih, dan kesal adalah 0,5, 0,23 dan 0,27. Jika saat ini

Viola sedih maka peluang suasana hatinya dalam permainan selanjutnya akan

senang, sedih dan kesal adalah 0,35, 0,35 dan 0,3. Sedangkan jika saat ini Viola

kesal maka peluang suasana hatinya dalam permainan selanjutnya akan senang,

sedih dan kesal adalah 0,42, 0,35 dan 0,23. Selain itu peluang Viola menang

7/31/2019 s_mat_0800266_chapter2

17/29

24

dalam keadaan hatinya senang, sedih dan kesal adalah 0,8, 0,55 dan 0,35. Peluang

Viola kalah dalam keadaan hatinya senang, sedih dan kesal adalah 0,2, 0,45 dan

0,65.

Kasus tersebut memenuhi asumsi HMM yaitu:

1. Asumsi Markov terpenuhi, artinya keadaan terobservasi (menang atau

kalah) saat ini hanya dipengaruhi oleh keadaan terobservasi terdekat

sebelumnya dan keadaan tersembunyi (senang, sedih atau kesal) saat ini

hanya dipengaruhi oleh keadaan tersembunyi terdekat sebelumnya.

2. Asumsi stasioneritas terpenuhi, artinya pada dua buah rentang waktu

tertentu yang panjangnya sama, peluang transisi dari suatu keadaan

tersembunyi (senang, sedih atau kesal) ke keadaan tersembunyi lainnya

adalah sama.

3. Asumsi independensi/kebebasan terpenuhi, artinya pengamatan pada kasus

Viola ini tidak dipengaruhi oleh pengamatan pada kasus Viola dalam

periode waktu lain sebelumnya.

Sehingga contoh kasus tersebut dapat diselesaikan menggunakan HMM,

dengan N, M , matriks transisi A, matriks emisi B , dan matriks prior sebagai

berikut:

1. Keadaan tersembunyi yaitu suasana hati yang terdiri dari senang, sedih,

dan kesal. Maka jumlah keadaan tersembunyi yaitu = 3 .

2. Keadaan terobservasi yaitu status permainan yang terdiri dari menang dan

kalah. Maka jumlah keadaan terobservasi yaitu = 2 .

7/31/2019 s_mat_0800266_chapter2

18/29

25

3. Matriks peluang transisi dari keadaan tersembunyi A (berordo 3 3 ),

yaitu:

= 0,5 0,23 0,270,35 0,35 0,30,42 0,35 0,23 4. Matriks peluang emisi B (berordo 3 2 ), yaitu :

=0,8 0,2

0,55 0,450,35 0,65

5. Matriks prior (berordo 3 1 ), yaitu:

=

13

13

13

2.7.3 Masalah-masalah Utama dalam HMM dan Metode Penyelesaiannya

Dalam HMM terdapat beberapa permasalahan yang utama, yaitu

menghitung peluang observasi dengan algoritma Maju dan Mundur, menentukan

barisan keadaan tersembunyi dengan algoritma Viterbi dan mengestimasi

parameter-parameter dalam HMM dengan algoritma Baum Welch.

2.7.3.1 Menghitung Peluang Observasi dengan Penyelesaian Algoritma Maju

dan Algoritma Mundur

A. Algoritma Maju

Algoritma maju adalah proses iterasi yang didasarkan pada perhitungan

peluang bersyarat melalui sifat-sifat pada peluang. Dengan menggunakan definisi

peluang bersyarat ( | ) dapat dihitung, namun operasi perhitungan yang

7/31/2019 s_mat_0800266_chapter2

19/29

26

dibutuhkan akan bertambah banyak karena operasinya akan naik secara

eksponensial, seiring dengan bertambah panjangnya barisan observasi yang ada

(Nisa Pandu, 2011). Algoritma ini menyimpan nilai yang telah dihitung pada

iterasi sebelumnya, sehingga mereduksi 2 . menjadi 2 operasi. Algoritma

ini akan sangat efisien ketika panjang barisan observasinya cukup besar.

Didefinisikan sebagai variabel maju, dimana:

= ( 1 , 2 ,

, ,

= | ) (2.3)

dengan menyatakan total peluang observasi yang berakhir pada keadaan

tersembunyi i pada saat dimana = 1,2, , jika diketahui suatu barisanobservasi 1 , 2 ,, . Menurut Rabiner (1989), secara umum algoritma majuterdiri atas tiga bagian, yaitu:

1. Tahap inisialisasi

1 = 1 dimana 1 (2.4)2. Tahap induksi+1 = =1 ( +1 ) = 1, , , = 1, , 1 (2.5)

3. Tahap terminasi

Pada tahap ini adalah menjumlahkan semua peluang gabungan dari

observasi dan keadaan tersembunyi bila diketahui sebuah model sehingga

diketahui peluang marjinal dari observasi tersebut atau ditulis:

= ( )=1 (2.6)

7/31/2019 s_mat_0800266_chapter2

20/29

27

B. Algoritma Mundur

Langkah algoritma mundur hampir sama dengan algoritma maju. Namun

bedanya, pada algoritma mundur inisialisasi didasarkan pada seluruh observasi

yang ada. Jadi algoritma mundur mengganti 1 , 2 ,, menjadi+1 , +2 ,, .

= ( +1 , +2 ,, | = , ) (2.7)Tahap-tahap algoritma mundur dijelaskan sebagai berikut:


= 1 untuk = 1,2, , (2.8)Pada tahap ini, dinyatakan = 1 karena diasumsikan adalah keadaan

terobservasi akhir, dan bernilai nol untuk yang lainnya.

2. Tahap induksi

= +1 =1 +1 (2.9)Untuk = 1, 2,,1 dan = 1,2, ,

3. Tahap Terminasi

= =1 1 1 ( ) (2.10)

Algoritma maju maupun algoritma mundur akan menghasilkan peluang

observasi yang bernilai sama.

Contoh 2.3

Pandang kembali kasus permainan komputer Viola. Dalam suatu periode

permainan misalkan Viola memainkan 4 kali permainan, jika ingin diketahui

7/31/2019 s_mat_0800266_chapter2

21/29

28

peluang barisan status permainan yang dimainkan misalnya menang, kalah,

menang dan menang menggunakan Algoritma Maju dan Algoritma Mundur.

Sehingga akan dihitung peluang bahwa model = , , menghasilkanbarisan observasi = , , , , jika diketahui:

= 0,5 0,23 0,270,35 0,35 0,30,42 0,35 0,23 , = 0,8 0,20,55 0,450,35 0,65 =

1313

13

Penyelesaian:

Permasalahan tersebut akan diselesaikan dengan menggunakan algoritma

maju dan mundur dimana panjang barisan observasi = 4 .

Algoritma Maju

Tabel 2.1 Hasil perhitungan

1 2 3 41 0,267 0,049 0,0742 0,04774 2 0,183 0,075 0,0399 0,021 3 0,1167 0,1 0,0205 0,0128

= , , , ==1

= 0,08154

Algoritma Mundur


4 3 2 11 1 0,621 0,379 0,139 2 1 0,5775 0,349 0,153 3 1 0,609 0,369 0,142

7/31/2019 s_mat_0800266_chapter2

22/29

29

= 1=1

1 = 0,08154

Sehingga peluang Viola menang, kalah, menang dan menang dalam

periode permainan tersebut adalah 0,08154.

2.7.3.2 Menentukan Barisan Keadaan Tersembunyi dengan Penyelesaian

Algoritma Viterbi

Didefinisikan ( ) dimana = ( = | , ) . Jika ( ) dijumlahkan terhadap , karena = merupakan partisi dari X maka menurutaturan Bayes mengenai partisi, hasilnya menjadi

= ( = | , )=1 = 1 (2.11)

Algoritma Viterbi diperkenalkan oleh Andrew J. Viterbi pada tahun 1967.

Algoritma ini pertama kali digunakan untuk menyelesaikan masalah pengkodean

yang rumit, namun akhir-akhir ini algoritma Viterbi telah banyak digunakan untuk

mempermudah penyelesaian masalah pada bidang-bidang lain. Salah satunya,

algoritma Viterbi digunakan dalam HMM untuk mencari barisan keadaan

tersembunyi yang paling optimal dari suatu barisan observasi (Nisa Pandu, 2011).

Didefinisikan,

arg max (2.12)

yaitu argumen y yang bersesuaian dengan nilai maksimum dari z. Algoritma

Viterbi memaksimalkan ( , ) dan probabilitas bersyarat ( | ) secarabersamaan berdasarkan fakta bahwa

max , = argmax

(

, | )

( | )

7/31/2019 s_mat_0800266_chapter2

23/29

30

Algoritma Viterbi mendefinisikan:

= max 1,

2,

,

1 (1 , 2 ,

, ,

1 ,

2 ,

,

1 ,

= (2.13)

dan

= max 1 1 (2.14)Variabel menyatakan peluang terbesar sepanjang t observasi pertama

dan berakhir pada keadaan tersembunyi i. Sehingga merupakan peluang dari

barisan keadaan tersembunyi yang paling optimal untuk barisan observasi secara

parsial. Sementara menyimpan keadaan tersembunyi sebelumnya yang akanmembentuk barisan keadaan tersembunyi yang paling optimal.

Algoritma Viterbi terdiri atas empat tahap:


Pada saat t=1,

1 = ( 1 = , 1 ) = 1 | 1 = ( 1 = ) Dengan mensubstitusi asumsi awal pada HMM yaitu

= = = dan = = Diperoleh:

1 = 1

Pada tahap ini

1 = 0

2. Tahap rekursi

Pada tahap rekursi,

= max 1

,

2,

,

1 (1 , 2 ,

,

1 , ,

1 ,

2 ,

,

1 ,

=

7/31/2019 s_mat_0800266_chapter2

24/29

31

= max 1 , 2 ,, 1 {( | 1 , 2 ,, , 1 , 2 ,, 1 , = , ) ( 1 , 2 ,

, 1 ,

1 ,

2 ,

,

1 ,

=

, )}

= max1 ( = | 1 = ) 1 = max1 1

3. Tahap terminasi

= max1 (2.15)

= max 1 (2.16)4. Tahap backtracking

= +1 +1, = 1, 2,,1 (2.17)Tahap backtracking memungkinkan barisan keadaan tersembunyi yang

paling optimal ditemukan dari titik terakhir yang disimpan pada tahap rekursi.

Contoh 2.4

Perhatikan kembali kasus permainan komputer Viola dengan barisan

observasi = , , , . Setelah diketahui peluang

observasinya adalah 0,08154, maka permasalahan selanjutnya adalah menentukan

barisan keadaan tersembunyi yang optimal pada kasus ini yaitu suasana hati

Viola.

Penyelesaian:

Hasil perhitungan adalah sebagai berikut:

7/31/2019 s_mat_0800266_chapter2

25/29

32


1 2 3 41 0,267 0,0267 0,0157 0,00628 2 0,183 0,0288 0,00902 0,001985 3 0,1167 0,04686 0,00377 0,00147

Hasil perhitungan adalah sebagai berikut:


1 2 3 41 0 1( ) 3( ) 1( ) 2 0 2( ) 3( ) 1( ) 3 0 1( ) 3( ) 1( )

= 0,00628 4= 1( )

= +1 (

+1)

3= 4 4= 4 1 = 1 2= 3 3= 3 1 = 3( ) 1= 2 2= 2 3 = 1( ) Jadi saat status permainan komputer Viola menang, kalah, menang,

menang, maka barisan keadaan tersembunyi (suasana hati Viola) yang paling

optimal adalah = {1 , 3 , 1 , 1( )}.2.7.3.3 Penaksiran Parameter-parameter HMM dengan Algoritma Baum

Welch

Permasalahan ketiga berkaitan dengan bagaimana menentukan estimasi 3

parameter HMM yaitu

, , dan sehingga terbentuk model baru = (

, , )

7/31/2019 s_mat_0800266_chapter2

26/29

33

dimana . Dengan kata lain, permasalahan ketiga adalah masalahoptimasi, dan permasalahan yang harus dipecahkan adalah mengestimasi model

terbaik yang dapat menjelaskan suatu barisan observasi.

Untuk menyelesaikan permasalahan terakhir pada HMM ini, biasanya

digunakan algoritma Baum-Welch yang akan dibahas lebih lanjut pada bab III.

2.8 Deoxyribonulcleic Acid (DNA)

DNA pertama kali berhasil dimurnikan pada tahun 1868 oleh ilmuwan

Swiss Friedrich Miescher di Tubingen, Jerman, yang menamainya nuclein

berdasarkan lokasinya di dalam inti sel. Perkembangan penelitian mengenai DNA

berkembang terutama setelah Gregory Mendell mengemukakan teori genetika

dalam penelitiannya dengan menggunakan kacang ercis (Wikipedia).

Genetika adalah ilmu yang mempelajari sifat atau karakter yang

diturunkan dari satu generasi ke generasi berikutnya secara turun-temurun. Bagian

yang diturunkan bukanlah sifat itu sendiri melainkan suatu faktor yang disebut

gen. Gen terletak pada tempat khusus yang disebut locus pada kromosom (bagian

dari suatu sel) yang terdapat dalam inti sel. Bahan dasar inti sel adalah protein

yang khas yang disebut protein inti atau nukleoprotein . Nukleoprotein dibangun

oleh senyawa protein dan asam nukleat. Menurut Thomas Hunt Morgan, di dalam

inti sel terdapat bermacam-macam asam nukleat, tetapi asam nukleat yang

berhubungan dengan hereditas (penurunan sifat) diantaranya adalah DNA

(deoxyribonucleic acid ) (Ida Herlina, 2006).
http://id.wikipedia.org/w/index.php?title=Friedrich_Miescher&action=edit&redlink=1http://id.wikipedia.org/wiki/Tubingenhttp://id.wikipedia.org/wiki/Jermanhttp://id.wikipedia.org/wiki/Jermanhttp://id.wikipedia.org/wiki/Tubingenhttp://id.wikipedia.org/w/index.php?title=Friedrich_Miescher&action=edit&redlink=1

7/31/2019 s_mat_0800266_chapter2

27/29

34

DNA ( deoxyribonucleic acid ) adalah sejenis asam nukleat (hasil susunan

protein) yang tergolong biomolekul (molekul yang hidup) utama penyusun setiap

organisme (makhluk hidup). Di dalam sel, DNA umumnya terletak di dalam inti

sel sehingga memiliki peran yang sangat penting bagi setiap makhluk hidup

(Wikipedia).

Peran DNA dalam sebuah sel adalah sebagai materi genetik, artinya materi

yang bertugas menurunkan sifat pada keturunannya. Sebagai contoh sepasang

suami istri yang memiliki seorang anak, maka anak itu akan mewarisi fisik dari

ibu maupun ayahnya.

Berdasarkan karakteristik kimia, DNA merupakan polimer (gabungan dari

beberapa monomer, monomer: rantai protein) yang terdiri dari tiga komponen

utama (Ida Herlina, 2005) yaitu:

1. Gugus fosfat

2. Gula deoksiribosa

3. Basa nitrogen (gugus protein penyusun DNA) yang terdiri dari Adenine

(A) , Guanine (G) , Cytosine (C), dan Thymine (T) (1953, James Watson

dan Francis Crick).

Keempat macam basa nitrogen/gugus protein (A,G,T,C) akan membentuk

kode-kode genetik pada DNA. Kode-kode genetik tersebut terdiri atas 3 buah basa

nitrogen yang dapat mengkodekan 1 asam amino.

Suatu kenyataan bahwa keanekaragaman merupakan fenomena penting

dalam dunia kehidupan. Keanekaragaman berasal dari proses evolusi yang

didasari oleh perubahan-perubahan genetis. Perubahan dalam materi genetik yang

7/31/2019 s_mat_0800266_chapter2

28/29

35

dapat diproduksi dan diwariskan pada generasi berikutnya disebut mutasi (Ida

Herlina, 2006) .

Mutasi terdiri dari 2 macam yaitu mutasi somatik (terjadi pada sel-sel

tubuh) dan mutasi germinal (terjadi pada sel-sel kelamin). Contoh mutasi di

antaranya sindroma Turner (keterbelakangan mental) yang ditemukan oleh H.H.

turner pada tahun 1938, sindroma klinefelter, sindroma Patau dan sindroma

Down (Ida Herlina, 2006).

Namun mutasi tidak seluruhnya merugikan bagi kehidupan manusia,

karena para ahli menerapkan mutasi untuk mengembangkan teknologi pangan

maupun ternak dan menelaah lebih lanjut mengenai penyakit yang diturunkan

beserta usaha untuk menanggulanginya.

Usaha tersebut yaitu rekayasa genetika yaitu rekombinasi DNA.

Rekombinasi DNA adalah teknik menyusun DNA asing ke dalam molekul DNA

suatu organisme. Tujuannya adalah agar organisme yang disisipi DNA asing

memiliki kemampuan untuk mengekspresikan gen baru.

Dalam penelitian DNA terdapat metode DNA sequence allignment atau

penyejajaran DNA yang dilakukan untuk meneliti kecocokan DNA baru dengan

DNA sebelumnya (Wikipedia). Penyejajaran DNA ini juga dilakukan untuk

melihat kecocokan DNA dari beberapa spesies yang berbeda, misalnya antara

manusia dan tikus atau lainnya. Dalam penyejajaran DNA ini jika suatu basa

nitrogen penyusun DNA suatu spesies sama dengan basa nitrogen penyusun DNA

dari spesies lain sama maka dikatakan cocok, jika tidak sama maka dikatakan

7/31/2019 s_mat_0800266_chapter2

29/29

36

sebagai sisipan dan jika terdapat suatu basa nitrogen yang hilang maka dikatakan

sebagai hapusan (Wikipedia).

Salah satu peran matematika dalam proses rekayasa genetika ini adalah

Hidden Markov Model (HMM) yang digunakan dalam meneliti barisan basa

nitrogen yang terdapat dalam DNA. Terutama dalam DNA sequence allignment,

yaitu proses pencocokan DNA yang diteliti dengan DNA lain yang terarsip

sebelumnya (wikipedia.org). Sehingga akan dipaparkan lebih lanjut mengenai

aplikasi dari HMM dalam suatu DNA terutama aplikasi algoritma Baum-Welch

untuk menentukan parameter-parameter pada HMM pada bab III dan IV.

Salah satu hal yang erat kaitannya dengan DNA adalah taksonomi yaitu

ilmu yang mempelajari urutan kekerabatan makhluk hidup. Sehingga dalam

penelitian berikutnya mengenai DNA akan digunakan penyejajaran suatu DNA

dengan DNA lain yang memiliki urutan taksonomi (urutan kekerabatan) cukup

dekat. Sehingga dalam penelitian mutasi suatu spesies, harus ditentukan terlebih

dahulu sampel DNA spesies lain yang mirip sehingga dapat dijadikan sampel

pambanding untuk meneliti mutasi pada spesies tersebut. Penelitian tingkat

kecocokan dalam menentukan sampel tersebut dapat menggunakan HMM yang

akan dibahas lebih lanjut dalam bab IV.

s_mat_0800266_chapter2

Documents