$p$-adic Principal Component Analysis

Il paper formula un problema di ottimizzazione $p$-adica sulla fattorizzazione di matrici e indaga un metodo euristico analogo all'analisi delle componenti principali (PCA).

L'essenziale

Immagina di avere una montagna di dati: liste di numeri, scelte sì/no, o categorie diverse. Il compito di un analista è trovare il "filo conduttore", ovvero capire quali sono le informazioni davvero importanti e quali sono solo rumore di fondo. Nel mondo reale, usiamo uno strumento chiamato PCA (Analisi delle Componenti Principali), che funziona come un filtro intelligente: riduce la complessità dei dati mantenendo solo le parti essenziali, proprio come un riassunto che cattura l'essenza di un libro lungo.

Tuttavia, questo strumento funziona bene solo con numeri "normali" (i numeri reali, come quelli che usiamo per misurare la temperatura o il prezzo di un caffè). Ma cosa succede se i tuoi dati non sono numeri reali, ma hanno una struttura matematica molto strana e "disconnessa"? Pensiamo ai dati binari (0 e 1), ai sistemi di crittografia o a certi tipi di intelligenza artificiale. Qui, i numeri "normali" falliscono.

L'autore di questo articolo, Tomoki Mihara, ha inventato una nuova versione della PCA, chiamata PCA p-adica. Ecco come funziona, spiegata con metafore semplici:

1. Il Mondo dei Numeri "P-adici": Una Città a Strati

Immagina che i numeri reali siano come una strada liscia e continua: puoi camminare da un punto all'altro senza salti.
I numeri p-adici (dove "p" è un numero primo, come 2, 3 o 7) sono invece come una città costruita su livelli concentrici, o come un albero genealogico infinito.

• In questa città, due numeri sono "vicini" non se sono simili per grandezza (come 10 e 11), ma se condividono una storia comune profonda (come due numeri che finiscono con le stesse cifre in una base specifica).
• È un mondo "frammentato": se provi a tracciare una linea tra due punti, potresti dover saltare attraverso buchi infiniti. È un universo perfetto per dati categorici o logici (come il codice binario di un computer), ma terribile per le regole matematiche tradizionali.

2. Il Problema: La Bussola Rotta

La PCA classica funziona cercando le direzioni in cui i dati si "allungano" di più, usando un concetto chiamato "ortogonalità" (come gli assi X e Y di un grafico che formano un angolo di 90 gradi).
Nel mondo p-adico, però, la bussola è rotta:

• Non puoi disegnare angoli di 90 gradi come fai su un foglio di carta.
• Non puoi usare la "derivata" (la pendenza di una curva) per trovare il punto migliore, perché in questo mondo le curve sono piatte quasi ovunque o saltano all'improvviso.
• Se provi a usare la PCA normale qui, è come cercare di navigare in un labirinto usando una mappa di una città pianeggiante: ti perderai.

3. La Soluzione: Trovare il "Punto Vicino" invece dell'Angolo

L'autore ha detto: "Dimentichiamo gli angoli di 90 gradi. Invece, chiediamoci: qual è il punto più vicino?"
Immagina di avere un punto nel tuo spazio dati e vuoi proiettarlo su una linea. Invece di cercare la linea che forma un angolo retto (che non esiste qui), cerchi la linea che ti porta al punto più vicino possibile in termini di "distanza p-adica".

• L'Analogia: Immagina di dover parcheggiare un'auto in un garage molto stretto e irregolare. Non puoi misurare l'angolo di ingresso. Invece, provi a entrare finché non tocchi il muro più vicino possibile senza sbattere. Quella è la tua "proiezione".

4. L'Algoritmo: Due Modi di Fare PCA

L'articolo propone due metodi per costruire questo nuovo filtro (la PCA p-adica):

• Metodo "Grezzo" (Non-reduced): È come cercare di pulire una stanza prendendo gli oggetti uno per uno, in ordine casuale, e buttando via ciò che sembra ridondante. È veloce, ma a volte ti lasci dietro pezzi di spazzatura o rompi cose utili.
• Metodo "Raffinato" (Reduced): Prima di iniziare a pulire, fai un giro completo della stanza e organizzi gli oggetti in pile ordinate, assicurandoti che non si sovrappongano in modo confuso. Poi procedi alla pulizia. È più lento all'inizio, ma il risultato finale è molto più pulito e ordinato.

5. L'Esperimento: Trovare gli Intrusi

Per testare il loro nuovo metodo, gli autori hanno creato un gioco di "caccia all'intruso" (rilevamento di anomalie).

• La scena: Immagina una stanza piena di persone vestite in modo normale (i dati "normali"). Qualcuno è vestito in modo strano (i dati "anomali").
• La sfida: In un mondo normale, l'intruso si vede subito perché è "grande" o "luminoso". Ma nel mondo p-adico, l'intruso potrebbe sembrare normale per grandezza, ma avere una "struttura" interna diversa.
• Il risultato: Il metodo "Raffinato" (Reduced PCA) è stato bravissimo a identificare gli intrusi, anche quando sembravano normali. Ha capito che, anche se un intruso aveva un "peso" basso, la sua posizione nella struttura a strati lo rendeva diverso. Il metodo "Grezzo" ha funzionato meno bene, ma ha commesso meno errori nel segnalare persone innocenti come colpevoli.

In Sintesi

Questo articolo ci dice che non dobbiamo forzare tutti i dati a stare nel mondo dei numeri reali. Se i tuoi dati hanno una struttura logica, discreta o "a blocchi" (come i dati dei computer o le scelte categoriche), possiamo usare la matematica p-adica.

L'autore ha creato un nuovo "occhiale" (la PCA p-adica) che ci permette di vedere le strutture nascoste in questi dati strani, trovando i punti più vicini invece degli angoli perfetti, e riuscendo a fare cose che i metodi tradizionali non possono fare, come distinguere un intruso in una folla dove tutti sembrano uguali. È un passo avanti per l'intelligenza artificiale e l'analisi dei dati nel mondo digitale.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper "p-adic Principal Component Analysis" di Tomoki Mihara, redatta in italiano.

Titolo: Analisi delle Componenti Principali p-adiche (p-adic PCA)

1. Il Problema e il Contesto

L'Analisi delle Componenti Principali (PCA) classica è uno strumento fondamentale per la riduzione della dimensionalità basato sull'algebra lineare su $\mathbb{R}$. Tuttavia, la sua applicazione diretta a variabili categoriali o a dati con strutture algebriche specifiche (come insiemi booleani $\{0, 1\}$ o anelli $\mathbb{Z}/n\mathbb{Z}$) presenta limiti significativi:

• Perdita di struttura: L'embedding in uno spazio euclideo spesso trascura le operazioni algebriche originali dei dati, producendo componenti che sono combinazioni reali virtuali e non variabili categoriali reali.
• Limiti dell'ottimizzazione p-adica: Sebbene i numeri p-adici ($\mathbb{Q}_p$) offrano un ambiente naturale per certi tipi di dati discreti e categoriali, l'ottimizzazione in questo campo è ostacolata da diverse difficoltà teoriche:
  • Assenza di gradienti: Non esiste una teoria del calcolo differenziale standard per funzioni a valori reali (come le funzioni di perdita) definite su spazi p-adici, rendendo inapplicabili metodi basati sul gradiente.
  • Mancanza di diagonalizzabilità: Le matrici simmetriche non sono necessariamente diagonalizzabili in $\mathbb{Q}_p$, invalidando il metodo classico della PCA basato sulla decomposizione della matrice di covarianza.
  • Problemi di inner product: Il prodotto scalare standard p-adico non soddisfa sempre la condizione di non-degenerazione ($\langle v, v \rangle = 0 \iff v = 0$), rendendo difficile collegare la correlazione all'inner product.
  • Distribuzioni: Non esiste un analogo p-adico naturale della distribuzione normale che permetta una standardizzazione efficace.

L'obiettivo del paper è formulare una versione della PCA adattata all'ambiente p-adico ($\mathbb{Q}_p^D$ o $\mathbb{Z}_p^D$) che rispetti la struttura algebrica dei dati e funzioni senza gradienti.

2. Metodologia

L'autore propone un approccio basato su una nuova definizione di ortogonalità p-adica e su metodi euristici di approssimazione a rango basso.

• Ortogonalità p-adica:
  Invece di basarsi su un inner product o sulla norma $\ell_\infty$, l'autore definisce l'ortogonalità attraverso la relazione tra il punto perpendicolare e il punto più vicino (nearest neighbour). Un vettore $w$ è la componente di $v_0$ lungo $v_1$ se $w$ è il punto più vicino a $v_0$ nel sottospazio generato da $v_1$. La componente ortogonale è definita come $v_0 - w$. Questa definizione non è simmetrica e richiede processi iterativi.

• Algoritmi di Proiezione e Ortogonalizzazione:

  • Proiezione 1D: Viene utilizzato un algoritmo basato su Trie Tree (alberi di prefissi) per risolvere il problema di ottimizzazione $\min_{c \in \mathbb{Q}_p} \|v_0 - c v_1\|$ in modo efficiente, sfruttando le espansioni p-adiche finite.
  • Ortogonalizzazione Iterata: Poiché l'ortogonalità non è simmetrica, un singolo passaggio di ortogonalizzazione non garantisce un sistema ortogonale. L'autore introduce un processo iterativo (Algoritmo 5) che ripete l'ortogonalizzazione finché la norma non si stabilizza o si raggiunge una soglia.

• Due Varianti di PCA p-adica:

  1. NRPCA (Non-reduced p-adic PCA): Un approccio greedy che seleziona dinamicamente il primo vettore non nullo disponibile dai dati residui come nuova componente, calcolando le proiezioni e aggiornando i dati. È computazionalmente più leggero ma produce un sistema di coordinate non ortogonale.
  2. RPCA (Reduced p-adic PCA): Un approccio che pre-calcola un sistema di coordinate approssimativamente ortogonale tramite ortogonalizzazione iterata dei dati originali, per poi selezionare le componenti da questo sistema pre-computato. Questo metodo è più costoso ma garantisce una migliore struttura ortogonale.

• Funzione di Perdita:
  A differenza della PCA classica che usa la norma $\ell_2$ (o $\ell_\infty$ per la fattorizzazione di Smith), questo metodo utilizza la norma $\ell_q$ (con $q \in [1, \infty)$). L'uso di $\ell_q$ è cruciale per l'individuazione di anomalie (anomaly detection), poiché la norma $\ell_\infty$ (usata nella forma normale di Smith) fallisce quando le anomalie hanno norme $\ell_\infty$ piccole ma significative in termini di struttura.

• Line Search e Coordinate Descent:
  Vengono introdotti metodi di ricerca lineare e discesa delle coordinate p-adici per verificare la località dell'ottimalità delle soluzioni ottenute, aggiornando i coefficienti finché non si raggiunge un minimo locale.

3. Risultati Sperimentali

Gli esperimenti sono stati condotti su dati sintetici con $p=7$, dimensione $D=100$, e compiti di rilevamento delle anomalie (anomaly detection) in contesti non supervisionati.

• Scenario 1: Palle Aperte (Open Balls):
  I dati normali sono distribuiti in unioni disgiunte di palle chiuse.

  • RPCA ha mostrato tassi di veri positivi (True Positive Ratio) molto superiori rispetto alla NRPCA, specialmente quando il numero di palle ($B$) era inferiore alla dimensionalità ridotta ($D_-$).
  • La RPCA è riuscita a distinguere le anomalie anche quando le loro norme $\ell_\infty$ erano grandi, un compito in cui la fattorizzazione basata sulla forma normale di Smith fallisce.
  • La NRPCA ha mostrato tassi di falsi positivi (False Positive Ratio) leggermente inferiori, rendendola potenzialmente utile quando la priorità è minimizzare gli allarmi falsi.

• Scenario 2: Sottospazi Affini:
  I dati normali giacciono su un sottospazio affine di codimensione positiva con rumore.

  • La RPCA ha ottenuto prestazioni eccezionali (tasso di veri positivi > 95%) anche quando la dimensione del sottospazio ($D'$) era maggiore della dimensionalità ridotta target ($D_-$).
  • Questo risultato è significativo perché i metodi lineari classici (come l'eliminazione di Gauss su $\mathbb{F}_p$ o la forma normale di Smith) non riescono in questi scenari non supervisionati, poiché le anomalie possono avere norme $\ell_\infty$ maggiori delle righe "dispari" della matrice di base, ingannando i metodi basati su $\ell_\infty$.

4. Contributi Chiave

1. Formulazione della PCA p-adica: Prima formulazione sistematica di un metodo di riduzione della dimensionalità per spazi vettoriali p-adici, aggirando la mancanza di diagonalizzabilità e gradienti.
2. Nuova Definizione di Ortogonalità: Introduzione di un concetto di ortogonalità basato sulla proiezione del punto più vicino, che sostituisce l'inner product classico in contesti p-adici.
3. Algoritmi Efficienti: Sviluppo di algoritmi basati su Trie Tree per la risoluzione efficiente dei problemi di ottimizzazione locale in $\mathbb{Q}_p$.
4. Validazione per l'Anomaly Detection: Dimostrazione empirica che la PCA p-adica, utilizzando norme $\ell_q$, supera i limiti dei metodi basati sulla forma normale di Smith (che usano $\ell_\infty$) nel rilevare anomalie in dati con strutture algebriche complesse.

5. Significato e Implicazioni

Il lavoro di Mihara apre nuove strade per l'analisi dei dati categoriali e discreti che possiedono una struttura algebrica intrinseca (come dati binari o modulari).

• Superamento dei limiti reali: Mostra che l'embedding in spazi euclidei non è sempre la scelta migliore per dati discreti; l'uso diretto di spazi p-adici preserva meglio la struttura dei dati.
• Applicabilità nell'IA e Machine Learning: Il metodo è rilevante per le reti neurali p-adiche e l'analisi di cluster, offrendo strumenti per l'ottimizzazione e la riduzione della dimensionalità in domini dove i metodi basati sul gradiente falliscono.
• Robustezza: La capacità di RPCA di funzionare bene anche quando la dimensionalità intrinseca dei dati supera quella target suggerisce una robustezza superiore rispetto ai metodi lineari classici in scenari di rumore e non-linearità strutturale.

In sintesi, il paper fornisce un framework teorico e pratico per estendere le tecniche di analisi multivariata classica al mondo p-adico, risolvendo problemi fondamentali di ottimizzazione e offrendo soluzioni pratiche per l'analisi di dati categoriali complessi.