Ex. 4.6

Suppose we have $N$ points $x_{i}$ in $R^{p}$ in general position, with class labels $g_{i} \in {- 1, 1}$ . Prove that the perceptron learning algorithm converges to a separating hyperplane in a finite number of steps:

(a) Denote a hyperplane by $f (x) = β_{1}^{T} x + β_{0} = 0$ or in a more compact notation $β^{T} x^{*} = 0$ , where $x^{*} = (x, 1)$ and $β = (β_{1}, β_{0})$ . Let $z_{i} = x_{i}^{*} / ‖ x_{i}^{*} ‖$ . Show that separability implies the existence of a $β_{sep}$ such that $y_{i} β_{sep}^{T} z_{i} \geq 1 \forall i$ .
(b) Given a current $β_{old}$ , the perceptron algorithm identifies a point $z_{i}$ that is misclassified, and produces the update $β_{new} \leftarrow β_{old} + y_{i} z_{i}$ . Show that $‖ β_{new} - β_{sep} ‖^{2} \leq ‖ β_{old} - β_{sep} ‖^{2} - 1$ , and hence that the algorithm converges to a separating hyperplane in no more than $‖ β_{start} - β_{sep} ‖^{2}$ steps （Pattern Recognition and Neural Networks）.

Soln. 4.6

(a) By definition of separability, there exists $β$ such that

\begin{array}{rcl} β^{T} x_{i} > & 0 & for y_{i} = 1 \\ β^{T} x_{i} < & 0 & for y_{i} = - 1. \end{array}

Thus we have $y_{i} β^{T} x_{i} > 0$ for all $x_{i}$ , thus for $y_{i} β^{T} z_{i} > 0$ for all $z_{i}$ .

Define

m := min_{i} ‖ y_{i} β^{T} z_{i} ‖ .

Thus, $y_{i} (\frac{1}{m} β^{T}) z_{i} \geq 1$ . So there exists a $β_{sep} := \frac{1}{m} β$ such that $y_{i} β_{sep}^{T} z_{i} \geq 1 \forall i$ .

(b) We have

\begin{array}{rcl} ‖ β_{new} - β_{sep} ‖^{2} & = & ‖ β_{old} - β_{sep} + y_{i} z_{i} ‖^{2} \\ = & ‖ β_{old} - β_{sep} ‖^{2} + ‖ y_{i} z_{i} ‖^{2} + 2 y_{i} (β_{old} - β_{sep})^{T} z_{i} \\ = & ‖ β_{old} - β_{sep} ‖^{2} + 1 + 2 y_{i} β_{old}^{T} z_{i} - 2 y_{i} β_{sep}^{T} z_{i} \\ \leq & ‖ β_{old} - β_{sep} ‖^{2} + 1 + 2 \cdot 0 - 2 \cdot 1 \\ = & ‖ β_{old} - β_{sep} ‖^{2} - 1. \end{array}