Creating a working perceptron

Question

I'm trying to learn more about AI by trying to program a neural network. First I'm trying to understand writing my own perceptron but I'm struggling to get a basic perceptron working correctly.

I've tried writing a few basic perceptrons to do very basic tasks for example trying to classify a point as above or below a line y = x.

The problem I'm facing is it seems that when training the perceptron my weights start increasing exponentially and it doesn't seem like I'm getting anywhere.

If I start with a perceptron with two weights representing an x and a y value of a point on a graph: starting weight values of 1 and 1 Using the sign function of the output being more than or equal to 0 outputs +1 and less than 0 is -1.

I'm using the training data with examples (1,2), (2,1), (3,3), (2,1). I think I'm correct in saying if the perceptron outputs the correct value then you don't need to adjust the weights, if it's incorrect then the weights can be updated using

new_weight = old_weight + ((expected_ouptut - false_output) * input)

By the first iteration I have weights of -4 and -2 respectively, the second passes, the third i.e (3,3) with weights (-4,-2) changes the weights to (53,55).

I'm fairly sure my math is correct, and it seems like the weights are increasing exponentially without making any difference to getting a working perceptron. Are there any errors I'm making with trying to design a working perceptron?

Thanks!

Sorry this may get slightly long! EDIT:

I think I may have been making mistakes doing it manually, I’ve written the code now that seems to be partly working.

The way my code works is by running test firstly with test cases, followed by the results from those test cases in the same order within the lists. Followed by the weights and finally the test case to run it from. So running in ghci:

test [(5,2)] [(-1)] (1,1) (5,2)

this works correctly, first it tests the coordinates (5,2) in the perceptron with weights (1,1) and checks to see if it is equal to -1, if it is not equal to one it will run it again and alter the weights with the alter function until it does equal -1, when this happens it then checks the perceptron again and outputs with the final tuple (5,2) which is the test case to check if it’s working. This works correctly, however when working with larger sets it doesn’t work. 
Next I tried

test [(1,2),(2,5),(3,1),(7,0),(6,5),(4,4)] [1,1,(-1),(-1),(-1),1] (1,1) (5,1)

where the first two lists are the test cases and the results, then the weights (1,1) and finally after running all of the test cases trying to teach the perceptron it then runs the perceptron on the final tuple (5,1) and outputs the result, it should be (-1) as it is below y = x, however it outputs 1.

Pseudocode:

testFunction
if(test cases remaining):
  if calling sign on the output of the perceptron != result for test case then:
    call same test case again but alter weights
  else:
    call testFunction again will same lists minus the first test arguments and results
else if(no more test cases, all have been tested and removed, or none specified):
  call sign on the output of the perceptron for the final tuple provided with the altered weights

Code in Haskell:

module Main where

-- function to take training data, results from that data to test the perceptron
-- also takes weights and finally outputs the result of the test case
test :: [(Float,Float)] -> [Float] -> (Float,Float) -> (Float,Float) -> Float
test [] [] weights testCase = sign(perceptron testCase weights)
test (t:trainData) (r:trainResult) weights testCase
  | (output /= r) = test ([t] ++ trainData) ([r] ++ trainResult) (alter weights output t r) testCase -- add t and r
  | otherwise     = test trainData trainResult weights testCase
  where
    output = sign(perceptron t weights)

-- function that computes x1*w1 + x2*w2
perceptron :: (Float,Float) -> (Float,Float) -> Float
perceptron coordinate weights = ((((fst coordinate) * (fst weights))) + ((snd coordinate) * (snd weights)))

-- function that finds the new weights by doing w1 = w1 + (expected_result - perceptron output)*x1 and similar for w2
alter :: (Float,Float) -> Float -> (Float,Float) -> Float -> (Float,Float)
alter (w1,w2) output (x1,x2) result = ((w1 + ((result - output) * x1)), (w2 + ((result - output) * x2)))

-- activation function
sign :: Float -> Float
sign n
  | n >= 0 = 1
  | otherwise = (-1)

Answer 1

First, of all the formula you have supplied new_weight = old_weight + ((expected_ouptut - false_output) * input) has no learning rate. The learning rate is there to scale the weights (one of its function).

Secondly, where is the bias term? Although its not necessary if you already know a decision boundary passing through the origin will seperate the data, but in some cases it can scale the other parameters. For example, lets say the parameters are theta0, theta1, theta2. Now since there is an additional theta0 term getting added when there is error it will help to see that the correct result is reached faster. I know this is not a proper mathematical explanation and helps only a very tiny tiny bit almost negligible but maybe good for intuition. Correct me if i am wrong. Also it is better practice to have a bias term even for a beginner.

Another thing I would like to say I don't know how actually increasing training data helped your problem. As per your algorithm two different points increase the weight by different amounts. Let us say we have y = ax as the starting line. Say your training set contains two points. Now we use two different values of a for two different cases, each one for which one of the training data will be miss classified. After a single run in both the cases will the theta1, theta2 change same? No actually. This can be problematic if you see the next point.

Say your training set has outliers (the ones which cannot be classified properly and are partly in the other class)

Then your algorithm will get trapped in a loop (maybe a local minimum) and the weights will definitely increase exponentially. You can stop this from happening by adding a regularization term (might be quite advanced topic for beginner, but very easy to understand).

Lastly the mathematics of these type of perceptron classifiers (discrete 1 or 0 are too hard and involved to be visualized since you cannot use the tools of continuous algebra (differentiation, maxima, minima, etc). Your algorithm might get trapped in local minimum with no way of you knowing it easily. So, some of the errors you might face cannot be explained easily.

Also I might be wrong for the aforementioned reason, but if you find some better intuition please do share.

Answer 2

Solved it, the problem was I wasn't supplying it enough training data.

running the following in ghci should allow you to change the final tuple and solve the problem

test [(104,1),(1,104),(52,3),(4,79),(9,109),(92,23),(11,78),(3,109),((-2),78),(192,30),(103,20),(4,78),(23,193),(1,58),(98,2)] [(-1),1,(-1),1,1,(-1),1,1,1,(-1),(-1),1,1,1,(-1)] (1,1) (25,24)