Co to znaczy, że algorytm jest zbieżny?

12

Cały czas spotykam się z tym terminem, czytając o uczeniu się przez wzmacnianie, na przykład w tym zdaniu:

Jeśli problem jest starannie modelowany, niektóre algorytmy uczenia się zbrojenia mogą zbiegać się do globalnego optimum

http://reinforcementlearning.ai-depot.com/

lub tu:

W przypadku dowolnej ustalonej polityki Pi udowodniono, że algorytm TD opisany powyżej jest zgodny z VPi

http://webdocs.cs.ualberta.ca/~sutton/book/ebook/node62.html

Rozumiem, że słowo zbieżne oznacza, że ​​oznacza to, że kilka rzeczy łączy się w tym samym punkcie, ale jak jedna rzecz (algorytm) może to zrobić?

algorithms machine-learning rozgwiazda
źródło
7
W przypadku algorytmów iteracyjnych mówi się, że są one zbieżne, gdy ich potencjalne rozwiązania dla każdej iteracji zbliżają się coraz bardziej do pożądanego rozwiązania.
MetaFight,
6
Może pomóc przypomnieć, że ograniczenie matematyczne mówi się, że albo zbieżne, albo rozbieżne, chociaż „limit” jest „pojedynczą rzeczą”.
Ixrec,
@Ixrec: „Limit” został nazwany na podstawie wartości, z którą con / dywerguje do / od. Np. Jak w „zbieżnym do 1”, co oznacza „nigdy nie przekracza 1”, co oznacza, że ​​„1 jest maksymalną wartością wynikową”, a zatem „granicą” twoich oczekiwań. Stąd liczba pojedyncza.
Flater

Odpowiedzi:

14

Algorytm iteracyjny mówi się zbiegać, gdy jako iteracje postępować, wyjście dostaje coraz bliżej jakiejś konkretnej wartości. Dokładniej, bez względu na to, jak mały wybierzesz zakres błędów, jeśli będziesz kontynuować wystarczająco długo, funkcja ostatecznie pozostanie w tym zakresie błędów wokół wartości końcowej.

W niektórych okolicznościach algorytm nie jest zbieżny, a jego wynik zawsze zmienia się o pewną wartość. Może nawet się różnić, gdzie jego wydajność będzie podlegać coraz większym wahaniom wartości, nigdy nie osiągając użytecznego wyniku. Dokładniej, bez względu na to, jak długo będziesz kontynuować, wartość funkcji nigdy nie ustabilizuje się w zakresie jakiejkolwiek „ostatecznej” wartości.

Wyrażenie „zbieżne do optymalnego globalnego” w pierwszym zdaniu odnosi się do algorytmów, które mogą się zbiegać, ale nie do wartości „optymalnej” (np. Algorytm wspinania się na wzgórze, który w zależności od funkcji i warunków początkowych może być zbieżny z lokalne maksimum, nigdy nie osiągające globalnego maksimum).

Daniel Griscom
źródło
3

Czym w ogóle jest konwergencja

Pojęcie konwergencji jest dobrze zdefiniowanym terminem matematycznym. Zasadniczo oznacza to, że „w końcu” sekwencja elementów zbliża się do jednej wartości. Tę pojedynczą wartość nazywamy „limitem”.

Formalna definicja wygląda mniej więcej tak:

Biorąc pod uwagę (nieskończoną) sekwencję liczb rzeczywistych, X0, X1, X2, ... Xn ...mówimy, że Xn converges to a given number Ljeśli dla każdego pozytywnego błędu, który myślisz, istnieje Xmtaki, że każdy element, Xnktóry następuje po nim, Xmróżni się Lo mniej niż ten błąd.

Przykład:

Wyobraź sobie taką sekwencję:

  • X0 = 1
  • X1 = 0,1
  • X2 = 0,01
  • X3 = 0,001
  • X4 = 0,0001
  • ...
  • Xn = 1 / (10 ^ n)

Czy Xn jest zbieżny do zera? Tak! Czemu?

Pomyśl o błędzie E (na przykład E = 0.0025). Czy w sekwencji jest jakiś element, po którym każdy element jest poniżej 0.025? Tak! Ten element to X3 = 0.001. Po X2 wszystko XNjest poniżej 0.0025. Czy można to zrobić dla każdego E> 0? Tak. Za każdy wybrany przez nas pozytywny błąd możemy zobaczyć, ile zer ma przed pierwszym punktem dziesiętnym, a sekwencja będzie niższa niż począwszy od elementu, który ma taką samą liczbę zer.

To znaczy że Xn = 1/(10^5) converges to 0. Jak w „może być coraz bliżej zera” tyle, ile chcemy.

Co to znaczy, że algorytm jest zbieżny?

„Technicznie” to, co jest zbieżne, nie jest algorytmem, ale wartością, którą algorytm manipuluje lub iteruje. Załóżmy na przykład, że piszemy algorytm, który drukuje wszystkie cyfry PI.

Algorytm rozpoczyna drukowanie liczb takich jak:

  • X0 = 3,14
  • X1 = 3,141
  • X2 = 3,1415
  • X3 = 3,14159
  • ...

Możemy zadać sobie pytanie: czy algorytm wypisuje liczby coraz bardziej zbliżone do PI? Innymi słowy, czy sekwencja X0, X1, ... XN ...drukowana przez nasz algorytm jest zbieżna z PI?

Jeśli tak, mówimy, że nasz algorytm jest zbieżny z PI.

Zazwyczaj jesteśmy zainteresowani udowodnieniem poprawności algorytmu.

Zwykle, gdy piszemy algorytm, jesteśmy zainteresowani, aby wiedzieć, czy rozwiązanie, które zapewnia algorytm, jest właściwe dla rozwiązania problemu. Czasami może to przybrać formę konwergencji.

Ogólnie algorytmy mają tak zwane metryki . Metryka to liczba, którą podajemy danemu wynikowi uzyskanemu przez algorytm. Na przykład w iteracyjnych algorytmach AI / Machine Learning bardzo często śledzimy „błąd” generowany przez algorytm na podstawie danych wejściowych. Ten błąd jest miarą.

W tych algorytmach iteracyjnych każdy krok generuje inny błąd. Algorytm próbuje zminimalizować ten błąd, aby był coraz mniejszy. Mówimy, że algorytm jest zbieżny, jeśli zbiega się sekwencja błędów.

W takich przypadkach global optimumjest to zwykle konfiguracja, w której występuje najniższy możliwy błąd. W takim przypadku „algorytm jest zbieżny z globalnym optimum” oznacza, że ​​„algorytm generuje błędy w sekwencji, która jest zbieżna z najmniejszym możliwym błędem”.

Jeśli „globalne optimum” jest naszym „poprawnym rozwiązaniem”, stwierdzenie, że nasz algorytm jest zbieżny, jest tym samym, co stwierdzenie, że nasz algorytm jest poprawny.

Należy również pamiętać, że stwierdzenie, że algorytm jest zbieżny, wymaga dowodu (tak jak w przypadku naszego przykładu 0,001, 0,0001, ...).

Na przykład klasyfikator

Przykładem może być w przypadku klasyfikatora. Załóżmy, że chcemy sklasyfikować, czy liczby są nieparzyste lub nawet wykorzystują algorytm uczenia maszynowego, i że mamy następujący zestaw danych:

  • (1, nieparzysty)
  • (2, nawet)
  • (3, nieparzysty)
  • (77, nieparzysty)
  • (4, nawet)

Nasz algorytm dla każdego zestawu liczb pluje dla każdego z nich, jeśli są parzyste lub nieparzyste. W tym celu możemy zdefiniować błąd metryczny jako liczbę przypadków, w których popełnił błąd, podzieloną przez całkowitą liczbę podanych elementów.

Jeśli więc nasz algorytm wypluwa następujące informacje:

  • (1, nawet) // źle
  • (2, nawet)
  • (3, nawet) // źle
  • (77, nawet) // źle
  • (4, nawet)

Nasz wskaźnik błędu to 3/5 = 0.6. Powiedzmy teraz, że ponownie uruchomimy algorytm i teraz pluje:

  • (1, nawet) // źle
  • (2, nawet)
  • (3, nieparzysty)
  • (77, nieparzysty)
  • (4, nawet)

Nasz wskaźnik błędu to 1/5 = 0.2.

Powiedzmy, że działa coraz więcej razy, a nasza sekwencja błędów wygląda mniej więcej tak:

0.6, 0.2, 0.1, 0.01, 0.000456, 0.00000543, 0.000000000444 ....

Główne pytanie brzmi: czy nasz algorytm wyzeruje się kiedykolwiek? Czy kiedykolwiek zbliży się do zera? Czy nasz algorytm będzie się zbieżny? Czy możemy udowodnić, że ostatecznie uda się to naprawić (lub jak najbliżej prawicy, jak to możliwe)?

Mam nadzieję, że tak :)

Albuquerque
źródło