精确隐马尔可夫模型训练算法

Question

在大多数情况下,Baum-Welch算法用于训练隐马尔可夫模型.

然而,在许多论文中,有人认为BW算法将进行优化,直到它陷入局部最优.

是否存在实际成功找到全局最优的精确算法(除了枚举几乎所有可能的模型并对其进行评估)？

当然对于大多数应用程序,BW将正常工作.然而,我们有兴趣在减少状态数量时找到信息丢失量的下限.因此,我们总是需要生成最好的模型.

因此,我们正在寻找一种有效的NP-hard算法(只能枚举(可能)指数数量的极值点),而不是模型中每个概率的离散数量的浮点数.

Answer 1

快速搜索在http://www.cs.tau.ac.il/~rshamir/algmb/98/scribe/html/lec06/node6.html中查找"在这种情况下,找到最佳参数集的问题$\theta ^ {\ ast} $已知是NP完全的.Baum-Welch算法[2]是EM技术(期望和最大化)的特例,可以用于启发式地找到解决方案.因此,我建议保证在多项式时间内找到全局最优的EM变量将证明P = NP且未知,实际上可能不存在.

这个问题几乎肯定不是凸的,因为实际上会有多个全局最优解具有相同的分数 - 给定任何提出的解决方案,通常给出基础状态的观察的概率分布,例如,您可以重命名隐藏状态0作为隐藏状态1,反之亦然,调整概率分布,使得由两个不同解产生的观察到的行为是相同的.因此,如果有N个隐藏状态,则至少有N个!通过在他们自己之间置换隐藏状态而产生的局部最优.

在EM的另一个应用中,https://www.math.ias.edu/csdm/files/11-12/amoitra_disentangling_gaussians.pdf提供了一种用于寻找全局最优高斯混合模型的算法.它观察到EM算法经常用于这个问题,但指出它不能保证找到全局最优,并且不作为相关工作引用可能的任何版本的EM(它也说EM算法很慢) .

如果你试图在例如4状态模型和5状态模型之间进行某种似然比检验,如果由于局部最优,拟合的5态模型的可能性低于4态模型,则显然会令人尴尬.四态模型.避免这种情况或从中恢复的一种方法是从非常接近发现的最佳4态模型的起点开始5态EM.例如,您可以使用概率epsilon创建第5个状态,并使用反映4态输出分布平均值的输出分布,将4态分布保持为新5态模型中的其他4个分布,乘以a某个地方的(1-epsilon)因子,所以一切仍然加起来.