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

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语言的库都很好，但任何语言的代码都可以。

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

Answer 1

我们刚刚学习了计算机架构中的分支预测器（因为处理器在实际评估一个条件时会花费太长时间，所以它会尝试“猜测”，这样可以节省一些时间）。我相信在这个领域已经有更多的研究，但目前我能想到的就这些。

我没有见过像你这样的独特设置，所以我觉得你可能需要自己做一些初步实验。试着让你的解决方案运行X秒，使用N个历史记录槽，这样的正确率是多少？然后将这个结果与相同的X值和不同的N历史记录槽进行比较，看看哪个内存历史比例最好（可以把结果画成图表）。

如果多个事件可以同时发生……这有点复杂，肯定会有一些限制：如果同时发生无限多个事件怎么办？那样的话，对你来说在计算上是不可能的。我建议你还是一次处理一个事件，除了在预测器启用的情况下，可以预测多个事件同时发生。

Answer 2

与其保留完整的历史记录，不如保留一些汇总信息，同时保持一个相对较短的滑动历史，用于预测逻辑的输入。

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

• 保持一个单个事件计数的表格，目的是计算四种不同事件的概率，而不考虑它们的顺序。
• 保持一个二元组（bigram）计数的表格，也就是对到目前为止观察到的事件进行累积计数。
  这个表开始时是空的，当观察到第二个事件时，我们可以存储第一个二元组，计数为1。当观察到第三个事件时，由第二个和第三个事件组成的二元组会被“添加”到表中：要么增加已有二元组的计数，要么以计数1作为新的（之前从未见过的）二元组添加。依此类推。
  同时，保持一个二元组的总计数。
  这个表和总计数可以用来计算给定事件的概率，基于它前面的一个事件。
• 以类似的方式保持一个三元组（trigram）计数的表格，以及已观察到的三元组的总计数（注意，这个总数等于二元组的数量减去1，因为第一个三元组是在第一个二元组之后添加的一个事件后才出现的，之后每新增一个事件都会增加一个三元组）。这个三元组表格可以用来计算给定事件的概率，基于它前面的两个事件。
• 同样，保持N-元组（N-Grams）的表格，最多到10元组（算法会告诉我们是否需要增加或减少这个数量）。
• 保持一个滑动窗口，记录最近的10个事件。
• 以上的表格为预测提供了基础；总体思路是：
  • 使用一个公式，表示下一个事件的概率是基于不同N-元组的个别概率的加权平均。
  • 通过增加公式中相应的权重来奖励表现更好的N-元组长度；反之，惩罚表现较差的长度。（要注意，个别事件的边际概率需要考虑，以免我们偏向那些预测最频繁事件的N-元组，而忽视它们相对较差的预测价值）
  • 一旦系统“看过”足够多的事件，查看与长N-元组相关的权重当前值，如果这些值相对较高，可以考虑添加表格来保持关于更大N-元组的汇总信息。（这不幸会在空间和时间上对算法造成负担）

上述描述的逻辑可以有多种变体。特别是在选择用于“评分”个别N-元组长度预测质量的特定指标时。
还需要考虑检测和适应事件分布可能的变化（上述假设事件源是一般遍历的）。一种可能的方法是使用两组表格（相应地组合概率），并定期清空其中一组的所有表格内容。选择这些重置的合适周期是一项棘手的工作，基本上是在统计上显著的历史量和足够短的周期之间取得平衡，以免错过较短的波动...

Answer 3

这其实是一个序列预测的问题，所以你可以使用递归神经网络（RNN）或者隐马尔可夫模型（HMM）。

如果你只能回顾固定的时间段，那么时间窗口的方法可能就够用了。你可以把序列数据分成重叠的窗口，每个窗口的长度是n。比如说，你把序列ABCDEFG分成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

这会为每个事件打印出一个布尔值数组。