Подтвердить что ты не робот

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

Простой вопрос машинного обучения. Вероятно, существует множество способов решить эту проблему:

Существует поток бесконечный из 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 хороши, но что-то будет делать.

Обновление: И что, если в каждом раунде может происходить несколько событий одновременно. Изменило ли это решение?

4b9b3361

ОТВЕТЫ

Ответ 1

Это по существу проблема с предсказанием последовательности, поэтому вам нужны рекуррентные нейронные сети или скрытые марковские модели.

Если у вас есть только фиксированное время, чтобы оглянуться назад, можно подойти к временному окну. Вы берете данные последовательности и разбиваете на перекрывающиеся окна длиной n. (например, вы разбиваете последовательность ABCDEFG на ABC, BCD, CDE, DEF, EFG). Затем вы тренируете аппроксиматор функции (например, нейронную сеть или линейную регрессию), чтобы отобразить первые n-1 части этого окна на n-ю часть.

Ваш предсказатель не сможет оглянуться назад во времени дольше, чем размер вашего окна. RNN и HMM могут делать это теоретически, но их трудно настроить или иногда просто не работают.

(Современные реализации RNN можно найти в PyBrain http://pybrain.org)

Обновление: вот ваш код для диагностики вашего мозга. (Я его не тестировал, могут быть некоторые опечатки и прочее, но общая структура должна работать.)

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

Это будет печатать массив булевых элементов для каждого события.

Ответ 2

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

Предварительная реализация может выглядеть следующим образом:
В двух словах: Управление множеством марковских цепей возрастающего порядка и градуировкой и усреднением их прогнозов

  • сохранить таблицу отдельных счетчиков событий, цель состоит в том, чтобы вычислить вероятность любого из 4 разных событий без какой-либо последовательности.
  • сохранить таблицу счетчиков bigram, т.е. кумулятивный счет наблюдаемых событий [пока]
    Стол начинается пустым, во втором наблюдении события мы можем сохранить первый биграмм с подсчетом 1. на третье событие, bigram, сделанный из 2-го и 3-го событий, "добавлен" в таблицу: либо увеличивает счетчик существующий bigram или добавленный с оригинальным счетчиком 1, как новый (никогда невидимый-далекий) bigram. и т.д.
    Параллельно держите общее количество биграмм в таблице.
    Эта таблица и общая сумма позволяют рассчитать вероятность данного события на основе предыдущего события.
  • Аналогичным образом храните таблицу счетчиков триграмм и подсчитывает общее количество триграмм (обратите внимание, что это будет равно числу биграмм, минус один, поскольку первая триграмма добавляется к одному событию после первого битрама, и после этого каждый из них добавляется с каждым новым событием). Эта таблица триграмм позволяет вычислять вероятность данного события на основе двух предыдущих событий.
  • аналогично, сохраняйте таблицы для N-граммов, до, скажем, 10-граммов (алгоритм подскажет, нужно ли нам увеличивать или уменьшать это).
  • сохранить скользящие окна в последние 10 событий.
  • Приведенные выше таблицы служат основой для прогнозирования; общая идея заключается в следующем:
    • используйте формулу, которая выражает вероятности следующего события как взвешенное среднее индивидуальных вероятностей, основанное на разных N-граммах.
    • вознаградить лучшую индивидуальную N-граммовую длину, увеличив соответствующий вес в формуле; наказать худшую длину в обратном порядке. (Остерегайтесь предельной вероятности отдельных событий, которые необходимо учитывать, чтобы мы не одобряли N-граммы, которые могут предсказать наиболее частые события, независимо от относительного плохого прогнозирующего значения, связанного с ними). ​​
    • Как только система увидит достаточно событий, просмотрите текущие значения для весов, связанных с длинными N-граммами, и если они относительно высоки, подумайте о добавлении таблиц, чтобы сохранить агрегированную информацию о более крупных N-граммах. (Это, к сожалению, вредит algorightm как по пространству, так и по времени).

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

Ответ 3

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

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

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

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

Для чего стоит думать, что поиск простой "мягкой" нейронной сети может быть лучшим планом.

Ответ 4

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

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

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

Ответ 5

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