用于预测事件顺序的机器学习算法？

Question

简单机器学习问题。可能有很多种方式来解决这个问题：

有一个无限的流，其中有4种可能的事件:

'event_1', 'event_2', 'event_3', '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库很好，但任何东西都可以。

更新：如果每轮可能同时发生多个事件，那会不会改变解决方案?

- user213060

Answer 1

这本质上是一个序列预测问题，因此您需要使用循环神经网络或隐马尔可夫模型。如果您只有固定的时间来回顾历史数据，则可以采用时间窗口方法。您将序列数据拆分为长度为n的重叠窗口（例如，您将序列ABCDEF拆分为ABC，BCD，CDE，DEF，EFG）。然后，训练一个函数逼近器（例如神经网络或线性回归）来将该窗口的前n-1个部分映射到第n个部分。您的预测器将无法回头查看比您的窗口大小更长的历史数据。理论上，RNN和HMM可以这样做，但很难调整或有时根本不起作用。（最先进的RNN实现可以在PyBrain中找到 http://pybrain.org）。更新: 下面是适用于您问题的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个时代，并在每个时代后打印出错误。之后，您可以像这样检查正确的预测：

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

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

- bayer

---

能否提供一个“your_sequences”变量应该长什么样子的小例子？即使有描述，我猜我也没弄对。 - Fernando

Answer 2

不必保留完整历史记录，而是可以保留有关过去的聚合信息（以及相对较短的滑动历史记录，用作预测逻辑的输入）。

一个初步的实现可能是这样的：
简单来说：管理一组逐渐增加阶数的马尔可夫链，并对它们的预测进行分类和平均处理

• 维护一个事件计数表，其目的是计算任何4种不同事件的概率，而不考虑任何顺序。
• 维护一个二元组计数表，即观察到的事件的累积计数[至今]
  表格为空，第二个事件被观察时，我们可以存储第一个二元组，并带有计数为1。在第三个事件上，由第2个和第3个事件组成的二元组被"添加"到表中：要么增加现有二元组的计数，要么作为新的(从未出现过)二元组添加原始计数为1.等等
  同时，保持表中二元组的总计数。
  该表格和总计数允许根据前一个事件计算给定事件的概率。
• 以类似的方式维护三元组计数表，并运行总三元组数的累计计数（请注意，这将等于二元组数量减1，因为第一个三元组是在第一个二元组之后的一个事件后添加的，之后每个三元组都是在每个新事件时添加的）。该三元组表允许根据前两个事件计算给定事件的概率。
• 同样地，保持N-Gram的表格，例如，到10元组（算法将告诉我们是否需要增加或减少）。
• 保持最近10个事件的滑动窗口。
• 上述表格为预测提供了基础；一般思路是：
  • 使用公式，将下一个事件的概率表示为基于不同N-Gram的单个概率的加权平均值。
  • 通过增加公式中相应权重来奖励表现更好的个体N-Gram长度; 反向惩罚表现较差的长度。(要注意考虑个别事件的边际概率，以免我们偏袒预测最频繁事件的N-Grams，而无论它们相对较差的预测价值如何)
  • 一旦系统已经“看到”足够多的事件，查看与长N-Grams相关的权重当前值，如果这些值相对较高，则考虑添加表格以保留关于更大N-Grams的聚合信息。(不幸的是，这会在空间和时间上损害算法)

上述基本逻辑有多种变化形式。特别是在选择用于“评分”的特定度量标准方面存在差异。
其他注意事项应该放在检测和适应事件分布可能发生变化方面（上述假设通常成立于符合人类观察规律且随机性存在的事件源）。 一种可能的方法是使用两组表格（相应地合并概率），并定期删除其中一个集合的所有表格内容。 选择这些重置的正确周期是一个棘手的问题，需要在统计显着的历史容量和短期周期之间取得平衡，以免错过较短的调整...

- mjv

---

这是我会尝试的方法。与神经网络不同，它应该很容易实现，更重要的是易于理解。 - Carlos Rendon

Answer 3

问题是预测器应该保留多长时间的历史记录。

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

这取决于需要多么准确。我认为即使有无限的历史记录，这种策略也永远不可能达到100%的准确性。尝试使用10个历史记录，您将获得x％的准确性，然后尝试100个历史记录，您将获得y％的准确性，依此类推...

最终，您应该发现系统要么像您所需的那样准确，要么您会发现准确性的提高不值得增加历史记录长度（以及增加的内存使用、处理时间等）。此时，您要么完成了工作，要么需要找到新的策略。

就我而言，我认为研究一个简单的“软”神经网络可能是一个更好的计划。

- gingerbreadboy

---

虽然你可能可以进行一些数学计算来确定给定历史记录的预期准确性，但这取决于你的算法。 - gingerbreadboy

你无法确定需要回溯多长时间，因为你不知道底层动态。你只知道一些例子，而且你看到的甚至可能是随机的。 - bayer

Answer 4

我们刚刚在计算机体系结构中学习了分支预测器（因为处理器如果要实际评估条件if(EXPRESSION)会花费太长时间，所以它尝试“猜测”并节省一些时间）。我相信在这个领域已经进行了更多的研究，但这是我目前能想到的全部。

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

如果有多个事件可以同时发生...那就有点令人费解了，必须有一些限制：如果有无限数量的事件同时发生怎么办？哦，对于你来说这是计算上不可能的。我建议采用与一次只有一个事件相同的方法，只是在启用预测器预测多个事件时略有不同。

- rlb.usa

---

分支预测器是专为硬件设计的。如果您不太关心微秒级别的性能，可以使用更复杂的算法。 - bayer

没错 - 但是内存与正确性之间的相同根本问题（减去微秒）仍然存在。一些流行的分支预测器使用马尔可夫模型。 - rlb.usa

Answer 5

处理器使用一些非常轻便的技巧来预测分支语句是否会分支。这有助于它们进行高效的流水线操作。它们可能不像马尔可夫模型那样通用，但由于其简单性而非常有趣。这里是维基百科关于分支预测的文章。请查看饱和计数器和两级自适应预测器。

- Nathan