Implement PLA

First cook up some linearly separable data to try it on

In [36]:
from numpy import *
d = 2
n = 500
x = random.rand(d,n)
x
X = empty((d+1,n))
X[0,:] = 1
X[1:,:] = x
X
W = array([-1,-2,3.])
y = sign(dot(W,X))
y
# let's open up a little space between the classes
halfgap = 0.05
x[-1,][y>0] += halfgap
x[-1,][y<0] -= halfgap
# copy the changes into X
X[1:,:] = x
In [37]:
%pylab inline
Populating the interactive namespace from numpy and matplotlib
In [38]:
xp = x.T[y>0].T 
xm = x.T[y<0].T 
subplot(111,aspect=1)
plot(xp[0],xp[1],'ro')
plot(xm[0],xm[1],'bo');

Now forget that we already know a separating W !!!

Our task is to use the PLA to find a separating W

In [ ]:
# We are given X and y ONLY!!

W = array([-1,-1,5.])  # starting guess at separating W

while(True):
    if sum(sign(dot(W,X))==y)==n: # correctly classified
        break
    # index i of misclassified point !!!!!!!!!!!!
    W += y[i]*X[:,i]
        
In [ ]: