Intuition behind perceptron algorithm with offset

Question

I was looking for an intuition for the perceptron algorithm with offset rule, why the update rule is as follows:

cycle through all points until convergence:

$\textbf{if }\, y^{(t)} \neq \theta^{T}x^{(t)} + \theta_0 \, \textbf{ then}\\\ \quad \theta^{(k+1)} \leftarrow \theta^{k} + y^{(t)}x^{(t)}\\ \quad \theta^{(k+1)}_0 \leftarrow \theta^{k}_0 + y^{(t)}\\ $

When the offset is zero, I think the update rule is completely intuitive. However, without it, it seems a little odd just adding 1 or -1 to the offset. The only reason I could come up with to explain it was the following but I don't really think its very intuitive explanation and was looking for a different explanation.

My non-intuitive answer:

When the perceptron makes a mistake then:

$y^{(t)}(\theta^{T}x + \theta_0) \leq 0$

But we can re-write the top part as:

$<\theta, \theta_0> \cdot <x^{(t)}, 1> = \theta^{T}x + \theta_0$

and now if we just appeal to the original perceptron rule and change the feature vector to have the one attached at the end and the normal now includes $\theta_0$, now the update would occur as following:

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

which is:

$<\theta, \theta_0> + y^{(t)}<x^{(t)}, 1> = <\theta + y^{(t)}x^{(t)}, \theta_0+y^{(t)}>$

I think this might be correct, but even if it is, I didn't really think it was intuitive or "obvious" and was wondering if anyone had a different argument?

Thanks!

PS: Feel free to edit my algorithm to have indentation and spaces, I couldn't make it have indentation without losing the latex :(

Answer 1

Some geometric intuition: the bias term $\theta_0$ is related to the distance of the separating hyperplane from the origin. More precisely, the distance of the decision hyperplane $\theta^Tx+\theta_0=0$ from origin is given by $|\frac{\theta_0}{||\theta||}|$.Now, let's see why the updation step $\theta_0 \leftarrow \theta_0+y^{(t)}$ leads to the shift of the decision hyperplane in the right direction, to take care of the mis-classification.

When $y^{(t)}=+1$ and $sign(\theta^Tx^{(t)}+\theta_0)=-1$ (i.e., a positive datapoint is misclassified), it implies that the distance of the particular data point from the origin is greater than the distance of the separating hyperplane from origin, that's why the hyperplane needs to be taken further away from the origin by incrementing $\theta_0$ (i.e., $\theta_0 \leftarrow \theta_0+1$, as shown in the next figure), so that the new decision hyperplane is given by $\theta^Tx+\theta_0+1=0$ i.e., $\theta^Tx+\theta_0=-1$.

The similar argument for a misclassified negative datapoint $y^{(t)}=-1$ and $sign(\theta^Tx^{(t)}+\theta_0)=+1$ will need the decision hyperplane to be brought closer to the origin to rectify the mis-classification in this case (as shown in the figure above), by decrementing $\theta_0$ (i.e., $\theta_0 \leftarrow \theta_0-1$), resulting in the new decision hyperplane $\theta^Tx+\theta_0-1=0$ or $\theta^Tx+\theta_0=1$ .

Hence, in both the cases, to take the mis-classification into account, we need to update the hyperplane's bias term by $\theta_0 \leftarrow \theta_0+y^{(t)}$.

Also, note that if a misclassified point is far away from the decision hyperplane, then this simple update of bias by unit step alone may not correct the mis-classification, but it will certainly be a step to translate the hyperplane in the right direction to rectify the mis-classification.

Answer 2

I was also taught the "adding 1 feature" trick.

My current understanding is that all you have to do for $\theta_0$ is either move the boundary towards the negative or positive side. 1 is arbitrary and controls the ratio of this shift relative to $\theta$. For example: $$x^{(1)} = (2,2),~~ y^{(1)} = 1 \\ \theta^{(1)} = (2,2),~~\theta_0^{(1)} = 0 \\ x^{(2)} = (1,1),~~ y^{(2)} = -1 $$

The next update: $$\theta^{(2)} = (1,1),~~\theta_0^{(2)}=-1$$

The point is still misclassified, but the decision boundary has been moved to pass through $(1/2,1/2)$ from $(0,0)$ previously. If we had $\theta^{(1)} = (3,3)$ instead, then $\theta^{(2)} = (2,2)$ and the decision boundary passes through $(1/4,1/4)$. So the boundary moves less with larger $\theta$.

What should we do then? Can we change the update rule to $\theta_0^{(k+1)} = \theta_0^{(k)} + 10y^{(t)}$ so that $\theta_0^{(k+1)} = -10$? Now the boundary passes through $(5,5)$ and the point is correctly classified. But now, $x^{(1)} = (2,2)$ becomes misclassified. Without knowing $x$ in advance, we can't tell what update of $\theta_0$ is best, hence we use 1 for simplicity. (It still has to be a constant because each example is treated equally; learning rate doesn't affect perceptron convergence and can be omitted.)