Wymiar Wapnika-Czerwonienkisa (wymiar VC, ) – podstawowe pojęcie teorii uczenia maszynowego wprowadzone przez Władimira Wapnika i Aleksieja Czerwonienkisa. Stanowi miarę mocy wyrażania pojęć danej przestrzeni hipotez. Jest on zdefiniowany jako liczność największego zbioru, który jest rozbijany przez przestrzeń hipotez. Fundamentalne twierdzenie teorii uczenia charakteryzuje potencjalnie wyuczalne przestrzenie hipotez jako te o skończonym wymiarze VC.
Rozbijanie Zbiór przykładów (o elementach) jest rozbijany przez przestrzeń hipotez jeśli dla dowolnej (z możliwych) klasyfikacji elementów zbioru istnieje hipoteza dla której jest taką klasyfikacją. Na przykład dla perceptronu każde trzy niewspółliniowe punkty mogą być rozbite (przykłady pozytywne oddzielone od negatywnych prostą), ale nie istnieją cztery punkty, które są rozbijane. Zatem wymiar VC perceptronu wynosi 3.
Plik:VC1.svg Plik:VC2.svg Plik:VC3.svg Plik:VC4.svg 3 punkty rozbijane 4 punkty nierozbijalne
Przykłady Dla skończonej przestrzeni hipotez wymiar VC nie przekracza logarytmu z liczności. Przestrzeń przedziałów ma wymiar 2. Przestrzeń sum skończonej liczby rozłącznych przedziałów ma nieskończony wymiar VC.
Bibliografia Martin Anthony, Norman Biggs, Computational Learning Theory, Cambridge University Press, 1992.
Kategoria:Klasyfikacja statystyczna Kategoria:Uczenie maszynowe