Large-Scale Bayesian Tensor Reconstruction: An Approximate Message Passing Solution

Sintesi Tecnica: Ricostruzione Tensoriale Bayesiana su Larga Scala tramite CP-GAMP

Definizione del Problema
La ricostruzione tensoriale, in particolare attraverso la decomposizione CANDECOMP/PARAFAC (CPD), è essenziale per l'analisi di dati su larga scala con strutture complesse in campi che spaziano dall'elaborazione dei segnali alle neuroscienze. Sebbene i framework bayesiani offrano una quantificazione del principio di incertezza e un apprendimento automatico degli iperparametri, i metodi esistenti affrontano significative sfide di scalabilità. Gli approcci tradizionali di Inferenza Variazionale (VI), pur essendo più veloci dei metodi di campionamento, richiedono inversioni di matrici ad alta dimensione ad ogni iterazione, rendendoli computazionalmente proibitivi per tensori di grandi dimensioni. Inoltre, le precedenti soluzioni di Approximate Message Passing (AMP) per problemi tensoriali o ignorano la sparsità coerente tra i fattori latenti (degradando le prestazioni) o non riescono a gestire osservazioni incomplete e l'apprendimento degli iperparametri (limitandone l'applicabilità nel mondo reale).

Metodologia
Gli autori propongono CP-GAMP (Tensor CPD Generalized Approximate Message Passing), un algoritmo bayesiano scalabile progettato per superare i colli di bottiglia computazionali dell'inversione di matrice, gestendo al contempo dati incompleti e iperparametri sconosciuti.

1. Fondamento Algoritmico: CP-GAMP è derivato dal Loopy Belief Propagation (LBP) su un grafo di fattori che rappresenta il modello tensoriale CPD. Per rendere trattabili gli integrali ad alta dimensione, gli autori utilizzano il Teorema del Limite Centrale (CLT) e approssimazioni della serie di Taylor sotto il limite del sistema ampio. Ciò trasforma l'algoritmo sum-product in un framework GAMP generalizzato, evitando esplicite inversioni di matrici.
2. Gestione di Dati Incompleti: L'algoritmo accoglie tensori incompleti (dove alcuni elementi sono mancanti) modellando il processo di osservazione con un tensore indicatore binario e rumore bianco gaussiano additivo (AWGN). La funzione di verosimiglianza è adattata per tenere conto delle voci osservate e non osservate.
3. Apprendimento Automatico degli Iperparametri:
   • Stima del CP-Rank: Per determinare automaticamente il rango del tensore, gli autori introducono un prior Bernoulli-Gaussian (BG). Questo prior, che induce la sparsità, permette all'algoritzione di eliminare le componenti non necessarie. Il parametro di Bernoulli ($\lambda_r$), che determina la necessità della $r$-esima componente del rango, viene aggiornato tramite una routine di Expectation-Maximization (EM).
   • Stima della Potenza del Rumore: Viene derivato anche un aggiornamento EM per apprendere la potenza del rumore ($v_w$) quando questa è sconosciuta, uno scenario comune nelle applicazioni reali.
4. Processo Iterativo: Il nucleo dell'algoritmo aggiorna iterativamente i messaggi tra i nodi di variabile (elementi delle matrici fattore) e i nodi di fattore (verosimiglianze e prior). Utilizza una funzione di denoising derivata dal prior BG per calcolare le medie e le varianze a posteriori, eseguendo efficacementmente l'inferenza congiunta dei fattori latenti e degli iperparametri.

Contributi Chiave
Il documento delinea quattro contributi primari:

1. Algoritmo CP-GAMP: Un nuovo algoritmo basato su GAMP capace di gestire funzioni di verosimiglianza componente per componente, specificamente per tensori incompleti con AWGN. È derivato utilizzando l'approssimazione gaussiana e le espansioni della serie di Taylor.
2. Apprendimento Automatico del Rango: L'integrazione di un prior BG con una routine EM consente la stima automatica del CP-rank senza conoscenza pregressa, affrontando un limite critico nei metodi AMP tensoriali esistenti.
3. Apprendimento della Potenza del Rumore: La derivazione di una regola di aggiornamento EM permette all'algoritmo di apprendere dinamicamente la potenza del rumore, migliorando la robustezza in scenari pratici.
4. Scalabilità ed Efficienza: Il metodo è validato per ridurre significativamente la complessità computazionale rispetto ai metodi basati su VI all'avanguardia, mantenendo l'accuratezza della ricostruzione.

Risultati Sperimentali
L'efficacia di CP-GAMP è stata validata attraverso esperimenti su dati sintetici e compiti di inpainting di immagini, confrontandolo con il metodo di Variational Bayesian CPD (FBCP) e il Tensor Completion AMP (TC-AMP).

• Dati Sintetici: In esperimenti coinvolgenti tensori di rango 20 con dimensioni $100 \times 100 \times 100$ e solo il 20% di elementi osservati, CP-GAMP ha ottenuto una riduzione del tempo di esecuzione dell'82,7% rispetto a FBCP. Ha mantenuto prestazioni di Normalized Mean Squared Error (NMSE) comparabili a FBCP e ha superato significativamente TC-AMP, che ha sofferto di un NMSE più elevato a causa della sua incapacità di tenere conto della sparsità coerente.
• Inpainting di Immagini: Su tensori di immagini $256 \times 256 \times 3$ con rapporti di osservazione del 30%, CP-GAMP ha ridotto il tempo di esecuzione del 56,3% rispetto a FBCP. Ha ottenuto il valore NMRE più basso tra i metodi confrontati, mentre TC-AMP era più veloce ma sacrificava la qualità della ricostruzione.
• Scalabilità: I risultati hanno dimostrato che, all'aumentare delle dimensioni del tensore e dei CP-rank, CP-GAMP manteneva un profilo di tempo di esecuzione inferiore rispetto a FBCP, confermando la sua scalabilità.

Significatività
Il documento afferma che CP-GAMP fornisce una soluzione scalabile per la ricostruzione tensoriale bayesiana su larga scala. Eliminando la necessità di inversioni di matrici ad alta dimensione e integrando l'apprendimento automatico degli iperparametri (rango e potenza del rumore), l'algoritmo colma il divario tra i benefici teorici dell'inferenza bayesiana e i requisiti pratici di elaborazione di dataset incompleti, rumorosi e di grandi dimensioni. Gli autori sottolineano che questo approccio rende la quantificazione del principio di incertezza e la selezione automatica del modello fattibili per applicazioni reali dove le risorse computazionali e la completezza dei dati sono vincolate.