Studiez învățarea automată din prelegerile Andrew Ng Stanford și tocmai am întâlnit teoria dimensiunilor VC. Conform prelegerilor și a ceea ce am înțeles, definiția dimensiunea VC poate fi dată ca,
Dacă puteți găsi un set de $ n $ puncte, astfel încât să poată fi spulberat de clasificator (adică clasificați corect toate etichetările posibile de $ 2 ^ n $) și nu puteți găsi niciun set de $ n + 1 $ puncte care să poată fi spulberat (adică pentru orice set de $ n + 1 $ puncte există cel puțin o ordine de etichetare astfel încât clasificatorul nu poate separa corect toate punctele), atunci dimensiunea VC este $ n $.
De asemenea, profesorul a luat un exemplu și a explicat acest lucru frumos. Care este:
Să,
$ H = \ {{set \ of \ linear \ classifiers \ in \ 2 \ Dimensions \}} $
Apoi orice 3 puncte pot să fie clasificat corect cu $ H $ cu hiperplanul de separare așa cum se arată în figura următoare.
Și de aceea dimensiunea VC de $ H $ este 3. Deoarece pentru orice 4 puncte în plan 2D, un clasificator liniar poate nu distruge toate combinațiile de puncte. De exemplu,
Pentru acest set de puncte, nu există un plan hiper de separare care poate fi trasat pentru a clasifica acest set. Deci dimensiunea VC este 3.
Am ideea până aici. Dar dacă „urmărim tipul de model?
Sau modelul în care trei puncte coincid unul pe celălalt, nici aici nu putem desena hiperplanul de separare între 3 puncte. Dar totuși acest model nu este luat în considerare în definiția dimensiunii VC. De ce? același punct este discutat și despre prelegerile pe care le urmăresc Aici la 16:24 , dar profesorul nu menționează motivul exact din spatele acestui lucru.
Orice exemplu intuitiv de explicație va fi apreciat. Mulțumiri
Comentarii
- preluate de la datascience.stackexchange.com/a/16146/23305
Răspuns
Definiția dimensiunii VC este: if există un set de n puncte care pot fi spulberate de clasificator și nu există set de n + 1 puncte care pot fi spulberate de clasificator, atunci dimensiunea VC a clasificatorului este n.
Definiția nu spune: dacă orice set de n puncte poate fi spulberat de clasificator. ..
Dacă dimensiunea VC a unui clasificator este 3, nu trebuie să distrugă tot posibilul aranjamente de 3 puncte.
Dacă din toate aranjamentele de 3 puncte puteți găsi cel puțin un un astfel de aranjament care poate fi spulberat de clasificator și nu poate găsi 4 puncte care pot fi spulberate, atunci dimensiunea VC este 3.
Comentarii
- Apoi în acest caz putem obține cel puțin un model din orice număr de puncte care pot fi clasificate după linie dreaptă. De exemplu, gândiți-vă la 4 puncte. Două puncte roșii în partea stângă și două puncte albastre în partea dreaptă ar face posibilă clasificarea, și dimensiunea VC ar fi 4. Deci, de ce nu s-a luat în considerare acest lucru?
- Clasificat – da. Spulberat – nu
- Deci, care este semnificația zdrobind un aranjament de puncte? ' sunt foarte confuz aici. Mulțumiri
- Un aranjament de puncte poate fi spulberat dacă orice subset al acestui aranjament poate fi izolat și pus într-o singură clasă. Spuneți, doriți să testați dacă un anumit aranjament (nu toate aranjamentele posibile, ci doar un anumit aranjament) de n puncte poate fi spulberat de un anumit tip de clasificatori. Apoi, testați mai întâi dacă un singur punct poate fi izolat. Apoi, dacă există 2 puncte care pot fi izolate, atunci dacă există 3 puncte, etc, până la orice puncte n-1 din acel aranjament particular. Vedeți aici en.wikipedia.org/wiki/Shattered_set
- Figura cu 8 subploturi este o ilustrare foarte bună a ceea ce spulberă. Aici aveți 3 puncte, 2 clase, deci 2 ^ 3 = 8 posibile etichetări ale acestor 3 puncte. Toate cele 8 etichetări pot fi făcute și izolate cu o linie, prin urmare acest set poate fi spulberat de o linie. Cifra cu 4 puncte: are câteva etichete care pot fi izolate cu o linie (să zicem, două la stânga sunt roșii, două la dreapta sunt albastre), dar are și o etichetare care nu poate fi izolată cu o linie (ca în Figura: superior și albastru inferior; stânga și dreapta sunt stânga). Deoarece are o etichetare care nu poate fi izolată cu o linie, acest set nu este spart.
Răspuns
Punctele trebuie să îndeplinească puncte în condiții generale înainte de a lua în considerare dimensiunea VC. 