Kalman Filter
Table of Contents
(Reposted from here with some changes)
Kalman Filter merupakan sebuah teknik yang digunakan untuk mengestimasi nilai sebuah parameter atau state dalam suatu waktu tertentu. Variabel waktu di sini merupakan sebuah variabel yang diskrit, yakni jarak antar satu titik waktu dengan titik yang lainnya adalah konstan, dimulai dari 0, 1, 2, … dan seterusnya.
Pada setiap satuan waktu terdapat sebuah state yang nilainya akan diestimasi. State sendiri merupakan kumpulan variabel-variabel yang menentukan kondisi dari sistem yang diukur dalam suatu waktu tertentu. Sebagai contoh, jika kita ingin mengestimasi ketinggian dari sebuah air dalam sebuah bak berbentuk persegi panjang dalam waktu tertentu, kita bisa membuat sebuah state S yang isinya merupakan kumpulan dari ketinggian air pada keempat titik sudut bak tersebut, lalu mengestimasi ketinggian air bak sebagai rata-rata dari keempat nilai pada state nya tersebut. Pada setiap waktu, kita dapat mengukur nilai state ini secara langsung, dan hasil pengukurannya tersebut disebut sebagai measured value.
Akan tetapi, walaupun pengukuran berhasil dilakukan dan nilai state pada tiap satuan waktu dapat diperoleh, nilai yang dihasilkan ini cukup noisy, karena nilai dari setiap komponen state berubah-ubah tiap saat (sistemnya dinamis), dan terdapat ketidakpastian dalam pengukuran. Teknik Kalman Filter digunakan untuk memperoleh taksiran nilai state tersebut dengan meminimalisir noise (faktor ketidakpastian), atau secara formal meminimalisir nilai ekspektasi dari squared-error (atau Mean Square Error, yaitu sebuah metrik yang umum digunakan sebagai error function untuk mengukur akurasi model) dengan memanfaatkan data-data yang diperoleh dari waktu sebelumnya.
Kalman Filter cukup powerful karena dapat mengestimasi nilai state dari past, present, dan future, tanpa perlu mengetahui cara sistem bekerja, serta karena algoritma yang digunakan hanya bergantung pada statistik dari data yang diobservasi. Dalam Kalman Filter digunakan sebuah asumsi, yakni data pengukuran adalah distribusi Gaussian, sehingga noise nya dapat diasumsikan sebagai Gaussian noise. Algoritma ini biasanya digunakan untuk memodelkan sebuah sistem yang dinamis dan linear (Linear Dynamic Systems), yakni sebuah sistem yang dapat dinyatakan sebagai berikut,
di mana x dengan dot merupakan turunan x terhadap waktu, dan x sendiri merupakan sebuah vektor yang menyimpan nilai-nilai parameter pada waktu tertentu (sehingga dapat dianggap sebagai state), dan A merupakan sebuah matriks konstan yang bergantung pada sistem (Karena A konstan, maka sistemnya merupakan sistem linear). Contoh paling sederhana dari sistem seperti ini adalah trajectory sebuah benda yang jatuh bebas (free-fall), dengan state-nya dapat berupa ketinggian, posisi, ataupun kecepatan benda.
Secara umum, proses pada Kalman Filter memakai konsep pemrograman dinamis serta rekursif, yang jika digabung serupa dengan back propagation. Terdapat beberapa tahapan utama dalam algoritma Kalman Filter:
Prediction⌗
Pada tahap ini dilakukan estimasi nilai state pada waktu berikutnya.
Filtering⌗
Pada tahap ini, nilai dari state saat ini (saat t = k) diprediksi berdasarkan nilai estimasi yang diperoleh dari data-data sebelumnya (saat t = k-1, k-2, …, 0). Tentu saja, kondisi awal (t = 0) merupakan sebuah kasus khusus karena merupakan titik awal pengambilan data, sehingga datanya diperoleh dari observasi ataupun sditambah dengan asumsi-asumsi lainnya.
Smoothing⌗
Pada tahap ini, nilai dari state di masa lalu ditaksir ulang berdasarkan data observasi saat ini. Hal ini, sesuai dengan namanya, bertujuan untuk memperhalus nilai prediksi sehingga meminimalisir noise dari hasil prediksi.
Dalam penerapannya, algoritma dalam Kalman Filter melibatkan banyak sekali variabel, yang jika ingin diketahui lebih lanjut dapat dilihat pada tautan berikut.
Namun, secara sederhana kita dapat memandang persamaannya itu sebagai berikut ini:
Dalam hal ini, variabel X(k) merupakan estimasi nilai state pada waktu ke-k, variabel Z(k) merupakan measured value pada waktu ke-k, dan K(k) merupakan nilai dari koefisien Kalman Gain. Nilai koefisien ini lah yang perlu dihitung agar X(k) dapat mengestimasi nilai state lebih baik daripada Z(k), karena jika Z(k) sudah baik, kita mungkin tidak perlu lagi melakukan estimasi lebih lanjut. Estimasi ini dilakukan karena perhitungan Z(k) melibatkan ketidakpastian (noise), dan pada algoritma ini diasumsikan distribusi nilai dari data Z mengikuti distribusi Gaussian.
Selain itu, Kalman Filter disebut juga sebagai predictor-corrector algorithm. Hal ini dapat dilihat sesuai ilustrasi berikut, yang menggambarkan flow dari algoritma Kalman Filter secara sederhana:
Step prediction dilakukan untuk menghitung estimasi nilai state pada waktu berikutnya, sedangkan step correction dilakukan untuk melakukan smoothing serta mencari nilai optimal dari Kalman Gain dengan menggunakan measured value pada saat itu.
Penerapan Kalman Filter⌗
Terdapat banyak penerapan Kalman Filter dari berbagai macam bidang. Secara umum, teknik ini sangat berguna dalam pemodelan sebuah sistem yang dinamis (yakni sistem yang nilai parameternya berubah-ubah seiring waktu), dan hasil pengukuran nilai parameter tersebut dapat memiliki error sehingga menghasilkan noise. Beberapa penerapannya adalah sebagai berikut:
- Sistem kontrol, navigasi dan kendali, seperti pada robot dan rudal.
- Tracking pergerakan objek dan estimasi lokasinya, seperti estimasi ketinggian sebuah spinning spacecraft¹ , estimasi lokasi robot, dan lain-lain. Pada device yang lokasinya * diinformasikan melalui GPS, bisa saja titik lokasi yang ditampilkan oleh GPS memiliki noise, dan Kalman Filter digunakan untuk memberikan estimasi lokasi device dengan lebih baik.
- Pada ekonomi dan quantitative trading, contohnya prediksi permintaan peminjaman international reserve sebuah negara²
- Pada bidang computer vision, seperti feature tracking, cluster tracking, pengukuran fisis (seperti kedalaman atau kecepatan) berdasarkan data dari perangkat seperti kamera, radar, dan lain-lain.
- Prediksi nilai berikutnya pada sebuah time-series
- Beberapa contoh seperti peluncuran Falcon 9 milik SpaceX, dan peluncuran Apollo 8 pada tahun 1968, yakni sebuah human spaceflight pertama yang mengorbit bulan.