Ik studeer machine learning van Andrew Ng Stanford-lezingen en kwam net de theorie van VC-dimensies tegen. Volgens de lezingen en wat ik begreep, is de definitie van VC-dimensie kan worden gegeven als,
Als je een set van $ n $ punten kunt vinden, zodat deze kan worden verbrijzeld door de classificatie (bijv. classificeer alle mogelijke $ 2 ^ n $ labeling correct) en u kunt geen enkele set van $ n + 1 $ punten vinden die kan worden verbrijzeld (dwz voor elke set van $ n + 1 $ punten is er ten minste één labelvolgorde, zodat de classificator kan niet alle punten correct scheiden), dan is de VC-dimensie $ n $.
Professor nam ook een voorbeeld en legde dit mooi uit. Dat is:
Let,
$ H = \ {{set \ of \ linear \ classifiers \ in \ 2 \ Dimensions \}} $
Dan kunnen 3 punten correct worden geclassificeerd door $ H $ met scheidende hypervlakken zoals weergegeven in de volgende afbeelding.
En daarom is de VC-dimensie van $ H $ 3. Omdat voor elke 4 punten in het 2D-vlak een lineaire classificatie kan niet alle combinaties van de punten verbrijzelen.
Voor deze set punten, er is geen scheidend hypervlak dat kan worden getekend om deze set te classificeren. Dus de VC-dimensie is 3.
Ik krijg het idee tot hier. Maar wat als we “het type patroon volgen?
Of het patroon waarbij drie punten op elkaar samenvallen, ook hier kunnen we geen scheiding maken tussen drie punten. Maar toch wordt met dit patroon geen rekening gehouden in de definitie van de VC-dimensie. Waarom? hetzelfde punt wordt ook besproken in de lezingen die ik “bekijk Hier om 16:24 maar de professor noemt de exacte reden hierachter niet.
Elk intuïtief voorbeeld van uitleg wordt gewaardeerd. Bedankt
Reacties
- afkomstig van datascience.stackexchange.com/a/16146/23305
Answer
De definitie van VC-dimensie is: if er bestaat een set van n punten die kunnen worden verbroken door de classifier en er is geen set van n + 1 punten die kunnen worden verbroken door de classificator, dan is de VC-dimensie van de classifier n.
De definitie zegt niet: als elke set van n punten kan worden verbroken door de classificator. ..
Als de VC-dimensie van een classificatie 3 is, hoeft deze niet alle mogelijke arrangementen van 3 punten.
Als van alle arrangementen van 3 punten ten minste één een dergelijke opstelling die kan worden verbrijzeld door de classificator, en geen 4 punten kan vinden die kunnen worden verbrijzeld, dan is VC-dimensie 3.
Opmerkingen
- Dan in dit geval kunnen we ten minste één patroon van een willekeurig aantal punten krijgen dat kan worden geclassificeerd met een rechte lijn. Denk bijvoorbeeld aan 4 punten. Twee rode punten aan de linkerkant en twee blauwe punten aan de rechterkant zouden het mogelijk maken om te classificeren, en VC-dimensie zou 4 zijn. Dus waarom zou dit niet worden overwogen?
- Geclassificeerd – ja. Verbroken – nee
- Dus wat is de betekenis van een arrangement van punten verbrijzelen? Ik ' ben hier echt in de war. Bedankt
- Een rangschikking van punten kan worden verbroken als een subset van deze rangschikking kan worden geïsoleerd en in één klasse kan worden ondergebracht. Stel dat u wilt testen of een bepaalde rangschikking (niet alle mogelijke rangschikkingen, maar slechts één bepaalde rangschikking) van n punten kan worden verbroken door een bepaald type classificaties. Vervolgens test u eerst of een enkel punt kan worden geïsoleerd. Als er dan 2 punten kunnen worden geïsoleerd, dan 3 punten, enz., Tot n-1 punten van die specifieke opstelling. Zie hier en.wikipedia.org/wiki/Shattered_set
- Figuur met 8 subplots is een zeer goede illustratie van wat verbrijzelt. Hier heb je 3 punten, 2 klassen, dus 2 ^ 3 = 8 mogelijke labels van deze 3 punten. Alle 8 labels kunnen worden aangebracht en geïsoleerd met een lijn, daarom kan deze set worden verbrijzeld door een lijn. De figuur met 4 punten: het heeft een aantal labels die kunnen worden geïsoleerd met een lijn (bijvoorbeeld twee links zijn rood, twee rechts zijn blauw), maar heeft ook een label dat niet kan worden geïsoleerd met een lijn (zoals in de figuur: bovenste en onder blauw; links en rechts zijn links). Omdat het een label heeft dat niet kan worden geïsoleerd met een lijn, is deze set niet verbrijzeld.
Antwoord
De punten moeten voldoen aan de algemene voorwaarden voordat ze in aanmerking komen voor VC-dimensie. 