Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networks

Sintesi Tecnica: Approssimazione Rapida e Apprendimento di Compiti di Classificazione Binaria in Strutture O-minime utilizzando Reti Neurali ReLU

Problema
Il documento investiga problemi di classificazione binaria in cui l'insieme decisionale $A \subseteq [-1/2, 1/2]^n$ è definito all'interno di un'espansione o-minima del campo reale. Sebbene le reti neurali profonde abbiano dimostrato un successo empirico, la comprensione teorica del loro potere di approssimazione e della loro apprendibilità statistica si basa spesso su assunzioni strutturali specifiche riguardo al set target, come la regolarità (smoothness) del confine o classi di funzioni di tipo Barron. Gli autori mirano a stabilire tassi quantitativi di approssimazione e di apprendimento per una classe più ampia di insiemi "tami" definiti dall'o-minimalità, che include insiemi semi-algebrici e varie strutture analitiche, senza fare affidamento su assunzioni di regolarità globale che potrebbero non sussistere per confini decisionali complessi.

Metodologia
Gli autori introducono una classe di insiemi chiamata insiemi tracciabili (traceable sets) come un proxy classico per gli insiemi definibili nelle strutture o-minime. Questo concetto è motivato dai teoremi di decomposizione in celle inerenti alla geometria o-minima.

1. Insiemi Tracciabili: Un insieme $A$ è definito come $m$-tracciabile se può essere costruito induttivamente tramite mappe $C^m$ limitate $f_i, g_i$ che definiscono i confini dell'insieme in modo fibra-dipendente. Nello specifico, l'insieme è costruito come una sequenza di funzioni "orizzonte" dove ogni strato è delimitato da funzioni regolari. Gli autori definiscono gli insiemi $(m, \ell)$-tracciabili come unioni finite disgiunte di tali insiemi.
2. Proprietà di Estensione: Per facilitare l'approssimazione, il documento impone una proprietà di estensione $(m, B)$, richiedendo che le funzioni di confine $f_i, g_i$ possano essere estese a funzioni $C^m$ su l'intero dominio con norme di Sobolev limitate.
3. Strategia di Approssimazione: La tecnica di approssimazione centrale prevede:
   • Approssimare le "funzioni orizzonte" (funzioni caratteristiche di regioni delimitate da grafici regolari) utilizzando reti neurali ReLU. Ciò sfrutta i risultati esistenti sull'approssimazione di funzioni regolari e delle loro composizioni.
   • Costruire la funzione caratteristica dell'insieme tracciabile componendo queste approssimazioni utilizzando operazioni di minimo e massimo basate su ReLU (poiché $\chi_{\cap} = \min$ e $\chi_{\cup} = \max$).
   • Utilizzare il fatto che la frontiera (confine) di questi insiemi ha misura di Lebesgue nulla sotto le assunzioni di estensione, garantendo che l'approssimazione della chiusura dell'insieme sia sufficiente per l'approssimazione in $L^p$.
4. Framework di Apprendimento: L'analisi dell'apprendimento statistico combina i derivati tassi di approssimazione con stime di entropia (numeri di copertura) per le classi di reti neurali ReLU. Gli autori applicano la minimizzazione del rischio empirico (ERM) con perdita hinge su queste specifiche classi di reti per derivare i limiti di generalizzazione.

Contributi Chiave e Risultati

• Tassi di Approssimazione Quantitativi: Il documento dimostra che la funzione caratteristica $\chi_\Omega$ di un qualsiasi insieme $(m, \ell)$-tracciabile $\Omega \subseteq [-1/2, 1/2]^n$ può essere approssimata in norma $L^p$ con accuratezza $\epsilon$ da una rete neurale ReLU $\Phi_\epsilon$.

  • Dimensione della Rete: Il numero di pesi non nulli (dimensione) richiesto è $O(\epsilon^{-p(n-1)/m})$.
  • Profondità: La profondità della rete è limitata indipendentemente da $\epsilon$, specificamente $O(\log(\ell n) + \log(m))$.
  • Pesi: I pesi crescono al massimo polinomialmente in $1/\epsilon$.
  • Questo risultato si estende a una sottoclasse di mappe definibili $f: [-1/2, 1/2]^n \to \mathbb{R}$ che sono piecewise smooth su domini tracciabili.

• Tassi di Apprendimento Statistico: Per $N$ campioni indipendenti estratti uniformemente dal dominio, gli autori derivano i tassi di apprendimento per la minimizzazione del rischio empirico sulle costruite classi di reti ReLU.

  • L'errore di classificazione atteso del classificatore risultante è limitato da $O(N^{-m/(m+pn-p)})$ fino a un fattore di perdita polinomiale arbitrariamente piccolo $N^\kappa$.
  • Questo tasso è derivato combinando i limiti di errore di approssimazione con l'entropia di copertura della classe di ipotesi.

• Applicazione alle Strutture O-minime: Gli autori dimostrano che le collezioni definibili "$m$-ammissibili" in strutture o-minime (collezioni di fibre di insiemi definibili con limiti uniformi sulla decomposizione in celle) soddisfano le proprietà degli insiemi tracciabili. Di conseguenza, i derivati tassi di approssimazione e di apprendimento si applicano direttamente a queste collezioni definibili, fornendo una teoria unificata per i problemi di classificazione con confini decisionali "tami".

Significatività e Rivendicazioni
Il documento sostiene di fornire una nozione matematicamente robusta di regolarità per la teoria della classificazione basata sulla definibilità nelle strutture o-minime. Isolando le caratteristiche analitiche (tracciabilità e estensioni regolari) necessarie per una rapida approssimazione, gli autori mostrano che l'o-minimalità cattura una vasta gamma di pratici insiemi decisionali pur consentendo comunque forti tassi quantitativi di approssimazione e stima.

La significatività risiede nel colmare il divario tra teoria dei modelli (o-minimalità) e deep learning moderno. Gli autori sostengono che le strutture o-minime offrono un quadro unificante naturale dove la teoria dell'approssimazione, l'apprendimento statistico e l'ottimizzazione possono essere studiati simultaneamente. A differenza degli ambienti di tipo Barron, che possono avere difficoltà con la composizione di funzioni, il framework o-minimo accoglie naturalmente la composizione ripetuta di mappe affini e attivazioni non lineari tipiche delle reti neurali profonde, poiché la composizione di mappe definibili rimane definibile.

I risultati suggeriscono che per i confini decisionali che sono "tami" (definibili in una struttura o-minima), le reti neurali ReLU possono raggiungere tassi ottimali o quasi ottimali a seconda del parametro di regolarità $m$ e della dimensione $n$, senza richiedere che i confini siano globalmente regolari. Il documento nota esplicitamente che questi tassi sono derivati per specifiche sottoclassi di insiemi e mappe, e che i tassi di apprendimento sono contingenti alle proprietà di finitezza uniforme (limiti uniformi sulle componenti connesse e sulla dimensione VC) inerenti alle collezioni definibili nelle strutture o-minime.