在 HMM 中查找前 k 个维特比路径

2023-12-25

我需要编写一个算法来查找 HMM 中的前 k 个维特比路径(使用常规维特比算法来查找最佳路径)。

我想我可能需要为每个状态 N 保存一个大小为 k 的列表 V_t,N,其中包含以状态 N 结尾的前 K 个路径,但我不太确定如何跟踪该列表。 有任何想法吗?谢谢


我们可以小心地解决这个问题。通过查看 hmm 的网格结构最容易看出:

在此示例中,隐藏状态为 00、01、10、11,将这四个状态的集合表示为 S。观察结果未显示,但假设它们为 0,1。

假设我们有正确的转移矩阵:

transition[4][4]

发射概率:

emissions[4][2]

和初始概率:

p[2]

因此,每一列都代表隐藏状态,维特比的目标是计算给定观察结果的最可能的隐藏状态序列。现在让 alpha(i, t) = 隐藏状态序列在时间 t 处于状态 i(i 是 00、01、10、11 之一)的最大概率,其中时间 t 的观测值是 o_t(o_t 是 1) 0, 1)。将第一个观察值表示为 o_1。它可以有效地计算为:

alpha(i, 1) = p[i] * emissions[i][o_1]
alpha(i, t) = emissions[i][o_t] * max_{k in states} (alpha(k, t-1) * transition[k][i]) 

为了找到最佳路径,我们在 alpha(i, t) 步骤中保持指针向后,指向上面最大化 max 函数的状态。最后,我们只检查状态中的所有 alpha(i, T) 和 for i,并找到哪一个最大,然后跟踪它以获得最可能的状态序列。

现在我们需要扩展它来存储顶级 k 路径。目前,在每个 alpha(i,t) 中,我们仅存储一个父级。然而,假设我们存储了前 k 个前辈。因此,每个 alpha(i, t) 不仅对应于最可能的值及其转换的节点,还对应于它可能转换的前 k 个节点的列表及其按排序顺序排列的值。

这很容易做到,因为我们不是执行 max 操作,而是只取一个前面的节点,而是取前 k 个前面的节点并存储它们。现在,对于基本情况,没有前面的节点,因此 alpha(i, 1) 仍然只是一个值。当我们到达任意列(例如 t)并想要找到以该列中的节点 (i) 结束的前 k 条路径时,我们必须找到来自前 k 条前驱路径以及从它们出发的前 k 条路径。

这就好像我们有以下问题,一个大小为 4 x k 的矩阵 m,其中一行表示先前的状态,m[state] 表示结束于该位置的路径的前 k 个概率。这样m的每一行都按照从大到小排序,现在的问题就变成了find:

Best_K_Values(t, i) = Top K over all i,preceding_state,k (emissions[i][o_t] * m[preceding_state][k] * transition[preceding_state][i])

现在这看起来令人畏惧,但需要一些时间来理解它,我们通常可以使用 O(4 log k) 或 O(numStates log k) 的堆来解决排序矩阵问题中的 top k。

看看这个细微的变化排序矩阵中第 K 个最小元素 https://stackoverflow.com/questions/15179536/kth-smallest-element-in-sorted-matrix,请注意,在我们的例子中,列没有排序,但其中的想法仍然适用。

如果您仍在阅读,请注意此方法的总体复杂度为 O((numStates log k) * numStates * t) = O(numStates^2 * t * log k) (我相信这是正确的复杂度)。

这可能很难理解,但如果您有任何疑问,或者我做错了什么,请告诉我。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

在 HMM 中查找前 k 个维特比路径 的相关文章

  • 如何选择部分密集数据集的均匀分布子集?

    P是一个 n d 矩阵 持有nd 维样本 P某些地区的密度是其他地区的几倍 我想选择一个子集P其中任意样本对之间的距离大于d0 并且我需要将其传播到整个区域 所有样本都具有相同的优先级 无需优化任何内容 例如覆盖面积或成对距离之和 这是执行
  • 获取无平方数的列表

    获得该值的一种方法是自然数 1 n 我们对每个因子进行因式分解 看看它们是否有重复的质因数 但这对于大的情况来说会花费很多时间n 那么有没有更好的方法从 1 中获取无平方数n 您可以使用埃拉托斯特尼筛法的修改版本 取一个布尔数组 1 n 预
  • 如何对数组进行排序(索引)以使用这些索引将原始数组从最小到最大值排序

    例如我有这个数组 int a 6 10 16 11 7 12 3 9 8 5 我想像这样对其索引进行排序 6 9 0 4 8 7 1 3 5 2 所以我可以使用索引将 a 从最小到最大值排序 在我的代码中我得到了这个 6 9 4 8 7 4
  • 当目标是查找某个字符串的所有出现情况时,KMP 最坏情况的复杂度是多少?

    我还想知道哪种算法在查找另一个字符串中所有出现的字符串时具有最坏情况的复杂性 博耶 摩尔算法似乎具有线性时间复杂度 KMP 算法在查找字符串中所有出现的模式时具有线性复杂度 如 Boyer Moore 算法1 如果您尝试在 aaaaaaaa
  • 检查数独字段的很酷的算法?

    有谁知道一个简单的算法来检查数独配置是否有效 我想出的最简单的算法是 对于大小为 n 的板 伪代码 for each row for each number k in 1 n if k is not in the row using ano
  • 我想优化这个短循环

    我想优化这个简单的循环 unsigned int i while j 0 j is an unsigned int with a start value of about N 36 000 000 float sub 0 i 1 unsig
  • 稀疏矩阵中的最大和子矩形

    求一个子矩形中的最大和NxN矩阵可以完成O n 3 正如其他帖子中指出的 使用 2 d kadane 算法的时间 然而 如果矩阵是稀疏的 具体来说O n 非零条目 可以O n 3 时间被打败了吗 如果有帮助的话 对于我感兴趣的当前应用程序
  • 交换两个向量之间的值,使两个向量的 max_element 之和最小

    这是 Codechef 的问题 但请耐心等待 https www codechef com ZCOPRAC problems ZCO16001 https www codechef com ZCOPRAC problems ZCO16001
  • 合并字符数组中的最小重复次数

    假设我有两个数组 我想合并它们 以便合并后的数组具有最小重复次数 例如 x x 是重复 arr1 x d d m f m arr2 d d x f f m 唯一的条件是在合并数组中 元素来自arr1 and arr2必须出现在各自的订单中a
  • 如何从二叉搜索树中均匀随机地返回节点?

    给定一个 BST 可能平衡也可能不平衡 如何能够均匀地随机返回 任何 节点 一个限制是您不能使用外部索引数据结构 您必须以每个节点都有平等被访问的机会的方式遍历树 这个问题让我困惑了好一阵子 如果我们确实可以使用外部哈希表 指针 我们可以对
  • 搜索/排序算法 - 是否有类似 GoF 的列表?

    我是一名自学成才的开发人员 坦率地说 我不太擅长找出在任何特定情况下使用哪种搜索或排序算法 我只是想知道是否有设计模式 esque 列出了以太坊中可用的常见算法 供我添加书签 就像是 算法名称 带有别名 如果有的话 它解决的问题 大O成本
  • 用 Java 创建迷宫求解算法

    我被分配了用 Java 创建迷宫求解器的任务 这是任务 Write an application that finds a path through a maze The maze should be read from a file A
  • C 中的菱形数组排序

    我有以下 C 语言作业 我基本上需要一种方法而不是解决方案 我们有一个 13 x 13 的数组 在数组中 我们有一个需要考虑的菱形形状 该菱形之外的所有内容都初始化为 1 不重要 下面的 5 x 5 数组示例 x x 1 x x x 2 2
  • Exposé 布局算法

    我正在制作一些项目 其布局类似于 Mac OS X 在 Expos 中对窗口所做的操作 它适应项目的长宽比和可用区域的长宽比 基本上 可用区域分为行和列 每个单元格 行和列的交集 中放置一个项目 这些项目必须保持其纵横比 此处width h
  • 使用FFT算法计算

    给定在平面上的点 1 0 2 0 n 0 上发现的一组 n 个粒子电荷载流子 在 i 0 点发现的粒子电荷记为 Qi 作用在粒子上的力由以下公式给出 C is a Coulomb s constant 给出一个算法来计算 Fi 对于总复杂度
  • 在 O(n) 时间内找到 n x n 矩阵中的局部最小值

    所以 这不是我的家庭作业问题 而是取自 coursera 算法和数据结构课程的未评分作业 现已完成 You are given an n by n grid of distinct numbers A number is a local m
  • 编程 Pearls - 随机选择算法

    Programming Pearls 第一版第 120 页介绍了从 N 个整数总体中选择 M 个等概率随机元素的算法 InitToEmpty Size 0 While Size lt M do T RandInt 1 N if not Me
  • 使用C标准数学库精确计算标准正态分布的CDF

    标准 C 数学库不提供计算标准正态分布 CDF 的函数 normcdf 然而 它确实提供了密切相关的函数 误差函数 erf 和互补误差函数 erfc 计算 CDF 的最快方法通常是通过误差函数 使用预定义常量 M SQRT1 2 来表示 d
  • 快速搜索压缩文本文件

    我需要能够在大量压缩文件 txt 中搜索文本 压缩可能会改变为其他东西 甚至成为专有的 我想避免解压所有文件并压缩 编码 搜索字符串并在压缩文件中搜索 这应该可以通过对所有文件使用相同的码本使用霍夫曼压缩来实现 我不想重新发明轮子 所以 任
  • 如何将一组重叠范围划分为不重叠范围?

    假设您有一组范围 0 100 一 0 75 b 95 150 c 120 130 d 显然 这些范围在某些点上重叠 您将如何剖析这些范围以生成不重叠范围的列表 同时保留与其原始范围相关的信息 在本例中为范围后面的字母 例如 运行算法后的上述

随机推荐

  • oauth2 框:grant_type 参数无效或参数丢失

    我不知道我做错了什么 但每次我尝试获取令牌 当然是在用户身份验证之后 结果总是 Invalid grant typeparameter orparametermissing 可能与Box API 在获取访问令牌时始终返回无效的 grant
  • 如何在 React 的 render() 中包含 Font Awesome 图标

    每当我尝试在 React 中使用 Font Awesome 图标时render 尽管它可以在普通 HTML 中工作 但它不会显示在生成的网页上 render function return div i class fa fa spinner
  • Google 地图上的移动位置跟踪

    我需要为我的网站开发一项功能 用户可以通过该功能跟踪 Google 地图上的任何手机号码 就像下面的链接一样 转到以下链接并输入9810098109文本框中的数字以查找其在地图上的位置 http wwwa way2sms com jsp L
  • Android:动画循环进度可绘制

    我需要一个看起来像旋转进度圈的可绘制对象 我想在 GridView 内的 ImageView 等中使用该可绘制对象 因此 根据其他帖子 我从文件夹 sdk platforms android xx data res drawable 中获取
  • Tensorflow错误:DLL加载失败:找不到指定的过程

    我尝试在我的windows8 1 64位python3 6 0中使用pip安装tensorflow cpu 使用pip install tensorflow但它给了我这个错误 Traceback most recent call last
  • jq绘图到图像

    我知道这个问题已经存在 但我认为它没有得到正确的回答 到目前为止 我正在使用这种方法 对于我必须做的任何情节 它都 100 有效 请评论代码的效率等 我想知道其中是否还有错误 非常感谢 function jqplotToImg obj va
  • 哪里应该使用PageViewer?

    我已经实施了浏览器和数量Fragment作为孩子 这里每个孩子都会覆盖自己的onAttach onCreateView onViewCreated and setUserVisibleHint 在我的应用程序中 导航行为是随机的 并非每次都
  • 是否可以将矩阵映射到 igraph 对象?

    我有一个矩阵A定义自相交多边形的有序线段 A lt t matrix c 0 0 1 0 1 2 2 2 2 1 0 1 0 4 1 4 1 2 2 2 2 3 0 3 0 0 nrow 2 par mfrow c 1 3 plot A c
  • 使用Python向远程进程发送信号

    有两台机器 其中一台有脚本wait for signal sh 第二个有一个名为controller py 每个脚本的代码如下所示 目的controller py是产生一个调用的子进程wait for signal sh脚本通过ssh 当控
  • UILabel:如何设置字体大小?

    如何设置字体大小UILabel My code UILabel myView UILabel alloc initWithFrame RectFrame myView setBackgroundColor UIColor blueColor
  • 失去焦点时窗口闪烁?

    我一直在开发基于 C 的 Windows 窗体应用程序 我需要一些帮助 我正在尝试重新创建大多数 Windows 应用程序在窗体失去父窗体焦点时出现的窗口闪烁 我可以解释这一点的最好方法是打开计算器 打开帮助窗口并尝试单击计算器 然后帮助窗
  • 如何获取正在运行的 EC2 现货实例的价格?

    我正在尝试使用 boto3 api 创建 ec2 现货实例 到目前为止 我能够获取现货实例历史价格 启动现货实例等 但我不知道如何使用 boto api 获取我们为现货实例支付的价格 有人知道怎么做吗 Thanks Update See S
  • 如何检查 CMakeLists.txt 中的 SDL2_ttf?

    我目前正在使用 SDL2 ttf 库编写一个 SDL2 程序 并希望在 CMakeLists txt 中添加对其的检查 我怎么做 我正在使用 CMake 3 1 FindSDL ttf 不适用于 SDL2 因此您必须使用第三方选项 我用过这
  • 每天更改图标

    就像 iPhone 和 iPod 上的日历应用程序一样 如何每天更改图标 我认为这是针对 iOS 应用程序的 答案是 你不能 日历应用程序可以访问 iOS 中的功能 而我们普通开发人员无法访问这些功能 你也许可以用越狱的手机来实现这一点 但
  • 在 R Markdown 文档中,“包含”docx 输出?

    在下面的 Rmd 中我有includes in header 用于 pdf 输出和includes before body 用于 docx 输出 docx 输出有类似的东西吗 我当前的黑客是包括生成 docx 输出时有条件地代码块 但我不想
  • CL 格式秘诀:将 nil 作为值处理

    我一直在寻找格式化食谱 但我找不到我要找的东西 format nil CONTROL STRING day name num apples 假设我不想改变上面形式中的参数 只是CONTROL STRING day and num apple
  • Google 地图 API V3 - 自定义图块

    我目前正在开发 Google Maps API V3here http apps humannetworklabs com GoogleMapAPI html 如果在 21 到 23 之间缩放 地图上将会出现图像叠加 该图像加载时间太长 我
  • Android 振动已弃用。如何在 Android>= API 26 中使用 VibrationEffect?

    我正在使用安卓的VIBRATOR SERVICE为按钮触摸提供触觉反馈 Vibrator getSystemService VIBRATOR SERVICE vibrate 300 Android Studio 给我警告该方法vibrate
  • Java AES CBC 解密

    PHP 加密函数 privateKey 1234567812345678 iv 1234567812345678 data Test string encrypted mcrypt encrypt MCRYPT RIJNDAEL 128 p
  • 在 HMM 中查找前 k 个维特比路径

    我需要编写一个算法来查找 HMM 中的前 k 个维特比路径 使用常规维特比算法来查找最佳路径 我想我可能需要为每个状态 N 保存一个大小为 k 的列表 V t N 其中包含以状态 N 结尾的前 K 个路径 但我不太确定如何跟踪该列表 有任何