我正在做一个游戏，遇到了一些问题。我认为我知道解决方案（或者应该应用什么解决方案），但不确定如何将所有“碎片”拼凑在一起。

游戏运作方式：

（来自 如何处理一个带有转折的数字猜谜游戏算法？ ）

用户将获得具有价值的物品（价值每天都在变化，并且程序知道价格的变化）。例如

Apple = 1Pears = 2Oranges  = 3

然后，他们将有机会选择他们喜欢的任何组合（例如，100 个苹果，20 个梨和 1 个橙子）。计算机获得的唯一输出是总价值（在本例中，当前为 $143）。计算机将尝试猜测他们拥有什么。显然，它第一次无法正确猜中。

         价值  数量（第 1 天）  价值（第 1 天）Apple    1      100             100Pears    2      20              40Orange   3      1               3总计           121             143

在下一回合，用户可以修改他们的数字，但不能超过总量的 5%（或者我们可能选择的其他百分比。我将使用 5% 作为示例）。水果的价格可能会（随机）变化，因此总价值也可能会因此而变化（为简单起见，在本示例中我没有更改水果价格）。使用上面的示例，在游戏的第 2 天，用户返回的值为 $152，在第 3 天返回的值为 $164。这是一个例子。

数量（第 2 天）  % 变化（第 2 天）   价值（第 2 天） 数量（第 3 天）  % 变化（第 3 天）   价值（第 3 天）104                             104         106                             10621                              42          23                              462                               6           4                               12127             4.96%           152         133             4.72%           164

*(我希望表格显示正确，我是手动空格的，所以希望不仅仅是在我的屏幕上显示，如果它不起作用，请告诉我，我会尝试上传屏幕截图）。

我试图看看是否可以随着时间的推移计算出数量（假设用户有耐心继续输入数字）。我知道现在我唯一的限制是总价值不能超过 5%，所以我现在无法达到 5% 的准确度，因此用户将永远输入。

到目前为止我做了什么：

我已经获取了所有水果的价值和提供给我的水果篮的总价值，并创建了一个包含所有可能性的大的表格。一旦我有了所有可能性的列表，我就使用图论，并为每个可能的解决方案创建节点。然后，我在每一天的节点之间创建边（链接）（例如，第 1 天到第 2 天），如果它在 5% 的变化范围内。然后，我删除所有没有边（链接到其他节点）的节点，并且随着用户不断玩游戏，我还删除整个路径，当路径变成死胡同时。这很棒，因为它缩小了选择范围，但现在我被困住了，因为我想进一步缩小这些选择范围。我被告知这是一个隐马尔可夫问题，但这是一个更棘手的版本，因为状态正在变化（正如您在上面看到的，每回合都会添加新节点，并删除旧的/不太可能的节点）。

** 如果有帮助，我在这里获得了一个很棒的答案（带有示例代码），关于 baum-welch 模型（用于训练数据）的 python 实现： Baum-Welch 实现示例 **

我认为需要做的事情（这可能是错误的）：

现在我缩小了结果范围，我基本上试图让程序尝试根据缩小的结果库来预测正确的结果。我以为这是不可能的，但是有几个人建议可以使用隐马尔可夫模型来解决这个问题。我认为我可以多次迭代数据（使用 Baum-Welch 模型），直到概率稳定（并且应该随着用户更多回合的输入而变得更好）。隐马尔可夫模型能够检查拼写或笔迹并随着他们犯错而改进的方式（在这种情况下，错误是选择一个在下一回合被删除的篮子，因为它不太可能）。

两个问题：

1. 如果所有状态起初都相等，我如何计算出转移矩阵和发射矩阵？例如，由于所有状态同样可能，因此必须使用某些东西来指定状态变化的概率。我一直在考虑使用我制作的图来将具有最多边的节点作为转移/发射状态计算的一部分进行加权？这有道理吗，还是有更好的方法？

2. 如何跟踪状态中的所有变化？随着添加新篮子并删除旧篮子，会出现跟踪篮子的问题。我以为分层狄利克雷过程隐马尔可夫模型 (hdp-hmm) 是我需要的，但不太确定如何应用它。

（对不起，如果我的语气听起来有点沮丧…知道一个问题可以解决，但无法从概念上掌握需要做什么，这有点难）。

一如既往，感谢您的时间和任何建议/建议将不胜感激。

回答：

正如你所说，这个问题可以用 HMM 描述。 你本质上是对维护潜在的或者说隐藏的状态的分布感兴趣，而这些状态可以表示每个时间点的真实数量。 然而，看起来你混淆了学习 HMM 参数的问题，与简单地在已知的 HMM 中进行推断的问题。 你有后一个问题，但提出采用一种旨在解决前一个问题的解决方案（Baum-Welch）。 也就是说，你已经有了模型，你只需要使用它。

有趣的是，如果你为你的问题编写一个离散的 HMM，你会得到一个与你在图论解决方案中描述的非常相似的算法。 最大的区别在于你的解决方案是在追踪什么是可能的，而一个正确的推断算法，比如 Virterbi 算法，将追踪什么是可能的。 当一个域的 5% 范围内存在重叠时，即当多个可能的状态可能转换到同一状态时，差异是明显的。 你的算法可能会给一个点添加 2 条边，但我怀疑当你计算第二天时，这会产生影响（它应该算两次，本质上）。

无论如何，如果你只对最近一天的最佳猜测感兴趣，你可以使用 Viterbi 算法，我将简要介绍一下如何修改你的图论解决方案。与其在状态之间维护边，不如维护一个表示该状态是正确状态的概率的分数（这种分布有时称为置信状态）。在每一天，通过将每个桶增加其父级的概率来向前传播你的置信状态（而不是添加边，你添加一个浮点数）。你还必须确保你的置信状态已正确归一化（总和为 1），因此只需在每次更新后除以其总和即可。在那之后，你可以通过你的观察结果来加权每个状态，但是由于你没有嘈杂的观察结果，你可以直接将所有不可能的状态设置为零概率，然后重新归一化。你现在有一个关于潜在数量的分布，这个分布是以你的观察结果为条件的。

我在这里跳过了很多统计细节，只是给你一个想法。

编辑（回复问题）：你问题的答案实际上取决于你想要什么，如果你只想要最近一天的分布，那么你可以使用我描述的这种单程算法。 但是，如果你想要每一天数量的正确分布，你将不得不进行一次后向传递。 因此，也因此有了 前向-后向算法 这个恰当的名称。 我感觉到，由于你希望后退一步并删除边，那么你可能想要所有天的分布（不像我最初假设的那样）。 当然，你注意到可以使用一些信息，以便“未来可以告知过去”，这正是你需要进行后向传递的原因，这并不是很复杂，你只需运行完全相同的算法，从链的末尾开始。 想要获得良好的概述，请查看 Christopher Bishop 在 videolectures.net 上的 6 部分教程。

因为你提到了添加/删除边，所以让我澄清一下我之前描述的算法，请记住这只适用于单次前向传递。 假设总共有 N 个可能的数量排列，因此你将有一个 N 个元素的稀疏向量（称为 v_0）的置信状态。 你收到的第一步是总和的观察结果，并且你通过将所有可能的值设置为概率 1.0 来填充向量，然后重新归一化。 下一步，你创建一个新的所有 0 的稀疏向量 (v_1)，迭代 v_0 中的所有非零条目，并将 v_1 中所有在 5% 以内的条目增加（v_0 中的概率）。 然后，将 v_1 中所有根据新观察结果不可能的条目归零，然后重新归一化 v_1 并丢弃 v_0。 永远重复，v_1 将始终是可能性上的正确分布。

顺便说一句，如果你的观察结果嘈杂、状态非常大或状态连续，事情可能会变得更加复杂。 因此，很难阅读一些关于统计推断的文献，它非常笼统。