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

It is said that we are dealing with the case of binary classification, where $y \in \{ -1, +1 \}$. But the author claims that $E(X) = (y − \text{sign}\{\overline{W} \cdot \overline{X} \}) \in \{ −2, +2 \}$, which doesn't include the case of $0$. So shouldn't the $\{ -2, +2 \}$ in $E(X) = (y − \text{sign}\{\overline{W} \cdot \overline{X} \}) \in \{ −2, +2 \}$ be $\{ -2, 0, +2 \}$?

$\endgroup$
2
  • $\begingroup$ The author is saying that $E(X)$ can never be zero for misclassified points, so I am not sure I understand your question/concerns. (Btw, I didn't really read that excerpt carefully). $\endgroup$
    – nbro
    Nov 21, 2020 at 14:33
  • $\begingroup$ @nbro But why can it never be zero for misclassified points? As I said, $y \in \{ -1, +1 \}$, so I don't see why $E(X) = (y − \text{sign}\{\overline{W} \cdot \overline{X} \})$ cannot be zero. $\endgroup$ Nov 21, 2020 at 14:38

1 Answer 1

2
$\begingroup$
  1. It is important to note that the exact statement is the eqation given below can never be 0 for misclassified points in $ S^+$ $$ E(X) = (y - \text{sign}\{\overline{W} \cdot \overline{X}\}) $$
  2. And $S+$ is defined as the set of all misclassified training points $X \in S$ that satisfy the condition $y(\overline{W} \cdot \overline{X})<0 $ which means that $y$ and $ (\overline{W} \cdot \overline{X}) $ will have different signs i.e if $y < 0$ then $(\overline{W} \cdot \overline{X}) > 0$ and vice versa.
  3. Finally the condition on $S^+$ constraints the the $ E(X)$ to these values when $ y < 0$ and $(\overline{W} \cdot \overline{X}) > 0$ $$ E(X) = (-1 - \text{sign}(+ve)) = -2 $$ or when $ y > 0$ and $(\overline{W} \cdot \overline{X}) < 0$ $$ E(X) = (1 - \text{sign}(-ve)) = 2 $$
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .