38

简单的机器学习问题。可能有很多方法可以解决这个问题：

有 4 种可能的事件的无限流：

'event_1', 'event_2', 'event_4', 'event_4'

事件的顺序不是完全随机的。我们将假设大多数事件的出现顺序有一些复杂的模式，而其余事件只是随机的。不过，我们并不提前知道这些模式。

收到每个事件后，我想根据过去事件的顺序来预测下一个事件将是什么。所以我的问题是：我应该为这个预测器使用什么机器学习算法？

然后预测器将被告知下一个事件实际上是什么：

Predictor=new_predictor()

prev_event=False
while True:
    event=get_event()
    if prev_event is not False:
        Predictor.last_event_was(prev_event)
    predicted_event=Predictor.predict_next_event(event)

问题是预测器应该维持多长时间的历史，因为维持无限的历史是不可能的。我会留给你来回答。尽管出于实用性考虑，答案不能是无限的。

所以我相信这些预测必须通过某种滚动历史来完成。因此，添加新事件和使旧事件过期应该是相当有效的，例如，不需要重建整个预测器模型。

对我来说，特定的代码而不是研究论文将为您的回复增加巨大的价值。Python 或 C 库很好，但任何事情都可以。

更新：如果每一轮可以同时发生多个事件怎么办。这会改变解决方案吗？

4

5 回答 5

23

这本质上是一个序列预测问题，所以你需要递归神经网络或隐马尔可夫模型。

如果您只有固定的时间回顾，时间窗口方法可能就足够了。您获取序列数据并将其拆分为长度为 n 的重叠窗口。（例如，您将序列 ABCDEFG 拆分为 ABC、BCD、CDE、DEF、EFG）。然后你训练一个函数逼近器（例如神经网络或线性回归）将该窗口的前 n-1 部分映射到第 n 部分。

您的预测器将无法及时回顾超过您的窗口大小。RNN 和 HMM 在理论上可以做到这一点，但很难调整或者有时根本不起作用。

（可以在 PyBrain http://pybrain.org中找到最先进的 RNN 实现）

更新：这是您的问题的 pybrain 代码。（我还没有测试过，可能有一些错别字和东西，但整体结构应该可以工作。）

from pybrain.datasets import SequentialDataSet
from pybrain.supervised.trainers import BackpropTrainer
from pybrain.tools.shortcuts import buildNetwork
from pybrain.structure import SigmoidLayer

INPUTS = 4
HIDDEN = 10
OUTPUTS = 4

net = buildNetwork(INPUTS, HIDDEN, OUTPUTS, hiddenclass=LSTMLayer, outclass=SigmoidLayer, recurrent=True)

ds = SequentialDataSet(INPUTS, OUTPUTS)

# your_sequences is a list of lists of tuples which each are a bitmask
# indicating the event (so 1.0 at position i if event i happens, 0.0 otherwise)

for sequence in your_sequences:
    for (inpt, target) in zip(sequence, sequence[1:]):
        ds.newSequence()
        ds.appendLinked(inpt, target)

net.randomize()

trainer = BackpropTrainer(net, ds, learningrate=0.05, momentum=0.99)
for _ in range(1000):
    print trainer.train()

这将训练循环网络 1000 个 epoch 并在每个 epoch 之后打印出错误。之后，您可以检查正确的预测，如下所示：

net.reset()
for i in sequence:
  next_item = net.activate(i) > 0.5
  print next_item

这将为每个事件打印一个布尔数组。

于 2010-03-26T17:04:07.317 回答
13

与其保留完整的历史记录，不如保留关于过去的聚合信息（连同相对较短的滑动历史记录，用作预测器逻辑的输入）。

一个试探性的实现可能是这样的：
简而言之：管理一组递增顺序的马尔可夫链，并对它们的预测进行分级和平均

  • 保留单个事件计数表，目的是计算 4 个不同事件中的任何一个的概率，而不考虑任何顺序。
  • 保留一个二元计数表，即观察到的事件的累积计数 [到目前为止]
    表开始为空，在第二个事件观察时，我们可以存储第一个二元组，计数为 1。在第三个事件之后，二元组由第二个和第三个事件被“添加”到表中：增加现有二元组的计数或添加原始计数 1，作为新的（迄今为止从未见过的）二元组。等等
    。并行地，在表中保留二元组的总数。
    该表和总计数允许根据前一个事件计算给定事件的概率。
  • 以类似的方式保留一个三元组计数表和总三元组的运行记录（请注意，这将等于二元组的数量减一，因为第一个三元组是在第一个二元组之后添加一个事件，并且之后每个新事件都会添加一个）。此三元表允许根据前两个事件计算给定事件的概率。
  • 同样，为 N-Gram 保留表格，例如，最多 10-gram（算法会告诉我们是否需要增加或减少它）。
  • 在最后 10 个事件中保留一个滑动窗口。
  • 以上表格为预测提供了依据；总体思路是：
    • 使用一个公式，该公式将下一个事件的概率表示为基于不同 N-gram 的各个概率的加权平均值。
    • 通过增加公式中的相应权重来奖励更好的个体 N-gram 长度；以相反的方式惩罚较差的长度。（请注意，需要考虑单个事件的边际概率，以免我们偏爱碰巧预测最频繁事件的 N-gram，而不管与它们相关的相对较差的预测值如何）
    • 一旦系统“看到”了足够多的事件，请查看与长 N-Gram 相关的权重的当前值，如果这些值相对较高，请考虑添加表格以保留有关更大 N-Gram 的汇总信息。（不幸的是，这在空间和时间方面都损害了算法）

上述一般逻辑可能有多种变体。特别是在选择用于“分级”各个 N-Gram 长度的预测质量的特定度量时。关于检测和适应事件分布的可能变化（以上假设一般遍历事件源），
还应考虑其他因素。一种可能的方法是使用两组表（相应地组合概率），并定期删除其中一组表的所有表的内容。为这些重置选择正确的时间是一件棘手的事情，基本上要平衡对具有统计意义的历史数量的需求和足够短的时间的需求，以免我错过较短的调制......

于 2010-03-26T17:06:43.280 回答
0

处理器使用一些非常轻量级的技巧来预测分支语句是否会分支。这有助于他们进行高效的管道内衬。例如，它们可能不像马尔可夫模型那样通用，但由于它们的简单性，它们很有趣。这是关于分支预测的维基百科文章。请参阅饱和计数器和两级自适应预测器

于 2010-06-29T19:39:26.433 回答
0

问题是预测器应该保持多长时间的历史

唯一的答案是“这取决于”。

这取决于这需要有多准确。我不相信即使有无限的历史，这种策略也不会 100% 准确。尝试 10 的历史记录，您将获得 x% 的准确度，然后尝试 100，您将获得 y% 的准确度，等等......

最终，您应该会发现系统与您希望的一样准确，或者您会发现准确性的提高不值得增加历史长度（以及增加的内存使用量、处理时间等......）。此时要么工作完成，要么您需要寻找新的策略。

对于值得我认为研究一个简单的“软”神经网络可能是一个更好的计划。

于 2010-03-26T16:10:02.347 回答
0

我们刚刚研究了计算机体系结构中的分支预测器（因为处理器会花费很长时间来实际评估条件 if(EXPRESSION)，它会尝试“猜测”并以这种方式节省一些时间）。我确信在这方面已经进行了更多的研究，但目前我能想到的就是这些。

我还没有看到像你这样独特的设置，所以我认为你可能需要自己做一些初步的实验。尝试使用 N 个插槽的历史运行您的解决方案 X 秒，正确率是多少？并将其与相同的固定 X 和不同的 N 历史槽进行比较，以尝试找到最佳的内存历史比率（将它们绘制出来）。

如果一个以上的事件可以同时发生......这有点弯曲，那里必须有一些限制：如果一次发生无限数量的事件怎么办？呃，这对你来说在计算上是不可能的。我会尝试与一次仅一个事件相同的方法，除非启用了预测器，一次预测多个事件。

于 2010-03-26T16:11:42.603 回答