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

Question

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

有一个由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库很好，但是任何东西都可以。

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

Answer 1

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

一个暂定的实现可以如下：
简而言之：管理一组递增阶的马尔可夫链，以及分级和平均它们的预测

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

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

Answer 2

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

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

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

（最先进的RNN实现可以在PyBrainhttp://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

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

Answer 3

The question arises of how long of a history that the predictor should maintain

唯一的答案是“视情况而定”。

这取决于需要多精确。我不相信这个策略在无限的历史中也能100%准确。尝试10的历史，你会得到x%的准确率，然后尝试100，你会得到y%的准确率，等等。。。

最终，你会发现要么系统是你想要的那样精确，要么你会发现精确性的提高不值得历史长度的增加（以及内存使用量、处理时间的增加等等）。此时要么完成工作，要么你需要找到一个新的策略。

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