Online-Maschinelles Lernen - Online machine learning

Teil einer Serie über
Maschinelles Lernen und Data Mining
Probleme Einstufung Clustering Rückschritt Anomalieerkennung AutoML Vereinsregeln Verstärkungslernen Strukturierte Vorhersage Feature-Engineering Feature-Lernen Online lernen Teilüberwachtes Lernen Unbeaufsichtigtes Lernen Rangieren lernen Grammatikeinführung
Überwachtes Lernen ( Klassifikation  • Regression ) Entscheidungsbäume Ensembles Absacken Erhöhen Zufälliger Wald k -NN Lineare Regression Naive Bayes Künstliche neurale Netzwerke Logistische Regression Perzeptron Relevanzvektormaschine (RVM) Support-Vektor-Maschine (SVM)
Clustering BIRKE HEILUNG Hierarchisch k -bedeutet Erwartung-Maximierung (EM) DBSCAN OPTIK Mittlere Verschiebung
Dimensionsreduktion Faktorenanalyse CCA ICA LDA NMF PCA PID t-SN
Strukturierte Vorhersage Grafische Modelle Bayes-Netz Bedingtes Zufallsfeld Versteckte Markov
Anomalieerkennung k -NN Lokaler Ausreißerfaktor
Künstliche neuronale Netz Autoencoder Kognitives Rechnen Tiefes Lernen DeepDream Mehrschichtiges Perzeptron RNN LSTM GRÜ ESN Eingeschränkte Boltzmann-Maschine GAN SO M Faltungsneurales Netzwerk U-Netz Transformator Spiking neuronales Netzwerk Speichertransistor Elektrochemischer RAM (ECRAM)
Verstärkungslernen Q-Lernen SARSA Zeitliche Differenz (TD)
Theorie Bias-Varianz-Kompromiss Computergestützte Lerntheorie Empirische Risikominimierung Occam-Lernen PAC-Lernen Statistisches Lernen VC-Theorie
Veranstaltungsorte für maschinelles Lernen NeurIPS ICML ML JMLR ArXiv:cs.LG
Verwandte Artikel Glossar der künstlichen Intelligenz Liste der Datensätze für die maschinelle Lernforschung Überblick über maschinelles Lernen
v T e

In der Informatik ist maschinelles Online-Lernen eine Methode des maschinellen Lernens, bei der Daten in einer sequentiellen Reihenfolge verfügbar werden und verwendet wird, um den besten Prädiktor für zukünftige Daten bei jedem Schritt zu aktualisieren, im Gegensatz zu Batch-Learning-Techniken, die den besten Prädiktor durch Lernen generieren auf den gesamten Trainingsdatensatz auf einmal. Online-Lernen ist eine gängige Technik, die in Bereichen des maschinellen Lernens verwendet wird, in denen es rechnerisch nicht möglich ist, den gesamten Datensatz zu trainieren, was die Notwendigkeit von Out-of-Core- Algorithmen erfordert . Es wird auch in Situationen verwendet, in denen der Algorithmus sich dynamisch an neue Muster in den Daten anpassen muss oder wenn die Daten selbst als Funktion der Zeit generiert werden, z. B. bei der Aktienkursvorhersage . Online-Lernalgorithmen können anfällig für katastrophale Störungen sein , ein Problem, das durch inkrementelle Lernansätze angegangen werden kann.

Einführung

Im Rahmen des überwachten Lernens soll eine Funktion von gelernt werden, die man sich als Input- und Output- Raum vorstellt, die gut auf Instanzen vorhersagt, die aus einer gemeinsamen Wahrscheinlichkeitsverteilung auf gezogen werden . In Wirklichkeit kennt der Lernende nie die wahre Verteilung über die Instanzen. Stattdessen hat der Lernende in der Regel Zugriff auf eine Reihe von Trainingsbeispielen . In dieser Einstellung wird die Verlustfunktion als angegeben , sodass die Differenz zwischen dem vorhergesagten Wert und dem wahren Wert gemessen wird . Das ideale Ziel ist es, eine Funktion auszuwählen , wobei ein Raum von Funktionen als Hypothesenraum bezeichnet wird, so dass ein gewisser Totalverlust minimiert wird. Je nach Modelltyp (statistisch oder kontradiktorisch) kann man sich unterschiedliche Verlustvorstellungen ausdenken, die zu unterschiedlichen Lernalgorithmen führen. ${\displaystyle f:X\to Y}$${\displaystyle X}$${\displaystyle Y}$ ${\displaystyle p(x,y)}$${\displaystyle X\times Y}$${\displaystyle p(x,y)}$${\displaystyle (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$${\displaystyle V:Y\times Y\to\mathbb{R}}$${\displaystyle V(f(x),y)}$${\displaystyle f(x)}$${\displaystyle y}$${\displaystyle f\in {\mathcal{H}}}$${\displaystyle {\mathcal{H}}}$

Statistische Ansicht des Online-Lernens

In statistischen Lernmodellen wird davon ausgegangen, dass die Trainingsstichprobe aus der wahren Verteilung gezogen wurde und das Ziel darin besteht, das erwartete "Risiko" zu minimieren. ${\displaystyle (x_{i},y_{i})}$${\displaystyle p(x,y)}$

${\displaystyle I[f]=\mathbb {E} [V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .}$

Ein gängiges Paradigma in dieser Situation ist die Schätzung einer Funktion durch empirische Risikominimierung oder regularisierte empirische Risikominimierung (normalerweise Tikhonov-Regularisierung ). Die Wahl der Verlustfunktion führt hier zu mehreren wohlbekannten Lernalgorithmen, wie zum Beispiel Regularized Least Squares und Support Vector Machines . Ein reines Online-Modell in dieser Kategorie würde nur auf der Grundlage der neuen Eingabe , des aktuell besten Prädiktors und einiger zusätzlich gespeicherter Informationen lernen (von denen normalerweise erwartet wird, dass sie unabhängig von der Trainingsdatengröße Speicheranforderungen haben). Für viele Formulierungen, zum Beispiel nichtlineare Kernel-Methoden , ist echtes Online-Lernen nicht möglich, obwohl eine Form des hybriden Online-Lernens mit rekursiven Algorithmen verwendet werden kann, wo es erlaubt ist, von und allen vorherigen Datenpunkten abzuhängen . In diesem Fall ist der Platzbedarf nicht mehr garantiert konstant, da alle vorherigen Datenpunkte gespeichert werden müssen, aber die Berechnung der Lösung mit dem Hinzufügen eines neuen Datenpunkts kann im Vergleich zu Batch-Lerntechniken weniger Zeit in Anspruch nehmen. ${\displaystyle {\hat {f}}}$${\displaystyle (x_{t+1},y_{t+1})}$${\displaystyle f_{t}}$${\displaystyle f_{t+1}}$${\displaystyle f_{t}}$${\displaystyle (x_{1},y_{1}),\ldots ,(x_{t},y_{t})}$

Eine gängige Strategie zur Überwindung der oben genannten Probleme besteht darin, mit Mini-Batches zu lernen, die jeweils eine kleine Menge von Datenpunkten verarbeiten. Dies kann als Pseudo-Online-Lernen betrachtet werden, das viel kleiner ist als die Gesamtzahl der Trainingspunkte. Mini-Batch-Techniken werden mit wiederholtem Übergeben der Trainingsdaten verwendet, um optimierte Out-of-Core-Versionen von maschinellen Lernalgorithmen zu erhalten, z. B. stochastischer Gradientenabstieg . In Kombination mit Backpropagation ist dies derzeit die de-facto-Trainingsmethode zum Training künstlicher neuronaler Netze . ${\displaystyle b\geq 1}$${\displaystyle b}$

Beispiel: Lineare kleinste Quadrate

Das einfache Beispiel der linearen kleinsten Quadrate wird verwendet, um eine Vielzahl von Ideen im Online-Lernen zu erklären. Die Ideen sind allgemein genug, um auf andere Einstellungen angewendet zu werden, beispielsweise mit anderen konvexen Verlustfunktionen.

Batch-Lernen

Betrachten Sie die Einstellung des überwachten Lernens mit einer zu lernenden linearen Funktion: ${\displaystyle f}$

${\displaystyle f(x_{j})=\langle w,x_{j}\rangle =w\cdot x_{j}}$

wobei ein Vektor von Eingaben (Datenpunkten) und ein linearer Filtervektor ist. Ziel ist es, den Filtervektor zu berechnen . Dazu wird eine quadratische Verlustfunktion ${\displaystyle x_{j}\in\mathbb{R}^{d}}$${\displaystyle w\in\mathbb{R}^{d}}$${\displaystyle w}$

${\displaystyle V(f(x_{j}),y_{j})=(f(x_{j})-y_{j})^{2}=(\langle w,x_{j}\rangle - j_{j})^{2}}$

wird verwendet, um den Vektor zu berechnen, der den empirischen Verlust minimiert ${\displaystyle w}$

${\displaystyle I_{n}[w]=\sum_{j=1}^{n}V(\langle w,x_{j}\rangle,y_{j})=\sum_{j=1} ^{n}(x_{j}^{T}w-y_{j})^{2}}$

wo

${\displaystyle y_{j}\in\mathbb{R}}$.

Sei die Datenmatrix und der Spaltenvektor der Sollwerte nach dem Eintreffen der ersten Datenpunkte. Unter der Annahme, dass die Kovarianzmatrix invertierbar ist (ansonsten ist es vorzuziehen, in ähnlicher Weise mit der Tikhonov-Regularisierung vorzugehen), ist die beste Lösung des linearen Kleinste-Quadrate-Problems gegeben durch ${\displaystyle X}$${\displaystyle i\times d}$${\displaystyle y\in\mathbb{R}^{i}}$${\displaystyle i}$${\displaystyle \Sigma_{i}=X^{T}X}$${\displaystyle f^{*}(x)=\langle w^{*},x\rangle}$

${\displaystyle w^{*}=(X^{T}X)^{-1}X^{T}y=\Sigma _{i}^{-1}\sum _{j=1}^{ i}x_{j}y_{j}}$.

Nun braucht die Berechnung der Kovarianzmatrix Zeit , das Invertieren der Matrix Zeit , während der Rest der Multiplikation Zeit braucht , was eine Gesamtzeit von ergibt . Wenn der Datensatz Gesamtpunkte enthält, um die Lösung nach dem Eintreffen jedes Datenpunkts neu zu berechnen , wird der naive Ansatz eine Gesamtkomplexität aufweisen . Beachten Sie, dass beim Speichern der Matrix , dann muss sie bei jedem Schritt aktualisiert werden, nur hinzugefügt werden muss , was Zeit in Anspruch nimmt , wodurch die Gesamtzeit auf reduziert wird , jedoch mit einem zusätzlichen Speicherplatz von to store . ${\displaystyle \Sigma_{i}=\sum_{j=1}^{i}x_{j}x_{j}^{T}}$${\displaystyle O(id^{2})}$${\displaystyle d\times d}$${\displaystyle O(d^{3})}$${\displaystyle O(d^{2})}$${\displaystyle O(id^{2}+d^{3})}$${\displaystyle n}$${\displaystyle i=1,\ldots,n}$${\displaystyle O(n^{2}d^{2}+nd^{3})}$${\displaystyle \Sigma_{i}}$${\displaystyle x_{i+1}x_{i+1}^{T}}$${\displaystyle O(d^{2})}$${\displaystyle O(nd^{2}+nd^{3})=O(nd^{3})}$${\displaystyle O(d^{2})}$${\displaystyle \Sigma_{i}}$

Online-Lernen: rekursive kleinste Quadrate

Der Algorithmus der rekursiven kleinsten Quadrate (RLS) betrachtet einen Online-Ansatz für das Problem der kleinsten Quadrate. Es kann gezeigt werden, dass durch Initialisieren von und die Lösung des linearen Kleinste-Quadrate-Problems aus dem vorherigen Abschnitt durch die folgende Iteration berechnet werden kann: ${\displaystyle \textstyle w_{0}=0\in \mathbb {R} ^{d}}$${\displaystyle \textstyle \Gamma_{0}=I\in\mathbb{R}^{d\times d}}$

${\displaystyle \Gamma_{i}=\Gamma_{i-1}-{\frac {\Gamma_{i-1}x_{i}x_{i}^{T}\Gamma_{i-1 }}{1+x_{i}^{T}\Gamma_{i-1}x_{i}}}}$

${\displaystyle w_{i}=w_{i-1}-\Gamma_{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})}$

Der obige Iterationsalgorithmus kann mit Induktion auf bewiesen werden . Das zeigt auch der Beweis . Man kann RLS auch im Zusammenhang mit adaptiven Filtern betrachten (siehe RLS ). ${\displaystyle i}$${\displaystyle \Gamma_{i}=\Sigma_{i}^{-1}}$

Die Komplexität für die Schritte dieses Algorithmus ist , was eine Größenordnung schneller ist als die entsprechende Batch-Lernkomplexität. Die Speicheranforderungen bei jedem Schritt hier bestehen darin, die Matrix zu speichern , die konstant bei ist . Für den Fall, wenn nicht invertierbar ist, betrachten Sie die regularisierte Version der Problemverlustfunktion . Dann ist es einfach zu zeigen, dass derselbe Algorithmus mit arbeitet und die Iterationen fortfahren, um zu ergeben . ${\displaystyle n}$${\displaystyle O(nd^{2})}$${\displaystyle i}$${\displaystyle \Gamma_{i}}$${\displaystyle O(d^{2})}$${\displaystyle \Sigma_{i}}$${\displaystyle \sum_{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}+\lambda ||w||_{2}^{2 }}$${\displaystyle \Gamma_{0}=(I+\lambda I)^{-1}}$${\displaystyle \Gamma_{i}=(\Sigma_{i}+\lambda I)^{-1}}$

Stochastischer Gradientenabstieg

Wenn das

${\displaystyle \textstyle w_{i}=w_{i-1}-\Gamma_{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})}$

wird ersetzt durch

${\displaystyle \textstyle w_{i}=w_{i-1}-\gamma_{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})=w_ {i-1}-\gamma_{i}\nabla V(\langle w_{i-1},x_{i}\rangle,y_{i})}$

oder durch wird dies der stochastische Gradientenabstiegsalgorithmus. In diesem Fall reduziert sich die Komplexität für die Schritte dieses Algorithmus auf . Der Speicherbedarf bei jedem Schritt ist konstant bei . ${\displaystyle \Gamma_{i}\in\mathbb{R}^{d\times d}}$${\displaystyle \gamma_{i}\in\mathbb{R}}$${\displaystyle n}$${\displaystyle O(nd)}$${\displaystyle i}$${\displaystyle O(d)}$

Die Schrittgröße muss jedoch sorgfältig gewählt werden, um das erwartete Risikominimierungsproblem zu lösen, wie oben beschrieben. Durch Wahl einer abfallenden Schrittweite kann man die Konvergenz der durchschnittlichen Iteration beweisen . Diese Einstellung ist ein Sonderfall der stochastischen Optimierung , ein bekanntes Problem bei der Optimierung. ${\displaystyle \gamma_{i}}$${\displaystyle \gamma_{i}\approx {\frac {1}{\sqrt {i}}},}$${\displaystyle {\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}}$

Inkrementeller stochastischer Gradientenabstieg

In der Praxis kann man mehrere stochastische Gradientendurchläufe (auch Zyklen oder Epochen genannt) über die Daten durchführen. Der so erhaltene Algorithmus heißt inkrementelles Gradientenverfahren und entspricht einer Iteration

${\displaystyle \textstyle w_{i}=w_{i-1}-\gamma_{i}\nabla V(\langle w_{i-1},x_{t_{i}}\rangle ,y_{t_{ ich}})}$

Der Hauptunterschied zum stochastischen Gradientenverfahren besteht darin, dass hier eine Sequenz gewählt wird, um zu entscheiden, welcher Trainingspunkt im -ten Schritt besucht wird. Eine solche Folge kann stochastisch oder deterministisch sein. Die Anzahl der Iterationen wird dann auf die Anzahl der Punkte entkoppelt (jeder Punkt kann mehrfach berücksichtigt werden). Es kann gezeigt werden, dass die inkrementelle Gradientenmethode das empirische Risiko minimiert. Inkrementelle Techniken können vorteilhaft sein, wenn objektive Funktionen betrachtet werden, die aus einer Summe vieler Terme bestehen, zB ein empirischer Fehler, der einem sehr großen Datensatz entspricht. ${\displaystyle t_{i}}$${\displaystyle i}$

Kernel-Methoden

Kernel können verwendet werden, um die obigen Algorithmen auf nicht-parametrische Modelle (oder Modelle, bei denen die Parameter einen unendlichen dimensionalen Raum bilden) zu erweitern. Das entsprechende Verfahren wird nicht mehr wirklich online sein, sondern alle Datenpunkte speichern, ist aber immer noch schneller als das Brute-Force-Verfahren. Diese Diskussion ist auf den Fall des quadratischen Verlustes beschränkt, obwohl sie auf jeden konvexen Verlust ausgedehnt werden kann. Es kann durch eine einfache Induktion gezeigt werden, dass wenn die Datenmatrix und die Ausgabe nach Schritten des SGD-Algorithmus ist, dann ${\displaystyle X_{i}}$${\displaystyle w_{i}}$${\displaystyle i}$

${\displaystyle w_{i}=X_{i}^{T}c_{i}}$

wo und die Sequenz die Rekursion erfüllt: ${\displaystyle \textstyle c_{i}=((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb{R}^{i}}$${\displaystyle c_{i}}$

${\displaystyle c_{0}=0}$

${\displaystyle (c_{i})_{j}=(c_{i-1})_{j},j=1,2,...,i-1}$ und

${\displaystyle (c_{i})_{i}=\gamma_{i}{\Big (}y_{i}-\sum_{j=1}^{i-1}(c_{i-1 })_{j}\langle x_{j},x_{i}\rangle {\Groß)}}$

Beachten Sie, dass hier nur der Standard-Kernel on ist und der Prädiktor die Form . hat ${\displaystyle \langle x_{j},x_{i}\rangle}$${\displaystyle \mathbb{R} ^{d}}$

${\displaystyle f_{i}(x)=\langle w_{i-1},x\rangle =\sum_{j=1}^{i-1}(c_{i-1})_{j} \langle x_{j},x\rangle}$.

Wenn nun stattdessen ein allgemeiner Kernel eingeführt wird und der Prädiktor sei ${\displaystyle K}$

${\displaystyle f_{i}(x)=\sum_{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x)}$

dann wird der gleiche Beweis auch zeigen, dass ein Prädiktor, der den Verlust durch kleinste Quadrate minimiert, erhalten wird, indem die obige Rekursion in geändert wird

${\displaystyle (c_{i})_{i}=\gamma_{i}{\Big (}y_{i}-\sum_{j=1}^{i-1}(c_{i-1 })_{j}K(x_{j},x_{i}){\Groß)}}$

Der obige Ausdruck erfordert das Speichern aller Daten zum Aktualisieren . Die Gesamtzeitkomplexität für die Rekursion bei der Auswertung für den -ten Datenpunkt beträgt , wobei die Kosten für die Auswertung des Kernels an einem einzelnen Punktpaar sind. Somit hat die Verwendung des Kernels die Bewegung von einem endlich dimensionalen Parameterraum zu einem möglicherweise unendlich dimensionalen Merkmal ermöglicht, das durch einen Kernel repräsentiert wird, indem stattdessen die Rekursion auf dem Parameterraum durchgeführt wurde , dessen Dimension die gleiche wie die Größe des Trainingsdatensatzes ist . Im Allgemeinen ist dies eine Folge des Repräsentantensatzes . ${\displaystyle c_{i}}$${\displaystyle n}$${\displaystyle O(n^{2}dk)}$${\displaystyle k}$${\displaystyle \textstyle w_{i}\in \mathbb {R} ^{d}}$${\displaystyle K}$${\displaystyle \textstyle c_{i}\in \mathbb {R} ^{i}}$

Online konvexe Optimierung

Online-konvexe Optimierung (OCO) ist ein allgemeiner Rahmen für die Entscheidungsfindung, der die konvexe Optimierung nutzt , um effiziente Algorithmen zu ermöglichen. Der Rahmen ist der des wiederholten Spiels wie folgt:

Für ${\displaystyle t=1,2,...,T}$

• Lernender erhält Input ${\displaystyle x_{t}}$
• Lernerausgaben aus einer festen konvexen Menge${\displaystyle w_{t}}$${\displaystyle S}$
• Die Natur sendet eine konvexe Verlustfunktion zurück .${\displaystyle v_{t}:S\rightarrow\mathbb{R}}$
• Der Lernende erleidet einen Verlust und aktualisiert sein Modell${\displaystyle v_{t}(w_{t})}$

Ziel ist es, Reue zu minimieren , oder die Differenz zwischen kumulativem Verlust und dem Verlust des besten Fixpunktes im Nachhinein. Betrachten Sie als Beispiel den Fall der linearen Online-Regression der kleinsten Quadrate. Hier kommen die Gewichtungsvektoren aus der konvexen Menge und die Natur sendet die konvexe Verlustfunktion zurück . Beachten Sie hier, dass implizit mit gesendet wird . ${\displaystyle u\in S}$${\displaystyle S=\mathbb{R} ^{d}}$${\displaystyle v_{t}(w)=(\langle w,x_{t}\rangle -y_{t})^{2}}$${\displaystyle y_{t}}$${\displaystyle v_{t}}$

Einige Online-Vorhersageprobleme passen jedoch nicht in den Rahmen von OCO. Bei der Online-Klassifizierung sind beispielsweise der Vorhersagebereich und die Verlustfunktionen nicht konvex. In solchen Szenarien werden zwei einfache Techniken zur Konvexisierung verwendet: Randomisierung und Surrogatverlustfunktionen.

Einige einfache online konvexe Optimierungsalgorithmen sind:

Folge dem Anführer (FTL)

Die einfachste Lernregel besteht darin, (im aktuellen Schritt) die Hypothese auszuwählen, die in allen vergangenen Runden den geringsten Verlust aufweist. Dieser Algorithmus heißt Follow the Leader und wird einfach rund gegeben durch: ${\displaystyle t}$

${\displaystyle w_{t}=\operatorname {arg\,min} _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)}$

Diese Methode kann daher als gieriger Algorithmus betrachtet werden . Für den Fall der quadratischen Online-Optimierung (bei der die Verlustfunktion ) ist, kann man eine Reue-Grenze zeigen, die als wächst . Für andere wichtige Modellfamilien wie die lineare Online-Optimierung können jedoch keine ähnlichen Grenzen für den FTL-Algorithmus erhalten werden. Dazu modifiziert man FTL, indem man Regularisierung hinzufügt. ${\displaystyle v_{t}(w)=||w-x_{t}||_{2}^{2}}$${\displaystyle\log(T)}$

Folgen Sie dem regulären Führer (FTRL)

Dies ist eine natürliche Modifikation von FTL, die verwendet wird, um die FTL-Lösungen zu stabilisieren und bessere Reue-Grenzen zu erzielen. Eine Regularisierungsfunktion wird gewählt und das Lernen wird in Runde t wie folgt durchgeführt: ${\displaystyle R:S\rightarrow\mathbb{R}}$

${\displaystyle w_{t}=\operatorname {arg\,min} _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)+R(w)}$

Als besonderes Beispiel betrachten wir den Fall der linearen Online-Optimierung, dh wo die Natur Verlustfunktionen der Form zurücksendet . Lassen Sie auch . Angenommen, die Regularisierungsfunktion wird für eine positive Zahl gewählt . Dann kann man zeigen, dass die bedauernsminimierende Iteration zu ${\displaystyle v_{t}(w)=\langle w,z_{t}\rangle}$${\displaystyle S=\mathbb{R} ^{d}}$${\displaystyle R(w)={\frac {1}{2\eta}}||w||_{2}^{2}}$${\displaystyle \eta}$

${\displaystyle w_{t+1}=-\eta \sum_{i=1}^{t}z_{i}=w_{t}-\eta z_{t}}$

Beachten Sie, dass dies als umgeschrieben werden kann , was genau wie der Online-Gradientenabstieg aussieht. ${\displaystyle w_{t+1}=w_{t}-\eta \nabla v_{t}(w_{t})}$

Wenn S stattdessen ein konvexer Unterraum von ist , müsste S auf projiziert werden, was zu der modifizierten Aktualisierungsregel führt ${\displaystyle \mathbb{R} ^{d}}$

${\displaystyle w_{t+1}=\Pi_{S}(-\eta\sum_{i=1}^{t}z_{i})=\Pi_{S}(\eta\theta_ {t+1})}$

Dieser Algorithmus wird als Lazy Projection bezeichnet, da der Vektor die Gradienten akkumuliert. Er ist auch als Dual-Averaging-Algorithmus von Nesterov bekannt. In diesem Szenario von linearen Verlustfunktionen und quadratischer Regularisierung ist das Reue durch begrenzt , und somit geht das durchschnittliche Reue wie gewünscht auf 0 . ${\displaystyle \theta_{t+1}}$${\displaystyle O({\sqrt {T}})}$

Online-Subgradient-Abstieg (OSD)

Das Obige erwies sich für lineare Verlustfunktionen als bedauerlicherweise . Um den Algorithmus auf eine beliebige konvexe Verlustfunktion zu verallgemeinern, wird der Subgradient von als lineare Annäherung an near verwendet , was zum Online-Subgradient-Abstiegsalgorithmus führt: ${\displaystyle v_{t}(w)=\langle w,z_{t}\rangle}$ ${\displaystyle \partial v_{t}(w_{t})}$${\displaystyle v_{t}}$${\displaystyle v_{t}}$${\displaystyle w_{t}}$

Parameter initialisieren ${\displaystyle \eta ,w_{1}=0}$

Für ${\displaystyle t=1,2,...,T}$

• Vorhersage mit , von der Natur erhalten.${\displaystyle w_{t}}$${\displaystyle f_{t}}$
• Wählen ${\displaystyle z_{t}\in \partial v_{t}(w_{t})}$
• Wenn , aktualisieren als${\displaystyle S=\mathbb{R} ^{d}}$${\displaystyle w_{t+1}=w_{t}-\eta z_{t}}$
• Wenn , projizieren Sie kumulative Farbverläufe auf ie${\displaystyle S\subset \mathbb{R}^{d}}$${\displaystyle S}$${\displaystyle w_{t+1}=\Pi_{S}(\eta\theta_{t+1}),\theta_{t+1}=\theta_{t}+z_{t}}$

Man kann den OSD-Algorithmus verwenden, um Reue-Grenzen für die Online-Version von SVMs zur Klassifizierung abzuleiten , die den Scharnierverlust verwenden${\displaystyle O({\sqrt {T}})}$${\displaystyle v_{t}(w)=\max\{0,1-y_{t}(w\cdot x_{t})\}}$

Andere Algorithmen

Quadratisch regularisierte FTRL-Algorithmen führen wie oben beschrieben zu faul projizierten Gradientenalgorithmen. Um das Obige für beliebige konvexe Funktionen und Regularisierer zu verwenden, verwendet man Online-Spiegelabstieg. Die im Nachhinein optimale Regularisierung lässt sich für lineare Verlustfunktionen ableiten, dies führt zum AdaGrad- Algorithmus. Für die euklidische Regularisierung lässt sich eine Reue-Schwelle von aufzeigen , die noch weiter verbessert werden kann für stark konvexe und exp-konkave Verlustfunktionen. ${\displaystyle O({\sqrt {T}})}$${\displaystyle O(\log T)}$

Kontinuierliches Lernen

Kontinuierliches Lernen bedeutet die ständige Verbesserung des gelernten Modells durch die Verarbeitung kontinuierlicher Informationsströme. Kontinuierliche Lernfähigkeiten sind für Softwaresysteme und autonome Agenten unerlässlich, die in einer sich ständig verändernden realen Welt interagieren. Kontinuierliches Lernen ist jedoch eine Herausforderung für maschinelles Lernen und neuronale Netzmodelle, da die kontinuierliche Erfassung inkrementell verfügbarer Informationen aus instationären Datenverteilungen in der Regel zu katastrophalem Vergessen führt .

Interpretationen des Online-Lernens

Das Paradigma des Online-Lernens hat je nach Wahl des Lernmodells unterschiedliche Interpretationen, von denen jede unterschiedliche Auswirkungen auf die Vorhersagequalität der Funktionsabfolge hat . Für diese Diskussion wird der prototypische stochastische Gradientenabstiegsalgorithmus verwendet. Wie oben erwähnt, ist seine Rekursion gegeben durch ${\displaystyle f_{1},f_{2},\ldots,f_{n}}$

${\displaystyle \textstyle w_{t}=w_{t-1}-\gamma_{t}\nabla V(\langle w_{t-1},x_{t}\rangle ,y_{t})}$

Die erste Interpretation betrachtet die Methode des stochastischen Gradientenabstiegs als Anwendung auf das oben definierte Problem der Minimierung des erwarteten Risikos . Da im Fall eines unendlichen Datenstroms angenommen wird, dass die Beispiele aus der Verteilung stammen , ist die Gradientenfolge von in der obigen Iteration tatsächlich eine Probe stochastischer Schätzungen des Gradienten des erwarteten Risikos und daher man kann Komplexitätsergebnisse für das stochastische Gradientenabstiegsverfahren anwenden, um die Abweichung zu begrenzen , wobei der Minimierer von ist . Diese Interpretation gilt auch im Fall einer endlichen Trainingsmenge; obwohl bei mehreren Durchläufen durch die Daten die Gradienten nicht mehr unabhängig sind, können dennoch in speziellen Fällen Komplexitätsergebnisse erhalten werden. ${\displaystyle I[w]}$${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),\ldots }$${\displaystyle p(x,y)}$${\displaystyle V(\cdot,\cdot)}$${\displaystyle I[w]}$${\displaystyle I[w_{t}]-I[w^{\ast}]}$${\displaystyle w^{\ast}}$${\displaystyle I[w]}$

Die zweite Interpretation gilt für den Fall eines endlichen Trainingssatzes und betrachtet den SGD-Algorithmus als eine Instanz des inkrementellen Gradientenabstiegsverfahrens. In diesem Fall betrachtet man stattdessen das empirische Risiko:

${\displaystyle I_{n}[w]={\frac {1}{n}}\sum _{i=1}^{n}V(\langle w,x_{i}\rangle ,y_{i} )\ .}$

Da die Gradienten von in den inkrementellen Gradientenabstiegsiterationen auch stochastische Schätzungen des Gradienten von sind , bezieht sich diese Interpretation auch auf die stochastische Gradientenabstiegsmethode, wird jedoch angewendet, um das empirische Risiko im Gegensatz zum erwarteten Risiko zu minimieren. Da diese Interpretation das empirische Risiko und nicht das erwartete Risiko betrifft, sind mehrere Durchläufe durch die Daten ohne weiteres zulässig und führen tatsächlich zu engeren Grenzen für die Abweichungen , wobei der Minimierer von ist . ${\displaystyle V(\cdot,\cdot)}$${\displaystyle I_{n}[w]}$${\displaystyle I_{n}[w_{t}]-I_{n}[w_{n}^{\ast }]}$${\displaystyle w_{n}^{\ast}}$${\displaystyle I_{n}[w]}$

Implementierungen

• Vowpal Wabbit : Open-Source, schnelles Out-of-Core-Online-Lernsystem, das sich durch die Unterstützung einer Reihe von Reduzierungen des maschinellen Lernens, einer Wichtigkeitsgewichtung und einer Auswahl verschiedener Verlustfunktionen und Optimierungsalgorithmen auszeichnet. Es verwendet den Hashing-Trick, um die Größe des Satzes von Merkmalen unabhängig von der Menge der Trainingsdaten zu begrenzen.
• scikit-learn : Bietet Out-of-Core-Implementierungen von Algorithmen für
  • Klassifizierung: Perceptron , SGD-Klassifikator , Naive Bayes-Klassifikator .
  • Regression: SGD-Regressor, passiver aggressiver Regressor.
  • Clustering: Mini-Batch-k-Mittel .
  • Merkmalsextraktion: Mini-Batch-Wörterbucherlernen , inkrementelle PCA .

Siehe auch

Lernparadigmen

• Inkrementelles Lernen
• Faules Lernen
• Offline-Lernen , das Gegenmodell
• Verstärkungslernen
• Überwachtes Lernen

Allgemeine Algorithmen

• Online-Algorithmus
• Online-Optimierung
• Streaming-Algorithmus
• Stochastischer Gradientenabstieg

Lernmodelle

• Adaptive Resonanztheorie
• Hierarchisches Zeitgedächtnis
• k-nächster Nachbar-Algorithmus
• Vektorquantisierung lernen
• Perzeptron

Verweise

Externe Links

• http://onlineprediction.net/ , Wiki für Online-Vorhersage.
• 6.883: Online-Methoden des maschinellen Lernens: Theorie und Anwendungen. Alexander Rakhlin. MIT