Question

Given a set of samples which belong to two classes C1 and C2, assume C1 and C2 are linearly separable, please prove that perceptron learning algorithm applied to the samples will terminate after a finite number of iterations.

Answer 1

Given that the input variables come from
two linearly separable classes C1& C2
Let T1& T2 be subsets of training vectors which
belong to the classes C1 & C2 respectively.
Then T1 U T2 is the complete training set.

As we have seen, the learning algorithms
purpose is to find a weight vector w such that

w⋅x > 0 ∀ x∈C1
w⋅x ≤ 0 ∀ x∈C2
(x is an input vector)

If the kth member of the training set, x(k), is
correctly classified by the weight vector w(k)
computed at the kth iteration of the algorithm,
then we do not adjust the weight vector.
However, if it is incorrectly classified, we use the
modifier

w(k+1)=w (k)+ηd (k)x (k)

So we get

w(k+1) = w(k )−ηx (k ) if w(k )⋅x (k ) > 0, x (k )∈C2
w(k+1) = w(k )+η(k ) if w(k )⋅x (k ) ≤ 0, x (k)∈C1

Wecan set η = 1, as for η ≠ 1 (>0) just scales

the vectors.
We can also set the initial condition w(0) = 0, as
any non-zero value will still converge, just
decrease or increase the number of iterations.

Suppose that w(k)⋅x(k) < 0 for k = 1, 2, ... where
x(k) ∈ T1
, so with an incorrect classification we
get
By expanding iteratively, we get

w(k+1)=x (k)+w(k )
=x (k )+x (k – 1)+w(k – 1)

:

:
=x (k )+...+x (1)+w(0)

As we assume linear separability, ∃ a solution w*
where w⋅x(k) > 0, x(1)...x(k) ∈ T1. Multiply both sidesby the solution w*
to get

hus it is proved that for ηk= 1,∀ k, w(0) = 0,
given that a solution vector w*exists, the
perceptron learning rule will terminate after at
most kmax iterations