您现在的位置是:网站首页> 内容页

隐马尔可夫模型(HMM)及Viterbi算法

  • mgm集团官网
  • 2019-03-11
  • 142人已阅读
简介HMM简介  对于算法爱好者来说,隐马尔可夫模型的大名那是如雷贯耳。那么,这个模型到底长什么样?具体的原理又是什么呢?有什么具体的应用场景呢?本文将会解答这些疑惑。  本文将通过具体形

HMM简介

  对于算法爱好者来说,隐马尔可夫模型的大名那是如雷贯耳。那么,这个模型到底长什么样?具体的原理又是什么呢?有什么具体的应用场景呢?本文将会解答这些疑惑。  本文将通过具体形象的例子来引入该模型,并深入探究隐马尔可夫模型及Viterbi算法,希望能对大家有所启发。  隐马尔可夫模型(HMM,hidden Markov model)是可用于标注问题的统计学模型,描述由隐藏的马尔可夫链随机生成观测序列的过程,属于生成模型。HMM模型在实际的生活和生产中有着广泛的应用,包括语音识别,自然语言处理,生物信息,模式识别等领域。

引入

  某天,你的女神告诉你说,她放假三天,将要去上海游玩,准备去欢乐谷、迪士尼和外滩(不一定三个都会去)。  她呢,会选择在这三个地方中的某几个逗留并决定是否购物,而且每天只待在一个地方。根据你对她的了解,知道她去哪个地方,仅取决于她去的上一个地方,且是否购物的概率仅取决于她去的地方。已知她去的三个地方的转移概率表如下:

上个地方欢乐谷迪士尼外滩
欢乐谷0.80.050.15
迪士尼0.20.60.3
外滩0.20.30.5

稍微对这个表格做些说明,比如第一行,前一天去了欢乐谷后,第二天还待在欢乐谷的概率为0.8,去迪士尼的概率为0.05,去外滩的概率为0.15。  她在每个地方的购物概率为:

地点购物概率
欢乐谷0.1
迪士尼0.8
外滩0.3

  在出发的时候,她跟你说去每个地方的可能性相同。后来,放假回来后,你看了她的朋友圈,发现她的购物情况如下:第一天不购物,第二三天都购物了。于是,你很好奇,她这三天都去了哪些地方。  怎么样,聪明的你能求解出来吗?

HMM的模型参数

  接下来,我们将会介绍隐马尔可夫模型(HMM)。  隐马尔可夫模型是关于时序的概率模型,描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列,再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列,称为状态序列;每个状态生成一个观测,而由此产生的观测的随机序列,称为观测序列。序列的每一个位置又可以看作是一个时刻。  隐马尔可夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定。隐马尔可夫模型的形式定义如下:  设Q是所有可能的状态的集合,V是所有可能的观测的集合,也就是说,Q是不可见的,而V是可见的,是我们观测到的可能结果。

[q={q_1,q_2,...,q_N}, V={v_1,v_2,...,v_M}]

其中,N是可能的状态数,M是可能的观测数。  在刚才的例子中,(Q)是不可见的状态集合,应为(Q={欢乐谷,迪士尼,外滩}),而(V)是可以观测的集合,应为(V={购物,不购物})  I是长度为T的状态序列,O是对应的观测序列。

[I=(i_1,i_2,...,i_T), O=(o_1,o_2,...,o_T)]

在刚才的例子中,(I)这个序列是我们需要求解的,即女生去了哪些地方,而(O)是你知道的序列,(O={不购物,购物,购物})  A是状态转移概率矩阵:

[A=[a_{ij}]_{Nimes N}]其中,(a_{ij}=P(i_{t+1}=q_j|i_{t}=q_{i}), i=1,2,...,N; j=1,2,..,N)是在时刻t处于状态(q_i)的条件下在时刻t+1转移到状态(q_j)的概率。在刚才的例子中,转移概率矩阵为:

[A=egin{bmatrix}{0.8}&{0.05}&{0.15}\{0.6}&{0.6}&{0.2}\{0.2}&{0.3}&{0.5}\end{bmatrix}]

  B是观测概率矩阵:

[B=[b_{j}(k)]_{Nimes M}]

其中,(b_{j}(k)=P(o_t = v_{k}|i_{t}=q_{j}), k=1,2,...,M; j=1,2,...,N)是在时刻t处于状态(q_{j})的条件下生成观测(v_{k})的概率。在刚才的例子中:

[B=egin{bmatrix}{0.1}&{0.9}\{0.8}&{0.2}\{0.3}&{0.7}\end{bmatrix}]

  (pi)是初始状态概率向量(pi=(pi_i)),其中(pi_i = P(i_1 = q_i), i=1,2,...,N)是时刻t=1处于状态(q_{j})的概率。在刚才的例子中, (pi = (frac{1}{3}, frac{1}{3}, frac{1}{3}).)  综上,我们已经讲完HMM中的基本概念。同时,我们可以知道,隐马尔可夫模型由初始状态概率向量(pi),状态转移概率矩阵(A)和观测概率矩阵(B)决定。(pi)(A)决定状态序列,(B)决定观测序列。因此,隐马尔可夫模型(lambda)可用三元符号表示,即

[lambda = (A, B, pi)]

(A,B,pi)称为HMM的三要素。  当然,隐马尔可夫模型之所以被称为马尔可夫模型,是因为它使用了两个基本的假设,其中之一为马尔可夫假设。它们分别是:

    齐次马尔科夫假设,即假设隐藏的马尔可夫链在任意时刻t的状态只依赖于其前一时刻的状态,与其他时刻的状态及观测无关,也与时刻t无关。

[P(i_{i}|i_{t-1},o_{t-1},...,i_1,o_1)=P(i_{t}|i_{t-1}), t=1,2,...,T]

    观测独立性假设,即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态,与其他观测及状态无关。

[P(o_{i}|i_{T},o_{T},...,i_{t+1},o_{t+1},i_{t}, t_{t-1},o_{t-1},...,i_{1},o_{1})=P(o_{t}|i_{t}), t=1,2,...,T]

  在刚才的假设中,我们对应的两个假设分别为:她去哪个地方,仅取决于她去的上一个地方;是否购物的概率仅取决于她去的地方。前一个条件为齐次马尔科夫假设,后一个条件为观测独立性假设。  以上,我们就介绍了HMM的基本概念及假设。而HMM的三个基本问题如下:

    概率计算问题。给定模型(lambda=(A,B,pi))和观测序列(O=(o_1,o_2,...,o_T)),计算在模型(lambda)下观测序列(O)出现的概率(P(O|lambda).)学习问题。已知观测序列(O=(o_1,o_2,...,o_T)),估计模型(lambda=(A,B,pi))参数,使得在该模型下观测序列概率(P(O|lambda))最大。预测问题。已知模型(lambda=(A,B,pi))和观测序列(O=(o_1,o_2,...,o_T)),求对给定观测序列条件概率(P(I|O))最大的状态序列(I=(i_1,i_2,...,i_T).)即给定观测序列,求最有可能的对应的状态序列。

  上面的例子即为HMM的第三个基本问题,也就是,给定观测序列{不购物,购物,购物},结果最有可能的状态序列,即游玩的地方。

Viterbi算法

  求解HMM的第三个基本问题,会用到大名鼎鼎的维特比算法(Viterbi Algorithm)。  维特比算法以安德鲁·维特比(Andrew Viterbi)命名,是现代数字通信中最常用的算法,同时也是很多自然语言处理采用的解码算法。可以毫不夸张地讲,维特比是对我们的生活影音力最大的科学家之一,因为基于CDMA的3G移动通信标准主要就是他和厄文·雅各布(Irwin Mark Jacobs)创办的高通公司(Qualcomm)指定的。  维特比算法是一个特殊但应用最广的动态规划(dynamic programming)算法,利用动态规划,可以解决任何一个图中的最短路径问题,同时,它也是求解HMM描述的第三个基本问题的算法。  在维特比算法中,需要引入两个变量(delta)(psi.)定义在时刻t状态i的所有单个路径((i_1,i_2,...,i_t))中概率最大值为

[delta_{t+1}(i) = max_{1leq j leq N}[delta_{t}(j)a_{ji}]b_{i}(o_{t+1}), i=1,2,...,N; t=1,2,...,T.]

定义在时刻t状态为i的所有单个路径((i_1,i_2,...,i_{t-1},i))中概率最大的路径的第i-1个节点为

[psi_{t}(i) = arg max_{1leq j leq N}[delta_{t-1}(j)a_{ji}], i=1,2,...,N; t=1,2,...,T.]

  下面是维特比算法在HMM的第三个基本问题的算法:

Python代码实现

  下面,对于刚才给出的例子,我们将使用Python,来写代码实现Viterbi算法,同时求解刚才的问题。

# -*- coding: utf-8 -*-# HMM.py# Using Vertibi algorithmimport numpy as npdef Viterbi(A, B, PI, V, Q, obs): N = len(Q) T = len(obs) delta = np.array([[0] * N] * T, dtype=np.float64) phi = np.array([[0] * N] * T, dtype=np.int64) # 初始化 for i in range(N): delta[0, i] = PI[i]*B[i][V.index(obs[0])] phi[0, i] = 0 # 递归计算 for i in range(1, T): for j in range(N): tmp = [delta[i-1, k]*A[k][j] for k in range(N)] delta[i,j] = max(tmp) * B[j][V.index(obs[i])] phi[i,j] = tmp.index(max(tmp)) # 最终的概率及节点 P = max(delta[T-1, :]) I = int(np.argmax(delta[T-1, :])) # 最优路径path path = [I] for i in reversed(range(1, T)): end = path[-1] path.append(phi[i, end]) hidden_states = [Q[i] for i in reversed(path)] return P, hidden_statesdef main(): # 状态集合 Q = ("欢乐谷", "迪士尼", "外滩") # 观测集合 V = ["购物", "不购物"] # 转移概率: Q -> Q A = [[0.8, 0.05, 0.15], [0.2, 0.6, 0.2], [0.2, 0.3, 0.5] ] # 发射概率, Q -> V B = [[0.1, 0.9], [0.8, 0.2], [0.3, 0.7] ] # 初始概率 PI = [1/3, 1/3, 1/3] # 观测序列 obs = ["不购物", "购物", "购物"] P, hidden_states = Viterbi(A,B,PI,V,Q,obs) print("最大的概率为: %.5f."%P) print("隐藏序列为:%s."%hidden_states)main()

输出结果如下:

最大的概率为: 0.02688.隐藏序列为:["外滩", "迪士尼", "迪士尼"].

  现在,你有很大的把握可以确定,你的女神去了外滩和迪士尼。

   注意:本人现已开通微信公众号: Python爬虫与算法(微信号为:easy_web_scrape), 欢迎大家关注哦~~

参考文献

    一文搞懂HMM(隐马尔可夫模型):https://www.cnblogs.com/skyme/p/4651331.html李航《统计学习方法》 清华大学出版社HMM与分词、词性标注、命名实体识别:http://www.hankcs.com/nlp/hmm-and-segmentation-tagging-named-entity-recognition.htmlHidden Markov Models 1: http://docplayer.net/21306742-Hidden-markov-models-1.html吴军 《数学之美》 人民邮电出版社

文章评论

Top