Punti di sella nell'ottimizzazione: cosa sono e perché contano

Anche se tutte le derivate parziali della tua funzione sono nulle, non è detto che tu sia vicino a un minimo.

L'ottimizzazione è la ricerca del valore minimo o massimo di una funzione, e ogni metodo che usi cerca un punto in cui il gradiente è piatto. Ma un gradiente piatto non garantisce che tu abbia trovato la soluzione migliore. A volte significa che la funzione sale in una direzione e scende in un'altra, proprio nello stesso punto.

Quel punto si chiama punto di sella: scende da un lato, sale dall'altro, ed è piatto tutto intorno. Riconoscere i punti di sella è importante perché il tuo algoritmo può bloccarsi lì e scambiare un gradiente piatto per un vero minimo.

In questo articolo ti mostrerò come individuare un punto di sella matematicamente e perché spesso confonde gli algoritmi di ottimizzazione.

Cos'è un punto di sella?

In un punto di sella, il gradiente è zero, proprio come in un minimo o in un massimo. Ma un punto di sella non è né l'uno né l'altro.

La funzione curva verso l'alto in alcune direzioni e verso il basso in altre, esattamente nello stesso punto. Se vai lungo un asse, il valore sale, e se vai lungo un asse diverso, scende. Da qui il nome: richiama la forma di una sella, che curva verso l'alto davanti e dietro e verso il basso ai lati.

Ecco una semplice funzione in due variabili che userò per mostrare com'è fatta:

Funzione in due variabili

All'origine, (0, 0), entrambe le derivate parziali sono nulle, quindi è un punto critico (detto anche punto stazionario). Muovendoti lungo l'asse x, f aumenta a causa del termine x^2. Muovendoti lungo l'asse y, f diminuisce a causa del termine -y^2 .

Se rappresenti questa funzione in 3D, la superficie curva in su in una direzione e in giù nell'altra, formando proprio la forma a cui il punto di sella deve il nome.

Grafico di superficie 3D di f(x, y) = x^2 - y^2

Un grafico delle curve di livello della stessa funzione racconta la stessa storia dall'alto. Le linee di livello attorno all'origine sembrano iperboli, non i loop chiusi che vedresti attorno a un minimo o a un massimo.

Curve di livello di f(x, y) = x^2 - y^2

La definizione esatta cambia un po' a seconda del campo. In analisi multivariata, un punto di sella è un punto critico che non è un minimo o un massimo locale. In ottimizzazione e in teoria dei giochi, il termine può significare qualcosa di diverso, legato a problemi di minimax più che alla curvatura. Tratterò questa distinzione più avanti nell'articolo.

Punti di sella vs. minimi e massimi

Prima di vedere come identificare matematicamente i punti di sella, aiuta confrontarli con gli altri due tipi di punti critici.

Minimo locale

In un minimo locale, la funzione aumenta in ogni direzione vicina. Immagina una ciotola: se ti allontani dal fondo in qualsiasi direzione, sali. La funzione f(x, y) = x2 + y2 si comporta così.

Massimo locale

In un massimo locale, la funzione diminuisce in ogni direzione vicina. È l'immagine speculare di un minimo, una cupola invece di una ciotola. La funzione f(x, y) = -x2 - y2 diminuisce in ogni direzione mentre ti allontani dall'origine.

Punto di sella

In un punto di sella, la funzione aumenta in alcune direzioni e diminuisce in altre. È questo che rende f(x, y) = x2 - y2, l'esempio della sezione precedente, un punto di sella invece di un minimo o un massimo: sale lungo l'asse x e scende lungo l'asse y, nello stesso punto.

Ecco come si confrontano i tre affiancati:

Grafici di superficie 3D affiancati di un minimo locale, massimo locale e punto di sella

Come trovare un punto di sella

Trovare un punto di sella significa calcolare le derivate, trovare dove si annullano e poi osservare come la funzione curva attorno a quel punto.

Userò la stessa funzione di prima:

Funzione di riferimento

Ecco il processo, passo dopo passo.

1. Calcola le prime derivate parziali

Deriva f rispetto a x, trattando y come costante, poi fai lo stesso per y:

Calcolo delle prime derivate parziali

2. Pónile uguali a zero

Risolvi per il punto in cui entrambe le derivate parziali si annullano contemporaneamente:

Impostare le derivate a zero

Questo dà x = 0 e y = 0, quindi (0, 0) è un punto critico. Le prime derivate non ti diranno di che tipo.

3. Calcola le derivate seconde

Te ne servono tre: la derivata di f_x rispetto a x, la derivata di f_y rispetto a y e la derivata mista:

Derivate seconde

4. Classifica il punto critico usando la curvatura 

f_xx = 2 è positivo, quindi f curva verso l'alto lungo l'asse x. f_yy = -2 è negativo, quindi f curva verso il basso lungo l'asse y. Una direzione curva in su, l'altra in giù, nello stesso punto: questo è il punto di sella.

Questo processo in quattro passaggi funziona per qualsiasi funzione due volte derivabile.

Nelle prossime due sezioni, formalizzerò il passaggio 4 con strumenti che scalano oltre due variabili: la matrice Hessiana e il test della derivata seconda.

Come la matrice Hessiana identifica i punti di sella

La matrice Hessiana raccoglie tutte le derivate seconde dell'ultima sezione in un unico oggetto, ed è lo strumento che ti dice se un punto critico è un minimo, un massimo o un punto di sella.

Per una funzione in due variabili, l'Hessiana ha questo aspetto:

Hessiana per una funzione in due variabili

Ogni elemento descrive la curvatura: f_xx e f_yy descrivono la curvatura lungo gli assi x e y, e f_xy descrive come interagiscono quelle due direzioni. Se inserisci le derivate seconde della sezione precedente, l'Hessiana della nostra funzione di esempio diventa così:

Hessiana per la funzione di riferimento

Una matrice da sola non ti dice molto. Ciò che conta sono i suoi autovalori: i numeri che descrivono come la funzione curva lungo un insieme specifico di direzioni chiamate autovettori.

• Un autovalore positivo significa che la funzione curva verso l'alto lungo la direzione del suo autovettore
• Un autovalore negativo significa che la funzione curva verso il basso lungo quella direzione
• Un mix di autovalori positivi e negativi significa che la funzione curva in su in alcune direzioni e in giù in altre (un punto di sella)

Poiché l'Hessiana del nostro esempio è diagonale, gli autovalori sono proprio sulla diagonale: 2 e -2. I loro autovettori puntano lungo l'asse x e l'asse y, esattamente la curvatura che hai trovato a mano nella sezione precedente. f curva in su lungo x perché lì l'autovalore è positivo, e in giù lungo y perché lì l'autovalore è negativo.

La maggior parte delle funzioni non avrà un'Hessiana diagonale, quindi gli autovettori non si allineeranno perfettamente con gli assi x e y, e dovrai calcolarli direttamente invece di leggerli dalla matrice. Ma un autovalore positivo e uno negativo significano che ti trovi su un punto di sella.

Il test della derivata seconda per i punti di sella

Non serve calcolare a mano gli autovalori ogni volta. Per le funzioni in due variabili c'è una scorciatoia: il test della derivata seconda, costruito sul determinante dell'Hessiana.

Ecco il determinante, usando le stesse derivate seconde di prima:

Il determinante

D è il determinante dell'Hessiana, e il suo segno - combinato con il segno di f_xx - classifica il punto critico:

• D > 0 e f_xx > 0: Minimo locale

• D > 0 e f_xx < 0: Massimo locale

• D < 0: Punto di sella

• D = 0: Inconcludente

Nel nostro esempio, f_xx = 2, f_yy = -2 e f_xy = 0:

Test della derivata seconda per la funzione di riferimento

D è negativo, quindi il test conferma che (0, 0) è un punto di sella.

Questo test è la regola degli autovalori della sezione precedente, riscritta in una forma calcolabile senza risolvere per gli autovettori. D è il prodotto dei due autovalori e f_xx + f_yy è la loro somma. Quando D è negativo, gli autovalori devono avere segni opposti, e questo definisce un punto di sella. Quando D è zero, almeno un autovalore è zero, quindi la curvatura in quella direzione è piatta, e né il test né i soli autovalori possono dirti cosa sta succedendo lì.

Punti di sella nell'ottimizzazione

Finora abbiamo parlato di identificare un punto di sella quando hai già la funzione. Nell'ottimizzazione, invece, cerchi il punto migliore senza saperlo in anticipo, e i metodi basati sul gradiente usano il gradiente nullo per decidere quando fermarsi.

Ed è proprio qui che i punti di sella creano problemi.

Un ottimizzatore basato sul gradiente si muove nella direzione che riduce più velocemente la funzione obiettivo e continua finché il gradiente non si avvicina a zero. Ma un gradiente quasi nullo non dice all'algoritmo se ha trovato un minimo o un punto di sella.

Le direzioni di curvatura positiva spingono la funzione verso l'alto, e l'algoritmo ha già imparato che fare passi lì peggiora le cose. Le direzioni di curvatura negativa ci sono ancora, e sono la via d'uscita, ma un algoritmo che si fida solo del gradiente può non vederle, perché proprio in un punto di sella il gradiente in quelle direzioni è vicino a zero anch'esso.

È anche qui che l'ottimizzazione rallenta.

La magnitudine del gradiente tende a ridursi avvicinandosi a qualunque punto stazionario, quindi un algoritmo che scala i passi in base alla dimensione del gradiente fa passi piccoli vicino a un punto di sella, che sia o meno vicino al minimo che sta realmente cercando.

Trovare un punto stazionario non equivale a concludere un'ottimizzazione. Ti serve comunque un modo per capire che un gradiente quasi nullo appartiene a un punto di sella e non a un minimo, e un modo per trovare la direzione che continua a migliorare l'obiettivo una volta che lo sai.

Punti di sella nel machine learning

La funzione di perdita di una rete neurale è funzione di ogni peso e bias nella rete, a volte milioni o miliardi di dimensioni. Siamo ben lontani da un esempio giocattolo a due variabili.

In un'analisi dell'ottimizzazione non convessa ad alta dimensionalità, Dauphin e colleghi sostengono che all'aumentare del numero di dimensioni i punti critici hanno molte più probabilità di essere punti di sella che minimi o massimi locali. Ogni dimensione aggiunge un'altra direzione in cui la curvatura può andare in un senso o nell'altro, e basta una sola direzione di curvatura negativa per trasformare un punto critico in un punto di sella invece che in un minimo.

Questo conta durante l'addestramento perché la discesa del gradiente può vedere solo il gradiente su cui si trova in quel momento.

Vicino a un punto di sella, quel gradiente diventa piccolo in ogni direzione: lo stesso segnale che vedresti avvicinandoti a un vero minimo. L'addestramento può rallentare o bloccarsi in una regione per niente ottimale, e non c'è modo di capire dal solo andamento della loss se sei vicino a un minimo o bloccato su un punto di sella.

Ecco perché i punti di sella compaiono così spesso insieme ai minimi locali quando si parla di addestramento di reti neurali. Ma non sono l'unico ostacolo. Gradienti che svaniscono, curvatura mal condizionata e la scala dello spazio di ricerca rendono l'ottimizzazione ad alta dimensionalità difficile.

Come gli algoritmi di ottimizzazione gestiscono i punti di sella

Nulla di tutto questo significa che l'addestramento basato sul gradiente sia destinato a fallire vicino a un punto di sella. Ci sono alcune tecniche che possono aiutarti a superarli, ciascuna da un'angolazione diversa.

Stochastic gradient descent

Stochastic gradient descent calcola il gradiente da un sottoinsieme casuale dei dati di addestramento invece che dall'intero dataset, e quel sottoinsieme cambia a ogni passo.

Il rumore introdotto fa sì che il gradiente stimato sia raramente esattamente zero, anche in una regione in cui il gradiente vero è vicino a zero. Quel rumore può bastare a spingere l'ottimizzatore fuori da un punto di sella e in una direzione di curvatura negativa, invece di stallare proprio dove il gradiente si annulla.

Momentum

Il momentum mantiene una media mobile dei gradienti passati e la usa, invece del solo gradiente attuale, per decidere il passo successivo.

Intorno a un punto di sella, questo conta perché l'ottimizzatore arriva già in movimento in una certa direzione, trascinato dai gradienti prima di arrivarci. Quel moto accumulato può portarlo attraverso la regione piatta attorno alla sella, invece di rallentare nel momento in cui il gradiente locale si avvicina a zero.

Metodi del secondo ordine

I metodi del secondo ordine usano direttamente le informazioni sulla curvatura.

Lavorando con l'Hessiana o una sua approssimazione, questi metodi possono distinguere tra direzioni di curvatura positiva e negativa in un punto critico. È proprio la distinzione su cui si regge un punto di sella, quindi un metodo del secondo ordine può identificare la direzione di discesa e muoversi in quella, invece di trattare tutti i gradienti quasi nulli allo stesso modo.

Punti di sella vs. concetti correlati

Alcuni termini vengono confusi abbastanza spesso con i punti di sella da meritare un chiarimento.

Punto di sella vs. minimo locale

Un minimo locale curva verso l'alto in ogni direzione vicina, quindi mostra curvatura positiva coerente tutto intorno. Un punto di sella curva verso l'alto solo in alcune direzioni e verso il basso in altre. Nel momento in cui trovi anche solo una direzione con curvatura negativa, non stai più guardando un minimo.

Punto di sella vs. massimo locale

Lo stesso ragionamento vale al contrario per un massimo locale. La curvatura resta negativa in ogni direzione vicina. Un punto di sella aggiunge almeno una direzione di curvatura positiva accanto a quelle negative.

Punto di sella vs. punto di flesso

Un punto di flesso è un'idea monodimensionale. È dove una curva passa da concavità verso l'alto a concavità verso il basso, o viceversa, lungo una singola variabile.

Un punto di sella richiede almeno due variabili, perché l'intero concetto dipende dal confronto della curvatura in direzioni diverse nello stesso punto. Una funzione di una variabile può avere un punto di flesso, ma non può avere un punto di sella, non essendoci una seconda direzione che curvi nell'altro senso.

Punto di sella vs. punto stazionario

Ogni punto di sella è un punto stazionario, dato che il gradiente lì è zero. Ma non vale il contrario. Un punto stazionario è semplicemente un punto in cui il gradiente è zero: può essere un minimo locale, un massimo locale o un punto di sella. Ti servono le informazioni di curvatura dall'Hessiana o dal test della derivata seconda per sapere quale dei tre sia.

Ecco una panoramica più visiva di come si confrontano:

Punti di sella a confronto con altri concetti

Punti di sella nell'ottimizzazione minimax

Finora abbiamo usato "punto di sella" per descrivere la curvatura di un punto critico. Esiste un secondo significato, più antico, che viene dalla teoria dei giochi e che compare anche nel machine learning moderno.

Nell'ottimizzazione minimax, un giocatore minimizza una funzione mentre un altro la massimizza, e un punto di sella è la coppia di valori in cui nessuno dei due può migliorare il proprio risultato cambiando solo la propria mossa.

La teoria dei giochi usa questo per descrivere strategie di equilibrio in giochi competitivi. L'ottimizzazione avversaria prende in prestito la stessa struttura per problemi in cui un processo cerca il caso peggiore che un altro processo deve saper contrastare.

Le generative adversarial networks (GAN) sono il miglior esempio nel machine learning. Un generatore minimizza la propria loss producendo dati falsi convincenti, mentre un discriminatore massimizza la propria capacità di distinguere i dati reali da quelli falsi. Addestrare una GAN significa cercare un punto di sella in questo senso minimax, ovvero un equilibrio in cui generatore e discriminatore hanno entrambi trovato la miglior risposta all'altro.

Questo punto di sella minimax è correlato al punto di sella come punto critico visto in precedenza, ma i due non sono intercambiabili.

La versione come punto critico descrive la curvatura in un singolo punto di una funzione. La versione minimax descrive un equilibrio tra due obiettivi in competizione. Usano la stessa parola perché entrambi coinvolgono un mix di comportamenti "in su" e "in giù", ma confonderli non ti porterà lontano se provi ad applicare un test basato sull'Hessiana a un gioco a due giocatori.

Errori comuni quando si lavora con i punti di sella

La maggior parte della confusione sui punti di sella si riduce a un paio di errori ricorrenti. Ecco cosa devi sapere.

Supporre che un gradiente nullo implichi un minimo

Un gradiente nullo ti dice solo che hai trovato un punto critico, non di che tipo. Controlla la curvatura prima di dare per finito il lavoro, perché anche un punto di sella ha gradiente zero.

Classificare un punto usando solo le derivate prime

Le derivate prime trovano i punti critici ma non possono classificarli. Ti servono le derivate seconde, tramite l'Hessiana o il test della derivata seconda, per distinguere un minimo da un massimo da un punto di sella.

Ignorare le diverse direzioni di curvatura

Una funzione può curvare verso l'alto lungo l'asse x ed essere comunque complessivamente un punto di sella, se un'altra direzione curva verso il basso. Controlla ogni direzione, o usa gli autovalori dell'Hessiana, che le coprono tutte insieme.

Confondere i punti di sella con i punti di flesso

Un punto di flesso descrive un cambio di curvatura in una singola variabile. Un punto di sella descrive curvatura mista su più variabili nello stesso punto. Sono concetti affini in linea generale, ma non si applicano allo stesso tipo di funzione e la matematica sottostante non è intercambiabile.

Trattare tutti gli usi di "punto di sella" come identici

Il punto di sella come punto critico e il punto di sella minimax condividono il nome, non la definizione. Prima di applicare un test basato sull'Hessiana o un argomento sugli autovalori, verifica quale significato è in gioco: teoria dei giochi e ottimizzazione avversaria usano la versione minimax, che non si riduce a un controllo di curvatura su una singola funzione.

Conclusione

Un punto di sella curva verso l'alto in alcune direzioni e verso il basso in altre, alle stesse coordinate: ecco perché non è né un minimo né un massimo, anche se lì il gradiente va a zero proprio come in entrambi.

I gradienti trovano il punto critico. Gli autovalori dell'Hessiana, o il test della derivata seconda, ti dicono quale tipo hai davanti. In alta dimensione questa distinzione conta molto perché i punti di sella sono più numerosi dei minimi locali, e algoritmi di addestramento come SGD e momentum esistono anche per superarli.

Un'ultima cosa da tenere distinta è che il punto di sella minimax della teoria dei giochi e delle GAN condivide il nome ma non la matematica: quindi assicurati di sapere a quale ti riferisci.

Se l'idea dei punti di sella ti incuriosisce, ti piacerà il nostro Deep Learning Track in Python. Oltre alla teoria, userai PyTorch per creare reti neurali per diversi tipi di problemi.