Studiuję uczenie maszynowe z wykładów Andrew Ng Stanforda i właśnie natknąłem się na teorię wymiarów VC. Zgodnie z wykładami i tym, co zrozumiałem, definicja wymiaru VC można podać jako,
Jeśli możesz znaleźć zbiór $ n $ punktów, aby mógł zostać rozbity przez klasyfikator (tj. sklasyfikuj poprawnie wszystkie możliwe $ 2 ^ n $ etykietowania) i nie możesz znaleźć żadnego zestawu $ n + 1 $ punktów, które można rozbić (tj. dla dowolnego zestawu $ n + 1 $ punktów istnieje co najmniej jedna kolejność etykietowania, więc klasyfikator nie może poprawnie oddzielić wszystkich punktów), wówczas wymiar VC wynosi $ n $.
Również profesor wziął przykład i ładnie to wyjaśnił. To jest:
Niech,
$ H = \ {{set \ of \ linear \ classifiers \ in \ 2 \ Dimensions \}} $
Wtedy dowolne 3 punkty mogą zostać poprawnie sklasyfikowane przez $ H $ z oddzielającą hiperpłaszczyzną, jak pokazano na poniższym rysunku.
I dlatego wymiar VC $ H $ wynosi 3. Ponieważ dla dowolnych 4 punktów w płaszczyźnie 2D, klasyfikator liniowy może nie rozbijaj wszystkich kombinacji punktów. Na przykład
Dla ten zbiór punktów, nie można narysować oddzielającej hiperpłaszczyzny w celu sklasyfikowania tego zbioru. Zatem wymiar VC wynosi 3.
Do tej pory mam pomysł. Ale co, jeśli „śledzimy typ wzorca?
Lub wzór, w którym trzy punkty pokrywają się ze sobą, tutaj również nie możemy narysować oddzielającej hiperpłaszczyzny między 3 punktami. Ale nadal ten wzór nie jest uwzględniany w definicji wymiaru VC. Dlaczego? Ten sam punkt jest również omawiany w wykładach, które oglądam Tutaj o 16:24 , ale profesor nie wymienia dokładnego powodu tego.
Doceniony zostanie każdy intuicyjny przykład wyjaśnienia. Dzięki
Komentarze
- pobrane z datascience.stackexchange.com/a/16146/23305
Odpowiedź
Definicja wymiaru VC to: if istnieje zbiór n punktów, które mogą zostać zniszczone przez klasyfikator i nie ma zbiór n + 1 punktów, które mogą zostać zniszczone przez klasyfikator, wtedy wymiar VC klasyfikatora wynosi n.
Definicja nie mówi: jeśli jakikolwiek zbiór n punktów może zostać zniszczony przez klasyfikator. ..
Jeśli wymiar VC klasyfikatora wynosi 3, nie musi on niszczyć wszystkich możliwych układy po 3 punkty.
Jeśli ze wszystkich układów po 3 punkty można znaleźć co najmniej jeden taki układ, który może zostać zniszczony przez klasyfikator i nie może znaleźć 4 punktów, które można rozbić, wtedy wymiar VC wynosi 3.
Komentarze
- Następnie w tym przypadku możemy uzyskać przynajmniej jeden wzór z dowolnej liczby punktów, które można sklasyfikować linią prostą. Na przykład pomyśl o 4 punktach. Dwa czerwone punkty po lewej stronie i dwa niebieskie punkty po prawej stronie pozwolą na klasyfikację, a VC wynosiłby 4. Dlaczego więc tego nie wziąć pod uwagę?
- Sklasyfikowane – tak. Zdruzgotane – nie
- Jakie jest więc znaczenie zburzyć układ punktów? ' Jestem tu naprawdę zdezorientowany. Dzięki
- Układ punktów może zostać zniszczony, jeśli jakikolwiek podzbiór tego układu może zostać wyizolowany i umieszczony w jednej klasie. Powiedzmy, że chcesz sprawdzić, czy pewien układ (nie wszystkie możliwe układy, ale tylko jeden konkretny układ) n punktów może zostać zniszczony przez określony typ klasyfikatorów. Następnie najpierw sprawdzasz, czy można wyodrębnić pojedynczy punkt. Następnie, jeśli dowolne 2 punkty można wyodrębnić, to jeśli jakiekolwiek 3 punkty, itd., Aż do dowolnych n-1 punktów tego konkretnego układu. Zobacz tutaj en.wikipedia.org/wiki/Shattered_set
- Rysunek z 8 pobocznymi wykresami jest bardzo dobrą ilustracją tego, co się rozpada. Tutaj masz 3 punkty, 2 klasy, więc 2 ^ 3 = 8 możliwych oznaczeń tych 3 punktów. Wszystkie 8 etykiet można wykonać i odizolować za pomocą linii, dzięki czemu ten zestaw może zostać zniszczony linią. Rysunek z 4 punktami: ma kilka etykiet, które można wyodrębnić linią (powiedzmy, dwie lewe są czerwone, dwie prawe niebieskie), ale ma również etykietę, której nie można oddzielić linią (jak na rysunku: górna i dolny niebieski; lewy i prawy są lewe). Ponieważ ma etykietę, której nie można odizolować linią, ten zestaw nie jest rozbity.
Odpowiedź
Punkty powinny odpowiadać punktom w ogólnym stanie przed rozważeniem wymiaru VC. 