Dynamic time warping: come funziona la distorsione temporale dinamica

Il dynamic time warping è usato per confrontare sequenze di valori di lunghezze diverse al fine di rilevare le similarità con il pattern matching. L’algoritmo del DTW genera percorsi di warping dai quali, mediante backtracking e misurazioni delle differenze, si possono riconoscere le similarità nonostante la distorsione temporale o la velocità diversa. Il DTW è utilizzato ad esempio per il riconoscimento vocale, il riconoscimento digitale della firma o anche per l’analisi dei mercati finanziari.

Cosa significa dynamic time warping (DTW)?

Il dynamic time warping, ovvero “distorsione temporale dinamica”, di primo acchito può suonare come una tecnologia di Star Trek. In realtà non si tratta di nient’altro che di un algoritmo che mappa serie temporali o sequenze di valori diverse e le confronta. Con il “warping” è possibile riconoscere le similarità degli schemi corrispondenti tra le sequenze, anche se presentano una lunghezza o una velocità diverse.

In pratica: nel caso occorra allineare due sequenze diverse, l’algoritmo è in grado di riconoscere schemi identici anche con velocità o distanza diverse. Confrontando le firme della stessa persona è possibile individuare le similarità anche con dimensioni del carattere diverse.

Qual è lo scopo del dynamic time warping?

È vero che al primo impatto il DTW sembra un concetto astratto, senza vantaggi pratici evidenti. Ma è proprio il contrario: in svariate applicazioni, il dynamic time warping svolge un’importante funzione di analisi. Questo vale soprattutto per l’analisi di sequenze video e audio, grafici o modelli statistici, dunque per le sequenze che possono essere rappresentate in modo lineare e confrontate. Riconoscendo le corrispondenze, il DTW permette di avviare determinate azioni, segnali o funzioni.

Inoltre, mediante la misurazione e il riconoscimento di schemi nelle serie di valori è possibile rilevare sviluppi di sistema simili anche in lassi di tempo diversi. Per questo motivo l’algoritmo DTW trova applicazione anche in tecnologie all’avanguardia, come il machine learning, il supervised learning o le reti neurali, per addestrare le capacità di analisi e di reazione dei sistemi di autoapprendimento e valutare i record di dati in modo più efficiente.

Come funziona il dynamic time warping?

Per riconoscere schemi e similarità in serie di valori diverse, il DTW cerca corrispondenze ottimali, in inglese “optimal match”, sfruttando i principi “uno-a-molti” o “molti-a-uno”. Si applicano diverse regole e condizioni:

• Ciascun valore di una sequenza deve essere confrontato con uno o più valori della seconda sequenza (e viceversa).
• Il primo valore di una sequenza deve essere confrontato con il primo valore della seconda sequenza.
• L’ultimo valore di una sequenza deve essere confrontato con l’ultimo valore della seconda sequenza.
• La rappresentazione (mappatura) delle serie di valori della prima sequenza sulle serie di valori della seconda sequenza deve aumentare in modo monotono. Le posizioni dei valori all’inizio e alla fine delle sequenze devono quindi coincidere, senza omissioni o sovrapposizioni.

Si ha una corrispondenza ottimale quando tutti i requisiti e le condizioni sono soddisfatti. Si utilizza la cosiddetta “funzione di costo”, che permette di creare una misura della differenza tra i valori delle sequenze. Più la funzione di costo è bassa, più la corrispondenza è ottimale.

L’algoritmo crea inoltre un percorso di warping in grado di riconoscere corrispondenze ottimali anche in sequenze di lunghezze diverse. Il percorso di warping è creato attraverso il backtracking, con cui l’algoritmo rappresenta uno o più valori di una sequenza su punti della seconda sequenza. In questo modo è possibile trovare corrispondenze anche in sequenze temporali di lunghezza diverse nonostante o, meglio, grazie alla distorsione temporale.

Quali sono le applicazioni del dynamic time warping?

Il DTW è utilizzabile ovunque sia possibile rappresentare record di dati in sequenze lineari e confrontarli. Spesso è impiegato come pre e post controllo nell’analisi dei dati, che possono essere di tipo audio o video, alfanumerici o record basati sui Big Data.

Di seguito altri campi d’applicazione del DTW:

• Riconoscimento di schemi nelle sequenze audio: un’importante applicazione del DTW è il riconoscimento vocale. Gli schemi vocali registrati e salvati con il DTW vengono mappati nel pattern matching. In presenza di sequenze audio di diversa lunghezza o velocità, il DTW utilizza la distorsione temporale per creare un percorso di warping. Così si possono riconoscere le similarità anche in vocali e consonanti di lunghezza diversa o pronunciate a una velocità variabile.
• Riconoscimento di schemi nelle sequenze video: per il riconoscimento dei gesti e dei movimenti, il DTW mappa le sequenze video, ad esempio di serie di movimenti. Sono eseguiti un confronto e un riconoscimento di schemi nelle sequenze di movimenti anche in presenza di lunghezze temporali o velocità differenti.
• Riconoscimento di schemi nei dati finanziari: altre importanti applicazioni sono i mercati finanziari e le finanze aziendali. Il DTW si presta per creare previsioni sui cicli finanziari, curve del fatturato o tendenze di borsa. Operando su lassi di tempo diversi, può evidenziare e visualizzare tendenze e cicli simili o identici nei dati di mercato e aziendali. L’analisi è basata sia su previsioni sia sui dati aziendali e finanziari raccolti.

Quali strumenti implementano il dynamic time warping?

Troviamo l’algoritmo DTW nelle librerie di diversi software open source, tra cui:

• DTW Suite con pacchetti di programmazione per Python e R.
• FastDTW offre un’implementazione per gli algoritmi DTW.
• MatchBox implementa il DTW per i segnali audio.
• mlpy e pydtw, librerie di Python per l’apprendimento automatico, offrono anche funzioni DTW.
• Gesture Recognition offre algoritmi DTW per il riconoscimento dei gesti in tempo reale.

Per utilizzare il DTW nel modo più efficiente possibile si ricorre anche alle seguenti tecniche di calcolo rapido:

• PruneDTW
• SparseDTW
• FastDTW
• MultiscaleDTW

Esempio: il dynamic time warping come algoritmo in Python

Per illustrare la complessità del dynamic time warping trovate di seguito un esempio di algoritmo DTW nel codice Python:

def dtw(s, t, window):
    n, m = len(s), len(t)
    w = np.max([window, abs(n-m)])
    dtw_matrix = np.zeros((n+1, m+1))
    
    for i in range(n+1):
        for j in range(m+1):
            dtw_matrix[i, j] = np.inf
    dtw_matrix[0, 0] = 0
    
    for i in range(1, n+1):
        for j in range(np.max([1, i-w]), np.min([m, i+w])+1):
            dtw_matrix[i, j] = 0
    
    for i in range(1, n+1):
        for j in range(np.max([1, i-w]), np.min([m, i+w])+1):
            cost = abs(s[i-1] - t[j-1])
            # take last min from a square box
            last_min = np.min([dtw_matrix[i-1, j], dtw_matrix[i, j-1], dtw_matrix[i-1, j-1]])
            dtw_matrix[i, j] = cost + last_min
    return dtw_matrix

Nella funzione presentata nell’esempio di codice all’inizio vengono passati tre parametri. Prima i due segnali da analizzare vengono passati nei parametri chiamati s e t. Solitamente per i segnali si tratta di matrici o vettori. Il parametro window permette di specificare con quanti altri elementi può avvenire un abbinamento.

Nella funzione viene prima creata una matrice, inizializzata con il valore infinito. La fase centrale del DTW si svolge negli ultimi due cicli for annidati: ai costi che sono salvati nella variabile costs e che si ricavano dalla distanza dei due valori di input sul rispettivo indice si somma il valore salvato nella variabile last_min.

Si tratta di un valore che per via della programmazione dinamica deriva dai valori già calcolati. Si sceglie il minimo dai valori circostanti già calcolati e lo si aggiunge ai costi precedentemente conteggiati. Questo passo stabilisce se due elementi sono abbinati direttamente, se si aggiunge un elemento oppure lo si elimina.

Una volta eseguita la funzione, si riceve una matrice di distanza da cui si può leggere il percorso di warping.

Alternative al dynamic time warping

Ulteriori possibilità alternative al DTW per il riconoscimento di pattern nelle sequenze di valori e serie temporali sono:

• Correlation Optimized Warping (COW)
• Analisi dei dati funzionale
• Modello di Markov nascosto
• Algoritmo di Viterbi