Density-Matrix Spectral Embeddings for Categorical Data: Operator Structure and Stability

1. Il Problema

Il lavoro affronta la sfida della riduzione della dimensionalità e della classificazione per dati categorici ad alta dimensionalità (o dati misti discretizzati). In molti scenari reali (sondaggi, log di eventi, registri transazionali), le variabili qualitative vengono codificate tramite one-hot encoding. Questo approccio genera vettori sparsi in uno spazio ambientale di dimensione $d$ molto elevato (dove $d$ è la somma delle modalità di tutte le variabili), spesso molto maggiore del numero di classi $k$ ($d \gg k$).

Le problematiche principali includono:

• La sparsità estrema dei dati, che rende difficile l'estrazione di strutture geometriche significative.
• La necessità di metodi supervisionati che sfruttino le etichette delle classi per guidare l'embedding.
• La stabilità delle rappresentazioni latenti in presenza di rumore, sparsità e squilibrio delle classi.
• L'inefficienza computazionale delle tecniche spettrali standard su matrici di dimensione $d \times d$.

2. Metodologia Proposta

Gli autori propongono un metodo supervisionato basato sulla costruzione di un operatore di densità (density operator) indotto dalle frequenze condizionate alla classe.

Costruzione dell'Operatore di Densità

1. Codifica e Frequenze: Partendo da un dataset etichettato codificato in one-hot, si costruisce una matrice di frequenza $F \in \mathbb{R}^{d \times k}$, dove ogni colonna $f_y$ aggrega le occorrenze delle caratteristiche per la classe $y$.
2. Sollevamento di Ampiezza (Amplitude Lifting): Si applica una trasformazione radice quadrata entry-wise alla matrice di frequenza per ottenere $X = \sqrt{F}$.
3. Definizione dell'Operatore: Si definisce la matrice di densità $\rho_D$ come:
   $$\rho_D = \frac{XX^\top}{\text{tr}(XX^\top)}$$
   Questa matrice è simmetrica, semidefinita positiva (PSD) e ha traccia unitaria, soddisfacendo gli assiomi di un operatore di densità nella teoria della probabilità quantistica.

Proprietà Strutturali Chiave

• Rango Intrinseco: Il rango di $\rho_D$ è limitato superiormente dal numero di classi $k$ (Proposizione 3.6). Questo è cruciale perché permette di rappresentare i dati in uno spazio latente di dimensione $r \le k$, indipendentemente dalla dimensione ambientale $d$.
• Geometria di Hellinger/Bhattacharyya: L'uso della radice quadrata induce una geometria legata al coefficiente di affinità di Bhattacharyya e alla distanza di Hellinger tra le distribuzioni categoriche condizionate. Questo collega il metodo ai kernel spettrali classici.
• Riduzione Spettrale: L'embedding è ottenuto proiettando i vettori normalizzati sullo spazio proprio dominante (autovettori principali) di $\rho_D$. Poiché il rango è basso, gli autovettori possono essere calcolati efficientemente tramite la decomposizione di una matrice Gram $k \times k$ ($G = X^\top X$) invece che su una matrice $d \times d$.

Classificazione nello Spazio Latente

Una volta mappati i dati nello spazio latente a bassa dimensione ($\mathbb{R}^r$), la classificazione viene eseguita tramite:

• Stima di Densità (KDE): Si utilizza la stima di densità del kernel (Kernel Density Estimation) per modellare la distribuzione condizionata alla classe nello spazio latente.
• Regola Decisionale: Si applica una regola di massima verosimiglianza (ML) o massima a posteriori (MAP) per assegnare l'etichetta.

3. Contributi Chiave

1. Operatore PSD Supervisionato: Introduzione di una mappatura formale da dataset categorici etichettati a un operatore di densità normalizzato, fornendo una rappresentazione strutturata per l'apprendimento supervisionato.
2. Legame di Rango e Efficienza: Dimostrazione che il rango dell'operatore è limitato da $k$, permettendo un calcolo spettrale efficiente tramite la matrice Gram $k \times k$, evitando la complessità $O(d^2)$.
3. Interpretazione Geometrica: Collegamento esplicito della costruzione alla geometria di Hellinger e all'affinità di Bhattacharyya, giustificando teoricamente l'uso della radice quadrata.
4. Analisi di Stabilità (Perturbazione): Fornitura di limiti teorici rigorosi basati sul teorema di Davis-Kahan. Gli autori dimostrano che lo spazio proprio dominante è stabile rispetto alle perturbazioni delle frequenze empiriche (rumore di campionamento), a condizione che esista un "gap spettrale" sufficiente. Vengono derivati limiti di probabilità alta per l'errore di perturbazione sotto modelli di campionamento multinomiale.
5. Validazione Sintetica: Esperimenti controllati che testano la robustezza del metodo in scenari di alta cardinalità, sparsità, variabili irrilevanti e squilibrio delle classi.

4. Risultati Sperimentali

Gli esperimenti sintetici (S1-S4) confrontano il metodo proposto (DMM+KDE) con baseline come PCA+KNN, LDA e Random Forest (RF):

• Separazione Controllata (S1): Il metodo DMM+KDE mostra prestazioni superiori o competitive, specialmente in regimi di separazione moderata ($\delta=0.2$), dove riesce a catturare meglio le strutture stabili rispetto a PCA. In regimi di separazione estrema, tutte le metodi flessibili convergono verso la perfezione, ma LDA collassa in scenari di separazione categorica estrema a causa di problemi di condizionamento della covarianza.
• Alta Cardinalità e Sparsità (S2): Aumentando la dimensione ambientale $d$ (mantenendo $n$ fisso), DMM+KDE mantiene prestazioni stabili (accuratezza $\approx 0.98$), confermando la robustezza della struttura a basso rango intrinseco. Al contrario, Random Forest mostra un leggero degrado.
• Robustezza al Rumore (S3): L'aggiunta di variabili categoriche irrilevanti non degrada significativamente le prestazioni, dimostrando che l'operatore filtra efficacemente il rumore.
• Squilibrio delle Classi (S4): L'analisi mostra che l'uso della regola MAP con prior sbilanciati può danneggiare le metriche di classe minoritaria (balanced accuracy), mentre la regola ML pura rimane stabile. Questo evidenzia l'importanza della scelta della regola decisionale in presenza di sbilanciamento.

5. Significato e Implicazioni

Il lavoro offre un quadro teorico solido per l'analisi di dati categorici, spostando il focus dalle tradizionali tecniche di fattorizzazione di matrici di contingenza (come l'Analisi delle Corrispondenze) verso una visione operatoriale basata sulla densità.

• Robustezza Teorica: La connessione con la teoria della perturbazione (Davis-Kahan) fornisce garanzie matematiche sulla stabilità dell'embedding, un aspetto spesso trascurato nei metodi empirici.
• Efficienza Computazionale: La capacità di lavorare con matrici di dimensione $k \times k$ invece che $d \times d$ rende il metodo scalabile per dataset con migliaia o milioni di categorie (alta cardinalità), un caso d'uso comune nell'industria ma difficile per i metodi spettrali classici.
• Interpretabilità: L'approccio basato su densità e kernel offre una base probabilistica naturale per la classificazione, facilitando l'integrazione con modelli bayesiani o di stima di densità.

In sintesi, il paper propone un metodo elegante e matematicamente fondato che trasforma dati categorici sparsi e ad alta dimensionalità in rappresentazioni latenti stabili, efficienti e geometricamente significative, ponendo le basi per futuri sviluppi nell'apprendimento automatico su dati qualitativi.