Алгоритм машинного обучения для прогнозирования порядка событий?

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. После третьего события биграмма, созданная из 2-го и 3-го событий, «добавляется» в таблицу: либо увеличивая счетчик существующий биграмм или добавленный с исходным счетом 1, как новый (никогда не замеченный) биграмм. и т.д.
  Параллельно ведите общее количество биграмм в таблице.
  Эта таблица и общий подсчет позволяют рассчитать вероятность того или иного события на основе предыдущего события.
• Аналогичным образом сохраните таблицу подсчета триграмм и прослеживаемый подсчет общей триграммы (обратите внимание, что это будет равно количеству биграмм, минус один, поскольку первая триграмма добавляется через одно событие после первой биграммы и после этого каждый из них добавляется с каждым новым событием). Эта таблица триграмм позволяет рассчитать вероятность данного события на основе двух предыдущих событий.
• аналогично, сохраняйте таблицы для N-граммов, скажем, до 10 граммов (алгоритм скажет, нужно ли нам увеличивать или уменьшать это).
• держать раздвижные окна в последние 10 событий.
• Приведенные выше таблицы служат основой для прогнозирования; общая идея заключается в следующем:
  • используйте формулу, которая выражает вероятности следующего события в виде взвешенного среднего значения отдельных вероятностей, основанного на различных N-граммах.
  • наградите лучшую индивидуальную длину N-грамма, увеличив соответствующий вес в формуле; Накажи худшие длины в обратном порядке. (Помните, что необходимо учитывать предельную вероятность отдельных событий, чтобы мы не отдавали предпочтение N-граммам, которые предсказывают самые частые события, независимо от относительной плохой прогнозирующей ценности, связанной с ними). ​​
  • Как только система "увидит" достаточно событий, просмотрите текущие значения весов, связанных с длинными N-граммами, и, если они относительно высокие, рассмотрите возможность добавления таблиц, чтобы сохранить сводную информацию о больших N-граммах. (К сожалению, это вредит алгоритму как с точки зрения пространства, так и времени)

Может быть несколько вариантов общей логики, описанной выше . В частности, при выборе конкретной метрики, используемой для «оценки» качества прогнозирования отдельных длин N-грамм.
Другие соображения должны быть сделаны в отношении обнаружения и адаптации к возможным сдвигам в распределении событий (вышеизложенное предполагает в целом эргодический источник событий). Один из возможных подходов состоит в том, чтобы использовать два набора таблиц (соответственно комбинируя вероятности) и периодически отбрасывая содержимое всех таблиц одного из наборов. Выбор правильного периода для этих перезагрузок - сложная задача, по сути, сбалансировать потребность в статистически значимых объемах истории и потребность в достаточно коротком периоде, чтобы я не пропустил более короткие модуляции ...

Answer 3

Процессоры используют несколько действительно легких трюков, чтобы предсказать, будет ли ветвление оператора ветвления или нет. Это помогает им с эффективной прокладкой труб. Они могут быть не такими общими, как, например, марковские модели, но они интересны своей простотой. Вот статья в Википедии о предсказании ветвления . См. Счетчик насыщения и Двухуровневый адаптивный предсказатель

Answer 4

Мы только что изучили около предсказателей ветвлений в компьютерной архитектуре (поскольку процессору потребовалось бы слишком много времени, чтобы на самом деле оценить условие, если (EXPRESSION) он пытается «угадать» и сэкономить некоторое время таким образом) , Я уверен, что больше исследований было сделано в этой области, но это все, что я могу думать на данный момент.

Я не видел такой уникальной установки, как ваша, поэтому я думаю, что вам, возможно, придется провести некоторые предварительные эксперименты самостоятельно. Попробуйте запустить ваше решение в течение X секунд с историей из N слотов. Каков коэффициент корректности? И сравните это с тем же фиксированным X и различными N слотами истории, чтобы попытаться найти лучшее соотношение памяти и истории (вычерчивая их график).

Если одновременно может происходить более одного события ... это немного смущает, то здесь должны быть некоторые ограничения: что если одновременно происходит бесконечное число событий? Э-э, это вычислительно невозможно для вас. Я бы попробовал тот же подход, что и одно событие за раз, за ​​исключением случаев, когда включен предиктор, для прогнозирования нескольких событий одновременно.

Answer 5

Возникает вопрос о том, как долго история, которую предсказатель должен поддерживать

Единственный ответ - "это зависит".

Это зависит от того, насколько точным это должно быть. Я не верю, что эта стратегия могла бы быть на 100% точной даже с бесконечной историей. Попробуйте историю 10, и вы получите x% точности, затем попробуйте 100, и вы получите y% точности и т. Д. И т. Д. *

В конце концов вы должны обнаружить, что либо система настолько точна, насколько вы хотите, либо вы обнаружите, что повышение точности не будет стоить увеличения длины истории (и увеличения использования памяти, времени обработки и т. Д.) На данный момент либо работа выполнена, либо вам нужно найти новую стратегию.

Я думаю, что стоит подумать о простой "мягкой" нейронной сети.