维特比算法代码

article/2025/10/3 22:48:25

维特比算法实现python语言版

本文主要写一个关于维特比算法的代码,具体理论请参考一文搞懂HMM(隐马尔可夫模型):

  HMM(隐马尔可夫模型)是用来描述隐含未知参数的统计模型,举一个经典的例子:一个东京的朋友每天根据天气{下雨,天晴}决定当天的活动{公园散步,购物,清理房间}中的一种,我每天只能在twitter上看到她发的推“啊,我前天公园散步、昨天购物、今天清理房间了!”,那么我可以根据她发的推特推断东京这三天的天气。在这个例子里,显状态是活动,隐状态是天气。

任何一个HMM都可以通过下列五元组来描述:

:param obs:观测序列
:param states:隐状态
:param start_p:初始概率(隐状态)
:param trans_p:转移概率(隐状态)
:param emit_p: 发射概率 (隐状态表现为显状态的概率)
隐马尔可夫模型五元组
伪码如下:

states = ('Rainy', 'Sunny')
observations = ('walk', 'shop', 'clean')
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
transition_probability = {'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},}
emission_probability = {'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
}
... prompt'''

求解最可能的天气:

  求解最可能的隐状态序列是HMM的三个典型问题之一,通常用维特比算法解决。维特比算法就是求解HMM上的最短路径(-log(prob),也即是最大概率)的算法。

稍微用中文讲讲思路,很明显,第一天天晴还是下雨可以算出来:

  定义V[时间][今天天气] = 概率,注意今天天气指的是,前几天的天气都确定下来了(概率最大)今天天气是X的概率,这里的概率就是一个累乘的概率了。

  因为第一天我的朋友去散步了,所以第一天下雨的概率V[第一天][下雨] = 初始概率[下雨] * 发射概率[下雨][散步] = 0.6 * 0.1 = 0.06,同理可得V[第一天][天晴] = 0.24 。从直觉上来看,因为第一天朋友出门了,她一般喜欢在天晴的时候散步,所以第一天天晴的概率比较大,数字与直觉统一了。

  从第二天开始,对于每种天气Y,都有前一天天气是X的概率 * X转移到Y的概率 * Y天气下朋友进行这天这种活动的概率。因为前一天天气X有两种可能,所以Y的概率有两个,选取其中较大一个作为V[第二天][天气Y]的概率,同时将今天的天气加入到结果序列中

  比较V[最后一天][下雨]和[最后一天][天晴]的概率,找出较大的哪一个对应的序列,就是最终结果。
python代码如下:

# -*- coding: utf-8 -*-
from collections import defaultdictstates =                    ("Rainy", "Sunny")
observations =              ("Walk", "Shop", "Walk", "Shop", "Clean", "Walk", "Shop", "Walk")
start_probability =         {"Rainy": 0.6, "Sunny": 0.4}
transition_probability = {"Rainy": {"Rainy": 0.7, "Sunny": 0.3},"Sunny": {"Rainy": 0.4, "Sunny": 0.6},}emission_probability =   {"Rainy": {"Walk": 0.1, "Shop": 0.4, "Clean": 0.5},"Sunny": {"Walk": 0.6, "Shop": 0.3, "Clean": 0.1},}# 利用动态规划求解最佳路径
def compute(obs, states, start_p, trans_p, emit_p):# [{}, {}, {}]  长度与obs相同, 保存每条观测路径上面的各种天气的最佳概率v = [{} for _ in range(len(obs))]# {"state1": [], "state2": []}   长度与states 相同path = defaultdict(list)for state in states:v[0][state] = start_p[state] * emit_p[state][obs[0]]#path[state] = ["" for _ in range(len(obs))]path[state].append(state)# 以时间循环,从第一天开始循环for t in range(1, len(obs)):# print obs[t]for y1 in states :   # 从path中取路径,作为上一个开始的路径max_prob = -1for y0 in v[t-1]:nprob = v[t - 1][y0] * trans_p[y0][y1] * emit_p[y1][obs[t]]if nprob > max_prob:# 暂时记录到y1状态节点最后的概率max_prob = nprob# 暂时记录到y1状态节点的上一个y0节点max_state = y0# 保存到当前的y1状态的最好的概率值v[t][y1] = max_prob# 到上一条路径与当前的y1链接起来,作为y1状态的最好路径newpath = [] for state1 in path[max_state]:newpath.append(state1)newpath.append(y1)path[y1] = newpath# 寻找最终概率最大的路径prob = -1for y1 in states :if v[len(obs) - 1][y1] > prob:prob = v[len(obs) - 1][y1]state = y1# 返回路径最大的路径return path[state]if __name__ == "__main__":max_path = compute(observations, states, start_probability, transition_probability, emission_probability)for state in max_path :print state

最终运行结果为:
Sunny
Sunny
Sunny
Rainy
Rainy
Rainy
Sunny
Sunny
Sunny

大部分抄来的,写得不好,请轻轻拍砖。


http://chatgpt.dhexx.cn/article/S8mP1NW4.shtml

相关文章

维特比算法学习

参考文章1: 简直不要太通俗易懂,这篇文章,很值得看 参考文章2: 解释一些概念性的问题,我把他的一些内容写下来 维特比(Viterbi)算法的核心是动态规划。 对于 HMM 而言,其中一个重要的任务就是要找出最有…

5分钟理解维特比算法

安德鲁维特比老人家发明了维特比算法,用非常巧妙的方法简化了隐马尔可夫第二个问题运算过程。维特比先生后来发明了CDMA技术并与人一起创办了高通公司,高通现在是通信巨头,不生产产品却每年收取大量的专利费。 下面我们用简单的例子&#xff…

Viterbi-Algorithm(维特比算法)

Viterbi-Algorithm 维特比算法是一个特殊但应用最广的动态规划算法。利用动态规划,可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图-篱笆网了(Lattice)的有向图最短路径问题而提出来的。它之所以重要,是因为…

NLP学习笔记06-维特比算法

一序 本文属于NLP学习笔记系列。 上一篇整理了前向最大匹配算法与所有组合算法缺点(时间复杂度太高了)。 二 维特比算法 log(x*y*z) log(x)log(y)log(z) 概率上为了避免小数练乘出现的超范围溢出,改用log,改用-log,使得原来求概…

HMM-维特比算法

HMM-维特比算法(viterbi) HMM回顾隐马科夫链解法:维特比算法(Viterbi) HMM回顾 最终的公式可以解释主要分为两个部分: P(xi|yi),发射概率,字面意思是从一个词性中发射/生成出某一个…

Viterbi算法(维特比算法)

维特比算法背景: 安德鲁维特比(Andrew J. Viterbi),CDMA之父,IEEE Fellow,高通公司创始人之一,高通首席科学家。他开发了卷积码编码的最大似然算法而享誉全球。1991年香农奖(Claude …

HMM+维特比算法

一、简介 Viterbi 算法 考虑到穷举方法的缺点,可以采用:Viterbi 算法: 动态搜索最优状态序列,这样每个节点保存的是到当前节点的局部最优概率;依据最后一个时刻中概率最高的状态,逆向找其路径中的上一个最大部分最优路…

维特比算法的java实现_原创:维特比算法

看了宗成庆博士的《统计自然语言处理(中文信息处理)》的第六章,对维特比算法有着非常精辟的讲解。把其中的讲解上传上来,个人感觉比较正统。 今天用Java实现了这个算法,也可以转换为C代码: package com.nlp.hmm.algorithm.viterbi…

隐马尔可夫(HMM)、前/后向算法、Viterbi算法 再次总结

本总结是是个人为防止遗忘而作,不得转载和商用。 说明:此篇是作者对“隐马尔可夫模型”的第二次总结,因此可以算作对上次总结的查漏补缺以及更进一步的理解,所以很多在第一次总结中已经整理过的内容在本篇中将不再重复&#xff0c…

维特比(Viterbi)算法

维特比算法 (Viterbi algorithm) 是机器学习中应用非常广泛的动态规划算法,在求解隐马尔科夫、条件随机场的预测以及seq2seq模型概率计算等问题中均用到了该算法。实际上,维特比算法不仅是很多自然语言处理的解码算法,也是现代数字通信中使用…

小白给小白详解维特比算法(一)

小白给小白详解维特比算法(一) 小白给小白详解维特比算法一 篱笆网络Lattice的最短路径问题 这个问题长什么样子这个问题难在哪里简化成这个模样你总能回答了吧下一步我们该干什么 别倒立了我们再从头想一下这个问题 我们是怎么走过来的来我们从A开始走这…

viterbi算法

维特比算法(Viterbi Algorithm) 标签(空格分隔): 未分类 维特比算法(Viterbi Algorithm) viterbi算法用于寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) 对于…

维特比算法

1. 概述 维特比算法是安德鲁.维特比(Andrew Viterbi)于1967年为解决通信领域中的解码问题而提出的,它同样广泛用于解决自然语言处理中的解码问题,隐马尔可夫模型的解码是其中典型的代表。无论是通信中的解码问题还是自然语言处理中的解码问题&#xff0c…

维特比算法(Viterbi algorithm)

一、维特比算法(Viterbi)原理以及简单实现 维特比算法(Viterbi algorithm)是一种动态规划算法。它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列,特别是在马尔可夫信息源上下文和隐马尔可夫模型中。 维特比算法实际是用动…

机器学习:维特比算法(Viterbi Algorithm)

一、维特比算法(Viterbi Algorithm)讲解方式01:篱笆网络(Lattice)的最短路径问题 已知下图的篱笆网络,每个节点之间的数字表示相邻节点之间的距离,举个例子来说,如果我走&#xff0…

字符串匹配原理及实现(C++版)

字符串匹配原理及实现(C版) 1. 字符串匹配概念2. BF2.1 原理2.2 代码实现 3. KMP3.1 原理3.2 代码实现 4. BM4.1 坏字符4.2 好后缀4.3 代码实现 1. 字符串匹配概念 在查找操作中,我们用到很重要的概念就是字符串匹配,所谓字符串匹…

C++之单字符串匹配问题

有很多算法可以解决单模式匹配问题。而根据在文本中搜索模式串方式的不同,我们可以将单模式匹配算法分为以下几种: 基于前缀搜索方法:在搜索窗口内从前向后(沿着文本的正向)逐个读入文本字符,搜索窗口中文…

字符串——字符串匹配

文章目录 字符串匹配一、基本概念字符串匹配问题符号和术语后缀重叠引理 二、朴素字符串匹配算法三、Rabin-Karp算法(字符串Hash算法)进制Hash质数Hash 四、利用有限自动机进行字符串匹配有限自动机字符串匹配自动机计算状态转移函数代码 五、Knuth-Morris-Pratt算法模式的前缀…

朴素字符串匹配

描述 字符串匹配问题的形式定义: 文本(Text)是一个长度为 n 的字符串:T;模式(Pattern)是一个长度为 m 且 m≤n 的字符串:P; T 和 P 中的元素都属于有限的字母表 Σ 表; 有效位移 (Valid Shift): 如果 0≤ s ≤n-m,并且 T[s1…sm] P[1…m]&#xff0c…

算法之字符串匹配一

目录 前言: BF算法: RK算法 总结: 参考资料 前言: 字符串匹配指的是一个短点的字符串与一个长点的字符串进行匹配,并确认短的字符串是否在长的字符串中存在。匹配算法有很多,本文介绍两种简单、容易…