Twierdzenie Covera

Twierdzenie Covera jest stwierdzeniem w teorii obliczeniowego uczenia się i jest jedną z głównych teoretycznych motywacji do stosowania nieliniowych metod jądra w aplikacjach uczenia maszynowego . Zostało tak nazwane na cześć teoretyka informacji Thomasa M. Covera , który stwierdził to w 1965 roku, nazywając to twierdzeniem o funkcji liczenia .

Twierdzenie

Twierdzenie wyraża liczbę jednorodnie liniowo rozłącznych zestawów punktów w $re$ $}$ wyraźną funkcję zliczania liczby do $)$ punktów i wymiarowość ${ \$ $D}$ .

Wymaga to, jako warunku koniecznego i wystarczającego, aby punkty znajdowały się w ogólnym położeniu . Mówiąc najprościej, oznacza to, że punkty powinny być jak najbardziej niezależne liniowo (niewyrównane). Warunek ten jest spełniony „z prawdopodobieństwem 1” lub prawie na pewno dla losowych zestawów punktów, podczas gdy można go łatwo naruszyć w przypadku rzeczywistych danych, ponieważ są one często ustrukturyzowane wzdłuż rozmaitości o mniejszej liczbie wymiarów w przestrzeni danych.

Funkcja podlega dwóm różnym reżimom w zależności od relacji między i $,$ $, re ) {$ $C$ D .

Dla , funkcja jest wykładnicza w $+ 1}$ $\ Displaystyle N \ równoważnik$ . Zasadniczo oznacza to, że dowolny zestaw oznaczonych punktów w ogólnej pozycji iw liczbie nie większej niż wymiarowość + 1 jest liniowo separowalny; w żargonie mówi się, że klasyfikator liniowy rozbija dowolny zbiór punktów z ${\ Displaystyle N \ leq D + 1}$ . Ta wielkość graniczna jest również znana jako klasyfikatora liniowego Vapnika-Chervonenkisa .

Dla $licząca$ rosnąć mniej $uwagę$ próbkę o stałym rozmiarze $,$ większej wymiarowości jest bardziej prawdopodobne, że losowy zestaw oznaczonych punktów jest liniowo rozdzielny. I odwrotnie, przy ustalonej wymiarowości, dla większych rozmiarów próbek liczba zestawów losowych punktów, które można rozdzielić liniowo, będzie mniejsza, czyli innymi słowy prawdopodobieństwo znalezienia próbki rozłącznej liniowo zmniejszy się wraz z ${\ displaystyle N}$ .

Konsekwencją twierdzenia jest to, że mając zbiór danych treningowych, który nie jest liniowo separowalny , można z dużym prawdopodobieństwem przekształcić go w zbiór treningowy, który jest liniowo separowalny, rzutując go na przestrzeń wielowymiarową za pomocą transformacji nieliniowej, Lub:

Złożony problem klasyfikacji wzorców, rzucony nieliniowo w wielowymiarową przestrzeń, jest bardziej prawdopodobny, że można go liniowo rozdzielić niż w przestrzeni niskowymiarowej, pod warunkiem, że przestrzeń nie jest gęsto zaludniona.

Dowód

Dowód twierdzenia o funkcji liczącej Covera można uzyskać z relacji rekurencyjnej

${\ Displaystyle C (N + 1, D) = C (N, D) + C (N, D-1).}$

Aby pokazać, że przy ustalonym $,$ zwiększenie może zmienić zbiór punktów z nierozdzielnych na rozdzielne, $można$ mapowanie deterministyczne : załóżmy, że istnieją punkty $displaystyle N}$ . Podnieś je na wierzchołki simpleksu w wymiarowej przestrzeni rzeczywistej ${\ displaystyle N-1} .$ Ponieważ każdy podział próbek na dwa zestawy można oddzielić za pomocą separatora liniowego , wynika z tego właściwość.

Lewy obraz pokazuje 100 punktów w dwuwymiarowej przestrzeni rzeczywistej, oznaczonych według tego, czy znajdują się one wewnątrz, czy na zewnątrz okrągłego obszaru. Te oznaczone punkty nie są liniowo separowalne, ale podnosząc je do przestrzeni trójwymiarowej za pomocą sztuczki z jądrem , punkty stają się liniowo separowalne. Należy zauważyć, że w tym przypadku iw wielu innych przypadkach nie będzie konieczne podnoszenie punktów do 99-wymiarowej przestrzeni, jak założono w wyjaśnieniu.

Zobacz też

Haykin, Szymon (2009). Sieci neuronowe i maszyny uczące się (wyd. Trzecie). Upper Saddle River, New Jersey: Pearson Education Inc., s. 232–236. ISBN 978-0-13-147139-9 .
Okładka, TM (1965). „Właściwości geometryczne i statystyczne układów nierówności liniowych z zastosowaniami w rozpoznawaniu wzorców” (PDF) . Transakcje IEEE na komputerach elektronicznych . WE-14 (3): 326–334. doi : 10.1109/pgec.1965.264137 . S2CID 18251470 . Zarchiwizowane od oryginału (PDF) w dniu 2019-12-20.
Mehrotra, K.; Mohan, CK; Ranka S. (1997). Elementy sztucznych sieci neuronowych (wyd. 2). MIT Press. ISBN 0-262-13328-8 . (Sekcja 3.5)