Nell'ambito della teoria dell'apprendimento computazionale, la teoria di Vapnik-Červonenkis (nota anche come teoria VC) è stata sviluppata fra il 1960 e il 1990 da Vladimir Vapnik e Aleksej Červonenkis per spiegare il processo di apprendimento automatico da un punto di vista statistico.
Introduzione La teoria VC copre almeno quattro parti (come spiegato in The Nature of Statistical Learning Theory):
Teoria della coerenza statistica dei processi di apprendimento Quali sono le condizioni (necessarie e sufficienti) per la coerenza di un processo di apprendimento basato sul principio di minimizzazione del rischio empirico? Teoria non asintotica della velocità di convergenza dei processi di apprendimento Quanto è veloce il tasso di convergenza del processo di apprendimento? Teoria del controllo della capacità di generalizzazione dei processi di apprendimento Come si può controllare il tasso di convergenza (la capacità di generalizzare) del processo di apprendimento? Teoria della costruzione di macchine per l'apprendimento Come si possono costruire algoritmi in grado di controllare la capacità di generalizzazione?
La teoria VC costituisce un filone importante della teoria dell'apprendimento statistico. Una delle sue principali applicazioni nella teoria dell'apprendimento statistico è quella di fornire condizioni di generalizzazione per gli algoritmi di apprendimento. Da questo punto di vista, la teoria VC è correlata al framework teorico basato sulla stabilità, che rappresenta un approccio alternativo per caratterizzare la generalizzazione.
Inoltre, la teoria VC e la dimensione VC sono fondamentali nella teoria dei processi empirici, nel caso di processi indicizzati da classi VC. Probabilmente questi costituiscono le applicazioni più importanti della teoria VC e sono impiegate nelle dimostrazioni riguardanti le capacità di generalizzazione degli algoritmi di apprendimento. Sono state introdotte diverse tecniche ampiamente utilizzate nell'ambito dei processi empirici e della teoria VC.
Disugualianza VC Si considera un'impostazione comune nell'apprendimento automatico. Sia uno spazio di feature e . Una funzione è detta classificatore (binario). Dato un insieme di classificatori. Si definisce il coefficiente di frammentazione (shattering):
detto anche funzione di crescita. Si noti che esiste una corrispondenza biunivoca tra ciascuna delle funzioni in e l'insieme su cui la funzione vale 1. Si può quindi definire come l'insieme dei sottoinsiemi ottenuti dalla mappatura sopra indicata per ogni . Pertanto, il coefficiente di frammentazione è precisamente
.
Questa equivalenza, insieme al lemma di Sauer, implica che sarà polinomiale in , per sufficientemente grande, a condizione che l'insieme abbia un indice VC finito.
Sia un campione di esempi osservati. Si assume che i dati siano data generati da una distribuzione sconosciuta . Si definisce come la loss 0/1 attesa. Naturalmente dato che, in generale, è sconosciuta, non si ha accesso nemmeno a . Tuttavia si può certamente valutare il rischio empirico, dato da:
.
Quindi si dimostra il teorema che segue.
Teorema (Disugualianza VC) Per la classificazione binaria e la funzione di perdita 0/1 abbiamo i seguenti limiti di generalizzazione:
.
In altre parole, la disuguaglianza VC afferma che all'aumentare del campione, se ha una dimensione VC finita, il rischio empirico 0/1 diventa un buon indicatore del rischio 0/1 atteso. Si noti che entrambe le parti destre delle due disuguaglianze convergeranno verso 0, a condizione che cresca polinomialmente in .
Per le dimostrazioni si può consultare .
Note
Bibliografia
Categoria:Apprendimento automatico Categoria:Statistica