CAPITOLO IV METODI DI CLASSIFICAZIONE

CAPITOLO IV

METODI DI

CLASSIFICAZIONE

L’idea alla base della tesi, che ha condizionato il lavoro effettuato, non è solamente l’intenzione di classificare un movimento dell’atleta, ma cercare anche di confrontarlo con uno idealmente corretto effettuato da un professionista, così da offrire uno strumento utile ad analizzare le prestazioni di bambini delle scuole calcio, amatori ed appassionati dello sport in genere, oppure in caso di riabilitazione post-operatoria.

Con queste premesse, inizialmente si sono utilizzate tecniche di Template Matching, le quali richiedono dei segnali di riferimento (template) da confrontare con i dati da analizzare. Questi algoritmi sono tra i più utilizzati in settori di classificazione supervisionata e spesso con opportune ottimizzazioni possono portare a buoni risultati, quantomeno in ambito di laboratorio. Inoltre forniscono un punteggio (score) che, se confrontato con delle soglie empiriche, può consentire di attribuire una valutazione di qualità del movimento monitorato.

Siamo quindi partiti dal metodo di Correlazione

incrociata (XCorr) [1] e dal Dynamic Time Warping

(DTW) [2] con degli accorgimenti per ottimizzarne i risultati.

Successivamente, come completamento del lavoro di tesi, si è pensato di utilizzare un metodo di Machine Learning, le Reti Neurali. Questo per cercare di classificare in maniera più efficace i movimenti complessi d’interesse, in modo da confrontare la qualità dei risultati con i due metodi precedentemente citati (Correlazione incrociata e DTW) e avere una visione iniziale sull’ottimizzazione futura della ricerca.

IV 1. CORRELAZIONE

INCROCIATA

La Correlazione incrociata o Cross Correlation (XCorr) è un metodo standard per misurare la similitudine in due forme d’onda. Viene usata frequentemente per ricercare caratteristiche comuni in serie di dati di lunghezze uguali ed i campi di applicazione interessati a queste operazioni variano dal pattern recognition [3] alla crittoanalisi [4].

Per descrivere il funzionamento di questo metodo si considerino due serie di dati x e y di uguale lunghezza, di cui una trasla rispetto all’altra sull’asse temporale e per ogni valore di spostamento viene calcolato l’integrale del

prodotto, così da ottenere un massimo nel caso in cui i segnali combacino. Quando combaciano infatti, danno un apporto totalmente positivo al calcolo dell’aria. Formalmente si può definire il calcolo di correlazione incrociata per due segnali di energia finita x ed y : Rxy(t) = (x  y)(t) =



denota il complesso coniugato di x.

Mentre per due sequenze tempo-discreto x ed y, la correlazione incrociata è definita come:

Rxy[n] = (x  y)[n] =



denota il complesso coniugato di x.

Lo stesso algoritmo effettuato invece tra una sequenza di dati x e sè stessa, viene definito

autocorrelazione e viene molto spesso utilizzato

per cercare dei modelli (“pattern”) che si ripetono all’interno dello stesso segnale. Come si osserva in Fig.4.1, il concetto della correlazione incrociata è molto simile alla convoluzione, ma mentre quest’ultima inverte il segnale prima di traslarlo, l’altra si limita a traslare e moltiplicare.

Si può dire quindi che l’attenzione della XCorr si focalizzerà sulla forma del segnale, permettendo di controllare se lo stesso movimento presenterà uno stesso modello caratteristico che lo contraddistingue.

Fig.4.1 Convoluzione, Correlazione incrociata, Autocorrelazione

Questo modo di operare però, visto il caso in esame, può porre un limite nella qualità dei risultati. Le attività da riconoscere infatti non solo sono molto varie e complesse, ma anche sensibili alla velocità di esecuzione con cui vengono svolte, determinando delle traslazioni temporali dei dati. La velocità, grandezza fisica di cui bisogna tener conto, può variare a seconda del soggetto che esegue il movimento, ma anche per ragioni funzionali: ad esempio un calcio caricato per dare potenza piuttosto che un calcio caricato per effettuare un passaggio.

Per questa ultima ragione è stato approfondito anche il metodo DTW.

IV 2. DTW - DYNAMIC TIME

WARPING

L’algoritmo DTW è stato introdotto negli anni ‘60 e successivamente esteso a molte aree di ricerca come il motion capture [5], l’analisi di sequenza genetiche [6] e prima fra tutte il riconoscimento di linguaggio (speech recognition) [7], [8].

La ragione per cui è diventato popolare è la sua efficienza nel misurare la similarità tra serie temporali di dati minimizzando l’effetto della traslazione e distorsione nel tempo. Ciò avviene tramite una trasformazione non lineare, detta

warping, applicata ad uno o entrambi i segnali in

modo da rintracciare forme simili anche con allineamenti sull’asse x diversi (Fig.4.2). L’unica restrizione dell’algoritmo è che le due sequenze di dati da analizzare devono avere lo stesso tempo di campionamento, problema comunque aggirabile con un ricampionamento.

Fig.4.2 A) due segnali con forma simile ma diverso allineamento sull’asse x B) metodo di ricerca affinità adottato dal DTW

In molti casi la misura di similarità avviene con il calcolo della distanza Euclidea tra punti allineati sull’asse del tempo (Fig.4.3), mentre l’algoritmo DTW cerca la distanza minima tra gli interi segnali, calcolando cosi le distanze parziali fra punti anche non allineati a livello temporale (Fig.4.2B, Fig.4.4).

Fig.4.3 Misura similarità con distanza Euclidea

Considerando quindi due serie di dati X=(x1,..xn) e

Y=(y1,..ym) il primo passo che compie l’algoritmo è

costituire la matrice delle distanze locali o matrice

di costo locale. Queste distanze non sono altro che

le differenze euclidee calcolate fra tutte le coppie di dati delle due serie.

Una volta calcolata la matrice, l’algoritmo va a trovare l’allineamento ottimo tra le due sequenze, collegando i primi due elementi (angolo in basso a sx della matrice) con gli ultimi due (angolo in alto a dx della matrice), passando tra dei minimi trovati secondo un opportuno algoritmo (Fig.4.5). Questo allineamento tracciato viene definito come

percorso di warping ottimo o allineamento ottimo e

formalmente è cosi costituito: p = (p1, p2, …., pK)

con pl = (pi , pj) ϵ [1 : N] * [1 : M] per l ϵ [1 : K] .

dove N e M sono le lunghezze delle due sequenze da analizzare e K è la lunghezza dell’allineamento trovato.

L’allineamento deve soddisfare però alcuni criteri fondamentali:

 Condizioni al contorno (Boundary condition)

p1= (1,1) e pk= (N,M). I punti di partenza e

fine allineamento devono corrispondere rispettivamente al primo e all’ultimo punto dei segnali

 Condizione di monotonicità n1<n2<…<nK e

m1<m2<…<mk per garantire l’ordine

 Condizione di ampiezza passo che impedisce

salti troppo ampi tra un valore e l’altro del percorso. Normalmente sono considerati possibili spostamenti di (1,1), (1,0), (0,1)

Fig.4.5 Matrice delle distanze con percorso di warping tracciato (allineamento)

Si è definito ottimo l’allineamento tracciato, perché non è l’unico che può essere trovato con la coppia di segnali X ed Y, ma è quello che minimizza la distanza tra i due segnali. La distanza tra due punti, definita anche come

funzione costo, possiamo calcolarla:

dij = ‖ xi - yj ‖ con i ϵ [1 : N] e j ϵ [1 : M], dove i e j

corrispondo ai punti considerati nel calcolo della distanza tra le due serie.

Combinando un percorso trovato con la funzione costo otteniamo la distanza globale di un allineamento sommando i risultati parziali: dp ( X, Y ) =





L

l 1

d(xnl , yml), dove l corrisponde ad

un elemento dell’allineamento e xn e ym sono gli

elementi delle due serie per i quali è stato considerata la distanza locale.

Fra tutti gli allineamenti è poi possibile ottenere più di un allineamento ottimo. In teoria quindi si dovrebbero calcolare tutti i possibili allineamenti e poi considerarne uno tra gli ottimi, con distanza minima (punteggio più basso): processo questo che aumenterebbe in maniera esponenziale la complessità computazionale rispetto alla lunghezza delle serie di dati. Il DTW invece, adotta un sistema di programmazione dinamica per arrivare ad una complessità computazionale di O(N*M).

L’algoritmo in definitiva sfrutta la funzione costo per trovare l’allineamento ottimo:

DTW(X , Y )=dp (X , Y )=min { dp (X; Y ) con p ϵ PN*M }

dove PN*M _{rappresenta tutti i possibili allineamenti,}

e dp rappresenta il costo globale del pecorso p

considerato nella nuova matrice di costo globale D. I passi dell’algoritmo sono:

1. Riempimento prima riga D(1,1)= d(1,1)

dove N corrisponde al numero di colonne 2. Riempimento prima colonna

D(i , 1) = D(i-1 , 1) + d(i , 1) con i ϵ [2 : M] dove M corrisponde al numero di righe 3. Riempimento resto della matrice

D(i, j) = min { D(i –1 , j-1); D(i-1 , j);D(i , j-1)} +

d(xi , yj)

con i ϵ [1 , N] e j ϵ [1 : M]. 4. Fase di backtraking

Una volta che è stata completata la matrice di costo globale l’algoritmo può passare alla fase di

backtraking (punto 4.), che ricostruisce

l’allineamento ottimo di warping partendo dal

punto finale p(N,M) fino al punto iniziale p(1,1), con la logica di Figura 4.6 dove si osserva un

codice tratto dalla funzione

[Dist,D,k,w,rw,tw]=dtw(r,t,pflag), trovata in letteratura [9].

Dati di input della funzione:  r prima sequenza

 t seconda sequenza

 pflag parametro per richiedere di graficare o

meno i risultati: 0 non grafica, 1 grafica Dati di output:

 Dist distanza ottima

 D matrice di costo globale

 w percorso ottimo di warping

 rw primo segnale dopo warping

 tw secondo segnale dopo warping

Fig.4.6 Parte di codice MATLAB relativo alla fase di backtracking

Come si può notare dal codice la fase di backtraking parte dall’ultimo punto riferito a p(N,M), procede muovendosi a ritroso lungo i minimi locali che troviamo nelle tre direzioni possibili fino al punto p(1,1), uscendo così dal ciclo while.

Si osserva di seguito il risultato di una prova con dati ed algoritmo elaborati in ambiente Matlab:

a)

c)

d)

Fig.4.7 DTW fra segnali di un mote, Asse_x-> a),b) Asse_y->c),d) ; a),c) matrice di costo globale ed allineamento trovato ; b),d) grafico dei segnali originali e dopo aver subito il warping

Nelle Figura 4.7 è raffigurato un esempio di risultato grafico inerente a due semplici movimenti del braccio, registrati dall’accelerometro biassiale di un mote Iris (l’allineamento tracciato sul grafico si presenta sull’altra diagonale, non citata precedentemente, per via della struttura a matrice consona all’ambiente MATLAB).

La posizione di partenza di entrambi i movimenti è presentata in Figura 4.8:

Fig.4.8 Disposizione del braccio rispetto al corpo

Dalla suddetta posizione di partenza si sono effettuati due movimenti:

1. Una rotazione intorno all’asse longitudinale all’omero per un angolo di 90° (Fig.4.9a) 2. Una rotazione intorno all’asse longitudinale

all’asse longitudinale all’avambraccio (Fig.4.9b).

Essendo il mote posizionato sulla mano, con asse x longitudinale all’avambraccio e l’asse y trasversale, si nota che per entrambi i movimenti il segnale ricevuto sull’asse x è molto simile (Fig.4.7b), visto che non cambia mai la sua inclinazione rispetto all’asse di gravità, restituendo come risultato di allineamento una diagonale quasi perfetta sulla matrice di costo globale (Fig.4.7a) (indice di distanza bassa fra i due segnali), mentre per l’asse y si possono notare più variazioni tra un movimento e l’altro (Fig.4.7d), visto che nel secondo movimento l’inclinazione dell’asse y rispetto all’asse di gravità varia molto di più rispetto al primo movimento.

Esistono inoltre dei metodi per ottimizzare l’efficacia dell’algoritmo:

 Funzione passo (slope costraint). Spesso

l’algoritmo DTW non si limita a trovare la similarità tra due serie di dati, ma tende a trovare delle corrispondenze irrealistiche tra caratteristiche di una serie identificate in un tratto lungo di essa e caratteristiche dell’altra serie identificate in tratti molto più brevi. Questo provoca degli errori nei risultati, ma questo effetto indesiderato si può smorzare tramite dei vincoli su passi consecutivi dell’allineamento. Ad esempio dopo aver tracciato k passi in una direzione si può costringere l’algoritmo a cambiarla per l passi prima di poter tornare seguire la direzione iniziale (Fig.4.10).

 Vincolo sul percorso globale. Premettendo

che l’algoritmo DTW ha un costo computazionale di O(N*M) ed un’occupazione di memoria di due matrici N*M, questo vincolo sul percorso globale, introdotto in vari articoli [8], va a ottimizzarne il costo computazionale e la sensibilità al calcolo della similarità fra le serie di dati.

 Vincolo sulla finestra di warping. È un

vincolo che impedisce al percorso tracciato sulla matrice di oltrepassare dei limiti di validità nelle zone meno importanti (Fig.4.11a) riguardo al ritrovamento dell’allineamento, in modo da diminuire il costo computazionale, ed impedire di dare importanza a similarità in punti non corretti (Fig.4.11b). Viene espresso come |i(k)-j(k)|  r. Dove i e j rappresentano i punti lungo gli assi x ed y, mentre r indica la larghezza della finestra di warping.

b) Fig.4.11 Vincolo sulla finestra di warping

 Funzione peso. Questo termine w(k),

applicato alla funzione costo inizialmente considerata, va a favorire più o meno alcuni percorsi tenendo conto della differenza di fase tra punti consecutivi, fornendo cosi un’ottimizzazione dei risultati, specialmente nei casi in cui si desidera porre l’attenzione alla forma del segnale. Formalmente il calcolo della distanza tra due pattern A e B diventa quindi: DAB= MIN [





dove il numeratore rappresenta la sommatoria delle distanze locali d(p(k)) pesate dal coefficiente w(k), mentre il denominatore rappresenta il fattore di normalizzazione (N=

_

Questa funzione peso può essere implementata in due forme base [10]:

- Forma simmetrica

w(k) = (i(k) - i(k - 1)) + ( j(k) - j(k - l)), con fattore di normalizzazione N=I+J, dove I e J sono le lunghezze delle sequenze.

- Forma asimmetrica

w(k) = (i(k) - i(k - 1)) con N=I o

w(k) = (j(k) - j(k - l)) con N=J, con i e j che corrispondono agli elementi delle due serie.

Esiste poi un ulteriore funzione peso ottimizzata, introdotta da Young-Seon Jeong et al. [10], denominata Funzione

peso modificata logisticamente (Modified logistic weigth function o MLWF), la quale

presenta la possibilità di pesare secondo necessità la funzione costo, giocando con i valori delle variabili.

Formalmente: w(i)=[ )) ( exp( 1 max c m i g w    ]

dove i=1,2,…m, m rappresenta la lunghezza della sequenza da pesare, mc è

il punto medio della sequenza, wmax è il

limite massimo (upper bound) per la funzione peso, mentre g è una costante empirica che controlla la curvatura della funzione. Teoricamente g può assumere valori tra 0 ed infinito ma in pratica è stata studiata per alcuni casi noti: peso

sigmoidale (0.25), due pesi dstinti (g=3) (Fig.12). In relazione a questo si deve fare

attenzione al valore usato visto che usando una g=0 si ricade nel caso del DTW non pesato, mentre al diminuire della differenza di fase |i-j| ed all’aumentare della variabile g si verifica il caso della distanza Euclidea fra punti allineati. Per concludere l’argomento funzione peso, qualsiasi metodo si usi si otterrà comunque una versione dell’algoritmo definita WDTW, dove la W iniziale sta per Weigth (peso).

Fig.4.12 Funzione peso MLWF in

funzione della lunghezza della sequenza con diversi valori di g

Per quanto riguarda l’efficacia dell’algoritmo DTW, con qualsiasi ottimizzazione lo si implementi, essa presenta comunque delle imprecisioni, dovute proprio alla natura dell’algoritmo. Il fatto di voler dare un significato ai valori sull’asse y solamente attraverso un warping dell’asse x, fa sì infatti, che un punto di una serie di dati possa essere allineato con molti altri della serie di confronto. Inoltre l’algoritmo fallisce nel riconoscimento di alcune caratteristiche ovvie a prima vista come picchi, minimi locali e plateau. Questo errore si verifica in casi in cui queste caratteristiche del segnale hanno valori anche solo leggermente più alti o più bassi.

Per queste ragioni è stata considerata anche una variazione dell’algoritmo chiamata Derivate Dynamic Time Warping (DDTW).

III 2.1 DDTW – DERIVATE DTW

La differenza del DDTW [11] rispetto al classico DTW è il fatto di non riferirsi più ai dati grezzi che compongono la serie ma alle derivate locali dei dati, favorendo l’attenzione dei risultati sulle forme caratteristiche assunte dal segnale anche se traslato sull’asse x e variato per piccole grandezze sull’asse y (Fig.4.13).

Per stimare la derivata si può usare per semplicità la seguente forma:

DDx(q)= 2 2 / )) (( ) (q_i q_i1  q_i1q_i1 con 1<i<m DDx(c)= 2 2 / )) (( ) (cici1  ci1ci1 con 1<i<n

dove q e c rappresentano le serie temporali di dati, ed i DDx rappresentano semplicemente la media

delle pendenze tra il punto i-esimo con il punto alla sua sinistra (i-1) e tra i punti vicini all’i-esimo (i+1 e i-1) . Mentre la distanza tra due punti non sarà più quella Euclidea, ma sarà la radice quadrata della differenza delle due derivate:

dij= DDx(q(i))DDx(c(j))

Con questo metodo, non potendo stimare la derivata al primo e all’ultimo dato delle serie temporali, si considerano rispettivamente le stime del secondo e del penultimo.

Per quanto riguarda i metodi di ottimizzazione ed i vincoli di cui tenere conto, valgono tutti gli stessi accorgimenti dell’algoritmo DTW compresa la

funzione peso, definendo l’algoritmo WDDTW

(Weigth Derivate Dynamic Time Warping).

Analizzando invece la complessità computazionale a confronto con quella del DTW, risulta praticamente uguale a parte l’aggiunta del passaggio per la stima delle derivate. A livello empirico entrambi gli algoritmi risultano quindi con complessità computazionale di O(N*M).

IV 3. RETI NEURALI

Le reti neurali artificiali o più semplicemente NN (Neural Network) [12], [13], [14], rappresentano un metodo di Machine Learning che sfrutta algoritmi di apprendimento per poter simulare attività tipiche del cervello umano come percezione di immagini, riconoscimento di forme, comprensione del linguaggio, coordinamento senso-motorio. Devono perciò avere caratteristiche tali da approssimare la struttura e l’efficienza di una rete neurale reale.

Normalmente si dice che per soddisfare certe caratteristiche si debba “realizzare una rete di

elementi molto semplici che sia una struttura distribuita, massicciamente parallela, capace di apprendere e quindi di generalizzare (cioè produrre uscite in corrispondenza di ingressi non incontrati durante l’addestramento)” (Prof. Beatrice Lazzerini

[12]). Questo elemento “molto semplice” simulerà un neurone la cui struttura può essere riassunta con un sommatore in serie ad un filtro come mostrato in Fig.4.14.

Fig.4.14 Modello neurone

I valori x1, x2,…xn rappresentano gli ingressi o le

uscite dei nodi (neuroni) precedenti, i wn

rappresentano i pesi delle connessioni e la f è la cosiddetta funzione di attivazione, la quale può avere diverse forme: a soglia, lineare, lineare a tratti, sigmoidale, rappresentando quindi la logica di uscita del nodo in questione. Ogni nodo sarà connesso ad un altro costituendo delle strutture di diverso genere, tra cui quelle completamente connesse o quelle stratificate.

La struttura delle reti neurali e le sue caratteristiche come numero di nodi, connessioni, numero di strati neurali, funzione di attivazione, incideranno sulle capacità della rete di produrre uscite più vicine possibili a quelle desiderate. Per quanto concerne il funzionamento delle reti neurali, la prima e fondamentale fase da affrontare è l’addestramento o training della rete attraverso un algoritmo opportuno. Di quest’ultimo se ne può identificare tre tipologie: supervisionato, non supervisionato e di rinforzo. Nel primo caso, al momento dell’invio dei dati di ingresso, al sistema è nota la risposta che deve dare; nel secondo vengono inviati solamente dati senza alcuna conoscenza a priori (usato principalmente per algoritmi di estrazione caratteristiche); nel terzo invece è presente un sistema di premiazione (o punizione) per ogni determinata azione senza fornire nessuna informazione dettagliata sulla migliore scelta da compiere.

La fase di addestramento è sicuramente la più importante ai fini dell’esito dell’esperimento. Esso dipende molto dalla qualità del training set e quindi dalle serie di dati di ingresso, dei quali si conosce l’uscita (nel caso supervisionato). Questi dati di ingresso infatti, scorrono lungo la rete fornendo inizialmente una risposta scorretta e lontana da quella desiderata, per poi indurre il sistema a modificare i propri parametri e

migliorare l’uscita. In questo modo si avrà un errore di classificazione al di sotto di una certa soglia stabilita.

Uno degli algoritmi più usati per risolvere la fase di apprendimento è l’algoritmo di Back Propagation, nel quale dopo aver calcolato l'uscita

in corrispondenza ad un certo input, si calcola l'errore rispetto all'uscita desiderata per quell'input, e si propaga la necessaria correzione dei pesi wn dallo strato d'uscita a quello

d’ingresso.

Sempre considerando un addestramento supervisionato, la fase che segue è la validazione, con la quale attraverso un validation-set di campioni con caratteristiche uguali ai precedenti (training-set) e con uscite note, si verificherà la validità del metodo di riconoscimento.

Infine, la fase di verifica reale viene data analizzando un test-set, cioè una serie di misure non note a priori che sono classificate in base ai parametri strutturali che sono venuti fuori dall’apprendimento.

Prima di vedere più nel dettaglio il tipo di rete usata nel presente lavoro, si deve citare una delle più ricorrenti classificazioni di genere delle reti neurali, relativa alla struttura di queste:

 reti feeedforward (propagazione in avanti) nelle quali il flusso di dati procede da un ingresso ad un uscita senza inversioni;

 reti ricorsive le quali presentano dei cicli (definiti loop) al loro interno, permettendo così di avere come ingresso non solo i dati correnti ma anche informazioni relative agli stati passati. Questo le rende particolarmente funzionali per l’analisi di sequenze o serie temporali.

IV 3.1 ESN - ECHO STATE NETWORK

Le reti ESN [15] [16] [17], usate nel presente lavoro di tesi, fanno parte di un sottogruppo di reti ricorsive chiamato “Reservoir network”. Esse presentano una rete di neuroni con connessioni sparse e cicliche chiamata Reservoir (Fig.4.15). Nella loro forma più semplice hanno uno strato di ingresso collegato in maniera unidirezionale con il Reservoir e quest’ultimo è connesso bidirezionalmente con uno strato di uscita. Per quanto riguarda i pesi delle connessioni, quelli di ingresso sono fissati in maniera random e non modificabili, quelli di uscita invece sono gli unici che subiscono le variazioni in base all’addestramento.

La struttura di quest'architettura si basa fortemente sulla proprietà delle reti ricorsive di apprendere a priori ed il vantaggio principale è la loro velocità di apprendimento ed esecuzione.

Fig.4.15 Modello ESN generale

L'idea di fondo in questo tipo di rete neurale, è quella di guidare con il segnale d'ingresso una grande rete ricorrente con pesi fissati e random, facendo in modo che ogni nodo fornisca una differente risposta non lineare. Così facendo si ottengono una o più uscite che sono il risultato di un combinazione lineare di tutte le risposte della rete ricorrente. Il punto cruciale di quest'architettura è il fatto che gli unici pesi addestrabili della rete sono quelli di uscita del combinatore lineare.

Per validare l’approccio caratteristico di queste reti si possono considerare gli studi di Schiller e Steil [18]. Tali studi hanno mostrato come nei metodi tradizionali di addestramento delle NN ricorsive, dove vengono aggiornati tutti i pesi, le variazioni più significative avvengono nei pesi dello strato di uscita.

Nel campo delle neuroscienze invece è stato studiato un comportamento simile da Peter F.

Dominey [19] nel cervello dei mammiferi, specialmente nel riconoscimento vocale da parte degli esseri umani.

Infine si può dire che tutte le architetture di modelli basate su un Reservoir vengono riunite nel nome di “Reservoir Computing”.