Dlaczego głębokie uczenie się jest osłabione pomimo złego wymiaru VC?

86

Wzór Vapnika – Chervonenkisa (VC) dla sieci neuronowych zawiera się w przedziale od do , przy czym w najgorszym przypadku, gdzie jest liczbą krawędzi i to liczba węzłów. Liczba próbek treningowych potrzebnych do uzyskania silnej gwarancji uogólnienia jest liniowa z wymiarem VC.O(E)O(E2)O(E2V2)EV

Oznacza to, że w przypadku sieci z miliardami brzegów, tak jak w przypadku udanych modeli głębokiego uczenia, zestaw danych szkoleniowych potrzebuje miliardów próbek szkoleniowych w najlepszym przypadku, a nawet biliardów w najgorszym przypadku. Największe zestawy szkoleniowe mają obecnie około stu miliardów próbek. Ponieważ nie ma wystarczającej ilości danych szkoleniowych, mało prawdopodobne jest, aby modele głębokiego uczenia się generalizowały. Zamiast tego prześcigają się w danych treningowych. Oznacza to, że modele nie będą dobrze działać na danych niepodobnych do danych szkoleniowych, co jest niepożądaną właściwością uczenia maszynowego.

Biorąc pod uwagę niezdolność do głębokiego uczenia się do uogólnienia, zgodnie z analizą wymiarową VC, dlaczego wyniki głębokiego uczenia się są tak przereklamowane? Samo posiadanie wysokiej dokładności w niektórych zestawach danych nie znaczy wiele samo w sobie. Czy jest coś wyjątkowego w architekturze głębokiego uczenia się, która znacznie zmniejsza wymiar VC?

Jeśli nie uważasz, że analiza wymiaru VC jest odpowiednia, proszę przedstawić dowody / wyjaśnienia, że ​​głębokie uczenie się jest uogólniające i nie jest zbyt dobre. Czyli ma dobre przywołanie ORAZ precyzję, czy po prostu dobre przywołanie? 100% wycofania jest banalne, podobnie jak 100% precyzji. Uzyskanie obu wartości zbliżonych do 100% jest bardzo trudne.

Jako przeciwny przykład, oto dowód na to, że głębokie uczenie się jest zbyt dobre. Model overfit można łatwo oszukać, ponieważ zawiera on deterministyczny / stochastyczny hałas. Poniższy obraz przedstawia przykład nadmiernego dopasowania.

Przykład niedopasowania, dopasowania i niedopasowania.

Zobacz także odpowiedzi na to pytanie w rankingu poniżej, aby zrozumieć problemy z modelem overfit pomimo dobrej dokładności danych testowych.

Niektórzy odpowiedzieli, że regularyzacja rozwiązuje problem dużego wymiaru VC. Zobacz to pytanie do dalszej dyskusji.

yters
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
DW
7
Nie sądzę, żeby pytania, dlaczego coś „podskórnego” są dobre. Odpowiedź brzmi „ponieważ ludzie”. Ludzie interesują się rzeczami z wielu powodów, w tym z marketingu.
luk32
Głębokie uczenie się działa w praktyce. To może być przesadne. To może być całkowicie nieuzasadnione. Być może uczy się tajemnic wszechświata od bóstwa eldritcha. Ale hype pochodzi od praktyków, którzy nagle są w stanie napisać 30 wierszy w kodzie i nauczyć kamerę skanować podpisy i dopasowywać je do przechowywanych w celu weryfikacji transakcji bankowych. Lub oznacz nieznane osoby na zdjęciach. Itd. Może słyszałeś linijkę „to nie jest zniewaga, jeśli to prawda”? Cóż, to nie jest szum, jeśli to działa. Istnieje wiele problemów, na których nie działa i nadmierna popularność. Ale działa w rzeczywistych aplikacjach.
Stella Biderman
@StellaBiderman łatwość korzystania ze standardowych technik uczenia maszynowego jest dobra. Wydaje się jednak, że zainteresowanie dotyczy bardziej rzekomej zdolności uczenia się DNN, która być może rywalizuje z ludzkimi zdolnościami, co wydaje się nadmierne, biorąc pod uwagę analizę modelu VC. Tak wysoki wymiar VC oznacza, że ​​modele nie będą generalizować, a zamiast tego zapamiętują zestawy danych, co czyni je bardzo kruchymi. Wszystkie przeciwne dokumenty przykładowe wydają się wykazywać ten punkt.
po
@gerrit Nie jestem pewien, czy edycja była tak pomocna. Założę się, że więcej osób wie, czym jest wymiar VC, niż wie, co to znaczy.
David Richerby

Odpowiedzi:

75

„Jeśli mapa i teren się nie zgadzają, zaufaj temu terenowi”.

Nie do końca rozumie się, dlaczego głębokie uczenie się działa tak dobrze, ale z pewnością stare koncepcje teorii uczenia się, takie jak wymiary VC, nie wydają się bardzo pomocne.

Sprawa jest gorąco dyskutowana, patrz np .:

Jeśli chodzi o kwestię przykładów przeciwnych , problem został odkryty w:

Jest dalej rozwijany w:

Jest wiele dalszych prac.

Martin Berger
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
DW
Kiedy mówisz „Jest dużo kontynuacji”, czy masz na myśli ostatni artykuł z 2014 roku? Pierwsze dwa artykuły, o których wspominasz, są dość nowe. Czy możesz zaktualizować dokumenty, o których mowa?
VF1
2
Silne +1 za „Jeśli mapa i teren się nie zgadzają, zaufaj temu terenowi”. Modele działają wyjątkowo dobrze w praktyce, niezależnie od tego, czy matematyka mówi, że powinny. Z naukowego POV dzieje się to cały czas, a jeśli coś sprawia, że ​​problemy stają się bardziej interesujące. Nikt nie czytał pracy Razborova i Rudicha na temat naturalnych dowodów i nie powiedział „no cóż, wydaje mi się, że P kontra NP nie jest interesującym pytaniem”. Poszli i odkryli, że możliwe jest użycie geometrii algebraicznej do zrobienia teorii złożoności. Z punktu widzenia nauki problemy wykraczające poza nasze zrozumienie są lepsze , a nie gorsze.
Stella Biderman
65

„Biorąc pod uwagę niezdolność dogłębnego uczenia się do uogólnienia, zgodnie z analizą wymiarową VC [...]”

Nie, nie tak mówi analiza wymiarowa VC. Analiza wymiarowa VC daje pewne wystarczające warunki, w których gwarantowana jest generalizacja. Ale odwrotność niekoniecznie tak jest. Nawet jeśli nie spełnisz tych warunków, metoda ML nadal może zostać uogólniona.

Innymi słowy: głębokie uczenie się działa lepiej niż analiza wymiarowa VC doprowadziłaby do oczekiwań (lepsza niż „przewidywanie” analizy VC). To wada analizy wymiarowej VC, a nie wada głębokiego uczenia się. Nie oznacza to, że głębokie uczenie się jest wadliwe. Oznacza to raczej, że nie wiemy, dlaczego działa głębokie uczenie się - a analiza VC nie jest w stanie dostarczyć żadnych użytecznych informacji.

Wysoki wymiar VC nie oznacza, że ​​głębokie uczenie się można oszukać. Wysoki wymiar VC wcale nie gwarantuje, że da się go oszukać w praktycznych sytuacjach. Wymiar VC zapewnia jednokierunkowy, najgorszy przypadek: jeśli spełniasz te warunki, wtedy dobre rzeczy się zdarzają, ale jeśli nie spełniasz tych warunków, nie wiemy, co się stanie (być może dobre rzeczy i tak się zdarzają, jeśli natura zachowuje się lepiej niż najgorszy możliwy przypadek; analiza VC nie obiecuje, że dobre rzeczy nie mogą / nie będą miały miejsca).

Może być tak, że wymiar VC przestrzeni modelu jest duży (zawiera bardzo złożone wzorce, jak to możliwe), ale natura jest wyjaśniona prostymi wzorami, a algorytm ML uczy się prostego wzoru obecnego w naturze (np. Z powodu regularyzacji) - - w tym przypadku wymiar VC byłby wysoki, ale model uogólniałby (dla konkretnego wzoru występującego w naturze).

To powiedziawszy ... jest coraz więcej dowodów na to, że głębokie uczenie się można oszukać na podstawie przeciwnych przykładów. Ale uważaj na swój łańcuch rozumowania. Wnioski, które wyciągasz, nie wynikają z założeń, z których zacząłeś.

DW
źródło
6
Wysoki wymiar VC oznacza, że ​​trudniej jest go uogólnić (w pewnym sensie, przynajmniej w przypadku arbitralnych rozkładów). błędu uogólnienie dolna granica dokładnie oznacza, że liczba próbek małe w porównaniu do wymiarów VC istnieje taki rozkład, który w stosunku do niej żadnego algorytmu wystąpi duży błąd uogólnienia (z dużym prawdopodobieństwem). Ω(dn)
Ariel
5
-1 dla „Wysokie wymiary VC nie gwarantują niczego”. Nie jest to prawdą: wysoki wymiar VC implikuje złożoność próby w dolnych granicach dla uczenia się PAC. Dobra odpowiedź powinna dotyczyć najgorszych przypadków w porównaniu z „rzeczywistymi” rozkładami.
Sasho Nikolov
1
@SashoNikolov, dobra uwaga - dziękuję! Edytowane.
DW
Ten post był w recenzji niskiej jakości. Biorąc pod uwagę treść, długość, głosy i jakość, jest to śmieszne, wskazując na to tutaj, ale może wymagać meta, ponieważ coś jest naprawdę nie tak.
Zło
23

Ludzie z branży nie zwracają uwagi na wymiar VC, chuligani ...

Mówiąc poważniej, chociaż model PAC jest eleganckim sposobem myślenia o nauce (przynajmniej moim zdaniem) i jest na tyle skomplikowany, że rodzi ciekawe koncepcje i pytania (takie jak wymiar VC i jego związek z złożonością próby) , ma bardzo mało wspólnego z rzeczywistymi sytuacjami.

Pamiętaj, że w modelu PAC musisz obsługiwać dowolne rozkłady, co oznacza, że ​​Twój algorytm powinien obsługiwać rozkłady przeciwne. Próbując nauczyć się pewnych zjawisk w prawdziwym świecie, nikt nie podaje ci „danych kontradyktoryjnych”, które mogą popsuć twoje wyniki, więc wymaganie, aby klasa koncepcyjna była możliwa do nauczenia się PAC, może być zbyt silne. Czasami błąd generalizacji można powiązać niezależnie od wymiaru VC, dla określonej klasy dystrybucji. Dotyczy to granic marginesów, które są formułowane niezależnie od wymiaru VC. Mogą obiecać niski błąd uogólnienia, jeśli możesz zagwarantować wysoki margines empiryczny (co oczywiście nie może się zdarzyć dla wszystkich rozkładów, np. Weź dwa bliskie punkty na płaszczyźnie z przeciwnymi znacznikami i skoncentruj na nich rozkład).

Odkładając na bok model PAC i wymiar VC, myślę, że hype wynika z faktu, że po prostu wydają się działać i odnoszą sukcesy w zadaniach, które wcześniej nie były możliwe (jednym z najnowszych osiągnięć, które przychodzą na myśl, jest AlphaGo). Niewiele wiem o sieciach neuronowych, więc mam nadzieję, że ktoś z większym doświadczeniem przyjdzie, ale według mojej wiedzy nie ma jeszcze dobrych gwarancji (zdecydowanie nie tak jak w modelu PAC). Być może przy właściwych założeniach można formalnie uzasadnić sukces sieci neuronowych (zakładam, że są prace nad formalnym traktowaniem sieci neuronowych i „głębokim uczeniem się”, więc mam nadzieję, że ludzie z większą wiedzą na ten temat mogą powiązać niektóre artykuły) .

Ariel
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
DW
15

Biorąc pod uwagę niezdolność dogłębnego uczenia się do uogólnienia,

Nie wiem skąd to bierzesz. Empirycznie uogólnienie jest postrzegane jako wynik (np. Dokładność) na niewidzialnych danych.

Odpowiedź na pytanie, dlaczego są używane CNN, jest prosta: CNN działają znacznie lepiej niż cokolwiek innego . Zobacz na przykład ImageNet 2012:

  • CNN: 15,315% (to był wczesny przykład. CNN są teraz znacznie lepsze. Przy około 4% błędu w pierwszej piątce)
  • Najlepszy inny niż CNN: 26,172% Błąd w pierwszej piątce ( źródło - według mojej wiedzy techniki, które nie wykorzystują CNN, nie spadły poniżej 25% błędu w pierwszej piątce)

Utwórz klasyfikator, który będzie lepszy, a ludzie przejdą do tego.

AKTUALIZACJA: Udzielę odpowiedzi każdemu, kto dostarczy opublikowane dowody, że uczenie maszynowe w ogóle jest łatwe do oszukania, podobnie jak dowody dotyczące głębokiego uczenia się.

Nie o to chodzi. Możesz stworzyć klasyfikator, który jest niezwykle prosty na prostym zbiorze danych. Nie da się go oszukać (nie ma nawet znaczenia, co oznacza „łatwy”), ale nie jest to również interesujące.

Martin Thoma
źródło
3
Niski błąd nie oznacza uogólnienia. Jest to warunek konieczny, ale niewystarczający.
po
3
@yters Proszę zdefiniować uogólnienie.
Martin Thoma
5
@yters, ten komentarz sprawia, że ​​myślę, że nie przeczytałeś wiele na temat uczenia maszynowego. Martin powiedział dokładność niewidzialnych danych . Mówisz o dokładności danych treningowych. Zasadniczo masz rację co do tego, czym jest uogólnienie, ale pamiętaj, że wszyscy inni też to rozumieją .
Ken Williams
1
@yters Jestem pewien, że Ken (i wiele osób na tej stronie, w tym ja) wie o tym. Jeśli jednak zestaw testowy nie reprezentuje zestawu danych, nie można wypowiedzieć się na temat uogólnienia. Chociaż warto o tym pamiętać, nie rozumiem, w jaki sposób pomaga to w jakikolwiek sposób w przypadku tego pytania. Musisz tylko założyć / upewnić się, że Twój zestaw testowy reprezentuje twoje dane w czasie produkcji. W rzeczywistości bardzo łatwo jest wykazać, że można uczynić dowolnego klasyfikatora arbitralnym złym, jeśli próbki szkoleniowe nie reprezentują rozkładu.
Martin Thoma
2
To oczywiste. Nie można oczekiwać, że model dobrze się uogólni, jeśli zostanie przeszkolony w zakresie sprawdzania poprawności na niewłaściwych danych. Potrzebujesz lepszych danych, a nie lepszego modelu.
Emre
9

Jednym słowem jest „regularyzacja”. Naiwna formuła wymiaru VC tak naprawdę nie ma tutaj zastosowania, ponieważ regularyzacja wymaga, aby wagi nie były ogólne. Tylko niewielki (nieskończenie mały) odsetek kombinacji wagowych ma akceptowalną utratę po regularyzacji. W rezultacie rzeczywisty wymiar jest o wiele rzędów wielkości mniejszy, więc uogólnienia mogą wystąpić w przypadku zestawów treningowych, które mamy. Rzeczywiste wyniki pokazują, że przeważnie się nie zdarza.

David Khoo
źródło
2
Widziałem powtarzające się twierdzenie, że rzeczywiste wyniki pokazują uogólnione uczenie się. Jakie dokładnie wyniki pokazują uogólnienie? Do tej pory widziałem tylko to, że DL osiąga niski poziom błędów w określonych zestawach danych, co samo w sobie nie oznacza, że ​​DL się uogólnia.
po
3
pokazuje dobre wyniki („dobre” = lepsze niż inne metody ML) dla danych, na których nie był szkolony . nie jestem pewien, jak inaczej chcesz praktycznie zmierzyć uogólnienie.
lvilnis
3

Zajmujemy się dokumentem: Zrozumienie głębokiego uczenia się wymaga ponownego przemyślenia generalizacji. w

Ponowne przemyślenie uogólnienia wymaga rewizji starych pomysłów: podejścia do mechaniki statystycznej i złożone zachowania edukacyjne Charles H. Martin i Michael W. Mahoney

Zobacz: https://arxiv.org/pdf/1710.09553.pdf

Zasadniczo twierdzimy, że granice VC są zbyt luźne, ponieważ podstawowe podejście i sposób, w jaki przyjęty limit statystyczny jest nierealny.

Lepsze podejście leży w mechanice statystycznej, która uwzględnia klasę funkcji zależnych od danych, przyjmuje granicę termodynamiczną (nie tylko granicę dużych liczb)

Ponadto wskazujemy również, w jaki sposób naturalne nieciągłości w głębokiej potrzebie prowadzą do przejścia fazowego w krzywej uczenia się, co naszym zdaniem jest obserwowane w artykule Google (powyżej)

Jeśli chodzi o limity, patrz punkt 4.2 naszego dokumentu

„Oczywiście, jeśli naprawimy wielkość próby m i pozwolimy [rozmiar klasy funkcji] N → ∞, [lub odwrotnie, naprawimy N, niech m → ∞], nie powinniśmy oczekiwać wyniku niebanalnego, ponieważ [ N] staje się coraz większy, ale wielkość próbki jest stała. Zatem [w mechanice statystycznej] zwykle rozważa się przypadek, że m, N → ∞ takie, że α = m / N jest stałą stałą. ”

Oznacza to, że bardzo rzadko dodajemy więcej danych (m) do głębokiej sieci. Zawsze zwiększamy również rozmiar sieci (N), ponieważ wiemy, że możemy przechwycić bardziej szczegółowe funkcje / informacje z danych. Zamiast tego robimy w praktyce to, o co argumentujemy w artykule - przyjmujemy granicę dużego rozmiaru, ze stałym współczynnikiem m / N (w przeciwieństwie do powiedzenia ustalania mi wzrostem N).

Wyniki te są dobrze znane w statystycznej mechanice uczenia się. Analiza jest bardziej skomplikowana, ale wyniki prowadzą do znacznie bogatszej struktury, która wyjaśnia wiele zjawisk w głębokim uczeniu się.

Ponadto, w szczególności wiadomo, że wiele granic statystyki staje się albo trywialnych, albo nie stosuje się do nieładnych rozkładów prawdopodobieństwa, lub gdy zmienne przyjmują wartości dyskretne. W sieciach neuronowych zachodzi nietrywialne zachowanie z powodu nieciągłości (w funkcjach aktywacyjnych), prowadzącej do przejść fazowych (które powstają w granicy termodynamicznej).

Artykuł, który napisaliśmy, próbuje wyjaśnić najistotniejsze pomysły publiczności informatycznej.

Sam Vapnik zdał sobie sprawę, że jego teoria tak naprawdę nie miała zastosowania do sieci neuronowych ... w 1994 roku

„Rozszerzenie [wymiaru VC] na sieci wielowarstwowe napotyka [wiele] trudności. Istniejących algorytmów uczenia się nie można postrzegać jako minimalizujących ryzyko empiryczne w całym zestawie funkcji realizowanych przez sieć ... [ponieważ] jest prawdopodobnie ... wyszukiwanie będzie ograniczone do podzbioru [tych] funkcji ... Pojemność tego zestawu może być znacznie niższa niż pojemność całego zestawu ... [i] może się zmieniać wraz z liczbą obserwacji. Może to wymagać teorii uwzględniającej pojęcie nietrwałej pojemności z „aktywnym” podzbiorem funkcji ”
Vapnik, Levin i LeCun 1994

http://yann.lecun.com/exdb/publis/pdf/vapnik-levin-lecun-94.pdf

Chociaż nie jest to łatwe do leczenia teorią VC, nie jest to problemem dla statystyki mech ... a to, co opisują, bardzo przypomina Teorię Krajobrazu Energetycznego składania białka. (który będzie tematem przyszłej pracy)

Charles Martin
źródło
Brzmi interesująco, ale nie jestem pewien, czy podążę za twoją argumentacją. Czy potrafisz rozwinąć zdanie pierwsze, tj. To, w jaki sposób podstawowe podejście / granica statystyczna jest nierealistyczna, w sposób samowystarczalny, który nie wymaga zrozumienia mechaniki statystycznej? Jakie założenia przyjmują granice VC i dlaczego są nierealne? Być może możesz edytować swoją odpowiedź, aby uwzględnić tę informację?
DW
Dodałem odniesienie do oryginalnej pracy Vapnika i LeCuna (1994), która omawia ten problem.
Charles Martin
I dodał trochę wyjaśnień.
Charles Martin
1

Wydaje się, że nikt nie wskazał w powyższych odpowiedziach, że cytowana formuła wymiaru VC dotyczy tylko 1-warstwowej sieci neuronowej. Domyślam się, że wymiar VC faktycznie rośnie wykładniczo wraz ze wzrostem liczby warstw L. Moje rozumowanie opiera się na rozważeniu głębokich sieci neuronowych, w których funkcję aktywacji zastępuje wielomian. Następnie stopień złożonych wielomianów rośnie wykładniczo wraz ze wzrostem warstw.

Yan King Yin
źródło