Riassunto Tecnico: Spazi Polidisc Non-Archimediani e Applicazioni all'Ottimizzazione

1. Definizione del Problema

L'analisi di dati gerarchici è ubiquitaria in campi che spaziano dalla filogenetica alla genomica, dalla linguistica alla sociologia. Sebbene le strutture gerarchiche inducano naturalmente strutture geometriche non-archimediane (spesso visualizzate come alberi metrici), catturare tali strutture fedelmente sui numeri reali ($\mathbb{R}$) è difficile. L'embedding di tali dati in $\mathbb{R}^n$ spesso richiede spazi ad alta dimensionalità o geometria iperbolica, che potrebbero non preservare le proprietà ultrametriche intrinseche.

Al contrario, lavorare direttamente su campi non-archimediani (come i numeri $p$-adici $\mathbb{Q}_p$) preserva la struttura gerarchica ma presenta sfide significative per l'ottimizzazione. La topologia di questi campi è totalmente disconnessa, proibendo l'uso delle standard tecniche di ottimizzazione continua come la discesa del gradiente. Di conseguenza, i problemi di ottimizzazione su spazi non-archimediani si riduene frequentemente a ricerche combinatorie computazionalmente costose.

Il problema centrale affrontato da questo articolo è la mancanza di un framework geometrico che simultaneamente:

1. Rappresenti fedelmente i dati gerarchici tramite la geometria non-archimediana.
2. Fornisca un dominio continuo e connesso per cammini adatto alle tecniche di ottimizzazione standard (es. geodetiche, convessità, gradienti).

2. Metodologia e Framework

Gli autori propongono un nuovo framework ispirato alla geometria di Berkovich, introducendo gli spazi polidisc ($B^n$ e $H^n$) come dominio per l'ottimizzazione.

2.1 Spazi Polidisc

Invece di lavorare direttamente nello spazio non-archimediano $K^n$, gli autori definiscono gli spazi polidisc come prodotti di sfere chiuse su un campo non-archimediano $K$ (es. $\mathbb{Q}_p$ o campi di serie di Laurent).

• Struttura: $B^n$ consiste in polidisc $B_B(a, r)$ (raggio assoluto) o $B_H(a, v)$ (raggio valutativo).
• Geometria: Questi spazi mantengono la rigida struttura gerarchica di $K^n$ (insiemi annidati, non sovrapposti) acquisendo al contempo caratteristiche geometriche desiderabili assenti in $K^n$:
  • Connessione per cammini: Lo spazio è connesso tramite geodetiche.
  • Geodetiche: Lo spazio è unicamente geodesico (per $n=1$ o $1 < p < \infty$), permettendo la definizione di cammini tra due punti qualsiasi.
  • Convessità: Una nozione di involucri convessi è definita sulla base delle geodetiche.
  • Direzioni Tangenti: Viene introdotta una struttura di tipo calcolo tramite direzioni tangenti, definite come classi di equivalenza di geodetiche che emanano da un punto. Ciò permette la definizione di derivate direzionali.

2.2 Teoria delle Funzioni

Gli autori introducono una classe di funzioni a valori reali chiamate polinomi assoluti e polinomi di valutazione.

• Definizione: Dato un polinomio $f$ con coefficienti nel campo dei polidisc, la funzione mappa un polidisc $B$ nel supremo di $|f(z)|$ (o l'infimo di $val(f(z))$) su $z \in B$.
• Proprietà: Queste funzioni ammettono formule di valutazione esplicite. Crucialmente, sono polinomiali a tratti (nel caso assoluto) o lineari/tropicali a tratti (nel caso della valutazione) lungo le geodetiche.
• Approssimazione Universale: Gli autori dimostrano un teorema di approssimazione universale (Teorema 45), mostrando che combinazioni lineari di polinomi assoluti possono approssimare qualsiasi funzione continua su sottoinsiemi compatti di $B^n$.

2.3 Embedding di Alberi Metrici

L'articolo stabilisce che gli alberi metrici possono essere naturalmente e spesso isometricamente immersi nello spazio polidisc iperbolico $H^1$.

• Criteri: Un embedding isometrico esiste se il grado massimo dei vertici dell'albero è limitato da $|K| + 1$ e le lunghezze degli archi corrispondono a valori nel gruppo di valutazione di $K$.
• Estensione del Campo: Se queste condizioni non sono soddisfatte, il framework fornisce una procedura costruttiva per estendere il campo base $K$ (estendendo il gruppo di valutazione o il campo residuo) per consentire l'embedding senza modificare i sottoalberi precedentemente immersi.

2.4 Teoria dell'Ottimizzazione

L'articolo sviluppa una teoria per minimizzare funzioni della forma $\ell = \sum a_i |f_i|$, dove $a_i > 0$ e $f_i$ sono polinomi.

• Esistenza di Minimizzatori: I teoremi 52 e 55 stabiliscono le condizioni sotto le quali esistono minimi globali. Nello specifico, se le chiusure proiettive dei loci degli zeri dei polinomi si intersecano all'interno dello spazio affine $K^n$, o se non si intersecano mai, esiste un minimo globale.
• Localizzazione: Nel caso univariato, tutti i minimi globali sono confinati in una regione limitata determinata dai coefficienti dei polinomi (Teorema 62).
• Algoritmi: Gli autori adattano diverse strategie di ottimizzazione al contesto polidisc:
  • Best-First Descent: Raffinamento greedy dei polidisc.
  • Best-First Gradient Descent: Utilizza le derivate direzionali per selezionare la branca di discesa più ripida.
  • Deterministic Optimistic Optimisation (DOO): Bilancia esplorazione e sfruttamento utilizzando upper confidence bounds derivati dalle proprietà Lipschitz delle funzioni.
  • Monte-Carlo Tree Search (MCTS): Adatta MCTS allo spazio polidisc, includendo una variante DAG-MCTS per gestire la struttura a grafo aciclico diretto dei polidisc di dimensione superiore dove i nodi possono avere più genitori.

3. Contributi Chiave

1. Framework Geometrico: L'introduzione degli spazi polidisc ($B^n, H^n$) come un dominio computazionalmente trattabile e connesso per cammini per l'ottimizzazione non-archimediana, colmando il divario tra dati gerarchici discreti e ottimizzazione continua.
2. Classe di Funzioni: La definizione e l'analisi dei polinomi assoluti e di valutazione, provando la loro struttura a tratti lungo le geodetiche e le loro capacità di approssimazione universale.
3. Teoria dell'Ottimizzazione: Dimostrazione dell'esistenza di minimi globali per combinazioni lineari positive di polinomi assoluti sotto specifiche condizioni geometriche sui loci degli zeri, e la derivazione di limiti espliciti per i minimizzatori nel caso univariato.
4. Adattamento Algoritmico: La formulazione di algoritmi di ottimizzazione (Best-First, Gradient Descent, DOO, MCTS) su misura per la geometria gerarchica e ramificata degli spazi polidisc.
5. Implementazione Software: Lo sviluppo e il rilascio di NonArchimedeanMachineLearning.jl, una libreria open-source in Julia che implementa gli oggetti geometrici, le classi di funzioni e gli algoritmi di ottimizzazione.

4. Risultati e Scoperte Sperimentali

Gli autori hanno condotto esperimenti computazionali utilizzando la loro libreria Julia per validare il framework teorico:

• Ricerca delle Radici Polinomiali: Gli algoritmi sono riusciti a convergere verso le radici di polinomi su $\mathbb{Q}_p$. I metodi MCTS e Best-First hanno mostrato una convergenza più rapida rispetto a DOO nei compiti semplici di ricerca delle radici.
• Minimizzazione della Somma di Polinomi Assoluti: Gli algoritmi sono stati testati per minimizzare somme di valori assoluti di polinomi. MCTS e DAG-MCTS hanno generalmente superato i metodi greedy in termini di perdita finale, specialmente in scenari con landscape di perdita più complessi, sebbene con un costo computazionale maggiore.
• Interpolazione Polinomiale: Il framework ha risolto con successo problemi di interpolazione (trovare i coefficienti per un polinomio che passi per determinati punti) minimizzando la perdita dell'erroo quadratico.
• Apprendimento di Funzioni: Gli autori hanno dimostrato la capacità di apprendere funzioni (approssimando etichette binarie) utilizzando i polinomi assoluti come classe di ipotesi.
• Performance: I metodi basati su MCTS hanno ottenuto i migliori ranghi medi attraverso varie attività, ma hanno richiesto più valutazioni di funzioni e tempo di esecuzione rispetto ai metodi di discesa greedy. Gli esperimenti hanno confermato che aumentare il numero di simulazioni in MCTS migliora le prestazioni.

5. Significato e Rivendicazioni

L'articolo sostiene di fornire una base matematica e computazionale per l'ottimizzazione e il machine learning su spazi non-archimediani. La sua importanza risiede in:

• Unificazione di Rappresentazione e Ottimizzazione: Offre uno spazio unico ($B^n$) che funge sia da rappresentazione naturale per i dati gerarchici (tramite embedding isometrici di alberi) sia da dominio per l'ottimizzazione (tramite geodetiche e gradienti).
• Superamento delle Barriere Topologiche: Passando dal campo totalmente disconnesso $K^n$ allo spazio polidisc connesso per cammini $B^n$, gli autori rendono utilizzabili metodi basati su gradienti e ricerca ad albero precedentemente inapplicabili all'ottimizzazione non-archimediana.
• Viabilità Pratica: Lo sviluppo della libreria NonArchimedeanMachineLearning.jl dimostra che queste costruzioni teoriche sono computazionalmente fattibili, fornendo uno strumento per la ricerca futura all'intersezione tra geometria non-archimediana, ottimizzazione e machine learning.

Gli autori osservano che, sebbene l'attuale framework si concentri sui polinomi assoluti, l'approccio è modulare e potrebbe essere esteso a classi di funzioni più ampie. Posizionano questo lavoro come una prova di concetto per un nuovo paradigma nella gestione dei dati gerarchici, distinto dagli esistenti approcci iperbolici o euclidei ad alta dimensione.