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

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

$\Delta{w}^{(t+1)} = \Delta{w}^{(t)} + \eta(target - actual)x_i$

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 ({\pmb{w}^T\pmb{x}}) = sign( w_0 + w_1 x_1 + ... + w_d x_d)$

Spadek gradientu stochastycznego

$\Delta{w}^{(t+1)} = \Delta{w}^{(t)} + \eta(target - actual)x_i$

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:

$\Delta{w_{new}} \mathrel{{+}{=}} \Delta{w}^{(t)} + \eta(target - actual)x_i$

...

po 1 przejściu przez zestaw treningowy:

$\Delta{w} \mathrel{{+}{=}} \Delta{w_{new}}$

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

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ć =.$\Delta$

Perceptron:

$\pmb{w}^{(t+1)} = \pmb{w}^{(t)} + \eta_t (y^{(i)} - \hat{y}^{(i)}) \pmb{x}^{(i)}$

$\hat{y}^{(i)} = \text{sign} ({\pmb{w}^\top\pmb{x}^{(i)}})$$i^{th}$

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

Utrata perceptronu:

$L_{\pmb{w}}(y^{(i)}) = \max(0, -y^{(i)} \pmb{w}^\top\pmb{x}^{(i)})$

$\partial L_{\pmb{w}}(y^{(i)}) = \begin{array}{rl} \{ 0 \}, & \text{ if } y^{(i)} \pmb{w}^\top\pmb{x}^{(i)} > 0 \\ \{ -y^{(i)} \pmb{x}^{(i)} \}, & \text{ if } y^{(i)} \pmb{w}^\top\pmb{x}^{(i)} < 0 \\ [-1, 0] \times y^{(i)} \pmb{x}^{(i)}, & \text{ if } \pmb{w}^\top\pmb{x}^{(i)} = 0 \\ \end{array}$

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ś,

$\pmb{w}^{(t+1)} = \pmb{w}^{(t)} + \sum_{i=1}^n \{\pmb{w}^{(t)} - \eta_t \partial L_{\pmb{w}^{(t)}}(y^{(i)}) \}$

To powinno być:

$\pmb{w}^{(t+1)} = \pmb{w}^{(t)} - \eta_t \sum_{i=1}^n {\partial L_{\pmb{w}^{(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 $\eta_t = \frac{\eta_0}{\sqrt{t}}$.

* The perceptron algorithm is not exactly the same as SSGD on the perceptron loss. Usually in SSGD, in the case of a tie ($\pmb{w}^\top\pmb{x}^{(i)} = 0$), $\partial L= [-1, 0] \times y^{(i)} \pmb{x}^{(i)}$, so $\pmb{0} \in \partial L$, so you would be allowed to not take a step. Accordingly, perceptron loss can be minimized at $\pmb{w} = \pmb{0}$, which is useless. But in the perceptron algorithm, you are required to break ties, and use the subgradient direction $-y^{(i)} \pmb{x}^{(i)} \in \partial 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.