一種基于遺傳算法的語法網(wǎng)絡(luò)搜索方法

安徽城市管理職業(yè)學(xué)院 汪丹丹

1.引言

語音識(shí)別技術(shù)是讓機(jī)器通過識(shí)別和理解人類的語音信號，進(jìn)而聽懂人類的語言。近年來，由于計(jì)算機(jī)各項(xiàng)功能的日益強(qiáng)大，云計(jì)算技術(shù)的全面發(fā)展，語音信號處理技術(shù)也得到了長足的進(jìn)步。目前語音識(shí)別技術(shù)已廣泛應(yīng)用于醫(yī)療、教育、安全、電信客服等領(lǐng)域，覆蓋人類生活的方方面面。

但在實(shí)際應(yīng)用中仍然會(huì)存在較多的問題，比如信道干擾、背景噪音干擾等，這些不確定因素都會(huì)對識(shí)別率造成很大的影響。另外，在各類嵌入式設(shè)備終端上，語音識(shí)別系統(tǒng)的運(yùn)行環(huán)境相對比較差，在系統(tǒng)的效率和效果之間要做好平衡。基于以上問題，語音識(shí)別系統(tǒng)通常從三方面來評價(jià)，分別魯棒性、識(shí)別率以及響應(yīng)時(shí)間，本文重點(diǎn)關(guān)注語音識(shí)別系統(tǒng)的識(shí)別率和響應(yīng)時(shí)間。本文選擇基于隱馬爾科夫模型(Hidden Markov Model,HMM)的語音識(shí)別技術(shù)[1]構(gòu)建了基線系統(tǒng)。在該系統(tǒng)中，影響語音識(shí)別系統(tǒng)識(shí)別率和響應(yīng)時(shí)間的模塊比較多，但最主要的還是解碼模塊。該模塊通常采用傳統(tǒng)的Viterbi解碼方法，但是在海量命令詞識(shí)別時(shí)，如車載領(lǐng)域的興趣點(diǎn)(Position of Interesting,POI)識(shí)別，搜索空間急劇增大，獲取最優(yōu)解的效率大大降低。針對這類復(fù)雜的問題，需要把主要精力放在尋求滿意解上。

遺傳算法(Genetic Algorithm,GA)借鑒了生物學(xué)中的染色體和基因的概念，通過模擬自然進(jìn)化過程，求解滿意解較為有效。它對一個(gè)參數(shù)編碼群體進(jìn)行操作，提供的參數(shù)信息量較大，優(yōu)化效果也相對較好[2-4]。因此，本文將GA算法應(yīng)用于基線系統(tǒng)的語法網(wǎng)絡(luò)搜索模塊，以此來提升該模塊的全局優(yōu)化搜索能力，進(jìn)而改善系統(tǒng)的識(shí)別效果和響應(yīng)時(shí)間。

2.基線系統(tǒng)的構(gòu)建

2.1 系統(tǒng)結(jié)構(gòu)

如圖1所示，系統(tǒng)各部分按照與識(shí)別實(shí)例關(guān)系的不同分為兩大類：實(shí)例無關(guān)事物和實(shí)例相關(guān)事物。實(shí)例無關(guān)事物指的是與識(shí)別實(shí)例無關(guān)的永久性資源：包括拼音到HMM索引表、漢字到HMM的索引表和HMM集合。實(shí)例相關(guān)的事物則指的是與特定識(shí)別實(shí)例相聯(lián)系的行為或數(shù)據(jù)。它又可分為四個(gè)字模塊：詞典集合、搜索、轉(zhuǎn)化和錄音模塊。

錄音模塊，負(fù)責(zé)和錄音設(shè)備交互。負(fù)責(zé)從錄音設(shè)備中獲取聲音數(shù)據(jù)。負(fù)責(zé)自動(dòng)將含有靜音和語音的數(shù)據(jù)切分出來，提供給轉(zhuǎn)化使用。

轉(zhuǎn)化模塊，負(fù)責(zé)將波形數(shù)據(jù)轉(zhuǎn)化為特征向量序列。

搜索模塊，負(fù)責(zé)對特征向量序列在給定的語法網(wǎng)絡(luò)中搜索。對每一幀搜索數(shù)據(jù)，能夠更新搜索狀態(tài)。搜索狀態(tài)是一個(gè)記號集合，每個(gè)記號對應(yīng)于搜索網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，同時(shí)還包括搜索數(shù)據(jù)到達(dá)此節(jié)點(diǎn)的最大概率和路徑，以及內(nèi)部HMM各狀態(tài)的概率。

詞典集合模塊，負(fù)責(zé)管理詞典。實(shí)際系統(tǒng)支持多個(gè)詞典，形成一個(gè)詞典可包含多個(gè)詞典的詞典集合。每個(gè)詞典包含多個(gè)詞，可以增加、刪除詞。可以將一個(gè)詞典生成語法網(wǎng)絡(luò)，提供給搜索使用。

圖1 基線系統(tǒng)框架結(jié)構(gòu)

2.2 識(shí)別流程概述

系統(tǒng)有兩種運(yùn)行狀態(tài)：脫機(jī)識(shí)別和聯(lián)機(jī)識(shí)別。脫機(jī)識(shí)別和聯(lián)機(jī)識(shí)別的區(qū)別在于語音數(shù)據(jù)的來源不同。脫機(jī)識(shí)別數(shù)據(jù)來自文件，而聯(lián)機(jī)是別的數(shù)據(jù)來自麥克風(fēng)。這兩種狀態(tài)的運(yùn)行流程如圖2所示。

圖2 語音識(shí)別流程

3.語法網(wǎng)絡(luò)搜索的遺傳操作

在實(shí)際的搜索中，我們通常是將HMM根據(jù)語法的限制連接成一個(gè)語法網(wǎng)絡(luò)，如圖3就是一個(gè)簡單的孤立詞識(shí)別系統(tǒng)的語法網(wǎng)絡(luò)，語法網(wǎng)絡(luò)可以分為三層，如圖4所示。

語法網(wǎng)絡(luò)搜索過程又稱為解碼，邏輯上通常將解碼分為兩層，一層是HMM內(nèi)部狀態(tài)在時(shí)刻t的最大概率，另一層是以網(wǎng)絡(luò)節(jié)點(diǎn)為單元，它們之間的關(guān)系為網(wǎng)絡(luò)節(jié)點(diǎn)在時(shí)刻t的概率是本HMM內(nèi)部各狀態(tài)在時(shí)刻t的最大值。

傳統(tǒng)的解碼方法是Viterbi解碼，但是在一些應(yīng)用場合，比如車載領(lǐng)域的POI識(shí)別，其命令詞集合非常大，往往有數(shù)十萬條。此時(shí)，解碼的搜索空間將急劇增大，而系統(tǒng)的效率、效果將急劇下降。所以，對這類復(fù)雜的問題，需要把主要精力放在尋求滿意解上，而GA正是尋求這種滿意解的最佳工具之一。

圖3 孤立詞識(shí)別系統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)

圖4 語法網(wǎng)絡(luò)的三層模型[5]

3.1 編碼方案

將語法網(wǎng)絡(luò)的HMM標(biāo)號i(i,2,…,N)作為基因，構(gòu)造有K個(gè)命令詞的識(shí)別網(wǎng)絡(luò)，每個(gè)命令詞內(nèi)存放一類標(biāo)號，構(gòu)成遺傳操作的染色體。

3.2 創(chuàng)建初始種群

初始種群應(yīng)具有一定的規(guī)模，以保持群體內(nèi)個(gè)體的多樣性。由于GA具有很強(qiáng)的魯棒性，所以如何形成初始種群不影響優(yōu)化結(jié)果，只影響優(yōu)化時(shí)間。可以對一條染色體加以隨機(jī)擾動(dòng)產(chǎn)生一定N-1條剩余的染色體。

3.3 適應(yīng)度函數(shù)

計(jì)算染色體對應(yīng)的HMM狀態(tài)的似然度估計(jì)值，以此作為適應(yīng)度評價(jià)函數(shù)。似然值越大，適應(yīng)度值也就越大。不過這顯得有些簡單，后續(xù)還可以將似然值進(jìn)行分段處理，并增加輔助評價(jià)函數(shù)。

3.4 交叉運(yùn)算

交叉運(yùn)算是遺傳算法中產(chǎn)生新個(gè)體的主要操作過程，它以某一概率相互交換某兩個(gè)個(gè)體之間的部分染色體[6]。本文采用單點(diǎn)交叉的方法[7]，首先對群體進(jìn)行隨機(jī)配對；其次隨機(jī)設(shè)置交叉點(diǎn)位置；最后再相互交換配對染色體之間的部分基因。

3.5 突變運(yùn)算

突變運(yùn)算是對個(gè)體的某一個(gè)或某一些基因座上的基因值按某一較小的概率進(jìn)行改變，它也是產(chǎn)生新個(gè)體的一種操作方法[6]。本文采用基本位突變的方法來進(jìn)行突變運(yùn)算[8]，其具體操作過程是：首先確定出各個(gè)個(gè)體的基因變異位置，可以隨機(jī)產(chǎn)生的變異點(diǎn)位置，然后依照某一概率將變異點(diǎn)的原有基因值取反即可。

3.6 系統(tǒng)參數(shù)動(dòng)態(tài)控制

在群體演化進(jìn)程中，系統(tǒng)參數(shù)的最佳設(shè)置足隨演化進(jìn)程不斷變化的，如在演化開始時(shí)，群體的多樣性較高，較高的交叉率及交叉操作子權(quán)重，較低的突變率及突變操作子權(quán)重有利于利用已有好基因塊組成較好的染色體。隨著演化進(jìn)程的深入，群體的多樣性越來越小，此時(shí)，較高的突變率和較高的突變操作子權(quán)重有利于群體引進(jìn)新的基因，保持群體的多樣性，即探索新的解空間。

為充分發(fā)揮各遺傳操作子的搜索能力，已有多種系統(tǒng)參數(shù)動(dòng)態(tài)設(shè)置方案提出。本文采用一種較簡單的方法[5]，突變率及突變操作了權(quán)重隨進(jìn)化進(jìn)程指數(shù)遞增，而交叉率及交叉操作子權(quán)重進(jìn)化進(jìn)程指數(shù)遞減。

設(shè)pc(0)，pm(0)為初始交叉率及突變率，Tc、Tm為預(yù)設(shè)的最小交叉率及最大突變率。在t時(shí)刻，交叉率及突變率為：

其中，演化時(shí)間t可以是群體更新次數(shù)，也可是固定演化時(shí)間間隔的記數(shù)。

4.總結(jié)

傳統(tǒng)的解碼方法是Viterbi解碼，但是在海量命令詞識(shí)別時(shí)，如車載領(lǐng)域的POI識(shí)別，搜索空間急劇增大，獲取最優(yōu)解的效率大大降低。所以，對這類復(fù)雜的問題，需要把主要精力放在尋求滿意解上，本文應(yīng)用GA方法進(jìn)行語法網(wǎng)絡(luò)搜索，求解滿意解，提升了該方法的全局優(yōu)化搜索能力。

在GA方法中，適應(yīng)度評價(jià)函數(shù)的設(shè)計(jì)至關(guān)重要，本文以計(jì)算染色體對應(yīng)的HMM狀態(tài)的似然度估計(jì)值作為適應(yīng)度函數(shù)，似然值越大，適應(yīng)度越好。但這顯得有些簡單，后續(xù)研究還可以將似然值進(jìn)行分段處理，并增加輔助評價(jià)函數(shù)。

另外，GA解碼得到的搜索結(jié)果不唯一，但都是滿意解，因此可以稱之為“模糊搜索”，與“精確搜索”相對應(yīng)，是語音識(shí)別領(lǐng)域的一種全新的應(yīng)用理念。

[1]韓紀(jì)慶.語音信號處理[M].北京:清華大學(xué)出版社,2010.[2]Holland J.H.Adaptation in Natural and Artificial Systems[M].The University of Michigan Press.1975.

[3]宋小鵬,潘宏俠,宋叔飚.遺傳神經(jīng)網(wǎng)絡(luò)在語音識(shí)別中的應(yīng)用研究[J].機(jī)械工程與自動(dòng)化,2006,6(3):25-26.

[4]劉占軍,兆爾波.基于遺傳算法提高計(jì)算機(jī)連續(xù)語音識(shí)別率的研究[J].沈陽航空航天大學(xué)學(xué)報(bào),2005(1).

[5]賀前華,韋崗,金連文.基于遺傳算法的HMM最小錯(cuò)識(shí)率訓(xùn)練方法[J].電路與系統(tǒng)學(xué)報(bào),1999,4(4):46-50.

[6]玄光南.遺傳算法與工程優(yōu)化[M].北京:清華大學(xué)出版社,2012.

[7]林惠娟.基于遺傳算法的測試用例自動(dòng)生成技術(shù)研究[D].四川大學(xué),2006.

[8]劉秋生,楊繼昌.遺傳優(yōu)化閾值選取加速算法研究[J].江蘇大學(xué)學(xué)報(bào)(自然科學(xué)版),2003(3).