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

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

. Единственный ответ - «это зависит от обстоятельств».

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

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

Я думаю, что лучше изучить простую «мягкую» нейронную сеть.

Мы только что изучили предикторов ветвлений в компьютерной архитектуре (поскольку процессору потребуется слишком много времени, чтобы фактически оценить условие if (ВЫРАЖЕНИЕ), он пытается «угадать» и таким образом сэкономить время) . Я уверен, что в этой области было проведено больше исследований, но это все, о чем я могу думать на данный момент.

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

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

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

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

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

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

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

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

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

(Современные реализации 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

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

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