Viterbi Algorithm (Viterbi Algoritması)

#algoritma #hmm #dogal-dil-isleme #konusma-tanima

Gizli Markov Modellerinde verilen gözlem dizisine karşılık en olası durum dizisini dinamik programlamayla bulan, konuşma tanıma ve NLP'nin temel çözümleme algoritması.

Viterbi Algoritması, 1967 yılında iletişim mühendisi Andrew Viterbi tarafından geliştirilen ve verilen bir gözlem dizisine karşılık gelen en olası gizli durum dizisini bulan dinamik programlama tabanlı bir algoritmadır. Başlangıçta dijital haberleşmede evrişimli kodların etkin biçimde çözülmesi için tasarlanan algoritma, kısa sürede Gizli Markov Modellerinin (HMM) çözümleme problemi için standart çözüm hâline gelmiştir. Algoritmanın temel fikri, olası durum yollarını tek tek değerlendirmek yerine dinamik programlama ilkesiyle her zaman adımında en yüksek olasılıklı kısmi yolu izlemektir. Her zaman adımında, önceki adımların en iyi yolunu hatırlamak için bir iz tablosu (traceback table) tutulur. Çözümleme tamamlandıktan sonra bu tablo geriye doğru taranarak en olası durum dizisi elde edilir. Zaman karmaşıklığı O(T × N²) olup T gözlem uzunluğunu, N ise durum sayısını gösterir; bu değer olası tüm yolları denemekle ortaya çıkan O(Nᵀ) üstel karmaşıklığın yerine geçer ve büyük ölçekte işlem yapmayı mümkün kılar. Konuşma tanımada Viterbi algoritması, akustik model olarak kullanılan HMM'lerin çözümleme adımında fonem sıralamasını belirler. Her ses çerçevesi için olasılıksal akustik özellikler hesaplanır; algoritma bu özelliklerden en olası fonem dizisini türetir. Doğal dil işlemede sözcük türü etiketleme (POS tagging) ve adlandırılmış varlık tanıma (NER) görevlerinde Koşullu Rastsal Alan (CRF) modelleri Viterbi ile çözümlenir. Biyoinformatikte DNA dizi hizalaması, gen segmentasyonu ve protein yapısı tahmini için yaygın biçimde kullanılır. Derin öğrenme çağında Viterbi algoritması, CTC (Connectionist Temporal Classification) ve CRF katmanlarıyla birleştirilerek modern konuşma tanıma ve dizi etiketleme sistemlerinde yer almaya devam etmektedir. Algoritmanın değişmez popülerliği; garantili optimal çözüm üretmesi, deterministik ve öngörülebilir çalışma süresi ile sınırlı bellek gereksinimiyle açıklanabilir. Günümüzde ESPnet ve Kaldi gibi konuşma teknolojisi araç setleri Viterbi tabanlı çözümleme modüllerini üretim sistemlerinde etkin biçimde kullanmaktadır.

Algoritmanın Çalışma Prensibi

Viterbi algoritması, bir Gizli Markov Modeli (HMM) içindeki en olası gizli durum dizisini bulmak için dinamik programlamayı kullanır. Olası tüm yolları kaba kuvvetle denemek O(Nᵀ) zaman alır ve pratikte olanaksızdır; Viterbi bunu O(T × N²)'ye indirerek çözülebilir kılar. Algoritma, her zaman adımında δ(t, s) değerini — o adıma kadar s durumuna ulaşan en yüksek olasılıklı yolu — ve ψ(t, s) iz işaretçisini — bu yolun hangi önceki durumdan geldiğini — günceller. Tüm adımlar tamamlandıktan sonra son adımın en yüksek δ değerine sahip durumundan başlanarak ψ tablosu geriye taranır ve en olası durum dizisi (en iyi yol) elde edilir. Bu geri izleme adımı algoritmanın ikinci aşamasını oluşturur.

Başlıca Uygulama Alanları

🎙️ Konuşma Tanıma (ASR)

HMM tabanlı akustik modellerde fonem sıralamasını belirler. Her ses çerçevesinin MFCC özellikleri akustik olasılıklara dönüştürülür; Viterbi en olası fonem — ve dolayısıyla kelime — dizisini türetir. Kaldi ve ESPnet gibi araç setleri bu yaklaşımı üretimde kullanmaktadır.

📝 Doğal Dil İşleme

POS etiketleme, NER ve morfolojik analiz görevlerinde CRF (Koşullu Rastsal Alan) modellerinin çözümleme adımı Viterbi ile yapılır. Cümledeki her kelimeye en uygun sözcük türünü ya da varlık etiketini tahmin eder. spaCy ve sklearn-crfsuite bu yaklaşımı kullanır.

🧬 Biyoinformatik

DNA dizi segmentasyonu, gen bölgesi tespiti ve protein yapısı tahmini için profile HMM ile birlikte kullanılır. HMMER aracı, biyolojik dizi analizi için Viterbi tabanlı çözümleme uygular. Gizli evrimsel durumlar gözlemlenen dizi pozisyonlarından çıkarsanır.

📡 Dijital Haberleşme

Algoritmanın doğduğu alan: evrişimli kodlar ve gürültülü kanal üzerinden iletilen sembollerin hatasız çözülmesi. 4G/LTE ve kablosuz ağlarda hata düzeltme kodlayıcılarının çözme (decoding) aşamasında hâlâ kullanılmaktadır.

HMM ile İlişkisi

Gizli Markov Modeli (HMM), üç temel hesaplama problemini çözmek zorundadır: (1) Değerlendirme — verili gözlem dizisinin bu model tarafından üretilme olasılığını İleri Algoritma ile hesaplamak, (2) Çözümleme — en olası gizli durum dizisini Viterbi ile bulmak, (3) Öğrenme — parametreleri Baum-Welch (EM) ile gözlemlerden tahmin etmek. Viterbi, bu üç problemin ikincisini çözer ve HMM'in 'inference' adımının merkezinde yer alır. CTC tabanlı modern derin öğrenme modellerinde bile Viterbi, çıktı olasılıklarını en tutarlı transkripte dönüştürmek için kullanılmaya devam etmektedir.

Beam Search ile Karşılaştırma

Viterbi algoritması, Markov zinciri varsayımı altında kesin optimal çözümü garanti eder. Buna karşılık Beam Search, arama uzayını genişlik olarak kırparak (beam width = k) verimlilik kazanır ancak optimalliği garanti edemez. Büyük kelime dağarcığı ve açık-kelime (open-vocabulary) senaryolarında HMM tabanlı Viterbi hesaplama açısından ölçeklenemez hale gelir; bu durumda Beam Search tercih edilir. Transformer tabanlı dil modelleriyle birlikte çalışırken Beam Search baskın olsa da küçük ve kapalı durum uzaylarında Viterbi hâlâ optimal seçimdir.

Sık Sorulan Sorular

  • check_circle Viterbi algoritması neden 'dinamik programlama' olarak sınıflandırılır?: Dinamik programlamanın temel ilkesi olan 'optimal alt yapı' özelliğini kullanır: en olası yolun her alt yolu da kendi bağlamında olasıdır. Bu sayede aynı durum-zaman çifti için tekrar hesaplama yapmak yerine önceki adımda hesaplanan δ değerlerini doğrudan kullanır. Kaba kuvvete göre üstel farkla daha hızlıdır.
  • check_circle Viterbi ile Forward algoritması arasındaki fark nedir?: Forward algoritması, tüm olası gizli yollar üzerinden toplam olasılığı hesaplar — P(gözlemler | model). Viterbi ise yalnızca en yüksek olasılıklı tek yolu bulur — argmax P(durumlar, gözlemler | model). İkisi benzer dinamik programlama yapısını paylaşır; ancak Forward 'topla', Viterbi 'maksimum al' operasyonunu kullanır.
  • check_circle CRF modellerinde Viterbi nasıl kullanılır?: CRF (Koşullu Rastsal Alan), gözlemler veriliyken etiket dizisi üzerindeki koşullu dağılımı modelleyen bir yapıdır. Tahmin aşamasında en yüksek puanlı etiket dizisini bulmak için Viterbi kullanılır. Lineer zincir CRF'de bu, HMM'deki Viterbi ile neredeyse aynı hesaplamaya karşılık gelir; fark, CRF'nin yayılım ve geçiş potansiyellerini doğrudan logliner olarak tanımlamasıdır.
  • check_circle Viterbi algoritmasının kısıtları nelerdir?: Markov varsayımına dayanır — bir sonraki durum yalnızca mevcut duruma bağlıdır, daha uzun bağımlılıkları modelleyemez. Büyük durum uzaylarında (geniş kelime dağarcığı) hesaplama maliyeti artar. Sürekli gözlem dağılımlarında Gaussian HMM ile birleştirildiğinde ayrık durumların belirlenmesi gerekir. Bu kısıtlar yüzünden açık-kelime ASR'de yerini Beam Search ve RNN/Transformer hibrit yaklaşımlarına bırakmıştır.
  • check_circle Türkçe NLP'de Viterbi kullanılır mı?: Türkçe morfolojik analiz ve sözcük türü etiketleme araştırmalarında HMM tabanlı Viterbi çözümleme tarihsel olarak kullanılmıştır. Türkçe'nin eklemeli yapısı geniş bir morfolojik durum uzayı gerektirdiğinden modern Türkçe NLP araçları büyük ölçüde derin öğrenme tabanlı mimarilere geçmiş olsa da akademik referans olarak HMM-Viterbi yaklaşımı yerini korumaktadır.