Convalida incrociata

Confronto dell'accuratezza stimata tramite convalida incrociata e percentuale di falsi negativi (sovrastima) per cinque modelli di classificazione. La grandezza delle sfere rappresenta la deviazione standard dell'accuratezza stimata con la convalida incrociata (10-fold).

La convalida incrociata (cross-validation in inglese), detta anche out-of-sample testing, è una famiglia di tecniche statistiche di convalida di modelli utili a valutare quanto i risultati di un'analisi statistica possano essere generalizzati su un insieme di dati indipendente. Essa include metodi di resampling e sample splitting che usano porzioni differenti dei dati per addestrare e poi testare un modello in diverse iterate. Viene spesso utilizzata in casi in cui l'obiettivo è la predizione e si vuole stimare empiricamente l'accuratezza di un modello predittivo. Si può usare anche per valutare la qualità di un modello appreso e la stabilità dei suoi parametri.

In un problema di predizione, a un modello viene solitamente fornito un insieme di dati noti su cui viene eseguito l'addestramento (training set) e un insieme di dati sconosciuti (o dati visti per la prima volta) rispetto ai quali il modello viene testato (detto validation set o test set). L'obiettivo della convalida incrociata è quello di testare la capacità del modello di prevedere nuovi dati che non sono stati utilizzati nella sua stima, al fine di segnalare problemi come il sovradattamento o il bias di selezione e di fornire una visione d'insieme su come il modello generalizzerà un insieme di dati indipendente (cioè un insieme di dati sconosciuti, ad esempio provenienti da un problema reale).

Un ciclo di convalida incrociata prevede il partizionamento di un campione di dati in sottoinsiemi complementari, l'esecuzione dell'analisi sul training set e la convalida dell'analisi sull'altro sottoinsieme, il validation set. Per ridurre la variabilità, nella maggior parte dei metodi vengono eseguiti più cicli di validazione incrociata utilizzando partizioni diverse e i risultati della validazione vengono combinati (ad esempio mediati) nei vari cicli per fornire una stima delle prestazioni predittive del modello.

In sintesi, la convalida incrociata combina (media) le misure di valutazione delle predizioni per ottenere una stima più accurata delle prestazioni predittive del modello.

Motivazione

Si consideri un modello con uno o più parametri sconosciuti e un insieme di dati a cui il modello può essere adattato (l'insieme di dati di addestramento). Il processo di adattamento ottimizza i parametri del modello per adattarlo il più possibile ai dati di addestramento. Se si estrae un campione indipendente di dati di convalida dalla stessa popolazione dei dati di addestramento, in genere si riscontra che il modello non si adatta ai dati di convalida tanto quanto si adatta ai dati di addestramento. L'entità di questa differenza è probabilmente elevata, specialmente quando la dimensione dell'insieme di dati di addestramento è ridotta o quando il numero di parametri nel modello è elevato. La convalida incrociata è un modo per stimare l'entità di questo effetto.

Esempio: regressione lineare

Nella regressione lineare, si hanno valori di risposta reali $y_{1},\ldots ,y_{n}$ e $n$ vettori $p$-dimensionali di covariate ${\textstyle \mathbf {x} _{1},\ldots ,\mathbf {x} _{n}}$. Le componenti del vettore $\mathbf {x} _{i}$ sono denotate da $x_{i1},\ldots ,x_{ip}$. Se si usano i minimi quadrati per adattare una funzione in forma di iperpiano ${\hat {\mathbf {y} }}=a+{\boldsymbol {\beta }}^{\top }\mathbf {x}$ ai dati $(\mathbf {x} _{i},y_{i})_{1\leq i\leq n}$, allora l'adattamento può essere valutato usando l'errore quadratico medio (MSE). L'MSE per la stima dei valori dei parameteri $a$ e ${\boldsymbol {\beta }}$ sul training set $(\mathbf {x} _{i},y_{i})_{1\leq i\leq n}$ è definito da:

${\begin{aligned}{\text{MSE}}&={\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-{\hat {y}}_{i})^{2}={\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-a-{\boldsymbol {\beta }}^{T}\mathbf {x} _{i})^{2}\\&={\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-a-\beta _{1}x_{i1}-\dots -\beta _{p}x_{ip})^{2}.\end{aligned}}$

Se il modello è specificato correttamente, è possibile dimostrare, sulla base di ipotesi ragionevoli, che il valore atteso dell'MSE per l'insieme di addestramento è $(n-p-1)/(n+p+1)<1$ volte il valore atteso dell'MSE per l'insieme di convalida (valore atteso calcolato sulla base della distribuzione dei training set). Pertanto, un modello adattato e un MSE calcolato sul set di addestramento darà luogo a una valutazione ottimistica di quanto il modello possa adattarsi a un insieme di dati indipendente. Tale stima distorta è chiamata stima dell'adattamento in-sample, mentre la stima della convalida incrociata è una stima out-of-sample.

Poiché nella regressione lineare è possibile calcolare direttamente il fattore $(n-p-1)/(n+p+1)$ con cui l'MSE di addestramento sottostima l'MSE di convalida, supponendo che la specifica del modello sia corretta, si può utilizzare la convalida incrociata per verificare se il modello sia sovradattato, nel qual caso l'MSE sull'insieme di convalida supererà sostanzialmente il suo valore previsto. Nel contesto della regressione lineare, la convalida incrociata è utile anche nella scelta di una funzione di costo regolarizzata ottimale.

Tipologie

Si distinguono due tipologie di convalida incrociata: esaustiva e non esaustiva.

Convalida incrociata esaustiva

I metodi di convalida incrociata esaustiva sono metodi che apprendono e testano sulla base di tutti i modi in cui è possibile suddividere il campione originario in un insieme di addestramento e un insieme di convalida.

Validazione incrociata Leave-p-out

La convalida incrociata Leave-p-out (LpO CV) prevede l'utilizzo di $p$ osservazioni come insieme di validazione e delle osservazioni rimanenti come insieme di addestramento. Questo processo viene ripetuto in tutti i modi possibili per suddividere il campione originario in un insieme di convalida di $p$ osservazioni e un insieme di addestramento.

La convalida incrociata LpO richiede l'addestramento e la validazione del modello $C_{p}^{n}$ volte, dove $n$ è il numero di osservazioni nel campione originario e dove ${\displaystyle C_{p}^{n}}$ è il coefficiente binomiale. Per $p>1$ e per $n$ anche moderatamente grande, la CV LpO può diventare intrattabile dal punto di vista computazionale. Ad esempio, con $n=100$ e $p=30$, $C_{30}^{100}\approx 3\times 10^{25}$.

Una variante della validazione incrociata LpO con $p=2$ nota come convalida incrociata leave-pair-out è stata raccomandata come metodo quasi privo di distorsioni per stimare l'area sotto la curva ROC dei classificatori binari.

Leave-one-out cross-validation

Illustrazione della convalida incrociata leave-one-out (LOOCV) per $n=8$ osservazioni. Vengono addestrati e testati 8 modelli in totale.

La convalida incrociata leave-one-out (LOOCV) costituisce un caso particolare della leave-p-out in cui $p=1$. Il processo somiglia a quello del metodo jackknife, tuttavia con la convalida incrociata si cacola una statistica sui campioni esclusi, mentre con il jackknife la statistica viene calcolata solo su quelli conservati.

la convalida incrociata LOO richiede ha un minor costo computazionale rispetto alla LpO in quanto servono solo $C_{1}^{n}=n$ passate anziché $C_{p}^{n}$. In ogni modo, $n$ passate possono comunque richiedere parecchio tempo di calcolo, nel qual caso altri approcci possono rendersi più appropriati, come la k-fold cross validation.

Convalida incrociata non esaustiva

k-fold cross validation

Diagramma esplicativo della k-fold cross-validation

Fra le più utilizzate, avendo a disposizione un buon numero di campioni, la convalida incrociata cosiddetta k-fold consiste nella suddivisione dell'insieme di dati totale in k parti di uguale numerosità e, a ogni passo, la kª parte dell'insieme di dati viene a essere quella di convalida, mentre la restante parte costituisce sempre l'insieme di addestramento. Così si addestra il modello per ognuna delle k parti, evitando quindi problemi di sovradattamento, ma anche di campionamento asimmetrico (e quindi affetto da distorsione) del campione osservato, tipico della suddivisione dei dati in due sole parti (ossia addestramento/convalida). In altre parole, si suddivide il campione osservato in gruppi di egual numerosità, si esclude iterativamente un gruppo alla volta e si cerca di predirlo coi gruppi non esclusi, al fine di verificare la bontà del modello di predizione utilizzato.

Convalida incrociata annidata

Quando la validazione incrociata viene utilizzata sia per la selezione del miglior insieme di iperparametri sia per la stima dell'errore (e la valutazione della capacità di generalizzazione), è necessaria una validazione incrociata annidata. Esistono molte varianti. Se ne possono distinguere almeno due:

• k*l-fold cross-validation;
• k-fold cross-validation con insiemi di convalida e test.

Misure di valutazione

L'obiettivo della validazione incrociata è stimare il livello previsto di adattamento di un modello a un insieme di dati indipendente dai dati utilizzati per addestrare il modello. Può essere utilizzata per stimare qualsiasi misura quantitativa di adattamento appropriata per i dati e il modello. Ad esempio, per i problemi di classificazione binaria, ogni caso nell'insieme di validazione viene predetto correttamente o in modo errato. In questa situazione, il tasso di errore di classificazione errata può essere utilizzato per misurare l'adattamento, sebbene possano essere utilizzate anche altre misure derivate dalle informazioni (ad esempio, conteggi, frequenza) contenute in una tabella di contingenza o in una matrice di confusione. Quando il valore previsto è distribuito in modo continuo, è possibile utilizzare l'errore quadratico medio, la sua radice quadrata o la deviazione mediana assoluta per riassumere gli errori.

Bibliografia

• E. Alpaydın: Introduction to Machine Learning, 4th edition. ch. 20. The MIT Press. 2020, ISBN 9780262043793
• I. Witten, E. Frank: Data Mining: Practical Machine Learning Tools and Techniques, Morgan Kaufmann
• R. Duda, P. Hart, D. Stork: Pattern Classification, Wiley
• T. Hastie, R. Tibshirani, J. Friedman: The Elements of Statistical Learning, Springer

Voci correlate

• Ricampionamento
• Metodo bootstrap
• Training set
• Ricerca su griglia

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su convalida incrociata

Collegamenti esterni

• (EN) Cross-Validation tutorial by Andrew Moore, Carnegie Mellon University, Stati Uniti, su autonlab.org. URL consultato il 28 ottobre 2009 (archiviato dall'url originale il 16 aprile 2010).