Viterbi algoritması - Viterbi algorithm

Viterbi algoritması bir dinamik program algoritma en çok bulmak için muhtemelen gizli durumlar dizisi - denir Viterbi yolu—Özellikle şu bağlamda bir dizi gözlemlenen olay ile sonuçlanır Markov bilgi kaynakları ve gizli Markov modelleri (HMM).

Algoritma, kod çözmede evrensel bir uygulama buldu. evrişimli kodlar ikisinde de kullanıldı CDMA ve GSM dijital hücresel, çevirmek modemler, uydu, derin uzay iletişimi ve 802.11 kablosuz LAN'lar. Şimdi de yaygın olarak kullanılmaktadır Konuşma tanıma, konuşma sentezi, diarizasyon,^[1] anahtar kelime belirleme, hesaplamalı dilbilimleri, ve biyoinformatik. Örneğin, konuşmadan yazıya (konuşma tanıma), akustik sinyal gözlemlenen olaylar dizisi olarak değerlendirilir ve bir metin dizisi akustik sinyalin "gizli nedeni" olarak kabul edilir. Viterbi algoritması, akustik sinyal verilen en olası metin dizisini bulur.

Tarih

Viterbi algoritması adını Andrew Viterbi, 1967'de bunu bir kod çözme algoritması olarak öneren evrişimli kodlar gürültülü dijital iletişim bağlantıları üzerinden.^[2] Bununla birlikte, bir geçmişi vardır çoklu buluş Viterbi tarafından yapılanlar da dahil olmak üzere en az yedi bağımsız keşifle, Needleman ve Wunsch, ve Wagner ve Fischer.^[3] Tanıtıldı Doğal Dil İşleme yöntemi olarak Konuşma bölümü etiketleme 1987 kadar erken.

"Viterbi yolu" ve "Viterbi algoritması", dinamik programlama algoritmalarının olasılıkları içeren maksimizasyon problemlerine uygulanması için standart terimler haline gelmiştir.^[3]Örneğin, istatistiksel ayrıştırma Yaygın olarak "Viterbi ayrıştırması" olarak adlandırılan bir dizenin en olası tek bağlamdan bağımsız türevini (ayrıştırmasını) keşfetmek için dinamik bir programlama algoritması kullanılabilir.^[4]^[5]^[6] Başka bir uygulama hedef takibi, bir dizi gözlem için maksimum olasılık atayan iz hesaplanır.^[7]

Uzantılar

Viterbi algoritmasının bir genellemesi, maksimum toplam algoritması (veya maksimum ürün algoritması) tümünün veya bir kısmının en olası atamasını bulmak için kullanılabilir. gizli değişkenler çok sayıda grafik modeller, Örneğin. Bayes ağları, Markov rasgele alanları ve koşullu rastgele alanlar. Gizli değişkenlerin genel olarak, değişkenler arasında sınırlı sayıda bağlantı ve değişkenler arasında bir tür doğrusal yapı ile bir HMM'ye benzer bir şekilde bağlanması gerekir. Genel algoritma şunları içerir: ileti geçişi ve büyük ölçüde benzerdir inanç yayılımı algoritması (bu, ileri-geri algoritması ).

Algoritma adı verilen yinelemeli Viterbi kod çözme Belirli bir gözlemle en iyi (ortalama olarak) eşleşen bir gözlemin alt dizisi bulunabilir. gizli Markov modeli. Bu algoritma, Qi Wang ve ark. başa çıkmak turbo kodu.^[8] Yinelemeli Viterbi kod çözme, değiştirilmiş bir Viterbi algoritmasını yinelemeli olarak çağırarak çalışır ve yakınsamaya kadar bir dolgu için puanı yeniden tahmin eder.

Alternatif bir algoritma, Tembel Viterbi algoritması, önerilmiştir.^[9] Makul gürültü koşulları altında pratik açıdan ilgi çekici birçok uygulama için, tembel kod çözücü (Lazy Viterbi algoritması kullanan) orijinalinden çok daha hızlıdır Viterbi kod çözücü (Viterbi algoritması kullanarak). Orijinal Viterbi algoritması, olası sonuçların kafesindeki her düğümü hesaplarken, Lazy Viterbi algoritması, sırayla değerlendirmek için öncelikli bir düğüm listesi tutar ve gerekli hesaplama sayısı tipik olarak sıradan Viterbi algoritmasından daha azdır (ve asla daha fazla değildir) aynı sonuç. Ancak o kadar kolay değil^{[açıklama gerekli ]} donanımda paralelleştirmek için.

Sözde kod

Bu algoritma bir yol oluşturur ${ displaystyle X = (x_ {1}, x_ {2}, ldots, x_ {T})}$ , bir durum dizisi olan ${ displaystyle x_ {n} in S = {s_ {1}, s_ {2}, dots, s_ {K} }}$ gözlemleri oluşturan ${ displaystyle Y = (y_ {1}, y_ {2}, ldots, y_ {T})}$ ile ${ displaystyle y_ {n} in O = {o_ {1}, o_ {2}, dots, o_ {N} }}$ , nerede ${ displaystyle N}$ gözlem alanındaki olası gözlemlerin sayısıdır ${ displaystyle O}$ .

İki 2 boyutlu boyut tablosu ${ displaystyle K times T}$ inşa edilir:

Her öğe ${ displaystyle T_ {1} [i, j]}$ nın-nin ${ displaystyle T_ {1}}$ şimdiye kadarki en olası yolun olasılığını depolar ${ displaystyle { hat {X}} = ({ hat {x}} _ {1}, { hat {x}} _ {2}, ldots, { hat {x}} _ {j} )}$ ile ${ displaystyle { şapka {x}} _ {j} = s_ {i}}$ bu üretir ${ displaystyle Y = (y_ {1}, y_ {2}, ldots, y_ {j})}$ .
Her öğe ${ displaystyle T_ {2} [i, j]}$ nın-nin ${ displaystyle T_ {2}}$ mağazalar ${ displaystyle { hat {x}} _ {j-1}}$ şimdiye kadarki en olası yolun ${ displaystyle { hat {X}} = ({ hat {x}} _ {1}, { hat {x}} _ {2}, ldots, { hat {x}} _ {j- 1}, { hat {x}} _ {j} = s_ {i})}$ için ${ displaystyle forall j, 2 leq j leq T}$

Tablo girişleri ${ displaystyle T_ {1} [i, j], T_ {2} [i, j]}$ sırasını artırarak doldurulur ${ displaystyle K cdot j + i}$ :

{ displaystyle T_ {1} [i, j] = max _ {k} {(T_ {1} [k, j-1] cdot A_ {ki} cdot B_ {iy_ {j}})}}

,

{ displaystyle T_ {2} [i, j] = operatöradı {argmax} _ {k} {(T_ {1} [k, j-1] cdot A_ {ki} cdot B_ {iy_ {j}} )}}

,

ile ${ displaystyle A_ {ki}}$ ve ${ displaystyle B_ {iy_ {j}}}$ aşağıda açıklandığı gibi. Bunu not et ${ displaystyle B_ {iy_ {j}}}$ Negatif olmadığı ve şunlardan bağımsız olduğu için ikinci ifadede görünmesi gerekmez. ${ displaystyle k}$ ve bu nedenle argmax'ı etkilemez.

Giriş

gözlem alanı ${ displaystyle O = {o_ {1}, o_ {2}, noktalar, o_ {N} }}$ ,
durum alanı ${ displaystyle S = {s_ {1}, s_ {2}, noktalar, s_ {K} }}$ ,
bir dizi başlangıç olasılıkları ${ displaystyle Pi = ( pi _ {1}, pi _ {2}, noktalar, pi _ {K})}$ öyle ki ${ displaystyle pi _ {i}}$ olasılığını depolar ${ displaystyle x_ {1} = s_ {i}}$ ,
bir dizi gözlem ${ displaystyle Y = (y_ {1}, y_ {2}, ldots, y_ {T})}$ öyle ki ${ displaystyle y_ {t} = i}$ eğer gözlem zamanında ${ displaystyle t}$ dır-dir ${ displaystyle o_ {i}}$ ,
geçiş matrisi ${ displaystyle A}$ boyut ${ displaystyle K times K}$ öyle ki ${ displaystyle A_ {ij}}$ depolar geçiş olasılığı eyaletten geçiş ${ displaystyle s_ {i}}$ belirtmek ${ displaystyle s_ {j}}$ ,
emisyon matrisi ${ displaystyle B}$ boyut ${ displaystyle K times N}$ öyle ki ${ displaystyle B_ {ij}}$ gözlemleme olasılığını depolar ${ displaystyle o_ {j}}$ eyaletten ${ displaystyle s_ {i}}$ .

Çıktı

En olası gizli durum dizisi ${ displaystyle X = (x_ {1}, x_ {2}, ldots, x_ {T})}$

 işlevi VITERBI ${ displaystyle (O, S, Pi, Y, A, B): X}$      için Her eyalet  ${ displaystyle i = 1,2, ldots, K}$  yapmak          ${ displaystyle T_ {1} [i, 1] leftarrow pi _ {i} cdot B_ {iy_ {1}}}$           ${ displaystyle T_ {2} [i, 1] leftarrow 0}$      sonu için     için her gözlem  ${ displaystyle j = 2,3, ldots, T}$  yapmak         için Her eyalet  ${ displaystyle i = 1,2, ldots, K}$  yapmak              ${ displaystyle T_ {1} [i, j] max _ {k} alır {(T_ {1} [k, j-1] cdot A_ {ki} cdot B_ {iy_ {j}})} }$               ${ displaystyle T_ {2} [i, j] gets arg max _ {k} {(T_ {1} [k, j-1] cdot A_ {ki} cdot B_ {iy_ {j}} )}}$          sonu için     sonu için      ${ displaystyle z_ {T} arg max alır {k} {(T_ {1} [k, T])}}$       ${ displaystyle x_ {T} leftarrow s_ {z_ {T}}}$      için  ${ displaystyle j = T, T-1, ldots, 2}$  yapmak          ${ displaystyle z_ {j-1} leftarrow T_ {2} [z_ {j}, j]}$           ${ displaystyle x_ {j-1} leftarrow s_ {z_ {j-1}}}$      sonu için     dönüş  ${ displaystyle X}$  son işlev

Python yakınında kısa ve öz olarak yeniden ifade edilmiştir:

 # olasılık == p. Tm: geçiş matrisi. Em: emisyon matrisi. işlevi viterbi (O, S, Π, Tm, Em): best_path kafes ← matris (uzunluk (S), uzunluk (O)) # p'yi tutmak için. her gözlem verildi. # Her gizli durumun p'yi belirleyin. 0… zamanda için s aralıktaki (uzunluk (S)): kafes [s, 0] ← Π [s] * Em [s, O [0]] #… ve daha sonra, her durumun en olası önceki durumu, k. için o aralıkta (1, uzunluk (O)): için aralıktaki s (uzunluk (S)): k ← argmax (k kafes içinde [k, o-1] * Tm [k, s] * Em [s, o]) kafes [s, o] ← kafes [k, o-1] * Tm [k, s] * Em [s, o] en iyi_yol ← liste () için o (-1, - (uzunluk (O) +1), -1) aralığında: # Son gözlemden geri dönüş. k ← argmax (k kafes içinde [k, o]) # En olası durum o best_path.insert (0, S [k]) # dönüş için not edildi. dönüş en iyi_yol

Açıklama

Diyelim ki bize bir gizli Markov modeli (HMM) durum uzayıyla ${ displaystyle S}$ , ilk olasılıklar ${ displaystyle pi _ {i}}$ devlette olmanın ${ displaystyle i}$ ve geçiş olasılıkları ${ displaystyle a_ {i, j}}$ devletten geçiş ${ displaystyle i}$ belirtmek ${ displaystyle j}$ . Diyelim ki çıktıları gözlemliyoruz ${ displaystyle y_ {1}, noktalar, y_ {T}}$ . En olası durum dizisi ${ displaystyle x_ {1}, noktalar, x_ {T}}$ gözlemleri üreten, tekrarlama ilişkileri ile verilir^[10]

{ displaystyle { begin {align} V_ {1, k} & = mathrm {P} { big (} y_ {1} | k { büyük)} cdot pi _ {k}, V_ {t, k} & = max _ {x in S} left ( mathrm {P} { big (} y_ {t} | k { big)} cdot a_ {x, k} cdot V_ {t-1, x} sağ). end {hizalı}}}

Buraya ${ displaystyle V_ {t, k}}$ en olası durum dizisinin olasılığıdır ${ displaystyle mathrm {P} { büyük (} x_ {1}, dots, x_ {t}, y_ {1}, dots, y_ {t} { büyük)}}$ ilkinden sorumlu ${ displaystyle t}$ olan gözlemler ${ displaystyle k}$ son hali olarak. Viterbi yolu, hangi durumu hatırlayan geri işaretçiler kaydedilerek alınabilir. ${ displaystyle x}$ ikinci denklemde kullanılmıştır. İzin Vermek ${ displaystyle mathrm {Ptr} (k, t)}$ değerini döndüren işlev ol ${ displaystyle x}$ hesaplamak için kullanılır ${ displaystyle V_ {t, k}}$ Eğer ${ displaystyle t> 1}$ veya ${ displaystyle k}$ Eğer ${ displaystyle t = 1}$ . Sonra

{ displaystyle { begin {align} x_ {T} & = arg max _ {x in S} (V_ {T, x}), x_ {t-1} & = mathrm {Ptr} (x_ {t}, t). end {hizalı}}}

Burada standart tanımını kullanıyoruz arg max.

Bu uygulamanın karmaşıklığı ${ displaystyle O (T times sol | {S} sağ | ^ {2})}$ . Daha iyi bir tahmin, dahili döngüdeki maksimum, bunun yerine, yalnızca mevcut duruma doğrudan bağlanan durumlar üzerinden yineleyerek bulunursa (yani, ${ displaystyle k}$ -e ${ displaystyle j}$ ). Sonra kullanarak amortize edilmiş analiz karmaşıklığın olduğu gösterilebilir ${ displaystyle O (T kere ( sol | {S} sağ | + sol | {E} sağ |))}$ , nerede ${ displaystyle E}$ grafikteki kenarların sayısıdır.

Misal

Tüm köylülerin ya sağlıklı ya da ateşli olduğu bir köy düşünün ve her birinin ateşi olup olmadığını sadece köy doktoru belirleyebilir. Doktor, hastalara nasıl hissettiklerini sorarak ateşi teşhis eder. Köylüler sadece normal, baş dönmesi veya üşüdüklerini söyleyerek cevap verebilirler.

Doktor, hastalarının sağlık durumunun ayrı ayrı işlediğine inanıyor. Markov zinciri. "Sağlıklı" ve "Ateş" olmak üzere iki durum vardır, ancak doktor bunları doğrudan gözlemleyemez; onlar gizli ondan. Her gün, hastanın sağlık durumuna bağlı olarak doktora "normal", "soğuk" veya "baş dönmesi" olduğunu söyleme şansı vardır.

gözlemler (normal, soğuk, baş dönmesi) ile birlikte gizli durumu (sağlıklı, ateş) gizli bir Markov modeli (HMM) oluşturur ve aşağıdaki gibi temsil edilebilir: Python programlama dili:

gözlem = ("normal", "soğuk", "baş döndürücü")eyaletler = ("Sağlıklı", "Ateş")start_p = {"Sağlıklı": 0.6, "Ateş": 0.4}trans_p = {    "Sağlıklı": {"Sağlıklı": 0.7, "Ateş": 0.3},    "Ateş": {"Sağlıklı": 0.4, "Ateş": 0.6},}emit_p = {    "Sağlıklı": {"normal": 0.5, "soğuk": 0.4, "baş döndürücü": 0.1},    "Ateş": {"normal": 0.1, "soğuk": 0.3, "baş döndürücü": 0.6},}

Bu kod parçasında, start_p doktorun hasta ilk ziyaretinde HMM'nin hangi durumda olduğu konusundaki inancını temsil eder (tek bildiği hastanın sağlıklı olma eğiliminde olduğudur). Burada kullanılan belirli olasılık dağılımı, yaklaşık olarak (geçiş olasılıkları verildiğinde) olan denge değildir. {"Sağlıklı": 0,57, "Ateş": 0,43}. geçiş_p temeldeki Markov zincirindeki sağlık durumundaki değişikliği temsil eder. Bu örnekte, bugün sağlıklıysa, yarın hastanın ateşi çıkma ihtimali yalnızca% 30'dur. Emission_p Normal, soğuk veya baş dönmesi gibi olası her gözlemin, altta yatan sağlık durumu veya ateşinin ne kadar olası olduğunu gösterir. Hasta sağlıklıysa, kendini normal hissetme şansı% 50'dir; ateşi varsa, başının dönmesi olasılığı% 60'tır.

Verilen HMM'nin grafik temsili

Hasta arka arkaya üç gün ziyarete gelir ve doktor ilk gün normal hissettiğini, ikinci gün üşüdüğünü, üçüncü gün başının döndüğünü fark eder. Doktorun bir sorusu var: Hastanın bu gözlemleri açıklayacak en olası sağlık durumu sırası nedir? Bu, Viterbi algoritmasıyla yanıtlanır.

 1 def Viterbi(gözlem, eyaletler, start_p, trans_p, emit_p): 2     V = [{}] 3     için st içinde eyaletler: 4         V[0][st] = {"prob": start_p[st] * emit_p[st][gözlem[0]], "önceki": Yok} 5     # T> 0 olduğunda Viterbi'yi çalıştır 6     için t içinde Aralık(1, len(gözlem)): 7         V.eklemek({}) 8         için st içinde eyaletler: 9             max_tr_prob = V[t - 1][eyaletler[0]]["prob"] * trans_p[eyaletler[0]][st]10             prev_st_selected = eyaletler[0]11             için prev_st içinde eyaletler[1:]:12                 tr_prob = V[t - 1][prev_st]["prob"] * trans_p[prev_st][st]13                 Eğer tr_prob > max_tr_prob:14                     max_tr_prob = tr_prob15                     prev_st_selected = prev_st16 17             max_prob = max_tr_prob * emit_p[st][gözlem[t]]18             V[t][st] = {"prob": max_prob, "önceki": prev_st_selected}19 20     için hat içinde dptable(V):21         Yazdır(hat)22 23     seçmek = []24     max_prob = 0.025     önceki = Yok26     # En olası durumu ve geri dönüşünü alın27     için st, veri içinde V[-1].öğeler():28         Eğer veri["prob"] > max_prob:29             max_prob = veri["prob"]30             best_st = st31     seçmek.eklemek(best_st)32     önceki = best_st33 34     # İlk gözleme kadar geri dönüşü takip edin35     için t içinde Aralık(len(V) - 2, -1, -1):36         seçmek.eklemek(0, V[t + 1][önceki]["önceki"])37         önceki = V[t + 1][önceki]["önceki"]38 39     Yazdır ('Devletlerin adımları' + ' '.katılmak(seçmek) + en yüksek olasılıkla % s' % max_prob)40 41 def dptable(V):42     # Sözlükten bir adım tablosu yazdırın43     Yol ver " ".katılmak(("% 12d" % ben) için ben içinde Aralık(len(V)))44     için durum içinde V[0]:45         Yol ver "% .7s: " % durum + " ".katılmak("% .7s" % ("% f" % v[durum]["prob"]) için v içinde V)

İşlev Viterbi aşağıdaki argümanları alır: gözlem gözlemlerin dizisidir, ör. ['normal', 'soğuk', 'baş dönmesi']; eyaletler gizli durumlar kümesidir; start_p başlangıç olasılığıdır; trans_p geçiş olasılıklarıdır; ve emit_p emisyon olasılıklarıdır. Kodun basitliği için, gözlem dizisinin gözlem boş değil ve bu trans_p [i] [j] ve emit_p [i] [j] tüm i, j durumları için tanımlanmıştır.

Çalışan örnekte forward / Viterbi algoritması aşağıdaki gibi kullanılmıştır:

Viterbi(gözlem,        eyaletler,        start_p,        trans_p,        emit_p)

Komut dosyasının çıktısı

$ python viterbi_example.py         0          1          2Sağlıklı: 0.30000 0.08400 0.00588Ateş: 0,04000 0,02700 0,01512Durumların adımları, 0,01512 ile en yüksek olasılıkla Sağlıklı Sağlıklı Ateştir.

Bu, gözlemlerin ['normal', 'soğuk', 'baş dönmesi'] büyük olasılıkla eyaletler tarafından oluşturuldu ["Sağlıklı", "Sağlıklı", "Ateş"]. Diğer bir deyişle, gözlemlenen aktiviteler göz önüne alındığında, hasta hem kendini normal hissettiği ilk gün hem de üşüdüğünde ikinci günde sağlıklı olmuş ve ardından üçüncü gün ateşi yakalanmıştı.

Viterbi'nin algoritmasının çalışması, birkafes diyagramı. Viterbi yolu aslında bu kafesin içinden geçen en kısa yoldur.

soft output Viterbi algoritması

soft output Viterbi algoritması (SOVA), klasik Viterbi algoritmasının bir çeşididir.

SOVA klasikten farklıdır Viterbi algoritması dikkate alan değiştirilmiş bir yol metriği kullandığından önsel olasılıklar girilir ve bir yumuşak gösteren çıktı güvenilirlik kararın.

SOVA'daki ilk adım, hayatta kalan yolunun seçimidir, her seferinde anında bir benzersiz düğümden geçer, t. Her düğümün kendisine yakınsayan 2 dalı olduğu için (bir dal, Survivor Yoluve diğeri atılır), şube metriklerindeki fark (veya maliyet) seçilen ve atılan dallar arasındaki hata miktarı seçimde.

Bu maliyet sürgülü pencerenin tamamı boyunca birikir (genellikle eşittir en azından beş kısıtlama uzunluğu), yumuşak çıktı güvenilirlik ölçüsü zor karar of Viterbi algoritması.

Ayrıca bakınız

Referanslar

^ Xavier Anguera ve diğerleri, "Konuşmacı Diarization: Son Araştırmaların Gözden Geçirilmesi", erişim tarihi: 19. Ağustos 2010, IEEE TASLP
^ 29 Nisan 2005, G.David Forney Jr: Viterbi Algoritması: Kişisel Bir Tarih
^ ^a ^b Daniel Jurafsky; James H. Martin. Konuşma ve Dil İşleme. Pearson Education International. s. 246.
^ Schmid, Helmut (2004). Son derece belirsiz bağlamdan bağımsız gramerlerin bit vektörleriyle verimli bir şekilde ayrıştırılması (PDF). Proc. 20. Uluslararası Konf. Hesaplamalı Dilbilim (COLING) üzerine. doi:10.3115/1220355.1220379.
^ Klein, Dan; Manning, Christopher D. (2003). A * ayrıştırma: hızlı tam Viterbi ayrıştırma seçimi (PDF). Proc. 2003 Conf. İnsan Dili Teknolojisi Üzerine Hesaplamalı Dilbilim Derneği (NAACL) Kuzey Amerika Bölümü. sayfa 40–47. doi:10.3115/1073445.1073461.
^ Stanke, M .; Keller, O .; Gündüz, I .; Hayes, A .; Waack, S .; Morgenstern, B. (2006). "AĞUSTOS: Alternatif transkriptlerin ab initio tahmini". Nükleik Asit Araştırması. 34 (Web Sunucusu sorunu): W435 – W439. doi:10.1093 / nar / gkl200. PMC 1538822. PMID 16845043.
^ Quach, T .; Farooq, M. (1994). "Viterbi Algoritması ile Maksimum Olabilirlik İzleme Oluşumu". 33. IEEE Karar ve Kontrol Konferansı Bildirileri. 1. s. 271–276. doi:10.1109 / CDC.1994.410918.CS1 bakimi: birden çok ad: yazarlar listesi (bağlantı)
^ Qi Wang; Lei Wei; Rodney A. Kennedy (2002). "Yüksek Hızlı Eşlik-Birleştirilmiş TCM için Yinelemeli Viterbi Kod Çözme, Kafes Şekillendirme ve Çok Düzeyli Yapı". İletişimde IEEE İşlemleri. 50: 48–55. doi:10.1109/26.975743.
^ Evrişimli kodlar için hızlı bir maksimum olabilirlik kod çözücü (PDF). Araç Teknolojisi Konferansı. Aralık 2002. s. 371–375. doi:10.1109 / VETECF.2002.1040367.
^ Xing E, 11. slayt.

Genel referanslar

Viterbi AJ (Nisan 1967). "Evrişimli kodlar için hata sınırları ve asimptotik olarak optimum kod çözme algoritması". Bilgi Teorisi Üzerine IEEE İşlemleri. 13 (2): 260–269. doi:10.1109 / TIT.1967.1054010. (not: Viterbi kod çözme algoritması IV. bölümde açıklanmıştır.) Abonelik gereklidir.
Feldman J, Abou-Faycal I, Frigo M (2002). Evrişimli Kodlar için Hızlı Maksimum Olabilirlik Kod Çözücü. Araç Teknolojisi Konferansı. 1. s. 371–375. CiteSeerX 10.1.1.114.1314. doi:10.1109 / VETECF.2002.1040367. ISBN 978-0-7803-7467-6.
Forney GD (Mart 1973). "Viterbi algoritması". IEEE'nin tutanakları. 61 (3): 268–278. doi:10.1109 / PROC.1973.9030. Abonelik gerekli.
Basın, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Bölüm 16.2. Viterbi Kod Çözme". Sayısal Tarifler: Bilimsel Hesaplama Sanatı (3. baskı). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
Rabiner LR (Şubat 1989). "Gizli Markov modelleri ve konuşma tanımada seçilen uygulamalar hakkında bir eğitim". IEEE'nin tutanakları. 77 (2): 257–286. CiteSeerX 10.1.1.381.3454. doi:10.1109/5.18626. (HMM'ler için ileri algoritmayı ve Viterbi algoritmasını açıklar).
Shinghal, R. ve Godfried T. Toussaint, "Değiştirilmiş Viterbi algoritmasıyla metin tanıma deneyleri," Örüntü Analizi ve Makine Zekası Üzerine IEEE İşlemleri, Cilt. PAMI-l, Nisan 1979, s. 184–193.
Shinghal, R. ve Godfried T. Toussaint, "Değiştirilmiş Viterbi algoritmasının kaynak istatistiklerine duyarlılığı," Örüntü Analizi ve Makine Zekası Üzerine IEEE İşlemleri, cilt. PAMI-2, Mart 1980, s. 181–185.

Uygulamalar

Mathematica Stokastik süreçlere verdiği desteğin bir parçası olarak bir uygulamaya sahiptir
Susa sinyal işleme çerçevesi, C ++ uygulamasını sağlar İleri hata düzeltme kodlar ve kanal eşitleme İşte.
C ++
C #
Java
Java 8
Perl
Prolog
Haskell
Git
SFIHMM Viterbi kod çözme kodunu içerir.

Dış bağlantılar

Vikikitap'ta Java, F #, Clojure, C # uygulamaları
Öğretici viterbi kod çözme ile evrişimli kodlama üzerine, Chip Fleming tarafından
Viterbi algoritmasının bir açıklamasını içeren bir Gizli Markov Modeli araç seti (C'de uygulanmıştır) için bir eğitim
Viterbi algoritması Yazan Dr. Andrew J. Viterbi (alimpedia.org).

[1] Xavier Anguera ve diğerleri, "Konuşmacı Diarization: Son Araştırmaların Gözden Geçirilmesi", erişim tarihi: 19. Ağustos 2010, IEEE TASLP

[2] 29 Nisan 2005, G.David Forney Jr: Viterbi Algoritması: Kişisel Bir Tarih

[slp-3] Daniel Jurafsky; James H. Martin. Konuşma ve Dil İşleme. Pearson Education International. s. 246.

[4] Schmid, Helmut (2004). Son derece belirsiz bağlamdan bağımsız gramerlerin bit vektörleriyle verimli bir şekilde ayrıştırılması (PDF). Proc. 20. Uluslararası Konf. Hesaplamalı Dilbilim (COLING) üzerine. doi:10.3115/1220355.1220379.

[5] Klein, Dan; Manning, Christopher D. (2003). A * ayrıştırma: hızlı tam Viterbi ayrıştırma seçimi (PDF). Proc. 2003 Conf. İnsan Dili Teknolojisi Üzerine Hesaplamalı Dilbilim Derneği (NAACL) Kuzey Amerika Bölümü. sayfa 40–47. doi:10.3115/1073445.1073461.

[6] Stanke, M .; Keller, O .; Gündüz, I .; Hayes, A .; Waack, S .; Morgenstern, B. (2006). "AĞUSTOS: Alternatif transkriptlerin ab initio tahmini". Nükleik Asit Araştırması. 34 (Web Sunucusu sorunu): W435 – W439. doi:10.1093 / nar / gkl200. PMC 1538822. PMID 16845043.

[7] Quach, T .; Farooq, M. (1994). "Viterbi Algoritması ile Maksimum Olabilirlik İzleme Oluşumu". 33. IEEE Karar ve Kontrol Konferansı Bildirileri. 1. s. 271–276. doi:10.1109 / CDC.1994.410918.CS1 bakimi: birden çok ad: yazarlar listesi (bağlantı)

[8] Qi Wang; Lei Wei; Rodney A. Kennedy (2002). "Yüksek Hızlı Eşlik-Birleştirilmiş TCM için Yinelemeli Viterbi Kod Çözme, Kafes Şekillendirme ve Çok Düzeyli Yapı". İletişimde IEEE İşlemleri. 50: 48–55. doi:10.1109/26.975743.

[9] Evrişimli kodlar için hızlı bir maksimum olabilirlik kod çözücü (PDF). Araç Teknolojisi Konferansı. Aralık 2002. s. 371–375. doi:10.1109 / VETECF.2002.1040367.

[10] Xing E, 11. slayt.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]