Wymiar Wapnika-Czerwonienkisa: Różnice pomiędzy wersjami
utworzenie artykułu |
(Brak różnic)
|
Wersja z 14:23, 7 gru 2013
Wymiar Vapnika-Chervonenkisa (wymiar VC, ang. VC dimension) - podstawowe pojęcie teorii uczenia maszynowego wprowadzone przez Vladimira Vapnika i Aleksieja Chervonenkisa. 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.
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.