Teoria e Tecniche del Riconoscimento

Cosimo Distantecosimo.distante@imm.cnr.it

Fondamenti di Matematica

Uno spazio vettoriale linearespazio vettoriale lineare X è costituito da un insieme di elementi (vettori) definito su un campo scalare R che soddisfa le seguenti condizioni:

Xyx , )1 Xyxva)(commutati )2 Xxyyx

va)(associatix)(x)( 4)

)()( )3

zyxzyx

iva)(distributxx)( 6)

)( )5

xyxyx

Xzy, x,, Siano

x0 xX,x ' )7 X01x1 0x0 1,0 )8

Richiami di Algebra lineare

dx

xx

2

1

x

Un vettore a d dimensioni x ed il suo trasposto xt è definito da

dt xxx ,,, 21 x

Dove tutte le componenti possono essere a valori reali.

Denotiamo con M una matrice n×d (rettangolare) e la sua trasposta Mt di dimensioni d×n

ndnn

d

d

d

dn

mmm

mmmmmmmmm

21

33231

22221

11211

M

nddd

n

n

n

tnd

mmm

mmmmmmmmm

21

32313

22212

12111

M

Una matrice d×d è chiamata • Simmetrica se mij=mji

• Anti-simmetrica se mij=-mji

TTT ABAB )(

TTT BABA )(

In generale una matrice è chiamata non-negativase mij ≥ 0 i,j

Matrici

Matrici

Matrice Identità:

AAIIAI

100

010001

La funzione (oppure il simbolo) delta di Kronecker è definito come

altrimenti0 se1 ji

ij

MatricipnA

Rango:Rango:Il rango di una matrice è il numero massimo di righe linearmente indipendenti (o colonne) di A.

Proprietà di base: ),min()(0 npr A

Si denota con r(A) il rango della matrice A

)()( Trr AA

Se A è una matrice quadrata (n=p) allora

0)det( se solo e se )( AA pr)()()( BABA rrr

)(),(min)( BAAB rrr )()()( AAAAA rrr TT

Sia Xp1 e bn1 allora l’equazione AX=bdefinisce un sistema di n equazioni lineari.Se n=p e det(A)0 allora l’unica soluzione

bAX 1In generale, il sistema di equazioni ammetterà almeno una soluzione se il rango di A è uguale al rango della matrice aumentata (A,b)

Autovalori - Autovettori

2221

1211

aaaa

A

Se è soluzione per qualche x0 allora:• è denominato autovaloreautovalore di A• x è denominato autovettoreautovettore di A

Sia A=[ajk] una matrice quadrata (nn).

Consideriamo scalare con xAx

Possiamo riscrivereCioè n equazioni algebriche in n incognite x1,…,xn

0xIA )(

Per n = 2

00

2

1

2221

1211

xx

aaaa

0)(0)(

222121

212111

xaxaxaxa

Autovalori - Autovettori

0)(0)(

222121

212111

xaxaxaxa

Si noti che )det( IA è il determinate caratteristico di A che se nullo allora A è una matrice singolare

2221

1211)det(aa

aaIA

0)(

))((

2112221122112

21122211

aaaaaa

aaaa

2

1

Soluzione di A

1)1(x )2(x2

Autovalori - AutovettoriEsempio:Esempio:

2.16.10.40.4

A

Trovare gli autovettori e corrispondenti autovalori della matrice quadrata

06.18.22.16.144

)det( 2

IA

SoluzioneSoluzione21

8.02

0)(0)(

222121

212111

xaxaxaxa

0)0.22.1(6.100.4)0.20.4(

21

21

xxxx

I corrispondenti autovettori sono dati da

Otteniamo per 1= -2 12

2

1

xx

12)1(x

8.01

8.0per )2(2 x

Possiamo moltiplicare una matrice per un vettore come segueMx=y

ndndnn

d

d

d

y

yy

x

xx

mmm

mmmmmmmmm

2

1

2

1

21

33231

22221

11211

dove

d

jjiji xmy

1

Siano un insieme di vettori di uno spazio vettoriale X nx,,x,x 21

naaa ,,, 21Siano scalari

Se sussiste la seguente relazione

0 02211 inn aaaa xxx

tiindipenden elinearment sono 21 nx,,x,x

Vettori linearmente indipendenti

Sia X uno spazio vettoriale lineare, e sia un sottoinsieme di X.

Possiamo dire che il sottoinsieme , “spanna” cioè genera lo spazio X se e solo se

mu,,u,u 21

Spanning a Space

mu,,u,u 21

mmm aaaX uuxx 111 a ' ),,(

N.B. La dimensione di uno spazio è costituito dal numero minimo di vettori che generano lo spazio

Prodotto Interno (dot-Product)

xxx t

xxyy

xyyxyxyx t

d

iii

t yx 1

),(

Il prodotto interno è uno Il prodotto interno è uno SCALARE!SCALARE!

Diremo che un vettore x è normalizzato se 1x

Prodotto Interno (dot-Product)

xxyy

cos|||||||| yxyx t

yxyx 0

||||||||

cosyx

yx

t

Perciò il prodotto interno è una misura di collinearità di due vettori (concetto di similarità)

Dalla diseguaglianza di Cauchy-Schwartz ricordiamo che

|||||||| yxyx t

OrtogonalitàDue vettori x,y sono ortogonali tra loro se (x,y)=0 (x y)

Possiamo estenderlo anche a spazi. Un vettore x di X è ortogonale ad un sottospazio X1 se esso è ortogonale ad ogni vettore di X1 (x X1)

Due spazi X1 e X2 sono ortogonali se ogni vettore di X1 è ortogonale ad ogni vettore di X2 (X1 X2)

Dati alcuni vettori linearmente indipendenti come possiamo convertirli in un insieme di vettori ortogonali che spannano lo stesso spazio?

Ortogonalizzazione di Gram-Schmidt

Sottospazi lineari

Se sono n vettori linearmente indipendenti di Allora ogni sottoinsieme di essi con k≤n genera un sottospazio lineare di

Esempi di sottospazi di sono piani e rette passanti per l’origine

nx,,x,x 21n

kx,,x,x 21n

3

Proiezione Ortogonale

x~x

x̂

x

x nx

Se Π è sottospazio di n allora qualsiasi vettore arbitrariopuò essere decomposto nella somma di due vettori: Π~Πˆ~ˆ x x xxx

Proiezione ortogonale

Teorema della ProiezioneDi tutte le decomposizioni della forma conquella che corrisponde alla proiezione ortogonale soddisfa la seguente:

xxx x

minimo è x

Gram-SchmidtSupponiamo di avere n vettori indipendenti e da essi si vogliono ottenere n vettori ortogonali

ny,,y,y 21

nv,,v,v 21

Scegliamo il primo vettore ortogonale come primo vettore lin. ind.11 yv

Per ottenere il secondo vettore ortogonale v2 scegliamo y2 ma gli sottraiamo la parte che è in direzione di v1

122 vyv a

Dove a viene scelto in modo che v1v2. Ossia),(),( 12121 vyvvv a ),(),( 1121 vvyv a 0

),(),(

11

21

vvyv

a

Gram-Schmidt cont’dPertanto continuando il processo si ottiente alla k-esima compoenente

i

k

i ii

kikk v

vvyvyv

1

1 ),(),(

nnd5gs

Misure di distanza di patterns

Vettori osservabili devono essere rappresentati in uno spazio che possiede una metrica

Introduciamo il concetto di distanzadistanza d(x,y) tra coppie di elementi dello spazio

),(),(),( C3)),(),( C2)

0),( C1)

yzdzxdyxdxydyxd

yxd

Definita per vettori binari, indica il numero di posizioni (elementi) in cui due vettori differiscono. Le regole C1, C2 e C3 sono valide

Distanza di Hamming

Distanza Euclidea),,,( 21 nxxx x ),,,( 21 nyyy y

n

iiiE yxyxd

1

2)(),(

CorrelazioneUsata per confrontare pattern di segnali, misurandone la loro similarità. Siano

La loro correlazione non-normalizzata è data da

Oss. Se x e y sono vettori dello spazio Euclideo, allora la correlazione coincide col prodotto interno

Metodi di correlazione sono adatti a rilevare segnali quasi periodici contaminati da rumore Gaussianorumore Gaussiano

n,x,,xx 21x n,y,,yy 21y

n

iii yxC

1

Direzione di coseniSe l’informazione rilevante dei pattern o dei segnali da analizzare è contenuta solo nei moduli delle loro componenti, allora la similarità può essere misurata in termini di direzione di coseni

Siano nyx ,

||||||||)(cosyx

yx

Si noti che se i vettori sono normalizzati ad 1, allora il coseno coincide con la correlazione

ortogonali sono e 0matchbest 1

cosyx

Misura di similarità nella metrica di MinkowskyRappresenta una generalizzazione della distanza Euclidea.Usata per esperimenti di psicologiaDefinita come segue

),(/1

1

n

iiiM yxyxd

La distanza “city-blockcity-block” è ottenuta per =1

Misura di similarità di Tanimoto

Alcuni risultati hanno mostrato che questa distanza è stata efficiente in alcuni contesti rispetto ad altri. Definita come segue

),(),(),( 22 yxyx

yxyxdT

Originariamente introdotta per il confronto di insiemi.Siano A e B due insiemi non ordinati distinti (non-numerici) di elementi (per. Es. identificatori o descrittori di documenti, o feature discrete)La similarità tra A e B può essere definita come la variazione del numero di elementi in comune rispetto al numero totale di elementi.Sia n(X) il numero di elementi in X allora

)()()()(),(

BAnBnAnBAnBAdT

Misura di similarità di Tanimoto

Usata con successo per valutare la similarità tra documentiCiascun singolo descrittore può essere fornito di un proprio peso.

Per esempio, supponiamo che ik sia il peso del k-esimo descrittore per l’i-esimo documento. Allora la similarità di due documenti denotati xi e xj è ottenuta definendo

ijk

jkikji xx ),(

ijjjii

ijjiT xxd

),(

Distanza di Mahalonobis

Le componenti di x e y possono essere generate da un processo stocastico che definisce una dipendenza statistica tra esse.Si definisce un prodotto interno come segue

La distanza è data da

),(),( yxyx

)()(),( yxyxyxyxd t

Con ψ è l’inverso della matrice di covarianza di x e y.

Svantaggi• Il calcolo di ψ per pattern a n dimensioni necessita l’acquisizione di un numero di campioni »n2

•Il calcolo di prodotti matrice-vettore è di gran lunga più complesso del prodotto scalare.