語音識別解碼過程使用的是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ā)了卷積碼編碼的最大似然算法