Jelaskan algoritma Mundur untuk Model Markov Tersembunyi

8

Saya telah mengimplementasikan algoritma Viterbi dan Forward , sayangnya anehnya saya tidak mengerti bagaimana cara kerja algoritma Backward . Secara intuitif saya merasa perlu melakukan hal yang sama seperti di Forward hanya mundur, menggunakan nilai yang dihitung selama propagasi Forward .

Apakah intuisi saya benar?

Saya telah membaca banyak slide dan muak dengan notasi matematika pada saat ini. Itu tidak membantu. Saya butuh sesuatu yang dalam bahasa Inggris menjelaskan perbedaan antara algoritma Backward dan Forward .

Bisakah Anda memberikan penjelasan singkat bagaimana algoritma Backward dilakukan?

Asumsikan HMM kecil berikut dan hasil algoritma Teruskan untuk urutan "BB" di bawah ini:

START -> 1
H: 0.5 * 0.8 = 0.4
L: 0.5 * 0.6 = 0.3

1 -> 2
H: 0.4 * 0.2 * 0.8 + 0.3 * 0.6 * 0.8 = 0.208
L: 0.4 * 0.8 * 0.6 + 0.3 * 0.4 * 0.6 = 0.264

2 -> END
END: 0.208 * 0.3 + 0.264 * 0.7 = 0.2472

masukkan deskripsi gambar di sini

mineral
sumber

Jawaban:

7

Sepertinya urutan pengamatan Anda adalah B, B. Mari kita tunjukkan pengamatan pada waktu sebagai dan status tersembunyi pada waktu sebagai . Jika kita menyatakan sebagai nilai forward dan sebagai nilai backward, ( adalah salah satu kemungkinan status tersembunyi)tzttxtαt(i)βt(i)i

αt(i)=P(xt=i,z1:t)

Ini berarti adalah probabilitas untuk menyatakan pada waktu memancarkan pengamatan hingga waktu . Kemudian,αt(i)itt

βt(i)=P(zt+1:Txt=i) yang merupakan probabilitas memancarkan urutan yang tersisa dari sampai akhir waktu setelah berada dalam keadaan tersembunyi pada waktu .t+1it

Untuk melakukan rekursi pada kita dapat menulis,βt(i)

P(zt+1:Txt=i)=jP(xt+1=j,zt+1:Txt=i)

Menggunakan aturan rantai, P(xt+1=j,zt+1:Txt=i)=P(zt+2:T,zt+1,xt+1=jxt=i)=P(zt+2:Tzt+1,xt+1=j,xt=i)P(zt+1xt+1=j,xt=i)P(xt+1=jxt=i)

Dari independensi bersyarat HMM, probabilitas di atas disederhanakan menjadi P(zt+2:Txt+1=j)P(zt+1xt+1=j)P(xt+1=jxt=i)

Perhatikan bahwa dari definisi kami.P(zt+2:Txt+1=j)=βt+1(j)

Mengganti menjadi kita dapatkan,P(zt+1:Txt=i)

βt(i)=P(zt+1:Txt=i)=jβt+1(j)P(zt+1xt+1=j)P(xt+1=jxt=i)

Sekarang Anda memiliki rekursi untuk beta. Dua istilah terakhir dari persamaan terakhir yang Anda tahu dari model Anda. Di sini mulai dari akhir rantai (T) kita mundur menghitung semua , maka dari itu algoritma mundur. Di depan Anda harus mulai dari awal dan Anda pergi ke akhir rantai.βt

Dalam model Anda, Anda harus menginisialisasi untuk semua . Ini adalah probabilitas tidak memancarkan pengamatan setelah .βT(i)=P(xT=i)=1iT=2

pengguna2939212
sumber