machine - modelos de clasificacion python

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

Question

Pregunta de aprendizaje automático simple. Probablemente hay numerosas formas de resolver esto:

Hay una secuencia infinita de 4 eventos posibles:

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

Los eventos no vienen en orden completamente aleatorio. 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 según el orden en que los eventos hayan llegado en el pasado. Entonces mi pregunta es: ¿Qué algoritmo de aprendizaje automático debería usar para este predictor?

Luego se le dirá al predictor cuál fue el siguiente evento en realidad:

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)

Surge la pregunta de cuánto tiempo de una historia debe mantener el predictor, ya que no será posible mantener una historia infinita. 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 historia continua. 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 documentos de investigación, me agregaría un inmenso valor a sus respuestas. Las bibliotecas de Python o C son agradables, pero cualquier cosa servirá.

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

Answer 1

Surge la pregunta de cuánto tiempo de una historia debe mantener el predictor

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. Prueba un historial de 10 y obtendrás un x% de precisión, luego prueba con 100 y obtendrás un% de precisión, etc.

Finalmente, debe encontrar que el sistema es tan preciso como lo desea o que el aumento en la precisión no justificará el aumento en la longitud de la historia (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 red neuronal "suave" podría ser un mejor plan.

Answer 2

Acabamos de estudiar acerca branch-predictors en la arquitectura de la computadora (porque el procesador tardaría demasiado en evaluar realmente una condición si (EXPRESIÓN), intenta ''adivinar'' y ahorrar algo de tiempo 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 de forma simultánea ... eso es un poco incómodo, tiene que haber algunas restricciones allí: ¿qué pasa si un número infinito de eventos sucede 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

En lugar de mantener un historial completo, se puede mantener información agregada sobre el pasado (junto con un historial de deslizamiento relativamente corto, que se utilizará como entrada a la lógica del Predictor).

Una implementación tentativa podría ser así:
En pocas palabras: administrar un conjunto de cadenas de Markov de orden creciente y calificar y promediar sus predicciones

• mantenga 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 recuentos de bigramas, es decir, un recuento acumulativo de los eventos observados [hasta ahora]
  La tabla comienza vacía, luego del segundo evento observado, podemos almacenar el primer bigram, con un conteo de 1. Además del tercer evento, el bigram hecho de los eventos segundo y tercero es "agregado" a la tabla: ya sea incrementando el conteo de un bigram existente o agregado con el recuento original 1, como un nuevo bigram (nunca visto). etc.
  En paralelo, 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 birams, menos uno, ya que el primer trigrama se agrega un evento después del primer bigrama, y ​​luego se agrega uno de cada uno con 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:
  • use una fórmula que exprese las probabilidades del próximo evento como un promedio ponderado de las probabilidades individuales basado en los diferentes N-gramas.
  • 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 a los N-grams que predicen los eventos más frecuentes, independientemente del valor de predicción relativamente pobre asociado a 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 lamenta lastimosamente el algoritmo tanto en términos de espacio como de tiempo)

Puede haber varias variaciones en la lógica general descrita 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.
Deben hacerse otras consideraciones con respecto a la detección y adaptación 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 reinicios es un asunto complicado, que esencialmente equilibra 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 4

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 hacia atrás, los enfoques 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.

(Las implementaciones RNN de última generación se pueden encontrar en PyBrain http://pybrain.org )

Actualización: Aquí está el código de Pybrain para su problema. (No lo he probado, puede haber errores tipográficos y otras 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 entrenará a la red recurrente para 1000 épocas e imprimirá el error después de cada época. 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 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. branch-predictors . Consulte el contador de saturación y el predictor adaptativo de dos niveles