Epsilon-Neighborhood Decision-Boundary Governed Estimation (EDGE) of 2D Black Box Classifier Functions

1. Il Problema

In molte applicazioni reali critiche (sicurezza, qualità, fattibilità), è fondamentale identificare con precisione il confine decisionale ($\partial S$) che separa gli stati del sistema "desiderabili" (es. stabili, sicuri) da quelli "indesiderabili".
Tuttavia, quando il sistema è modellato come una funzione "Black Box" (senza espressione analitica nota, spesso basata su simulazioni costose o esperimenti fisici), definire questo confine analiticamente è impossibile.
Le sfide principali identificate sono:

• Mancanza di garanzie di precisione: I metodi esistenti (come l'apprendimento attivo o le reti neurali) affinano iterativamente il confine ma non garantiscono che la stima rimanga entro una specifica tolleranza di errore ($\varepsilon$) rispetto al confine reale.
• Inefficienza nel campionamento: I metodi attuali esplorano spesso regioni lontane dal confine o richiedono un numero elevato di valutazioni della funzione (campioni), il che è proibitivo quando le valutazioni sono computazionalmente costose.
• Dipendenza da iperparametri: Molte tecniche richiedono un'attenta sintonizzazione degli iperparametri e soffrono di variabilità stocastica nei risultati.

2. Metodologia: L'Algoritmo EDGE

Il paper propone EDGE ($\varepsilon$-Neighborhood Decision-Boundary Governed Estimation), un algoritmo efficiente e agnostico rispetto alla funzione, progettato per stimare il confine decisionale di un classificatore binario 2D all'interno di un $\varepsilon$-intorno specificato dall'utente.

Principi Fondamentali

• Teorema del Valore Intermedio (IVT): L'algoritmo si basa sull'assunzione che il confine sia continuo. Se esistono due punti, uno interno ($f(x)=1$) e uno esterno ($f(x)=0$), la cui distanza è $\le \varepsilon$, l'IVT garantisce che il confine reale intersechi il segmento che li unisce.
• Definizione dell'Intorno: Invece di cercare il confine esatto (impossibile senza conoscenza analitica), EDGE cerca di delimitare due insiemi di punti:
  • $\partial \tilde{S}_1$: Punti interni entro distanza $\varepsilon$ dal confine.
  • $\partial \tilde{S}_0$: Punti esterni entro distanza $\varepsilon$ dal confine.
    Questi due insiemi "incapsulano" il confine reale.

Fasi dell'Algoritmo

1. Inizializzazione e Bisezione:
   • Si individua una coppia di punti iniziale (uno interno, uno esterno).
   • Viene applicato un algoritmo di bisezione sul segmento che li unisce per localizzare due punti finali ($x_{in}^{end}$ e $x_{out}^{end}$) la cui distanza è inferiore a $\varepsilon$. Questo garantisce che il confine passi tra di essi.
2. Cammino del Confine (Boundary Walk):
   • Una volta trovati i punti iniziali, l'algoritmo "cammina" lungo il confine utilizzando cerchi di raggio $\varepsilon$ centrati sui punti più recenti degli insiemi interno ed esterno.
   • Si calcolano le intersezioni tra i cerchi. Un punto di test viene selezionato in base al prodotto vettoriale (cross product) per mantenere la direzione corretta.
   • Se il punto di test è interno, viene aggiunto a $\partial \tilde{S}_1$; se esterno, a $\partial \tilde{S}_0$.
3. Gestione dei Confini del Dominio:
   • Se il cammino raggiunge il bordo del dominio di interesse ($\partial X$), l'algoritmo esegue un passo lungo il confine del dominio stesso finché non rileva un cambio di stato (da interno a esterno o viceversa), per poi riprendere il cammino principale.
4. Terminazione:
   • L'algoritmo si ferma quando il cammino si chiude su se stesso (torna vicino ai punti di partenza), garantendo che l'intera lunghezza del confine sia stata coperta entro la tolleranza $\varepsilon$.

3. Contributi Chiave

• Garanzia $\varepsilon$-neighborhood: A differenza delle tecniche di apprendimento attivo, EDGE garantisce matematicamente che ogni punto campionato si trovi entro la distanza $\varepsilon$ dal confine reale.
• Efficienza del Campionamento: L'algoritmo è progettato per massimizzare l'efficienza. Una volta superata la fase di inizializzazione, ogni punto campionato contribuisce direttamente alla costruzione dell'approssimazione del confine (100% di efficienza nel "walking" del confine).
• Agnosticismo e Semplicità: Non richiede iperparametri da sintonizzare (a differenza delle SVM o delle reti neurali) ed è applicabile a qualsiasi funzione black box continua.
• Metrica di Accuratezza: Utilizza la Distanza Superficiale Media (ASD) per quantificare l'errore totale tra il confine stimato e quello reale, evitando soluzioni banali.

4. Risultati Sperimentali

L'algoritmo è stato testato su tre funzioni benchmark non lineari (Rosenbrock, Goldenstein-Price, Beale) e su un caso studio reale di stabilità della rete elettrica con fonti rinnovabili (iniezione di potenza variabile).

I risultati sono stati confrontati con:

1. Campionamento a Griglia Naive: Garantisce l'accuratezza $\varepsilon$ ma è estremamente inefficiente (il numero di campioni scala con $1/\varepsilon^2$).
2. Active Learning Boundaries (ALB) con SVM: Un metodo iterativo che cerca di apprendere il confine.

Punti di forza evidenziati:

• Efficienza dei Campioni: EDGE richiede drasticamente meno campioni rispetto alla griglia naive (es. migliaia di campioni in meno) e meno dell'ALB in termini di stabilità.
• Accuratezza (ASD): EDGE ottiene valori di ASD inferiori e più consistenti rispetto all'ALB, che mostra alta variabilità stocastica a seconda dei punti di inizializzazione.
• Tempo di Calcolo: EDGE è significativamente più veloce dell'ALB, poiché quest'ultimo deve risolvere problemi di ottimizzazione SVM con complessità $O(m^3)$ ad ogni iterazione.
• Scalabilità: Mentre il metodo a griglia diventa intrattabile all'aumentare della precisione ($\varepsilon$), la complessità di EDGE scala linearmente con la lunghezza del confine ($L/\varepsilon$).

5. Significato e Implicazioni

Il lavoro di EDGE rappresenta un avanzamento significativo nella stima dei confini decisionali per sistemi black box, specialmente in contesti ingegneristici dove:

• Le valutazioni sono costose (simulazioni ad alta fedeltà, esperimenti fisici).
• È richiesta una garanzia rigorosa di sicurezza (il confine stimato non deve "sbagliare" di più di una certa soglia).
• Si evitano i costi computazionali e la complessità della sintonizzazione degli iperparametri tipici dei metodi di Machine Learning supervisionato.

Il paper conclude suggerendo estensioni future verso problemi multiclasse, spazi ad alta dimensionalità e sistemi con rumore di misura, dove il parametro $\varepsilon$ può essere utilizzato per gestire le zone di transizione morbida tra le classi. Inoltre, i punti campionati da EDGE potrebbero essere utilizzati come vettori di supporto ottimali per addestrare SVM più efficienti e meno stocastici.