In a course on Machine Learning, in the chapter about a Perceptron, there is this statement:

If a generously feasible region exists, then the distance between the current weight vector and a weight vector in the generously feasible region will monotonically decrease as the learning proceeds.

Why is this the case?


To summarise, it basically comes down to the fact that all the vectors have a component in the direction of the input vector $x$, so when we update the current weight vector by adding $x$ to it, the new weight vector has either a smaller negative component or a positive component in the $x$ direction. Note that by definition a generously feasible vector is one with a large $x$ component, so by making our current vector's $x$ component more positive we get closer to the generously feasible one. This is the rough idea, and is hopefully made more clear by the following calculations which shows exactly what I mean by all this component stuff.

For simplicity let's assume that we have just the one constraint i.e. let's say there is a vector $x$ and so the feasible region is the set of vectors $w$ such that $\langle x, w \rangle > 0$. Note that from linear algebra we know $w = \alpha x + \beta y$ where $\alpha, \beta \in \mathbb{R}$ and $y$ is an orthogonal vector to $x$. Since we're assuming $w$ is feasible, we have $0 < \langle w, x \rangle = \langle \alpha x + \beta y, x \rangle = \alpha \langle x,x \rangle + \beta \langle y, x \rangle = \alpha \langle x, x\rangle$. And since $\langle x,x \rangle > 0$, we must also have $\alpha > 0$. So now we know that $w$ is a feasible solution if and only if when expressed in the above form we have $\alpha > 0$.

Now say we're starting with an infeasible vector $v = \gamma x + \delta y$ so $\gamma < 0$. Then when taking a learning step we update $v$ to $v' := v + x = (\gamma + 1) x + \delta y$, so $v'$ is either less negative than $v$, or $v'$ is actually positive.

Now let's say that $w$ is a generously feasible i.e. $\langle w, x \rangle > \langle x, x\rangle$. Then $\alpha$ must be at least 1. The distance from $v$ to $w$ is $\| w- v\| = \| (\alpha - \gamma)x + (\beta - \delta)y \| = \sqrt{(\alpha - \gamma)^2 + (\beta - \delta)^2} $ whereas $\|w - v'\| = \sqrt{\langle (\alpha - \gamma - 1)^2 + (\beta - \delta)^2}$. Note that which vector $w$ is closer to basically comes down to whether $|\alpha - \gamma| > | \alpha - \gamma - 1 |$ or not. But since $w$ is generously feasible and $v$ is infeasible by assumption, $\alpha > 1,$ and $\gamma < 0$ so $\alpha - \gamma - 1 > \alpha -1 > 0$ so indeed we have $| \alpha - \gamma | > | \alpha - \gamma - 1|$ so the updated vector $v'$ is closer.


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.