Arresto anticipato

Nell'apprendimento automatico, l'arresto anticipato è una forma di regolarizzazione utilizzata per evitare il sovradattamento nell'addestramento di un modello con un metodo iterativo, come la discesa del gradiente. Tali metodi aggiornano il modello per adattarlo meglio ai dati di addestramento a ogni iterazione. Fino a un certo punto, questo migliora le prestazioni del modello misurate su dati esterni al set di addestramento (ad esempio, il set di validazione). Oltre tale livello, tuttavia, il miglioramento dell'adattamento del modello ai dati di addestramento comporta un aumento dell'}errore di generalizzazione. Le regole di arresto anticipato forniscono indicazioni sul numero di iterazioni che possono essere eseguite prima che il learner inizi a sovradattarsi. Regole di arresto anticipato sono impiegate in molti tipi metodi di apprendimento automatico, con diversi fondamenti teorici.

Contesto

In questa sezione sono richiamati alcuni dei concetti di base dell'apprendimento automatico necessari per una descrizione dei metodi di arresto anticipato.

Sovradattamento

Figura 1. La linea verde rappresenta un modello sovradattato e la linea nera rappresenta un modello regolarizzato. Sebbene la linea verde segua meglio i dati di training, è troppo dipendente da tali dati ed è probabile che presenti un tasso di errore più elevato sui nuovi dati non visualizzati, i punti con contorno nero, rispetto alla linea nera.

Gli algoritmi di apprendimento automatico addestrano un modello basato su un insieme finito di dati di training. Durante questa fase, il modello viene valutato in base alla sua accuratezza nel predire le osservazioni contenute nel set di training. In generale, tuttavia, l'obiettivo di un algoritmo di apprendimento automatico è produrre un modello che generalizzi, ovvero che sia capace di fare predizioni su osservazioni mai viste prima. Il sovradattamento si verifica quando un modello si adatta bene ai dati del set di training, incorrendo tuttavia in un errore di generalizzazione maggiore.

Regolarizzazione

La regolarizzazione, nel contesto dell'apprendimento automatico, si riferisce al processo di modifica di un algoritmo di apprendimento in modo da prevenire l'overfitting. Ciò generalmente comporta l'imposizione di una sorta di vincolo di uniformità sul modello appreso. Questa uniformità può essere imposta esplicitamente, fissando il numero di parametri nel modello o aumentando la funzione di costo come nella regolarizzazione di Tikhonov. Questa, insieme alla regressione delle componenti principali e a molti altri schemi di regolarizzazione, rientrano nella regolarizzazione spettrale, caratterizzata dall'applicazione di un filtro. Anche l'arresto anticipato appartiene a questa classe di metodi.

Metodi di discesa del gradiente

I metodi di discesa del gradiente sono metodi di ottimizzazione iterativi del primo ordine. Ogni iterazione aggiorna una soluzione approssimata del problema di ottimizzazione compiendo un passo nella direzione del gradiente negativo della funzione obiettivo. Scegliendo opportunamente la lunghezza del passo, tale metodo può convergere a un minimo locale della funzione obiettivo. La discesa del gradiente viene utilizzata nell'apprendimento automatico definendo una funzione di perdita che riflette l'errore del modello sul training set la quale viene in seguito minimizzata.

Arresto anticipato basato su risultati analitici

Arresto precoce nella teoria dell'apprendimento statistico

L'arresto anticipato può essere utilizzato per regolarizzare i problemi di regressione non parametrici tipici dell'apprendimento automatico. Dato uno spazio di input $X$, uno spazio di output $Y$ e un insieme di campioni estratti da una distribuzione di probabilità sconosciuta $\rho$ su $Z=X\times Y$, l'obiettivo in tali problemi è approssimare una funzione di regressione $f_{\rho }$, data da

$f_{\rho }(x)=\int _{Y}y\,d\rho (y\mid x),\,x\in X,$

dove $\rho (y\mid x)$ è la distribuzione condizionata da $x$ indotta da $\rho$ . Una scelta comune per approssimare la funzione di regressione è quella di utilizzare funzioni da uno spazio di Hilbert a kernel riproducente. Questi spazi possono essere a dimensioni infinite, cosicché possono fornire soluzioni che si sovradattano a insiemi di addestramento di dimensione arbitraria. La regolarizzazione è, quindi, particolarmente importante per tali metodi. Un modo per regolarizzare i problemi di regressione non parametrica è applicare una regola di arresto anticipato a una procedura iterativa come la discesa del gradiente.

Le regole di arresto anticipato proposte per questi problemi si basano sull'analisi dei limiti superiori dell'errore di generalizzazione in funzione del numero di iterazioni. Esse forniscono indicazioni sul numero di iterazioni da eseguire che possono essere calcolate prima di avviare il processo risolutivo.

Esempio: perdita dei minimi quadrati

[Adattamento da ]

Siano $X\subseteq \mathbb {R} ^{n}$ e $Y=\mathbb {R} .$ Dato un insieme di campioni

$\mathbf {z} =\left\{(x_{i},y_{i})\in X\times Y:i=1,\dots ,m\right\}\in Z^{m},$

estratto in maniera indipendente da $\rho$, si voglia minimizzare il funzionale

${\mathcal {E}}(f)=\int _{X\times Y}(f(x)-y)^{2}\,d\rho$

dove, $f$ è un membro dello spazio di Hilbert a nucleo riproducente ${\mathcal {H}}$. Cioè, minimizzare il rischio atteso per una funzione di perdita dei minimi quadrati. Poiché ${\mathcal {E}}$ dipende dalla distribuzione di probabilità sconosciuta $\rho$, non può essere utilizzato per il calcolo. Si consideri, invece, il seguente rischio empirico

${\mathcal {E}}_{\mathbf {z} }(f)={\frac {1}{m}}\sum _{i=1}^{m}\left(f(x_{i})-y_{i}\right)^{2}.$

Siano $f_{t}$ e $f_{t}^{\mathbf {z} }$ le t -esime iterazioni della discesa di gradiente applicate, rispettivamente, ai rischi attesi ed empirici, dove entrambe le iterazioni sono inizializzate all'origine ed entrambe utilizzano una dimensione del passo pari $\gamma _{t}$. Le $f_{t}$ costituiscono l'iterazione della popolazione, che converge a $f_{\rho }$, ma non possono essere utilizzato nel calcolo, mentre le $f_{t}^{\mathbf {z} }$ costituiscono l'iterazione del campione che solitamente converge verso una soluzione di sovradattamento.

Si deve tenere sotto controllo la differenza tra il rischio atteso dell'iterazione del campione e il rischio atteso minimo, ovvero il rischio atteso della funzione di regressione:

${\mathcal {E}}(f_{t}^{\mathbf {z} })-{\mathcal {E}}(f_{\rho })$

Tale differenza può essere riscritta come somma di due termini: la differenza nel rischio atteso tra le iterazioni del campione e della popolazione e quella tra l'iterazione della popolazione e la funzione di regressione:

${\mathcal {E}}(f_{t}^{\mathbf {z} })-{\mathcal {E}}(f_{\rho })=\left[{\mathcal {E}}(f_{t}^{\mathbf {z} })-{\mathcal {E}}(f_{t})\right]+\left[{\mathcal {E}}(f_{t})-{\mathcal {E}}(f_{\rho })\right]$

Questa equazione presenta un compromesso tra bias e varianza, che viene poi risolto per fornire una regola di arresto ottimale che può dipendere dalla distribuzione di probabilità sconosciuta. Per tale regola esistono limiti probabilistici associati all'errore di generalizzazione. Per un'analisi che porta alla regola di arresto anticipato e ai limiti, si rimanda il lettore all'articolo originale. In pratica, si possono utilizzare metodi basati sui dati, ad esempio la convalida incrociata, per ottenere una regola di arresto adattiva.

Arresto anticipato nel boosting

Il boosting è una famiglia di algoritmi in cui un insieme di modelli deboli (learner che sono solo leggermente correlati con il processo reale) vengono combinati per produrre un modello forte. È stato dimostrato, per diversi algoritmi di boosting (fra i quali AdaBoost), che la regolarizzazione tramite arresto anticipato può fornire garanzie di consistenza, ovvero far sì che il risultato dell'algoritmo tenda ad avvicinarsi alla soluzione reale all'aumentare del numero di campioni

Boosting L₂

I metodi di boosting hanno stretti legami con i metodi di discesa del gradiente descritti in precedenza e possono essere considerati un metodo di basato su una funzione di perdita $L_{2}$: L₂Boost .

Arresto anticipato basato sulla convalida

Tali regole di arresto anticipato funzionano suddividendo l'insieme di addestramento originale in un nuovo set di addestramento e un insieme di convalida. L'errore sull'insieme convalida viene utilizzato come approssimazione dell'errore di generalizzazione nel determinare quando è iniziato il sovradattamento. Questi metodi sono impiegati nell'addestramento di molti algoritmi iterativi, comprese quelli per le reti neurali. Prechelt fornisce il seguente schema per un'implementazione ingenua dell'arresto anticipato basato su holdout nel modo seguente:

• Suddividere i dati di training in un training set e uno di validazione, ad es. in proporzioni 2-a-1.
• Addestrare solo sul training set e, ogni tanto, valutare l'errore sui singoli esempi del set di validazione, ad es. ogni 5 epoche.
• Arrestare l'addestramento non appena l'errore sul set di validazione sia diventato più alto rispetto al controllo precedente.
• Usare i pesi della rete al passo precedente come risultato dell'addestramento.

''Early Stopping – But When?''—Lutz Prechelt

La validazione incrociata è un'alternativa applicabile a scenari non basati su serie temporali. Essa prevede la suddivisione in più partizioni dei dati del training set e un insieme di convalida – invece di una singola partizione in un training set e un insieme di convalida. Pur essendo semplice, nella pratica la procedura è complicata dal fatto che l'errore di convalida può variare molto durante l'addestramento, producendo molteplici minimi locali. Questa complicazione ha portato alla creazione di numerose regole ad hoc per decidere quando l'overfitting è realmente iniziato.

Voci correlate

• Overfitting
• Errore di generalizzazione
• Regolarizzazione (matematica)
• Teoria dell'apprendimento statistico
• Potenziamento (apprendimento automatico)
• Validazione incrociata, in particolare utilizzando un insieme di convalida
• Reti neurali artificiali