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

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

这本质上是一个序列预测问题,因此您需要递归神经网络或隐马尔可夫模型.

如果您只有固定的时间回顾,时间窗口方法可能就足够了.您获取序列数据并将其拆分为长度为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

这将为每个事件打印一系列布尔值.

Answer 2

可以保留关于过去的聚合信息(以及相对较短的滑动历史,以用作预测器逻辑的输入),而不是保持完整的历史记录.

暂时的实施可能是这样的:
简而言之:管理一组增加秩序的马尔可夫链,并对其预测进行分级和平均

• 保留一个单独的事件计数表,目的是计算4个不同事件中任何一个的概率,而不考虑任何序列.
• 保持一个二元组计数表,即事件观察到的累积计数[到目前为止]
  表开始为空,在第二个事件观察时,我们可以存储第一个二元组,计数为1.第三个事件,二元组由第二个和第三个事件被"添加"到表中:要么增加现有的二元组的计数,要么添加原始计数1,作为一个新的(从未见过的)最大的二元组.等
  平行地,保持在表中的双字母组的总计数.
  该表和总计数允许基于前一事件计算给定事件的概率.
• 以类似的方式保留一个三元组计数表和一个总三元组的运行计数(请注意,这将等于bigrams的数量减一,因为第一个三元组在第一个二元组之后添加了一个事件,之后每个新事件都添加其中一个).该三元组表允许基于前两个事件计算给定事件的概率.
• 同样地,保留N-Grams的表格,例如10克(算法将告诉我们是否需要增加或减少这个).
• 在最近10个事件中保持一个滑动窗口.
• 上表提供了预测的基础; 一般的想法是:
  • 使用一个公式,该公式表示下一个事件的概率,作为基于不同N-gram的个体概率的加权平均值.
  • 通过增加公式中的相应权重来奖励更好的个体N-gram长度; 以相反的方式惩罚更糟糕的长度.(注意个别事件的边际概率需要考虑在内,以免我们倾向于预测最常见事件的N-gram,无论与它们相关的相对较差的预测值如何)
  • 一旦系统"看到"了足够的事件,请查看与长N-Grams相关联的权重的当前值,如果这些值相对较高,请考虑添加表以保持有关较大N-Grams的聚合信息.(不幸的是,这无论在空间和时间上都伤害了算法)

上述一般逻辑可以有几种变化.特别是在用于"评定"各个N-Gram长度的预测质量的特定度量的选择中.
关于检测和适应事件分布中可能的变化,应该考虑其他因素(上面假设一般是遍历事件源).一种可能的方法是使用两组表(相应地组合概率),并周期性地丢弃其中一组的所有表的内容.为这些重置选择正确的时间段是一项棘手的工作,基本上平衡了对统计上显着的历史数量的需求以及对足够短的时间的需求,以免错过较短的调制...

Answer 3

出现的问题是预测器应该维持多长时间的历史记录

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

这取决于这需要有多准确。我不相信这个策略能够 100% 准确，即使有无限的历史。尝试历史记录 10，你会得到 x% 的准确率，然后尝试 100，你会得到 y% 的准确率，等等……

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

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