Jak zdefiniować warunek zakończenia opadania gradientu?

24

Właściwie chciałem zapytać, jak mogę zdefiniować warunek końcowy zejścia gradientu.

Czy mogę to zatrzymać na podstawie liczby iteracji, tj. Biorąc pod uwagę wartości parametrów, powiedzmy, 100 iteracji?

A może powinienem poczekać, aż różne wartości dwóch parametrów „nowy” i „stary” będą bardzo małe w stosunku do powiedzmy ? To na pewno zajmie dużo czasu.10-6

Jaki jest najlepszy sposób? W moim przypadku nawet jedna iteracja zajmuje dużo czasu. W tej sytuacji, jeśli poczekam na drugi warunek, może to potrwać nawet tygodnie.

Którego podejścia powinienem użyć. Jak poradzić sobie z tym scenariuszem?

użytkownik31820
źródło
1
Nie jest to wyraźnie określone, ale zakładam, że próbujesz znaleźć MLE. Twój wynik naprawdę zależy całkowicie od przestrzeni parametrów, funkcji prawdopodobieństwa i potrzeb (czyli najlepiej nie jest dobrze zdefiniowany). Jeśli szukasz tylko teoretycznego uzasadnienia, takiego jak skuteczność asymptotyczna; w warunkach Le'Cam możesz po prostu użyć jednoetapowego MLE (przy dalszym założeniu jest to, że używasz metody Newtona i funkcji punktacji do zejścia gradientu). Wymaga to, że wartość początkowa jest taka, że prawdopodobieństwa. n1/2)θ^0θ
Jonathan Lisic
więc poczekaj, kiedy powiesz, że „nowy” - „stary” jest wystarczająco mały, czy jest to niepoprawny warunek zakończenia dla spadku gradientu? (jeśli mają zastosowanie twierdzenia o punkcie stałym, warunek ten powinien być w porządku?)
Charlie Parker
fajafajaxja3)×2)ftolabs ftolrelxtolabs

Odpowiedzi:

19

Fajne pytanie. W literaturze widziałem wiele zasad zatrzymania, a każda z nich ma swoje zalety i wady, w zależności od kontekstu. Na przykład optimfunkcja w R ma co najmniej trzy różne reguły zatrzymania:

  • maxit, tj. z góry określona maksymalna liczba iteracji. Inną podobną alternatywą, którą widziałem w literaturze, jest maksymalna liczba sekund przed upływem limitu czasu. Jeśli potrzebujesz jedynie przybliżonego rozwiązania, może to być bardzo rozsądne. W rzeczywistości istnieją klasy modeli (szczególnie modele liniowe), dla których wczesne zatrzymanie jest podobne do umieszczania Gaussa przed wartościami parametrów. Częstochowiec powiedziałby, że masz „normę L2”, a nie przeor, ale uważałby to również za rozsądną rzecz. Przeczytałem tylko ten artykuł , ale mówi on o związku między wczesnym zatrzymaniem a regularyzacją i może pomóc w uzyskaniu dalszych informacji. Ale krótka wersja jest, tak, wczesne zatrzymanie może być całkowicie szanowaną rzeczą, w zależności od tego, co „

  • abstol, tzn. zatrzymać, gdy funkcja „dostatecznie zbliży się” do zera. Może to nie być dla ciebie odpowiednie (nie brzmi to tak, jakbyś oczekiwał zera), więc pominę go.

  • reltol, co jest twoją drugą sugestią - przestań, gdy poprawa spadnie poniżej progu. Właściwie to nie wiem, ile teorii jest na ten temat, ale prawdopodobnie będziesz w ten sposób uzyskiwać niższe minima w ten sposób niż przy małej maksymalnej liczbie iteracji. Jeśli jest to dla Ciebie ważne, warto uruchomić kod, aby uzyskać więcej iteracji.

Inna rodzina reguł zatrzymywania ma związek z optymalizacją funkcji kosztów w zbiorze danych walidacyjnych (lub w walidacji krzyżowej), a nie w danych szkoleniowych. W zależności od tego, do czego chcesz używać swojego modelu, możesz dobrze zatrzymać się, zanim osiągniesz lokalne minimum danych treningowych, ponieważ może to wiązać się z przeregulowaniem. Jestem pewien, że Trevor Hastie napisał o dobrych sposobach na zrobienie tego, ale nie pamiętam cytatu.

Inne możliwe opcje znalezienia niższych minimów w rozsądnym czasie mogą obejmować:

  • Stochastyczne zejście gradientu, które wymaga jedynie oszacowania gradientów dla małej części danych na raz (np. Jeden punkt danych dla „czystego” SGD lub małych mini-partii).

  • Bardziej zaawansowane funkcje optymalizacji (np. Metody typu Newtona lub gradient koniugatu), które wykorzystują informacje o zakrzywieniu funkcji celu, aby pomóc ci wskazać lepsze kierunki i podjąć większe rozmiary kroków podczas zjazdu.

  • Określenie „pędu” w regule aktualizacji, dzięki czemu optymalizator lepiej zsuwa się niż zjeżdżając ze ścian kanionu w funkcji celu.

Wszystkie te podejścia zostały omówione w notatkach z wykładów, które znalazłem w Internecie.

Mam nadzieję że to pomoże!

Edytuj och, a także możesz spróbować uzyskać lepsze wartości początkowe (np. Rozwiązując prostszą wersję problemu), aby mniej iteracji wymagało mniejszej liczby iteracji, aby osiągnąć optymalny poziom od „ciepłego startu”.

David J. Harris
źródło
problem z wybraniem stałej liczby iteracji polega na tym, że jeśli nie można wyraźnie wykreślić krzywej kosztów (i ma mały szum), trudno jest ustalić, ile iteracji jest zbyt wielu, szczególnie jeśli funkcja optymalizacji jest skomplikowana i kto wie ile ma lokalnych minimów i jeśli masz losową inicjalizację, to dodatkowo pogarsza problem, ponieważ jeszcze trudniej zgadnąć, co jest dobrą „małą” liczbą iteracji. Jak rozwiązać te problemy w rzeczywistości, jeśli chcesz faktycznie skorzystać z wczesnego zatrzymania? W jaki sposób upewniasz się, że nie przesadzasz i nie przesadzasz?
Charlie Parker,
Chciałbym wyjaśnić, co reltol(tj. Kiedy przestaje być „poprawa”) oznacza. Pierwsza poprawa oznacza zmniejszenie funkcji kosztów. Zakładam więc, że masz na myśli to, że kiedy funkcja kosztu przestaje wystarczająco zmniejszać się (lub zaczyna rosnąć), jeden przestaje, prawda? Tak naprawdę nie robi się „| stary - nowy |” rodzaj reguły aktualizacji, prawda?
Charlie Parker,
1
Ten abstolparametr ma sens tylko wtedy, gdy przyjmuje się tolerancję gradientu funkcji kosztu, a nie samą funkcję kosztu. W lokalnym optymalizatorze wartość gradientu wynosi zero; ale nie wartość funkcji.
Mario Becerra,
„ciepły start” to bardzo sprytna sztuczka! dzięki
Mehdi LAMRANI