Author(s): Hizkia J. Branch
Awalnya diterbitkan di Menuju AI.
Hai semuanya! Saya kembali dengan artikel fantastis lainnya 😄
Jika Anda mengikuti saya di LinkedIn atau platform lain, Anda mungkin tahu bahwa saya mengikuti program sarjana teknik. Sepanjang jalan, saya telah mempelajari banyak topik menarik yang ingin saya bagikan dengan Anda semua.
Topik yang ingin saya fokuskan kali ini adalah rantai Markov. Rantai Markov sangat populer di sejumlah bidang, termasuk biologi komputasi, pemrosesan bahasa alami, peramalan deret waktu, dan bahkan analitik olahraga. Kita dapat menggunakan rantai Markov untuk membuat Model Markov Tersembunyi (HMM), model prediktif yang berguna untuk data temporal.
Jika Anda baru mengenal konten saya, ketahuilah bahwa tutorial saya lebih berfokus pada konsep daripada pembuktian. Saya mencoba yang terbaik untuk mengubah topik rumit menjadi nugget yang mudah dicerna.
Dan berbicara tentang nugget yang dapat dicerna, saya memperkenalkan Rantai Markov.
Panas terik musim panas menguasai Boston awal 1990-an. Di dalam apartemen Egleston Anda, suara WCVB-TV terdengar dari televisi RCA kecil. Anda tidak percaya pada unit AC jendela sehingga jendela Anda tetap retak dengan pintu freezer terbuka. Entah dari mana, sebuah amplop kuning meluncur di bawah pintu depan Anda, diikuti dengan kaki yang bergerak cepat. Anda menunggu suara pintu tertutup sebelum mengambil amplop dengan hati-hati. Anda telah dipekerjakan sebagai penyelidik swasta untuk menyelesaikan hilangnya pejabat terpilih terkemuka. Secara kebetulan, Anda sudah melacak kasus ini selama beberapa waktu. Anda berjalan ke papan bukti Anda dan, sekali lagi, mencoba menghubungkan titik-titik tersebut. Untuk beberapa alasan, itu terlihat seperti rantai …
Rantai Markov, dinamai menurut ahli matematika Rusia Andrey Markov, digunakan untuk memodelkan urutan keadaan, dengan mengandalkan probabilitas perpindahan dari satu keadaan ke keadaan berikutnya. Istilah “keadaan” dapat mewakili sejumlah objek dunia nyata, termasuk kata-kata, pola cuaca, film Netflix, apa saja. Model ini mengasumsikan data diurutkan dalam beberapa cara (yaitu, data berurutan). Rantai Markov mengasumsikan bahwa keadaan dapat diamati. Jika beberapa dari status ini tidak dapat diamati (yaitu, tersembunyi), kami akan menggunakan HMM. Cukup umum untuk menyebut semua status rantai Markov sebagai Q.
Kuis cepat:
Jika kita memiliki rantai Markov yang terdiri dari huruf-huruf alfabet Inggris, berapa banyak negara bagian yang kita miliki?
Solusi: Jawaban yang benar adalah 26! Dalam hal ini, kami memiliki status untuk masing-masing dari 26 huruf alfabet.
Jika keadaan kita adalah hal-hal yang dapat kita hitung dengan jari kita (seperti contoh yang kami cantumkan di atas), kita menggunakan istilah rantai Markov. Jika kita tidak dapat menghitungnya dengan jari kita (yaitu, kontinu), kita menggunakan istilah proses Markov.
Asumsi utama di balik model Markov adalah bahwa kita dapat memprediksi keadaan berikutnya hanya dengan menggunakan keadaan kita saat ini. Asumsi “tanpa ingatan” ini disebut Asumsi Markov. Jurafsky dan Martin (2021) memberikan Asumsi Markov sebagai:
Status berbeda dari rantai Markov kita adalah q1, …, qi-1 di mana qi-1 adalah status terbaru kita dalam rantai tersebut. Seperti yang kita pelajari sebelumnya, semua keadaan ini membentuk Q.
Asumsi Markov di atas adalah distribusi probabilitas bersyarat.
Distribusi probabilitas bersyarat adalah bagaimana kita mengukur probabilitas bahwa suatu variabel mengambil beberapa nilai ketika kita memiliki pengetahuan tentang beberapa variabel lain.
Seperti distribusi probabilitas apa pun:
Probabilitas tidak boleh negatif Probabilitas harus berjumlah 1 Ruang probabilitas adalah jumlah dari bagian-bagian yang terpisah
Contoh Dunia Nyata
Katakanlah Anda bekerja sebagai analis produk di Disney+. Anda mungkin ingin mengukur probabilitas bahwa seri Marvel baru akan diperbarui, mengingat variabel lain seperti peringkat rata-rata, jumlah penonton mingguan, biaya produksi, dll. Untuk menemukan probabilitas ini, Anda memerlukan distribusi probabilitas bersyarat.
Sekarang jika kita melihat ekspresi untuk Asumsi Markov, Anda akan melihat bahwa probabilitas bersyarat kami tidak berubah saat kami memperhitungkan status tambahan sebelumnya. Ungkapan ini adalah contoh bagus tentang kemandirian versus eksklusivitas timbal balik.
Ketika kita berbicara tentang kemandirian, kita mengatakan bahwa pengetahuan kita tentang variabel lain tidak “memperbarui” cara berpikir kita tentang variabel yang kita minati. Ini berbeda dengan saling eksklusif, di mana dua hal tidak dapat terjadi pada waktu yang bersamaan.
Kuis cepat:
Biarkan A mewakili apa yang terakhir Anda makan untuk sarapan, dan B mewakili apa yang terakhir saya makan untuk sarapan. Apakah A dan B independen, saling eksklusif, keduanya, atau tidak keduanya?
Solusi: Jika Anda mengatakan A dan B independen tetapi tidak saling eksklusif, Anda benar! Pilihan sarapan kami tidak bergantung satu sama lain karena apa yang saya makan tidak memengaruhi apa yang saya makan. Namun, mereka belum tentu saling eksklusif karena kita mungkin makan sarapan pada waktu yang sama. Istilah-istilah ini sering membingungkan, tetapi penting untuk mengetahui perbedaan antara keduanya.
Jika kita memiliki rantai Markov dengan distribusi bersyarat yang independen dari semua kecuali keadaan terbaru, kita akan menyebutnya rantai Markov orde pertama. Jika probabilitas bersyarat tidak bergantung pada semua kecuali 2 status terbaru, kami akan memiliki rantai Markov orde kedua. Jika probabilitas bersyarat tidak bergantung pada semua kecuali 3 status terbaru, kami akan memiliki rantai Markov orde ketiga, dan seterusnya.
Organisasi model rantai Markov berdasarkan nomor urut
Setelah kami memilih rantai Markov kami, kami perlu menentukan bagaimana kami berpindah dari satu keadaan ke keadaan berikutnya. Setiap keadaan memiliki probabilitas transisi, yang mewakili probabilitas bahwa kita pindah ke keadaan tertentu.
Kami menyimpan semua probabilitas transisi ini dalam matriks transisi A.
Kolom dan baris matriks mewakili keadaan rantai Markov kita. Kolom matriks transisi A membentuk distribusi probabilitas, sehingga nilai setiap kolom harus berjumlah 1. Ini berarti bahwa semua sisi dalam rantai Markov kita yang meninggalkan keadaan juga harus berjumlah 1. Menariknya, jika setiap baris dan setiap kolom dari A jumlah 1, kita sebut A ganda stokastik.
Contoh matriks stokastik ganda
Perhatikan bagaimana dalam matriks stokastik ganda di atas, Anda dapat menyeret jari Anda melintasi setiap baris atau setiap kolom dan selalu berakhir dengan nilai 1. Namun, untuk rantai Markov, kita hanya memerlukan kolom untuk dijumlahkan menjadi 1. Ini adalah disebut kolom stokastik. Matriks seperti ini disebut matriks stokastik kiri. Rantai Markov dibiarkan stokastik tetapi tidak harus stokastik ganda.
Proses Markov (kasus kontinu) dapat memiliki jumlah kolom atau baris menjadi 1. Namun, artikel ini hanya membahas tentang rantai Markov.
Kuis cepat
Di bawah ini, kami memiliki contoh dua rantai Markov yang diusulkan. Berdasarkan apa yang baru saja kita pelajari, apakah gambar kiri atau kanan adalah rantai Markov yang sebenarnya?
Periksa akhir posting ini untuk jawaban yang benar.
Karena Asumsi Markov adalah “tanpa memori”, memiliki representasi negara yang bermakna sangat penting untuk keberhasilan model kami.
Waktu Aktivitas: Mari Membuat Rantai Markov!
Temukan selembar kertas terdekat dan tulis nama karakter TV favorit Anda. Buat rantai Markov menggunakan huruf dari nama karakter sebagai status dalam rantai Markov Anda. Pastikan untuk menambahkan probabilitas transisi untuk edge antar state.
Posting gambar rantai Markov Anda dan matriks transisi yang sesuai di komentar!
Sejauh ini, kita dapat membuat rantai Markov dan berpindah antar status dalam rantai, tetapi bagaimana kita tahu harus mulai dari mana?
Ini memberi kita persyaratan terakhir untuk rantai Markov, yang disebut distribusi probabilitas awal π. Distribusi ini didefinisikan sebelum “pembelajaran” apa pun terjadi. Anda dapat menganggapnya sebagai titik awal kami yang “tidak mendapat informasi”.
Kami mengalikan π dengan matriks transisi kami A untuk mendapatkan prediksi kami.
Contoh prediksi diberikan oleh MathAdamSpiegler di bawah ini:
Di sini, kita mengalikan matriks transisi 3×3 A dengan distribusi awal 3×1 π untuk mendapatkan prediksi pertama kita. Perhatikan bagaimana prediksi kami pada jumlah paling kanan menjadi 1 (0,41 + 0,475 + 0,115 = 1). Dalam skenario ini, prediksinya adalah persentase suara yang sesuai dengan tiga kandidat politik. Prediksi di atas menunjukkan bahwa Calon 1 memperoleh 41% suara, Calon 2 memperoleh 47,5% suara, dan Calon 3 memperoleh 11,5% suara.
Kami dapat mengulangi proses ini beberapa kali untuk membuat prediksi. Untuk melakukannya, kita menaikkan matriks transisi ke pangkat tertentu dan mengalikannya dengan distribusi awal. Akhirnya, prediksi tersebut hampir tidak akan berubah. Ini disebut distribusi stasioner. Banyak aplikasi rantai Markov berfokus pada pencarian distribusi stasioner. Namun, salah satu batasan dunia nyata dari rantai Markov adalah perlu beberapa saat untuk menemukan distribusi stasioner ini.
Sekarang sebelum kita berangkat, mari lakukan rekap singkat dari apa yang kita pelajari:
Ringkasan
Rantai Markov adalah model yang berguna untuk membuat prediksi pada data sekuensial, khususnya ketika pengamatan sebelumnya tersedia. Prediksi kami, probabilitas bersyarat bahwa keadaan masa depan sama dengan suatu nilai, tidak bergantung pada keadaan masa lalu dari rantai Markov. Komponen rantai Markov adalah keadaan Q, matriks transisi A, dan distribusi probabilitas awal π. Kami membuat prediksi dengan rantai Markov kami dengan mengalikan matriks transisi A dengan distribusi awal π. Jadi, prediksi kami adalah produk yang sama dengan Aπ atau ((A)^k)π di mana k adalah suatu daya. Prediksi jangka panjang dapat didefinisikan dalam hal distribusi stasioner.
Solusi untuk Markov Chain Quick Quiz:
Jika Anda melihat tepi keluar, hanya gambar kiri yang memiliki tepi keluar yang berjumlah 1 untuk setiap status dalam rantai Markov. A memiliki sisi keluar (0,7 + 0,3 = 1), B tidak memiliki sisi keluar, C memiliki sisi keluar (0,5 + 0,4 + 0,1 = 1), dan D memiliki satu sisi keluar (1 = 1) yang juga berfungsi sebagai loop.
Jika Anda mengulangi proses ini untuk citra yang tepat, Anda akan menemukan keadaan dengan sisi keluar yang tidak berjumlah 1. Akibatnya, kita memiliki distribusi probabilitas yang tidak valid.
Jadi, hanya gambar kiri yang merupakan rantai Markov!
Untuk tutorial interaktif, lihat:
(2) Pengantar rantai Markov dengan Python! – Youtube
Lain kali…
PT II: Markov Random Fields (MRFs)
——————————————————————————————————————
Sumber
Pemrosesan Pidato dan Bahasa. Daniel Jurafsky & James H. Martin. Hak Cipta © 2021. Semua hak dilindungi undang-undang. Draf 29 Desember 2021.
Uskup, CM, & Nasrabadi, NM (2006). Pengenalan pola dan pembelajaran mesin (Vol. 4, №4, p. 738). New York: peloncat.
Cap, M. (2004). Pengantar yang mengungkap model Markov yang tersembunyi. Departemen Ilmu Komputer Universitas Negeri San Jose, 26–56.
Rantai Markov — Wikipedia
(2) L24.2 Pengantar Proses Markov — YouTube
Matematika 19b: Aljabar Linier dengan Probabilitas Oliver Knill, Musim Semi 2011 Kuliah 33: Matriks Markov
Probabilitas SticiGui: Aksioma dan Fundamen (berkeley.edu)
(3) MATEMATIKA 3191: Membuat Prediksi Jangka Panjang dengan Markov Chains — YouTube
Panduan Pemula untuk Rantai Markov, Probabilitas Bersyarat, dan Kemandirian awalnya diterbitkan di Towards AI on Medium, di mana orang melanjutkan percakapan dengan menyoroti dan menanggapi cerita ini.
Diterbitkan melalui Menuju AI
