Teoria e Tecniche del
Riconoscimento
Fondamenti di Matematica
Cosimo Distante
[email protected]
Uno spazio vettoriale lineare X è costituito da un insieme di
elementi (vettori) definito su un campo scalare R che soddisfa le
seguenti condizioni:
Siano  ,    x, y, z  X
1) x, y  X  x  y  X
2) x  y  y  x  X (commutati va)
3) ( x  y )  z  x  ( y  z ) 
(associati va)
4) (   )  x    (   x) 
5)   ( x  y )    x    y 
(distribut iva)
6) (   )  x    x    x 
7)  0  X ' x  X, x  0  x
8) 0,1  0  x  0  1 x  1
Richiami di Algebra lineare
Un vettore a d dimensioni x ed il suo trasposto xt è definito da
 x1 
 
 x2 
x 

 
x 
 d
x t  x1 , x2 , , xd 
Dove tutte le componenti possono essere a valori reali.
Matrici
Denotiamo con M una matrice n×d (rettangolare) e la sua trasposta Mt di dimensioni d×n
M nd
 m11 m12
m
 21 m22
 m31 m32


 
mn1 mn 2
 m1d 
 m2 d 
 m3d 

  
 mnd 
Una matrice d×d è chiamata
• Simmetrica se mij=mji
• Anti-simmetrica se mij=-mji
M td n
 m11
m
 12
  m13

 
m1d
m21  mn1 
m22  mn 2 
m23  mn 3 

   
m2 d  mnd 
( A  B)T  AT  BT
In generale una matrice è chiamata non-negativa
se mij ≥ 0  i,j
( AB)  B A
T
T
T
Matrici
Matrice Identità:
1 0  0


0 1  0
I
IA

AI

A
   


0 0  1
La funzione (oppure il simbolo) delta di Kronecker è definito come
1 se i  j
 ij  
0 altrimenti
Matrici
Rango:
Il rango di una matrice
colonne) di A.
An p è il numero massimo di righe linearmente indipendenti (o
Si denota con r(A) il rango della matrice A
Proprietà di base:
0  r ( A )  min( p, n )
r ( A)  r ( A T )
Se A è una matrice quadrata (n=p) allora
r ( A)  p se e solo se det( A)  0
r ( A  B)  r ( A )  r ( B)
r(AB)  min r(A), r(B)
r ( AA T )  r ( AT A)  r ( A)
Sia Xp1 e bn1 allora l’equazione AX=b
definisce un sistema di n equazioni lineari.
Se n=p e det(A)0 allora l’unica soluzione
X  A 1b
In generale, il sistema di equazioni ammetterà
almeno una soluzione se il rango di A è uguale
al rango della matrice aumentata (A,b)
Autovalori - Autovettori
Sia A=[ajk] una matrice quadrata (nn).
Consideriamo
Ax  x
con  scalare
Se  è soluzione per qualche x0 allora:
•  è denominato autovalore di A
• x è denominato autovettore di A
Possiamo riscrivere ( A  I )x  0
Cioè n equazioni algebriche in n incognite x1,…,xn
 a11 a12 
A
Per n = 2

a
a
21
22


a12   x1  0
a11  
 
 a



a22     x2  0
 21
(a11   ) x1 
a12 x2
a21x1
 (a22   ) x2
0
0
Autovalori - Autovettori
Si noti che
det( A  I)
det( A  I) 
è il determinate caratteristico di A che se nullo allora A è
una matrice singolare
a11  
a12
a21
a22  
 (a11   )( a22   )  a12a21
 2  (a11  a22 )  a11a22  a12a21  0
1 
 Soluzione di A
2 
(a11   ) x1 
a12 x2
a21x1
 (a22   ) x2
x
(1)
1
2
x(2)
0
0
Autovalori - Autovettori
Esempio:
Trovare gli autovettori e corrispondenti autovalori della matrice quadrata
 4.0 4.0
A

  1.6 1.2 
Soluzione
4
4
det( A  I) 
 2  2.8  1.6  0
 1.6 1.2  
1  2
2  0.8
I corrispondenti autovettori sono dati da
(a11   ) x1 
a12 x2
0
( 4.0  2.0) x1 
4.0 x2
0
a21x1
 (a22   ) x2  0
 1.6 x1
 (1.2  2.0) x2  0
x1  2
2
(1)
Otteniamo per 1= -2
x  
1
x2  1
( 2)
1 
per 2  0.8 x   
0.8
Possiamo moltiplicare una matrice per un vettore come segue
Mx=y
 m11 m12

 m21 m22
m
m32
 31

 
m
 n1 mn 2
 m1d 
 x1   y1 
 m2 d    
 x2   y 2 

 m3d     
 

     
xd   y n 


 mnd 
dove
d
yi   mij x j
j 1
Vettori linearmente indipendenti
Siano x1 , x 2 ,, x n  un insieme di vettori di uno spazio vettoriale X
Siano a1 , a2 ,, an  scalari
Se sussiste la seguente relazione
a1x1  a2 x 2    an x n  0 ai  0
x1 , x2 ,, xn 
sono linearment e indipenden ti
Spanning a Space
Sia X uno spazio vettoriale lineare, e sia u1 , u 2 ,, u m  un
sottoinsieme di X.
Possiamo dire che il sottoinsieme u1 , u 2 ,, u m , “spanna” cioè genera
lo spazio X se e solo se
x  X (a1 ,, am ) ' x  a1u1    amu m
N.B. La dimensione di uno spazio è costituito dal numero minimo di
vettori che generano lo spazio
Prodotto Interno (dot-Product)
x

d
y
(x, y )  x  y  x y   xi yi  y x
t
t
i 1
Il prodotto interno è uno SCALARE!
x  xx
t
Diremo che un vettore x è normalizzato se x  1
Prodotto Interno (dot-Product)
x

y
xt y || x ||  || y || cos 
xt y
cos  
|| x ||  || y ||
Perciò il prodotto interno è una misura di collinearità di due vettori
(concetto di similarità)
xy  0  x  y
Dalla diseguaglianza di Cauchy-Schwartz ricordiamo che
x y || x ||  || y ||
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
n
Se x1 , x 2 ,, x n  sono n vettori linearmente indipendenti di 
Allora ogni sottoinsieme di essi x1 , x 2 ,, x k  con k≤n genera un
sottospazio lineare di  n
3

Esempi di sottospazi di
sono piani e rette passanti per
l’origine
Proiezione Ortogonale
Se Π è sottospazio di n allora
qualsiasi vettore arbitrario x   n
può essere decomposto nella
somma di due vettori:
x  xˆ  ~
x
xˆ  Π ~
x Π
x
x
x
~
x

x̂
Proiezione ortogonale
Teorema della Proiezione
Di tutte le decomposizioni della forma x  x  x con x  
quella che corrisponde alla proiezione ortogonale soddisfa la seguente:
x è minimo
Gram-Schmidt
Supponiamo di avere n vettori indipendenti y1 , y 2 ,, y n  e da essi si
vogliono ottenere n vettori ortogonali v1 , v 2 ,, v n 
Scegliamo il primo vettore ortogonale come primo vettore lin. ind.
v1  y1
Per ottenere il secondo vettore ortogonale v2 scegliamo y2 ma gli
sottraiamo la parte che è in direzione di v1
v 2  y 2  av1
Dove a viene scelto in modo che v1v2. Ossia
( v1 , v 2 )  ( v1 , y 2  av1 )  ( v1 , y 2 )  a( v1 , v1 )  0
( v1 , y 2 )
a
( v1 , v1 )
Gram-Schmidt cont’d
Pertanto continuando il processo si ottiente alla k-esima compoenente
k 1
(vi , y k )
vk  yk  
vi
i 1 ( v i , v i )
nnd5gs
Misure di distanza di patterns
Vettori osservabili devono essere rappresentati in uno spazio che
possiede una metrica
Introduciamo il concetto di distanza d(x,y) tra coppie di elementi
dello spazio
C1) d ( x, y )  0
C2) d ( x, y )  d ( y, x)
C3) d ( x, y )  d ( x, z )  d ( z , y )
Distanza Euclidea
x  ( x1 , x2 ,, xn ) y  ( y1 , y2 ,, yn )
d E ( x, y) 
n
 (x  y )
i 1
i
2
i
Distanza di Hamming
Definita per vettori binari, indica il numero di posizioni (elementi)
in cui due vettori differiscono. Le regole C1, C2 e C3 sono valide
Correlazione
Usata per confrontare pattern di segnali, misurandone la loro
similarità.
Siano x  x1,x2 , ,xn  y   y1,y2 , ,yn 
La loro correlazione non-normalizzata è data da C 
n
x y
i 1
i
i
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 Gaussiano
Direzione di coseni
Se 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
x, y  
n
(x  y )
cos  
|| x ||  || y ||
1 best match
cos   
0 x e y sono ortogonali
Si noti che se i vettori sono normalizzati ad 1, allora il coseno coincide
con la correlazione
Misura di similarità nella metrica di Minkowsky
Rappresenta una generalizzazione della distanza Euclidea.
Usata per esperimenti di psicologia
Definita come segue
 n
d M ( x, y )    xi  yi
 i 1

 1/ 




 
La distanza “city-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
d T ( x, y ) 
( x, y )
x  y  ( x, y )
2
2
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
n( A  B )
dT ( A, B) 
n( A)  n( B)  n( A  B)
Misura di similarità di Tanimoto
Usata con successo per valutare la similarità tra documenti
Ciascun 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
( xi , x j )    ik jk   ij
k
 ij
dT ( xi , x j ) 
 ii   jj   ij
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
( x, y )  ( x,y )
La distanza è data da
d ( x, y )  x  y   ( x  y ) t ( x  y )
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.