Algoritmo di apprendimento automatico per prevedere l'ordine degli eventi?

Question

Semplice domanda di apprendimento automatico. Probabilmente molti modi per risolvere questo:

C'è un flusso infinita di 4 eventi possibili:

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

Gli eventi non sono disponibili in in ordine del tutto casuale. Assumeremo che ci siano alcuni schemi complessi nell'ordine in cui la maggior parte degli eventi arrivano, e il resto degli eventi sono solo casuali. Tuttavia, non conosciamo gli schemi in anticipo.

Dopo aver ricevuto ciascun evento, desidero prevedere quale sarà il prossimo evento in base all'ordine in cui gli eventi sono entrati in passato. Quindi la mia domanda è: Quale algoritmo di machine learning dovrei usare per questo predittore?

Il predittore verrà detto quale fosse il prossimo evento in realtà:

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) 

Si pone la questione di quanto tempo di una storia che il predittore deve mantenere, in quanto il mantenimento di storia infinita non sarà possibile. Lascio questo a te per rispondere. La risposta non può essere infinita per praticità.

Quindi credo che le previsioni dovranno essere fatte con una sorta di storia a rotazione. L'aggiunta di un nuovo evento e la scadenza di un vecchio evento dovrebbero quindi essere piuttosto efficienti e non richiedere la ricostruzione dell'intero modello predittore, ad esempio.

Codice specifico, invece di documenti di ricerca, aggiungerebbe per me il valore immenso alle vostre risposte. Le librerie Python o C sono belle, ma qualsiasi cosa farà.

Aggiornamento: E se più di un evento può accadere simultaneamente in ogni round. Questo cambia la soluzione?

Answer 1

Si pone la questione di quanto tempo di una storia che il predittore dovrebbe mantenere

L'unica risposta è "dipende".

Dipende da quanto accurato deve essere. Non credo che questa strategia possa mai essere accurata al 100% anche con una storia infinita. Prova una cronologia di 10 e otterrai la precisione dell'1%, quindi prova 100 e otterrai la precisione%, ecc. Ecc.

Eventualmente il sistema è preciso come lo desideri essere o scoprirai che l'aumento della precisione non valuterà l'aumento della lunghezza della cronologia (e l'aumento dell'uso della memoria, del tempo di elaborazione ecc ...). A questo punto o hai finito o hai bisogno di trovare una nuova strategia.

Per quello che vale, penso che esaminare una semplice rete neurale "morbida" potrebbe essere un piano migliore.

Answer 2

Abbiamo appena studiato su branch-predictors nell'architettura del computer (poiché il processore impiegherebbe troppo tempo per valutare effettivamente una condizione se (ESPRESSIONE), cerca di "indovinare" e risparmiare un po 'di tempo in quel modo). Sono certo che sono state fatte ulteriori ricerche in questo settore, ma questo è tutto quello che posso pensare al momento.

Non ho visto una configurazione univoca come la vostra, quindi penso che potrebbe essere necessario fare qualche esperimento preliminare da soli. Prova a eseguire la soluzione per X numero di secondi con una cronologia di N slot, qual è il rapporto di correttezza? E confrontalo con la stessa X fissa e le varie finestre di storia N per cercare di trovare il miglior rapporto tra memoria e storia (disegnandoli graficamente).

Se più di un evento può accadere simultaneamente ... è una piccola mente che si piega, ci devono essere alcuni vincoli lì: e se accadesse un numero infinito di eventi alla volta? Uhoh, per te è computazionalmente impossibile. Proverei lo stesso approccio di un solo evento alla volta, tranne quando il predittore è abilitato a prevedere più eventi alla volta.

Answer 3

Questo è essenzialmente un problema di previsione di sequenza, quindi si desidera reti neurali ricorrenti o modelli Markov nascosti.

Se si ha solo un tempo fisso per guardare indietro, gli approcci alla finestra temporale potrebbero essere sufficienti. Prendi i dati della sequenza e li dividi in finestre sovrapposte di lunghezza n. (ad esempio, si divide una sequenza ABCDEFG in ABC, BCD, CDE, DEF, EFG). Quindi si allena un approssimatore di funzione (ad esempio una rete neurale o una regressione lineare) per mappare le prime n-1 parti di quella finestra sull'ennesima parte.

Il predittore non sarà in grado di guardare indietro nel tempo più a lungo della dimensione della finestra. RNN e HMM possono farlo in teoria, ma sono difficili da sintonizzare o, a volte, semplicemente non funzionano.

(Stato dell'arte implementazioni RNN possono essere trovati in PyBrain http://pybrain.org)

Aggiornamento: Ecco il codice pybrain per il vostro problema. (Non l'ho provato, ci potrebbero essere alcuni errori di battitura e roba, ma la struttura complessiva dovrebbe funzionare.)

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

Questa sarà addestrare la rete ricorrente per 1000 epoche e stampare l'errore dopo ogni epoche. Successivamente è possibile verificare previsioni corrette come questa:

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

Questo stamperà una matrice di booleani per ogni evento.

Answer 4

Anziché mantenere una storia completa, si può mantenere informazioni aggregate sul passato (insieme con una storia relativamente breve scorrevole, per essere usato come ingresso alla logica Predictor).

Un'implementazione tentativo potrebbe andare in questo modo:
In poche parole: gestione di una serie di catene di Markov dell'ordine crescente, e classificazione e media loro previsioni

• mantenere un tabella dei conteggi di singoli eventi, lo scopo è quello di calcolare la probabilità di uno dei 4 diversi eventi, senza riguardo a nessuna sequenza.
• mantenere una tabella di bigram conteggi, cioè un conteggio cumulativo eventi osservati [finora]
  Tabella inizia vuoto, sul secondo evento osservare, possiamo memorizzare il primo bigram, con un conteggio di 1.al terzo evento, il bigram costituito dal 2 ° e 3 ° evento viene "aggiunto" alla tabella: incrementando il conteggio di un bigram esistente o aggiunto con il conteggio originale 1, come un nuovo bigram (mai visto così lontano) . ecc.
  In parallelo, mantenere un conteggio totale di bigram nella tabella.
  Questa tabella e il conteggio totale consentono di calcolare la probabilità di un determinato evento, in base all'evento precedente.
• In modo simile, mantenere una tabella di conteggi del trigramma e un conteggio corrente del trigramma totale visto (si noti che questo sarebbe uguale al numero di bigram, meno uno, poiché il primo trigramma viene aggiunto un evento dopo il primo bigram e dopo di ciò uno di ciascuno viene aggiunto ad ogni nuovo evento). Questa tabella del trigramma consente di calcolare la probabilità di un dato evento in base ai due eventi precedenti.
• allo stesso modo, mantenere le tabelle per N-Gram, fino a, ad esempio, 10 grammi (l'algoritmo indicherà se è necessario aumentare o diminuire questo valore).
• mantenere una finestra scorrevole negli ultimi 10 eventi.
• Le tabelle precedenti forniscono la base per la previsione; l'idea generale è di:
  • utilizzare una formula che esprime le probabilità del prossimo evento come una media ponderata delle probabilità individuali in base ai diversi N-grammi.
  • ricompensa la migliore lunghezza individuale di N grammi aumentando il peso corrispondente nella formula; punire le lunghezze peggiori nella maniera opposta. (Prestare attenzione alla probabilità marginale di eventi individuali deve essere presa in considerazione per non favorire gli N-gram che capita di prevedere gli eventi più frequenti, indipendentemente dal relativo valore di previsione associato ad essi)
  • Una volta che il sistema ha "visto" "abbastanza eventi, vedere i valori correnti per i pesi associati ai lunghi N-Gram, e se questi sono relativamente alti, si consideri l'aggiunta di tabelle per mantenere informazioni aggregate su N-Gram più grandi. (Questo fa male purtroppo l'algorightm sia in termini di spazio e di tempo)

Ci possono essere diverse varianti sulla logica generale sopra descritto. In particolare nella scelta della particolare metrica utilizzata per "classificare" la qualità della predizione delle singole lunghezze N-Gram.
Altre considerazioni dovrebbero essere fatte riguardo allo che rileva e si adatta ai possibili cambiamenti nella distribuzione degli eventi (il precedente presuppone una fonte di eventi generalmente ergodica). Un possibile approccio consiste nell'utilizzare due serie di tabelle (combinando di conseguenza le probabilità) e di eliminare periodicamente il contenuto di tutte le tabelle di uno degli insiemi. La scelta del periodo giusto per queste reimpostazioni è un'attività delicata, che bilancia essenzialmente la necessità di volumi statisticamente significativi di cronologia e la necessità di un periodo abbastanza breve per non perdere le modulazioni più brevi ...

Answer 5

I processori utilizzano alcuni trucchi davvero leggeri per prevedere se una succursale si diramerà o meno. Questo li aiuta con un efficiente rivestimento del tubo. Possono non essere così generali come i modelli Markov, ad esempio, ma sono interessanti per la loro semplicità. Here is the Wikipedia article on branch prediction. Vedere la saturazione contatore , e il a due livelli Adaptive Predictor