问题标签 [viterbi]

我是隐马尔可夫模型的新手，我目前正在尝试使用连续 HMM 来预测 R 中 UCI 人类活动识别数据集（由加速度计和陀螺仪值组成）上的 6 个活动。我有训练数据和测试数据，还有总共有 561 个功能。在阅读了几篇论文后，我制作了一个 6 状态 HMM，并使用我拥有的训练数据对其进行了训练，假设状态代表一个要分类的活动。之后，我使用维特比来预测 HMM 应用于测试数据时最可能的序列。使用 HMM 的 depmixS4 包，我尝试输入以下代码：

当使用所有 561 个功能时，我很惊讶地看到这些代码产生了 100% 的准确度（使用 Jahmm 时我只获得了大约 80% 的准确度，但后来我无法使用它的所有 561 个功能，因为它挂起）。我实际上是在和 depmixS4 的开发者接触，他确认代码没问题，但也说，“注意，下面的拟合模型实际上是观察到的或普通的马尔科夫模型，而不是隐藏马尔科夫模型，因为所有的响应在边界处估计概率。” 他所说的“在边界处估计响应概率”是什么意思？我尝试在网上搜索它的含义，但没有运气。

使用维特比不是意味着它确实是一个隐马尔可夫模型吗？我做错了吗？

请注意，“viterbi()”函数仍然是包上未发布的函数（开发人员好心地告诉我它能够尝试我的想法）。

我有一系列值，我正在尝试为每个状态建模一个 HMM。目前每个模型都有 1 个状态，我有两个模型正在尝试模拟。
例如：

现在我想为每个序列创建一个模型，然后确定每个序列的维特比分数。不过，我对如何生成模型感到困惑，因为这些只是双值，而且我不知道排放量等。

我希望是这样的：

从这里，我们得到了概率。

我正在尝试在OpenMP 的帮助下实现Viterbi 算法。到目前为止，我的测试表明并行程序的执行时间大约是顺序程序执行时间的 4 倍。这是我的代码：

我究竟做错了什么？

假设我有一组随机的观察结果：

obs = [1, 2, 3, 5, 5, 5, 5, 5]

这些观察代表 HMM 中的 1 个状态。在 Matlab 中，我想对这些观察进行建模，这样我就可以使用 Viterbi 算法来创建一种分类器。

我遇到的问题是，在 Matlab 中生成模型方面，我真的不知道从哪里开始。工具箱中的功能似乎没有这个。

是否有一个特定的库，可以让我执行这样的程序来模拟一系列观察？

我正在尝试学习隐马尔可夫模型，维特比算法。因此，我正在寻找一个例子来学习。我从这个链接中遇到了一个简单的例子；

直到位置 3，我什么都明白了。但是在计算A时在位置3；

由于B值大于A值，我们为状态 3 中的A选择状态 2 中的B。状态 3 中的A值应为 0.09604

计算状态3的B值；

由于B值大于A值，我们为状态 3 中的 B 选择状态2 中的B。因此状态 3 中的B值应为 0.02744

然而，在状态 3 的示例中，值在示例中的计算如下：

与我的回答不同。

我还在学习这门课，所以很可能我犯了一个错误。但是我看不到在哪里。

为什么我得到不同的答案？我的解决方案有什么问题？

我试图理解维特比算法。

各州是；S1、S2、S3、开始、结束

这些值被舍入和截断。

平滑状态转移表如下；

S1 -0.7 -1.6 -1.6 -INF -2.0

S2 -2.0 -1.3 -0.7 -INF -2.0

S3 -1.3 -0.7 -2.0 -INF -2.0

B -1.2 -1.2 -1.2 -INF -1.9

E -INF -INF -INF -INF -INF

从状态到红色、绿色、蓝色的平滑发射表；

S1 -0.9 -1.2 -1.6

S2 -1.6 -0.9 -1.2

S3 -1.6 -1.6 -0.6

B -INF -INF -INF

E -INF -INF -INF

问题是; 已经看到的符号是； 红色 红色 绿色 蓝色

最有可能的状态是什么？

所以;

我根据上面的值创建了维特比算法矩阵；

第一行代表看到红色符号时的 S1、S2、S3 值，就像看到红色、绿色和蓝色时的 S1、S2、S3 值的其余行一样。

对于第一行，我计算了它；

通过取它们的自然对数来平滑值，因此我将值相加而不是相乘。

对于第一个看到的红色；

δ(S1) = MAX{P(S1|B)+P(R|S1)+δ(B)} = -1.2 - 0.9 + 0= -2.1

δ(S2) = MAX{P(S2|B)+P(R|S2)+δ(B)} = -1.2 - 1.6 + 0= -2.8

δ(S3) = MAX{P(S3|B)+P(R|S3)+δ(B)} = -1.2 - 1.6 + 0= -2.8

就像上面一样，下一个看到的红色；

δ(S1) = MAX{ (P(S1|S1)+P(R|S1)+δ(S1) ), ( P(S1|S2)+P(R|S2)+δ(S2) ), ( P(S1|S3)+P(R|S3)+δ(S3))}

= 最大{ (-0.7-0.9-2.1),(-1.6-1.6-2.8), (-1.6-1.6-2.8) } = 最大{-3.7, -6, -6}

最大值为 -3.7，因此看到 RED 时的 S1 值；-3.7 。其余值如上计算。

维特比算法矩阵；

红色 -2.1 -2.8 -2.8 -INF -INF

红色 -3.7 -5.2 -5.2 -INF -INF

绿色 -5.8 -6.3 -7.0 -INF -INF

蓝色 -8.1 -8.6 -7.8 -INF -INF

这个例子的答案表明最有可能的状态是；S1、S1、S2、S3

但是不应该吗？S1，S1，S1，S3？因为第一个红色的最大值是-2.1，属于 S1，第二个红色的最大值是 S1，第三个红色的最大值是 S1，蓝色的 S3 值是最高的。我可能是错的，因为我实际上无法理解 Viterbi 的动态编程方法。

我正在寻找 R 中的 HMM 实现来分析字符串中的状态，并且 HMM 库似乎运行缓慢，然后我正在使用 RHmm 库。

我的数据是一串 1953138 个符号 (U,D,N)

这是我的数据样本：

拟合 HMM

运行维特比，这是我得到错误的地方

但是，如果我只使用字符串 viterbi() 的一个子集就可以了：

实际上，如果我尝试运行：

我得到相同的堆栈溢出错误，然后向量中的 49964 个元素是限制

我认为问题可能与 --max-ppsize 的默认 R 选项是 50000 的事实有关，但是将此参数更改为它的限制 --max-ppsize 500000 并不能#fix 问题。然而 viterbi() 中的向量限制确实增加了，它从 49964 个元素增加到字符串向量中的 499960 个元素左右。

我尝试分块运行维特比算法。首先，我将字符串拆分为 49960 个元素的块并将 viterbi 应用于每个元素，但我得到了同样的错误

在 stackoverflow 中，我发现了与我遇到的LINK类似的问题。显然问题的根源是不需要的循环内的保护。我跳进了 viterbi 函数的 c++ 源代码，但没有一个 PROTECT。

我也试过ulimit -s unlimited了，但我得到了同样的错误。

我正在使用 1009 GB RAM 内存的 unix

链接到RHmm 包

非常感谢您的帮助！

我一直在使用前向后向算法来找到从状态 1 到状态 N 的最有效（由成本函数确定，该成本函数取决于当前状态与下一个状态的不同）路径。在下图中，可以看到问题的简短版本，每个状态只有 3 个状态和 2 个节点。我对此进行了前后算法，并找到了正常的最佳路径。图片中的红色位是代码中前向传播位期间检查的路径。

现在有趣的是，我现在想找到最好的 3-State Length 路径（和以前一样），但现在只有第一个 State 中的节点是已知的。其他 4 个现在是自由浮动的，可以被视为处于任何状态（状态 2 或状态 3）。我想知道你们是否知道如何做到这一点。

图片：http: //i.imgur.com/JrQ2tul.jpg

注意：请记住，原始问题由大约 25 个状态和每个状态 100 个节点组成。因此，您将知道状态 1 中大约 100 个节点的状态，但其他 24*100 个节点是无状态的。在这种情况下，我想找到一个 25-State 长度的路径（成本最低）。

附录：有人指出更好的算法是维特比算法。所以这里有更多变量的问题。你们能解释一下如何实现吗？同样的规则适用，路径应该从状态 1 中的一个节点（节点 a 或节点 b）开始。此外，在这种情况下，使用规范的成本函数没有意义，因为我们只有一个属性（节点大小），但在实际问题中，我期待更多的属性。

我正在尝试在 R 中实现维特比算法。我编写了以下代码，

我试图将以下参数传递给函数参数，

当我运行算法本身时，程序不会抛出任何错误，但是，当我使用上述值运行程序时，它会抛出以下错误

“被替换元素的数量不是替换长度的倍数”

我对 R 编程错误还不太熟悉，我不确定这是关于什么或如何调试它。有人可以帮忙吗？

提前致谢！

我一直在开发一个程序，该程序将读取 OCR 输出，找到页码，然后将它们还给我。每当我的函数找到一个数字时，它就会开始一个序列，然后它会在下一页上查找比前一个大 1 的数字。它还可以添加空格来推断缺失的数字。

在任何给定的书中，我的函数将识别 1-100 个潜在序列。它识别的许多序列都是垃圾……完全没用。然而，其他的通常是主要序列的子集，可以拼接在一起形成更全面的序列。这是我的问题：我如何将它们缝合在一起？我的输出现在看起来像这样：

索引是书籍封面的页数，包括所有那些传统上未编号的版权、奉献、目录页数。PNUM 是我的算法检测到的页码。在这里我们可以看到三个不同的序列，它们的顶部和底部应该缝合在一起。您会注意到顶部序列的索引和 pnum 之间的偏移量是 27，而底部序列的偏移量是 25。偏移量之间存在差异的最常见原因是缺少页面，或者页面扫描了两次。

有人建议我使用 Viterbi 最佳路径算法将这些序列拼接在一起，但这对我来说似乎有点矫枉过正，因为我真的只需要将我的序列拼接在一起，而不是确认它们的准确性。我真的不知道该去哪里，我非常感谢任何帮助。谢谢！