Aclaración sobre la implementación de la regla de Perceptron vs. el descenso del gradiente vs. el descenso del gradiente estocástico

Experimenté un poco con diferentes implementaciones de Perceptron y quiero asegurarme de entender las "iteraciones" correctamente.

La regla original del perceptrón de Rosenblatt

Según tengo entendido, en el clásico algoritmo perceptrón de Rosenblatt, los pesos se actualizan simultáneamente después de cada ejemplo de entrenamiento a través de

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

donde $eta$ es la regla de aprendizaje aquí. Y el objetivo y el real están ambos trillados (-1 o 1). Lo implementé como 1 iteración = 1 pasada sobre la muestra de entrenamiento, pero el vector de peso se actualiza después de cada muestra de entrenamiento.

Y calculo el valor "real" como

$sign ({\pmb{w}^T\pmb{x}}) = sign( w_0 + w_1 x_1 + ... + w_d x_d)$

Descenso de gradiente estocástico

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

Sin embargo, es igual a la regla del perceptrón targety actualno son valores trillados sino reales. Además, cuento la "iteración" como ruta sobre la muestra de entrenamiento.

Tanto SGD como la regla clásica de perceptrón convergen en este caso linealmente separable, sin embargo, estoy teniendo problemas con la implementación de descenso de gradiente.

Descenso de gradiente

Aquí, reviso la muestra de entrenamiento y sumo los cambios de peso para 1 pasada sobre la muestra de entrenamiento y actualizo los pesos a partir de entonces, por ejemplo,

para cada muestra de entrenamiento:

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

...

después de 1 pase sobre el conjunto de entrenamiento:

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

Me pregunto si esta suposición es correcta o si me falta algo. Intenté varias tasas de aprendizaje (hasta infinitamente pequeñas) pero nunca pude lograr que mostrara ningún signo de convergencia. Entonces, me pregunto si entendí mal algo. aquí.

Gracias Sebastián

$\Delta$

Perceptrón:

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

donde y ( i )es la predicción del modelo en el$\hat{y}^{(i)} = \text{sign} ({\pmb{w}^\top\pmb{x}^{(i)}})$$i^{th}$

Esto puede verse como un método estocástico de descenso de subgradiente en la siguiente función de "pérdida de perceptrón" *:

Pérdida de perceptrón:

$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}$.

Dado que perceptron ya es una forma de SGD, no estoy seguro de por qué la actualización de SGD debería ser diferente de la actualización de perceptron. La forma en que ha escrito el paso SGD, con valores no restringidos, sufre una pérdida si predice una respuesta demasiado correctamente. Eso es malo.

El paso de gradiente de lote es incorrecto porque está usando "+ =" cuando debería estar usando "=". Los pesos actuales se agregan para cada instancia de entrenamiento . En otras palabras, la forma en que lo has escrito,

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

What it should be is:

$\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.