Come semplificare lo smoothing
Per calcolare la regolarizzazione ( o smoothing ) di ogni stato temporale K, occorre calcolare la ricorsione in avanti e indietro fino a K per ogni nodo della catena.
La complessità temporale dello smoothing è pari a O(t2). Pertanto, se il processo da analizzare è composto da una catena di nodi molto lunga, il tempo di esecuzione dell'algoritmo diventa proibitivo perché cresce in modo esponenziale.
Per questa ragione è necessario semplificare la regolarizzazione ( smoothing ) con un algoritmo di calcolo più efficiente come l'algoritmo forward-backward.
Come funziona l'algoritmo forward-backward
Per semplificare l'algoritmo si può calcolare la ricorsione in avanti ( forward ) in una fase preliminare, memorizzando tutti i risultati del filtraggio sui K nodi in un vettore ( spazio di memoria ).
Poi si calcola la ritorsione all'indietro ( backward ) dall'ultimo nodo T fino al primo. A ogni passo si calcola la regolarizzazione sul nodo K.
In questo modo la complessità temporale dello smoothing si riduce a O(t).
Quali sono gli handicap dell'algoritmo
L'algoritmo forward-backward riduce la complessità temporale ( tempo di esecuzione ) ma aumenta la complessità spaziale ( spazio di memoria ).
Se gli stati ( nodi ) della catena sono tanti oppure le informazioni da memorizzare in ogni nodo sono molte, lo spazio di memoria necessario potrebbe diventare troppo grande.
Esempio. Se ogni nodo contiene soltanto una variabile booleana ( vero o falso ) lo spazio di memoria è minimo. Se, invece, ogni nodo contenesse un vettore con migliaia di stringhe alfanumeriche, lo spazio di memoria aumenterebbe a dismisura. Allo stesso modo, una catena con migliaia di nodi è gestibile facilmente da qualsiasi PC mentre una catena con centinaia di miliardi di nodi richiede un computer più potente.
Inoltre, l'algoritmo non si presta a essere usato in problemi online, dove la catena deve essere regolarizzata dopo pochissimi istanti perché le nuove prove arrivano continuamente.
Per risolvere questi problema si ricorre a una variante dell'algoritmo forward-backward detta smoothing fixed lag ( o smothing a ritardo costante / fisso ).
Come funziona l'algoritmo smoothing fixed lag
L'algoritmo di smoothing fixed lag analizza soltanto gli ultimi N nodi della catena a partire dallo stato corrente T.
In questo modo, l'algoritmo limita la complessità computazionale a pochi istanti precedenti abbattendo sia il tempo di esecuzione che lo spazio di memoria.
Qual è la differenza con il forward-backward? Un algoritmo di smoothing forward-backward classico analizza tutti i nodi della catena mentre lo smoothing a ritardo costante soltanto gli ultimi N nodi ( es. ultimi 5 nodi ). Per il resto, in entrambi i casi si utilizza il metodo forward-backward con la memorizzazione del filtraggio in uno spazio di memoria.
Questa soluzione è efficace ma ha il limite di ridurre la regolarizzazione soltanto agli ultimi nodi quando arriva una nuova osservazione ( prova ).
Il resto dei dati nella catena resta invariato.
