python - Perceptron Learning Algorithm taking a lot of iterations to converge? -

i solving homework-1 of caltech machine learning course (http://work.caltech.edu/homework/hw1.pdf) . solve ques 7-10 need implement pla. implementation in python:

import sys,math,random  w=[] # stores weights data=[] # stores vector x(x1,x2,...) output=[] # stores output(y)   # returns 1 if dot product more 0 def sign_dot_product(x):     global w     dot=sum([w[i]*x[i] in xrange(len(w))])     if(dot>0):         return 1     else :         return -1  # checks if point misclassified def is_misclassified(rand_p):     return (true if sign_dot_product(data[rand_p])!=output[rand_p] else false)   # loads data in following format: # x1 x2 ... y # in present case d=2 # x1 x2 y def load_data():     f=open("data.dat","r")     global w     line in f:         data_tmp=([1]+[float(x) x in line.split(" ")])         data.append(data_tmp[0:-1])         output.append(data_tmp[-1])   def train():     global w     w=[ random.uniform(-1,1) in xrange(len(data[0]))] # initializes w random weights     iter=1     while true:          rand_p=random.randint(0,len(output)-1) # randomly picks point         check=[0]*len(output) # check list. ith location 1 if ith point correctly classified         while not is_misclassified(rand_p):             check[rand_p]=1             rand_p=random.randint(0,len(output)-1)             if sum(check)==len(output):                 print "all points satisfied in ",iter-1," iterations"                 print iter-1,w,data[rand_p]                 return iter-1         sign=output[rand_p]         w=[w[i]+sign*data[rand_p][i] in xrange(len(w))] # changing weights         if iter>1000000:             print "greater 1000"             print w             return 10000000         iter+=1  load_data()  def simulate():    #tot_iter=train()     tot_iter=sum([train() x in xrange(100)])     print float(tot_iter)/100  simulate() 

the problem according answer of question 7 should take around 15 iterations perceptron converge when size of training set implementation takes average of 50000 iteration . training data randomly generated generating data simple lines such x=4,y=2,..etc. reason why getting wrong answer or there else wrong. sample of training data(separable using y=2):

1 2.1 1 231 100 1 -232 1.9 -1 23 232 1 12 -23 -1 10000 1.9 -1 -1000 2.4 1 100 -100 -1 45 73 1 -34 1.5 -1 

it in format x1 x2 output(y)

it clear doing great job learning both python , classification algorithms effort.

however, because of of stylistic inefficiencies code, makes difficult , creates chance part of problem miscommunication between , professor.

for example, professor wish use perceptron in "online mode" or "offline mode"? in "online mode" should move sequentially through data point , should not revisit points. assignment's conjecture should require 15 iterations converge, curious if implies first 15 data points, in sequential order, result in classifier linearly separates data set.

by instead sampling randomly replacement, might causing take longer (although, depending on distribution , size of data sample, admittedly unlikely since you'd expect 15 points first 15).

the other issue after detect correctly classified point (cases when not is_misclassified evaluates true) if witness new random point is misclassified, code kick down larger section of outer while loop, , go top overwrite check vector 0s.

this means way code detect has correctly classified points if particular random sequence evaluates them (in inner while loop) happens string of 1's except miraculous ability on particular 0, on pass through array, classifies correctly.

i can't quite formalize why think make program take longer, seems code requiring stricter form of convergence, sort of has learn @ once on 1 monolithic pass way late in training stage after having been updated bunch already.

one easy way check if intuition crappy move line check=[0]*len(output) outside of while loop , initialize 1 time.

some general advice make code easier manage:

1. don't use global variables. instead, let function load , prep data return things.

2. there few places say, example,

   return (true if sign_dot_product(data[rand_p])!=output[rand_p] else false)

   this kind of thing can simplified to

   return sign_dot_product(data[rand_p]) != output[rand_p]

   which easier read , conveys criteria you're trying check in more direct manner.

3. i doubt efficiency plays important role since seems pedagogical exercise, there number of ways refactor use of list comprehensions might beneficial. , if possible, use numpy has native array types. witnessing how of these operations have expressed list operations lamentable. if professor doesn't want implement numpy because or trying teach pure fundamentals, ignore them , go learn numpy. jobs, internships, , practical skill these kinds of manipulations in python vastly more fighting native data types not designed (array computing).