Viterbi Algoritması

viterbi algoritması nedir?

Viterbi algoritması, bir gizli Markov modelinde (HMM) elindeki gözlem dizisinin arkasındaki en olası gizli durum dizisini bulan bir yöntem. Durum şu: senin görebildiğin tek şey gözlemler — ses dalgaları, bir cümledeki kelimeler, sensör okumaları. Bu gözlemleri üreten asıl durumlar (hangi ses birimi söylendi, kelime hangi türden, robot haritada nerede) gizli. Viterbi tam bu soruyu yanıtlar: "bu gözlemleri en büyük olasılıkla hangi durum dizisi üretti?"

Akla gelen ilk çözüm, tüm olası durum dizilerini tek tek deneyip en olasını seçmek. Ama |Y| durum ve d adım varsa bu |Y|^d yol demek — 50 durum ve 100 adımda hesaplanamayacak kadar çok. Viterbi bunu akıllı bir kısayolla çözer.

nasıl çalışır?

Temeli dinamik programlama. Fikir şu: her zaman adımında, her durum için "o duruma varan en iyi yolun olasılığını" sakla, gerisini unut.

Başlangıç: İlk gözlem için her durumun olasılığını hesapla (başlangıç olasılığı × gözlem olasılığı).
İleri özyineleme: Sonraki her adımda, her durum için bir önceki adımdaki tüm durumlara bak ve en yüksek olasılığı veren yolu seç: v_t(j) = max_i [ v_{t-1}(i) × geçiş × gözlem ]. Hangi önceki durumun bu maksimumu verdiğini bir geri işaretçide (backpointer) not et.
Bitiş: Son adımda en yüksek olasılıklı durumu seç.
Geriye izleme: Geri işaretçileri sondan başa takip ederek en olası yolu geri çıkar.

Maliyeti O(d·|Y|²) — yani adım ve durum sayısıyla polinom olarak büyür, üstel değil.

neden önemli?

Çünkü imkansızı mümkün kılıyor. Kaba kuvvetle üstel sayıda yolu denemek yerine, Viterbi aynı cevabı polinom zamanda veriyor. Bu sayede dizi tabanlı modeller gerçek zamanlı çalışabiliyor. Köken olarak haberleşmede hata düzeltme için ortaya çıktı, ama bugün hâlâ dizi modellemesinin iskeletinde duruyor.

kullanım alanları

Konuşma tanıma: ses spektrumlarından hangi ses birimlerinin söylendiğini çözer.
Makine çevirisi: iki dildeki kelimeleri birbirine hizalamakta kullanılır.
Robot konum takibi: sensör okumalarından robotun harita üzerindeki yerini tahmin eder.

Dizisel etiketleme gereken her yerde — "görünür veriden gizli yapıyı çıkar" probleminde — Viterbi klasik araçlardan biri.

Viterbi Algoritması