Sintesi Tecnica: EM-NESY: Expectation Maximization per l'Apprendimento Neurosimbolico

Definizione del Problema

I modelli neurosimbolici (NeSy) mirano a integrare i punti di forza percettivi delle reti neurali con le capacità di ragionamento della logica simbolica. Sebbene i modelli NeSy allo stato dell'arte raggiungano tipicamente un apprendimento end-to-end tramite la backpropagation dei gradienti attraverso sia i componenti neurali che quelli simbolici, questo approccio affronta sfide significative quando il componente simbolico si affida all'inferenza approssimata.

L'inferenza probabilistica esatta è spesso #P-hard e computazionalmente intrattabile per compiti complessi. Di conseguenza, molti sistemi ricorrono a metodi di inferenza approssimata (ad esempio, campionamento, propagazione del messaggio o rilassamenti di programmazione lineare). Tuttavia, questi metodi introducono problemi di differenziabilità:

1. Non differenziabilità: Tecniche come il campionamento sono intrinsecamente non differenziabili, richiedendo stimatori di gradiente specializzati (ad esempio, REINFORCE) o trucchi di riparametrizzazione.
2. Overhead Computazionale: Anche metodi iterativi teoricamente differenziabili (ad esempio, la propagazione del messaggio) diventano impraticabili da differenziare nella pratica a causa del massiccio grafo computazionale richiesto per eseguire la backpropagation attraverso tutte le iterazioni.

Le soluzioni attuali spesso richiedono modifiche specifiche all'inferenza per garantire la differenziabilità, limitando la flessibilità e la scalabilità dei sistemi NeSy.

Metodologia: EM-NeSy

Gli autori propongono EM-NeSy, un framework di apprendimento che inquadra l'apprendimento NeSy probabilistico come un'istanza dell'algoritmo Expectation-Maximization (EM). Questa formulazione scinde il processo di inferenza simbolica dal calcolo del gradiente, consentendo l'uso di qualsiasi motore di inferenza (esatto o approssimato, differenziabile o meno).

Il Framework

Il modello NeSy è trattato come un modello a variabili latenti dove:

• $X$: Input subsimbolico (ad esempio, immagini).
• $Z$: Variabili simboliche latenti (predette neuralmente).
• $Y$: Output simbolico target (ad esempio, la validità di una griglia di Sudoku).
• $\theta$: Parametri della rete neurale.

Il processo di apprendimento alterna due fasi:

1. E-Step (Expectation):
   Il componente simbolico calcola la distribuzione a posteriori delle variabili latenti $Z$ condizionata all'osservato $Y$ e all'input $X$:
   $$p(z|y, x, \theta) = \frac{p_{Ne}(z|x, \theta)p_{Sy}(y|z)}{p(y|x, \theta)}$$
   Qui, $p_{Ne}$ è il prior neurale e $p_{Sy}$ è la verosimiglianza simbolica. Fondamentalmente, questo step agisce come un "correttore probabilistico", abducendo etichette soft o hard per $Z$ basandosi sulla conoscenza di background. Questo step può essere eseguito da qualsiasi motore di inferenza simbolica (esatto, approssimato, basato su campionamento) senza richiedere la differenziabilità.

2. M-Step (Maximization):
   I parametri neurali $\theta$ vengono aggiornati minimizzando la cross-entropy tra il prior neurale $p_{Ne}(z|x, \theta)$ e la posterior $\ell(z)$ calcolata nell'E-step:
   $$L_{EM-NeSy}(\theta) = -\sum_{z \in R(Z)} \ell(z) \log p_{Ne}(z|x, \theta)$$
   I gradienti sono propagati all'indietro solo attraverso il componente neurale, trattando la posterior $\ell(z)$ come una costante. Ciò elimina la necessità di differenziare attraverso il processo di inferenza simbolica.

Equivalenza Teorica

Il paper dimostra che, sotto inferenza esatta, i gradienti calcolati da EM-NeSy sono matematicamente equivalenti a quelli del normale apprendimento NeSy end-to-end differenziabile (Teorema 3.1). Pertanto, EM-NeSy recupera l'impostazione standard quando l'inferenza esatta è fattibile, ma offre un vantaggio distinto quando non lo è.

Varianti ed Estensioni

• Hard EM: Utilizza assegnazioni Maximum A Posteriori (MAP) invece di posterior soft.
• Multi-M EM: Esegue molteplici M-step (aggiornamenti del gradiente) per un singolo E-step per accelerare la convergenza senza ricalcolare la costosa posterior.
• Inferenza Approssimata: Il framework supporta naturalmente metodi basati sul campionamento (ad esempio, Rejection Sampling, ABC Sampling) e algoritmi iterativi (ad esempio, Belief Propagation) senza modifiche.

Contributi Chiave

1. Riformulazione dell'Apprendimento NeSy: Gli autori hanno riclassificato l'apprendimento NeSy all'interno del framework EM, consentendo l'uso di varianti avanzate di EM (Generalized EM, Stochastic EM, Hard EM) per una maggiore flessibilità.
2. Integrazione Priva di Differenziabilità: È stato proposto un framework generale che integra qualsiasi motore di inferenza probabilistica in un modello NeSy senza richiedere che il processo di inferenza simbolica sia differenziabile.
3. Scalabilità ed Efficienza: L'approccio dimostra che l'apprendimento NeSy può scalare a compiti in cui l'inferenza esatta è intrattabile o dove differenziare attraverso solver iterativi è computazionalmente proibitivo.

Risultati Sperimentali

Gli autori hanno valutato EM-NeSy su tre benchmark: MNISTAdd (addizione di cifre scritte a mano), Visual Sudoku e Warcraft path-planning.

• Inferenza Esatta (MNISTAdd): EM-NeSy ha raggiunto un'accuratezza comparabile al normale NeSy end-to-end differenziabile (BP-std) e a DeepStochLog. Tuttavia, ha superato significativamente questi ultimi in termini di scalabilità ed efficienza. Mentre DeepStochLog non è riuscito a scalare a 15 cifre a causa dei limiti della compilazione della conoscenza, EM-Nexy è scalato a 100 cifre. Ha inoltre ridotto l'uso di memoria di picco da ~90 GB a ~35 GB e ha ridotto il tempo di addestramento.
• Inferenza Approssimata/Non Differenziabile:
  • Visual Sudoku: I metodi differenziabili standard (Scallop, SL) sono andati in timeout su griglie 9x9. EM-NeSy, utilizzando il campionamento Approximate Bayesian Computation (ABC), ha ottenuto un'accuratezza competitiva (53,3%) con un tempo di addestramento minimo (8,24 min), mentre altri metodi erano inapplicabili.
  • Warcraft Path-Planning: EM-NeSy con campionamento ABC ha raggiunto un'accuratezza state-of-the-art (98,80% su 12x12, 69,60% su 30x30) con tempi di addestramento significativamente più rapidi rispetto a I-MLE ed EXAL.
• Limitazioni Osservate: Le prestazioni di EM-NeSy dipendono dalla qualità della posterior approssimata. L'Hard EM (MAP) ha mostrato bias su MNISTAdd, e la loopy belief propagation è fallita su Sudoku 9x9 a causa della struttura del factor graph. Il campionamento ABC ha mostrato un'alta varianza su istanze più grandi, ma è rimasto efficace in contesti più piccoli.

Significato e Rivendicazioni

Il paper sostiene che EM-NeSy fornisce un framework di apprendimento unificato che semplifica sostanzialmente la progettazione del modello eliminando la necessità di modifiche alla differenziabilità specifica per l'inferenza. Trattando l'apprendimento NeSy come un problema EM, l'approccio:

• Permette l'uso di qualsiasi motore di inferenza simbolica, inclusi solver specializzati, ottimizzati o non differenziabili.
• Recupera l'apprendimento standard end-to-end sotto inferenza esatta, offrendo al contempo una superiore efficienza computazionale e scalabilità della memoria.
• Consente ai sistemi NeSy di affrontare compiti che coinvolgono vincoli combinatori complessi (come il path-planning o il Sudoku) dove l'inferenza esatta è impraticabile e le approssimazioni differenziabili sono difficili da costruire.

Gli autori concludono che, sebbene EM-NeSy non risolva il problema della selezione di approssimazioni efficaci (che rimane dipendente dal compito), esso rimuove la barriera della differenziabilità, abilitando così sistemi neurosimbolici più scalabili e flessibili.