将机器学习应用于猜谜游戏？
我在制作一个游戏时遇到了问题。我觉得我知道解决方案（或者说该用什么方案），但不太确定所有的“部分”是怎么结合在一起的。
游戏的工作原理：
(来自 如何处理带有变化的数字猜测游戏算法？)
用户会获得一些物品，每个物品都有一个价值（这些价值每天都会变化，程序会知道价格的变化）。比如说：
Apple = 1
Pears = 2
Oranges = 3
然后他们可以选择任何他们喜欢的组合（例如：100个苹果，20个梨，1个橙子）。计算机得到的唯一输出是这些物品的总价值（在这个例子中，目前是143美元）。计算机会尝试猜测他们拥有的物品。显然，它在第一轮时不会猜对。
Value quantity(day1) value(day1)
Apple 1 100 100
Pears 2 20 40
Orange 3 1 3
Total 121 143
在下一轮，用户可以修改他们的数量，但修改的总量不能超过5%（或者我们选择的其他百分比。我这里用5%作为例子）。水果的价格可能会随机变化，所以总价值也可能会因此变化（为了简单起见，我在这个例子中不改变水果价格）。使用上面的例子，在游戏的第二天，用户返回的价值是152美元，第三天是164美元。以下是一个例子。
quantity(day2) %change(day2) value(day2) quantity(day3) %change(day3) value(day3)
104 104 106 106
21 42 23 46
2 6 4 12
127 4.96% 152 133 4.72% 164
*(希望表格能正确显示，我手动调整了间距，希望这不是只在我屏幕上这样，如果不行请告诉我，我会尝试上传截图)。
我想看看能否随着时间推移找出数量（假设用户有耐心不断输入数字）。我知道目前我唯一的限制是总价值不能超过5%，所以我现在不能在5%的准确度内，这样用户就会一直输入下去。
我到目前为止做了什么：
我把所有水果的价值和给我的水果篮的总价值都列出来，创建了一个所有可能性的庞大表格。一旦我有了所有可能性的列表，我就使用图论为每个可能的解决方案创建了节点。然后，我在每一天的节点之间创建边（链接），如果它们在5%的变化范围内（例如从第一天到第二天）。接着，我删除所有没有边（链接到其他节点）的节点，随着用户的继续游戏，当路径变成死胡同时，我也会删除整个路径。这很好，因为它缩小了选择范围，但现在我卡住了，因为我想进一步缩小这些选择。我被告知这是一个隐马尔可夫问题，但更棘手，因为状态在变化（如上所示，每轮都会添加新节点，而旧的或不太可能的节点会被移除）。
**如果有帮助，我在这里得到了一个很棒的答案（带有示例代码），关于如何在Python中实现baum-welch模型（用于训练数据）：Baum-Welch的实现示例 **
我认为需要做的事情（这可能是错的）：
现在我已经缩小了结果，我基本上是在尝试让程序根据缩小后的结果来预测正确的答案。我原以为这不可能，但好几个人建议可以用隐马尔可夫模型来解决。我想我可以对数据进行多次迭代（使用Baum-Welch模型），直到概率稳定（并且随着用户的回合增多应该会变得更好）。隐马尔可夫模型能够检查拼写或手写，并在出错时改进（在这种情况下，错误是选择一个在下一轮被删除的篮子，认为它不太可能）。
两个问题：
如果所有状态一开始都是相等的，我该如何找出转移和发射矩阵？例如，既然所有状态都是同样可能的，就必须用某种方法来确定状态变化的概率。我在想是否可以利用我制作的图来加权那些边数最多的节点，作为计算转移/发射状态的一部分？这样做有道理吗，还是有更好的方法？
我该如何跟踪所有状态的变化？随着新篮子的添加和旧篮子的移除，跟踪篮子就成了一个问题。我觉得一个层次狄利克雷过程隐马尔可夫模型（hdp-hmm）可能是我需要的，但不太确定如何应用它。
（抱歉如果我听起来有点沮丧……知道一个问题是可以解决的，但却无法在概念上理解需要做什么，确实有点难）。
一如既往，感谢你的时间，任何建议或意见都将不胜感激。
1 个回答
正如你所说，这个问题可以用隐马尔可夫模型（HMM）来描述。你主要是想保持一个关于潜在状态的分布，这些状态就是每个时间点的真实数量。不过，看起来你把学习HMM的参数和在已知HMM中进行推断这两个问题搞混了。你现在面临的是后者的问题，但你却提出了一个解决方案（Baum-Welch），这个方案是用来解决前者的。也就是说，你已经有了模型，只需要使用它就行了。
有趣的是，如果你为你的问题编写一个离散的HMM，你会得到一个和你在图论解决方案中描述的算法非常相似的东西。最大的区别在于，你的解决方案是在追踪什么是可能的，而一个正确的推断算法，比如维特比算法，则是在追踪什么是可能性更大的。当在某个领域中有5%的重叠时，这个区别就很明显，也就是说，当多个可能的状态可能转移到同一个状态时。你的算法可能会在一个点上增加2条边，但我怀疑当你计算下一天时这会有影响（实际上应该算两次）。
无论如何，如果你只对最近一天的最佳猜测感兴趣，可以使用维特比算法。我给你简单介绍一下如何修改你的图论解决方案。你可以不再在状态之间维护边，而是维护一个表示该状态是正确的概率的分数（这个分布有时被称为信念状态）。在每个新的一天，向前传播你的信念状态，通过增加每个桶的父状态的概率来更新（而不是添加边，你是在添加一个浮点数）。你还需要确保你的信念状态是正确归一化的（总和为1），所以在每次更新后就把它的总和除掉。之后，你可以根据你的观察来加权每个状态，但由于你没有噪声观察，你可以直接把所有不可能的状态设为零概率，然后再进行归一化。现在你就有了一个基于你观察的底层数量的分布。
我这里省略了很多统计细节，只是给你一个大概念。
编辑（关于问题）：
你问题的答案实际上取决于你想要什么。如果你只想要最近一天的分布，那么你可以用我描述的单次算法。如果你想要每一天的数量的正确分布，那么你就需要进行一次反向传递。因此，正如其名的前向-后向算法。我感觉你想回过头来删除边，所以你可能想要所有天的分布（这和我最初的假设不同）。当然，你注意到有信息可以利用，这样“未来可以影响过去”，这正是你需要进行反向传递的原因。其实并不复杂，你只需从链的末端开始运行完全相同的算法。想要了解更多，可以查看Christopher Bishop在videolectures.net上的六部分教程。
因为你提到添加/删除边，所以让我澄清一下我之前描述的算法，请记住这是针对单次前向传递的。假设有N种可能的数量排列，那么你会有一个长度为N的稀疏向量（称为v_0）。第一步你接收到一个总和的观察，然后通过将所有可能的值设为概率1.0来填充这个向量，然后进行归一化。接下来，你创建一个新的稀疏向量（v_1），初始值全为0，遍历v_0中所有非零条目，并将v_0中的概率加到v_1中所有在5%范围内的条目上。然后，将v_1中根据新观察不可能的条目设为0，再对v_1进行归一化，最后丢弃v_0。这样重复下去，v_1将始终是正确的可能性分布。
顺便说一下，如果你有噪声观察或非常大的状态或连续状态，事情会变得更加复杂。因此，阅读一些关于统计推断的文献会比较困难；它们通常比较笼统。