4
$\begingroup$

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:

enter image description here

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?

$\endgroup$
3
  • $\begingroup$ Hi! you didn't accept my answer. Is it because my answer was unclear? Please feel free to clarify, I was a bit busy when I wrote the answer, but now I can answer any doubts you have about the nswer $\endgroup$ – DuttaA Feb 4 at 10:41
  • $\begingroup$ @DuttaA My apologies, I completely forgot. I think I awarded you the bounty from my phone and then forgot to check back. Please give me a moment to read everything again. $\endgroup$ – The Pointer Feb 4 at 10:41
  • $\begingroup$ I was also confused about this specific part of the book and came accross the following video explaining hinge loss. Hope it might help: youtube.com/watch?v=PM2MSAYmzXM $\endgroup$ – user45643 Mar 24 at 1:22
0
+100
$\begingroup$

The point author is trying to make is:

  • Even though the SVM and the particular characterization of Perceptron loss made by the author has the same gradient, the points which will be considered erroneous are different.
  • One can replace $y$ with $E(X)$ in which case one does not need to explicitly construct the set $S^+$

For part 1 it is pretty simple to see, that the SVM will incur loss until and unless $y(W^TX) > 1$ which is what the $\max(0,1-y(W^TX))$ does. And this is loss is clearly linear with $Z = (W^TX)$. A point to note is that this will take care of the misclassifications for both $y \in \{+1,-1\}$ (check this out yourself).

Now, a more general SVM formulation would be $\max(0,\theta-y(W^TX))$, put $\theta=0$ and you get your Perceptron loss. Here you only have to satisfy $y(W^TX) > 0$. Thus, only the threshold changes, and there is no effect on slope.

Infact, one can create different SVM formualtions with different such tolerances, which itself maybe variable i.e $\theta = f(x^*)$.

For the second part, instead of writing:

$$\overline{W} \Leftarrow \overline{W} + \alpha \sum_{(\overline{X}, y) \in S^+} y \overline{X}$$

where you are explicitly constructing a set of $S^+$ ot misclassified points, just write it as: $$\overline{W} \Leftarrow \overline{W} + \frac{\alpha}{2} \sum_{i=1}^n E(X_i) \overline{X_i}$$ where $E(X) = (y − \text{sign}\{\overline{W} \cdot \overline{X} \}) \in \{ −2, +2 \}$. This will result in the exact same updates, as when $W^TX_i > 0, y=-1$, we will get $E(X) = -2$ with which we replace $y=-1$, and thus adjuest it with $\frac{\alpha}{2}$ instead of $\alpha$.

$\endgroup$
-2
$\begingroup$

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!

enter image description here

$\endgroup$
2
  • 2
    $\begingroup$ Hi. Thanks for trying to contribute, but you should at least try to address the actual question. $\endgroup$ – nbro Nov 24 '20 at 3:03
  • 1
    $\begingroup$ Your information regarding the hinge loss is interesting, but, as @nbro said, it doesn't answer my question. $\endgroup$ – The Pointer Nov 24 '20 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.