語音識別解碼過程使用的是Viterbi算法救恨，本質上是一種動態(tài)規(guī)劃算法陷揪，能夠得到全局最優(yōu)解王滤。為了進一步減少計算復雜度腿准，引用了Beam Search 算法际起，可以在損失微小性能的條件下提高解碼速度，Beam Search無法保證全局最優(yōu)解吐葱。
Viterbi解碼算法
如果從起點到終點有一條最終路徑街望，那么這條路徑子路徑也是從起點到相應時刻點的最優(yōu)路徑。如上圖弟跑，紅線是一條從起點到終點的最優(yōu)路徑灾前，那么從起點到時刻4的紅線部分也是該時間段的最優(yōu)路徑。換句話說孟辑，任一時刻哎甲，只需記錄到該時刻所有狀態(tài)的最優(yōu)路徑即可蔫敲，以時刻4為例，在時刻4炭玫，只需記錄時刻4上經(jīng)過三個狀態(tài)S1,S2,S3的最優(yōu)路徑即可奈嘿，也就是只需要記錄三條路徑，接著到時刻5吞加，時刻5的S3狀態(tài)有兩條路徑經(jīng)過裙犹，取其中最優(yōu)路徑，時刻5的S2衔憨、S1狀態(tài)類似叶圃，也就是說到了時刻5，仍然只需要記錄三條路徑即可践图。
所以每一時刻需要做兩次循環(huán)盗似，外層循環(huán)現(xiàn)在時刻所有狀態(tài)，內層循環(huán)現(xiàn)在時刻某一狀態(tài)到下一時刻所有狀態(tài)平项。時間復雜度赫舒，所有時間段時間復雜度
。上圖中闽瓢，N=3接癌，實際大規(guī)模語音識別中任一時刻的狀態(tài)可能很大，比如5000個扣讼，這樣即使使用了維特比缺猛，時間復雜度還是太大，實際中為了解決這個問題椭符，引入了Beam Search算法
Beam Search 算法
Viterbi解碼中涉及到現(xiàn)在時刻state數(shù)目以及下一時刻state數(shù)目荔燎，如果我們想要提高解碼速度，需要對這兩個數(shù)值都做縮減销钝。
實際做法是設置閾值有咨，減少語音識別中現(xiàn)在時刻以及下一時刻狀態(tài)數(shù)目，具體做法是：
- 對所有狀態(tài)排序蒸健，最優(yōu)狀態(tài)放最前面座享，最優(yōu)狀態(tài)得分=best_weight
- 設置一個beam，設置閾值1=cur_cutoff似忧，cur_cutoff=best_weight+beam渣叛，所有得分在cur_cutoff以內的，保留盯捌，反之丟棄淳衙，現(xiàn)在時刻的state數(shù)目減少。
- 計算到下一時刻的最優(yōu)路徑得分new_weight。
- 設置一個adaptive_beam, 設置閾值2=next_cutoff箫攀，next_cutoff=new_weight+adaptive_beam肠牲，所有得分在next_cutoff以內的，保留匠童，反之丟棄埂材，下一時刻的state數(shù)目減少。
kaldi實際解碼過程中汤求，cur_cutoff俏险、next_cutoff這兩個閾值是計算出來，涉及到的傳入?yún)?shù)包括：config_.beam扬绪，config_.beam_delta竖独，config_.max_active，config_.min_active挤牛。之所以引入max_active莹痢，min_active是為了保證任意時刻的state數(shù)目在[min_active，max_active]之間墓赴，單純的只用beam竞膳，有可能會導致某一時刻state數(shù)目過大或者過小。
具體Kaldi代碼解析見Kaldi 解碼代碼解析
Reference
http://kaldi-asr.org/doc/index.html
注1: 安德魯·維特比（Andrew J. Viterbi）诫硕，CDMA之父坦辟，IEEE Fellow ，高通公司創(chuàng)始人之一章办，高通首席科學家锉走。他開發(fā)了卷積碼編碼的最大似然算法
