Nella teoria di Vapnik-Chervonenkis, la dimensione di Vapnik-Chervonenkis (VC) è una misura della dimensione (capacità, complessità, potere espressivo, ricchezza o flessibilità) di una classe di insiemi. La nozione può essere estesa a classi di funzioni binarie. Essa è definita come la cardinalità del più grande insieme di punti per il quale tutte le possibili etichettature binarie possono essere realizzate da una funzione nella classe. Si dice anche che che la classe di funzioni frantuma (shatters) l'insieme e che l'insieme è completamente separabile dalla classe. La misura è stata originariamente definita da Vladimir Vapnik e Alexey Chervonenkis.

In termini informali, la capacità di un modello di classificazione è correlata alla sua complessità. Ad esempio, si consideri un classificatore ottenuto applicando una soglia a un polinomio di grado elevato: dato un punto, se il polinomio è valutato sopra lo zero, il punto viene classificato come positivo, altrimenti come negativo. Un polinomio di grado elevato può essere ondulato, in modo da adattarsi bene a un dato insieme di esempi di addestramento. Un tale polinomio avrà un'elevata capacità. Un classificatore alternativo molto più semplice si ottiene applicando una soglia a una funzione lineare. Questa funzione potrebbe non adattarsi bene all'insieme di addestramento, perché ha una bassa capacità. Questa nozione di capacità verrà definita più rigorosamente nel seguito.

Definizioni Dimensione VC di un modello di classificazione Sia una famiglia di insiemi (raccolta o collezione di insiemi) e un insieme. La loro intersezione è definita come la seguente famiglia di insiemi:

di solito e ciascun sono sottoinsiemi di un grande "universo" di possibilità nel quale si realizza l'intersezione.

Si dice che un insieme è frantumato (shattered, o separato completamente) da se , ossia l'insieme delle intersezioni, contiene (quindi è uguale a) tutti i sottoinsiemi di . Per insiemi finiti questo è equivalente a

La dimensione VC di è la cardinalità dell'insieme più grande che possa essere frantumato da . Se possono essere frantumati insiemi arbitrariamente grandi, la dimensione VC di sarà .

Dimensione VC di una famiglia di insiemi Dato un modello di classificazione binaria con un dato vettore di parametri , si dice che frantumi un insieme di punti posizionati arbitrariamente se, per ogni assegnazione di etichette a quei punti, esiste un tale che il modello non commette errori nel valutare quell'insieme di punti (dati).

La dimensione VC di un modello è il numero massimo di punti che possono essere disposti in modo che li frantumi (separi completamente). Più formalmente, è il numero cardinale massimo tale che esista un insieme di punti posizionati arbitrariamente di cardinalità che possa essere separato completamente da .

Esempi è un classificatore costante (senza parametri); la sua dimensione VC è 0 dato che non può separare completamente nemmeno un singolo punto. In generale, la dimensione VC di un modello di classificazione finito, che può restituire al più classificatori diversi, è al più limite superiore sulla dimensione VC; il lemma di Sauer–Shelah fornisce un limite inferiore sulla dimensione). è un classificatore con singola soglia parametrica su numeri reali; ossia, per una certa soglia , il classificatore restituisce 1 se il numero in input è più grande di e 0 altrimenti. La dimensione VC di è 1 poiché: (a) può separare completamente un singolo punto. Per ogni punto , un classificatore lo etichetta con 0 se e con 1 se . (b) non può separare completamente tutti gli insiemi di due punti. Per ogni insieme di due numeri, se il più piccolo è etichettato con 1, allora anche il più grande lo sarà necessariamente, quindi non tutte le etichettature sono possibili. è un classificatore con singolo intervallo parametrico su numeri reali; ossia per un certo parametro , il classificatore restituisce 1 se il numero in input è nell'intervallo e 0 altrimenti. La dimensione VC di è 2 poiché: (a) può separare completamente alcuni insiemi di due punti. Ad es., per ogni insieme , un classificatore lo etichetta con (0,0) se o se , con (1,0) se , con (1,1) se e con (0,1) se . (b) non può separare completamente un qualsiasi insieme di tre punti. Per ogni insieme di tre numeri, se il più piccolo e il più grande sono etichettati con 1, anche quello intermedio avrà la stessa etichetta, quindi non tutte le etichettature sono possibili. è una linea retta intesa come modello di classificazione per punti su un piano bidimensionale (modello usato dal percettrone). Le retta dovrebbe separare i punti positivi da quelli negativi. Esistono insiemi di 3 punti che possono essere separati completamente usando tale modello (qualsiasi terna di punti non collineari può esserlo). Tuttavia, nessun insieme di 4 punti può essere separato completamente: per il teorema di Radon, qualsiasi quaterna di punti può essere partizionata in due sottoinsiemi con inviluppi convessi che si intersechino, per cui non è possibile separare uno di tali due sottoinsiemi dall'altro. Pertanto, la dimensione VC di tale specifico classifier is 3. È importante ricordare che mente si può scegliere qualsiasi disposizione di punti, questa non può essere cambiata nel tentativo di separare completamente per qualche assegnazione di etichette. Si noti che in figura solo 3 delle 23 = 8 assegnazioni possibili sono per i tre punti. è un classificatore sinusoidale a singolo parametro, i.e., per un dato valore del parametro , il classificatore restituisce 1 se per il numero in input risulta e 0 altrimenti. La dimensione VC di è infinita, dato che può separare completamente qualunque sottoinsieme finito dell'insieme .

3 punti completamente separati 4 punti non separabili

Usi Nella teoria dell'apprendimento statistico La dimensione VC permette di determinare un limite superiore probabilistico per l'errore di test di un modello di classificazione. Vapnik ha dimostrato che la probabilità che l'errore di test (ovvero il rischio basato sulla funzione di loss 0-1) si allontani da un limite superiore (su dati estratti i.i.d. dalla stessa distribuzione dell'insieme di addestramento) è data da:

dove è la dimensione VC del modello di classificazione, , e è la dimensione dell'insieme di addestramento (restrizione: questa formula è valida per . Quando è più grande, l'errore di test potrebbe essere molto più alto dell'errore di addestramento. Ciò a causa di sovradattamento).

La dimensione VC appare anche nei limiti relativi alla complessità del campione. Uno spazio di funzioni binarie con dimensione VC pari a può essere appreso con un numero di esempi pari a:

dove è l'errore di apprendimento e è la probabilità di fallimento. Pertanto, la complessità del campione è una funzione lineare della dimensione VC dello spazio delle ipotesi.

Esempi di classi VC Dimensione VC di un classificatore da boosting Si supponga di avere una classe-base di classificatori semplici, la cui dimensione VC è .

Si può costruire un classificatore più potente combinando diversi classificatori contenuti in ; questa tecnica è chiamata boosting. Formalmente, dati classificatori e un vettore-pesi , si può definire il seguente classificatore:

La dimensione VC dell'insieme di tutti questi classificatori (per tutte le selezioni di classificatori in e vettore-pesi in ), assumendo che , è al massimo:

Dimensione VC di una rete neurale Una rete neurale è descritta da un grafo aciclico orientato G (V,E), dove:

V è l'insieme dei nodi. Ogni nodo è una semplice cella di calcolo. E è l'insieme degli archi. Ogni arco ha un peso. L'input alla rete è rappresentato dalle sorgenti del grafo, ovvero i nodi senza archi in entrata. L'output della rete è rappresentato dai sink del grafo, ovvero i nodi senza archi in uscita. Ogni nodo intermedio riceve come input una somma ponderata degli output dei nodi sui suoi archi in entrata, dati i pesi sugli archi. Ogni nodo intermedio emette una certa funzione crescente del suo input, come la funzione segno o la funzione sigmoide. Questa funzione è chiamata funzione di attivazione.

La dimensione VC di una rete neurale è limitata come segue:

Se la funzione di attivazione è la funzione segno e i pesi sono generici, allora la dimensione VC è al massimo . Se la funzione di attivazione è la funzione sigmoide e i pesi sono generici, allora la dimensione VC è almeno e al massimo . Se i pesi provengono da una famiglia finita (ad esempio i pesi sono numeri reali rappresentabili con al massimo 32 bit in un calcolatore), allora, per entrambe le funzioni di attivazione, la dimensione VC è al massimo .

Note

Bibliografia

Altri progetti

Categoria:Apprendimento automatico