|
1算法的理论基础
基因是生物学概念，之所以将基因算法引入HMM的训练中，是因为HMM的训练过
程实际上是一个在特定范围内将HMM模型进行一次次的迭代提纯，选择最优模型
的过程。这和自然界物种间互相竞争、优胜劣汰的现象是相似的。
生物的遗传基因包含在染色体中，染色体总是成对的出现，父代生物的染色体各
自复制自己的基因传给子代，经过一定的交叉，基因重组形成下一代生物的染色
体，来自父代的基因特性能够在子代上体现并保持下去。而在遗传的同时，又有
一定的基因突变。基因突变造成生物体突变现象，打破了旧有的平衡，突破了旧
的基因的活动区域，对物种的进化有很大的影响。生物进化的动力来自于遗传和
选择，不论是正常的基因重新组合，还是突发的无方向性的基因突变，都可以控
制对子代基因中有害淘汰，而只将有益的保留下来，使生物向好的方向进化。将
较优的基因保留下来，一代又一代不断选择的结果使子代的基因收敛于某个单一
的基因形式，这个基因型就是在特定优化问题的最优解。从数学的角度解释，可
以简单地认为，基因重组使子代基因趋向于局部最优解，而基因突变使子代基因
突破局部的范围，经过很多代的遗传和选择，达到全域最优解。
字串9
传统的CHMM训练算法的实质是选择一个CHMM模型为初始值，也即选择初始状态
向量π。状态转移矩阵A和每个状态的输出概率密度函数bj(o)=∑cjk N(o,μjk,Ujk)，
将其数值与观测序列一起运算，求出一个新的、优于旧CHMM的估计模型，反复迭
代，直到局部最优解。可以采用几个不同的初始值，希望能够到达更好的最佳值。
将基因算法引入CHMM的训练，就是基于将CHMM看作在特定域的有约束的寻找最
佳匹配点的问题。CHMM的状态转移矩阵A和输出概率密度函数中的混合系数c矩阵
的每一行向量之和为1.0，可看作是优化问题的约束条件。如果在选取CHMM的初始
值时，不是选取一个初始值，而是选取一组分布于不同区域的初始值，以某一种特
定的训练方法，使其趋向于全域最优解，那么最终也同样可以完成对CHMM的训练。 字串7
2基因算法的实现 字串3
在自然界中，生物进化的动力来自于遗传和选择。在基因算法中，主要的操作就
是模拟遗传的基因重组和基因突变，以及模拟自然选择的样本选择。
根据待优化问题的数学模型，定义适合函数F(ai)。其中ai是某一条染色体，则适
合函数F(ai)就是该染色体与目标函数的距离，或是判断该染色体优劣的依据。
对每一代基因，计算所有染色体的适合函数，进行排序选择一定数目较优秀的染
色体，作为生成下一代基因的父代样本。
自然界中染色体成对出现，交配时一对染色体分离、重组。图1为多点交叉重组的
示意图。多点交叉在实现时，可以设定交叉概率门限为ρc。染色体的长度为L，
对于随机数0≤rj≤1 (j=1,2,…,L)，如果rj≥ρc，那么下一个变量属于另一条
基因，否则下一个变量与前一个变量属于同一条基因。
图1多点交叉示例
Fig.1Multi points crossover
最佳基因是在一代一代的基因重组和基因突变中形成的，是在选择的作用下最适
应的个体。基因突变有利于从局部最佳处跳出，防止算法的过早收敛。设定突变
概率门限为ρm，对于随机数0≤rj≤1 (j=1,2,…,L)，如果rj≤ρm，那么染色体中 字串5
第j个变量有突变现象发生；否则，复制原染色体的第j个变量。
下面给出基因算法的具体实现步骤：
(1) 产生随机数，组成最初的染色体p0=(a1,a2,…,aL)。其中ai为一条染色体，由数
学模型中所有的参数按某一特定的排列方式组成。
(2) 计算各条染色体的适合函数F(ai)。并选其适合函数F(ai)进行排序，设定门限，
选取新的父代染色体p′t。
(3) 以随机方式选取染色体交叉。
(4) 在自然界的生物进化过程中，基因变异是很重要的。由于某一两个元素的突
变，可能导致子基因比父基因有较大的适应能力。表现在基因算法中，染色体以
比较小的突变率进行小单位的变异。
(5) 计算各子代基因的适应函数，是否达到结束的条件，否则转到(2)进行下一步
的运算。 字串9
3基因算法训练CHMM 字串1
HMM是用一个有限状态系统作为语音特征参数的生成模型，每个状态能产生连续
的输出特征。HMM实际上是一个特征参数发生器，依据其产生的参数与观察到的
语音参数的比较，从而识别语音。在识别时的判决依据是HMM模型的生成概率。
在将基因算法引入CHMM训练的过程中，首先要解决的是染色体的构造问题。将
CHMM模型的所有参数排列成一串，构成染色体.对于语音识别，采用自左向右的
HMM模型，本文中为5状态自左向右只含一阶跳转的CHMM模型。CHMM模型中
参数由初始状态向量π，状态转移矩阵A和每个状态的输出概率密度函数组成。
向量π共含5个元素，在A矩阵中，共有元素5×5=25个，其中不为0的参数为12个。
较为复杂的是各状态的输出概率密度函数bj(o)=∑cjkN(o,μjk,Ujk)。其中：j代
表第j个状态；cjk为混合系数；N()为高斯函数；μjk为平均矢量；Ujk为协方差
矩阵。语音信号由微机Sound Blaster声霸卡录音采样获得，生成wav文件采样频
率为11.025 kHz.分析帧长为256点，每帧帧移为128点。采用10阶LPC倒谱，选取
bj(o)为5个高斯概率密度函数的混合。将向量π、短阵A和混合系数矩阵c的参数
共5+12+25=42个按行组成一串，形成染色体的前一部分，将平均矢量μ和协方差 字串7
矩阵U共5×5×(10+10×10)=2 750个参数按行组成一串，形成染色体的后一部分。
在CHMM模型中，染色体前一部分的行向量之和均为1。也就要求在产生染色体时，
需对其进行一定的控制。在生成每一代染色体时，对这一部分行向量所对应的每
一段染色体进行归一化，则可以满足CHMM的约束条件。
Viterbi算法在通常的CHMM语音识别中是作为识别算法的，换句话说，使观测序
列与CHMM模型经Viterbi算法的运算结果最大即为优化目标.基于这样的思想，基
因算法的适合函数为：所有该CHMM对应的观测序列用Viterbi算法求其观测概率
之和，运算结果越大，则该染色体越优秀。
在实验中染色体的前一部分依概率进行二点或多点交叉，而后一部分染色体只进
行多点交叉，多点交叉概率ρc=0.8。染色体前一段的基因突变概率ρm=0.1；而
对于染色体的后一部分，取ρm1=0.01，对应于以一个参数为单位发生基因突变；
ρm2=0.08，以行向量为单位发生基因突变。经基因交叉或基因突变后，对染色体
的前一部分需要进行各行向量的归一化处理。每一代基因的数目为300，从中选出
60条优秀的染色体作为新的父代基因，经基因重组和基因突变生成240条染色体，
字串4
共同组成新一代染色体。CHMM模型的训练问题已转化为求其对观测序列适应概
率最大值的问题，用基因算法求解。
表1语音识别系统测试结果
Tab.1Recognition rate of speech recognition system
0123456789
Ne1211312312
Nr49484949474948474948
R(%)98969898949896949896 字串6
4实验结果及讨论
字串1
实验在微机上完成，由3名实验者作小字库语音识别。实验中选取0～9十个数字
作为待识别语音，训练数据取自3人(A、B、C)，训练时对每个字音A读40遍，B、
C各读30遍。表1列出了系统的识别能力测试结果。其中，对每个字音A、B各测试
20次，C测试10次。在表中，Nr、Ne分别代表正确、错误的次数，R%表示识别率。
由表1可见，总的平均识别率为96.6%。在同样的实验条件下，用传统的CHMM训练
方法，得到的识别率为93.0%，可见，用基因算法训练CHMM可在一定程度上提高
识别率。这是基因算法训练时收敛于全域最优点的缘故。
在实验中，达到以上的识别率，GA算法所用训练时间只是传统训练算法的1/5。这
是因为，传统的HMM训练方法中要以每一观测序列为训练单位进行大量迭代的矩阵
运算。在传统的HMM训练方法中，用某一观测序列进行训练时，首先需要计算对每
一时间点的前向递推概率αt(i)和后向递推概率βt(i)，该过程是迭代进行的。而后求
出辅助概率函数γt(i,j)，对应于状态i在t时间的第j个混合概率函数。最后还要经过大
量的矩阵运算才能分别求出所有的HMM模型参数。而在GA算法中，由于只需要匹配
概率，用Viterbi算法求出各观测序列对应匹配概率的log值相加即可，变乘法运算为 字串3
加法运算；同时，训练是批量进行的，GA算法需要更多的内存以储存一些中间值，
以存储量换取速度，因此，该算法可以节省训练时间。
参考文献
1Bahl L R, Jelinek F, Mercer R L. A maximum likelihood approach to cont inuous speech recognition. IEEE Trans on PAMI, 1983,5(2):179～190
2Bourlard H， Wellekens C J. Links between markov models and multilay er perceptrons. IEEE Trans on PAMI,1990,12(12):1167～1178
3Lee K F, Hon H W. Speekerindependent phone recognition using hidden markov models. IEEE Trans on ASSP,1990,37(11):1641～1648
4Hung S L, Adeli H. A parallel genetic/neural network learning algorith m for MIMD shared memory machines. IEEE Trans on Neural Networks,1994,5(6):900～ 909
5Maniezzo V. Genetic evolution of the topology and weight distribution of neural networks. IEEE Trans on Neural Networks,1994,5(1):39～53
字串8
|
