Decomposizione in valori singolari
Ciao,
Una domandina sulla decomposizione in valori singolari, oggi il prof di algebra ci ha spiegato una delle applicazioni della decomposizione in valori singolari.
Se abbiamo un immagine di \( m \times n \) pixel e ogni pixel può assumere un valore che può variare tra 0 e 100 allora il numero di pixel da memorizzare è \( nm \) che può essere un numero grande. Invece decomponendo la matrice in valori singolari \( \sigma_1 \geq \ldots \geq \sigma_k >0\) possiamo scrivere la matrice "pixel" \( A=PDQ \) e considerare solamente i primi \( \ell \) valori signolari e buttare via gli altri e avere una compressione dell'immagine di buona qualità e sta volta bisogna memorizzare solamente \( 2\ell n + \ell \) pixel.
Per rendere l'idea del vantaggio ipotizziamo \( n=m=1000 \) e \( \ell = 20 \) che generamente è sufficiente,
invece di memorizzare \( n^2=1000000 \) di pixel il computer deve memorizzare solamente \( 40020 \) pixel che è una grossa differenza.
Alla domanda cosa giustifica il fatto che possiamo prendere solo i primi \( \ell \) valori singolari invece che \( k \) valori singolari ha risposto: "funziona per esperienza, gli ingenieri a volte dimostrano le cose altre volte no."
Nonostante la risposta simpatica, io non capisco proprio il motivo per cui possiamo considerarne solo alcuni, e coma si fa ad avere ancora una buona qualità dell'immagine.
Una domandina sulla decomposizione in valori singolari, oggi il prof di algebra ci ha spiegato una delle applicazioni della decomposizione in valori singolari.
Se abbiamo un immagine di \( m \times n \) pixel e ogni pixel può assumere un valore che può variare tra 0 e 100 allora il numero di pixel da memorizzare è \( nm \) che può essere un numero grande. Invece decomponendo la matrice in valori singolari \( \sigma_1 \geq \ldots \geq \sigma_k >0\) possiamo scrivere la matrice "pixel" \( A=PDQ \) e considerare solamente i primi \( \ell \) valori signolari e buttare via gli altri e avere una compressione dell'immagine di buona qualità e sta volta bisogna memorizzare solamente \( 2\ell n + \ell \) pixel.
Per rendere l'idea del vantaggio ipotizziamo \( n=m=1000 \) e \( \ell = 20 \) che generamente è sufficiente,
invece di memorizzare \( n^2=1000000 \) di pixel il computer deve memorizzare solamente \( 40020 \) pixel che è una grossa differenza.
Alla domanda cosa giustifica il fatto che possiamo prendere solo i primi \( \ell \) valori singolari invece che \( k \) valori singolari ha risposto: "funziona per esperienza, gli ingenieri a volte dimostrano le cose altre volte no."
Nonostante la risposta simpatica, io non capisco proprio il motivo per cui possiamo considerarne solo alcuni, e coma si fa ad avere ancora una buona qualità dell'immagine.
Risposte
@arnett: bella risposta, spiega che bisogna conservare i valori singolari più bassi e buttare quelli alti. Ma resta comunque una arbitrarietà nella scelta di \(20\).
Qualcuno una volta mi ha spiegato che in queste cose ci sono degli standard internazionali. Non conosco questa compressione ai valori singolari, parlo della compressione JPG, che (a quanto ne so) è grosso modo la stessa cosa, usando una trasformata discreta di Fourier. Per il JPG c'è stato un comitato di esperti che, nell'anno '97 (credo), ha stabilito quanti modi si dovessero conservare e quanti buttare. La cosa poi è stata raffinata ed è nato il JPG2.
È così che nascono le estensioni di file, ognuna si riferisce ad un diverso standard.
Qualcuno una volta mi ha spiegato che in queste cose ci sono degli standard internazionali. Non conosco questa compressione ai valori singolari, parlo della compressione JPG, che (a quanto ne so) è grosso modo la stessa cosa, usando una trasformata discreta di Fourier. Per il JPG c'è stato un comitato di esperti che, nell'anno '97 (credo), ha stabilito quanti modi si dovessero conservare e quanti buttare. La cosa poi è stata raffinata ed è nato il JPG2.
È così che nascono le estensioni di file, ognuna si riferisce ad un diverso standard.
La SVD è un contributo degli statistici: anzi in statistica corrisponde alla tecnica chiamata analisi delle componenti principali ed è strettamente legata all'analisi discriminante.
Gli impieghi sono infiniti, è semplicemente la decomposizione più utlizzata al mondo dato che persino in questo istante Google e compagnia bella stanno prendendo ogni nostro dato rilasciato e ogni nostra azione online, poi lo infilano in un vettore e in base ad una SVD ci associano a gruppi ben definiti a cui inviare esattamente certe pubblicità e nella modalità più efficace
Riguardo quali valori scartare, si ordina prima la matrice degli autovalori della sigma (che sono al quadrato) dal più grande al più piccolo. Quelli pressochè nulli, vengono arbitrariamente scartati perchè hanno un impatto irrisorio Tecnicamente sono varianze associate ai nuovi assi/componenti, combinazioni di quelli originali, per cui venogno rimossi gli assi/componenti giudicate irrilevanti per spiegare la varianza/covarianza totale delle variabili in gioco.
In pratica, l'idea è di partire con una serie caratteri (tipo peso, altezza, etc etc) da questi creare nuovi caratteri (mix dei precedenti) e tenere solo quelli che spiegano in massima parte la variabilità totale.
Se segui la stessa logica anche nella decomposizione di un'immagine, comprendi cosa sta accadendo e perchè sia possibile ridefinirla e successivamente comprimerla con perdite marginali.
Va detto però che non è la sola decomposizione che può essere usata per la compressione (in generale) e nemmeno quella effettivamente utlizzata (perchè costa troppo in termini di calcolo): in realtà per lo standard odierno usano un'altra base per decomporre il tutto (se trovo il video di Strang in cui ne parla lo posto).
Infine, eoni fa trovai un .pdf meraviglioso (italiano!) in cui il prof faceva vedere l'immagine originale, e poi compressa per vari livelli di "scarti". Magari provo a cercarlo ma non assicuro nulla.
Gli impieghi sono infiniti, è semplicemente la decomposizione più utlizzata al mondo dato che persino in questo istante Google e compagnia bella stanno prendendo ogni nostro dato rilasciato e ogni nostra azione online, poi lo infilano in un vettore e in base ad una SVD ci associano a gruppi ben definiti a cui inviare esattamente certe pubblicità e nella modalità più efficace
Riguardo quali valori scartare, si ordina prima la matrice degli autovalori della sigma (che sono al quadrato) dal più grande al più piccolo. Quelli pressochè nulli, vengono arbitrariamente scartati perchè hanno un impatto irrisorio Tecnicamente sono varianze associate ai nuovi assi/componenti, combinazioni di quelli originali, per cui venogno rimossi gli assi/componenti giudicate irrilevanti per spiegare la varianza/covarianza totale delle variabili in gioco.
In pratica, l'idea è di partire con una serie caratteri (tipo peso, altezza, etc etc) da questi creare nuovi caratteri (mix dei precedenti) e tenere solo quelli che spiegano in massima parte la variabilità totale.
Se segui la stessa logica anche nella decomposizione di un'immagine, comprendi cosa sta accadendo e perchè sia possibile ridefinirla e successivamente comprimerla con perdite marginali.
Va detto però che non è la sola decomposizione che può essere usata per la compressione (in generale) e nemmeno quella effettivamente utlizzata (perchè costa troppo in termini di calcolo): in realtà per lo standard odierno usano un'altra base per decomporre il tutto (se trovo il video di Strang in cui ne parla lo posto).
Infine, eoni fa trovai un .pdf meraviglioso (italiano!) in cui il prof faceva vedere l'immagine originale, e poi compressa per vari livelli di "scarti". Magari provo a cercarlo ma non assicuro nulla.
Trovata...è una delle ultime lezioni dedicata in buona parte alla compressione.
https://youtu.be/vGkn-3NFGck
https://youtu.be/vGkn-3NFGck
Molto interessante, grazie Bokonon. (Mi piacerebbe davvero capire che ci azzecca la decomposizione ai valori singolari con Google, me lo chiedo da parecchio).
Ok, visto l'interesse e il pubblico superscafato, provo a dare un'idea generale di come vengano impiegate le tecniche di analisi fattoriale saltando dettagli per voi ovvi.
Il sogno perverso di ogni buon statistico è trovare un piccolo insieme di caratteri/variabili totalmente indipendenti che spieghino interamente la variabilità di un fenomeno. Ma il mondo non è ideale e per quanto ci si sforzi di individuare le variabili migliori e meno ridondanti possibili, ci sarà sempre un legame (covarianza) fra di esse.
Quindi il nostro piccolo statistico prepara una rilevazione per n persone in cui rileva m caratteri/variabili papabili e si ritrova con una matrice M nxm con n>>m. Sicuramente le colonne sono indipendenti (a meno di un evento pressochè impossibile) ma non saranno ortogonali (a meno di un evento ancora più improbabile) e a questo punto si chiederà "che me ne faccio?".
Immaginiamo un esempio concreto che ci seguirà nel discorso. La rilevazione riguarda i gusti delle gente nel cinema e le variabili sono le più disparate horror, shi-fi, polpettoni amorosi, qualità, regia, età della pellicola, età e sesso della persona e quant'altro...tutte quantificabili però.
Un'idea potrebbe essere innnazitutto di prendere le colonne calcolare la media e sottrala dai valori. Poi il piccolo statistico nota che se fa $MM^T$ ottiene una matrice simmetrica (con tutte le sue belle proprietà) e che è una matrice di devianza e codevianza dato che il prodotto scalare la crea "naturalmente" per lui. A questo punto si chiede come potrebbe scomporla e dissezionarla e scopre che trovando gli autovalori e autovettori di $MM^T$ e $M^TM$ può riscrivere la sua matrice nxm rispetto ad una decomposizione SVD. Non solo i nuovi assi delle due basi sono un mix dei vecchi caratteri ma sono ortogonali quindi li può vedere come "nuove" variabili perfettamente indipendenti fra di loro, ma i valori normalizzati sono "pesi" che gli dicono quanto un vecchio carattere ha contributo a creare il nuovo.
Quindi nell'esempio scopre un asse che predilige prevalentemente i mix di film d'amore, tragedie e commedie e ribattezza la nuova variabile con l'etichetta "romantico". Un'altra sarà "azione", una terza "film d'autore" e così via.
Ad ogni nuova componente è associata la sua variabilità l'autovalore al quadrato) la cui somma totale è la variabilità totale iniziale. Perciò alcune componenti si rivelaranno quasi irrilevanti e il nostro piccolo statistico le scarterà, forte del fatto che le nuove variabili spiegheranno la quasi totalità della variaiblità del fenomeno...in modo più ridotto e compatto, efficace ed esattamente come le vorrebbe nella suo mondo utopico, ortogonali. In base ai pesi può anche tornare alle singole persone rilevate e tracciarle e formeranno piccole nubi di punti, spesso significativamente separate.
Magari tramite l'analisi discriminante crea anche un algoritmo che associ le persone rilevate a quei gruppi...ma anche le persone "future". Ovvero in base alle info che una nuova persona rilevata fornisce, può essere associata univocamente ad uno di quei gruppi. E quindi scrive un algoritmo per inviare suggerimenti personalizzati per i film (come su netflix) oppure pubblicità mirate.
Non sono stato affatto preciso ma spero di aver reso l'idea. Google e FB (solo per citare due colossi) macinano matrici immense continuamente per l'adversiting. Per questo persone come Strang si sono occupati e si occupano di trovare sempre nuovi modi per rispamiare memoria e tempi di calcolo per determinare (fra le altre cose) gli autovalori.
Un esempio recente di utilizzo "malefico" dell'analisi fattoirale sono le recenti elezioni americane: non solo i russi hanno bombardato specifici target usando le piattaforme social ma anche gli americani stessi, come Bannon. Il pentito https://www.youtube.com/watch?v=FXdYSQ6nu-M di Cambridge Analytica https://en.wikipedia.org/wiki/Cambridge_Analytica ha spiegato molto bene nelle sue interviste come usando un'app del cacchio hanno raccolto su FB 87 milioni di profili di utenti americani e poi li abbiano usati (tramite analisi fattoriali) per impostare una campagna di voter targeting. Ad ognuno il suo messaggio personalizzato: se era già associato al gruppo di "fedeli" allora dovevano spingerlo a fare propaganda inviando fake news che avrebbe volontariamente ritrasmesso, se invece era "nemico" dovevano inserire il dubbio e così via.
Non illudiamoci, oramai è una cosa consolidata e spesso organizzata dai governi stessi...anche il piccolo statistico può essere parte dell'asse del male.
Il sogno perverso di ogni buon statistico è trovare un piccolo insieme di caratteri/variabili totalmente indipendenti che spieghino interamente la variabilità di un fenomeno. Ma il mondo non è ideale e per quanto ci si sforzi di individuare le variabili migliori e meno ridondanti possibili, ci sarà sempre un legame (covarianza) fra di esse.
Quindi il nostro piccolo statistico prepara una rilevazione per n persone in cui rileva m caratteri/variabili papabili e si ritrova con una matrice M nxm con n>>m. Sicuramente le colonne sono indipendenti (a meno di un evento pressochè impossibile) ma non saranno ortogonali (a meno di un evento ancora più improbabile) e a questo punto si chiederà "che me ne faccio?".
Immaginiamo un esempio concreto che ci seguirà nel discorso. La rilevazione riguarda i gusti delle gente nel cinema e le variabili sono le più disparate horror, shi-fi, polpettoni amorosi, qualità, regia, età della pellicola, età e sesso della persona e quant'altro...tutte quantificabili però.
Un'idea potrebbe essere innnazitutto di prendere le colonne calcolare la media e sottrala dai valori. Poi il piccolo statistico nota che se fa $MM^T$ ottiene una matrice simmetrica (con tutte le sue belle proprietà) e che è una matrice di devianza e codevianza dato che il prodotto scalare la crea "naturalmente" per lui. A questo punto si chiede come potrebbe scomporla e dissezionarla e scopre che trovando gli autovalori e autovettori di $MM^T$ e $M^TM$ può riscrivere la sua matrice nxm rispetto ad una decomposizione SVD. Non solo i nuovi assi delle due basi sono un mix dei vecchi caratteri ma sono ortogonali quindi li può vedere come "nuove" variabili perfettamente indipendenti fra di loro, ma i valori normalizzati sono "pesi" che gli dicono quanto un vecchio carattere ha contributo a creare il nuovo.
Quindi nell'esempio scopre un asse che predilige prevalentemente i mix di film d'amore, tragedie e commedie e ribattezza la nuova variabile con l'etichetta "romantico". Un'altra sarà "azione", una terza "film d'autore" e così via.
Ad ogni nuova componente è associata la sua variabilità l'autovalore al quadrato) la cui somma totale è la variabilità totale iniziale. Perciò alcune componenti si rivelaranno quasi irrilevanti e il nostro piccolo statistico le scarterà, forte del fatto che le nuove variabili spiegheranno la quasi totalità della variaiblità del fenomeno...in modo più ridotto e compatto, efficace ed esattamente come le vorrebbe nella suo mondo utopico, ortogonali. In base ai pesi può anche tornare alle singole persone rilevate e tracciarle e formeranno piccole nubi di punti, spesso significativamente separate.
Magari tramite l'analisi discriminante crea anche un algoritmo che associ le persone rilevate a quei gruppi...ma anche le persone "future". Ovvero in base alle info che una nuova persona rilevata fornisce, può essere associata univocamente ad uno di quei gruppi. E quindi scrive un algoritmo per inviare suggerimenti personalizzati per i film (come su netflix) oppure pubblicità mirate.
Non sono stato affatto preciso ma spero di aver reso l'idea. Google e FB (solo per citare due colossi) macinano matrici immense continuamente per l'adversiting. Per questo persone come Strang si sono occupati e si occupano di trovare sempre nuovi modi per rispamiare memoria e tempi di calcolo per determinare (fra le altre cose) gli autovalori.
Un esempio recente di utilizzo "malefico" dell'analisi fattoirale sono le recenti elezioni americane: non solo i russi hanno bombardato specifici target usando le piattaforme social ma anche gli americani stessi, come Bannon. Il pentito https://www.youtube.com/watch?v=FXdYSQ6nu-M di Cambridge Analytica https://en.wikipedia.org/wiki/Cambridge_Analytica ha spiegato molto bene nelle sue interviste come usando un'app del cacchio hanno raccolto su FB 87 milioni di profili di utenti americani e poi li abbiano usati (tramite analisi fattoriali) per impostare una campagna di voter targeting. Ad ognuno il suo messaggio personalizzato: se era già associato al gruppo di "fedeli" allora dovevano spingerlo a fare propaganda inviando fake news che avrebbe volontariamente ritrasmesso, se invece era "nemico" dovevano inserire il dubbio e così via.
Non illudiamoci, oramai è una cosa consolidata e spesso organizzata dai governi stessi...anche il piccolo statistico può essere parte dell'asse del male.
Che bello, grazie mille, nel mondo di oggi queste cose sono importanti da sapere, almeno a grandi linee.
"dissonance":
[...] (Mi piacerebbe davvero capire che ci azzecca la decomposizione ai valori singolari con Google, me lo chiedo da parecchio).
Relevant
@080e73990d22b9e30ee6fddddc45a902d78283e6 Quello è il motore di ricerca
"Bokonon":
@080e73990d22b9e30ee6fddddc45a902d78283e6 Quello è il motore di ricerca
Lo so, ma è comunque una risposta valida ad uno che chiede cosa ci azzecchino i valori singolari(/autovalori) con Google.
"Bokonon":
@080e73990d22b9e30ee6fddddc45a902d78283e6 Quello è il motore di ricerca
Purtroppo non ho ancora trovato il tempo di leggerlo, ma mi sembra che, in fondo, gli algoritmi del motore di ricerca e quelli dell'advertising sono gli stessi, o mi sbaglio?
Nell'articolo non si parla di analisi fattoriale.
Per come l'ho tradotto, in parole povere, costruiscono una matrice degli hyperlink per legare n pagine web che, si presume, abbiano un contenuto simile in base alle parole chiave. Poi usano i pesi creati per costruire una matrice a somma 1 da interpretare come probabilità di passare da uno stato i allo stato j. In pratica è una matrice di cambiamento di stato che rappresenta una catena di Markov, quindi ha sempre un autovalore massimo e pari ad 1...ed è quello più interessante.
Spiego brevemente il perchè. Se si vuole analizzare cosa accade al crescere dei cambiamenti di stato, si analizza in sostanza l'applicazione reiterata della matrice P. Quindi diventa $P^2$ e poi $P^3$ e $P^n$.
Come è noto con la diagonalizzazione $P=SDS^-1$ e $P^n=SD^nS^-1$ quindi non solo è utile diagonalizzare per calcolare rapidamente tutte le potenze di P, ma conoscendo la matrice diagonale si può anche analizzare il caso in cui $n->oo$ e in questo caso l'unico vettore davvero rilevante per la convergenza è quello associato all'autovalore 1 (perchè tutti gli altri autovalori sono compresi fra 0 e 1 e tenderanno a zero).
Ringrazio @obnoxiuos per il link, sottolineavo solo che non aveva niente a che vedere con l'analisi fattoriale.
Per come l'ho tradotto, in parole povere, costruiscono una matrice degli hyperlink per legare n pagine web che, si presume, abbiano un contenuto simile in base alle parole chiave. Poi usano i pesi creati per costruire una matrice a somma 1 da interpretare come probabilità di passare da uno stato i allo stato j. In pratica è una matrice di cambiamento di stato che rappresenta una catena di Markov, quindi ha sempre un autovalore massimo e pari ad 1...ed è quello più interessante.
Spiego brevemente il perchè. Se si vuole analizzare cosa accade al crescere dei cambiamenti di stato, si analizza in sostanza l'applicazione reiterata della matrice P. Quindi diventa $P^2$ e poi $P^3$ e $P^n$.
Come è noto con la diagonalizzazione $P=SDS^-1$ e $P^n=SD^nS^-1$ quindi non solo è utile diagonalizzare per calcolare rapidamente tutte le potenze di P, ma conoscendo la matrice diagonale si può anche analizzare il caso in cui $n->oo$ e in questo caso l'unico vettore davvero rilevante per la convergenza è quello associato all'autovalore 1 (perchè tutti gli altri autovalori sono compresi fra 0 e 1 e tenderanno a zero).
Ringrazio @obnoxiuos per il link, sottolineavo solo che non aveva niente a che vedere con l'analisi fattoriale.
Wow, grazie bokonon per le risposte esaustive.
@Bokonon: 
Grazie a tutti, mi fa piacere che abbiate trovato interessante l'argomento.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo