Al Rahimi wygłosił ostatnio bardzo prowokujący wykład w NIPS 2017, porównując obecne uczenie maszynowe z alchemią. Jednym z jego twierdzeń jest to, że musimy wrócić do rozwoju teoretycznego, aby mieć proste twierdzenia potwierdzające fundamentalne wyniki.
Kiedy to powiedział, zacząłem szukać głównych twierdzeń dotyczących ML, ale nie mogłem znaleźć dobrego odniesienia, które miałoby sens z głównych wyników. Oto moje pytanie: jakie są obecne główne twierdzenia matematyczne (teoria) w ML / DL i co one dowodzą? Domyślam się, że praca Vapnika gdzieś tu pójdzie. Dodatkowo, jakie są główne teoretyczne otwarte problemy?
machine-learning
deep-learning
theory
statslearner
źródło
źródło
Odpowiedzi:
Jak napisałem w komentarzach, pytanie to wydaje mi się zbyt ogólne, ale spróbuję znaleźć odpowiedź. Aby wyznaczyć pewne granice, zacznę od małej matematyki, która leży u podstaw większości ML, a następnie skoncentruję się na najnowszych wynikach dla DL.
Bias-wariancji kompromis jest określany w niezliczonych książkach, kursach, MOOCs, blogi, tweety, itp na ML, więc nie można uruchomić bez wymieniania go:
Dowód tutaj: https://web.stanford.edu/~hastie/ElemStatLearn/
Twierdzenie Gaussa-Markowa (tak, regresja liniowa pozostanie ważną częścią uczenia maszynowego, bez względu na to: jak sobie z tym poradzić) wyjaśnia, że gdy model liniowy jest prawdziwy i niektóre założenia dotyczące terminu błędu są prawidłowe, OLS ma minimum średni błąd kwadratu (który w powyższym wyrażeniu jest po prostu ) tylko wśród bezstronnych estymatorów liniowych modelu liniowego. Tak więc mogą istnieć estymatory liniowe z odchyleniem (lub estymatory nieliniowe), które mają lepszy błąd średniej kwadratowej, a zatem lepszy oczekiwany błąd predykcji, niż OLS. A to toruje drogę do całego arsenału regularyzacji (regresja grzbietu, LASSO, spadek masy ciała itp.), Który jest koniem ML. Dowód jest podany tutaj (i w wielu innych książkach):Bias2 + Variance https://www.amazon.com/Linear-Statistic-Models-James-Stapleton/dp/0470231467
Prawdopodobnie bardziej istotne dla eksplozji podejść regularyzacyjnych, jak zauważył Carlos Cinelli w komentarzach, i zdecydowanie przyjemniejsze do nauczenia się, jest twierdzenie Jamesa-Steina . Rozważ niezależnych, tej samej wariancji, ale nie takich samych średnich zmiennych losowych Gaussa:n
innymi słowy, mamy składowy losowy wektor Gaussa . Mamy jedną próbkę z i chcemy oszacować . Estymatorem MLE (a także UMVUE) jest oczywiście . Rozważ estymator Jamesa-Steinan− X∼N(θ,σ2I) x X θ θ^MLE=x
Oczywiście, jeśli , zmniejsza oszacowanie MLE do zera. James-Stein twierdzenie mówi, że dla , bezwzględnie dominuje , to znaczy, że ma niższy MSE . Dziwne, zaskakująco, nawet jeśli skurczymy się w kierunku jakiejkolwiek innej stałej , nadal dominuje . Od(n−2)σ2≤||x||2 θ^JS n≥4 θ^JS θ^MLE ∀ θ c≠0 θ^JS θ^MLE Xi są niezależne, może wydawać się dziwne, że próba oszacowania wzrostu trzech niepowiązanych osób, w tym próbki z liczby jabłek wyprodukowanych w Hiszpanii, może średnio poprawić naszą ocenę . Kluczową kwestią jest tutaj „średnio”: średni błąd kwadratowy dla równoczesnego oszacowania wszystkich składników wektora parametrów jest mniejszy, ale błąd kwadratowy dla jednego lub więcej składników może być znacznie większy i rzeczywiście często ma miejsce, gdy masz „ekstremalne” obserwacje.
Dowiedzenie się, że MLE, który był rzeczywiście „optymalnym” estymatorem w przypadku estymacji jednoczynnikowej, został zdetronizowany dla estymacji wielowymiarowej, było wówczas dość szokiem i doprowadziło do dużego zainteresowania skurczem, lepiej znanym jako regularyzacja w mowie ML. Można zauważyć pewne podobieństwa z modelami mieszanymi i koncepcją „siły zaciągania pożyczek”: rzeczywiście istnieje pewne powiązanie, jak omówiono tutaj
Ujednolicony pogląd na kurczenie się: jaka jest relacja (jeśli występuje) między paradoksem Steina, regresją grzbietu i efektami losowymi w modelach mieszanych?
Odniesienia: James, W., Stein, C., Estimation with Quadratic Loss . Materiały z czwartego sympozjum Berkeley na temat statystyki matematycznej i prawdopodobieństwa, tom 1: Wkład do teorii statystyki, 361--379, University of California Press, Berkeley, Kalifornia, 1961
Podstawowa analiza składowa jest kluczem do ważnego tematu redukcji wymiarów i opiera się na rozkładzie wartości osobliwych : dla każdej rzeczywistej macierzy (chociaż twierdzenie łatwo uogólnia się na złożone macierze) możemy napisaćN×p X
gdzie o rozmiarze jest ortogonalny, jest macierzą diagonalną z nieujemnymi elementami diagonalnymi, a o wielkości jest ponownie ortogonalny. Dowody i algorytmy obliczania można znaleźć w: Golub, G. i Van Loan, C. (1983), Obliczenia Matrix , prasa John Hopkins University, Baltimore.U N×p D p×p U p×p
Twierdzenie Mercer'a jest kamieniem węgielnym dla wielu różnych metod ML: cienkie splajny płytowe, maszyny wektorów nośnych, oszacowanie Kriginga losowego procesu Gaussa itp. Zasadniczo jest jednym z dwóch twierdzeń stojących za tak zwaną sztuczką jądra . Niech będzie symmmetryczną funkcją ciągłą lub jądrem. jeśli jest dodatnim półfinałem, to przyjmuje ortonormalną podstawę funkcji własnych odpowiadającą nieujemnym wartościom własnym:K(x,y):[a,b]×[a,b]→R K
O znaczeniu tego twierdzenia dla teorii ML świadczy liczba odniesień, jakie otrzymuje w słynnych tekstach, takich jak na przykład Rasmussen i Williams o procesach Gaussa .
Odniesienia: J. Mercer, Funkcje typu dodatniego i ujemnego oraz ich związek z teorią równań całkowych. Transakcje filozoficzne Royal Society of London. Seria A, zawierająca dokumenty o charakterze matematycznym lub fizycznym, 209: 415-446, 1909
Prostsza prezentacja znajduje się również w Konradzie Jörgensie, operatorach całki liniowej , Pitman, Boston, 1982.
Drugim twierdzeniem, które wraz z twierdzeniem Mercer'a stanowi teoretyczne podstawy sztuczki jądra, jest twierdzenie reprezentujące . Załóżmy, że masz przykładową przestrzeń i symetryczne dodatnie jądro semidfinite . Także pozwala być RKHS związane z . Na koniec niech będzie próbką szkoleniową. Twierdzenie mówi, że spośród wszystkich funkcji , które wszystkie przyjmują nieskończoną reprezentację pod względem funkcji własnychX K:X×X→R HK K S={xi,yi}ni=1 f∈HK K z powodu twierdzenia Mercer'a to, które minimalizuje ryzyko regulowane, zawsze ma skończoną reprezentację w podstawie utworzonej przez jądro oceniane w punktach treningowych, tj.n
(twierdzenie jest ostatnią równością). Odniesienia: Wahba, G. 1990, Spline Models for Observational Data , SIAM, Philadelphia.
Uniwersalny przybliżenie twierdzenie zostało już cytowany przez użytkownika Tobias Windisch i jest znacznie mniej istotne dla uczenia maszynowego, niż jest do analizy funkcjonalnej, nawet jeśli nie może wydawać się więc na pierwszy rzut oka. Problem polega na tym, że twierdzenie mówi tylko, że taka sieć istnieje, ale:
Mniejszy problem z wersją tego twierdzenia Hornika polega na tym, że nie dotyczy to funkcji aktywacyjnych ReLU. Jednak Bartlett udowodnił później rozszerzoną wersję, która pokrywa tę lukę.
Do tej pory wydaje mi się, że wszystkie twierdzenia, które rozważałem, były dobrze znane każdemu. Czas na zabawę :-) Zobaczmy kilka twierdzeń o głębokim uczeniu się :
Założenia:
Następnie:
Jest to bardzo interesujące: CNN wykonane tylko z warstw splotowych, ReLU, max-pooling, w pełni połączone ReLU i warstwy liniowe są dodatnio jednorodnymi funkcjami, a jeśli uwzględnimy funkcje aktywacji sigmoidalnej, nie jest to już prawdą, co może częściowo tłumaczyć wyższość wydajność w niektórych aplikacjach ReLU + max pooling w odniesieniu do sigmoidów. Co więcej, twierdzenia te obowiązują tylko wtedy, gdy jest dodatnio jednorodna w w tym samym stopniu co . faktem jest to, że lub , choć pozytywnie jednorodna, nie ma tego samego stopnia (stopieńΘ W Φ l1 l2 Φ Φ , w prostym przypadku CNN wspomnianym wcześniej, wzrasta wraz z liczbą warstw). Zamiast tego, bardziej nowoczesne metody regularyzacji, takie jak normalizacja partii i ścieżka-SGD, odpowiadają dodatnio jednorodnej funkcji regularyzacji o takim samym stopniu jak , a porzucenie, choć nie pasujące dokładnie do tego frameworka, wykazuje silne podobieństwo do niego. To może wyjaśniać, dlaczego, aby uzyskać wysoką dokładność z CNN, i nie są wystarczające, ale musimy zastosować wszelkiego rodzaju diabelskie sztuczki, takie jak rezygnacja i normalizacja partii! Zgodnie z moją najlepszą wiedzą jest to najbliższe wytłumaczenie skuteczności normalizacji partii, która poza tym jest bardzo niejasna, jak słusznie zauważył Al Rahimi w swoim wystąpieniu.Φ l1 l2
Kolejnym spostrzeżeniem, które niektórzy robią na podstawie Twierdzenia 1 , jest to, że mogłoby to wyjaśnić, dlaczego ReLU działa dobrze, nawet w przypadku problemu martwych neuronów . Zgodnie z tą intuicją fakt, że podczas treningu niektóre neurony ReLU „giną” (idą do aktywacji zerowej, a następnie nigdy się z niej nie regenerują, ponieważ dla gradient ReLU wynosi zero) jest „cechą, a nie błędem „, ponieważ jeśli osiągnęliśmy minimum i umarła pełna podsieć, to prawdopodobnie osiągnęliśmy globalne minimum (zgodnie z hipotezami Twierdzenia 1x<0 ). Być może czegoś mi brakuje, ale myślę, że ta interpretacja jest zbyt daleko idąca. Przede wszystkim podczas szkolenia ReLU mogą „umrzeć” na długo przed osiągnięciem lokalnego minimum. Po drugie, należy udowodnić, że kiedy jednostki ReLU „umierają”, zawsze robią to w pełnej podsieci: jedynym przypadkiem, gdy jest to trywialnie prawdziwe, jest tylko jedna ukryta warstwa, w którym to przypadku oczywiście każdy pojedynczy neuron jest podsieć. Ale ogólnie byłbym bardzo ostrożny, widząc „martwe neurony” jako dobrą rzecz.
Bibliografia:
B. Haeffele i R. Vidal, Globalna optymalizacja w szkoleniu w sieci neuronowej , Na konferencji IEEE nt. Wizji komputerowej i rozpoznawania wzorców, 2017.
B. Haeffele i R. Vidal. Globalna optymalizacja w rozkładzie na czynniki tensorowe, głębokie uczenie się i nie tylko , arXiv, abs / 1506.07540, 2015.
Klasyfikacja obrazów wymaga uczenia się reprezentacji, które są niezmienne (lub przynajmniej solidne, tj. Bardzo słabo wrażliwe) na różne transformacje, takie jak lokalizacja, poza, punkt widzenia, oświetlenie, ekspresja itp., Które są zwykle obecne na naturalnych obrazach, ale nie zawierają informacji do zadania klasyfikacyjnego. To samo dotyczy rozpoznawania mowy: zmiany wysokości, głośności, tempa, akcentu. itp. nie powinny prowadzić do zmiany klasyfikacji tego słowa. Operacje takie jak splot, maksymalna pula, średnia pula itp. Stosowane w sieciach CNN mają dokładnie ten cel, dlatego intuicyjnie oczekujemy, że będą działać w tych aplikacjach. Ale czy mamy twierdzenia na poparcie tej intuicji? Istnieje twierdzenie o niezmienności translacji pionowej, która, niezależnie od nazwy, nie ma nic wspólnego z tłumaczeniem w kierunku pionowym, ale jest to w zasadzie wynik, który mówi, że cechy wyuczone w kolejnych warstwach stają się coraz bardziej niezmienne w miarę wzrostu liczby warstw. Jest to sprzeczne ze starszym twierdzeniem o niezmienności translacji poziomej, które jednak dotyczy sieci rozpraszania, ale nie CNN. Twierdzenie to jest jednak bardzo techniczne:
Wskaż za pomocą wyjście warstwy CNN, gdy wejściem jest . Wreszcie:Φn(f) n f
(potrójne słupki nie są błędem), co w zasadzie oznacza, że każda warstwa uczy się cech, które stają się coraz bardziej niezmienne, a na granicy nieskończenie głębokiej sieci mamy doskonale niezmienną architekturę. Ponieważ CNN mają skończoną liczbę warstw, nie są one niezmiennie niezmienne w tłumaczeniu, co jest dobrze znane praktykom.
Odniesienia: T. Wiatowski i H. Bolcskei, A Mathematical Theory of Deep Convolutional Neural Networks for Extraction , arXiv: 1512.06293v3 .
Podsumowując, liczne granice błędu uogólnienia głębokiej sieci neuronowej opartej na wymiarze Vapnika-Chervonkensisa lub złożoności Rademachera rosną wraz z liczbą parametrów (niektóre nawet wykładniczo), co oznacza, że nie potrafią wyjaśnić, dlaczego DNN działają tak dobrze w praktyce, nawet gdy liczba parametrów jest znacznie większa niż liczba próbek treningowych. W rzeczywistości teoria VC nie jest zbyt przydatna w głębokim uczeniu się.
I odwrotnie, niektóre wyniki z ubiegłego roku wiązały błąd uogólnienia klasyfikatora DNN z wielkością niezależną od głębokości i wielkości sieci neuronowej, ale zależną tylko od struktury zestawu treningowego i przestrzeni wejściowej. Zgodnie z kilkoma dość technicznymi założeniami dotyczącymi procedury uczenia się, zestawu treningowego i przestrzeni wejściowej, ale z bardzo małymi założeniami dotyczącymi DNN (w szczególności CNN są w pełni uwzględnione), to z prawdopodobieństwem co najmniej mamy1−δ
gdzie:
J. Sokolic, R. Giryes, G. Sapiro i M. Rodrigues. Błąd uogólnienia niezmiennych klasyfikatorów . W AISTATS, 2017
źródło
See [here] for a modern exposition
lub na odwrót”.Myślę, że następujące twierdzenie, na które się powołujesz, jest uważane za dość fundamentalne w nauce statystycznej.
Twierdzenie (Vapnik i Chervonenkis, 1971) Niech będzie klasą hipotez funkcji z dziedziny do i niech funkcją straty będzie strata . Następnie następujące są równoważne:H X {0,1} 0−1
Udowodniono w wersji ilościowej tutaj:
VN Vapnik i AY Chervonenkis: O jednolitej zbieżności względnych częstotliwości zdarzeń z ich prawdopodobieństwami. Teoria prawdopodobieństwa i jej zastosowania, 16 (2): 264–280, 1971.
Wersja sformułowana powyżej wraz z ładną prezentacją innych wyników teorii uczenia się jest dostępna tutaj :
Shalev-Shwartz, Shai i Shai Ben-David. Zrozumienie uczenia maszynowego: od teorii do algorytmów. Prasa uniwersytecka Cambridge, 2014.
źródło
Sztuczka jądra to ogólny pomysł, który jest używany w wielu miejscach i pochodzi z wielu abstrakcyjnych matematyki na temat Hilberta Spacesa. Zbyt wiele teorii, by napisać (skopiować ...) tutaj, aby znaleźć odpowiedź, ale jeśli przejrzysz to, możesz uzyskać dobry pomysł na jej rygorystyczne podstawy:
http://www.stats.ox.ac.uk/~sejdinov/teaching/atml14/Theory_2014.pdf
źródło
Moim ulubionym jest nierówność Krafta.
Ta nierówność wiąże się z kompresją z gęstościami prawdopodobieństwa : biorąc pod uwagę kod, długość wyniku reprezentowanego przez ten kod jest ujemnym prawdopodobieństwem logicznym modelu zidentyfikowanego przez kod.
Co więcej, twierdzenie o braku darmowego lunchu dla uczenia maszynowego ma mniej znane twierdzenie o braku hiper kompresji, które stwierdza, że nie wszystkie sekwencje można skompresować.
źródło
Nie nazwałbym tego głównym twierdzeniem, ale myślę, że następujące (czasem określane jako uniwersalne twierdzenie aproksymacyjne) jest interesujące (i przynajmniej dla mnie zaskakujące), ponieważ podaje przybliżoną moc sprzężonych sieci neuronowych.
Twierdzenie: Niech będzie nietrwałą i monotynicznie rosnącą funkcją ciągłą. Dla każdej funkcji continuos i dowolnego istnieje liczba całkowita i wielowarstwowy perceptron z jedną ukrytą warstwą posiadającą neuronów, które mają jako aktywację działają tak, żeσ f:[0,1]m→R ϵ>0 N F N σ
Oczywiście, ponieważ jest to stwierdzenie o istnieniu , jego wpływ na praktyków jest znikomy.
Dowód można znaleźć w Hornik, Aproximation Capabilities of Muitilayer Feedforward Networks, Neural Networks 4 (2), 1991,
źródło
Miły post skupiający się na tym pytaniu (w szczególności głębokie uczenie się zamiast ogólnych twierdzeń o uczeniu maszynowym) znajduje się tutaj:
https://medium.com/mlreview/modern-theory-of-deep-learning-why-does-it-works-so-well-9ee1f7fb2808
Daje dostępne podsumowanie głównych pojawiających się twierdzeń o zdolności tak głębokich uogólnień głębokich sieci neuronowych.
źródło