python - 将机器学习应用于猜谜游戏？

Question

我正在制作的游戏有问题。我想我知道解决方案(或适用什么解决方案)，但不确定所有“部分”如何组合在一起。

游戏的工作方式:

(来自How to approach number guessing game(with a twist) algorithm?)

将为用户提供带有值的商品(值每天都会更改，并且程序会意识到价格的变化)。例如

Apple = 1
Pears = 2
Oranges  = 3

然后，他们将有机会选择自己喜欢的任何组合(即100个苹果，20个梨和1个橙子)。计算机获得的唯一输出是总值(value)(在此示例中，当前值(value)为143美元)。计算机将尝试猜测它们所拥有的。显然，第一轮将无法正确获得。

         Value  quantity(day1)  value(day1)
Apple    1      100             100
Pears    2      20              40
Orange   3      1               3
Total           121             143

下一轮用户可以修改其号码，但不能超过总数的5％(或我们可以选择的其他百分比。例如，我将使用5％)。水果的价格可以(随机)变化，因此总值(value)也可以基于此变化(为简单起见，在此示例中，我不更改水果的价格)。使用上面的示例，在游戏的第2天，用户在第3天返回了$ 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％，因此用户将永远输入该值。

我到目前为止所做的:

我已经拿走了我所有的水果值(value)和水果篮的总值(value)，并创建了一张包含所有可能性的大表格。一旦获得所有可能性的 list ，我便使用图论并为每种可能的解决方案创建了节点。然后，如果每天(例如day1到day2)之间的变化在5％之内，我将在节点之间创建边(链接)。然后，我删除所有不具有边线的节点(链接到其他节点)，并且当用户继续玩时，当路径变为死角时，我也会删除整个路径。
这很棒，因为它缩小了选择范围，但现在我陷入困境，因为我想进一步缩小选择范围。有人告诉我这是一个隐藏的马尔可夫问题，但版本却比较棘手，因为状态在变化(如您所见，每转一圈都会添加新节点，而旧/不可能的节点也会被删除)。

**如果有帮助，我会在这里获得关于baum-welch模型(用于训练数据)的python实现的惊人答案(带有示例代码): Example of implementation of Baum-Welch **

我认为需要做的事情(这可能是错误的):

现在，我缩小了结果的范围，基本上是在尝试让程序根据缩小的结果库来预测正确的结果。我以为这是不可能的，但是一些人建议可以通过隐藏的马尔可夫模型解决。我认为我可以对数据进行多次迭代(使用Baum-Welch模型)，直到概率稳定(并应随着用户的转弯次数而变好)。
隐藏的马尔可夫模型能够检查拼写或笔迹并在出错时进行改进(这种情况下的错误是选择一个篮子，该篮子在下一轮被删除是不可能的)的方式。

两个问题:

如果所有状态一开始都相等，我如何计算过渡和发射矩阵？例如，由于所有状态都是同等可能，因此必须使用某种方法来确定状态变化的可能性。我在考虑使用我制作的图来加权具有最高数量的边的节点，作为过渡/发射状态计算的一部分？这有意义还是有更好的方法？

如何跟踪状态的所有变化？随着新篮子的增加和旧篮子的去除，跟踪篮子成为一个问题。我虽然需要一个Dirichlet分层流程隐藏的markov模型(hdp-hmm)，但我不确定如何应用它。

(对不起，如果我听起来有点沮丧，..知道一个问题是可以解决的，但是不能从概念上掌握需要做什么，这有点困难)。

与往常一样，感谢您的宝贵时间，任何建议/建议都将不胜感激。

Answer 1

就像您说的那样，可以使用HMM来描述此问题。您实际上对保持潜在状态或隐藏状态的分布感兴趣，这是每个时间点的真实数量。但是，与仅在已知HMM中进行推论相反，似乎让您迷惑了为HMM学习参数的问题。您有后一个问题，但建议采用一个解决方案(Baum-Welch)来设计前一个问题。也就是说，您已经有了模型，只需要使用它即可。

有趣的是，如果您针对问题进行离散HMM编码，则所获得的算法与图论解决方案中描述的算法非常相似。最大的区别是您的解决方案正在跟踪可能是的可能性，而正确的推理算法(例如Virterbi algorithm)将跟踪可能是的东西。当域的5％范围内有重叠时，也就是说，当多个可能的状态可能潜在地转换为同一状态时，差异显而易见。您的算法可能会在一条点上增加2条边，但是我怀疑当您计算第二天有效果时(本质上应该计算两次)。

无论如何，您可以使用Viterbi算法，如果您只对最近一天的最佳猜测感兴趣，那么我只是给您一个简短的想法，您可以如何修改图形理论解决方案。代替维持状态之间的边缘，而是保留代表状态正确的概率的分数(此分布有时称为置信状态)。在每个新的一天，通过将每个存储桶作为父项的概率递增(而不是通过添加浮点数来增加边沿)来传播您的信念状态。您还必须确保您的信念状态已正确归一化(总和为1)，因此在每次更新后只需除以其总和即可。之后，您可以通过观察加权每个状态，但是由于您没有嘈杂的观察，因此您可以将所有不可能的状态设置为零概率，然后重新进行归一化。现在，您可以根据观测条件分配基础数量。

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

编辑(回复:问题):
您问题的答案实际上取决于您想要的内容，如果您只希望获得最近一天的分布，则可以采用我所描述的一遍算法。但是，如果您想在每一天对数量进行正确的分配，则还必须进行向后传递。因此，恰当地命名为forward-backward algorithm。我感觉到，由于您希望退后一步并删除边线，因此您可能希望整天都进行分配(与我最初假设的不同)。当然，您已经注意到可以使用一些信息，以便可以说“ future 可以告知过去”，这正是您也需要进行反向传递的原因，您仅拥有的并不复杂从链的末尾开始运行完全相同的算法。要获得良好的概述，请在videolectures.net上查看Christopher Bishop的6篇教程。

因为您提到了添加/删除边，所以让我只是澄清一下我先前描述的算法，请记住，这是针对单次向前通过。假设总共有N个可能的数量置换，那么您将拥有一个信念状态，该状态为长度为N个元素的稀疏向量(称为v_0)。第一步，您将得到和的观测值，然后通过将所有可能的值设置为概率为1.0来填充矢量，然后重新进行归一化。下一步，您将创建一个全为0的新稀疏向量(v_1)，迭代v_0中的所有非零条目，并递增(按v_0中的概率)v_1中所有5％之内的条目。然后，根据新观察将v_1中所有不可能的条目清零，然后重新规范化v_1并丢弃v_0。永远重复一次，v_1将永远是可能性的正确分配。

顺便说一句，如果您有嘈杂的观察结果，非常大的状态或连续状态，那么事情会变得比这更复杂。因此，很难阅读一些有关统计推论的文献。这很一般。