2
$\begingroup$

Recall the perceptron algorithm:

cycle through all points until convergence

$\text{if }\, y^{(t)} \neq \theta^{T}x^{(t)} + \theta_0\,\{\\ \quad \theta^{(k+1)} = \theta^{k} + y^{(t)}x^{(t)}\\ \}$

I was studying a modification to to the update rule such that the new update rule is:

$\theta^{(k+1)} = \theta^{k} + \eta_k y^{(t)}x^{(t)}\\$

where:

$\eta_k = \frac{ Loss (y^{(k)} \theta^{(k)} \cdot x^{(k)} ) }{\left \| x^{(k)} \right \|^2}$

and the loss function was the hinge loss. i.e:

$Loss(y^{(k)} \theta^{(k)} \cdot x^{(k)}) = max\{0, 1-y^{(k)} \theta^{(k)} \cdot x^{(k)}\}$

I was trying to understand the new weight $\eta_k$ and understand why it was the way it was. I think intuitively I can see why the hinge loss is being used because the least confident we are about our prediction, the higher the loss value it will give it (since we are more concerned of correcting that specific example I guess...), however, I was not sure what the denominator was doing. It seems to me it's some kind of an attempt to normalize the step-size or the weight, but was unsure how to interpret it. However, I was not 100% sure why the numerator was the way it was and any additional insight on either/both would be appreciated!

Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

The denominator prevents a single data point x from throwing off the entire perceptron. Imagine if a single $x^{(i)}$ is really far away from origin and every other $x^{(j)}$ is close to origin (e.g. $\|x^{(i)}\|=10^9$, $\|x^{(j)}\|<1$). Just for the easy of picturing, drop the bias for your perceptron. If the perceptron got $x^{(i)}$ wrong, next iteration $\theta$ will be dominated by the adjustment brought by $x^{(i)}$. Suppose $y^{(i)}=1$ and $x^{(i)}$ points in a very different direction than other examples where $y^{(j)}=1$. It will take a large amount of mistakes on other $x^{(j)}$ to change the direction weight vector. Having the normalization in the denominator, in effect, makes the data lie on a similar scale, making the perceptron learn quicker.

As for the numerator: If you make a very bad guess, your loss is going to be large. So the numerator increase the change to the weight if you make a big mistake, and decrease the change if you make a small mistake.

Improve this answer
$\endgroup$
6
  • $\begingroup$ the thing that still confuses me is, why are we dividing by $\|x^{(i)}\|^2$ and not $\|x^{(i)}\|$, I don't see the difference in that case. That seemed a little arbitrary for me. $\endgroup$
    – Charlie Parker
    Commented Feb 18, 2014 at 16:44
  • $\begingroup$ The thing is that, the reason I am not sure if what you suggested applies (maybe I am completely misunderstanding this) but when there is a loss then we have $\frac{1}{\| x \| ^2} - \frac{\|\theta \| cos(a)}{\|x\|}$ which isn't really normalized because for large x's as you pointed out, they are affect drastically, but now they are affected in the opposite way. Now the denominator is so large, that they don't really contribute much to the weight. I thought that dividing by $\| x\|$ would have made more sense. (note a is the angle between x and $\theta$). $\endgroup$
    – Charlie Parker
    Commented Feb 18, 2014 at 16:56
  • 1
    $\begingroup$ Note that for a perceptron, the learning rate is not that important. If the data is linearly separable, any reasonable learning rate would lead to convergence. So a lot of design works. I think $\|x^{(i)}\|$ is also a legitimate choice. However, note that $x^{(i)}$ occurs twice in the update equation, once as a vector, once in the hinge loss in the numerator. So it makes sense to normalize by $\|x^{(i)}\|^2$ $\endgroup$
    – BW0
    Commented Feb 18, 2014 at 17:51
  • 1
    $\begingroup$ When there is a loss, we have $\frac{1-y \theta \cdot x}{\|x\|} y \frac{x}{\|x\|} = \left( \frac{1}{\|x\|} - \frac{y \theta \cdot x}{\|x\|} \right) y \frac{x}{\|x\|}$. So the $\frac{1}{\|x\|}$ doesn't matter. Only how negative the $\frac{y \theta \cdot x}{\|x\|}$ matters. Makes sense, right? If there is anything unclear, I can clarify. $\endgroup$
    – BW0
    Commented Feb 18, 2014 at 18:02
  • $\begingroup$ Oh, that makes much more sense now. One last thing, the thing that I am still not sure is, why doesn't $1/\|x\|$ matter? I am not sure what you meant by that. For me, it seems that dividing by that extra $\|x\|$ makes all the difference because as you pointed out, due to the vector part of $x$. Or were you talking about the $\frac{1}{\|x\|} - \text{terms...}$ in the summation/subtraction equation? $\endgroup$
    – Charlie Parker
    Commented Feb 18, 2014 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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