11 · Prawa i prawdy · 4 min czytania · aktualizacja
Czym jest wymiar VC i co mówi o generalizacji modelu?
W skrócie
Wymiar VC to największa liczba punktów, którym rodzina modeli potrafi nadać dowolne etykiety. Im jest większy, tym więcej danych trzeba do pewnej generalizacji.
Co to jest
Wymiar VC rodziny klasyfikatorów to największa liczba punktów, które ta rodzina potrafi rozbić (shatter), czyli rozdzielić zgodnie z każdym z 2ⁿ możliwych przypisań etykiet. Pojęcie wprowadzili Władimir Vapnik i Aleksiej Czerwonenkis w 1971 roku, dowodząc, że skończony wymiar VC gwarantuje zbieżność błędu treningowego do błędu prawdziwego.
Przykład: prosta na płaszczyźnie. Trzy punkty niewspółliniowe da się rozdzielić prostą przy każdym z 8 układów etykiet. Czterech punktów — już nie zawsze: układ „na krzyż” (XOR) jest nieosiągalny. Wymiar VC prostych na płaszczyźnie wynosi więc 3. Ogólnie dla hiperpłaszczyzn w d wymiarach to d + 1.
Wymiar VC mierzy pojemność modelu w najgorszym przypadku: ile przypadkowych wzorców etykiet model potrafi „zapamiętać”. Nie liczy parametrów, tylko elastyczność.
Mechanizm — dlaczego tak działa
Dla jednego ustalonego klasyfikatora nierówność Hoeffdinga mówi, że błąd na n przykładach szybko zbliża się do błędu prawdziwego. Problem: model wybieramy spośród nieskończenie wielu kandydatów, a im więcej kandydatów, tym łatwiej trafić na takiego, który przypadkiem dobrze wygląda na treningu.
Vapnik i Czerwonenkis zauważyli, że na skończonym zbiorze n punktów nieskończona rodzina zachowuje się jak skończona — liczy się tylko, ile różnych podziałów potrafi wytworzyć. Jeśli wymiar VC to h, liczba tych podziałów rośnie nie jak 2ⁿ, lecz wielomianowo, jak n^h (lemat Sauera–Shelaha). Wielomian przegrywa z wykładniczo malejącym ogonem Hoeffdinga, więc dla dużych n błąd treningowy wiarygodnie przybliża prawdziwy.
Klasyczna granica Vapnika mówi, że z prawdopodobieństwem 1 − δ: błąd prawdziwy ≤ błąd treningowy + √[(h·(ln(2n/h) + 1) + ln(4/δ)) / n]. Wniosek jakościowy: potrzebna liczba przykładów rośnie mniej więcej proporcjonalnie do h.
Ograniczenia są duże. Granice VC są pesymistyczne, bo dotyczą najgorszego rozkładu danych. Dla głębokich sieci wymiar VC jest ogromny, a mimo to generalizują one dobrze — Zhang i in. (2017) pokazali, że te same sieci potrafią zapamiętać zupełnie losowe etykiety. Teoria VC nie tłumaczy więc, dlaczego sieci generalizują; to otwarty problem, który próbują rozwiązać granice oparte na normach, marginesie i stabilności.
Na przykładzie
Sprawdziliśmy rozbijanie programowaniem liniowym (czy istnieje prosta rozdzielająca). Trzy punkty (0,0), (1,0), (0,1): wszystkie 8 układów etykiet jest liniowo separowalnych. Cztery wierzchołki kwadratu: separowalnych jest 14 z 16 — brakuje dwóch układów XOR. Cztery punkty, z których jeden leży wewnątrz trójkąta pozostałych: też 14 z 16 — nie da się oddzielić punktu środkowego od trzech zewnętrznych. Żaden układ czterech punktów nie daje 16 z 16, stąd h = 3.
Ile to znaczy w praktyce? Dla h = 3 i δ = 0,05 granica Vapnika daje zapas 0,164 przy 1000 przykładów, 0,058 przy 10 000 i 0,020 przy 100 000. Dla modelu o h = 100 te same liczby to 0,64, 0,25 i 0,093 — przy tysiącu przykładów granica jest bezużyteczna, choć w praktyce taki model często generalizuje dobrze.
W praktyce
- Wymiar VC rzadko liczy się w praktyce; służy jako język do myślenia o pojemności modelu.
- Klasyfikator liniowy z d cechami: h = d + 1. Dla SVM z jądrem RBF wymiar VC jest nieskończony, a generalizację ratuje margines (
C,gamma). - Reguła kciuka „około 10 przykładów na stopień swobody” wywodzi się z tego sposobu myślenia, ale nie jest twierdzeniem.
- O realnej generalizacji rozstrzyga walidacja (
cross_val_score), nie granica VC. - Test losowych etykiet: jeśli model osiąga 100% na treningu także po przetasowaniu
y, ma pojemność wystarczającą do zapamiętania danych.
Najczęstsze pytania
- Czy wymiar VC to liczba parametrów?
- Nie zawsze. Dla modeli liniowych pokrywa się z liczbą parametrów, ale klasyfikator sign(sin(ωx)) ma jeden parametr i nieskończony wymiar VC.
- Dlaczego sieci neuronowe generalizują mimo ogromnego wymiaru VC?
- Bo granica VC dotyczy najgorszego przypadku, a algorytm uczenia (gradient prosty) i struktura danych wybierają spośród możliwych sieci rozwiązania o specyficznych, „prostych” własnościach. Pełne wyjaśnienie wciąż jest przedmiotem badań.
- Do czego wymiar VC przydaje się dziś?
- Do zrozumienia, dlaczego uczenie w ogóle jest możliwe i dlaczego pojemność trzeba równoważyć ilością danych. To fundament teorii PAC i zasada stojąca za regularyzacją i SVM.
Źródła
- Vapnik V. N., Chervonenkis A. Ya. (1971). On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. Theory of Probability and Its Applications, 16(2), 264–280.
- Vapnik V. N. (1995). The Nature of Statistical Learning Theory. Springer.
- Shalev-Shwartz S., Ben-David S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, rozdz. 6.
- Zhang C., Bengio S., Hardt M., Recht B., Vinyals O. (2017). Understanding Deep Learning Requires Rethinking Generalization. ICLR 2017, arXiv:1611.03530.