本科阶段学了三四遍的HMM,机器学习课,自然语言处理课,中文信息处理课;如今学研究生的自然语言处理,又碰见了这个老熟人;
虽多次碰到,但总觉得一知半解,对其了解不够全面,借着这次的机会,我想要直接搞定这个大名鼎鼎的模型,也省着之后遇到再费心。
模型引入与背景介绍
HMM的形式化表示
HMM的三个基本问题
Evalution
Learning
Decoding
案例
在面对一个复杂问题时,“图” 是一种有效的利器,它仅仅利用点和线就能表达实体之间复杂关联和约束,如果给关联实体的边附上概率,则它更能进一步的表达实体之间的强弱联系和逻辑关系。
具体到机器学习领域,概率图模型就是一套 用图来表示特征和类别、特征和特征、类别与类别之间依赖关系 的理论。它利用图来表示“与模型有关的变量的联合概率分布”,从本质上来说,它是一种生成式模型(generative model)。
在遇到一个实际问题时,概率图模型则用观测结点表示观测到的数据,用隐含结点表示潜在的知识,用边来描述知识与数据的相互关系,最后基于这样的关系图获得一个概率分布,很好的获得了隐藏在数据中的知识。
概率图中的点分为隐含结点和观测节点,边也分为有向边和无向边。根据边的不同,可将概率图模型分为贝叶斯网络和马尔科夫网络两大类。
而我们在介绍HMM之前,也将对其相关的概念进行梳理,方便进行区分。
与马尔科夫相关的概念有许多,在之前的学习中,也都是零散的知识点,今天发掘到一条从概率图出发的逻辑链,很好的将这些知识整合到一起,大家从上到下依次阅读,应该就能明白了:
关于相关概念的体系关系,可以参考B站UP主 shuahuai008 的相关视频,我jio着说的很不错!
在上文中,我们已经对相关概念进行了系统性的阐述,但我们仍需对其中的重点的概念进行进一步的阐释,在这一节中,我们将更进一步的审视马尔科夫模型 和 隐马模型。
一个马尔可夫模型是一个三元组(S, Π, A),其中 S是状态的集合,Π是初始状态的概率, A是状态间的转移概率,其具体的含义将在HMM的形式化表示中进行介绍,在此仅用一个实例对此进行展示:
$\mathbf{A}=\left[\begin{array}{cccc}{a_{1,1}} & {a_{1,2}} & {\cdots} & {a_{1, Q}} \\ {a_{2,1}} & {a_{2,2}} & {\cdots} & {a_{2, Q}} \\ {\vdots} & {\vdots} & {\vdots} & {\vdots} \\ {a_{Q, 1}} & {a_{Q, 2}} & {\cdots} & {a_{Q, Q}}\end{array}\right]$
其中,$a_{i, j}=P\left(i_{t+1}=j | i_{t}=i\right)$,表示在时刻t处于$\mathbf{q}_{i}$状态的条件下,在t+1时刻转移到$\mathbf{q}_{j}$状态的概率。
$\mathbf{B}=\left[\begin{array}{cccc}{b_{1}(1)} & {b_{1}(2)} & {\cdots} & {b_{1}(V)} \\ {b_{2}(1)} & {b_{2}(2)} & {\cdots} & {b_{2}(V)} \\ {\vdots} & {\vdots} & {\vdots} & {\vdots} \\ {b_{Q}(1)} & {b_{Q}(2)} & {\cdots} & {b_{Q}(V)}\end{array}\right]$
其中$b_{j}(k)=P\left(o_{t}=k | i_{t}=j\right)$,表示在时刻t处于$\mathbf{q}_{i}$状态的条件下,生成观测变量$\mathbf{v}_{k}$的概率。
在定义了上述的内容后,我们可以形式化的定义一个HMM模型,即用一个五元组表示$\lambda=(\mathrm{Q}, \mathrm{V}, \mathrm{\Pi}, \mathrm{A}, \mathrm{B})$,其中,$\mathbf{A}, \mathbf{B}, \vec{\pi}$称为隐马尔科夫模型的三要素:
- 状态转移概率矩阵$\mathbf{A}$和初始状态概率向量$\vec{\pi}$确定了隐藏的马尔科夫链,生成不可预测的状态序列。
- 观测矩阵矩阵$\mathbf{B}$确定了如何从状态变量生成观测变量,并与状态序列$\mathbf{I}$一起确定了如何产生观测序列。
$P\left(i_{t} | i_{t-1}, o_{t-1}, \cdots, i_{1}, o_{1}\right)=P\left(i_{t} | i_{t-1}\right), \quad t=1,2, \cdots, T$
$P\left(o_{t} | i_{T}, o_{T}, \cdots, i_{t-1}, o_{t+1}, i_{t}, i_{t-1}, o_{t-1}, \cdots, i_{1}, o_{1}\right)=P\left(o_{t} | i_{t}\right), \quad t=1,2, \cdots, T$
隐马尔科夫模型可以解决三种基本问题:
概率计算问题,或称为评估问题(Evoluation):
模型构建问题,即学习问题(Learning):
隐状态求解问题,即解码问题(Decoding):
给定模型$\lambda=(\mathrm{Q}, \mathrm{V}, \mathrm{\Pi}, \mathrm{A}, \mathrm{B})$和观测序列$\mathbf{O}=\left(o_{1}, o_{2}, \cdots, o_{T}\right)$,求对给定的观测序列的条件概率$P(\mathbf{I} | \mathbf{O})$最大的状态变量序列$\mathbf{I}=\left(i_{1}, i_{2}, \cdots, i_{T}\right)$。
即给定观测序列,求最可能的对应的状态序列 。
例如:在语音识别任务中,观测值为语音信号,隐藏状态为文字。解码问题的目标就是:根据观测的语音信号来推断最有可能的文字序列。
给定模型$\lambda=(\mathrm{Q}, \mathrm{V}, \mathrm{\Pi}, \mathrm{A}, \mathrm{B})$和观测序列$\mathbf{O}=\left(o_{1}, o_{2}, \cdots, o_{T}\right)$,计算观测序列$\mathbf{O}$出现的概率$P(\mathbf{O} | \lambda)$
最直接的方法就是按照概率公式直接计算:通过列举所有可能的长度为T的在状态序列$\mathbf{I}=\left(i_{1}, i_{2}, \cdots, i_{T}\right)$,求各个状态序列$\mathbf{I}$与观测序列$\mathbf{O}=\left(o_{1}, o_{2}, \cdots, o_{T}\right)$的联合概率$P(\mathbf{O}, \mathbf{I} | \lambda)$,然后对所有可能的状态求和得到$P(\mathbf{O} | \lambda)$
其计算过程如下所示:
上述的直接计算方法,时间复杂度太大,只在理论中可行,无法投入真正的使用
前向算法的本质是引入了动态规划的思想,将计算观测序列$\mathbf{O}=\left(o_{1}, o_{2}, \cdots, o_{T}\right)$ 的出现概率 转化为 在$t=1$时出现 $o_{1}$的概率$\times$在$t=2$时出现 $o_{2}$的概率$\times$……$\times$在$t=T$时出现 $o_{T}$的概率。
因此,定义前向概率,即:在时刻$t$的观测序列为$o_{1}, o_{2}, \cdots, o_{t}$,且隐状态为$q_{j}$的概率 ,记作:$\alpha_{t}(i)=P\left(o_{1}, o_{2}, \cdots, o_{t}, i_{t}=i ; \lambda\right)$;
而如果我们能从初始状态递推得出最后一个时刻的前向概率,就可以估计出 观测序列为$O$时的状态变量,其递推公式的构建过程可见下述思路:
$\alpha_{t+1}(i)=\left[\sum_{j=1}^{Q} \alpha_{t}(j) a_{j, i}\right] b_{i}\left(o_{t+1}\right)$
由此,我们也就得到了前向算法的流程与描述:
Input:
Output:观测序列概率$P(\mathbf{O} | \lambda)$
算法步骤:
手机扫一扫
移动阅读更方便
你可能感兴趣的文章