Perceptron problems

Question

I am trying to make a training set of data points by making a line (perceptron) f and making the points on one side +1 and -1 on the other. Then making a new line g and trying to get it as close to f as possible by updating with w = w+ y(t)x(t) where w is weights and y(t) is +1,-1 and x(t) is coordinates of a missclassified point. after implementing this tho i am not getting a very good fit from g to f. here is my code and some sample outputs.

import random

random.seed()

points = [ [1, random.randint(-25, 25), random.randint(-25,25), 0] for k in range(1000)]

weights = [.1,.1,.1]

misclassified = []

############################################################# Function f

interceptf = (0,random.randint(-5,5))

slopef = (random.randint(-10, 10),random.randint(-10,10))

point1f = ((interceptf[0] + slopef[0]),(interceptf[1] + slopef[1]))
point2f = ((interceptf[0] - slopef[0]),(interceptf[1] - slopef[1]))

############################################################# Function G starting
interceptg = (-weights[0],weights[2])

slopeg = (-weights[1],weights[2])

point1g = ((interceptg[0] + slopeg[0]),(interceptg[1] + slopeg[1]))
point2g = ((interceptg[0] - slopeg[0]),(interceptg[1] - slopeg[1]))
#############################################################

def isLeft(a, b, c):
      return ((b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0])) > 0


for i in points:
    if isLeft(point1f,point2f,i):
        i[3]=1
    else:
        i[3]=-1

for i in points:
    if (isLeft(point1g,point2g,i)) and (i[3] == -1):
        misclassified.append(i)

    if (not isLeft(point1g,point2g,i)) and (i[3] == 1):
        misclassified.append(i)

print len(misclassified)


while misclassified:
    first = misclassified[0]
    misclassified.pop(0)

    a = [first[0],first[1],first[2]]
    b = first[3]

    a[:] = [x*b for x in a]

    weights = [(x + y) for x, y in zip(weights,a)]

interceptg = (-weights[0],weights[2])

slopeg = (-weights[1],weights[2])

point1g = ((interceptg[0] + slopeg[0]),(interceptg[1] + slopeg[1]))
point2g = ((interceptg[0] - slopeg[0]),(interceptg[1] - slopeg[1]))

check = 0

for i in points:
    if (isLeft(point1g,point2g,i)) and (i[3] == -1):
        check += 1

    if (not isLeft(point1g,point2g,i)) and (i[3] == 1):
        check += 1

print weights
print check

117 <--- number of original missclassifieds with g

[-116.9, -300.9, 190.1] <--- final weights

617 <--- number of original missclassifieds with g after algorithm

956 <--- number of original missclassifieds with g

[-33.9, -12769.9, -572.9] <--- final weights

461 <--- number of original missclassifieds with g after algorithm

Answer 1

There are at least few problems with your algorithm:

• Your "while" conditions is wrong - the perceptron learning is not about iterating once through all misclassified points as you do now. The algorithm should iterate through all the points for as long as any of them is missclassified. In particular - each update can make some correctly classified point as the wrong one, so you have to always iterate through all of them and check if everything is fine.

• I am pretty sure that what you actually wanted is update rule in form of (y(i)-p(i))x(i) where p(i) is predicted label and y(i) is a true label (but this obviously degenrates to your method if you only update misclassifieds)