Wymiar Wapnika-Czerwonienkisa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Wymiar Wapnika-Czerwonienkisa (wymiar VC, ang. VC dimension) – 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[edytuj | edytuj kod]

Zbiór przykładów X(o n elementach) jest rozbijany przez przestrzeń hipotez H, jeśli dla dowolnej (z 2^n możliwych) klasyfikacji elementów zbioru istnieje hipoteza h \in H, dla której (h(x_1), \ldots ,h(x_n))) 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.

VC1.svg VC2.svg VC3.svg VC4.svg
3 punkty rozbijane 4 punkty nierozbijalne

Przykłady[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

  • Martin Anthony, Norman Biggs, Computational Learning Theory, Cambridge University Press 1992.