Python实现隐马尔可夫模型的前向后向算法的示例代码

本篇文章对隐马尔可夫模型的前向和后向算法进行了Python实现,并且每种算法都给出了循环和递归两种方式的实现。

前向算法Python实现

循环方式

import numpy as np
def hmm_forward(Q, V, A, B, pi, T, O, p):
  """
  :param Q: 状态集合
  :param V: 观测集合
  :param A: 状态转移概率矩阵
  :param B: 观测概率矩阵
  :param pi: 初始概率分布
  :param T: 观测序列和状态序列的长度
  :param O: 观测序列
  :param p: 存储各个状态的前向概率的列表,初始为空
  """
  for t in range(T):
    # 计算初值
    if t == 0:
      for i in range(len(Q)):
        p.append(pi[i] * B[i, V[O[0]]])
    # 初值计算完毕后,进行下一时刻的递推运算
    else:
      alpha_t_ = 0
      alpha_t_t = []
      for i in range(len(Q)):
        for j in range(len(Q)):
          alpha_t_ += p[j] * A[j, i]
        alpha_t_t.append(alpha_t_ * B[i, V[O[t]]])
        alpha_t_ = 0
      p = alpha_t_t
  return sum(p)
# 《统计学习方法》书上例10.2
Q = [1, 2, 3]
V = {'红':0, '白':1}
A = np.array([[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]])
B = np.array([[0.5, 0.5], [0.4, 0.6], [0.7, 0.3]])
pi = [0.2, 0.4, 0.4]
T = 3
O = ['红', '白', '红']
p = []
print(hmm_forward(Q, V, A, B, pi, T, O, p)) # 0.130218

递归方式

import numpy as np
def hmm_forward_(Q, V, A, B, pi, T, O, p, T_final):
  """
  :param T_final:递归的终止条件
  """
  if T == 0:
    for i in range(len(Q)):
      p.append(pi[i] * B[i, V[O[0]]])
  else:
    alpha_t_ = 0
    alpha_t_t = []
    for i in range(len(Q)):
      for j in range(len(Q)):
        alpha_t_ += p[j] * A[j, i]
      alpha_t_t.append(alpha_t_ * B[i, V[O[T]]])
      alpha_t_ = 0
    p = alpha_t_t
  if T >= T_final:
    return sum(p)
  return hmm_forward_(Q, V, A, B, pi, T+1, O, p, T_final)

Q = [1, 2, 3]
V = {'红':0, '白':1}
A = np.array([[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]])
B = np.array([[0.5, 0.5], [0.4, 0.6], [0.7, 0.3]])
pi = [0.2, 0.4, 0.4]
T = 0
O = ['红', '白', '红']
p = []
T_final = 2 # T的长度是3,T的取值是(0时刻, 1时刻, 2时刻)
print(hmm_forward_(Q, V, A, B, pi, T, O, p, T_final))

后向算法Python实现

循环方式

import numpy as np
def hmm_backward(Q, V, A, B, pi, T, O, beta_t, T_final):
  for t in range(T, -1, -1):
    if t == T_final:
      beta_t = beta_t
    else:
      beta_t_ = 0
      beta_t_t = []
      for i in range(len(Q)):
        for j in range(len(Q)):
          beta_t_ += A[i, j] * B[j, V[O[t + 1]]] * beta_t[j]
        beta_t_t.append(beta_t_)
        beta_t_ = 0
      beta_t = beta_t_t
    if t == 0:
      p=[]
      for i in range(len(Q)):
        p.append(pi[i] * B[i, V[O[0]]] * beta_t[i])
      beta_t = p
  return sum(beta_t)
# 《统计学习方法》课后题10.1
Q = [1, 2, 3]
V = {'红':0, '白':1}
A = np.array([[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]])
B = np.array([[0.5, 0.5], [0.4, 0.6], [0.7, 0.3]])
pi = [0.2, 0.4, 0.4]
T = 3
O = ['红', '白', '红', '白']
beta_t = [1, 1, 1]
T_final = 3
print(hmm_backward_(Q, V, A, B, pi, T, O, beta_t, T_final)) # 0.06009

递归方式

import numpy as np
def hmm_backward(Q, V, A, B, pi, T, O, beta_t, T_final):
  if T == T_final:
    beta_t = beta_t
  else:
    beta_t_ = 0
    beta_t_t = []
    for i in range(len(Q)):
      for j in range(len(Q)):
        beta_t_ += A[i, j] * B[j, V[O[T+1]]] * beta_t[j]
      beta_t_t.append(beta_t_)
      beta_t_ = 0
    beta_t = beta_t_t
  if T == 0:
    p=[]
    for i in range(len(Q)):
      p.append(pi[i] * B[i, V[O[0]]] * beta_t[i])
    beta_t = p
    return sum(beta_t)
  return hmm_backward(Q, V, A, B, pi, T-1, O, beta_t, T_final)
jpgQ = [1, 2, 3]
V = {'红':0, '白':1}
A = np.array([[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]])
B = np.array([[0.5, 0.5], [0.4, 0.6], [0.7, 0.3]])
pi = [0.2, 0.4, 0.4]
T = 3
O = ['红', '白', '红', '白']
beta_t = [1, 1, 1]
T_final = 3
print(hmm_backward_(Q, V, A, B, pi, T, O, beta_t, T_final)) # 0.06009

这里我有个问题不理解,这道题的正确答案应该是0.061328,我计算出的答案和实际有一点偏差,我跟踪了代码的计算过程,发现在第一次循环完成后,计算结果是正确的,第二次循环后的结果就出现了偏差,我怀疑是小数部分的精度造成,希望有人能给出一个更好的解答,如果是代码的问题也欢迎指正。

以上所述是小编给大家介绍的Python实现隐马尔可夫模型的前向后向算法,希望对大家有所帮助!

(0)

相关推荐

  • python sklearn常用分类算法模型的调用

    本文实例为大家分享了python sklearn分类算法模型调用的具体代码,供大家参考,具体内容如下 实现对'NB', 'KNN', 'LR', 'RF', 'DT', 'SVM','SVMCV', 'GBDT'模型的简单调用. # coding=gbk import time from sklearn import metrics import pickle as pickle import pandas as pd # Multinomial Naive Bayes Classifier d

  • python基于隐马尔可夫模型实现中文拼音输入

    在网上看到一篇关于隐马尔科夫模型的介绍,觉得简直不能再神奇,又在网上找到大神的一篇关于如何用隐马尔可夫模型实现中文拼音输入的博客,无奈大神没给可以运行的代码,只能纯手动网上找到了结巴分词的词库,根据此训练得出隐马尔科夫模型,用维特比算法实现了一个简单的拼音输入法.githuh地址:https://github.com/LiuRoy/Pinyin_Demo 原理简介隐马尔科夫模型 抄一段网上的定义: 隐马尔可夫模型 (Hidden Markov Model) 是一种统计模型,用来描述一个含有隐含未

  • Python实现隐马尔可夫模型的前向后向算法的示例代码

    本篇文章对隐马尔可夫模型的前向和后向算法进行了Python实现,并且每种算法都给出了循环和递归两种方式的实现. 前向算法Python实现 循环方式 import numpy as np def hmm_forward(Q, V, A, B, pi, T, O, p): """ :param Q: 状态集合 :param V: 观测集合 :param A: 状态转移概率矩阵 :param B: 观测概率矩阵 :param pi: 初始概率分布 :param T: 观测序列和状态

  • python实现隐马尔科夫模型HMM

    一份完全按照李航<<统计学习方法>>介绍的HMM代码,供大家参考,具体内容如下 #coding=utf8 ''''' Created on 2017-8-5 里面的代码许多地方可以精简,但为了百分百还原公式,就没有精简了. @author: adzhua ''' import numpy as np class HMM(object): def __init__(self, A, B, pi): ''''' A: 状态转移概率矩阵 B: 输出观察概率矩阵 pi: 初始化状态向量 '

  • Python一阶马尔科夫链生成随机DNA序列实现示例

    目录 1. 原理 2. 代码实现 3. 运行结果 1. 原理 对于DNA序列,一阶马尔科夫链可以理解为当前碱基的类型仅取决于上一位碱基类型.如图1所示,一条序列的开端(由B开始)可能是A.T.G.C四种碱基(且可能性相同,均为0.25),若序列的某一位是A,则下一位碱基是A.T.G.C的概率分别为0.25.0.20.0.20.0.20,下一位无碱基(即序列结束,状态为E)的概率为0.15. 图1 DNA序列的一阶马尔科夫链 2. 代码实现 以下代码运行于Jupyter Notebook (Pyt

  • Python实现异常检测LOF算法的示例代码

    目录 背景 LOF算法 1.k邻近距离 2.k距离领域 3.可达距离 4.局部可达密度 5.局部异常因子 LOF算法流程 LOF优缺点 Python实现LOF PyOD Sklearn 大家好,我是东哥. 本篇和大家介绍一个经典的异常检测算法:局部离群因子(Local Outlier Factor),简称LOF算法. 背景 Local Outlier Factor(LOF)是基于密度的经典算法(Breuning et. al. 2000), 文章发表于 SIGMOD 2000, 到目前已经有 3

  • 用python实现前向分词最大匹配算法的示例代码

    理论介绍 分词是自然语言处理的一个基本工作,中文分词和英文不同,字词之间没有空格.中文分词是文本挖掘的基础,对于输入的一段中文,成功的进行中文分词,可以达到电脑自动识别语句含义的效果.中文分词技术属于自然语言处理技术范畴,对于一句话,人可以通过自己的知识来明白哪些是词,哪些不是词,但如何让计算机也能理解?其处理过程就是分词算法. 可以将中文分词方法简单归纳为: 1.基于词表的分词方法 2.基于统计的分词方法 3.基于序列标记的分词方法 其中,基于词表的分词方法最为简单,根据起始匹配位置不同可以分

  • Python&Matlab实现灰狼优化算法的示例代码

    目录 1 灰狼优化算法基本思想 2 灰狼捕食猎物过程 2.1 社会等级分层 2.2 包围猎物 2.3 狩猎 2.4 攻击猎物 2.5 寻找猎物 3 实现步骤及程序框图 3.1 步骤 3.2 程序框图 4 Python代码实现 5 Matlab实现 1 灰狼优化算法基本思想 灰狼优化算法是一种群智能优化算法,它的独特之处在于一小部分拥有绝对话语权的灰狼带领一群灰狼向猎物前进.在了解灰狼优化算法的特点之前,我们有必要了解灰狼群中的等级制度. 灰狼群一般分为4个等级:处于第一等级的灰狼用α表示,处于第

  • Python实现12种降维算法的示例代码

    目录 为什么要进行数据降维 数据降维原理 主成分分析(PCA)降维算法 其它降维算法及代码地址 1.KPCA(kernel PCA) 2.LDA(Linear Discriminant Analysis) 3.MDS(multidimensional scaling) 4.ISOMAP 5.LLE(locally linear embedding) 6.t-SNE 7.LE(Laplacian Eigenmaps) 8.LPP(Locality Preserving Projections) 网

  • Python实现K-近邻算法的示例代码

    目录 一.介绍 二.k-近邻算法的步骤 三.Python 实现 四.约会网站配对效果判定 五.手写数字识别 六.算法优缺点 优点 缺点 一.介绍 k-近邻算法(K-Nearest Neighbour algorithm),又称 KNN 算法,是数据挖掘技术中原理最简单的算法. 工作原理:给定一个已知标签类别的训练数据集,输入没有标签的新数据后,在训练数据集中找到与新数据最邻近的 k 个实例,如果这 k 个实例的多数属于某个类别,那么新数据就属于这个类别.简单理解为:由那些离 X 最近的 k 个点

  • python实现经典排序算法的示例代码

    以下排序算法最终结果都默认为升序排列,实现简单,没有考虑特殊情况,实现仅表达了算法的基本思想. 冒泡排序 内层循环中相邻的元素被依次比较,内层循环第一次结束后会将最大的元素移到序列最右边,第二次结束后会将次大的元素移到最大元素的左边,每次内层循环结束都会将一个元素排好序. def bubble_sort(arr): length = len(arr) for i in range(length): for j in range(length - i - 1): if arr[j] > arr[j

随机推荐