Perceptron
Encode targets $t_n \in {-1, 1}$.
Then we can write the error function we want to minimize as:
$$E_p(\mathbb{w}) = - \sum_{n \in M} y_n t_n$$
Where $y_n = \mathbb{w}^T \phi_n$, i.e. applying weights to some feature vector of the input.
The decision boundary for the classification (which is a step function) is $w^T \phi(x_n) = 0$, meaning that the weight vector of the decision boundary is perpendicular to the feature vector (right?).
So we classify +1 for $f(a) \leq 0$, and -1 otherwise.
The feature vectors $\phi(x)$ are fixed, meaning that perceptron classification is fully determined by the weight vector.
Because we encode the classes as -1 and 1, we have that correctly classified samples always have a positive contribution (1x1 or -1x-1) and misclassified samples always have a negative contribution (-1x1 or 1x-1).
We thus want to maximize $\sum y_n t_n$, i.e. minimize the negative sum above.
Q: Why do we not use a typical loss function for regression, e.g. something that takes into account $y(x_n) - t_n$?
The perceptron weight vector only changes when the decision boundary crosses a data point. In most possible adjustments of w, that does not happen, so as a function of w the number of misclassified samples is constant almost everywhere. This means the total error is not a useful signal for determining the direction of the weight update. Also, if the weight vector is updated based on a misclassified sample, it may even still be the case that the total amount of misclassifications stays the same, as it may now be that another pattern is misclassified.
Instead we use [stochastic gradient descent]202102231656-stochastic_gradient_descent.md ): $w^{(t+1)} = w^{(t)} - \eta \nabla (E_n(w)))$
Note that you then use the error contribution of a single sample. Compute the gradient of the error for a single sample:
$$\Nabla E_n(w) = -\phi(x_n) t_n$$
Plugging this in into the gradient descent rule gives the perceptron update rule (notice the sign chance!):
$$w^{(t+1)} = w^{(t)} + \eta \phi(x_n) t_n$$
Note that the {-1, 1} encoding is absolutely crucial!
In this rule, we can set $\eta = 1$ without problems because only the sign of the outcome of $f(w^T \phi(x))$ matters for the classification. It can be shown this is unaffected by the scalar transform of $\eta$ in the update rule.