Fundamentals of Computing Continuous Dynamic Time Warping in 2D under Different Norms

Il paper dimostra che il Continuous Dynamic Time Warping (CDTW) non può essere calcolato esattamente sotto la norma euclidea 2 utilizzando solo operazioni algebriche, proponendo invece un algoritmo esatto per norme che approssimano tale norma e stabilendo fondamenti tecnici generalizzabili ad altre norme e misure correlate.

L'essenziale

Immagina di avere due persone che camminano lungo due sentieri diversi in una foresta. Entrambi vogliono arrivare dalla stessa partenza alla stessa destinazione, ma uno cammina veloce, l'altro lento, e a volte si fermano a guardare un fiore o a scattare una foto.

Il problema: Come misuriamo quanto sono "simili" questi due percorsi?
Se guardiamo solo i punti dove si sono fermati (le foto), potremmo dire che sono molto diversi perché i tempi non coincidono. Ma se guardiamo l'intero viaggio, notiamo che hanno percorso lo stesso sentiero, solo a velocità diverse.

Questo è il cuore del Dynamic Time Warping (DTW): un modo per allineare due curve (o percorsi) che si muovono a velocità diverse, trovando il modo migliore per "incollare" un punto del primo percorso a un punto del secondo.

La versione "continua" di questo problema (CDTW) è ancora più raffinata: non guarda solo le foto (i punti fermi), ma immagina che le persone siano in movimento costante lungo il sentiero, come un filmato fluido.

Ecco cosa hanno scoperto gli autori di questo paper, spiegato con parole semplici:

1. Il problema della "Misura Perfetta" (La Norma Euclidea)

Immagina di dover calcolare la distanza tra due punti su una mappa. Di solito usiamo il righello (la distanza in linea retta, o "norma 2-norm").
Gli autori dicono: "C'è un problema matematico enorme qui."
Se provi a calcolare la distanza esatta tra questi due percorsi fluidi usando la classica distanza in linea retta, ti imbatti in numeri che sono impossibili da scrivere esattamente con le operazioni matematiche normali (addizione, moltiplicazione, radici quadrate). Sono numeri "trascendentali", come il numero Pi greco o il logaritmo di certi numeri.

• L'analogia: È come se ti chiedessero di costruire un ponte perfetto usando solo mattoni di legno, ma la lunghezza esatta del ponte richiedesse un pezzo di legno fatto di "aria pura". Non puoi costruirlo esattamente con i tuoi strumenti.
• La conseguenza: Non esiste un algoritmo che possa dare la risposta esatta per questo caso specifico usando solo la matematica classica.

2. La Soluzione Creativa: I "Sentieri Poligonali"

Poiché non possiamo usare la misura perfetta (il cerchio perfetto), gli autori dicono: "Usiamo un poligono che sembri un cerchio!"
Invece di usare la distanza in linea retta (che crea un cerchio come forma di riferimento), usano una forma a "fetta di pizza" o un esagono, o un ottagono.

• L'analogia: Invece di cercare di disegnare un cerchio perfetto con un compasso (che nel nostro caso matematico è impossibile da calcolare esattamente), usiamo un esagono. Se disegni un esagono con molti lati, sembra quasi un cerchio!
• Il risultato: Usando queste forme "a spigoli" (norme poligonali), il calcolo diventa possibile e preciso. Più lati ha il poligono, più si avvicina alla perfezione del cerchio.

3. La "Valle" Magica

Per trovare il percorso migliore tra i due sentieri, gli autori hanno scoperto che esiste una sorta di "valle" invisibile nel terreno matematico.

• L'analogia: Immagina di dover scendere da una montagna. La strada migliore non è andare dritto, ma seguire la valle più profonda dove l'acqua scorrerebbe naturalmente. Gli algoritmi devono trovare questa "valle" matematica.
• La scoperta: Hanno dimostrato che, con le loro nuove regole (usando i poligoni), questa valle esiste sempre ed è sempre "in salita" in modo prevedibile, rendendo facile per il computer trovare la strada migliore senza perdersi.

4. L'Algoritmo: Un Nastro Trasportatore di Calcoli

Come fanno a calcolare tutto questo? Usano un metodo chiamato "Programmazione Dinamica".

• L'analogia: Immagina di dover calcolare il costo di un viaggio passo dopo passo. Invece di ripartire da zero ogni volta, il computer tiene un "nastro trasportatore" di informazioni. Quando arriva a un nuovo punto del sentiero, prende il calcolo fatto prima, lo aggiorna e lo passa al punto successivo.
• La novità: Hanno creato un modo per gestire questo nastro trasportatore anche quando i sentieri sono complessi e bidimensionali (su un piano), usando le "valle" di cui parlavamo prima per evitare di dover fare calcoli infiniti.

In sintesi

Questo paper è come un manuale di istruzioni per un esploratore che deve misurare la somiglianza tra due viaggi complessi.

1. Avviso: Se usi il righello classico (distanza euclidea), il calcolo esatto è matematicamente impossibile (i numeri diventano troppo strani).
2. Trucco: Usa un righello "a spigoli" (poligono) che sembra un righello curvo. Così i calcoli tornano a essere gestibili.
3. Metodo: Segui le "valle" nascoste nel terreno per trovare il percorso più economico.
4. Risultato: Ora possiamo calcolare la somiglianza tra curve complesse in modo esatto e veloce, senza dover approssimare tutto a pezzi piccoli (discretizzazione), ma mantenendo la fluidità del movimento.

È un lavoro fondamentale che ci dice: "Non possiamo avere tutto perfetto, ma possiamo avere qualcosa di quasi perfetto che possiamo calcolare davvero".

Sommario tecnico

1. Il Problema

Il Continuous Dynamic Time Warping (CDTW) è una misura di similarità tra curve poligonali che supera i limiti del DTW discreto e della distanza di Fréchet. Mentre il DTW discreto considera solo i vertici delle curve (ignorando la continuità e soffrendo di tassi di campionamento diversi) e la distanza di Fréchet è sensibile agli outlier (basandosi sul massimo della distanza), il CDTW minimizza l'integrale di percorso delle distanze tra punti corrispondenti lungo le curve, trattandole come oggetti continui.

Il problema centrale affrontato nel paper è la computabilità esatta e l'efficienza algoritmica del CDTW in due dimensioni (2D) sotto diverse norme (in particolare la norma Euclidea 2-norm e le approssimazioni poligonali).
Le sfide principali identificate sono:

• La complessità dell'integrazione continua su spazi di parametri bidimensionali.
• La natura dei numeri coinvolti nel calcolo sotto la norma Euclidea (potenzialmente non calcolabili esattamente con operazioni algebriche).
• La mancanza di algoritmi esatti efficienti per il caso 2D sotto la norma 2, a differenza del caso 1D o della norma 1.

2. Metodologia

Gli autori adottano un approccio che combina analisi geometrica, teoria dei numeri e programmazione dinamica.

• Formulazione Geometrica: Lo spazio dei parametri delle due curve viene discretizzato in una griglia di "celle" (ogni cella corrisponde a una coppia di segmenti delle curve). All'interno di ogni cella, il problema si riduce a trovare un percorso ottimo tra due punti.
• Analisi dei "Valley" (Valli): Viene introdotta una caratterizzazione geometrica dei percorsi ottimali basata sulle "valli" del terreno di costo. Una valle è una linea lungo la quale la distanza tra i punti delle curve è minimizzata localmente. Gli autori dimostrano che per la loro formulazione, sotto qualsiasi norma, esistono sempre valli con pendenza positiva, che guidano i percorsi ottimali.
• Teoria dei Numeri e Impossibilità Esatta: Per la norma Euclidea (2-norm), gli autori analizzano la natura algebrica dei valori risultanti. Utilizzando il Teorema di Baker sulla teoria dei numeri trascendenti, dimostrano che il valore del CDTW e i punti di piega dei percorsi ottimali possono essere numeri trascendenti. Questo implica che il problema non è risolvibile esattamente nel modello di calcolo algebrico (ACMQ) che permette solo operazioni aritmetiche e estrazione di radici.
• Algoritmo di Approssimazione Esatta: Per superare l'impossibilità della 2-norm, gli autori propongono un algoritmo esatto per una classe di norme con insiemi di livello poligonali (norme $G_{\psi(R_k)}$). Queste norme approssimano la norma Euclidea. L'algoritmo utilizza la programmazione dinamica per propagare funzioni di costo ottimali attraverso la griglia delle celle.
• Propagazione di Funzioni Quadratiche: A differenza degli approcci precedenti che discretizzavano le curve, questo metodo mantiene la continuità discretizzando la norma. Le funzioni di costo ottimali lungo i bordi delle celle sono rappresentate come funzioni piecewise quadratiche (a tratti quadratiche). L'algoritmo gestisce la propagazione di queste funzioni utilizzando strutture dati a pila (stack) e arrangiamenti di linee geometriche.

3. Contributi Chiave

1. Impossibilità di Calcolo Esatto per la 2-Norm:

   • Dimostrazione rigorosa che il CDTW sotto la norma Euclidea può coinvolgere numeri trascendenti (es. combinazioni di logaritmi di numeri algebrici).
   • Conseguenza: Non esiste un algoritmo esatto che utilizzi solo operazioni algebriche (somma, prodotto, radici) per calcolare il CDTW 2D Euclideo. Questo giustifica l'uso di approssimazioni.

2. Caratterizzazione Geometrica Robusta:

   • Dimostrazione che per la formulazione di CDTW proposta, sotto qualsiasi norma, esiste sempre una "valle" (linea di minimo locale) con pendenza positiva. Questo garantisce che i percorsi ottimali abbiano una struttura prevedibile e gestibile algoritmicamente, generalizzando risultati precedenti limitati alla norma 1.

3. Algoritmo Esatto per Norme Poligonali:

   • Sviluppo di un algoritmo di programmazione dinamica che calcola il CDTW esatto per norme i cui insiemi di livello sono poligoni convessi regolari (o trasformazioni lineari di essi).
   • L'algoritmo propaga funzioni quadratiche a tratti attraverso la griglia dello spazio dei parametri, evitando la discretizzazione delle curve stesse.

4. Schema di Approssimazione (1+ε):

   • Utilizzando l'algoritmo esatto per le norme poligonali, gli autori forniscono uno schema di approssimazione $(1+\varepsilon)$ per la norma Euclidea. Scegliendo un poligono regolare con $k = O(\varepsilon^{-1/2})$ lati, si ottiene un'approssimazione arbitrariamente precisa senza discretizzare le curve di input.

4. Risultati

• Teorici:
  • Il CDTW 2D sotto la norma 2 è intrinsecamente non calcolabile esattamente con operazioni algebriche a causa della presenza di numeri trascendenti.
  • Esistono percorsi ottimali con punti di piega le cui coordinate sono numeri trascendenti.
• Algoritmici:
  • Viene proposto un algoritmo esatto per norme poligonali.
  • La complessità temporale è analizzata in $O(N \cdot k^2 \log(k) \alpha(k))$, dove $N$ è il numero totale di pezzi quadratici generati e $k$ è il numero di lati del poligono della norma.
  • Viene evidenziato che il vincolo combinatorio per limitare $N$ in 2D (analogo al $O(n^5)$ del caso 1D) rimane un problema aperto, poiché le configurazioni geometriche in 2D possono portare a un comportamento di "raddoppio" dei pezzi che non si verifica in 1D.
• Approssimazione:
  • È possibile ottenere un'approssimazione $(1+\varepsilon)$ per la norma Euclidea scegliendo una norma poligonale con un numero di lati proporzionale a $\varepsilon^{-1/2}$.

5. Significato e Impatto

Questo lavoro rappresenta un passo fondamentale nella comprensione teorica e pratica del CDTW in 2D:

• Chiusura Teorica: Risolve la questione della calcolabilità esatta per la norma Euclidea, dimostrando che l'approccio esatto "puro" è impossibile e spingendo la comunità verso approcci di approssimazione o simbolici più complessi.
• Nuovo Paradigma Algoritmico: Introduce un metodo che non discretizza le curve (mantenendo la continuità geometrica) ma discretizza la norma di misura. Questo permette di ottenere risultati esatti per una vasta classe di norme e approssimazioni controllate per la norma Euclidea.
• Generalizzazione: I risultati sulla struttura delle "valli" e sulle proprietà delle funzioni di costo si generalizzano ad altre misure di similarità di curve, come la distanza di Fréchet parziale e la similarità di Fréchet lessicografica.
• Implicazioni Pratiche: Fornisce una base solida per applicazioni che richiedono una similarità robusta tra traiettorie (es. riconoscimento di firme, matching di mappe, clustering di traiettorie), offrendo un compromesso tra precisione e complessità computazionale gestibile.

In sintesi, il paper stabilisce i fondamenti matematici per il calcolo del CDTW in 2D, dimostrando i limiti fondamentali della norma Euclidea e fornendo un algoritmo robusto ed efficiente basato su norme poligonali come alternativa praticabile e teoricamente fondata.