Was bedeutet es für einen Algorithmus, zu konvergieren?

Ich stoße immer wieder auf diesen Begriff, wenn ich über das Lernen der Verstärkung lese, zum Beispiel in diesem Satz:

Wenn das Problem sorgfältig modelliert wird, können einige Reinforcement Learning-Algorithmen zum globalen Optimum konvergieren

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

oder hier:

Für jede feste Richtlinie Pi wurde nachgewiesen, dass der oben beschriebene TD-Algorithmus gegen VPi konvergiert

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

Mein Verständnis des Wortes Konvergenz ist, dass es bedeutet, dass mehrere Dinge zum selben Punkt zusammenkommen, aber wie kann eine einzelne Sache (der Algorithmus) das tun?

Ein iterativer Algorithmus konvergiert, wenn die Ausgabe im Verlauf der Iterationen einem bestimmten Wert immer näher kommt. Genauer gesagt, egal wie klein ein Fehlerbereich ist, wenn Sie lange genug fortfahren, bleibt die Funktion schließlich innerhalb dieses Fehlerbereichs um den Endwert.

Unter bestimmten Umständen konvergiert ein Algorithmus nicht und hat eine Ausgabe, die immer um einen bestimmten Betrag variiert. Es könnte sogar divergieren, wenn seine Ausgabe immer größeren Wertschwankungen unterliegt und sich niemals einem nützlichen Ergebnis nähert. Genauer gesagt, egal wie lange Sie fortfahren, der Funktionswert wird sich niemals in einem Bereich eines "endgültigen" Werts niederlassen.

Die Phrase "Konvergenz zu einem globalen Optimum" in Ihrem ersten Satz bezieht sich auf Algorithmen, die konvergieren können, jedoch nicht auf den "optimalen" Wert (z. B. einen Algorithmus zum Bergsteigen, der je nach Funktion und Anfangsbedingungen konvergieren kann ein lokales Maximum, das niemals das globale Maximum erreicht).

Was ist Konvergenz im Allgemeinen?

Das Konzept der Konvergenz ist ein genau definierter mathematischer Begriff. Dies bedeutet im Wesentlichen, dass "irgendwann" eine Folge von Elementen einem einzelnen Wert immer näher kommt. Wir nennen diesen Einzelwert das "Limit".

Die formale Definition sieht ungefähr so ​​aus:

Given (unendliche) Folge von reellen Zahlen X0, X1, X2, ... Xn ...wir sagen , Xn converges to a given number Lwenn für jeden positiven Fehler , dass Sie denken, es ist ein , Xmso dass jedes Element , Xndas nach dem kommt Xmvon unterscheiden sich Lum weniger als dieser Fehler.

Beispiel:

Stellen Sie sich eine Sequenz als solche vor:

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

Konvergiert Xn gegen Null? Ja! Warum?

Denken Sie an einen Fehler E (zum Beispiel E = 0.0025). Gibt es ein Element in der Sequenz, in dem sich danach jedes Element befindet 0.025? Ja! Dieses Element ist X3 = 0.001. Nach X2 ist jeder XNunten 0.0025. Kann dies mit jedem E> 0 gemacht werden? Ja. Für jeden positiven Fehler, den wir auswählen, können wir sehen, wie viele Nullen er vor seinem ersten Dezimalpunkt hat, und die Folge ist niedriger als ab dem Element, das die gleiche Anzahl von Nullen hat.

Das bedeutet das Xn = 1/(10^5) converges to 0. Wie in "es kann immer näher an Null kommen", so viel wir wollen.

Was bedeutet es für einen Algorithmus, zu konvergieren?

"Technisch" konvergiert nicht der Algorithmus, sondern ein Wert, den der Algorithmus manipuliert oder iteriert. Nehmen wir zum Beispiel an, wir schreiben einen Algorithmus, der alle Ziffern von PI druckt.

Der Algorithmus beginnt mit dem Drucken von Zahlen wie:

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

Wir könnten uns fragen: Druckt der Algorithmus Zahlen immer näher an PI? Mit anderen Worten, X0, X1, ... XN ...konvergiert die Sequenz , die unser Algorithmus druckt, gegen PI?

Wenn ja, sagen wir, dass unser Algorithmus zu PI konvergiert.

Wir sind normalerweise daran interessiert, die Richtigkeit eines Algorithmus zu beweisen.

Wenn wir einen Algorithmus schreiben, sind wir normalerweise daran interessiert zu wissen, ob die vom Algorithmus bereitgestellte Lösung die richtige für das Problem ist, das er löst. Dies kann manchmal in Form einer Konvergenz auftreten.

Im Allgemeinen haben Algorithmen sogenannte Metriken . Eine Metrik ist eine Zahl, die wir einem bestimmten Ergebnis geben, das der Algorithmus erzeugt. Beispielsweise ist es bei iterativen AI / Machine Learning-Algorithmen sehr häufig, dass wir den "Fehler" verfolgen, den der Algorithmus basierend auf der Eingabe generiert. Dieser Fehler ist eine Metrik.

In diesen iterativen Algorithmen erzeugt jeder Schritt einen anderen Fehler. Der Algorithmus versucht, diesen Fehler so gering wie möglich zu halten, damit er immer kleiner wird. Wir sagen, dass der Algorithmus konvergiert, wenn die Fehlerfolge konvergiert.

In diesen Fällen wird das global optimumnormalerweise als das Setup definiert, das den geringstmöglichen Fehler aufweist. In diesem Fall bedeutet "Algorithmus konvergiert gegen das globale Optimum", dass "der Algorithmus Fehler in einer Sequenz erzeugt, die gegen den niedrigstmöglichen Fehler konvergiert".

Wenn das "globale Optimum" unsere "richtige Lösung" ist, entspricht die Aussage, dass unser Algorithmus konvergiert, der Aussage, dass unser Algorithmus korrekt ist.

Denken Sie auch daran, dass die Angabe, dass ein Algorithmus konvergiert, einen Beweis erfordert (wie wir es für unser Beispiel 0,001, 0,0001, ... getan haben).

Als Beispiel ein Klassifikator

Ein Beispiel hierfür könnte ein Klassifikator sein. Angenommen, wir möchten mithilfe eines Algorithmus für maschinelles Lernen klassifizieren, ob Zahlen ungerade oder gerade sind, und wir haben den folgenden Datensatz:

• (1, ungerade)
• (2, gerade)
• (3, ungerade)
• (77, ungerade)
• (4, gerade)

Unser Algorithmus für jeden Satz von Zahlen spuckt für jeden von ihnen, wenn sie gerade oder ungerade sind. Dazu können wir einen Metrikfehler so definieren, wie oft er falsch war, geteilt durch die Gesamtzahl der angegebenen Elemente.

Wenn unser Algorithmus also Folgendes ausspuckt:

• (1, gerade) // falsch
• (2, gerade)
• (3, gerade) // falsch
• (77, gerade) // falsch
• (4, gerade)

Unsere Fehlermetrik wäre 3/5 = 0.6. Nehmen wir jetzt an, wir führen den Algorithmus erneut aus und er spuckt jetzt:

• (1, gerade) // falsch
• (2, gerade)
• (3, ungerade)
• (77, ungerade)
• (4, gerade)

Unsere Fehlermetrik wäre 1/5 = 0.2.

Nehmen wir an, es wird immer öfter ausgeführt, und unsere Fehlerfolge sieht ungefähr so ​​aus:

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

Die große Frage ist also: Wird unser Algorithmus jemals Null sein? Wird es jemals gegen Null konvergieren? Wird unser Algorithmus alle konvergieren? Können wir beweisen, dass es irgendwann richtig wird (oder so nah wie möglich am richtigen)?

Hoffentlich ja :)