Trattamento dei dati non strutturati

Settimana 1

Lezione 1 – 30/11

• Introduzione

  Il nostro scopo sarà andare a ridurre la dimensionalità dei dati per ottenere degli indici sintetici. Infatti, avere troppe variabili può andare a penalizzare i dati. La condensazione del dato, inoltre, può riuscire ad avere un’interpretazione più chiara del mio fenomeno. Un altro motivo per cui vogliamo una riduzione della dimensionalità è per la compressione di informazioni (foto, testi…). Ovviamente la riduzione deve essere fatta perdendo la minore quantità di informazione. Un altro tema che tocchiamo riguarderà i dati non-numerici.

• SVD

  Problema che ci poniamo: Nei nostri problemi abbiamo sempre una matrice X di dimensioni n x K dove k è minore di n. Per noi questa precisazione non è fondamentale, ma è la condizione che si pone necessaria in quasi tutti gli altri ambiti. Per ora questa matrice è numerica. La riga della matrice viene indicata con U e indica il profilo dell’unità statistica. Tendenzialmente, in questi contesti guarderemo la matrice per righe: questo, perché, tipicamente abbiamo problemi che riguardano le unità statistiche e non le variabili (esempio dei punteggi condensati per il benessere nelle singole città). Questa è semplicemente una scelta di prospettiva, perché tutto ciò che diciamo può essere anche fatto sulle colonne. Un’altra assunzione che facciamo è che la matrice X è a rango pieno (pari a k). Quando il rango è pieno, le k colonne sono indipendenti. Quello che cerchiamo di trovare è una matrice X approssimata di rango inferiore, in particolare di rango p < k, dove p è scelto da noi. La matrice X^ deve avere le stesse dimensioni ma rango inferiore (sarà una matrice ridondante: possiamo togliere colonne senza perdere informazioni). Il problema che si pone è andare a vedere la differenza tra X e X^: useremo la norma di Frobenius. Dobbiamo scegliere la matrice X^ nxk di rango p che minimizza questa norma. La norma di Frobenius generica è data da:

  ²∥ ∥∧X X min=- F

  Questa al quadrato è pari alla somma delle norme al quadrato delle colonne (norma̅̅ ( ) ∑T ²√∥ ∥A A A A√→ = =rt euclidea).ijF i j,

  Per calcolare l’approssimazione X^ serve la SVD (Singular Value Decomposition). La SVD è un risultato generale che serve per qualsiasi matrice nxk. L’idea fondamentale è quella di scomporre la mia matrice in 3 matrici: U, D, t (V). Vediamo come sono fatte singolarmente: TDVUX =- V: matrice le cui colonne sono gli autovettori normalizzati della matrice t(X)X. questo vale perché una matrice simmetrica edefinita positiva mi garantisce l’esistenza di k autovettori ortogonali. Le colonne sono multipli della matrice t(X)X e quindi autovettori. Questa matrice è ortogonale: t (V)V = Vt(V) = I; D: matrice diagonale che contiene gli oggetti a radice positiva di D². Questi valori sono chiamati singolari (da qui il nome della procedura), ordinati in modo crescente per convenzione; U: matrice rettangolare, con colonne ortonormali (k colonne).

  La dimostrazione della decomposizione si basa sul teorema spettrale, però la formula vera e propria si dimostra così: Con la seconda formula capiamo che le colonne di U sono gli autovettori normalizzati di Xt(X); gli autovalori associati agli autovettori di U e V sono i valori singolari di D. Le colonne di V prendono il nome di colonne singolari destre, quelli di U sinistri.

  Leghiamo a questa espressione una formula un po’ diversa che ci porterà a capire a che cosa effettivamente serve la SVD nei dati. Posso scrivere la SVD in un modo equivalente:

  k Dove u_i e v_i sono le righe i-esime delle matrici U e V.

  ∑X Z= σ i ii =1 tZ ·→ = vui i i

  Le matrici Z hanno delle proprietà interessanti. Ad esempio, il rango di queste matrici è pari a 1 perché le colonne risultato come multipli dell’unica colonna u_i. Poi, il prodotto scalare di Frobenius tra le matrici Z è dato da: Questo calcolo ci porta a dire che le matrici Z sono ortonormali. La nuova scrittura (con le z), ci permette di dire, rispetto a quella precedente, che posso vedere la X come combinazione lineare di matrici. Sommare le matrici significa sommare cella per cella: di fatto stiamo stratificando la X -> esprimo in modo più chiaro che sto ricostruendo X per strati. Nella prima formula, invece, utilizzo un classico prodotto matriciale. Ricordiamo che, sempre riferito alla formula con Z, sommando p radici di rango 1 otteniamo, almeno in questo caso, una matrice di rango p. Sostanzialmente ci predisponiamo ad usare il teorema della proiezione.

• Teorema di Eckart Young

  Questo risultato viene usato per risolvere il nostro problema: trovare la matrice X^ che minimizza la norma di Frobenius. La soluzione che cerchiamo è unica. La soluzione che cerchiamo è data dal teorema di Eckart Young. Questo teorema dice che:

  | ²∥∧ iX X =- m nF p∧ ∑X Z→ = σ i ii =1

  Qual è l’errore che io compio facendo questa approssimazione? Per risolvere il problema di stima, dunque, pendiamo i primi p termini della seconda formula della SVD. Dove, i termini da p+1 a k vanno a rappresentare una varianza residua. Come possiamo leggere il risultato precedente se messo nella formula iniziale? Le dimensioni delle singole matrici dipendono dal fatto che riduco la matrice D a p righe, ponendo a 0 i sigma dal p+1 al k. La dimostrazione del teorema è data da: Scelgo una M diagonale conveniente così che anche il secondo pezzo (*) vada a zero. Scelgo di porre sulla diagonale di M i sigma maggiori affinché la prima parte sia minima.

Lezione 2 – 1/12

• Utilizzo statistico della SVD

  Nella lezione precedente abbiamo costruito una soluzione matematica al problema dell’approssimazione della matrice X con una matrice X^. La soluzione è data dalla SVD tagliata all’ordine p grazie al teorema di Eckart. Ora formalizziamo il problema originario e vediamo se la soluzione può essere applicata. Il nostro scopo è la riduzione della dimensionalità dei dati. Ora guardiamo la matrice X per righe (le osservazioni). Ogni vettore riga è un punto dello spazio k∈ ℝx Rk.iIl nostro scopo è sintetizzare l’informazione contenuta nell’intera riga dell’osservazione. Dunque, costruisco un indicatore sintetico che mi porta da Rk a R, nuovo spazio di output (nell’esempio passo da k voti alla media aritmetica). Il mio obiettivo, quindi, è partire da Rka Rp: questo si fa grazie ad una funzione theta del vettore xi.k pθ :ℝ ℝ→k pθ∈ ∈→ℝ ℝx x( )i iLo scopo, dunque, è costruire la mappa theta: dobbiamo mappare per ogni punto in Rk, un punto in Rp, grazie a diverse tecniche. La mappa che costruiremo avrà delle caratteristiche interessanti. Ora dobbiamo chiederci se il risultato della SVD risolve questo problema. Apparentemente non sembra perché ogni riga di X è approssimata da una riga approssimata in X^: la dimensionalità sembra esattamente uguale e quindi non vediamo immediatamente la soluzione. Di fatto, minimizzare la norma di Frobenius significa andare a minimizzare la somma delle norme euclidee calcolate per i confronti tra righe delle due matrici:

  n ²∑ ∥ ∥∧ i=-x x m ni ii =1

  Devo scegliere delle righe di X^ tali che mi minimizzino la norma ma sotto il vincolo di ottenere una matrice di rango p: poniamo un vincolo globale, altrimenti potremmo andare ad utilizzare le stesse righe di X, mandando la norma a 0. Per vedere meglio l’utilità della SVD, prendiamo X scritta nella sua scomposizione. Questa formula contiene un sacco di informazioni che ci porteranno al risultato. Abbiamo detto che il prodotto matriciale può essere visto come combinazione lineare di linee o colonne. La prima riga di X non è altro che una combinazione lineare delle righe di Vt. Le righe di X sono esprimibili come combinazione lineare di Vt e quindi V è una base dello spazio vettoriale X. Fino ad ora non abbiamo approssimato. Se ora, invece, prendiamo fino alla p-esima riga, otteniamo: Prendo solo una parte di base V, vado a costruire uno spazio più piccolo che chiamo X^. L’informazione che contiene la SVD è duplice: V è la base su cui espando X^ ma indirettamente mi dice anche qual è lo spazio vettoriale. Nell’esempio della freccia, se è un vettore tridimensionale, io posso individuare la freccia con una sua approssimazione bidimensionale: so che è tridimensionale ma pongo l’ultima dimensione a 0, ma ce l’ho perché ho le altre due. Nel contesto della SVD, il mio vettore x^_i è rappresentato in Rk, ma posso rappresentarlo in Rp, perché ho solo p elementi della base su cui espanderlo -> conoscendo i p coefficienti e la base V posso approssimare ottimamente x^_i. I vettori di x e x^ sono lunghi k ma, fissando una base, il vettore approssimante diventa un vettore di p coordinate (dato dalla formula). L’obiettivo di questo ‘disegno’ è vedere che la mappa per passare da Rk a Rp è formata da due passaggi che si compongono. La SVD mi da come è fatta Fi (j). Per approssimare al meglio la matrice X in Rk, ti serve lo spazio vettoriale Vp, di cui ti do i vettori risultati dalla SVD: se cambia la base V, allora ho coordinate diverse che mi rappresentano lo stesso vettore approssimante ma su una base diversa. Cambiando la base quindi ho diverse coordinate ma arrivo sempre in Rp: posso passare dalle coordinate di base V alle altre, facendo i cambi di base. La SVD, dunque, mi dà una base automatica (V ma è una scelta di convenienza matematica) ma volendo posso sceglierla arbitraria grazie a diverse coordinate. Diciamo che, in generale, abbiamo diversi modi per rappresentare i dati ma non è detto che quello che scelgo sia il migliore. Ma perché scegliere la Fi in base alla SVD? Dimostreremo che questa scelta ci farà avere dei guadagni in altri ambiti. Ricordiamo che è grazie a Fi che facciamo il vero passaggio dimensionale. Una cosa che faremo è vedere come costruire le diverse Fi. Importante è osservare che la mappa non è invertibile: se io ho l’approssimato non posso andare a ricavare i dati originali perché non so quali informazioni ho perso. Quello che è invertibile è Psi (Y): dal vettore e dalla base ottengo i coefficienti ma anche dai coefficienti e dalla base posso ottenere il vettore (questo perché non perdo informazione).

  Altro problema: posso fare un clustering sulla matrice X^ se ha senso per il nostro problema lavorare su una matrice ridotta. Se io faccio cluster su X^ o A (UD) è equivalente? Sì, quando le distanze tra vettori in A sono equivalenti a quelle di X^. Questo succede solo se Psi è isometrica: questo succede quando la base è ortonormale; quindi, è per questo motivo che scegliamo la base V. → SVD per colonne: le colonne di X sono le colonne U con i pesi delle colonne Dt (V). Cosa succede se la X è centrata (colonne a media nulla)? Le colonne di V sono i vettori di sigma: arriviamo alle componenti principali -> UD. U diventa la matrice delle componenti principali normalizzate (norma 1).

Settimana 2

Lezione 3 – 6/12

Per comprendere questo argomento, dobbiamo tenere a mente il disegno della mappa theta, che prende un profilo k-dimensionale e lo mappa in un oggetto p-dimensionale. Questo passaggio avviene anche grazie alle funzioni Fi e Psi. Questo schema prende il nome di diagramma commutativo. Questa parte precede la SVD nelle dispense perché questa è uno dei modi per costruire questa mappa. Il tema diventerà capire cosa guadagniamo/perdiamo andando a scegliere o meno la SVD.

• Teorema delle proiezioni

  Ha una natura matematica ma un riflesso interessante dal punto di vista applicativo. La SVD mi dice che il sottospazio migliore è Vp, dandomi la base V che ricavo dalla scomposizione. Immaginiamo questa situazione: ho un vettore w di R³ e voglio la sua migliore approssimazione R², qual è? La proiezione ortogonale di w su R².

  3 W W∈ ⊃w∈ℝw 1 → esempio più generico che porta un WP=w2 vettore w da W a W₁ (contenuto in W).

  →ℝ ?w 1 w 1

  Fino ad ora abbiamo usato la SVD come metodo di approssimazione. Un’altra possibilità, però, sarebbe quello di fare delle proiezioni: proietto sullo spazio Vp ogni riga di x_i. Ovviamente fare le due cose è uguale. Vediamo, però, matematicamente perché è importante vedere anche questo aspetto. Lo scopo è quello di trasformare l’operatore P con una matrice. Dobbiamo scegliere una base, scegliamo V. Questo oggetto prende un oggetto in Rk e lo proietta su Rp. Lavorando per righe, dobbiamo applicare il proiettore a destra perché deve lavorare, appunto, sulle righe. Al posto di fare riga per riga, facciamo un’operazione matriciale. Abbiamo dimostrato che i due approcci funzionano. Ma perché? Questo era per dimostrare due cose: 1) quando si lavora con dati euclidei per approssimare andiamo a proiettare sul sottospazio che ci serve -> la SVD ci fornisce il sottospazio fondamentale (V); 2) tutto è collegato, vera natura delle cose che affrontiamo (regredire e proiettare sono la stessa cosa).

• Problema concreto

  L’SVD è valida fino a che non aggiungo nuove righe su X. Ma se io confronto due SVD fatte su due X diverse (in termini di righe), cosa succede alle SVD che ottengo? Ovviamente le matrici ottenute dalla SVD saranno diverse (input diverso, output diverso). Immaginiamo però di dover classificare in base alla SVD un totale di clienti. La classificazione è la stessa nelle due situazioni? L’interpretazione dipende da V. Dobbiamo scegliere se essere ottimali in senso stretto o in un senso più ampio: fare la SVD ogni giorno ci porta ad essere precisi nella classificazione ma poco con i nuovi clienti; facciamo la SVD dopo un anno di dati e proietto il vettore nuovo su un vecchio sottospazio. Per noi, la proiezione è un occhio elettronico che ci porta l’osservazione nuova nel sottospazio migliore che ho scelto sui vecchi dati. Ovviamente sappiamo che, proiettando i dati nuovi sul sottospazio vecchio, non facciamo più una cosa ottimale e commettiamo un errore. Dobbiamo, dunque, accorgerci quando l’errore che commettiamo è troppo (la situazione cambia) e cambiare interpretazione. Quindi, mi costruisco ogni volta dei sottospazi ottimali e vedo di quanto differiscono. Finché sono abbastanza simili posso continuare, se no devo cambiare sottospazio. Per fare ciò proietto i vari sottospazi uno sull’altro: se l’approssimazione è buona allora i sottospazi sono simili. Il cambiamento del sottospazio non dipende soltanto dall’orientamento ma anche dal bisogno di avere un sottospazio con un p maggiore. Quando p cresce, il dato è ‘poco correlato’ -> il dato/comportamento è molto più differenziato. Ricordiamo che la SVD ci piace perché possiamo applicare il teorema di Young che ci garantisce la minimizzazione totale: questo, infatti, non ci garantisce che ogni riga sia approssimata bene. Dobbiamo, dunque, verificare la bontà di approssimazione delle singole unità. Dal punto di vista teorico ciò è molto interessante perché significa che l’unità non è ben colta e quindi il fenomeno non è banale. Lo scopo sarà identificare una forma conveniente per decomporre le matrici.

Settimana 3

Lezione 4 – 13/12

Ricordiamo che l’oggetto fondamentale è la solita mappa con Fi e Psi. L’oggetto più importante è Fi (j) perché Psi dipende dalla base che scelgo, che nella SVD mi è data implicitamente (V). La SVD è uno dei modi per ottenere Fi. Abbiamo visto che fare la SVD equivale a fare delle proiezioni. Diciamo che la SVD è più facile da implementare; le proiezioni sono più eleganti come concetto. Ora cerchiamo delle alternative alla SVD. Quando applicarla? Che vantaggi ne traiamo? Quando costruire le mappe in modo diverso? Usiamo la SVD con la norma di Frobenius perché abbiamo il teorema di Young. Perché, dunque, cambiare metodo se lo strumento è già ottimo (come dice il teorema)? Perché a volte essere ottimali non serve.

• Non-negative Matrix Factorization (NMF)

  - Da cosa nasce l’esigenza della NMF Si parte da un aspetto tecnico delle SVD: molto spesso il dato di partenza è una tabella di numeri non negativi (tutte le entrate sono >= 0). Questo avviene molto spesso: pensiamo, ad esempio, ai dati demografici. Ciò comporta, rispetto alla SVD, nulla di nuovo dal punto di vista matematico. Ciò che cambia è che il primo autovettore (prima riga di Vt o prima colonna di U) è tutto ad entrate non negative, tutti gli altri no. Esiste un teorema di Perron-Frobenius che afferma: il primo autovettore (v1) è a tutte ad entrate non negative; gli altri, hanno una parte di componenti non negative e altre negative. Dal punto di vista matematico non comporta nulla alla SVD (nel senso che funziona). Perché, allora, questa cosa non ci piace? Perché crea problemi dal punto di vista interpretativo.