How should we interpret this figure that relates the perceptron criterion and the hinge loss?

Question

I am currently studying the textbook Neural Networks and Deep Learning by Charu C. Aggarwal. Chapter 1.2.1.2 Relationship with Support Vector Machines says the following:

The perceptron criterion is a shifted version of the hinge-loss used in support vector machines (see Chapter 2). The hinge loss looks even more similar to the zero-one loss criterion of Equation 1.7, and is defined as follows: $$L_i^{svm} = \max\{ 1 - y_i(\overline{W} \cdot \overline{X}_i), 0 \} \tag{1.9}$$ Note that the perceptron does not keep the constant term of $1$ on the right-hand side of Equation 1.7, whereas the hinge loss keeps this constant within the maximization function. This change does not affect the algebraic expression for the gradient, but it does change which points are lossless and should not cause an update. The relationship between the perceptron criterion and the hinge loss is shown in Figure 1.6. This similarity becomes particularly evident when the perceptron updates of Equation 1.6 are rewritten as follows: $$\overline{W} \Leftarrow \overline{W} + \alpha \sum_{(\overline{X}, y) \in S^+} y \overline{X} \tag{1.10}$$ Here, $S^+$ is defined as the set of all misclassified training points $\overline{X} \in S$ that satisfy the condition $y(\overline{W} \cdot \overline{X}) < 0$. This update seems to look somewhat different from the perceptron, because the perceptron uses the error $E(\overline{X})$ for the update, which is replaced with $y$ in the update above. A key point is that the (integer) error value $E(X) = (y − \text{sign}\{\overline{W} \cdot \overline{X} \}) \in \{ −2, +2 \}$ can never be $0$ for misclassified points in $S^+$. Therefore, we have $E(\overline{X}) = 2y$ for misclassified points, and $E(X)$ can be replaced with $y$ in the updates after absorbing the factor of $2$ within the learning rate.

Equation 1.6 is as follows:

$$\overline{W} \Leftarrow \overline{W} + \alpha \sum_{\overline{X} \in S} E(\overline{X})\overline{X}, \tag{1.6}$$ where $S$ is a randomly chosen subset of training points, $\overline{X} = [x_1, \dots, x_d]$ is a data instance (vector of $d$ feature variables), $\overline{W} = [w_1, \dots, w_d]$ are the weights, $\alpha$ is the learning rate, and $E(\overline{X}) = (y - \hat{y})$ is an error value, where $\hat{y} = \text{sign}\{ \overline{W} \cdot \overline{X} \}$ is the prediction and $y$ is the observed value of the binary class variable.

Equation 1.7 is as follows:

$$L_i^{(0/1)} = \dfrac{1}{2} (y_i - \text{sign}\{ \overline{W} \cdot \overline{X_i} \})^2 = 1 - y_i \cdot \text{sign} \{ \overline{W} \cdot \overline{X_i} \} \tag{1.7}$$

And figure 1.6 is as follows:

Figure 1.6 looks unclear to me. What is figure 1.6 showing, and how is it relevant to the point that the author is trying to make?

Answer 1

Figure 1.6 is depicting that the hinge-loss used in SVMs (Eqn 1.9):

$$L_i^{svm} = \text{max}\{1 - y_i (\overline{W} \cdot \overline{X}_i, 0\} \tag{1.9}$$

is a shifted version (+1 to the right) of the loss function (Eqn 1.8) used to optimize the perceptron criterion (see footnote (1)):

$$L_i = \text{max}\{-y_i (\overline{W} \cdot \overline{X}_i), 0\} \tag{1.8}$$

Using Figure 1.6 and the accompanying discussion in Section 1.2.1.2, the author (Charu C. Aggarwal) is trying to show that if you make the implicit training process of the perceptron explicit (with an objective function, in his case, a loss function defined by Eqn 1.8), then one realises (in his words):

that the perceptron is fundamentally not very different from well-known machine learning algorithms like the support vector machine in spite of its different origins.

Footnotes

(1) The perceptron criterion was introduced in Section 3.5.1 of Neural Networks for Pattern Recognition by Christopher Bishop as a continuous, piecewise linear error function given by:

$$E^{\text{perc}}(\bf{w}) = - \sum_{\phi^n \in \mathcal{m}} w^T (\phi^n t^n)$$

Bishop suggested that this objective function is minimised when training a perceptron. Aggarwal references this work as an example of how the perceptron training process implicitly minimises this error function, using it as a segue into his own derivation of Eqn 1.8 before encouraging the reader to check that the gradient of Eqn 1.8 leads to the perceptron update (i.e. $\overline{W} \Leftarrow \overline{W} - \alpha \nabla_{W} L_i$).

Answer 2

I can't fully explain the part because I forgot what it talks about.

However, regarding the hinge loss, it is basically allowing your SVM to tolerate misclassifications without increasing the cost function.

For example, you give someone 1 dollar or 1 euro. You can forgive them, you tolerate it. Your hinge loss is 0 for lending someone 1d dollar. However, if you give them 10 dollars or 100, you will ask them to refund you ASAP because you can't tolerate that much loss!