美文网首页数据分析
《数学之美》之隐含马尔科夫模型

《数学之美》之隐含马尔科夫模型

作者: 乌七七v | 来源:发表于2017-09-01 23:09 被阅读413次

    本章涉及到的概率论的知识较多。前方高能。

    前方高能。

    前方高能。。。。

    马尔科夫模型在前两章统计语言模型中已经有介绍了,这里不再赘述。

    在通信中,如何根据接收端的观测信号来推测信号源发送的信息呢?这就需要从所有的源信息中找到最可能产生观测信号的那一个信号。用概率论的语言,就是在已知接收到的信号o的情况下,求得令条件概率P(s|o)达到最大值的那个信息串s。

    先别晕。因为后面会更晕。

    根据贝叶斯公式转换一下,

    P(s|o)=P(o|s)*P(s)/P(o)

    即为求解P(s|o)*P(s)/P(o)最大值的过程。

    这时候就会发现一个问题,求解这样一个方程,是个复杂度极高的事情。隐含马尔科夫模型就要登场了。

    隐含马尔科夫模型是马尔科夫链的一个扩展:假设任一时刻t的状态st是不可见的。这样就没法通过s序列去推测转移概率等参数。(为什么要这样假设?因为对于骰子的输出163245来说,我们不仅仅有一串可见状态链,还有一串隐含状态链。可见状态链是确定的概率,如6个面骰子点数的概率;而隐含状态链是不确定概率,如选择的骰子是6个面的还是4个面)

    那这样还怎么玩?别急。

    隐含马尔科夫模型在每个时刻t会输出一个符号ot,而且ot跟且仅跟st相关。这是一个独立输出假设。

    基于马尔科夫假设和独立输出假设,我们就可以计算出某个特定的状态序列s产生出输出符号序列o的概率。

    要找到这个概率的最大值,可以使用维特比算法。这是个解码算法。

    维特比算法说白了就是动态规划实现最短路径,只要知道“动态规划可以降低复杂度”这一点就能轻松理解维特比算法。“利用动态规划,可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图——篱笆网络的有向图(Lattice )的最短路径问题而提出的。 它之所以重要,是因为凡是使用隐含马尔可夫模型描述的问题都可以用它来解码。”

    维特比算法的精髓就是,既然知道到第i列所有节点Xi{j=123…}的最短路径,那么到第i+1列节点的最短路径就等于到第i列j个节点的最短路径+第i列j个节点到第i+1列各个节点的距离的最小值。复杂度骤减为O(ND2),远远小于穷举O(DN)。

    总的来说,

    围绕着隐含马尔科夫模型有三个基本问题:

    1. 给定一个模型,如何计算某个特定的输出序列的概率;

    2. 给定一个模型和某个特定的输出序列,如何找打最可能产生这个输出的状态序列;

    3. 给定足够量的观测数据,如何估计隐含马尔科夫模型的参数。

    解:

    第一个问题,对应的算法是Forward-Backward算法。

    前向-后向算法首先对于隐马尔科夫模型的参数进行一个初始的估计(这很可能是完全错误的),然后通过对于给定的数据评估这些参数的的价值并减少它们所引起的错误来重新修订这些HMM参数(即隐含马尔科夫参数)。从这个意义上讲,它是以一种梯度下降的形式寻找一种错误测度的最小值。

    之所以称其为前向-后向算法,主要是因为对于网格中的每一个状态,它既计算到达此状态的“前向”概率(给定当前模型的近似估计),又计算生成此模型最终状态的“后向”概率(给定当前模型的近似估计)。 这些都可以通过利用递归进行有利地计算,就像我们已经看到的。可以通过利用近似的HMM模型参数来提高这些中间概率进行调整,而这些调整又形成了前向-后向算法迭代的基础。

    第二个问题,对应的算法是维特比算法(解码算法),不再赘述。

    第三个问题,是模型训练的问题。无监督模型对应的算法是Baum-Welch Algorithm(训练算法)。

    Baum-Welch Algorithm的基本思想是,随便找到一组能够产生输出序列o的模型参数,那就可以算出这个模型产生输出序列o的概率和这个模型产生o的所有可能的路径以及这些路径的概率,因此可以将这些视为“标注的训练数据”,根据最优解,计算出一组新的模型参数,从而不断迭代,直到使得输出概率达到最大化。这个过程称为期望最大化,也就是EM过程。

    解析完毕。

    晕了吧?

    要是已经晕了也没关系。

    不就是分词嘛,成熟工具多得是。我们又不专业搞算法研究,这种“轮子”的制造技术,知道个大概就好。把“车”开好才是王道。

    呜~~~~~

    相关文章

      网友评论

        本文标题:《数学之美》之隐含马尔科夫模型

        本文链接:https://www.haomeiwen.com/subject/diikjxtx.html