Completamento di matrici
- Introdotto da
- Emmanuel Candès & Benjamin Recht
- Anno
- 2009
- Tipo
- Convex low-rank recovery
- Famiglia
- Missing data
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
Il completamento di matrici è una tecnica per recuperare una matrice a basso rango da un sottoinsieme piccolo, possibilmente casuale, delle sue entrate.
Introdotto da Emmanuel Candès e Benjamin Recht nel 2009, riformula il problema come minimizzazione della norma nucleare — un surrogato convesso per la minimizzazione del rango — e fornisce garanzie teoriche che il recupero esatto è realizzabile quando le entrate sono osservate uniformemente a caso e la matrice soddisfa una condizione di incoerenza.
L’intuizione alla base del metodo
Immaginate un foglio di calcolo parzialmente riempito di valutazioni utente-film dove la maggior parte delle celle sono vuote. Se i dati sottostanti hanno una struttura semplice — diciamo, il gusto è spiegato solo da pochi fattori latenti come preferenza di genere ed epoca — allora conoscere anche una piccola frazione delle valutazioni è sufficiente per riempire il resto con fiducia. Il completamento di matrici sfrutta questa struttura nascosta a bassa dimensionalità, molto simile al completamento di un puzzle quando si sa che l'immagine ha solo poche forme distinte.
Storia
Il completamento di matrici è emerso dalla letteratura del compressed sensing. Candès e Recht (2009) hanno stabilito il primo teorema di recupero esatto tramite minimizzazione della norma nucleare, seguito da vicino dal lavoro di Candès e Tao sul potere dell'incoerenza. Il metodo ha guadagnato ampia attenzione pubblica attraverso la competizione Netflix Prize, dove i metodi di collaborative filtering a basso rango hanno raggiunto accuratezza di raccomandazione allo stato dell'arte. Lavori successivi di Recht, Fazel e Parrilo hanno collegato la minimizzazione della norma nucleare alla regolarizzazione della norma traccia nell'apprendimento automatico.
Quando usarlo
Utilizzare il completamento di matrici quando i dati possono essere organizzati come una matrice con entrate sistematicamente mancanti e c'è motivo di credere che il segnale vero abbia basso rango — per esempio, nei sistemi di raccomandazione, genomica, analisi di reti sociali e recupero di immagini. Le ipotesi chiave sono che le entrate mancano a caso e la matrice soddisfa una condizione di incoerenza. Non è appropriato per matrici con mancanza strutturata o non casuale, struttura di rango molto elevato, o quando l'ipotesi di basso rango è ingiustificata. Le alternative includono l'imputazione MICE per dati mancanti generali e NMF quando è richiesta la non negatività.
Limiti e considerazioni
- Il costo computazionale della programmazione semidefinita scala male con le dimensioni della matrice
- L'ipotesi di incoerenza può fallire in dataset reali con mancanza strutturata o outlier
- Le prestazioni degradano quando il rango vero non è molto inferiore alle dimensioni della matrice
- La minimizzazione della norma nucleare può essere sensibile al rumore; varianti robuste aggiungono complessità aggiuntiva
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Recupero esatto dimostrabile in condizioni blande con un programma convesso in tempo polinomiale
- Gestisce tassi di mancanza molto elevati quando la matrice è veramente a basso rango
- Non è richiesta alcuna conoscenza preliminare del rango; la minimizzazione della norma nucleare lo trova implicitamente
- Forti garanzie teoriche radicate nella teoria delle matrici casuali e nell'analisi convessa
Applicazioni
- Collaborative filtering e sistemi di raccomandazione (previsione delle valutazioni utente-elemento)
- Genomica e bioinformatica (recupero di matrici di espressione genica con misurazioni mancanti)
- Visione artificiale (inpainting di immagini e sottrazione di sfondo video)
- Localizzazione di reti di sensori (recupero di matrici di posizione da misurazioni di distanza parziali)
- Neuroscienze (completamento di matrici di connettività funzionale da osservazioni fMRI parziali)
Come funziona
Come funziona
L'algoritmo inizia con una matrice M le cui entrate sono osservate solo su un insieme di indici Omega. Questi valori osservati formano i vincoli per il problema di recupero. Si assume che il pattern di sparsità sia campionato uniformemente a caso, che è l'impostazione teorica in cui vengono stabilite le garanzie di recupero esatto.
Formula
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}Poiché minimizzare direttamente il rango di una matrice è NP-difficile, Candès e Recht propongono di minimizzare la norma nucleare — la somma dei valori singolari — come rilassamento convesso. La norma nucleare svolge lo stesso ruolo per le matrici che la norma L1 svolge per i vettori nel compressed sensing: promuove soluzioni a basso rango mantenendo il problema trattabile tramite programmazione semidefinita.
Formula
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\OmegaAffinché il recupero sia possibile, i vettori singolari della vera matrice non devono essere troppo allineati con la base standard, quantificato dal parametro di incoerenza mu. Le matrici che concentrano la loro energia in poche righe o colonne sono incoerenti; le matrici altamente localizzate violano questa condizione e non possono essere recuperate da un campione casuale, poiché troppe informazioni sono codificate nelle entrate non osservate.
Formula
\max_{i} \|U^\top e_i\|^2 \leq \frac{\mu r}{n_1},\quad \max_{j} \|V^\top e_j\|^2 \leq \frac{\mu r}{n_2}Quando il numero di entrate osservate supera una soglia proporzionale a mu volte il rango r volte n log n, il minimizzatore del problema della norma nucleare recupera la vera matrice esattamente con alta probabilità. Questo risultato mostra che la dimensione del campione richiesta è solo logaritmicamente più grande dei gradi di libertà intrinseci di una matrice di rango r, rendendo l'approccio teoricamente informativo quasi ottimale.
Formula
\text{If } |\Omega| \geq C \cdot \mu r n \log n,\; \text{then } \hat{X} = M \text{ with high probability}Errori comuni
- Assumere una mancanza casuale uniforme quando le osservazioni reali sono selezionate dall'utente o distorte (ad esempio, vengono valutati solo gli elementi altamente valutati), il che viola il modello di campionamento teorico
- Trascurare di verificare la condizione di incoerenza, portando a un recupero scadente anche con osservazioni sufficienti
- Utilizzare la minimizzazione della norma nucleare senza scaling o regolarizzazione in contesti rumorosi, dove la formulazione di recupero esatto è inappropriata
- Confondere il completamento di matrici con euristiche di fattorizzazione di matrici: i minimi quadrati alternati possono convergere a minimi locali e mancano delle garanzie di recupero della minimizzazione della norma nucleare
Domande frequenti
La minimizzazione della norma nucleare è l'unico modo per risolvere il completamento di matrici?
No. I minimi quadrati alternati (ALS) e la discesa del gradiente su forme fattorizzate (ad esempio, SGD su U e V tali che M ≈ UV^T) sono ampiamente utilizzati nella pratica per la scalabilità. Tuttavia, questi approcci non convessi mancano delle garanzie di recupero esatto della minimizzazione della norma nucleare e possono convergere a minimi locali senza un'inizializzazione attenta.
Quanti dati sono necessari per il recupero esatto?
Candès e Recht hanno dimostrato che circa C·mu·r·n·log(n) entrate osservate sono sufficienti per una matrice n×n di rango r con parametro di incoerenza mu. In pratica, ciò significa che una matrice a basso rango può spesso essere recuperata da un campione che è solo un piccolo multiplo dei suoi gradi di libertà intrinseci, che equivalgono a r(2n−r) per una matrice n×n.
Cos'è la condizione di incoerenza e perché è importante?
L'incoerenza misura quanto sono distribuiti i vettori singolari rispetto alla base delle coordinate. Una matrice con vettori singolari concentrati — come una matrice di rango 1 che è non nulla solo in una riga — immagazzina la maggior parte delle sue informazioni in un piccolo insieme di entrate. Se tali entrate non sono osservate, il recupero è impossibile indipendentemente da quante altre entrate sono note.
Metodi correlati
Fonti
Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.
Apri il riferimento DOICopiato.