Wyjaśnienie dotyczące reguły Perceptron vs. Gradient Descent vs. Stochastic Gradient Descent

15

Eksperymentowałem trochę z różnymi implementacjami Perceptron i chcę się upewnić, czy poprawnie rozumiem „iteracje”.

Oryginalna reguła perceptronowa Rosenblatta

O ile rozumiem, w klasycznym algorytmie perceptronowym Rosenblatta wagi są jednocześnie aktualizowane po każdym przykładzie treningu za pośrednictwem

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

gdzie eta jest tutaj zasadą uczenia się. A wartość docelowa i rzeczywista są progowe (-1 lub 1). Zaimplementowałem to jako 1 iteracja = 1 przejście przez próbkę treningową, ale wektor masy jest aktualizowany po każdej próbce treningowej.

I obliczam „rzeczywistą” wartość jako

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

Spadek gradientu stochastycznego

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

To samo co reguła perceptronowa targeti actualnie są progami, ale wartościami rzeczywistymi. Ponadto liczę „iterację” jako ścieżkę nad próbką treningową.

Zarówno SGD, jak i klasyczna reguła perceptronowa zbiegają się w tym przypadku rozdzielanym liniowo, jednak mam problemy z implementacją spadku gradientu.

Spadek gradientu

Tutaj przeglądam próbkę treningową i podsumowuję zmiany masy dla 1 przejścia nad próbką treningową, a następnie aktualizuję wagi, np.

dla każdej próbki treningowej:

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

...

po 1 przejściu przez zestaw treningowy:

Δw+=Δwnew

Zastanawiam się, czy to założenie jest poprawne, czy coś mi brakuje. Próbowałem różnych (nawet nieskończenie małych) wskaźników uczenia się, ale nigdy nie udało mi się uzyskać żadnych oznak konwergencji. Zastanawiam się więc, czy coś źle zrozumiałem. tutaj.

Dzięki, Sebastian


źródło

Odpowiedzi:

20

Masz kilka błędów w swoich aktualizacjach. Myślę, że ogólnie mylisz wartość bieżących wag z różnicą między aktualnymi wagami a poprzednimi wagami. Masz symbole rozrzucone w miejscach, gdzie nie powinno ich być, a + = tam, gdzie powinieneś mieć =.Δ

Perceptron:

ww(t+1)=ww(t)+ηt(y(i)y^(i))xx(i)

y^(i)=sign(wwxx(i))ith

Można to postrzegać jako stochastyczną metodę zstępowania podskładnego na następującej funkcji „utraty perceptronu” *:

Utrata perceptronu:

Lww(y(i))=max(0,y(i)wwxx(i))

Lww(y(i))={0}, if y(i)wwxx(i)>0{y(i)xx(i)}, if y(i)wwxx(i)<0[1,0]×y(i)xx(i), if wwxx(i)=0

Ponieważ perceptron jest już formą SGD, nie jestem pewien, dlaczego aktualizacja SGD powinna być inna niż aktualizacja perceptronu. Sposób, w jaki napisałeś krok SGD, z wartościami nieprogowymi, powoduje utratę, jeśli zbyt poprawnie przewidujesz odpowiedź . To źle.

Krok gradientu wsadowego jest nieprawidłowy, ponieważ używasz „+ =”, kiedy powinieneś używać „=”. Bieżące wagi są dodawane dla każdej instancji treningowej . Innymi słowy, sposób, w jaki to napisałeś,

ww(t+1)=ww(t)+i=1n{ww(t)ηtLww(t)(y(i))}

To powinno być:

ww(t+1)=ww(t)ηti=1nLww(t)(y(i)).

Also, in order for the algorithm to converge on every and any data set, you should decrease your learning rate on a schedule, like ηt=η0t.


* The perceptron algorithm is not exactly the same as SSGD on the perceptron loss. Usually in SSGD, in the case of a tie (wwxx(i)=0), L=[1,0]×y(i)xx(i), so 00L, so you would be allowed to not take a step. Accordingly, perceptron loss can be minimized at ww=00, which is useless. But in the perceptron algorithm, you are required to break ties, and use the subgradient direction y(i)xx(i)L if you choose the wrong answer.

So they're not exactly the same, but if you work from the assumption that the perceptron algorithm is SGD for some loss function, and reverse engineer the loss function, perceptron loss is what you end up with.

Sam Thomson
źródło
Thank you Sam, and I do apologize for my messy question. I don't know where the deltas come from, but the "+=" was the the thing that went wrong. I completely overlooked that part. Thanks for the thorough answer!