在 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 个维特比路径 的相关文章

  • 快速约会算法

    我在一家咨询公司工作 大部分时间都在客户所在地 正因为如此 我很少见到同事 为了更好地了解彼此 我们将安排一个晚宴 会有很多小桌子 方便人们聊天 为了在聚会期间与尽可能多的不同的人交谈 每个人都必须每隔一段时间 比如每小时 换一张桌子 如何
  • 使用并集查找(又名不相交集)检测图是否是二分图

    我正在 Spoj 上做一个问题 基本上可以简化为检测图是否是二分图 我正在尝试使用 dfs 为图表着色 但它太慢了 有人评论这个 没有 bfs 没有 dfs 没有二部图 简单的并查集就可以做到 确实速度很快 提示 1 偶数长度的环不会影响两
  • C# 中的 strstr() 等效项

    我有两个byte 我想找到第二个的第一次出现byte 在第一个byte 或其中的一个范围 我不想使用字符串来提高效率 翻译第一个byte to a string会效率低下 基本上我相信就是这样strstr 在 C 中做 最好的方法是什么 这
  • 直接选择排序与交换选择排序

    有什么区别直接选择排序 vs 交换选择排序 今天我陷入了一场争论 我的教授在他的讲义中使用了这两个术语 维基百科和任何教科书或网站都会为您提供的选择排序就是他所说的 交换选择排序 我以前从未听说过 交换选择排序 这个术语 仅 选择排序 并且
  • 具有多个谓词的 C++11 算法

    功能如std find if来自algorithmheader 确实很有用 但对我来说 一个严重的限制是我只能为每次调用使用 1 个谓词count if 例如给定一个像这样的容器std vector我想同时应用相同的迭代find if 多个
  • 子序列和

    给定一个整数数组 例如 1 2 3 1 查找是否存在总和为0并返回它 例如 1 2 3 or 2 3 1 检查每个子序列是O n 2 这效率太低了 有改进的想法吗 创建一个新数组 其中每个元素等于前一个元素加上该元素的总和 Input 1
  • 实施二分查找有哪些陷阱? [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 二分查找比看起来更难实现 虽然二分搜索的基本思想相对简单 但细节可能出人意料地棘手 Donald Knuth 新的二分搜索实现中最有可
  • 以 O(1) 计算汉明权重 [重复]

    这个问题在这里已经有答案了 在二进制表示中 汉明权重是 1 的数量 我偶然发现了网络并找到了一个 O 1 的答案 v v v gt gt 1 0x55555555 v v 0x33333333 v gt gt 2 0x33333333 in
  • 如何用约束标记一大组“传递群”?

    在 NealB解决方案之后进行编辑 与以下解决方案相比 NealB的解决方案非常非常快任何另一个 https stackoverflow com q 18033115 answers and 提出了关于 添加约束以提高性能 的新问题 Nea
  • 照片马赛克算法。如何在给定基本图像和瓷砖列表的情况下创建马赛克照片?

    Hy 我要做的是创建一个程序 使用 C 或 C 它将 24 位 像素位图和图像集合作为输入 我必须创建一个马赛克图像 类似于使用库的输入图像给定的图像 创建与输入类似的马赛克照片 到目前为止 我可以访问输入的图像像素及其颜色 但我有点卡住了
  • 数学/算法使图像适合屏幕保留纵横比

    我需要数学 算法方面的帮助来拍摄已知尺寸的图像并适合两个屏幕尺寸之一 720 x 480 或 1280 x 1024 图像尺寸来自 XML 文件 但这些尺寸是 Web 尺寸 我还从 XML 中选择了一些图像 这些图像的分辨率可能比 Web
  • 平铺单纯形噪声?

    我 作为业余爱好者 对伪随机噪声生成很感兴趣 特别是 Perlin 和 Simplex 算法 Simplex 的优点是速度 尤其是在更高的维度上 但 Perlin 可以相对容易地平铺 我想知道是否有人知道平铺单纯形算法 固定维度就好 泛型更
  • 动态规划 (DP) 中的重叠子问题是什么?

    为了使动态规划适用 问题必须具有两个关键属性 最优子结构 and 重叠子问题 1 https en wikipedia org wiki Dynamic programming 对于这个问题 我们只关注后一个属性 有各种不同的定义重叠子问题
  • 如何使用 python 有效地找到两个大文件的交集?

    我有两个大文件 它们的内容如下所示 134430513125296589151963957125296589 该文件包含未排序的 id 列表 某些 id 可能会在单个文件中出现多次 现在我想找到路口两个文件的一部分 这就是两个文件中都出现的
  • 优先连接,Matlab 中的复杂网络

    大家好 我现在正在 MATLAB 中研究优先附件模型 在理解以下内容时遇到一些困难 假设我一开始有 4 个节点 连接如下 time 0 1 lt gt 2 3 lt gt 4 在下一个时间步骤中 我添加一个节点和 4 个连接 然后添加另一个
  • 在矩阵/位图中查找质量簇

    这是此处发布的问题的延续 在 2D 位图上查找质心 https stackoverflow com questions 408358 finding the center of mass on a 2d bitmap正如给出的例子 它讨论了
  • 用于计算有向图上非循环路径数量的快速算法

    简而言之 我需要一个fast计算简单有向图中有多少条非循环路径的算法 By simple我的意思是没有自环或多重边的图 Apath可以从任何节点开始 并且必须在没有传出边的节点上结束 一条路径是acyclic如果没有边出现两次 我的图 经验
  • 优化两个三位数乘积的最大回文数?

    我正在研究一个面试问题 我被问到这个问题 我应该编写一个程序 从两个三位数的乘积中找到最大的回文数 这里是question https projecteuler net problem 4 我想出了这种从底部开始的蛮力方法 public c
  • 融合元组以查找等价类

    假设我们有一个包含 k 个元素的有限域 D d1 dk 我们认为 S 是 D n 的子集 即一组 形式的元组 其中 ai 在 D 中 我们希望使用 S 2 D n 的子集 即一组 形式的元组 其中 Ai 是 D 的子集 来 紧凑地 表示它
  • 关于逻辑/算法的想法以及如何防止线程写入 Sql Server 中的竞争

    我有以下逻辑 public void InQueueTable DataTable Table int incomingRows Table Rows Count if incomingRows gt RowsThreshold async

随机推荐

  • 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 个路径 但我不太确定如何跟踪该列表 有任何