BAB I PENDAHULUAN
1.1 Latar Belakang Masalah Dalam kehidupan sehari-hari, sering dijumpai peristiwa-peristiwa yang terjadi secara beruntun dan dengan kemungkinan yang berbeda-beda. Sebagai contoh sekarang ini kondisi perekonomian di negara ini sedang tidak menentu. Setiap hari nilai tukar rupiah terhadap dolar Amerika berubah., Hal tersebut berlanjut untuk harihari berikutnya yang memiliki kemungkinan masing-masing yang berbeda-beda, apakah nilai tukar rupiah terhadap dolar Amerika menguat, tetap, atau melemah. Untuk memperkirakan keadaan nilai tukar rupiah terhadap dolar Amerika yang mungkin terjadi pada hari ini, peristiwa yang telah terjadi di hari sebelumnya dapat dijadikan informasi untuk memperkirakan kemungkinan keadaan tersebut. Rantai Markov (Markov Chain) adalah suatu proses random (proses stokastik) dengan Markov Property di mana dengan keadaan saat ini, keadaan yang akan datang bersifat independen terhadap keadaan yang lampau dan hanya tergantung pada keadaan yang terdekat sebelumnya.
Rantai Markov baru diperkenalkan
sekitar tahun 1906, oleh seorang
matematikawan Rusia bernama Andrey A. Markov (1856-1922). Andrey Markov
1
memperoleh hasil pertama untuk proses ini, mengemukakan teori ketergantungan variabel proses acak yang dikenal dengan proses Markov secara teoritis.
Sebuah proses stokastik dikatakan termasuk Rantai Markov apabila memenuhi sifat Markovian (Markovian property). Markovian property menyatakan bahwa probabilitas bersyarat dari sebuah keadaan (state) di masa yang akan datang dengan diketahui kejadian masa lampau dan keadaan masa kini tidak tergantung oleh kejadian masa lampau dan hanya tergantung oleh keadaan masa kini atau masa sesaat sebelumnya. Ada beberapa syarat agar metode Markov dapat diaplikasikan dalam evaluasi kedalam keadaan sistem. Syarat-syarat tersebut adalah :
1. Jumlah probabilitas transisi untuk suatu keadaan awal dari sistem sama dengan 1. 2. Probabilitas-probabilitas tersebut berlaku untuk semua partisipan dalam sistem. 3. Sistem harus berkarakter lack of memory, dimana kondisi sistem dimasa mendatang tidak dipengaruhi (independent) oleh kondisi sebelumnya. Artinya kondisi sistem saat evaluasi tidak dipengaruhi oleh kondisi sebelumnya, kecuali kondisi sesaat sebelum kondisi saat ini. 4. Sistem harus stationery atau homogen, artinya perilaku sistem selalu sama disepanjang waktu atau peluang transisi sistem dari satu kondisi ke kondisi lainnya akan selalu sama disepanjang waktu.
2
Pada proses stokastik Rantai Markov {Xn} dengan n = 0, 1, 2, ... = |
= ,
=
=
,… ,
=
= |
= )
,
=
=
di mana nilai yang memungkinkan dari i dan j adalah suatu himpunan terhitung yang sering disebut sebagai state space (ruang keadaan). Probabilitas tersebut biasanya dikenal dengan kemungkinan perpindahan state (state transition probability) yang sering dilambangkan dengan simbol
(peluang bahwa proses akan berada di
keadaan j dari keaadaan i) di mana nilai
≥ 0, ∀ , dan nilai ∑
= 1, ∀ =
0,1, … Dengan matriks peluang transisis Pij sebagai berikut : P00 P 10 P= M Pi 0 M
P01 P11 M Pi 0 M
P02 L P12 L M M Pi 0 L M
Rantai Markov bermanfaat untuk menghitung peluang urutan keadaan yang diamati, tetapi terkadang ada urutan peristiwa yang ingin diketahui tetapi tidak dapat diamati. Untuk menyelesaikan permasalahan tersebut, dikembangkanlah model baru yang memodelkan keadaan yang tersembunyi, yaitu Hidden Markov Models.
Hidden Markov Models (HMM) atau Model Markov Tersembunyi adalah sebuah model statistik dari sebuah sistem yang diasumsikan sebuah Markov Process
3
dengan parameter yang tak diketahui, dan tantangannya adalah menentukan parameter-parameter tersembunyi (hidden) dari parameter-parameter yang dapat diamati. Parameter-parameter yang ditentukan kemudian dapat digunakan untuk analisis yang lebih jauh. Dalam sebuah model Markov, semua state dalam suatu barisan yang linear dapat secara langsung diobservasi.
Dalam situasi tertentu, beberapa faktor yang tidak dapat diobservasi mempengaruhi perhitungan perpindahan atau transisi state. Faktor-faktor tersebut dinamakan dengan keadaan yang tersembunyi (hidden states). Setiap state memiliki distribusi probabilitas atas keluaran yang mungkin muncul. Oleh karena itu rangkaian keluaran yang dihasilkan oleh HMM memberikan sebagian informasi tentang barisan state. Nilai probabilitas yang berasosiasi dengan setiap simbol dalam state dinamakan probabilitas emisi (emission probability). Untuk menghitung probabilitas total dari suatu jalur dalam model, baik probabilitas state ataupun probabilitas emisi yang menghubungkan semua keadaan terobservasi dan keadaan yang tidak terobservasi harus dimasukkan ke dalam perhitungan.
Pada dekade terakhir ini metode statisitik HMM semakin populer karena model tersebut kaya akan struktur matematika dan mengandung teori dasar yang bisa digunakan untuk beberapa aplikasi yang penting. Sebuah HMM dikarakteristikkan dengan parameter-parameter sebagai berikut (Rabiner, 1989):
4
π= keadaan awal, N = banyaknya keadaan yang tidak terobservasi, M = banyaknya keadaan terobservasi, A = matriks peluang transisi, B = distribusi peluang observasi pada saat t berada pada keadaan i (matriks emisi).
Dalam Hidden Markov Models ini terdapat tiga masalah utama, yaitu:
1. Evaluasi. Perhitungan probabilitas dari urutan nilai observasi yang diberikan oleh Hidden Markov Models. Menghitung peluang terjadinya suatu barisan observasi. 2. Decoding. Permasalahan decoding ini yaitu menemukan barisan state terbaik (optimal) yang berasosiasi dengan barisan observasi dari sebuah model yang juga telah diketahui. Menentukan keadaan tersembunyi dari suatu barisan observasi. 3. Learning. Melatih parameter HMM jika diberikan data set barisan-barisan tertentu. Penaksiran parameter-parameter dari Hidden Markov Models.
5
Masalah pertama dapat diselesaikan dengan menggunakan algoritma Forward atau algoritma Maju. Masalah kedua diselesaikan dengan menggunakan algoritma Viterbi. Sedangkan masalah ketiga dipecahkan dengan algoritma Baum-welch. Pada karya tulis ini, akan dibahas mengenai penyelesaian masalah pertama pada Hidden Markov Models, yaitu perhitungan peluang terjadinya suatu barisan observasi dengan menggunakan algoritma Forward. Oleh karena itu, tugas akhir ini diberi judul “APLIKASI ALGORITMA FORWARD UNTUK MENGHITUNG PELUANG BARISAN KEADAAN TEROBSERVASI PADA HIDDEN MARKOV MODELS”.
1.2
Rumusan Masalah dan Batasan Masalah Rumusan Masalah Permasalahan yang akan dikaji dalam tugas akhir ini adalah sebagai berikut : 1. Bagaimana penggunaan algoritma forward dalam menghitung peluang barisan dalam keadaan terobservasi pada HMM? 2. Bagaimana penggunaan aloritma forward dalam memperkirakan keadaan harga emas BAPPETI sebagai investasi jangka panjang? Batasan Masalah Tugas akhir ini hanya membahas tentang penggunaan algoritma forward dalam menghitung peluang barisan dalam keadaan terobservasi pada HMM.
6
1.3
Tujuan Penulisan Berdasarkan rumusan masalah di atas, maka tujuan pembuatan tugas akhir ini
adalah sebagai berikut : 1. Mengetahui bagaimana penggunaan algoritma Forward dalam menghitung peluang barisan dalam keadaan terobservasi pada HMM. 2. Mengetahui perhitungan untuk memperkirakan harga emas BAPPETI sebagai investasi jangka panjang.
1.4
Manfaat Penulisan
Hidden Markov Models (HMM) adalah suatu metode penyelesaian masalah secara efektif dan efisien di bidang-bidang yang melibatkan HMM seperti dalam bidang speech recognition atau optical character recognition, machine translation, bioinformatika dan genomik. Melalui tugas akhir ini, akan diperoleh cara perhitungan peluang terjadinya suatu barisan observasi pada keadaan yang terobservasi. Selain itu, penulisan karya tulis ini diharapkan dapat menambah wawasan dan menambah literaratur dalam bidang Statistika, khususnya tentang Hidden Markov Models.
1.5
Sistematika Penulisan Sistematika penulisan meliputi 5 bab, yaitu:
7
•
Bab 1: Pendahuluan Mencakup tentang isi makalah keseluruhan. Meliputi latar belakang, rumusan masalah, batasan masalah, tujuan penulisan, manfaat penulisan dan sistematika penulisan.
•
Bab 2 : Teori Penunjang Menjelaskan tentang teori penujang yang membahas mengenai cara perhitungan peluang terjadinya suatu barisan observasi pada suatu Hidden Markov Models.
•
Bab 3 : Pembahasan Menjelaskan pembahasan mengenai Hidden Markov Models dengan algoritma Forward dalam cara perhitungan peluang terjadinya suatu barisan observasi pada HMM.
•
Bab 4 : Penerapan Penerapan aloritma forward dalam menghitung peluang keadaan harga emas BAPPETI sebagai investasi jangka panjang.
8
•
Bab 5: Bab ini berisi tentang kesimpulan dan saran tentang pembahasan aplikasi algoritma forward untuk menghitung peluang barisan keadaan terobservasi pada HMM.
9
