Variational inference and density estimation with non-negative tensor of hierarchical tucker format

Sintesi Tecnica: Inferenza Variazionale e Stima della Densità con Tensore Non Negativo in Formato Hierarchical Tucker

Enunciato del Problema
Il documento affronta la sfida di comprimere distribuzioni di probabilità discrete ad alta dimensionalità, rappresentate come tensori $P: [n]^d \to \mathbb{R}_{\geq 0}$, in formati a basso rango trattabili. Memorizzare direttamente tale tensore richiede una complessità di $O(n^d)$, che diventa impraticabile anche per dimensioni moderate $d$ (ad esempio, decine di variabili). L'obiettivo è approssimare $P$ all'interno di una famiglia parametrica che permetta una memorizzazione, un campionamento e una valutazione della verosimiglianza efficienti. Il lavoro considera due modelli di accesso:

1. Inferenza Variazionale (VI): Accesso a $P$ tramite un oracolo che fornisce valori non normalizzati $P(i_1, \dots, i_d)$ fino a una costante.
2. Stima della Densità (DE): Accesso a $P$ tramite una collezione di campioni estratti dalla distribuzione.

I modelli di reti tensoriali esistenti, come il formato Tensor-Train (TT), sono efficaci per distribuzioni che soddisfano una "legge dell'area" (area law), ma faticano con modelli a reticolo 2D o strutture di interazione complesse dove la legge dell'area non è soddisfatta. Inoltre, le standard reti tensoriali non garantiscono intrinsecamente la non-negatività, il che è critico per le distribuzioni di probabilità per evitare "problemi di segno" in compiti successivi come il calcolo della divergenza di Kullback-Leibler o il campionamento.

Metodologia
Gli autori propongono un algoritmo end-to-end in due fasi per comprimere $P$ in un formato Non-Negative Hierarchical Tucker (NHT).

• Fase 1: Interpolazione Hierarchical Tucker (Costruzione del Riferimento)

  • Obiettivo: Costruire un'approssimazione Hierarchical Tucker (HT) con segno $\tilde{P} \approx P$.
  • Caso VI: Utilizza metodi di interpolazione esistenti basati sulla decomposizione interpolativa (decomposizione tipo CUR) per interrogare le voci di $P$ e ricostruire $\tilde{P}$.
  • Caso DE: Utilizza algoritmi di stima della densità esistenti per costruire $\tilde{P}$ dai campioni.
  • Output: Un tensore di riferimento $\tilde{P}$ con componenti con segno. Questa fase non impone la non-negatività.

• Fase 2: Fitting del Non-Negative Hierarchical Tucker

  • Obiettivo: Adattare un ansatz non negativo $P_G$ (parametrizzato da fattori tensoriali non negativi $G = \{G_q\}$) al riferimento con segno $\tilde{P}$.
  • Ottimizzazione: Il problema è formulato come la minimizzazione di una funzione di perdita $\ell(G)$ composta dalla norma di Frobenius al quadrato tra $P_G$ e $\tilde{P}$, più una penalità log-barrier per imporre la non-negatività:
    $$\ell(G) = \|P_G - \tilde{P}\|_F^2 + \sum_q \mu_q \phi_q(G_q)$$
    dove $\phi_q$ è una log-barrier sulle voci di $G_q$.
  • Algoritmo: Viene impiegato un approccio di minimizzazione alternata. Per ogni componente tensoriale $G_q$, l'algoritmo aggiorna la variabile utilizzando un passo di Newton del secondo ordine.
    • Gradiente/Essenza: Calcolati tramite passaggio di messaggi (message passing) sulla struttura dell'albero binario, utilizzando prodotti di Kronecker di matrici di Gram.
    • Efficienza: Per evitare il costo $O(\rho^9)$ dell'inversione di matrici Hessiane dense, il metodo utilizza il Gradiente Coniugato (CG) per i nodi intermedi e risoluzioni disaccoppiate per i nodi foglia.
  • Inizializzazione Warm (Warm Initialization): Un componente critico è la strategia di "gauge warm initialization" (Algoritmo 2.3). Invece di un naive thresholding del riferimento con segno, questo metodo sfrutta la libertà di gauge delle reti tensoriali. Esegue un passaggio disaccoppiato (dalle foglie alla radice) per trovare matrici di gauge ortogonali $Q$ e componenti positive $G_q$ che meglio si adattano alle componenti del riferimento $F_q$ in modalità "leave-one-out". Ciò migliora significativamente la convergenza ed evita minimi locali.

Contributi Chiave

1. Formato NHT per Distribuzioni ad Alta Dimensionalità: Il documento introduce l'uso del formato Non-Negative Hierarchical Tucker, che è più adatto per modelli a reticolo 2D e strutture di interazione complesse rispetto al formato Tensor-Train (TT), mantenendo al contempo la non-negatività richiesta dalle distribuzioni di probabilità.
2. Procedura di Fitting del Secondo Ordine: Gli autori progettano un metodo di ottimizzazione del secondo ordine su misura per la fase di fitting NHT. Questo include una nuova strategia di warm initialization che affronta la difficoltà di raggiungere minimi locali in contesti ad alta dimensionalità, migliorando spesso l'accuratezza finale di un ordine di grandezza rispetto all'inizializzazione standard.
3. Complessità Computazionale: Entrambe le fasi della metodologia proposta ammettono una complessità computazionale $O(d)$, rendendo l'approccio scalabile verso contesti ad alta dimensionalità.
4. Algoritmo End-to-End: Il lavoro fornisce una pipeline completa sia per i casi di Inferenza Variazionale che di Stima della Densità, colmando il divario tra la costruzione di un riferimento con segno e l'adattamento di un modello non negativo fisicamente valido.

Risultati Sperimentali
Esperimenti numerici sono stati condotti su entrambi i modelli di accesso:

• Inferenza Variazionale: Testato su un modello di Ginzburg-Landau 2D ($d=32$) e un modello a coda pesante (heavy-tailed) ($d=30$). L'iterazione di Newton precondizionata con barriera adattiva ha superato significativamente il benchmark di aggiornamento moltiplicativo, ottenendo una perdita di Frobenius al quadrato relativa inferiore nello stesso tempo di esecuzione (wall-clock time).
• Stima della Densità: Testato su un modello di Ising 2D ($d=32$) e un modello di Ising con campo trasverso 2D ($d=64$). Il metodo ha approssimato con successo la distribuzione reale, con valori di Log-Verosimiglianza Negativa (NLL) vicini ai valori esatti.
• Studi di Ablazione:
  • NHT vs. NTT: Nel modello Ginzburg-Landau 2D, l'ansatz NHT ha ottenuto una migliore accuratezza di fitting rispetto all'ansatz Non-negative Tensor-Train (NTT), anche quando al modello NTT sono stati dati il doppio dei parametri.
  • Inizializzazione: La proposta gauge warm initialization (Algoritmo 2.3) ha costantemente prodotto risultati di fitting migliori rispetto all'inizializzazione con un algoritmo di aggiornamento moltiplicativo (Algoritmo 3.1).

Significatività e Rivendicazioni
Il documento sostiene che la metodologia NHT proposta offre una soluzione robusta per comprimere distribuzioni discrete ad alta dimensionalità dove i modelli tradizionali di tensor-train falliscono a causa di vincoli strutturali (ad esempio, reticoli 2D). Garantendo la non-negatività attraverso l'ansatz e utilizzando una sofisticata procedura di fitting del secondo ordine con un particolare warm start, il metodo consente una stima della densità e un'inferenza variazionale accurate senza i problemi di segno associati alle reti tensoriali non vincolate. Gli autori osservano che, sebbene il metodo sia illustrato su alberi binari completi, il codice supporta alberi incompleti, e il lavoro futuro potrebbe estendere questo a ansatz tensoriali gerarchici funzionali o incorporare vincoli di conservazione dei momenti.