An Iterative Geometric Approach to Optimizing Separating Hyperplanes

Sintesi Tecnica: Un Approccio Geometrico Iterativo per l'Ottimizzazione di Iperpiani Separatori

Definizione del Problema
Il documento affronta il problema di calcolare l'iperpiano a margine massimo per un dataset con etichette binarie e linearmente separabile. Ciò equivale a risolvere il problema di ottimizzazione SVM a margine rigido (hard-margin), un programma quadratico convesso. Mentre i solver standard (ad es. SMO, metodi a punti interni) risolvono questo problema direttamente sull'intero dataset, il documento investiga uno scenario specifico: dato un iperpiano separatore iniziale, ammissibile (ma non ottimale), è possibile raggiungere la soluzione ottimale in modo più efficiente attraverso una sequenza di raffinamenti geometrici iterativi? L'obiettivo è migliorare il margine continuamente, mantenendo rigorosamente la separabilità lineare ad ogni passaggio.

Metodologia
Il metodo proposto è un algoritmo iterativo che trasforma un attuale iperpiano separatore $H_i$ in un nuovo iperpiano $H_{i+1}$ con un margine maggiore. Il processo si basa su informazioni locali (l' "insieme attivo") piuttosto che sul dataset globale. L'algoritmo procede come segue:

1. Identificazione dell'Insieme Attivo: Per l'attuale iperpiano $H_i$, l'algoritmo identifica l'insieme attivo $A_i$, costituito dai campioni di entrambe le classi più vicini all'iperpiano.
2. Ottimizzazione Locale: Un solver SVM esistente viene applicato esclusivamente all'insieme attivo $A_i$ per calcolare il suo iperpiano separatore a margine massimo locale, denotato con vettore normale $w^*_i$.
3. Controllo di Convergenza: Se l'attuale iperpiano $H_i$ coincide con $H^*_i$, l'algoritmo termina, poiché è dimostrato che un iperpiano ottimale per il proprio insieme attivo è globalmente ottimale (Lemma 1).
4. Ri-allineamento Geometrico: Se $H_i \neq H^*_i$, l'algoritmo ri-allinea $H_i$ verso $H^*_i$. Ciò viene ottenuto interpolando il vettore normale: $w_i(\alpha) = (1-\alpha)w_i + \alpha w^*_i$. La rotazione avviene attorno a un punto di pivot $m$, definito come il punto medio di una coppia selezionata di vettori di supporto di etichetta opposta appartenenti ad $A_i$.
5. Espansione del Margine e Blocco: Il parametro $\alpha$ viene incrementato da 0 a 1. Durante questa rotazione, il margine rispetto all'insieme attivo aumenta in modo strettamente monotono. Tuttavia, la rotazione è vincolata da "campioni di blocco" esterni all'insieme attivo che potrebbero attraversare gli iperpiani del margine. L'algoritmo calcola il massimo $\alpha$ ammissibile ($\alpha_{actual}$) tale che nessun nuovo campione violi il vincolo di separazione.
6. Iterazione: L'iperpiano viene aggiornato utilizzando $\alpha_{actual}$. Se $\alpha_{actual} < 1$, un nuovo campione (o un insieme di campioni) è diventato attivo (un "campione di blocco"), e il processo si ripete con l'aggiornato insieme attivo. Se $\alpha_{actual} = 1$, la soluzione ottima globale è stata raggiunta.

Contributi Chiave

• Tecnica Geometrica Iterativa: Il documento introduce un nuovo algoritmo che decompone il problema di ottimizzazione globale in una sequenza di sottoproblemi più piccoli definiti dagli insiemi attivi. A differenza dei metodi tradizionali che minimizzano una funzione obiettivo globale, questo approccio esegue trasformazioni geometriche (rotazioni) dell'iperpiano per massimizzare il margine.
• Risultati Teorici:
  • Ottimalità Locale-Globale: Il documento formalizza la condizione per cui, se un iperpiano separatore è ottimale rispetto al proprio insieme attivo, esso è globalmente ottimale.
  • Relazione del Margine Geometrico: Deriva una relazione che mostra come il margine dell'iperpiano interpolato sia proporzionale al coseno dell'angolo tra l'attuale vettore normale e il vettore normale ottimale dell'insieme attivo ($\gamma(\alpha) = \gamma^* \cos \theta(\alpha)$).
  • Interpretazione KKT: Il lavoro fornisce un'interpretazione geometrica delle condizioni di Karush–Kuhn–Tucker (KKT) nel contesto delle SVM, collegando la separazione degli involucri convessi proiettati all'ottimalità.
• Valutazione Sperimentale: Il metodo è stato implementato in Python utilizzando NumPy e CVXPY ed è stato testato su coppie di cifre MNIST linearmente separabili.

Risultati Sperimentali
Gli esperimenti hanno confrontato il metodo di raffinamento iterativo proposto con un solver globale di base (CVXPY con OSQP) su coppie di cifre MNIST (con un range di circa 2.000 ~ 12.000 campioni).

• Dataset Piccoli (~2.000 campioni): Il metodo proposto è stato più lento del solver globale diretto, richiedendo circa 10 volte il tempo di calcolo in alcuni casi. L'overhead del calcolo di molteplici sottoproblemi ha superato i benefici.
• Dataset Grandi (~12.000 campioni): Il metodo è diventato competitivo. Includendo il tempo per calcolare l'iperpiano ammissibile iniziale, il metodo è stato più veloce nei 6 esperimenti su 10 di set di addestramento. Assumendo che l'iperpiano iniziale fosse già preesistente, la sola fase di raffinamento ha superato la baseline in 8 esperimenti su 10.
• Dimensione dell'Insieme Attivo: Gli insiemi attivi sono rimasti significativamente più piccoli della dimensione totale del dataset (la dimensione media dell'insieme attivo era circa la metà del numero di vettori di supporto), validando la strategia di risolvere sottoproblemi ridotti.
• Convergenza: L'algoritmo ha raggiunto costantemente la soluzione ottimale in tutti gli esperimenti, con un numero di iterazioni compreso tra 84 e 778.

Significatività e Rivendicazioni
Il documento sostiene che l'approccio proposto sia particolarmente vantaggioso in scenari in cui trovare un iperpiano separatore ammissibile è computazionalmente più semplice rispetto al calcolo diretto di quello ottimale, o quando un iperpiano ammissibile è già disponibile. Il metodo non sostituisce i solver SVM esistenti, ma offre un quadro alternativo che sfrutta la fattibilità e la geometria dell'insieme attivo.

Gli autori sono modesti riguardo l'universalità del metodo. Riconoscono che il metodo non supera l'ottimizzazione diretta su dataset più piccoli e che la complessità computazionale dipende fortemente dal solver scelto per i sottoproblemi dell'insieme attivo. Inoltre, il documento nota che rimangono aperte alcune questioni teoriche, specificamente se la direzione di ri-allineamento scelta garantisca l'incremento di margine più rapido possibile e se il metodo sia garantito terminare in un numero finito di iterazioni per tutti i casi. Il lavoro è presentato come una prospettiva geometrica sull'ottimizzazione del margine massimo che fornisce nuovi approfondimenti sulla relazione tra ottimi locali e globali.