3.3 问题3的求解（学习问题）
HMM的第三个问题——学习问题是最困难的一个，需要通过最大化观测序列的概率来调整模型参数(A,B,π)。暂时还没有解析法来解决这个问题。事实上，给定一个有限观测序列作为训练数据，并不存在最优方法得到模型参数。但是，我们可以通过迭代法比如Baum-Welch算法（其实就是EM算法），或者使用梯度法，选择使得P(O|λ)局部最大的λ=(A,B,π)。这一节，我们讨论选择模型参数的一个迭代方法，这个方法主要基于Baum和他同事的经典工作。
为了描述HMM参数估计过程，首先定义给定模型和观测序列的条件下，时刻t的状态为Si且t+1的状态为Sj的概率为ξt(i,j)：
ξt(i,j)=P(qt=Si,qt+1=Sj|O,λ).(36)
(36)的计算结构如图6所示。显然，根据前向变量和后向变量的定义，我们可以得到
ξt(i,j)=αt(i)aijbj(Ot+1)βt+1(j)P(O|λ)=αt(i)aijbj(Ot+1)βt+1(j)∑Ni=1∑Nj=1αt(i)aijbj(Ot+1)βt+1(j).(37)
我们前面已经定义了给定模型和状态序列的条件下，时刻t的状态为Si的概率为γt(i)。通过在j上求和，有
γt(i)=∑j=1Nξt(i,j).(38)
如果对γt(i)在t上求和，得到的和可以理解为状态Si出现次数的期望值，如果去掉t=T项，那么得到的和可以理解为从状态Si进行转移的期望次数。类似地，在t上（从t=1到t=T−1）对ξt(i,j)进行求和得到的结果可以理解为从状态Si转移到Sj次数的期望值。即
∑t=1T−1γt(i)=从Si转移的期望次数(39a)
∑t=1T−1ξt(i,j)=从Si转移到Sj的期望次数.(39b)
利用上面的公式，我们可以给出估计HMM参数的方法。对π,A,B合理的估计可以是
πi¯=在t=1处于状态Si的概率=γt(i)(40a)
aij¯=从Si转移到Sj的期望次数从Si转移的期望次数=∑T−1t=1ξt(i,j)∑T−1t=1γt(i)(40b)
bj¯(k)=处于状态Sj且观测值为vk的期望次数状态Sj的期望次数=∑Tt=1,Ot=vkγt(j)∑Tt=1γt(j).(40c)
如果我们定义当前模型为λ=(A,B,π)，并且用它来计算(40a)-(40c)右边的表达式，然后定义新模型为λ¯=(A¯,B¯,π¯)，即(40a)-(40c)左边的部分，Baum和他同事证明了1）初始模型λ定义了似然函数的临界点；2）模型λ¯比λ更好，因为P(O|λ¯)>P(O|λ)，即我们找到了新模型λ¯，更有可能生成观测序列。
基于上面的步骤，如果我们迭代地更新λ为λ¯，那么P(O|λ)会不断增加，知道到达某个极限值。这个过程的结果称为HMM的极大似然估计。注意，前向-后向算法得到的是局部最大值，在大多数问题中，优化表面是非常复杂的并且有很多局部最大值。
更新公式(40a)-(40c)也可以通过最大化Baum的辅助函数推导出来:
Q(λ,λ¯)=∑QP(Q|O,λ)log[P(O,Q|λ¯)].(41)
Baum和他同事证明了最大化Q(λ,λ¯)可以增加似然，即
maxλ¯[Q[λ,λ¯]]=>P(O|λ¯)≥P(O|λ).(42)
最终似然函数会收敛到一个临界点。
上面的估计公式可以理解为EM算法的具体实现，其中E步是计算辅助函数Q(λ,λ¯)，M步是最大化Q(λ,λ¯)。于是，Baum-Welch估计方程本质上等价于EM算法的具体实现。
估计过程重要的一个方面是，HMM参数的随机约束，即
∑i=1Nπ¯i=1(43a)
∑j=1Na¯ij=1,1≤i≤N(43b)
∑k=1Mb¯j(k)=1,1≤j≤N(43c)
在每次迭代时是自动满足的。通过把参数估计问题看作一个带约束的优化问题，可以用拉格朗日乘子法来得到使P（P=P(O|λ)）最大的πi,aij,bj(k)值。通过标准拉格朗日优化，可以知道当
πi=πi∂P∂πi∑Nk=1∂P∂πk(44a)
aij=aij∂P∂aij∑Nk=1aik∂P∂aik(44b)
bj(k)=bj(k)∂P∂bj(k)∑Ml=1bj(l)∂P∂bj(l)(44c)
时，P是最大的。通过计算，可以发现公式(44)右边的表达式其实就是(40)右边的表达式。所以，估计公式实际上就是P的临界点。
最后，我们注意到由于整个问题可以看作一个优化问题，标准的梯度算法也可以用于求模型参数的最优值。这种方法的结果可以和标准估计过程媲美。
