Algoritmo de aprendizaje automático para predecir el orden de los eventos?

Question

Pregunta de aprendizaje automático simple. Probablemente muchas maneras de resolver esto:

Hay una corriente infinita de 4 eventos posibles:

'event_1', 'event_2', 'event_4', 'event_4'

Los eventos no entran en el fin completamente al azar. Supondremos que hay algunos patrones complejos en el orden en que aparecen la mayoría de los eventos, y el resto de los eventos son simplemente aleatorios. Sin embargo, no sabemos los patrones con anticipación.

Después de recibir cada evento, quiero predecir cuál será el siguiente evento en función del orden en que los eventos han llegado en el pasado. Entonces mi pregunta es: ¿Qué algoritmo de aprendizaje automático debo usar para este predictor?

El predictor Luego, se le lo era en realidad el próximo evento:

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) 

Se plantea la cuestión de cuánto tiempo de una historia que el predictor debe mantener, ya que mantener la historia infinita no será posible. Dejaré esto a tu disposición para responder. La respuesta no puede ser infinte, aunque por razones prácticas.

Así que creo que las predicciones tendrán que hacerse con algún tipo de historial continuo. Por lo tanto, agregar un nuevo evento y caducar un evento anterior debería ser bastante eficiente y no requerir la reconstrucción de todo el modelo de predicción.

Código específico, en lugar de artículos de investigación, me agregaría valor inmenso a sus respuestas. Las bibliotecas de Python o C son agradables, pero cualquier cosa servirá.

Actualización: Y, ¿qué pasa si más de un evento puede ocurrir simultáneamente en cada ronda. ¿Eso cambia la solución?

Answer 1

Se plantea la cuestión de cuánto tiempo de una historia que el predictor debe mantener

La única respuesta es "depende".

Depende de qué tan preciso debe ser esto. No creo que esta estrategia pueda ser 100% precisa incluso con una historia infinita. Pruebe un historial de 10 y obtendrá x% de precisión, luego pruebe 100 y obtendrá y% de precisión, etc. etc.

Eventualmente debe encontrar el sistema tan preciso como lo desee ser o encontrará que el aumento en la precisión no valdrá la pena el aumento en la longitud del historial (y el aumento en el uso de la memoria, el tiempo de procesamiento, etc.). En este punto, ya sea trabajo hecho, o necesita encontrar una nueva estrategia.

Por lo que vale, creo que buscar en una simple red neuronal "suave" podría ser un mejor plan.

Answer 2

Acabamos de estudiar acerca de branch-predictors en la arquitectura de la computadora (Debido a que el procesador tardaría demasiado en evaluar realmente una condición si (EXPRESIÓN), intenta 'adivinar' y ahorrar algo de esa manera). Estoy seguro de que se han realizado más investigaciones en esta área, pero eso es todo lo que puedo pensar en este momento.

No he visto una configuración única como la tuya, por lo que creo que deberías hacer algunos experimentos preliminares por tu cuenta. Intente ejecutar su solución por X cantidad de segundos con un historial de N ranuras, ¿cuál es la relación de corrección? Y compare eso con la misma X fija y variando ranuras de historial N para tratar de encontrar la mejor relación de historial de memoria (graficarlas).

Si puede suceder más de un evento simulatáneamente ... eso es un poco incómodo, tiene que haber algunas restricciones allí: ¿qué pasa si infinito número de eventos suceden a la vez? Uhoh, eso es computacionalmente imposible para ti. Intentaría el mismo enfoque como solo un evento a la vez, excepto que cuando el predictor esté habilitado, prediga múltiples eventos a la vez.

Answer 3

Esto es esencialmente un problema de predicción de secuencia, por lo que desea redes neuronales recurrentes o modelos ocultos de Markov.

Si solo tiene un tiempo fijo para mirar atrás, los acercamientos de ventana de tiempo podrían ser suficientes. Usted toma los datos de secuencia y los divide en ventanas superpuestas de longitud n. (por ejemplo, divide una secuencia ABCDEFG en ABC, BCD, CDE, DEF, EFG). Luego, entrena un aproximador de función (por ejemplo, red neuronal o regresión lineal) para asignar las primeras n-1 partes de esa ventana a la enésima parte.

Su predictor no podrá mirar atrás en el tiempo más que el tamaño de su ventana. Los RNN y los HMM pueden hacerlo en teoría, pero son difíciles de sintonizar o, a veces, simplemente no funcionan.

(Estado del arte implementaciones RNN se pueden encontrar en PyBrain http://pybrain.org)

Actualización: Aquí está el código pybrain para su problema. (Yo no lo he probado, puede haber algunos errores tipográficos y esas cosas, pero la estructura general debería funcionar.)

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() 

Esto formará a la red recurrente durante 1000 épocas e imprimir el error después de cada épocas. Luego puede verificar las predicciones correctas como esta:

net.reset() 
for i in sequence: 
    next_item = net.activate(i) > 0.5 
    print next_item 

Esto imprimirá una matriz de booleanos para cada evento.

Answer 4

En lugar de mantener un historial completo, uno puede mantener información agregada sobre el pasado (junto con una historia relativamente corto de deslizamiento, para ser utilizado como entrada a la lógica Predictor).

Una aplicación provisional podría ir así:
En pocas palabras: La gestión de un conjunto de cadenas de Markov de orden aumentando, y clasificación y promedio sus predicciones

• mantienen una tabla de recuentos de eventos individuales, el propósito es calcular la probabilidad de cualquiera de los 4 eventos diferentes, sin tener en cuenta ninguna secuencia.
• mantener una tabla de bigram recuento, es decir, un recuento acumulativo de los eventos observados [hasta ahora]
  Tabla comienza vacío, en el segundo evento observar, podemos almacenar el primer bigram, con un recuento de 1.Además del tercer evento, el gran evento de los eventos 2º y 3º se "agrega" a la mesa: ya sea incrementando el conteo de un bigram existente o agregando el conteo original 1, como un nuevo bigram (nunca visto) . etc.
  Paralelamente, mantenga un recuento total de los bigramas en la tabla.
  Esta tabla y la cuenta total permiten calcular la probabilidad de un evento dado, basado en el evento anterior.
• De manera similar, mantenga una tabla de recuentos de trigramas, y una cuenta corriente del trigrama total visto (tenga en cuenta que esto sería igual al número de bigrams, menos uno, ya que el primer trigrama se agrega un evento después del primer bigram , y luego de eso se agrega uno de cada evento nuevo). Esta tabla de trigrama permite calcular la probabilidad de un evento dado en función de los dos eventos precedentes.
• Asimismo, guarde las tablas para N-Grams, hasta, por ejemplo, 10 gramos (el algoritmo indicará si necesitamos aumentar o disminuir esto).
• mantener una ventana deslizante en los últimos 10 eventos.
• Las tablas anteriores proporcionan la base para la predicción; la idea general es:
  • usar una fórmula que exprese las probabilidades del próximo evento como un promedio ponderado de las probabilidades individuales basadas en los diferentes N-grams.
  • recompensa la mejor longitud de N-gramo individual al aumentar el peso correspondiente en la fórmula; castigar las peores longitudes en la forma inversa. (Tenga en cuenta que se debe tener en cuenta la probabilidad marginal de eventos individuales para que no favorezcamos los N-grams que predicen los eventos más frecuentes, independientemente del valor de predicción relativamente pobre asociado con ellos)
  • Una vez que el sistema ha "visto "suficientes eventos, vea los valores actuales para los pesos asociados con los N-Grams largos, y si estos son relativamente altos, considere agregar tablas para mantener la información agregada sobre N-Grams más grandes. (Esto, desafortunadamente, perjudica a la algorightm tanto en términos de espacio y tiempo)

No puede haber varias variaciones en la lógica general descrito anteriormente. En particular, en la elección de la métrica particular utilizada para "calificar" la calidad de predicción de las longitudes de N-Gram individuales.
Se deben realizar otras consideraciones con respecto a detectando y adaptándose a posibles cambios en la distribución de eventos (lo anterior supone una fuente de eventos generalmente ergódica). Un enfoque posible es utilizar dos conjuntos de tablas (combinando las probabilidades en consecuencia) y eliminar periódicamente los contenidos de todas las tablas de uno de los conjuntos. Elegir el período correcto para estos restablecimientos es un asunto complicado, esencialmente equilibrando la necesidad de volúmenes de historia estadísticamente significativos y la necesidad de un período suficientemente corto para no perder las modulaciones más cortas ...

Answer 5

Los procesadores usan algunos trucos realmente livianos para predecir si una declaración de rama se bifurcará o no. Esto los ayuda con un revestimiento de tubería eficiente. Puede que no sean tan generales como los modelos de Markov, por ejemplo, pero son interesantes por su simplicidad. Here is the Wikipedia article on branch prediction. Ver el de saturación Contador, y el de dos niveles de adaptación Predictor