Viterbi algoritmi nima

Viterbi algoritmi — holatlarning eng mos ketma-ketligini (Viterbi yo‘li deb ataladi) topish algoritmi bo‘lib, Markov zanjirlari doirasida sodir bo‘lgan hodisalarning eng ehtimoliy ketma-ketligini aniqlaydi.

U dinamik dasturlash algoritmidir va Viterbining konvolyutsion dekodlash algoritmida qo‘llanadi.

Algoritmni Endryu Viterbi 1967-yilda shovqinli aloqa tarmoqlari orqali uzatiladigan konvolyutsion kodni dekodlash uchun taklif etgan. U GSM va CDMA standartlaridagi mobil telefonlarda, dial-up modemlarda hamda 802.11 standartidagi simsiz tarmoqlarda konvolyutsion kodlarni dekodlash uchun keng qo‘llanadi. Shuningdek, algoritm nutqni tanib olish, nutq sintezi, kompyuter lingvistikasi va bioinformatika sohalarida ham keng qo‘llanadi. Masalan, nutqni tanib olishda tovush signali hodisalar ketma-ketligi sifatida qaraladi, matn esa akustik signalning «yashirin ma’nosi» hisoblanadi. Viterbi algoritmi ushbu signalga mos keluvchi eng ehtimoliy matnni aniqlaydi.

Algoritm quyidagi farazlarga asoslanadi:

  • Kuzatiladigan va yashirin hodisalar ketma-ketlik hosil qilishi kerak. Bu ketma-ketlik odatda vaqt bo‘yicha tartiblangan bo‘ladi.
  • Ikkala ketma-ketlik o‘zaro moslashtirilgan bo‘lishi kerak: har bir kuzatiladigan hodisaga aynan bitta yashirin hodisa mos kelishi lozim.
  • t vaqtigacha bo‘lgan eng ehtimoliy yashirin ketma-ketlikni hisoblash faqat t vaqtidagi kuzatiladigan hodisaga va t − 1 vaqtigacha bo‘lgan eng ehtimoliy ketma-ketlikka bog‘liq bo‘lishi kerak.

Algoritm

Faraz qilaylik, yashirin Markov modeli (YMM) mavjud bo‘lib, uning holatlar fazosi S={s1,s2,…,sK}, bunda K — tarmoqdagi mumkin bo‘lgan turli holatlar soni. Tarmoq holatlarini bevosita kuzatib bo‘lmaydi. xt — tarmoqning t vaqtdagi holati. Tarmoq chiqishida t vaqtda kuzatiladigan yt∈O={o1,o2,…,oN} qiymat hosil bo‘ladi, bunda N — tarmoq chiqishida kuzatilishi mumkin bo‘lgan turli qiymatlar soni. πi — tarmoqning i holatda bo‘lishining boshlang‘ich ehtimolini bildiradi; ai,j esa tarmoqning i holatidan maqsad holatga o‘tish ehtimoli bo‘lib, maqsad holat — j.

Faraz qilaylik, tarmoq chiqishida quyidagi ketma-ketlik kuzatiladi: y1,…,yT. U holda tarmoq holatlarining eng ehtimoliy ketma-ketligi x1,…,xT kuzatilgan ketma-ketlik asosida quyidagi rekurrent munosabatlar orqali aniqlanadi:

V1,k=P(y1 | k)⋅πkVt,k=maxx∈S(P(yt | k)⋅ax,k⋅Vt−1,x)

Bu yerda Vt,k — dastlabki t ta kuzatilgan qiymatga mos keluvchi va k holatida yakunlanadigan eng ehtimoliy holatlar ketma-ketligining ehtimolidir. Viterbi yo‘lini ikkinchi tenglamadagi x qiymatini eslab qoluvchi ko‘rsatkichlar yordamida aniqlash mumkin. Faraz qilaylik, Ptr(k,t) — x qiymatini qaytaruvchi funksiya. Bu qiymat Vt,k ni hisoblashda ishlatiladi, agar t>1 bo‘lsa; aks holda, k qiymatini qaytaradi, agar t=1 bo‘lsa. U holda

xT=arg⁡maxx∈S(VT,x)xt−1=Ptr(xt,t)

Bu yerda quyidagi operatorning standart ta’rifidan foydalaniladi: arg max.
Ushbu algoritmning hisoblash murakkabligi O(T×|S|2).