Implement PLA

First cook up some linearly separable data to try it on

In [1]:
from numpy import *
d = 2
n = 55
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
In [2]:
%pylab inline
Populating the interactive namespace from numpy and matplotlib
In [3]:
xp = X[1:,y>0]
xm = X[1:,y<0] 
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 [7]:
# We are given X and y ONLY!!

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

while(True):
    misclassified = sign(dot(W,X)) != y
    if not any( misclassified  ): break
    i = random.choice( arange(n)[misclassified] )  # random misclassified point 
    W += y[i]*X[:,i]  # PLA step
print(W)       
[-2.         -1.71548701  4.55258663]
In [8]:
random.choice([3,6,9])
Out[8]:
9

Let's do it again, but with graphics

In [9]:
subplot(111,aspect=1)
plot(xp[0],xp[1],'ro')
plot(xm[0],xm[1],'bo');

def drawline(W,color='g',alpha=1.):
    plot([0,1],[-W[0]/W[2],-(W[0]+W[1])/W[2]],color=color,alpha=alpha)
    
W = array([-1,-1,5],dtype=float)  # starting guess at separating W

drawline(W,color='c')                
while(True):
    misclassified = sign(dot(W,X)) != y
    if not any( misclassified  ): break
    i = random.choice( arange(n)[misclassified] )  # random misclassified point 
    W += y[i]*X[:,i]  # PLA step
    drawline(W,alpha=0.3)                

drawline(W,color='m')                
xlim(0,1)
ylim(0,1)
print(W)
[-2.         -1.84153093  4.6904186 ]
In [ ]: