Obliczanie wymiaru VC sieci neuronowej

11

Jeśli mam pewną stałą topologię nierekurencyjną (DAG) (ustalony zestaw węzłów i krawędzi, ale algorytm uczenia może zmieniać ciężar na krawędziach) neuronów esowatych z neuronami wejściowymi, które mogą przyjmować tylko łańcuchy w jako dane wejściowe i prowadzące do jednego wyniku (który wyprowadza rzeczywistą wartość, którą zaokrąglamy w górę do 1 lub w dół do -1, jeśli jest to pewna stała wartość progowa od 0). Czy jest jakiś szybki sposób na obliczenie (lub przybliżenie) wymiaru VC tej sieci?n{-1,1}n


Notatki

Poprosiłem o nieco bardziej precyzyjne przeformułowanie algorytmiczne w CS.SE:

Wydajne obliczanie lub przybliżanie wymiaru VC sieci neuronowej

Artem Kaznatcheev
źródło
Wyjaśnij: czy masz jakieś ukryte warstwy neuronów? Twoje pytanie nie określa wprost, czy masz ukryte warstwy.
Andrew
@Andrew metoda powinna działać w obu przypadkach. Ponieważ żadna ukryta warstwa nie jest klasyfikatorem liniowym, jest to trywialne; więc bardziej interesuje mnie przypadek niebanalny; załóżmy, że mamy ponad 2 ukryte warstwy (chociaż metoda powinna również działać na mniej, ponieważ jest łatwiej).
Artem Kaznatcheev,

Odpowiedzi:

6

Natknąłem się na twój post, szukając ogólnej formuły do ​​obliczania wymiarów VC w sieciach neuronowych, ale najwyraźniej nie ma takiej. Najwyraźniej mamy do czynienia z mnóstwem różnych równań VC, które mają zastosowanie tylko w niektórych wąskich przypadkach. Uwaga: Opieram to na starych badaniach, których ledwo rozumiem, na koncepcji VC Dimensions, o której dopiero się uczę. Niemniej jednak warto przejrzeć ten artykuł autorstwa Petera L. Bartletta i Wolfganga Maassa 1na obliczalność wymiarów VC. Zwróć uwagę, jak bardzo się starają, aby uzyskać formuły VC w 13 twierdzeniach, ale jak różnorodne i liczne są niezbędne warunki dla każdego z nich. Wymagania te obejmują zakres od liczby operatorów w funkcjach aktywacyjnych do dozwolonych typów skoków, liczby neuronów i ich pozycji, głębokości bitowej wejścia itp .; istnieje tak wiele tych rozrzuconych „gotch”, że sprawiają, że formuły są użyteczne tylko w przypadku niektórych wąskich klas problemów. Co gorsza, twierdzą w Twierdzeniach 5 i 8, że funkcje aktywacji sigmoidalnej są szczególnie trudne do obliczenia liczb VC. Na s. 6-7 piszą:

„Podczas gdy wymiar VC sieci z częściowymi wielomianowymi funkcjami aktywacyjnymi jest dobrze zrozumiany, większość aplikacji sieci neuronowych wykorzystuje logistyczną funkcję sigmoidalną lub Gaussowską radialną funkcję bazową. Niestety nie jest możliwe obliczenie takich funkcji przy użyciu skończonej liczby operacje arytmetyczne wymienione w Twierdzeniu 5. Jednak Karpiński i Macintyre [Karpinski i Macintyre, 1997] rozszerzyli Twierdzenie 5, aby umożliwić obliczanie wykładniczych. Dowód wykorzystuje te same idee, ale ograniczenie liczby rozwiązań układu równań jest znacznie trudniejsze ”.

Natknąłem się również na ten artykuł z zachęcającym tytułem „Ograniczający wymiar VC dla sieci neuronowych: postęp i perspektywy”. 2)Dużo matematyki jest nad moją głową i nie przeszukiwałem jej wystarczająco długo, aby przezwyciężyć mój brak umiejętności tłumaczenia, ale podejrzewam, że nie oferuje ona wstrząsających wstrząsów, ponieważ poprzedza ona drugie wydanie książki Bartlett i Maass, którzy cytują późniejsze prace tych samych autorów. Być może późniejsze badania w ciągu ostatnich 20 lat poprawiły obliczalność wymiarów VC dla sieci neuronowych, ale większość odniesień, które znalazłem, pochodzą z połowy lat 90. XX wieku; najwyraźniej w tamtym czasie doszło do serii prac, które od tamtego czasu umarły. Jeśli możliwości nie zostały rozszerzone przez nowsze stypendium znacznie wykraczające poza to, co były w latach 90., mam nadzieję, że ktoś wkrótce zaproponuje szersze zastosowanie, aby móc rozpocząć obliczanie wymiarów VC również w moich sieciach neuronowych. Przepraszam nie mogłem

1 Bartlett, Peter L. i Maass, Wolfgang, 2003, „Vapnik-Chervonenkis Dimension of Neural Nets”, str. 1188-1192 w The Handbook of Brain Theory and Neural Networks, Arbib, Michael A. ed. MIT Press: Cambridge, Mass.

2 Karpiński, Marek i Macintyre, Angus, 1995, „Bounding VC-Dimension for Neural Networks: Progress and Perspect”, s. 337–341 w materiałach z 2. Europejskiej Konferencji na temat teorii uczenia obliczeniowego, Barcelona, ​​Hiszpania. Vitanyi, P. ed. Wykład notatki w sztucznej inteligencji, nr 904. Springer: Berlin.

SQLServerSteve
źródło
0

Oto najnowsze dzieło: http://jmlr.org/papers/v20/17-612.html .

W.L.

doW.L.log(W./L.)V.dodoW.L.log(W.L.)
dodo

dodo

jachilles
źródło