11 · Prawa i prawdy · 3 min czytania · aktualizacja 8 października 2026

Co mówi twierdzenie Covera o liniowej separowalności w wysokich wymiarach?

Co to jest

Losowy układ etykiet na N punktach w położeniu ogólnym w przestrzeni d-wymiarowej jest tym bardziej prawdopodobnie liniowo separowalny, im wyższy jest wymiar w stosunku do liczby punktów — dlatego nieliniowe rzutowanie do wyższego wymiaru ułatwia klasyfikację. Twierdzenie udowodnił Thomas M. Cover w 1965 roku.

Rdzeniem jest wzór liczący, ile z 2ᴺ możliwych podziałów N punktów da się uzyskać hiperpłaszczyzną. Gdy punktów jest niewiele w stosunku do wymiaru, prawie wszystkie podziały są osiągalne. Gdy punktów jest dużo, prawie żaden. Przejście jest ostre i przypada na N ≈ 2d.

Stąd praktyczny wniosek, na którym opierają się jądra SVM, sieci z warstwą ukrytą i cechy wielomianowe: nie zginaj granicy decyzyjnej — wygnij przestrzeń, a granica może pozostać płaska.

Mechanizm — dlaczego tak działa

Cover policzył, że N punktów w położeniu ogólnym w przestrzeni z d stopniami swobody (dla hiperpłaszczyzn z wyrazem wolnym d = wymiar + 1) można liniowo podzielić na C(N, d) = 2·Σ_{k=0}^{d−1} (N−1 po k) sposobów. Dla N ≤ d to wszystkie 2ᴺ podziały. Dla N = 2d dokładnie połowa. Dla większych N odsetek spada gwałtownie do zera.

Interpretacja: każdy dodatkowy wymiar to dodatkowy kierunek, w którym można „wypchnąć” punkty jednej klasy od drugiej. Nieliniowe przekształcenie — np. dodanie cechy x² + y² — tworzy nowe kierunki zbudowane z kombinacji starych. Punkty, które w oryginalnej przestrzeni przeplatały się, w nowej mogą znaleźć się po przeciwnych stronach płaszczyzny.

Wynik Covera wyjaśnia też, skąd bierze się pojemność klasyfikatora liniowego: potrafi on „zapamiętać” mniej więcej 2d losowych etykiet. To ten sam rachunek, który leży pod wymiarem VC.

Zastrzeżenie: separowalność nie oznacza generalizacji. W odpowiednio wysokim wymiarze da się rozdzielić dowolne etykiety, także zupełnie losowe — to przepis na przeuczenie. Twierdzenie mówi, że rzutowanie umożliwia liniowy podział; o tym, czy podział coś znaczy, decydują dane i regularyzacja (np. margines w SVM).

Na przykładzie

Wzór dla płaszczyzny (wymiar 2, d = 3): 4 punkty — 87,5% podziałów separowalnych, 6 punktów — 50%, 8 — 22,7%, 12 — 3,3%. Dla wymiaru 10 (d = 11): 20 punktów — 67,6%, 22 — 50%, 33 — 2,5%. Sprawdziliśmy to empirycznie programowaniem liniowym: losowe punkty gaussowskie w 10 wymiarach z losowymi etykietami, 200 prób. Odsetek separowalnych wyniósł 0,96 dla 16 punktów (teoria 0,94), 0,45 dla 22 (teoria 0,50), 0,15 dla 28 (teoria 0,12) i 0 dla 44.

Rzutowanie w praktyce: dwa koncentryczne okręgi (make_circles, 500 punktów, szum 0,1). Regresja logistyczna na współrzędnych x, y osiąga w walidacji krzyżowej 0,46 — nie lepiej niż losowo. Po dodaniu jednej cechy x² + y² ta sama regresja logistyczna osiąga 0,99. Granica pozostała płaska; zmieniła się przestrzeń.

W praktyce

• Jądra w SVC(kernel='rbf') czy kernel='poly' realizują rzutowanie do wysokiego wymiaru bez jawnego liczenia cech (trik jądrowy).
• Jawne rzutowanie: PolynomialFeatures, SplineTransformer, RBFSampler lub Nystroem z liniowym modelem na końcu.
• Warstwa ukryta sieci neuronowej to wyuczone rzutowanie — kolejne warstwy czynią klasy coraz bardziej liniowo separowalnymi.
• Im wyższy wymiar, tym ważniejsza regularyzacja (C, alpha), bo rośnie zdolność do rozdzielenia szumu.
• Typowy błąd: interpretowanie 100% dokładności treningowej po rzutowaniu jako sukcesu — trzeba sprawdzić walidację.

Najczęstsze pytania

Czy twierdzenie Covera dotyczy tylko losowych etykiet?

Wzór liczy wszystkie możliwe podziały, więc mówi o „typowym” układzie etykiet. Realne problemy mają strukturę, dzięki której dobrze dobrane rzutowanie wystarcza często w znacznie niższym wymiarze.

Jaki jest związek z problemem XOR?

XOR na płaszczyźnie to jeden z dwóch podziałów czterech punktów, których prosta nie wytworzy. Dodanie cechy x·y przenosi punkty do trzech wymiarów, gdzie płaszczyzna je rozdziela — to twierdzenie Covera w najmniejszej skali.

Czy wyższy wymiar zawsze pomaga?

Pomaga w separowalności, ale szkodzi w szacowaniu: rośnie liczba parametrów i ryzyko przeuczenia. To dwie strony tej samej monety, którą opisują też zjawisko Hughesa i przekleństwo wymiarowości.

Źródła

Zobacz też