Sto studiando machine learning dalle lezioni di Andrew Ng Stanford e mi sono appena imbattuto nella teoria delle dimensioni VC. Secondo le lezioni e ciò che ho capito, la definizione della dimensione VC può essere data come,
Se riesci a trovare un insieme di $ n $ punti, in modo che possa essere frantumato dal classificatore (cioè classificare correttamente tutte le possibili etichette $ 2 ^ n $) e non riesci a trovare alcun insieme di $ n + 1 $ punti che possa essere frantumato (cioè per ogni insieme di $ n + 1 $ punti cè almeno un ordine di etichettatura in modo che il classificatore non può separare correttamente tutti i punti), quindi la dimensione VC è $ n $.
Anche il professore ha preso un esempio e lo ha spiegato bene. Che è:
Sia,
$ H = \ {{set \ of \ linear \ classifiers \ in \ 2 \ Dimensions \}} $
Quindi 3 punti qualsiasi possono essere classificato correttamente da $ H $ separando liperpiano come mostrato nella figura seguente.
Ed è per questo che la dimensione VC di $ H $ è 3. Perché per qualsiasi 4 punti nel piano 2D, un classificatore lineare può Non frantumare tutte le combinazioni dei punti. Ad esempio,
per questo insieme di punti, non è possibile disegnare un iperpiano di separazione per classificare questo insieme. Quindi la dimensione VC è 3.
Mi è venuta lidea fino a qui. Ma cosa succede se “abbiamo il seguente tipo di pattern?
O il modello in cui tre punti coincidono luno sullaltro, anche qui non possiamo disegnare un iperpiano di separazione tra 3 punti. Ma ancora questo modello non è considerato nella definizione della dimensione VC. Perché? Lo stesso punto viene discusso anche delle lezioni che sto guardando Qui alle 16:24 ma il professore non menziona il motivo esatto alla base di questo.
Qualsiasi esempio intuitivo di spiegazione sarà apprezzato. Grazie
Commenti
- tratto da datascience.stackexchange.com/a/16146/23305
Risposta
La definizione di dimensione VC è: if esiste un insieme di n punti che possono essere distrutti dal classificatore e non cè insieme di n + 1 punti che possono essere frantumati dal classificatore, quindi la dimensione VC del classificatore è n.
La definizione non dice: se qualsiasi insieme di n punti può essere frantumato dal classificatore. ..
Se la dimensione del VC di un classificatore è 3, non deve distruggere tutto il possibile arrangiamenti di 3 punti.
Se di tutti gli arrangiamenti di 3 punti puoi trovare almeno un tale disposizione che può essere distrutta dal classificatore e non riesce a trovare 4 punti che possono essere frantumati, la dimensione VC è 3.
Commenti
- Quindi in questo caso possiamo ottenere almeno un modello di un numero qualsiasi di punti che possono essere classificati in linea retta. Ad esempio, pensa a 4 punti. Due punti rossi a sinistra e due punti blu a destra consentirebbero di classificare, e la dimensione VC sarebbe 4. Allora perché non tenerne conto?
- Classificato – sì. In frantumi – no
- Allora qual è il significato di frantumare una disposizione di punti? ' sono davvero confuso qui. Grazie
- Una disposizione di punti può essere frantumata se qualsiasi sottoinsieme di questa disposizione può essere isolata e inserita in una classe. Supponiamo di voler verificare se una certa disposizione (non tutte le possibili disposizioni ma solo una particolare disposizione) di n punti può essere distrutta da un certo tipo di classificatori. Quindi si verifica prima se un singolo punto può essere isolato. Quindi, se è possibile isolare 2 punti qualsiasi, quindi 3 punti qualsiasi, ecc., Fino a qualsiasi n-1 punti di quella particolare disposizione. Vedi qui en.wikipedia.org/wiki/Shattered_set
- La figura con 8 sottotrame è un ottimo esempio di ciò che è sconvolgente. Qui hai 3 punti, 2 classi, quindi 2 ^ 3 = 8 possibili etichettature di questi 3 punti. Tutte le 8 etichettature possono essere fatte e isolate con una linea, quindi questo set può essere spezzato da una linea. La figura con 4 punti: ha alcune etichette che possono essere isolate con una linea (diciamo, due a sinistra sono rosse, due a destra sono blu) ma ha anche unetichettatura che non può essere isolata con una linea (come nella figura: superiore e blu inferiore; sinistra e destra sono sinistra). Poiché ha unetichettatura che non può essere isolata con una linea, questo set non viene frantumato.
Risposta
I punti devono soddisfare i punti in condizioni generali prima di prendere in considerazione la dimensione VC. 