Fondamenti_mat.ppt

27
Teoria e Tecniche del Riconoscimento Cosimo Distante [email protected] Fondamenti di Matematica

description

1

Transcript of Fondamenti_mat.ppt

  • Teoria e Tecniche del RiconoscimentoCosimo [email protected] di Matematica

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

  • Richiami di Algebra lineareUn vettore a d dimensioni x ed il suo trasposto xt definito daDove tutte le componenti possono essere a valori reali.

  • Denotiamo con M una matrice nd (rettangolare) e la sua trasposta Mt di dimensioni dn Una matrice dd chiamata Simmetrica se mij=mji Anti-simmetrica se mij=-mjiIn generale una matrice chiamata non-negativase mij 0 i,jMatrici

  • MatriciMatrice Identit:La funzione (oppure il simbolo) delta di Kronecker definito come

  • MatriciRango:Il rango di una matrice il numero massimo di righe linearmente indipendenti (o colonne) di A.Propriet di base:Si denota con r(A) il rango della matrice A Se A una matrice quadrata (n=p) allora

  • Autovalori - AutovettoriSe soluzione per qualche x0 allora: denominato autovalore di A x denominato autovettore di ASia A=[ajk] una matrice quadrata (nn).

    ConsideriamoPossiamo riscrivereCio n equazioni algebriche in n incognite x1,,xnPer n = 2

  • Autovalori - Autovettori

  • Autovalori - AutovettoriEsempio:Trovare gli autovettori e corrispondenti autovalori della matrice quadrataSoluzioneI corrispondenti autovettori sono dati daOtteniamo per 1= -2

  • Possiamo moltiplicare una matrice per un vettore come segueMx=ydove

  • Siano un insieme di vettori di uno spazio vettoriale XSiano scalariSe sussiste la seguente relazioneVettori 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

    Spanning a SpaceN.B. La dimensione di uno spazio costituito dal numero minimo di vettori che generano lo spazio

  • Prodotto Interno (dot-Product)Il prodotto interno uno SCALARE!Diremo che un vettore x normalizzato se

  • Prodotto Interno (dot-Product)Perci il prodotto interno una misura di collinearit di due vettori (concetto di similarit)Dalla diseguaglianza di Cauchy-Schwartz ricordiamo che

  • OrtogonalitDue 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)

  • Sottospazi lineariSe sono n vettori linearmente indipendenti di Allora ogni sottoinsieme di essi con kn genera un sottospazio lineare di

    Esempi di sottospazi di sono piani e rette passanti per lorigine

  • Proiezione OrtogonaleSe sottospazio di n allora qualsiasi vettore arbitrariopu essere decomposto nella somma di due vettori:

  • Gram-SchmidtSupponiamo di avere n vettori indipendenti e da essi si vogliono ottenere n vettori ortogonali Scegliamo il primo vettore ortogonale come primo vettore lin. ind.Per ottenere il secondo vettore ortogonale v2 scegliamo y2 ma gli sottraiamo la parte che in direzione di v1Dove a viene scelto in modo che v1v2. Ossia

  • Gram-Schmidt contdPertanto continuando il processo si ottiente alla k-esima compoenentennd5gs

  • Misure di distanza di patternsVettori 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

  • 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 Gaussiano

  • Direzione di coseniSe linformazione 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

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

  • Misura di similarit nella metrica di MinkowskyRappresenta una generalizzazione della distanza Euclidea.Usata per esperimenti di psicologiaDefinita come segueLa distanza city-block ottenuta per =1

  • Misura di similarit di TanimotoAlcuni risultati hanno mostrato che questa distanza stata efficiente in alcuni contesti rispetto ad altri. Definita come segueOriginariamente 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

  • Misura di similarit di TanimotoUsata 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 li-esimo documento. Allora la similarit di due documenti denotati xi e xj ottenuta definendo

  • Distanza di MahalonobisLe 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

    Con linverso della matrice di covarianza di x e y.Svantaggi Il calcolo di per pattern a n dimensioni necessita lacquisizione di un numero di campioni n2Il calcolo di prodotti matrice-vettore di gran lunga pi complesso del prodotto scalare.