Erläuterung der Implementierung von Perceptron-Regel vs. Gradient Descent vs. Stochastic Gradient Descent

15

Ich habe ein wenig mit verschiedenen Perceptron-Implementierungen experimentiert und möchte sicherstellen, dass ich die "Iterationen" richtig verstehe.

Rosenblatts ursprüngliche Perzeptronregel

Soweit ich weiß, werden bei Rosenblatts klassischem Perzeptron-Algorithmus die Gewichte nach jedem Trainingsbeispiel gleichzeitig über aktualisiert

Δw(t+1)=Δw(t)+η(targetactual)xi

wo hier die ist. Und sowohl Ziel als auch Ist sind begrenzt (-1 oder 1). Ich habe es als 1 Iteration = 1 Durchlauf über die Trainingsprobe implementiert, aber der Gewichtsvektor wird nach jeder Trainingsprobe aktualisiert.eta

Und ich berechne den "tatsächlichen" Wert als

sign(wwTxx)=sign(w0+w1x1+...+wdxd)

Stochastische Gefälleabfahrt

Δw(t+1)=Δw(t)+η(targetactual)xi

Entspricht jedoch der Perceptron-Regel targetund actualist kein Schwellenwert, sondern ein reeller Wert. Außerdem zähle ich "Iteration" als Pfad über die Trainingsprobe.

Sowohl SGD als auch die klassische Perzeptron-Regel konvergieren in diesem linear trennbaren Fall. Ich habe jedoch Probleme mit der Implementierung des Gradientenabfalls.

Gradientenabstieg

Hier gehe ich über das Trainingsmuster und fasse die Gewichtsänderungen für 1 Durchgang über das Trainingsmuster zusammen und aktualisiere die Gewichte danach, z.

für jedes Trainingsmuster:

Δwnew+=Δw(t)+η(targetactual)xi

...

Nach 1 Durchgang über das Trainingsset:

Δw+=Δwnew

Ich frage mich, ob diese Annahme richtig ist oder ob mir etwas fehlt. Ich habe verschiedene (bis zu unendlich kleine) Lernraten ausprobiert, konnte aber nie Anzeichen von Konvergenz erkennen. Ich frage mich also, ob ich etwas falsch verstanden habe. Hier.

Danke, Sebastian


quelle

Antworten:

19

Sie haben einige Fehler in Ihren Updates. Ich denke, im Allgemeinen verwechseln Sie den Wert der aktuellen Gewichte mit der Differenz zwischen den aktuellen Gewichten und den vorherigen Gewichten. Sie haben Symbole verstreut, wo es keine geben sollte, und + = wo Sie = haben sollten.Δ

Perceptron:

ww(t+1)=ww(t)+ηt(y(ich)-y^(ich))xx(ich) ,

Dabei ist die Vorhersage des Modells auf dem Trainingsbeispiel.y^(ich)=Zeichen(wwxx(ich))ichth

Dies kann als stochastische Subgradienten-Abstiegsmethode für die folgende Funktion "Perzeptronverlust" angesehen werden *:

Perzeptronverlust:

Lww(y(ich))=max(0,-y(ich)wwxx(ich)) .

Lww(y(ich))={0}, wenn y(ich)wwxx(ich)>0{-y(ich)xx(ich)}, wenn y(ich)wwxx(ich)<0[-1,0]×y(ich)xx(ich), wenn wwxx(ich)=0 .

Da bereits Perzeptron ist eine Form von SGD, ich bin nicht sicher , warum die SGD - Update als das Perzeptron Update anders sein sollte. Die Art und Weise, wie Sie den SGD-Schritt mit nicht festgelegten Werten geschrieben haben, führt zu einem Verlust, wenn Sie eine Antwort zu korrekt vorhersagen . Das ist schlecht.

Ihr Batch-Gradientenschritt ist falsch, weil Sie "+ =" verwenden, wenn Sie "=" verwenden sollten. Die aktuellen Gewichte werden für jede Trainingsinstanz hinzugefügt . Mit anderen Worten, wie Sie es geschrieben haben,

ww(t+1)=ww(t)+ich=1n{ww(t)-ηtLww(t)(y(ich))} .

Was es sein sollte ist:

ww(t+1)=ww(t)-ηtich=1nLww(t)(y(ich)) .

Damit der Algorithmus für jeden Datensatz konvergiert, sollten Sie Ihre Lernrate nach einem Zeitplan verringern, z. B. .ηt=η0t


* Der Perzeptron-Algorithmus ist nicht genau derselbe wie die SSGD für den Perzeptronverlust. Normalerweise ist bei SSGD im Falle eines Gleichstands ( ) , also , damit Sie keinen Schritt machen dürfen. Dementsprechend kann der Perzeptronverlust bei minimiert werden , was unbrauchbar ist. Im Perceptron- Algorithmus müssen Sie jedoch die Bindungen unterbrechen und die Subgradientenrichtung wenn Sie die falsche Antwort wählen.wwxx(ich)=0L=[-1,0]×y(ich)xx(ich)00Lww=00-y(ich)xx(ich)L

Sie sind also nicht genau gleich, aber wenn Sie davon ausgehen, dass der Perceptron-Algorithmus für eine Verlustfunktion SGD ist und die Verlustfunktion rückentwickelt wird, ist Perceptron-Verlust das, was Sie am Ende haben.

Sam Thomson
quelle
Vielen Dank, Sam, und ich entschuldige mich für meine unordentliche Frage. Ich weiß nicht, woher die Deltas kommen, aber das "+ =" war das, was schief gelaufen ist. Ich habe diesen Teil völlig übersehen. Danke für die gründliche Antwort!