Intuition on learning rate or step-size for perceptron algorithm

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!

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.
• 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. – Pinocchio Feb 18 '14 at 16:44
• 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$). – Pinocchio Feb 18 '14 at 16:56
• 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$ – BW0 Feb 18 '14 at 17:51
• 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. – BW0 Feb 18 '14 at 18:02
• 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? – Pinocchio Feb 18 '14 at 19:31