KAJIAN MODEL HIDDEN MARKOV DISKRET DAN APLIKASINYA PADA DNA
NURMAILY
SEKOLAH PASCA SARJANA INSTITUT PERTANIAN BOGOR BOGOR 2009
PERNYATAAN MENGENAI TUGAS AKHIR DAN SUMBER INFORMASI Dengan ini saya menyatakan bahwa tesis dengan judul “Kajian Model Hidden Markov Diskret dan Aplikasinya pada DNA” adalah karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini.
Bogor, Agustus 2009 Nurmaily NRP G551070281
ABSTRACT NURMAILY. The Study of Discrete Hidden Markov Model and Its Application on DNA Sequence. Under supervision of BERLIAN SETIAWATY and N. K. KUTHA ARDANA. A discrete hidden Markov model is a model which consists of the cause of event and observation process. This model assumes that the cause of event is a Markov chain, which is not observed directly. The observation process has discrete range. Parameters of this model are transition probability matrices. They are estimated using the maximum likelihood method and expectation maximization algorithm. The estimation procedure involves the change of measure. The estimation of parameters uses Mathematica 7.0, a functional programming based on algebraic computer systems. The model is applied to the DNA sequence. The estimated parameters are used to calculate the expectation of DNA sequence. The result depends on the decision of the initial value. There should be another study for determining the initial value which gives the optimal result. Keywords: Markov chain, discrete hidden Markov model, expectation maximization algorithm.
RINGKASAN NURMAILY. Kajian Model Hidden Markov Diskret dan Aplikasinya pada DNA. Di bawah bimbingan BERLIAN SETIAWATY dan N.K. KUTHA ARDANA. Setiap kejadian berkaitan erat dengan penyebab kejadian. Jika penyebab kejadian tersebut tidak diamati secara langsung dan membentuk rantai Markov, maka pasangan kejadian dan penyebabnya dapat dimodelkan dengan model Hidden Markov (Hidden Markov Model, HMM). Semua proses didefinisikan pada ruang peluang Ω, , . Misalkan ; adalah rantai Markov dengan state berhingga yang bersifat homogen dan diasumsikan ; adalah proses tidak diamati secara langsung, sedangkan observasinya. Pasangan proses stokastik , merupakan model Hidden Markov. Model Hidden Markov (Elliot et al. 1995) yang digunakan pada karya ilmiah ini adalah + Y
di mana , ,…, matriks peluang transisi dengan
CX
,
,
,
, A dan C merupakan
dan
memenuhi ∑
Jika dari , yaitu
, untuk
,
W
|
1, 0,
0, dan ∑ | 0 | diag diag
, maka vektor dan untuk
1,
dan
0. diag diag
, yang memenuhi
.
, ,…, merupakan nilai harapan ergodic memenuhi dan ∑ 1.
Parameter yang digunakan pada model di atas adalah ,1 , , ,1 , 1
.
Akan ditentukan parameter baru dengan menggunakan algoritme EM ,1 , , ̂ ,1 , 1 , yang memaksimumkan fungsi log-likelihood bersyaratnya. Hasilnya berupa parameter dalam bentuk pendugaan rekursif, diantaranya penduga untuk state, penduga untuk banyaknya loncatan, penduga lamanya rantai Markov berada pada suatu state tertentu dan penduga proses observasi.
Pendugaan rekursif yang diperoleh adalah 1. Pendugaan untuk state ∑ , . ∑ , , , 2. Pendugaan Banyaknya Lompatan = , , , Penduga banyaknya lompatan adalah ∑ , , , 1 Penduga smoother banyaknya lompatan adalah ∑ , , , 3. Pendugaan Lamanya Waktu Kejadian ,
.
,
.
.
Penduga lamanya waktu kejadian adalah ∑
,
,
,
,
.
Penduga smoother lamanya waktu kejadian adalah ∑
,
4.
,
,
.
Pendugaan untuk Proses Observasi ∑ , , , Penduga untuk proses observasi adala ∑ , , , Penduga smoother untuk proses observasi adalah ∑ , , ,
,
. ,
,
.
.
Dari pendugaan rekursif dapat ditentukan parameter model sebagai berikut
, 1 ̂ Nilai Harapan
,
.
, 1
, 1
.
adalah |
∑
1∑
1
.
Model Hidden Markov diskret di atas diaplikasikan pada perubahan urutan basa DNA pada spesies Aspergillus niger, dengan N = 2. Dalam perkembangan lebih lanjut, dibuat suatu program komputasi yang berbasis pemprograman fungsional untuk menyelesaikan masalah tersebut. Software yang digunakan adalah Mathematica 7.0. Hasil yang di peroleh pada penelitian ini sangat bergantung pada penentuan nilai awal. Sampai saat ini hasil yang diperoleh belum cukup baik, karena belum ditemukan cara untuk menentukan nilai awal yang paling baik sehingga hasil yang diperoleh optimal. Kata kunci: Rantai Markov, model hidden Markov diskret, algoritme EM.
© Hak Cipta milik IPB, tahun 2009 Hak Cipta dilindungi Undang-Undang 1. Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumber. a. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah b. Pengutipan tidak merugikan kepentingan yang wajar IPB 2. Dilarang mengumumkan dan memperbanyak sebagian atau seluruh Karya Tulis dalam bentuk apapun tanpa izin IPB.
KAJIAN MODEL HIDDEN MARKOV DISKRET DAN APLIKASINYA PADA DNA
NURMAILY
Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Program Studi Matematika Terapan
SEKOLAH PASCA SARJANA INSTITUT PERTANIAN BOGOR BOGOR 2009
Penguji Luar Komisi pada Ujian Tesis: Dr. Ir. Wayan Mangku, M.Sc.
Judul Tesis : Kajian Model Hidden Markov Diskret dan Aplikasinya pada DNA. Nama : Nurmaily NRP : G551070281
Disetujui Komisi Pembimbing
Dr. Berlian Setiawaty, M.S. Ketua
Ir. N. K. Kutha Ardana, M.Sc. Anggota
Diketahui
Ketua Program Studi Matematika Terapan
Dr. Ir. Endar H. Nugrahani, M.S.
Tanggal Ujian: 19 Agustus 2009
Dekan Sekolah Pascasarjana
Prof, Dr. Ir. Khairil A. Notodiputro, M.S.
Tanggal Lulus:
PRAKATA
Puji dan syukur penulis panjatkan ke hadirat Allah SWT atas segala rahmat dan karunia-Nya sehingga tugas akhir yang berjudul “Kajian Model Hidden Markov Diskret dan Aplikasinya pada DNA” ini bisa terselesaikan sebagai salah satu syarat untuk menyelesaikan pendidikan pada Program Studi Matematika, Sekolah Pascasarjana Institut Pertanian Bogor. Terimakasih yang mendalam penulis sampaikan kepada: 1. Dr. Berlian Setiawaty, M.S. dan Ir. N. K. Kutha Ardana, M.Sc. selaku pembimbing yang telah memberikan bimbingan dan motivasinya. 2. Dr. Ir. Wayan Mangku, M.Sc. selaku penguji yang telah memberikan saran dan kritiknya. 3. Departemen Agama Republik Indonesia yang telah memberikan beasiswa kepada penulis selama menempuh pendidikan di IPB. 4. Seluruh keluarga atas segala dukungan, doa dan kasih sayangnya. 5. Mahasiswa S2 Matematika Terapan IPB angkatan 2007, serta semua pihak yang telah membantu penulis. Penulis menyadari bahwa tugas akhir ini masih begitu banyak kekurangan. Dengan segala keterbatasan yang ada, semoga tugas akhir ini bermanfaat.
Bogor, Agustus 2009 Nurmaily
RIWAYAT HIDUP
Penulis dilahirkan di Banda Aceh pada tanggal 21 Mei 1971 dari pasangan Bapak Rusli Tgk. Ali (Alm) dan Ibu Nurjannah. Penulis merupakan anak ketiga dari lima bersaudara. Pendidikan sarjana ditempuh di Program Studi Matematika Fakultas Keguruan dan Ilmu Pendidikan Universitas Syiah Kuala Banda Aceh, lulus pada tahun 1996 dan pada tahun 2007 penulis diberi kesempatan melanjutkan studi di Program Studi Matematika Terapan, Sekolah Pascasarjana Institut Pertanian Bogor dengan beasiswa dari Departemen Agama Republik Indonesia. Penulis bekerja sebagai guru matematika pada Madrasah Aliyah Negeri Model Banda Aceh sampai sekarang.
DAFTAR ISI Halaman DAFTAR ISI …………………………………………………………………
xii
DAFTAR GAMBAR ………………………………………………………..
xiv
DAFTAR LAMPIRAN ……………………………………………………...
xv
BAB 1 PENDAHULUAN 1.1 Latar Belakang ………………………………………………... 1.2 Tujuan Penelitian ……………………………………………....
1 3
BAB 2 LANDASAN TEORI 2.1 Pengantar Teori Peluang ……………………………………... 2.2 Rantai Markov ……………………………………………….... 2.3 Ruang Hasil Kali Dalam ………………………………………..
4 10 13
BAB 3 MODEL HIDDEN MARKOV 3.1 State dan Proses Observasi dalam waktu diskret ……………… 3.2 Perubahan Ukuran ……………………………………………... 3.3 Pendugaan Rekursif ……………………………………………. 3.4 Pendugaan Parameter ………………………………………….. 3.5 Nilai Harapan ܻାଵ ………………………………………………….. 3.6 Algoritme Pendugaan Parameter ……………………………………...
15 21 29 38 47 47
BAB 4 APLIKASI MODEL HIDDEN MARKOV DISKRET PADA DNA 4.1 DNA Sebagai Materi Genetik …………………………………………. 4.2 Data Input DNA ……………………………………………………….. 4.3 Aplikasi Model Hidden Markov Diskret pada DNA ………………….. 4.4 Hasil Komputasi …………………………………………………
54
BAB 5 KESIMPULAN DAN SARAN 5.1 Kesimpulan ……………………………………………………... 5.2 Saran …………………………………………………………….
58 58
DAFTAR PUSTAKA ………………………………………………………….
59
50 52 53
LAMPIRAN …………………………………………………………………… 61
DAFTAR TABEL Halaman 1
Tabel nilai harapan model dengan 2 penyebab kejadian………………..
68
DAFTAR GAMBAR Halaman
1 Pembentukan secara skematik struktur dsDNA dari gula fosfat sebagai backbone dan basa nukleotida (A). Bentuk skematik double-helix DNA (B)……………………………………………… 2 Grafik distribusi nilai dugaan urutan DNA menggunakan penduga smoother untuk 2 penyebab kejadian (N = 2). Banyaknya data, 0.16 0.26 0.31 0.66 0.09 0.02 T = 1000. Nilai awal , 0.40 0.43 0.69 0.34 0.35 0.29 0.49 dan ..…………………………………………….......... 0.51 3 Grafik distribusi nilai dugaan urutan DNA menggunakan penduga smoother untuk 2 penyebab kejadian (N = 2). Banyaknya data, 0.37 0.20 0.37 0.35 0.27 0.02 T = 1000. Nilai awal , 0.26 0.33 0.63 0.65 0.10 0.45 0.50 dan ................................................................................. 0.50
52
55
56
DAFTAR LAMPIRAN Halaman 1
Bukti Teorema 3.3.5 ……………………………………………............
61
2
Program 1...................................................................................................
66
3
Program 2..................................................................................................
72
4
Tabel nilai harapan model dari Program 1................................................
78
5
Tabel nilai harapan model dari Program 2................................................
83
1
BAB I PENDAHULUAN 1.1 Latar Belakang Dalam kehidupan sehari-hari banyak fenomena yang dapat dimodelkan dengan proses stokastik. Setiap kejadian berkaitan erat dengan penyebab kejadian tersebut. Jika penyebab kejadian tersebut tidak diamati secara langsung dan membentuk rantai Markov, maka pasangan kejadian dan penyebabnya dapat dimodelkan dengan model Hidden Markov (Hidden Markov Model, HMM). ;
Misalkan
adalah penyebab kejadian yang tidak diamati secara langsung
dan membentuk rantai Markov yang bersifat homogen, sedangkan merupakan proses observasi, maka pasangan Model. Untuk
dan
,
;
merupakan Hidden Markov
peubah acak diskret maka pasangan
,
merupakan
Hidden Markov Model diskret. Karakteristik dari Model Hidden Markov dicirikan oleh parameter-parameternya, antara lain berupa matriks peluang transisi. Parameter tersebut diduga melalui pendugaan
ulang
parameter
dengan
menggunakan
algoritme
Expectation
Maximization (EM), sehingga diperoleh parameter model dalam bentuk pendugaan rekursif. Pendugaan rekursif ini nantinya dapat dievaluasi kembali dengan menggunakan parameter atau mungkin dengan data yang baru. Aplikasi Model Hidden Markov diskret sudah banyak dikembangkan pada berbagai bidang antara lain, di bidang biologi yaitu “Penerapan Hidden Markov Model dalam Prediksi Gen Organisme Prokariotik” (Hermanto, 2007), di bidang kebahasaan yaitu “Penggunaan Hidden Markov Model untuk Kompresi Kalimat” (Wibisono,2008), ”Sistem Pengenalan Bicara dengan Menggunakan Sistem Hidden Markov Model” (Hasymi,1996), di bidang teknologi komunikasi yaitu “Algoritma Viterbi dalam Metode HMM pada teknologi Speech Recognition” (Irfani, 2007),”Selecting Hidden Markov Model state number with Cross-Validated Likehood” (Celeux dan Durand,
2
2008), di bidang teknik yaitu “Aplikasi Pengenalan Wicara HMM untuk Kendali Robot PDA” (Bachtiar, 2007), “Computational Issues in Parameter Estimation for Stationary Hidden Markov Models” (Bulla dan Berzel, 2008), “Kajian Hidden Markov Diskret dan Aplikasinya pada Harga Gabah Kering Panen” (Jamal, 2008), di bidang budaya yaitu “Pengenalan Karakter Mandarin Secara On-Line dengan Menggunakan Hidden Markov Models” (Hadi, 2005). Dalam tesis ini akan dibahas aplikasi Model Hidden Markov diskret Elliott et al. 1995 yang telah dikaji oleh Jamal (2008). Model ini diaplikasikan untuk menggambarkan struktur urutan DNA pada spesies Aspergillus niger. Dengan menggunakan data urutan DNA pada spesies Aspergillus niger, maka dapat diduga parameter modelnya. Sebelum melakukan
pendugaan parameter, terlebih dahulu
dilakukan perubahan ukuran peluang yang kemudian diinterpretasikan kembali dengan menggunakan peluang asal. Perubahan ukuran peluang ini dibatasi oleh turunan Radon-Nykodim. Dalam ukuran peluang yang baru, dilakukan pendugaan parameter melalui pendugaan ulang parameter. Hasilnya berupa pendugaan rekursif di antaranya penduga untuk state, penduga untuk banyaknya loncatan, penduga lamanya rantai Markov berada pada suatu state tertentu dan penduga proses observasi. Pendugaan rekursif ini kemudian digunakan untuk menentukan parameter dengan menggunakan algoritme Expectation Maximization (EM ). Dalam perkembangan lebih lanjut, dibuat suatu program komputasi yang berbasis pemprograman fungsional untuk menyelesaikan masalah Model Hidden Markov diskret.
Software
yang
digunakan
adalah
Mathematica
7.0.
Keuntungan
menggunakan program tersebut adalah waktu kerja yang efisien serta memudahkan dalam menganalisis data yang cukup banyak. Dalam tesis ini, program tersebut digunakan untuk membantu penyelesaian masalah perubahan urutan DNA.
3
1.2 Tujuan Penelitian Tujuan dari penelitian ini adalah 1.
Mengkaji Model Hidden Markov diskret (Elliot et al. 1995).
2.
Melakukan pendugaan parameter melalui pendugaan ulang parameter, a. Pendugaan untuk state, b. Pendugaan untuk banyaknya loncatan, c. Pendugaan lamanya rantai Markov berada pada suatu state, d. Pendugaan proses observasi.
3. Mengimplementasikan Model Hidden Markov untuk masalah urutan
DNA.
BAB II LANDASAN TEORI
2.1 Pengantar Teori Peluang Definisi 2.1.1 Percobaan Acak (Ross 1996) Dalam suatu percobaan seringkali dilakukan pengulangan yang biasanya dilakukan dalam kondisi yang sama. Semua kemungkinan hasil yang akan muncul dapat diketahui, namun hasil pada percobaan berikutnya tidak dapat diketahui dengan tepat. Percobaan seperti ini, yang dapat diulang dalam kondisi yang sama, disebut percobaan acak.
Definisi 2.1.2 Ruang Contoh dan Kejadian (Ghahramani 2005) Himpunan dari semua kemungkinan hasil dari suatu percobaan acak disebut Ruang contoh dan dinotasikan dengan Ω. Suatu kejadian A adalah himpunan bagian dari Ω.
Definisi 2.1.3 Medan- σ (Ghahramani 2005) Medan- σ adalah himpunan yang anggotanya merupakan himpunan bagian dari Ω yang memenuhi: ;
1
,
2 Jika
,
3 Jika
maka
∞
;
.
maka
Definisi 2.1.4 Ukuran Peluang (Ghahramani 2005) Misalkan fungsi 1
adalah medan- σ dari ruang contoh Ω. Ukuran Peluang adalah suatu
:
0,1 pada Ω, 0,
yang memenuhi:
;
2 Jika P (φ ) = 0, P (Ω ) = 1;
4
5
3 Jika
,
adalah himpunan yang saling lepas yaitu Ai ∩ A j = φ
,
⎛∞ setiap pasangan i ≠ j , maka P⎜⎜ U Ai ⎝ i =1
untuk
⎞ ∞ ⎟⎟ = ∑ P( Ai ) . Pasangan Ω, , ) disebut ruang ⎠ i =1
peluang.
Definisi 2.1.5 Kejadian Saling Bebas (Grimmet dan Stirzaker 2001) Kejadian A dan B dikatakan saling bebas jika P ( A ∩ B ) = P ( A) P ( B ). Secara umum, himpunan kejadian
{Ai : i ∈ I }
⎛ ⎞ dikatakan saling bebas jika P⎜⎜ I Ai ⎟⎟ = ∏ P ( Ai ) ⎝ i∈J ⎠ i∈J
untuk setiap himpunan bagian berhingga dari J dari I.
Definisi 2.1.6 Peluang Bersyarat (Ghahramani 2005) Misalkan Ω, , ) adalah ruang peluang dan
,
maka peluang A dengan
syarat B didefinisikan sebagai
.
|
Definisi 2.1.7 Peubah Acak (Grimmet dan Stirzaker 2001) Misalkan Ω adalah ruang contoh dan adalah fungsi
:Ω
adalah medan- σ dari Ω. Suatu peubah acak X
dengan {ω ∈ Ω : X (ω ) ∈ A}∈
untuk setiap
.
Definisi 2.1.8 Peubah Acak Diskret (Grimmet dan Stirzaker 2001) Peubah acak X dikatakan diskret jika nilainya hanya pada himpunan bagian tercacah dari .
6
Definisi 2.1.9 Fungsi Sebaran (Grimmet dan Stirzaker 2001) Fungsi sebaran dari suatu peubah acak X adalah oleh
:
0,1 , yang didefinisikan
.
Definisi 2.1.10 Fungsi Kerapatan Peluang (Grimmet dan Stirzaker 2001) Misalkan Ω, , diskret
X
adalah ruang peluang. Fungsi kerapatan peluang dari peubah acak
adalah
suatu
fungsi
p : S → [0,1]
yang
didefinisikan
oleh
p X ( x) = P( X = x) untuk setiap x ∈ S .
Definisi 2.1.11 Fungsi Kerapatan Peluang Bersama Dua Peubah Acak diskret dan Marginal (Grimmet dan Stirzaker 2001) Misalkan Ω, ,
adalah ruang peluang. Fungsi kerapatan peluang bersama dari
peubah acak diskret X dan Y adalah suatu fungsi p : S × S → [0,1] yang didefinisikan oleh p XY ( x, y) = P( X = x, Y = y) untuk setiap x, y ∈ S . Fungsi kerapatan peluang marginal dari peubah acak X dan Y adalah berturut-turut ∑
,
∑
,
.
Definisi 2.1.12 Fungsi Kerapatan Peluang Bersyarat (Ross 1996) Jika X dan Y merupakan peubah acak diskret, maka fungsi kerapatan peluang bersyarat dari X jika diberikan Y=y, terdefinisi untuk setiap y sedemikian sehingga
P(Y=y)>0 adalah |
,
|
.
7
Definisi 2.1.13 Bebas Stokastik Identik (Hogg et al.2005) Misalkan X 1 , X 2 ,..., X n adalah n peubah acak yang memiliki fungsi kerapatan yang sehingga
sama yaitu
M
,
dan fungsi kerapatan bersamanya adalah
. Peubah acak X 1 , X 2 ,K, X n disebut bebas stokastik identik.
Definisi 2.1.14 Nilai Harapan Peubah Acak Diskret (Ghahramani 2005) Jika
X
adalah
peubah
acak
diskret
dengan
fungsi
kerapatan
peluang
p X ( x) = P( X = x) maka nilai harapan dari X adalah E[ X ] = ∑ xp X ( x) . x
Definisi 2.1.15 Nilai Harapan Bersyarat (Ghahramani 2005)
Misalkan X dan Y adalah peubah acak diskret dengan fungsi kerapatan peluang bersyarat dari X dengan syarat Y=y adalah
| , maka nilai harapan bersyarat
|
dari X dengan syarat Y=y adalah |
∑
|
| .
Definisi 2.1.16 Fungsi Indikator (Cassela dan Berger 1990)
Misalkan A adalah suatu kejadian pada ruang peluang Ω, , A adalah suatu fungsi I A : Ω → [0,1] , yang didefinisikan
. Fungsi indikator dari
8
1, jika 0, jika
.
Definisi 2.1.17 Himpunan P-Null (Grimmet dan Stirzaker 2001)
Misalkan Ω, , Ω:
adalah ruang peluang. Himpunan P-Null didefinisikan sebagai A,
,
0.
Definisi 2.1.18 Ruang Peluang Lengkap (Billingsley 1986)
Ruang peluang Ω, ,
disebut lengkap, jika A ⊂ B, B ∈
, dan P ( B ) = 0 maka
.
Definisi 2.1.19 Filtrasi (Grimmet dan Stirzaker 2001)
Misalkan dari ,
adalah medan- σ dan disebut filtrasi jika
,
,
merupakan barisan submedan-
untuk semua k ∈ .
Definisi 2.1.20 Filtrasi Lengkap (Protter 1995)
Misalkan Ω, ,
adalah ruang peluang lengkap. Misalkan
sebuah filtrasi. Jika
memuat semua himpunan P-Null di
=
maka
;
adalah disebut filtrasi
lengkap.
Definisi 2.1.21 Terukur(Measurable) (Grimmet dan Stirzaker 2001)
Misalkan X adalah peubah acak diskret yang terdefinisi pada ruang peluang Ω, , dan S adalah ruang state X. Jika {ω ∈ Ω; X (ω ) ∈ A}∈ dikatakan terukur- .
untuk setiap A ⊂ S , maka X
9
Definisi 2.1.22 Adapted (Grimmet dan Stirzaker 2001) Ω, ,
Misalkan
;
adalah ruang peluang. Barisan peubah acak jika
dikatakan adapted terhadap filtrasi {
terukur-
untuk setiap .
Definisi 2.1.23 Predictable (Grimmet dan Stirzaker 2001)
adalah filtrasi. Barisan peubah acak
Misalkan
predictable (terduga), jika
terukur-
;
dikatakan
untuk setiap k.
Definisi 2.1.24 Nilai Harapan Bersyarat (Shreve 2004)
Misalkan Ω, ,
adalah ruang peluang dan
adalah submedan- σ dari .
Misalkan X adalah peubah acak yang terintegralkan pada Ω, ,
. Maka
|
disebut nilai harapan bersyarat dari X jika diketahui , didefinisikan sebagai sebarang peubah acak Y yang memenuhi: 1 Y terukur- ; 2
∫ YdP =∫ XdP, ∀A ∈ A
;
A
Persamaan
|
|
dapat ditulis
.
Teorema 2.1.25 Nilai Harapan Bersyarat (Billingsley 1986)
dan
Misalkan X terintegralkan,
adalah dua medan- σ yang memenuhi
maka berlaku: |
|
|
|
|
Teorema 2.1.26. Sifat-sifat Nilai Harapan Bersyarat (Shreve 2004)
Misalkan X,Y, dan XY terintegralkan, maka berlaku: 1
|
;
2 Jika X terukur- , maka
|
;
.
,
10
|
|
3
4 Jika X ≥ 0 , maka 5 Jika Y terukur-
|
| ,
,
0; |
maka
skalar;
| .
Definisi 2.1.27. Kontinu Absolut (Billingsley 1986) _
Jika P dan P adalah dua ukuran peluang pada Ω, kontinu absolut ke ukuran peluang mengakibatkan
_
P
_
. Ukuran peluang P dikatakan
jika untuk setiap _
_
A ∈ F , P ( A) = 0 _
P ( A) = 0, dinotasikan P << P . Jika P << P dan P << P maka _
kedua ukuran dikatakan ekuivalen dan dinotasikan P ≡ P .
Definisi 2.1.28 Radon-Nikodym (Billingsley 1986) _
Jika P dan P adalah dua ukuran peluang pada Ω,
_
sedemikian sehingga P << P, _
maka terdapat peubah acak tak negatif Λ sehingga P ( A) = ∫ ΛdP untuk semua A
dinotasikan
= Λ.
2.2 Rantai Markov Definisi 2.2.1 Ruang State (Grimmet dan Stirzaker 2001)
Misalkan S adalah himpunan nilai dari barisan peubah acak, maka S disebut ruang state.
Definisi 2.2.2 Proses Stokastik (Ross 1996)
Proses stokastik X =
;
terdefinisi pada ruang peluang Ω, ,
adalah
suatu himpunan dari peubah acak yang memetakan ruang contoh Ω ke ruang state S.
11
Definisi 2.2.3 Rantai Markov dengan Waktu diskret (Grimmet dan Stirzaker
2001) Misalkan Ω, , ;
adalah ruang peluang dan S adalah ruang state. Proses stokastik dengan ruang state S, disebut rantai Markov dengan waktu diskret
jika untuk setiap k = {0,1,2,…}, berlaku: |
,
|
,
untuk semua kemungkinan nilai dari i0 , i1 ,..., ik , ik +1 ∈ S .
Definisi 2.2.4 Matriks Peluang Transisi (Grimmet dan Stirzaker 2001)
Misalkan
;
X =
adalah rantai Markov dengan state S berukuran N.
matriks transisi
|
, dengan
untuk
j , i ∈ S adalah matriks peluang transisi dari X.
Definisi 2.2.5 Rantai Markov Homogen (Grimmet dan Stirzaker 2001)
Misalkan X = homogen jika
;
adalah rantai Markov dengan ruang State S, dikatakan |
|
untuk j , i ∈ S .
Definisi 2.2.6 Peluang Transisi n-step ( ( a (nji ) ) (Ross 1996)
Misalkan X =
adalah rantai Markov dengan ruang state S. Peluang transisi n-step
dari X adalah peluang proses berpindah dari state i ke state j dengan n langkah yang didefinisikan oleh: |
,
0,
,
S.
Definisi 2.2.7 Accessible (Ross 1996)
Suatu state j disebut terakses (accessible) dari suatu state i, ditulis i → j , jika ada sebuah bilangan k ≥ 0 sehingga a (jik ) ≥ 0.
12
Definisi 2.2.8 Communicate (Ross 1996)
Dua state i dan j disebut berkomunikasi (communicate), ditulis i ↔ j , jika state i dapat diakses dari state j dan state j dapat diakses dari state i.
Definisi 2.2.9 Kelas State (Ross 1996)
Himpunan tak kosong S disebut kelas state apabila semua pasangan state yang merupakan anggota dari S berkomunikasi satu dengan yang lainnya, serta tidak ada state yang merupakan anggota S yang berkomunikasi dengan suatu state yang bukan anggota dari S.
Definisi 2.2.10 Irreducible (Ross 1996)
Rantai Markov disebut tak tereduksi (irreducible) jika hanya terdapat satu kelas state, yaitu jika semua state-nya berkomunikasi satu dengan yang lainnya.
Definisi 2.2.11 Recurrent (Ross 1996)
Peluang bahwa suatu proses yang dimulai dari state i akan bertransisi ke state j didefinisikan sebagai ∑∞
. State i berulang (recurrent) jika
1.
Teorema 2.2.12 Recurrent (Ross 1996)
State i berulang (recurrent) jika
∑
∞ n =0
aii( n ) = ∞ .
Definisi 2.2.13 (Ross 1996)
1
Suatu state i disebut memiliki periode d jika d adalah persekutuan pembagi terbesar bagi n sehingga aii( n ) > 0 ;
13
2
Suatu state dengan periode = 1 disebut aperiodic, sedangkan state dengan periode ≥ 2 disebut periodic;
3
Suatu state disebut berulang positif jika state tersebut berulang serta berlaku: jika proses dimulai dari state i, maka nilai harapan dari waktu sampai proses tersebut kembali ke state i adalah bilangan berhingga;
4
Rantai Markov dengan state berulang positif dan aperiodic disebut ergodic.
Teorema 2.2.14 Nilai Harapan Rantai Markov Homogen (Ross 1996)
Misalkan
;
adalah rantai Markov yang ergodic dengan ruang state
S berukuran N dan misalkan A merupakan matriks peluang transisi berukuran N × N dengan A = (a ji ) dan
|
maka nilai harapan dari X
dinotasikan dengan E[ X ] = π yang memenuhi:
Aπ = π dan
N
∑π j =1
j
= 1.
2.3 Ruang Hasil Kali Dalam Definisi 2.3.1 Ruang Vektor (Anton dan Rorres 2004)
V disebut ruang vektor, jika untuk setiap vektor u,v,w ∈ V dan sebarang skalar k dan l
dipenuhi aksioma berikut: 1 Jika u,v ∈ V, maka u+v ∈ V; 2 u+v=v+u; 3 u+(v+w)=(u+v)+w; 4 Ada 0 ∈ V sehingga 0+u=u+0=u, ∀ u ∈ V; 5 Untuk ∀ u ∈ V, ada -u ∈ V sehingga u+(-u)=(-u)+u=0; 6 Jika k adalah sebarang skalar dan u ∈ V, maka k u ∈ V; 7 k(u+v)=ku+kv;
14
8 (k+l)u=ku+lu; 9 k(lu)=(kl)u; 10 lu=u.
Definisi 2.3.2 Perkalian Dalam (Anton dan Rorres 2004)
Jika u = ( u1 , u 2 ,K, u n ) dan v = ( v1 , v2 ,K, vn ) adalah sebarang vektor pada
, maka
hasil kali dalam euclied u.v didefinisikan oleh: u.v= u1v1 + u 2 v2 + K + u n vn .
Definisi 2.3.3 Ruang Hasil Kali Dalam (Anton dan Rorres 2004)
Sebuah hasil kali dalam pada ruang vektor real V adalah fungsi yang mengasosiasikan bilangan real
u, v
dengan masing-masing pasangan vektor u dan v
pada V
sedemikian sehingga aksioma-aksioma berikut terpenuhi untuk semua u, v, w ∈ V dan skalar k. 1. u , v = v, u ; 2. u + v, w = u , w + v, w ; 3. ku , v = k u , v ; 4. v, v ≥ 0; dan v, v = 0 jika dan hanya jika v = 0. Sebuah ruang vektor real dengan sebuah hasil kali dalam dinamakan ruang hasil kali dalam real.
15
BAB III MODEL HIDDEN MARKOV 3.1 State dan Proses Observasi dalam waktu diskret Semua
proses
didefinisikan
;
pada
ruang
Ω, ,
peluang
.
Misalkan
adalah rantai Markov dengan state berhingga yang bersifat
homogen
dan
;
diasumsikan
tidak
diamati
secara
langsung,
sedangkan
adalah proses observasinya. Pasangan proses stokastik
,
merupakan model Hidden Markov. ,
Ruang state dari X adalah yaitu himpunan vektor satuan
di
,…,
0, … ,0,1,0, … ,0 ,
dengan
, di mana hanya elemen ke-i yang bernilai
1 dan lainnya 0. ,
Misalkan ,
,
Karena
,
dan
,
merupakan medan- σ yang dibangkitkan oleh
,
merupakan filtrasi lengkap yang dibangkitkan oleh
.
merupakan rantai Markov homogen, maka berdasarkan sifat rantai
Markov diperoleh ,
,
,
.
Lema 3.1.1 [Elliot et al.1995] Misalkan
merupakan
peluang
transisi
merupakan matriks peluang transisi yang memenuhi ∑ maka |
|
Bukti: Misalkan
maka
|
∑ ∑
.
dan 1,
16
,
,…,
. Sehingga dapat ditulis . Jadi ,
,…, ■
. Didefinisikan
(3.1) dengan |
| | |
|
|
|
0. Sehingga diperoleh persamaan state .
(3.2)
Lema 3.1.2 [Elliot et al.1995] ,
.
Bukti: Karena
,
1, untuk 0, untuk
,
maka ,
∑
, .
■
17
Jika dari
,
, maka vektor dan untuk
, yaitu
∑
,…,
merupakan nilai harapan
ergodic memenuhi
dan
1.
Proses state
tidak diamati secara langsung namun terdapat proses observasi
yaitu ,
,
,
dan
bersifat bebas stokastik identik,
di mana state dari
,
adalah ,
Misalkan dibangkitkan oleh
, ,
, ,
,
, ,
,
merupakan vektor satuan di
dengan ,
,
lengkap yang dibangkitkan oleh
,
,
,
dan
merupakan filtrasi ,
. Misalkan
medan- σ dari Ω yang dibangkitkan oleh
.
merupakan medan- σ dari Ω yang
,
dan
saling bebas. Ruang
,
,
,
,
dan
,
merupakan
merupakan filtrasi
, maka diperoleh
lengkap yang dibangkitkan oleh
,
,
,
,
,
,
,
.
Lema 3.1.3 [Elliot et al.1995] Misalkan
C = (c ji ) M×N
adalah
matriks
peluang
dan memenuhi ∑
|
1, 1
maka |
.
Bukti: Misalkan |
X k = ei , maka ∑
|
∑ , .
,
,
transisi,
di , 1
mana ,
18
|
Sehingga dapat ditulis Jadi
|
.
|
.
■
Didefinisikan (3.3) dengan |
| |
|
|
|
|
|
0. Sehingga dapat diperoleh suatu persamaan observasi .
(3.4)
Notasi 3.1.4 Misalkan dengan ∑
1, 0,
,
dan
,
,
1. . Untuk X k = el , maka
|
Misalkan
| |
, ∑
,
| |
, , ∑
, ,
.
,
,
,
19
,
Jadi ,
,
,
∑
|
,
Sehingga dapat ditulis
,
∑
|
,
. dan
maka |
.
Lema 3.1.5 [Elliot et al.1995] diag
diag
diag
dan | | diag
diag
,
di mana diag(z) merupakan matriks diagonal yang unsur diagonalnya adalah vektor z.
Bukti: .
dan Karena
. ,
maka
diag diag
diag(
diag
diag .
diag( ■
20
Lema 3.1.6 [Elliot et al.1995] diag
diag
diag
dan | ] diag
diag
,
di mana diag(z) merupakan matriks diagonal yang unsur diagonalnya adalah vektor z.
Bukti: dan
.
Karena , maka
diag diag
diag(
diag
diag
diag( ■
.
Sehingga didapat model hidden Markov Elliot et al. (1995) dalam waktu diskret dengan ukuran peluang P pada ruang state S sebagai berikut: , di mana
,
untuk
(3.5)
, A dan C merupakan matriks peluang transisi dengan dan
,
21
yang memenuhi
dan
∑
1,
0
∑
1,
0,
memenuhi: |
|
0, |
0 diag
|
diag
diag
diag
.
3.2 Perubahan Ukuran 3.2.1 Teorema Bersyarat Bayes Teorema 3.2.1 Teorema Bersyarat Bayes [Elliott et al.1995] Misalkan Ω, , dan
merupakan ruang peluang,
merupakan submedan-
dari
merupakan ukuran peluang lain yang kontinu absolut terhadap P dengan Λ. Jika
turunan Radon-Nikodym
adalah sebarang peubah acak
terintegralkan dan terukur- , maka berlaku |
[ |
|
.
Bukti: Menurut definisi 2.1.22 harus ditunjukkan: (i)
| |
Karena Λ| syarat
terukurΛ|
terukur- , dan maka
Λ dengan syarat
merupakan nilai harapan dari
Λ|
fungsi terukur- , maka
Λ|
yang merupakan nilai harapan dari Λ dengan
terukur- . Karena | |
maka
terukur- .
| |
merupakan pembagian
22
Λ| Λ|
|
(ii)
|
Definisikan
,
|
0
|
maka
,
untuk
Λ|
0
, untuk
Λ|
0
. Jadi
,
terukur- .
Akan ditunjukkan |
Ambil
,
.
sebarang. :
Misal Λ|
Λ|
0 , sehingga
0
Λ
dan Λ
. Maka dari definisi 2.1.22, 0, sehingga
0 atau Λ
0
hampir pasti di G. :
Selanjutnya mana
Λ|
0 , maka dapat dituliskan
di
, sehingga
dan |
Λ Λ
Λ
Karena Λ
0 hampir pasti pada Λ
0
.
Selanjutnya | | | |
Λ
, maka
| |
.
(3.6)
23
|
Λ
|
|
|
Λ|
|
Λ| Λ Λ
,
maka Λ
0
.
Sehingga persamaan (3.6) menjadi
Λ
Λ
Λ | . Jadi |
,
|
.
■
Lema 3.2.2 [Elliott et al.1995] Jika {
merupakan barisan peubah acak yang bisa diintegralkan, maka |
Bukti: Serupa dengan bukti Teorema 3.2.1
| |
.
24
3.2.2 Perubahan Ukuran Perubahan ukuran peluang diperoleh dengan mengubah ukuran peluang asal menjadi peluang baru yang kemudian diinterpretasikan kembali ke dalam peluang asal. Perubahan ukuran ini dibatasi oleh turunan Radon-Nikodym. Ω,
Di bawah ukuran P pada dibangkitkan •
X
,
dan
adalah medan-
yang
berlaku:
merupakan
rantai
Markov
, dan •
yang |
,
homogen
merupakan peubah acak yang bergantung pada
terhadap P. Misalkan
memenuhi
0. |
di mana
pada Ω,
Akan dikontruksikan suatu peluang baru
dan
ukuran peluang baru pada Ω,
0
dan
. yang kontinu absolut yang dibatasi oleh
turunan Radon-Nikodym
(3.7)
Λk . Definisikan
∏
,
(3.8)
dan Λ
di mana
1, 0,
∏
,
. Jadi
(3.9)
adalah fungsi tak linear dari
sehingga dapat
ditulis
∑
.
(3.10)
Lema 3.2.3 [Elliott et al.1995] |
1.
(3.11)
25
Bukti: Berdasarkan definisi (3.8) dan (3.10), diperoleh ∏
|
∑ ∑ 1 1
1
1
1
1|
1
1
1
1|
1
1
∑ 1 ∑
1
1
1
1
1
11
1.
Lema 3.2.4 [Elliott et al.1995] Di bawah
,
,
, merupakan peubah acak yang bebas stokastik identik
yang menyebar seragam dengan peluang 1
pada masing-masing , 1
.
.
Akan dibuktikan :
Bukti: Dengan sifat ,
|
,
| | 1
,
dan menggunakan nilai harapan di bawah ukuran peluang Lema 3.2.3, maka 1
Λ
|
,
[
1,
1
Λ Λ
|
1| 1
Λ
,
1, 1|
|
, Lema 3.2.2 dan
26
Λ
1,
1
Λ
|
1|
,
|
,
|
(3.12)
berdasarkan (3.11) dan (3.12), diperoleh 1|
|
,
∏
,
∑
| ,
,
|
|
| 1
1
1 .
1
Karena
1, maka
,
. Sehingga 1
1
Sehingga di bawah ukuran •
merupakan
pada Ω,
rantai
•
akan berlaku:
Markov
, dan
■
.
yang
|
homogen
dan
memenuhi
0.
Y merupakan barisan peubah acak diskret dengan
,
,
,
yang bersifat bebas stokastik identik dan menyebar seragam dengan untuk •
dan
saling bebas.
1,2,
,
.
27
Lema 3.2.5 [Elliot et al. 1995] |
0.
Bukti: Berdasarkan Persamaan (3.1), diperoleh |
|
,
| 0.
■
Lema 3.2.6 [Elliot et al. 1995] |
0.
Bukti: Berdasarkan Lema 3.2.5 diperoleh, |
| |
,
| |
0| 0.
■
Akan dikontruksi kembali ukuran peluang P pada Ω, absolut pada
yang kontinu
Λ sehingga di bawah P,
dengan turunan Radon-Nikodym
model (3.5) dipenuhi yaitu: •
merupakan
•
rantai
Markov
dan
|
,
homogen
yang
memenuhi
0. |
di mana
merupakan peubah acak yang bergantung pada
0 dan
.
Misalkan dan ,
,
, jadi ∑
1.
(3.13)
28
Untuk menentukan P dari
dan Λ yang merupakan invers dari
didefinisikan
dan Λ , yaitu ∏
,
∏
Λ dan
Λ .
dimana
1
(3.14)
,
(3.15) ,
(3.16)
Lema 3.2.7 [Elliott et al.1995] 1.
(3.17)
Bukti: 1
∑ ∑
1|
1
1|
1
∑
1
∑ 1
|
1|
1
∑ 1.
■
Lema 3.2.8 [Elliott et al.1995] Di bawah ukuran P,
|
.
Bukti: Dengan menggunakan Lema 3.2.2 1|
,
|
29
Λ
1,
1
Λ Λ
|
1| 1,
1
Λ
1
|
1,
1 1
| |
,
|
(3.18)
berdasarkan (3.17) dan (3.18) diperoleh 1|
|
, ∏
|
,
,
|
,
|
|
, (
,
1|
1 . Sehingga berdasarkan notasi 3.1.4 dapat ditulis,
| Dengan
. , maka
■
|
0.
Sehingga persamaan observasinya dapat ditulis .
3.3 Pendugaan Rekursif Untuk melakukan pendugaan parameter, maka dibentuk suatu pendugaan rekursif dari state, banyaknya lompatan, lamanya waktu kejadian dan proses observasi. Pada pembahasan sebelumnya
merupakan filtrasi yang dibangkitkan oleh
30
,
,
,
dan
dan
,
,
,
Dari
subbab
,
,
. 3.2,
di
bawah
, di mana {
,
merupakan filtrasi yang dibangkitkan oleh
ukuran
Ω,
pada
pada ( ,
berlaku
memenuhi 1
1
bebas stokastik identik dengan
, serta
|
0, dan
dan
saling
bebas. Definisikan |
,
Λ
untuk 1
,
,
sehingga ∑
∑
Λ Λ ∑ Λ |
,
|
,
|
.
(3.19)
Lema 3.3.1 [Elliot et al. 1995] ,
Untuk
,
,
maka
Λ
|
|
,
,
,
Bukti: Λ
|
,
∑
Λ
∑
Λ
∑
Λ
| | ,
Λ
,
, ,
|
.
■
Notasi 3.3.2 Jika
,
merupakan barisan peubah acak bernilai skalar yang
terintegralkan, dinotasikan [Λ
|
.
(3.20)
31
Dengan menggunakan Lema 3.2.2 dan persamaan (3.20) maka Λ
|
Λ
.
(3.21)
Sebagai nilai awal 1.
, di mana Misalkan 1
1,1, … ,1
. Maka ∑
,1
1.
,
Akibatnya ,1
Λ
|
Λ
,1 |
,1
,1 |
Λ
,1 ) ,1 ) . Jika
(3.22)
1 maka dari (3.19), (3.20) dan (3.22) diperoleh 1
,1 |
Λ
,1
,1 |
Λ [Λ ∑ Misalkan proses
.
;
bernilai skalar dan adapted terhadap
memenuhi , ∑
, ,
, ,
, ,
,
, 0,
serta
32
, {
di mana bernilai skalar,
,
,
adalah proses predictable terhadap
merupakan vektor berdimensi N, dan
,
merupakan vektor
berdimensi M.
,
Notasi 3.3.3 Jika proses
adapted terhadap , dinotasikan |
Λ
,
.
Notasi 3.3.4 Untuk penyederhanaan dinotasikan ∏
.
Teorema 3.3.5 [Elliot et al. 1995] Untuk 1
,
dengan
,
,
matriks
dan
matriks
, maka
,
,
adalah kolom ke-j dari
,
adalah kolom ke-j dari
,
∑
,
Λ
diag
,
,
,
|
,
.
Bukti: (Lampiran 1)
3.3.1 Penduga untuk State Dengan menggunakan Teorema 3.3.5 dan Lema 3.2.6, ambil 1, ,
1
0, maka penduga untuk state didefinisikan ,
diag
1
0
,
Λ
,
0, 0|
,
33
∑
,
∑
,
.
Jadi 1
,
∑
,
.
(3.23)
Bentuk pendugaan rekursif untuk nilai harapan tak ternormalkan dari ,
disebut unnormalized smoother, jika diketahui ,
1. Bentuk ini ,
dapat diperoleh dengan mengambil
,
,
1, 1
0, maka dengan menggunakan Teorema 3.3.5 diperoleh ∑
,
,
Λ
diag ∑
0
,
0|
,
,
,
0,
,
.
.
Jadi ∑
,
,
,
.
(3.24)
3.3.2 Pendugaan Banyaknya Lompatan ke state
Banyaknya rantai Markov berpindah dari state didefinisikan sebagai berikut: ,
=∑
, maka
Dengan menggunakan =∑
.
,
,
∑
, ,
,
,
, ,
,
,
, ,
,
, ,
, ,
) ,
sampai waktu ke-k
34
,
,
,
,
,
.
,
Dan dengan menggunakan Teorema 3.3.5 dan Lema3.2.6 dapat didefinisikan ,
∑
,
Λ
diag ∑
|
,
,
,
diag ∑
|
Λ ,
Ambil
|
Λ
,
diag
,
,
,
,
Λ
,
,
,
,
|
.
,
,
0,
,
,
,
,
,
0,
sehingga diperoleh ,
∑
Λ
diag ∑
∑
,
,
Λ
∑
Λ ,
Λ ,
∑
Λ ,
diag
Λ ,
,
,
,
,
,
,
,
,
,
|
,
,
,
|
,
|
, ,
,
}
,
|
,
,
diag ∑
,
,
diag
,
,
,
diag ∑
|
∑
diag
,
,
,
,
,
,
,
0,
,
|
,
,
diag
|
,
Λ
,
}
,
35
∑
,
,
,
,
,
,
,
,
,
,
diag ∑ diag ∑
.
Jadi ,
∑
Jika
1
,
,
,
diketahui, maka bentuk
unnormalized smoother untuk
|
Λ
,
(3.25)
adalah
.
,
Ambil
.
0,
maka dengan menggunakan
Teorema 3.3.5 diperoleh ∑
,
,
,
.
(3.26)
3.3.3 Pendugaan Lamanya Waktu Kejadian banyaknya kejadian rantai Markov X
Misalkan 1
berada pada state
,
, sampai waktu ke-k didefinisikan ∑
,
∑
,
, .
,
Dengan menggunakan Teorema 3.3.5, penduga untuk waktu kejadian dapat didefinisikan ,
∑ diag
,
,
,
Λ
,
|
,
36
∑
,
,
Λ
diag ∑
|
,
Λ ,
Untuk
|
Λ
,
diag
,
,
,
|
,
0,
.
,
,
,
,
,
0, diperoleh
,
∑ diag ∑
, ,
,
∑
,
,
,
,
,
∑
,
,
,
∑
∑
,
,
∑
,
,
,
0,
,
0|
,
Λ
|
,
Λ
,
,
,
,
,
,
,
,
.
Jadi ∑
,
jika diketahui
Bentuk unnormalized smoother untuk ,
Ambil
,
,
,
.
(3.27)
.
adalah
0, maka dengan menggunakan
,
Teorema 3.3.5 diperoleh ∑
,
.
,
,
(3.28)
3.3.4 Pendugaan untuk Proses Observasi ,1
,1
berada pada state
Banyak kejadian
, dan
berada pada state
, sampai waktu ke-k, didefinisikan ∑
,
,
, 1
, 1
maka ∑ ∑
, ,
, ,
,
,
,
37
,
, ,
.
,
Dengan menggunakan Teorema 3.3.7 dan Lema 3.3.2, dapat didefinisikan ,
∑
,
Λ
diag ∑
,
diag ,
Λ
Λ |
,
0,
,
Untuk
| ,
diag
,
,
,
,
Λ
∑
|
,
,
,
,
,
|
,
,
.
0,
,
diperoleh
,
∑
,
Λ
diag
,
Λ
,
|
,
,
0|
∑
,
Λ
∑
,
Λ
∑
,
∑
Λ
∑
,
,
|
,
,
|
,
,
,
,
,
, ,
|
,
,
, ,
Λ
0
,
,
∑
,
,
∑
,
,
∑
,
,
|
,
∏
,
,
, ,
,
, ,
.
Jadi ,
∑
,
,
,
,
.
(3.29)
,
38
Bentuk unnormalized smoother untuk 1
,
dan memilih
0, maka dengan menggunakan Teorema 3.3.7
,
diperoleh ∑
,
.
,
,
(3.30)
3.4 Pendugaan Parameter Pendugaan parameter model Hidden Markov dilakukan dengan pendugaan ulang parameter. Metode yang digunakan adalah algoritme EM dan hasilnya berupa parameter dalam bentuk pendugaan rekursif.
3.4.1 Maksimum Likelihood ,
Misalkan Ω,
Θ adalah himpunan ukuran peluang yang terdefinisi pada
dan kontinu absolut terhadap
. Misalkan
, fungsi Likelihood yang
digunakan untuk menghitung penduga parameter
berdasarkan informasi
adalah | dan
Maximum
Likelihood
arg max
, (MLE)
Estimation
didefinisikan
oleh
.
3.4.2 Expectation Maximization Langkah-langkah Excpectation Maximization (EM) adalah: 1. Set nilai awal parameter 2. Set
=
dan hitung ,
3. Cari 4.
=
arg max
0.
, dengan .,
dengan |
log ,
.
.
Ganti k dengan k+1 dan ulangi langkah ke 2 sampai langkah ke 4 hingga kriteria pemberhentian tercapai.
39
Parameter yang digunakan pada model (3.5) adalah ,1
,
,
,1
, 1
.
Akan ditentukan parameter baru dengan menggunakan algoritme EM ,1
,
, ̂
,1
, 1
.
3.4.3 Pendugaan Parameter Notasi 3.4.3.1 Untuk proses
,
ini mendefinisikan
|
, ditulis
. Dalam waktu diskret, kondisi
-optional projection. dengan
Untuk menggantikan parameter
pada rantai Markov
didefinisikan oleh
∏
,
,
∏
, Λ
,
Λ .
dan
Lema 3.4.3.2 [Elliot et al. 1995] , maka
dan misalkan
Di bawah ukuran peluang ,
|
.
Bukti: ,
1, Λ 1 Λ 1 1, Λ 1 Λ 1
|
Λ
1,
Λ
1 1
1,
1 1
1, ∏
∏
,
1
,
1,
1 1,
, ,
,
40
1,
∏
∏
1,
1 1,
1
1,
∑
∑
1,
1 1,
1 1,
∑
1,
1 1,
∑
1,
1 1,
∑
1,
1 ∑
∑
∑
1
,
1
1
1
1
,
1
karena
∑
∑
1
∑
1
∑
1
1
,
1, maka ,
|
.
■
Teorema 3.4.3.3 [Elliot et al. 1995] Penduga baru untuk parameter
pada waktu pengamatan
.
diberikan oleh (3.31)
41
Bukti: log ∏
log Λ
di mana
,
∏
∑
,
∑
∑
,
∑
,
log
∑
,
log
,
bebas terhadap ∑ ∑ ∑
,
∑
,
∑
,
∑
log
log
log ∑
log
,
, ∑
dengan
log
,
, sehingga
log
,
|
log
,
memenuhi ∑
Untuk
,
log
logΛ |
,
,
|
|
log log
.
(3.32)
1 dengan
,
∑
∑
∑
∑
∑
1
∑
,
(3.33) dan ∑
.
,
(3.34)
yang memaksimumkan persamaan (3.32) sebagai fungsi
Akan ditentukan
objektif dengan persamaan (3.34) sebagai fungsi kendala. Dengan menggunakan pengali lagrange diperoleh ,
∑
,
Turunan pertama terhadap diperoleh
∑
log
dan , serta
.
,
0 dan
0 sehingga
42
0 0
∑
(3.35)
0
,
∑
.
,
(3.36)
Dari persamaan (3.35) diperoleh 0
.
(3.37)
Substitusikan persamaan (3.37) ke persamaan (3.36) ∑
,
∑
,
∑
,
∑
,
1
∑
1
∑
∑
1
∑
∑
1
∑
1
∑
,
,
,
∑
, ,
1
1, sehingga
, 1
,
optimum bila 1
0
,
43
. Jadi
.
.
3.4.4 Penduga Parameter ̂ Untuk mengganti parameter
∏
dengan ̂ ,
̂
∏
,
pada matriks , didefinisikan , Λ
∏
dan
Λ .
Lema 3.4.4.1 [Elliott et al.1995] dan misalkan
Di bawah ukuran |
,
̂
=
, maka
.
Bukti: ,
|
,
|
, | , ∏
,
∏
∑
,
∏
1,
1,
∑ 1,
1, 1,
1,
∏
∏ ,
,
∏
44
1, 1,
∑
1, 1,
∑ ∑ ∑
,
1
∑
,
1 1
∑
1
∑
,
∑
karena ∑ ̂
1, maka |
,
̂
.
Teorema 3.4.4.2 Penduga maksimum likelihood untuk parameter ̂ waktu pengamatan
diberikan oleh ̂
.
Bukti: log Λ
log ∏
∏
∑
∑
∑
∑
∑
∑
∑
log ̂
∑
∑
log ̂
,
∏ , log ̂
log ̂
,
,
log
log ∑
∑ ,
log
pada
45
di mana
̂
bebas terhadap
∑
dengan
∑
log
,
sehingga ∑
log Λ
1∑
∑ ∑
1∑
1∑
∑
log ̂
1
1log
| ̂
∑
log ̂
memenuhi ∑
Untuk ̂
|
log ̂
1
,
̂
(3.38)
1,
maka ∑
∑
∑
̂
,
∑
∑
∑
∑
∑
1
∑
,
̂
̂
sehingga ∑
∑ ̂
.
(3.39) ̂
Dengan menggunakan pengali lagrange, dapat ditentukan
yang
memaksimumkan persamaan (3.38) sebagai fungsi objektif dengan persamaan (3.39) sebagai fungsi kendala, sehingga diperoleh .
̂,
∑
∑
∑
log ̂
Dengan menggunakan turunan pertama terhadap ̂
∑
dan , serta
̂
̂
.
0 dan
0 sehingga diperoleh 0
̂
̂
0. ̂
∑
∑ ∑
̂ ∑
(3.40)
̂
0 .
(3.41)
46
Dari persamaan (3.40) diperoleh 0 ̂
. ̂
Substitusikan persamaan (3.42) ke persamaan (3.41) ∑
∑
∑
∑ ∑
̂
∑ ∑
1
∑
∑
1
∑
1
∑
1
1,
,
∑
1
∑
1
∑
1
1,
,
∑
1
∑
1
∑
,
1
1
1, sehingga ̂
, 1
, 1 ̂
optimum bila 1
0
̂
.
Jadi ̂
.
(3.42)
47
3.5 Nilai Harapan adalah
Nilai Penduga terhadap
| ∑
|
∑
∑
,
∑
∑
|
∑
∑
|
∑
∑
| |
.
3.5 Algoritme Pendugaan Parameter Diketahui parameter model berbentuk ,1
,
,
,1
, 1
.
Akan ditentukan parameter baru ,1
,
, ̂
,1
, 1
,
yang memaksimumkan pseudo-loglikelihood bersyaratnya. Algoritme untuk menduga parameter tersebut diperoleh dari Setiawaty dan Kristina (2005) dengan beberapa penambahan langkah sebagai berikut:.
Langkah 1: Tetapkan N (banyaknya state penyebab kejadian), T (banyaknya data) dan input data
.
Langkah 2: Untuk N = 1 sampai dengan kriteria terpenuhi, maka tentukan nilai awal untuk:
dengan
dan memenuhi
dan ∑
1.
48
Langkah 3: Lakukan untuk
1 sampai dengan .
1 Tetapkan nilai awal untuk proses pendugaan : vektor unit di 0 0 0. 2
Lakukan untuk
0 sampai dengan
1
a. Hitung penduga rekursif smoother ∑
,
,
∑
,
,
.
,
∑
,
,
.
∑
,
,
.
,
,
,
.
di mana ∏ ,
, 1 dengan 1 b. Hitung penduga parameter 1 ̂
1
.
c. Tuliskan 1 . 1 dari
d. Tentukan 1
1
e. Ulangi a sampai dengan d untuk k berikut.
1 .
1,1, … ,1
.
49
3.
Berikan nilai 1 1 1
4.
.
Ulangi 1 sampai 3 untuk l berikutnya.
Langkah 4 Hitung nilai
∑
∑
.
Langkah 5 Hitung nilai
1
∑ ∑
2 2
.
Langkah 6 Untuk
1 sampai dengan T cetak
.
50
BAB IV APLIKASI MODEL HIDDEN MARKOV DISKRET PADA DNA Pada Bab ini dijelaskan mengenai DNA cendawan pada spesies Aspergillus niger [http://www.ncbi.nlm.gov/ 06/05/2009] sebagai data input yang digunakan
sebagai data pengamatan dan akan dibahas aplikasi model Hidden Markov diskretnya. Untuk memudahkan perhitungan dan analisis data, dibuat program komputasi berbasis pemprograman fungsional menggunakan Mathematica 7.0.
4.1 DNA Sebagai Materi Genetik DNA Asam deoksiribonukleat, lebih dikenal dengan DNA (deoxyribonucleic acid), adalah sejenis asam nukleat yang tergolong biomolekul utama penyusun berat kering setiap organisme. Di dalam sel, DNA umumnya terletak di dalam inti sel. Secara garis besar, peran DNA di dalam sebuah sel adalah sebagai materi genetik; artinya, DNA menyimpan cetak biru bagi segala aktivitas sel. Ini berlaku umum bagi setiap organisme. Di antara perkecualian yang menonjol adalah beberapa jenis virus (dan virus tidak termasuk organisme) seperti HIV (Human Immunodeficiency Virus). DNA merupakan molekul paling terkenal saat ini, sebab molekul ini merupakan substansi penurunan sifat. Faktor-faktor turunan Mendel dan gen-gen Morgan mengenai kromosom sesungguhnya tersusun dari DNA dan dapat disimpulkan bahwa DNA merupakan bahan dasar penyusun gen.
Struktur DNA Serangkaian studi genetik yang dikombinasikan dengan studi kimia, telah membawa kepada kesimpulan bahwa material genetik disusun oleh asam nukleat, yaitu Asam deoksiribonukleat (DNA) atau Asam Ribonukleat (RNA). Asam Deoksiribonukleat merupakan molekul kompleks yang dibentuk oleh 3 macam
51
molekul, yaitu 1
gula pentosa (deoksiribosa)
2
fosfat (PO −4 )
3
basa nitrogen, terdiri dari a. purin: Guanin(G) dan Adenin(A) b. pirimidin: Timin(T) dan Sitosin(C)
DNA terbentuk dari empat tipe nukleotida, yang berikatan secara
kovalen
membentuk rantai polinukleotida (rantai DNA atau benang DNA) dengan tulang punggung gula-fosfat tempat melekatnya basa-basa. Dua rantai polinukleotida saling berikatan melalui ikatan hidrogen antara basa-basa nitrogen dari rantai yang berbeda. Semua basa berada di dalam double helix dan tulang punggung gulafosfat berada di bagian luar. Purin selalu berpasangan dengan pirimidin (A-T, GC). Perpasangan secara komplemen tersebut memungkinkan pasangan basa dikemas dengan susunan yang paling sesuai. Hal ini bisa terjadi bila kedua rantai polinukleotida tersusun secara antiparalel. Erwin Chargaff (Campbell et al. 2002) menganalisis komposisi basa DNA dari sejumlah organisme yang berbeda. Pada tahun 1947. Ia melaporkan bahwa komposisi DNA berbeda-beda antara satu spesies dengan spesies lainnya. Dalam DNA dari spesies apa pun yang dipilih, banyaknya keempat basa nitrogen ini tidaklah sama tetapi hadir dalam rasio yang khas. Chargaff juga menemukan adanya keteraturan yang agak ganjil dalam rasio dari basa-basa nukleotida ini. Dalam DNA setiap spesies yang dipelajarinya, jumlah adenin kurang lebih sama dengan jumlah timin, dan jumlah guanine kurang lebih sama dengan jumlah sitosin. Sebagai
contoh
pada
DNA
manusia,
keempat basa ini
hadir
dalam persentase: A= 30,9% dan T=29,4%; G=19,9% dan C=19,8%. Kesamaan A=T dan G=C, yang kemudian dikenal sebagai aturan Chargaff, baru dapat dijelaskan setelah ditemukannya untai ganda.
52
A
B
Gambar 1 Pembentukan secara skematik struktur dsDNA dari gula fosfat sebagai backbone dan basa nukleotida (A). Bentuk skematik double-helix DNA (B).
Struktur untaian (helix) DNA ditentukan oleh tumpukan (stacking) basa-basa nukleotida berdekatan yang ada pada satu untai, sedangkan struktur untai gandanya ditentukan oleh ikatan hidrogen antara basa-basa yang berpasangan.
4.2 Data input DNA Data yang digunakan merupakan sebagian dari data komplit DNA pada cendawan aspergillus niger. Data yang diamati ada sebanyak 1000 basa nitrogen sebagai berikut
1 ccaccaaggg ttccattacc tccgtccagg ccgtctacgt ccctgctgac gatttgactg 61 accctgcccc cgccaccacc ttcgctcact tggacgccac cactgtcttg tcccgtggta 121 tctccgagtt gggtatctac cctgccgtcg accctctcga ctccaagtcc cgtatgctcg 181 acacccgtat cgtcggtgaa gaccactaca acaccgccac ccgtgtccag cagatgctcc 241 aggagtacaa gtccctccag gatatcattg ccattctggg tatggacgaa ctgtctgagg 301 ctgacaagct taccgtcgag cgtgctcgta agctccagcg tttcctgtcc cagcccttca 361 ccgtcgccca ggtcttcact g gtatcgagg gtaagctggt cgacctgaag gacaccatcc
53
421 gcagtttcaa ggccatcatc a acggtgaag gtgacgacct cctgagggt aagttgatct 481 ctccactttc t gtttggtga tc ggcatgga tgctaatttg tttatctaca gctgctttct 541 acatggttgg tgacttcgag tctgcccgcg ccaagggtga gaagatcttg gccgagctcg 601 agaacaaggc ctaaatgtaa tattgttttt aagcgccctt ttcctttttt gttagacatg 661 gacttccttt cttccatgtg ccgttttcta ccgatccgtg tacagtactc gaattgagaa 721 aagggagttg aaagaaaggc gaggtccccc ctatataaaa ggatgagagc gctcttaacg 781 tacacctctc tgaaagtctg gatggaaact tctagacttg tgttacacta cgtgctcatg 841 taagtaagtt aaaatgacca cagtcagcct gatacccgct gggctgggac aattgtactc 901 aaatttcctt tgttgaaccg ggggaccgtg atatctgttg cgtagacatt cctgtagcat 961 gtaatctgta agattccaaa cgagccatac gtcccttcta Sumber:[ http://www.ncbi.nlm.gov/ 06/05/2009] Keterangan: dari data di atas, 1, 61, 121,… menyatakan urutan ke- k urutan basa nitrogen.
4.3 Aplikasi Model Hidden Markov Diskret pada DNA Barisan DNA mengalami perubahan pada setiap urutannya. Sampai saat ini penyebab perubahannya tidak diketahui, namun penyebab tersebut diasumsikan sebagai state yang tidak diamati. Untuk menjelaskan perilaku urutan basa nitrogen pada cendawan spesies Aspergillus niger, dibangun suatu model stokastik. Ide memilih model Hidden Markov diskret Elliot et al. 1995 untuk masalah ini diperoleh dari Jamal (2008). Data yang diamati dan dimodelkan pada model Hidden Markov diskret [Elliot et al. 1995] hanya sebagian dari barisan DNA lengkap pada spesies Aspergillus niger, dengan banyaknya data T = 1000 dan k menyatakan urutan DNA. Pada komputasi, basa nitrogen c, g,t, dan a diubah menjadi c=1,g=2,t=3, dan a=4. Diasumsikan bahwa barisan DNA pada spesies Aspergillus niger dibangkitkan oleh proses pengamatan yang hanya dipengaruhi oleh proses penyebab kejadian yang membentuk rantai Markov dan tidak diamati secara langsung. Faktor-faktor yang menyebabkan terjadinya perubahan keteraturan DNA diasumsikan sebagai state dari suatu rantai Markov
. Pada setiap state, urutan DNA dibangkitkan
54
oleh peubah acak Ω, ,
yang menyebar dengan sebaran tertentu pada ruang peluang
. Misalkan hubungan antara
dan
ditentukan oleh persamaan
(3.5), yaitu , untuk
.
Berdasarkan asumsi bahwa penyebab perubahan DNA tidak diamati secara
tersembunyi (hidden) di balik data pengamatan
langsung, sehingga proses . Jadi pasangan
,
merupakan model Hidden Markov diskret [Elliot et
al. 1995] dengan parameter model di atas berbentuk :
,1
,
,
,1
, 1
.
Dengan menggunakan data di atas, parameter model diduga dengan menggunakan metode maximum likelihood dan pendugaan ulang menggunakan metode expectation maximization yang melibatkan perubahan ukuran. Penduga rekursif yang dilakukan pada penelitian ini adalah penduga smoother dengan N = 2.
4.4 Hasil Komputasi Dari algoritme di atas dibuat program berbasis pemograman fungsional menggunakan software Mathematica 7.0. Hasil run dan interpretasi model sebagai berikut
55
Kasus urutan DNA dengan banyak penyebab kejadian N = 2 4
Data duga Yi
3
2
28%
30%
21%
26%
25%
1
26%
30%
26%
28%
24%
28%
25%
19%
25%
24%
23%
0 0
1
2 Data Asli
3 Yi
4
: Y i = Yi
Gambar 2 Grafik distribusi nilai dugaan urutan DNA menggunakan penduga smoother untuk 2 penyebab kejadian (N = 2). Banyaknya data, ⎛ 0.16 0.26 ⎞ ⎜ ⎟ ⎛ 0.31 0.66 ⎞ ⎜ 0.09 0.02 ⎟ dan T = 1000. Nilai awal A0 = ⎜ , C = ⎟ 0 ⎜ 0.40 0.43 ⎟ ⎝ 0.69 0.34 ⎠ ⎜ ⎟ ⎝ 0.35 0.29 ⎠ ⎛ 0.49 ⎞ π0 = ⎜ ⎟. ⎝ 0.51 ⎠
56
Kasus urutan DNA dengan banyak penyebab kejadian N = 2 4
47%
data duga Yi
3
21%
2
17%
1
15%
44%
45%
13%
16%
12%
16%
24%
28%
23%
21%
2
3
15%
43%
0 0
1
data Asli
4
Yi
: Y i = Yi
Gambar 3 Grafik distribusi nilai dugaan urutan DNA menggunakan penduga smoother untuk 2 penyebab kejadian (N = 2). Banyaknya data, ⎛ 0.37 0.20 ⎞ ⎜ ⎟ 0.27 0.02 ⎟ ⎛ 0.37 0.35 ⎞ ⎜ T = 1000. Nilai awal A0 = ⎜ ⎟ , C0 = ⎜ 0.26 0.33 ⎟ ⎝ 0.63 0.65 ⎠ ⎜ ⎟ ⎝ 0.10 0.45 ⎠ ⎛ 0.50 ⎞ dan π 0 = ⎜ ⎟. ⎝ 0.50 ⎠ Dari grafik terlihat hasil komputasi yang menunjukkan distribusi nilai harapan model yang dihasilkan. Garis dengan
persamaan Y i = Yi merupakan penduga
model yang diharapkan pada Yi ∈ {1, 2,3, 4} .
Dari Gambar 1 dan Gambar 2, terlihat bahwa model menghasilkan distribusi penduga yang berbeda. Ini dapat dilihat dari titik-titik yang merupakan hasil
(
perhitungan komputasi berupa pasangan titik Yi , Y i
)
dengan Yi , Y i ∈ {1, 2,3, 4} .
Pada Gambar 1, terlihat 26% tepat muncul nilai harapan untuk data 1, 28% tepat
57
muncul nilai harapan untuk data 2, 26% tepat muncul nilai harapan untuk data 3 dan 28% tepat muncul nilai harapan untuk data 4. Pada Gambar 2, terlihat 15% tepat muncul nilai harapan untuk data 1, 15% tepat muncul nilai harapan untuk data 2, 16% tepat muncul nilai harapan untuk data 3 dan 43% tepat muncul nilai harapan untuk data 4. Ini berarti, pada Gambar 1, rata-rata model dapat menduga dengan tepat sebesar 27% dan pada Gambar 2, rata-rata model dapat menduga dengan tepat sebesar 22.25% . Model Hidden Markov Elliott dicirikan oleh parameter-parameternya yang berupa matriks peluang transisi. Dari kedua gambar di atas, untuk penyebab kejadian dan banyaknya data yang sama, menghasilkan nilai harapan model yang berbeda. Hasil yang diperoleh masih belum cukup baik, karena belum diperoleh cara untuk menentukan nilai awal yang paling baik. Oleh sebab itu perlu dikaji penentuan nilai awal yang terbaik untuk memperoleh hasil yang optimal. .
BAB V KESIMPULAN DAN SARAN
5.1 Kesimpulan Dari hasil penelitian dapat diambil kesimpulan sebagai berikut 1.
Model Hidden Markov diskret (Elliot et al. 1995) telah dikaji dan diimplementasikan pada urutan DNA.
2.
Dalam pendugaan parameter, hasil yang diperoleh sangat bergantung pada penentuan nilai awal. Hasil yang diperoleh belum cukup baik karena belum ditemukan cara untuk menentukan nilai awal terbaik agar hasilnya optimal.
5.2 Saran Dengan memperhatikan hasil penelitian ini, disarankan perlu adanya kajian untuk penentuan nilai awal pada proses komputasi.
DAFTAR PUSTAKA
Agresti A, Finlay B. 1999. Statistical Methods for the Social Sciences. Prentice Hall. New Jersey. Anton H, Rorres C. 2004. Aljabar Elementer. Versi Aplikasi. Erlangga. Jakarta. Bachtiar IS. 2007. Aplikasi Pengenalan Wicara HMM untuk Kendali Robot PDA. ITS Surabaya. Billingsley P. 1986. Probability and Measure. John Willey & Sons. New York. Bulla, Berzel. 2008. Computational Issues in Parameter Estimation for Stationary Hidden Markov Models. California. Campbell NA, Reece JB, Mitchell LG. 2002. Biologi. Edisi kelima-Jilid 1. Erlangga. Jakarta Casella G, Berger RL. 1990. Statistical Inference. Wadsworth & Brooks/Cole, Pasific Grove. California. Celeux, Durand. 2008. Selecting Hidden Markov Model state number with CrossValidated Likehood. New York. Elliott RJ, Aggoun L dan Moore JB. 1995. Hidden Markov Model. Estimation and Control. Spriger-Verlag. New York. Ghahramani S. 2005. Fundamentals of Probability. Second Edition. Prentice Hall. New Jersey. Grimmet GR, Stirzaker DR. 2001. Probability and Random Processes. Clarendon Press. Oxford. Hadi. 2005. Pengenalan Karakter Mandarin Secara On-Line dengan Menggunakan Hidden Markov Models. ITS. Surabaya. Hasymi. 1996. Sistem Pengenalan Bicara dengan Menggunakan Sistem Hidden Markov Model. ITB. Bandung. Hermanto. 2007. Penerapan Hidden Markov Model dalam Prediksi Gen Organisme Prokariotik. ITB. Bandung. Hoog RV, McKean JW, Craigg AT. 2005. Introduction to Mathematical Statistics. Prentice Hall, Engelwood Cliffs. New Jersey. http://www.ncbi.nlm.gov/ 06/05/2009
Irfani A. 2007. Algoritma Viterbi dalam Metode HMM pada Teknologi Speech Recognition. ITB. Bandung. Jamal. 2008. Kajian Model Hidden Markov Diskret dan Aplikasinya pada Harga Gabah Kering Panen. [Tesis]. IPB. Protter P. 1995. Stochastic Integration Differential Equations. Springer-Verlag. New York. Ross SM. 1996. Stochastic Processes. John Wiley & Sons. New York. Setiawaty B, Kristina L. 2005. Pendugaan Parameter Model Hidden Markov. Jurnal Matematika dan Aplikasinya 4: 23-39. Shreve SE. 2004. Stochastic Calculus for Finance I. Springer-Verlag. New York. Wibisono. 2008. Penggunaan Hidden Markov Model untuk Kompresi Kalimat. ITB. Bandung.
LAMPIRAN
61
Lampiran 1 Bukti Teorema 3.3.5 Teorema 3.3.5 [Elliot et al. 1995] Untuk 1
,
dengan
matriks
,
dan
,
,
,
,
adalah kolom ke-j dari adalah kolom ke-j dari matriks
, maka ,
∑
1
1
Λ
,
,
1
1
1,
1
1,
1
,
diag
.
Bukti:
,
) Λ
|
Λ
,
,
|
,
,
Λ
|
,
,
Λ
|
.
(1)
Berdasarkan Teorema 2.1.25, dan Lema 3.2.6 maka suku pertama dari sebelah kanan pada persamaan (1) diperoleh ,
,
, ,
Λ
|
,
Λ
|
Λ
|
|
,
Λ
Λ
, ,
|
|
Λ
|
,
Λ
|
|
Λ
|
62
Λ
|
|
, Λ
Λ |
Λ
Λ
|
Λ
|
|
,
|
|
,
.
(2)
Berdasarkan Teorema 2.1.25, Lema 3.1.5 dan Lema 3.2.6 maka suku kedua dari sebelah kanan dari persamaan (1) diperoleh ,
, ,
Λ ,
,
Λ
|
Λ
| ,
| |
|
|
|
|
Λ
,
|
|
Λ
,
|
|
Λ
,
|
|
Λ
|
|
Λ
|
|
|
|
Λ
|
Λ
Λ
,
Λ
,
|
| Λ
,
Λ
.
(3)
Substitusikan persamaan (2) dan (3) ke persamaan (1) ,
,
Λ
,
Λ ,
|
Λ
|
Λ Λ
| |
63
,
,
Λ
,
,
,
,
Λ
,
,
Λ
Λ
1
1
1
,
,
1
1
Λ
1,
1
1
1
1
1
,
,
Λ
Λ
,
,
,
Λ
,
,
Λ
,
|
Λ
,
,
Λ
1
,
,
Λ
,
Λ
Dari Lema 3.1.5, Definisi 2.3.3 dan Teorema 2.1.26, diperoleh
,
1
4
64
Λ
,
,
Λ
,
Λ
,
|
Λ
|
Λ
Λ
,
Λ
Λ
Λ
|
|
|
Λ
|
|
,
Λ
|
|
,
Λ
|
,
,
,
| ,
Λ
|
Λ
|
| ,
,
|
,
Λ
,
Λ
,
Λ Λ ,
,
|
diag
|
|
,
,
|
,
,
|
Λ
|
Λ
,
Λ
|
, |
,
Λ
| |
,
,
Λ
|
,
diag
, ,
Λ Λ
Λ Λ
|
,
,
|
,
,
,
Λ
,
|
,
|
,
|
,
65
,
,
,
diag
Λ
,
,
Λ
,
Λ
,
,
,
,
,
,
|
,
,
,
|
,
diag
diag
,
,
|
.
68
Lampiran 4 Tabel nilai harapan model dari Program 1 k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
Y 4 2 1 4 2 4 4 4 1 3 3 3 3 1 2 1 3 1 4 3 3 1 4 3 3 3 1 1 1 2 2 4 3 4 1 2 2 4 4 2 1 3 3 4 3 4 1 1 4 1
Yduga 4 4 4 1 4 2 2 1 1 4 1 3 3 4 1 1 2 3 3 1 1 1 2 4 4 4 1 3 4 2 1 1 1 1 4 1 4 3 4 3 2 1 1 2 4 3 4 2 1 4
k 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
Y 4 2 4 4 2 4 2 4 3 1 3 3 1 4 4 2 2 2 2 4 3 3 3 2 1 4 2 4 3 4 1 1 2 1 3 3 1 1 4 3 3 4 2 4 4 2 4 3 3 4
Yduga 4 1 1 3 1 2 4 2 4 2 1 1 2 4 1 2 4 3 2 1 3 2 3 2 2 4 1 2 1 3 2 1 3 3 3 3 3 1 1 4 1 1 3 4 4 2 2 2 3 3
k 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150
Y 1 3 2 1 4 3 1 2 2 3 1 1 3 4 3 3 3 1 3 2 1 4 1 2 2 1 4 2 3 3 1 3 2 2 1 4 1 2 2 1 2 4 3 1 2 4 4 2 3 2
Yduga 3 4 4 1 4 4 4 1 2 3 4 4 4 1 1 2 1 3 2 1 1 4 2 3 1 1 1 4 2 1 3 2 1 1 1 2 2 4 2 4 2 1 1 1 1 4 1 4 2 1
k 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
Y 1 4 4 1 3 4 4 2 4 3 1 2 4 3 1 2 3 2 2 3 1 1 1 3 2 3 2 4 2 3 3 2 2 3 3 1 3 2 4 2 2 4 3 3 1 1 3 4 3 4
Yduga 2 2 4 1 1 3 4 3 2 4 2 1 2 4 4 2 4 1 3 4 2 4 3 3 3 1 4 1 2 1 2 3 2 2 2 4 3 3 2 2 2 4 4 4 2 1 1 3 2 2
69 k 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250
Y 2 1 3 2 2 4 4 4 4 4 1 4 3 1 3 3 4 1 1 4 3 3 2 3 2 4 1 4 2 2 2 1 3 1 3 1 2 1 1 1 4 4 1 2 4 3 3 2 1 3
Yduga 3 3 3 3 2 1 3 2 1 2 4 4 4 3 1 4 3 3 4 2 1 4 1 3 3 2 2 1 1 1 4 1 1 1 3 1 3 2 4 4 1 4 1 1 4 2 1 3 2 4
k 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300
Y 3 3 4 1 4 3 1 1 2 1 3 2 1 3 1 2 1 1 2 4 2 3 2 4 1 1 2 1 1 3 2 1 4 3 4 3 3 2 1 4 4 1 4 3 2 1 4 4 4 4
Yduga 2 3 2 4 2 1 2 2 2 4 3 3 3 3 4 2 3 1 2 3 1 2 4 4 1 2 1 3 1 4 2 4 2 1 3 1 2 3 1 4 3 4 2 3 3 3 2 4 4 4
k 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350
Y 1 1 1 1 2 4 1 1 4 1 2 4 4 2 3 4 1 4 3 1 3 4 1 3 3 1 1 3 4 1 1 4 1 3 1 4 2 4 3 4 3 1 2 4 4 1 1 2 3 1
Yduga 3 4 1 1 1 4 1 4 1 2 4 3 4 2 2 3 2 1 4 1 1 4 1 4 2 4 1 1 4 1 2 4 4 4 4 3 4 1 1 2 4 4 4 1 4 3 2 4 4 1
k 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400
Y 2 2 4 4 3 4 3 4 1 1 3 1 4 1 3 1 1 3 1 3 1 2 2 4 4 3 3 1 1 3 2 4 4 4 1 3 3 2 1 1 1 1 3 3 1 2 3 3 2 2
Yduga 1 1 1 4 4 2 3 3 1 1 2 3 3 3 1 3 4 4 4 4 1 4 4 3 4 1 3 2 1 1 2 3 1 4 3 3 4 1 2 1 2 1 1 3 2 2 2 4 2 3
70 k 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450
Y 3 4 1 1 4 4 1 4 4 4 1 1 1 4 2 4 1 1 4 3 4 1 3 3 1 3 1 1 1 4 3 3 1 3 2 1 2 4 1 4 3 1 1 2 2 4 1 3 3 2
Yduga 4 3 3 2 4 1 1 4 4 2 4 2 4 4 4 2 4 1 4 4 4 2 4 2 3 3 1 4 3 4 4 3 3 4 4 4 1 1 1 4 3 1 2 3 2 4 4 3 1 3
k 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500
Y 4 4 3 1 3 2 4 4 1 4 4 1 4 3 1 3 3 2 4 3 4 2 1 2 1 1 1 4 4 3 3 1 1 2 1 4 4 4 2 4 3 3 2 1 3 4 2 3 4 3
Yduga 2 1 4 1 3 3 1 3 4 4 3 4 1 3 4 3 1 3 4 1 1 2 4 2 2 2 2 3 2 4 3 3 3 1 4 2 4 3 1 4 3 1 4 3 3 1 2 2 2 1
k 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550
Y 1 4 3 4 2 4 3 3 2 2 1 4 2 2 4 3 4 2 3 4 3 1 4 3 1 3 3 1 1 1 2 1 3 1 3 3 1 4 3 2 1 4 2 2 1 4 2 2 1 3
Yduga 4 1 3 3 3 1 1 4 3 4 3 3 4 4 2 4 2 3 2 2 3 3 4 1 2 4 3 2 2 1 2 1 3 3 4 2 2 2 4 1 4 4 2 2 2 3 3 1 1 2
k 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600
Y 4 3 1 1 4 2 1 1 3 3 3 3 2 1 2 4 2 1 4 3 2 4 3 3 1 2 3 1 2 4 4 2 4 1 3 1 4 4 4 2 1 3 3 4 1 4 2 4 3 3
Yduga 4 3 1 4 1 2 4 3 2 4 4 1 2 1 1 3 1 2 1 1 1 1 3 4 3 3 1 2 2 4 2 4 2 3 3 2 3 3 1 4 3 4 3 1 3 2 4 1 4 4
71 k 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650
Y 1 1 4 3 1 1 1 3 1 1 1 4 2 4 3 4 1 3 3 3 3 3 1 1 4 4 3 4 3 2 4 2 1 4 3 1 2 4 2 2 4 4 1 4 2 4 3 2 2 4
Yduga 3 1 3 3 3 4 3 4 1 4 3 4 2 4 3 1 1 4 3 4 3 4 1 1 3 3 3 4 2 2 4 2 1 1 3 4 4 3 4 2 4 2 1 2 2 4 1 4 2 1
k 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700
Y 4 2 1 4 4 4 4 2 1 3 2 4 4 3 3 3 1 2 3 3 1 1 2 4 2 2 4 4 2 1 4 4 4 3 1 3 1 3 4 1 3 1 1 4 1 4 2 1 4 2
Yduga 2 1 2 3 1 1 1 2 2 1 3 1 1 4 2 3 3 4 2 3 2 3 4 2 2 1 2 3 4 2 3 1 3 4 3 4 4 2 1 3 1 2 1 2 2 3 4 2 2 1
k 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750
Y 1 3 4 1 3 2 2 2 3 3 2 3 4 3 4 4 3 2 4 3 4 3 1 1 4 1 3 2 2 4 2 1 4 1 1 3 3 2 4 4 2 4 3 1 1 1 2 3 4 1
Yduga 3 4 1 3 2 4 3 4 3 1 2 3 4 3 3 2 4 4 2 4 3 4 4 4 2 1 4 4 2 3 3 1 2 2 4 3 4 2 4 1 3 4 2 3 4 4 3 1 3 4
k 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800
Y 1 3 3 2 2 1 4 3 2 1 2 4 1 4 1 3 4 3 1 3 2 3 4 3 1 4 4 1 4 4 4 1 4 2 2 2 3 4 1 1 1 3 3 2 2 2 4 3 2 2
Yduga 4 3 1 3 2 2 3 2 3 4 1 2 1 3 2 1 3 1 2 2 2 3 3 4 2 3 1 4 1 4 4 4 1 1 4 3 2 3 3 1 1 2 4 1 2 1 3 4 4 3
72 k 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850
Y 4 2 4 3 2 3 1 4 3 3 4 4 1 1 3 3 1 2 3 2 1 3 2 2 3 1 3 3 2 3 3 2 1 3 4 3 1 4 1 4 4 1 4 3 1 2 1 4 1 2
Yduga 2 3 2 3 2 2 2 3 3 1 2 2 3 2 2 1 1 4 3 4 2 3 2 2 1 3 2 2 2 4 1 3 4 3 2 4 2 4 1 1 1 4 4 3 1 3 2 1 3 4
k 851 852 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700
Y 3 1 3 2 2 4 2 3 4 4 1 4 3 3 4 1 4 3 1 2 2 4 4 3 2 1 3 2 3 1 1 2 2 3 2 4 1 2 3 3 1 3 1 3 2 4 3 1 4 4
Yduga 3 4 4 3 1 2 2 3 3 2 1 1 1 3 4 1 4 2 3 1 4 4 4 4 1 3 1 3 1 4 3 2 1 3 3 3 2 2 4 4 2 1 4 4 3 3 4 1 2 4
k 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950
Y 2 4 2 1 2 4 1 2 2 4 1 4 2 1 4 4 3 2 2 4 2 2 4 2 3 1 4 4 4 3 2 4 2 3 2 2 4 4 3 2 4 2 3 1 1 2 4 2 2 4
Yduga 1 2 1 4 4 3 2 4 1 4 3 2 1 2 4 4 1 2 2 1 2 1 2 3 4 4 1 4 1 4 3 3 3 1 1 3 3 2 2 2 4 3 2 3 4 3 3 2 3 4
k 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001
Y 4 1 3 1 1 3 4 4 1 3 4 3 1 4 3 1 4 2 2 4 4 1 2 4 1 3 3 4 2 2 3 4 3 3 2 4 1 1 1 1 2 4 4 2 2 3 2 2 3 4
Yduga 3 1 4 4 2 2 1 4 1 4 3 3 4 4 2 1 4 4 1 3 4 4 2 4 4 2 1 3 3 3 1 3 3 2 2 2 2 4 4 2 3 4 3 4 3 3 2 1 1 3 4
83
Lampiran 5 Tabel nilai harapan model dari Program 2 k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
Y 4 2 1 4 2 4 4 4 1 3 3 3 3 1 2 1 3 1 4 3 3 1 4 3 3 3 1 1 1 2 2 4 3 4 1 2 2 4 4 2 1 3 3 4 3 4 1 1 4 1
Yduga 4 4 4 2 4 1 2 4 2 4 1 3 4 3 1 2 4 4 2 4 1 3 3 4 4 4 4 3 4 4 3 2 2 4 3 4 4 2 4 2 4 4 1 4 4 4 1 4 4 4
k 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
Y 4 2 4 4 2 4 2 4 3 1 3 3 1 4 4 2 2 2 2 4 3 3 3 2 1 4 2 4 3 4 1 1 2 1 3 3 1 1 4 3 3 4 2 4 4 2 4 3 3 4
Yduga 1 1 1 2 4 1 4 4 4 4 4 4 4 3 4 3 4 2 4 1 4 4 4 4 4 4 3 2 2 2 4 4 1 4 4 4 1 4 4 1 3 4 4 2 4 2 3 3 2 1
k 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150
Y 1 3 2 1 4 3 1 2 2 3 1 1 3 4 3 3 3 1 3 2 1 4 1 2 2 1 4 2 3 3 1 3 2 2 1 4 1 2 2 1 2 4 3 1 2 4 4 2 3 2
Yduga 4 3 4 4 1 4 4 1 1 4 4 4 1 1 3 1 3 3 1 4 3 4 2 4 4 2 2 4 4 2 4 1 1 4 2 1 1 1 4 4 3 4 4 1 1 2 4 1 1 2
k 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
Y 1 4 4 1 3 4 4 2 4 3 1 2 4 3 1 2 3 2 2 3 1 1 1 3 2 3 2 4 2 3 3 2 2 3 3 1 3 2 4 2 2 4 3 3 1 1 3 4 3 4
Yduga 1 4 4 3 1 4 4 1 2 4 4 2 4 1 4 1 4 1 4 4 1 2 2 4 1 2 1 2 4 3 3 4 4 2 4 3 4 4 4 3 4 4 2 4 2 4 4 3 4 4
84
Lanjutan k 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250
Y 2 1 3 2 2 4 4 4 4 4 1 4 3 1 3 3 4 1 1 4 3 3 2 3 2 4 1 4 2 2 2 1 3 1 3 1 2 1 1 1 4 4 1 2 4 3 3 2 1 3
Yduga 4 3 2 1 1 4 1 4 4 4 4 1 1 4 1 4 1 4 1 4 1 4 3 1 4 2 2 4 1 4 2 2 4 2 2 3 4 2 1 2 3 4 4 1 2 1 4 4 4 3
k 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300
Y 3 3 4 1 4 3 1 1 2 1 3 2 1 3 1 2 1 1 2 4 2 3 2 4 1 1 2 1 1 3 2 1 4 3 4 3 3 2 1 4 4 1 4 3 2 1 4 4 4 4
Yduga 4 2 2 1 4 1 3 4 1 4 4 3 3 2 4 1 4 1 1 4 4 4 2 2 2 1 1 1 4 4 2 4 2 2 2 4 3 4 2 2 3 4 4 4 1 2 4 4 4 3
k 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350
Y 1 1 1 1 2 4 1 1 4 1 2 4 4 2 3 4 1 4 3 1 3 4 1 3 3 1 1 3 4 1 1 4 1 3 1 4 2 4 3 4 3 1 2 4 4 1 1 2 3 1
Yduga 1 1 1 1 2 4 1 1 4 1 2 4 4 2 3 4 1 4 3 1 3 4 1 3 3 1 1 3 4 1 1 4 1 3 1 4 2 4 3 4 3 1 2 4 4 1 1 2 3 1
k 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400
Y 2 2 4 4 3 4 3 4 1 1 3 1 4 1 3 1 1 3 1 3 1 2 2 4 4 3 3 1 1 3 2 4 4 4 1 3 3 2 1 1 1 1 3 3 1 2 3 3 2 2
Yduga 4 2 2 4 4 2 3 3 3 3 1 4 1 4 1 3 1 1 4 4 1 1 4 1 4 4 1 1 4 1 4 1 4 4 1 4 3 4 4 3 2 4 3 4 3 1 2 1 3 4
85
Lanjutan k 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450
Y 3 4 1 1 4 4 1 4 4 4 1 1 1 4 2 4 1 1 4 3 4 1 3 3 1 3 1 1 1 4 3 3 1 3 2 1 2 4 1 4 3 1 1 2 2 4 1 3 3 2
Yduga 4 4 2 3 1 1 3 1 4 2 4 1 1 4 1 4 2 4 1 1 3 3 4 3 4 3 4 4 1 1 2 1 4 4 4 4 4 4 2 4 4 4 4 4 2 2 2 1 4 3
k 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500
Y 4 4 3 1 3 2 4 4 1 4 4 1 4 3 1 3 3 2 4 3 4 2 1 2 1 1 1 4 4 3 3 1 1 2 1 4 4 4 2 4 3 3 2 1 3 4 2 3 4 3
Yduga 3 2 4 2 3 4 1 3 3 1 1 4 4 4 4 1 1 1 4 1 3 3 2 4 4 3 4 4 4 4 3 3 3 4 1 4 3 1 4 2 4 4 3 4 1 4 4 1 2 3
k 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550
Y 1 4 3 4 2 4 3 3 2 2 1 4 2 2 4 3 4 2 3 4 3 1 4 3 1 3 3 1 1 1 2 1 3 1 3 3 1 4 3 2 1 4 2 2 1 4 2 2 1 3
Yduga 3 3 1 1 4 4 2 3 4 1 1 2 2 4 2 4 2 2 2 4 4 3 4 1 3 3 3 3 1 1 1 4 4 3 3 4 4 3 1 3 3 4 1 2 4 2 1 2 4 4
k 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600
Y 4 3 1 1 4 2 1 1 3 3 3 3 2 1 2 4 2 1 4 3 2 4 3 3 1 2 3 1 2 4 4 2 4 1 3 1 4 4 4 2 1 3 3 4 1 4 2 4 3 3
Yduga 3 3 1 1 4 4 2 3 4 1 1 2 2 4 2 4 2 2 2 4 4 3 4 1 3 3 3 3 1 1 1 4 4 3 3 4 4 3 1 3 3 4 1 2 4 2 1 2 4 4
86
Lanjutan k 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650
Y 1 1 4 3 1 1 1 3 1 1 1 4 2 4 3 4 1 3 3 3 3 3 1 1 4 4 3 4 3 2 4 2 1 4 3 1 2 4 2 2 4 4 1 4 2 4 3 2 2 4
Yduga 3 4 2 4 4 4 4 4 4 3 3 1 3 4 1 4 4 4 4 4 3 3 1 3 4 1 1 4 3 4 2 2 2 2 1 4 4 4 4 1 4 4 2 4 3 4 4 4 4 1
k 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700
Y 4 2 1 4 4 4 4 2 1 3 2 4 4 3 3 3 1 2 3 3 1 1 2 4 2 2 4 4 2 1 4 4 4 3 1 3 1 3 4 1 3 1 1 4 1 4 2 1 4 2
Yduga 3 4 2 4 4 4 4 4 4 3 3 1 3 4 1 4 4 4 4 4 3 3 1 3 4 1 1 4 3 4 2 2 2 2 1 4 4 4 4 1 4 4 2 4 3 4 4 4 4 1
k 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750
Y 1 3 4 1 3 2 2 2 3 3 2 3 4 3 4 4 3 2 4 3 4 3 1 1 4 1 3 2 2 4 2 1 4 1 1 3 3 2 4 4 2 4 3 1 1 1 2 3 4 1
Yduga 1 2 1 4 1 2 1 3 4 4 3 3 3 1 4 4 1 4 2 4 4 4 4 2 4 4 3 4 4 1 4 4 4 1 3 1 1 2 2 4 4 2 2 4 4 4 4 4 2 4
k 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800
Y 1 3 3 2 2 1 4 3 2 1 2 4 1 4 1 3 4 3 1 3 2 3 4 3 1 4 4 1 4 4 4 1 4 2 2 2 3 4 1 1 1 3 3 2 2 2 4 3 2 2
Yduga 4 4 4 4 2 3 4 2 3 4 2 2 2 3 4 4 4 3 4 3 1 4 1 2 1 1 4 4 4 1 1 4 4 1 4 4 1 2 4 2 1 2 4 1 4 2 2 4 3 2
87
Lanjutan k 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850
Y 4 2 4 3 2 3 1 4 3 3 4 4 1 1 3 3 1 2 3 2 1 3 2 2 3 1 3 3 2 3 3 2 1 3 4 3 1 4 1 4 4 1 4 3 1 2 1 4 1 2
Yduga 3 2 2 1 2 2 2 1 2 2 3 4 1 3 4 4 4 3 1 2 2 4 4 1 4 3 4 2 1 4 3 1 3 1 4 2 3 4 4 4 1 4 2 4 1 1 3 1 4 1
k 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900
Y 3 1 3 2 2 4 2 3 4 4 1 4 3 3 4 1 4 3 1 2 2 4 4 3 2 1 3 2 3 1 1 2 2 3 2 4 1 2 3 3 1 3 1 3 2 4 3 1 4 4
Yduga 4 1 4 1 3 1 2 3 4 2 3 3 4 4 4 4 3 1 3 3 4 3 3 4 4 3 3 3 4 3 1 1 2 4 4 1 1 1 4 2 4 3 3 1 1 2 2 2 1 1
k 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950
Y 2 4 2 1 2 4 1 2 2 4 1 4 2 1 4 4 3 2 2 4 2 2 4 2 3 1 4 4 4 3 2 4 2 3 2 2 4 4 3 2 4 2 3 1 1 2 4 2 2 4
Yduga 4 2 3 4 4 3 2 1 4 4 4 4 1 2 1 4 4 3 2 3 2 4 4 4 4 4 4 1 4 2 4 2 4 2 1 1 2 2 3 4 4 4 2 3 4 2 4 4 4 1
k 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001
Y 4 1 3 1 1 3 4 4 1 3 4 3 1 4 3 1 4 2 2 4 4 1 2 4 1 3 3 4 2 2 3 4 3 3 2 4 1 1 1 1 2 4 4 2 2 3 2 2 3 4
Yduga 1 4 2 4 4 3 1 4 4 2 3 4 4 1 3 2 4 4 1 2 4 4 2 4 4 4 2 3 4 4 4 2 2 4 4 2 3 4 4 2 4 4 1 3 1 4 1 2 4 4 1
