LFD Book Forum Perceptron Learning Algorithm
 Register FAQ Calendar Mark Forums Read

#11
04-08-2012, 08:46 AM
 tcristo Member Join Date: Apr 2012 Posts: 23
Re: Perceptron Learning Algorithm

Quote:
 Originally Posted by GraceLAX If an algorithm always converges would the Pr(f(x) ne g(x)) = 0?

I believe you will need to generate a separate set of test data to process and determine the error rate. Don't update the weights when processing the test data, just process each data point and determine whether it was correct or not. Aggregate those results and you should have your classifier error rate.

BTW: This is how I did it which I guess shouldn't necessarily be confused with the correct way of doing it
#12
04-08-2012, 11:13 AM
 cool8137 Junior Member Join Date: Apr 2012 Location: Lalitpur, Nepal Posts: 5
Re: Perceptron Learning Algorithm

Quote:
 Originally Posted by GraceLAX Thanks for the clarification. That helped quite a bit. If an algorithm always converges would the Pr(f(x) ne g(x)) = 0?
I think, the probability depends on the number of data. Just as our Hypothesis function h converses towards the Target Function f, once all of the training data (x) agrees with the training values (y), the iteration stops, before it actually reaches f (simply because our sample training data satisfies to the final h, which is g)

For example: if the target function was a 45degree st. line (x2=x1), and there was only one training data say ((x1(1),x2(1)),y(1))=((1,2),+1), and if our first hypothesis function was the horizontal axis itself, the Perceptron Algorithm would stop in its first iteration, and conclude the the horizontal-axis to be close to the Target function (which was actually 45degree line through origin). But if we increase the number of data, the hypothesis function is forced to converge towards the target function, with more iterations.

But there will always be some discrepancy i guess, unless you are very lucky.
#13
04-08-2012, 03:39 PM
 htlin NTU Join Date: Aug 2009 Location: Taipei, Taiwan Posts: 601
Re: Perceptron Learning Algorithm

Quote:
 Originally Posted by tcristo I believe you will need to generate a separate set of test data to process and determine the error rate. Don't update the weights when processing the test data, just process each data point and determine whether it was correct or not. Aggregate those results and you should have your classifier error rate. BTW: This is how I did it which I guess shouldn't necessarily be confused with the correct way of doing it
This is what I'd do, too.
__________________
When one teaches, two learn.
#14
04-08-2012, 03:41 PM
 htlin NTU Join Date: Aug 2009 Location: Taipei, Taiwan Posts: 601
Re: Perceptron Learning Algorithm

Quote:
 Originally Posted by cool8137 I think, the probability depends on the number of data. Just as our Hypothesis function h converses towards the Target Function f, once all of the training data (x) agrees with the training values (y), the iteration stops, before it actually reaches f (simply because our sample training data satisfies to the final h, which is g) For example: if the target function was a 45degree st. line (x2=x1), and there was only one training data say ((x1(1),x2(1)),y(1))=((1,2),+1), and if our first hypothesis function was the horizontal axis itself, the Perceptron Algorithm would stop in its first iteration, and conclude the the horizontal-axis to be close to the Target function (which was actually 45degree line through origin). But if we increase the number of data, the hypothesis function is forced to converge towards the target function, with more iterations. But there will always be some discrepancy i guess, unless you are very lucky.
Indeed. I've made a similar comment here:

http://book.caltech.edu/bookforum/sh...31&postcount=4
__________________
When one teaches, two learn.
#15
04-08-2012, 03:49 PM
 htlin NTU Join Date: Aug 2009 Location: Taipei, Taiwan Posts: 601
Re: Perceptron Learning Algorithm

Quote:
 Originally Posted by GraceLAX I think it would be interesting if we can all input our actual numbers and you later show a histogram of what people entered on their homework solutions. ;-)
I cannot speak for the Caltech instructor but in my NTU class I ask each student to do so on there own (repeating the procedure for, say, 1000 times) and plot the histogram. That is an interesting first assignment.

Quote:
 Originally Posted by GraceLAX I'm having a hard time deciding how to answer the multiple choice Q 7-10. The answer depends upon if I use log or linear scaling. Aren't CS algorithm efficiencies usually classified in log scaling? Or am I over-thinking this?
I personally don't see any need to consider scaling.

Quote:
 Originally Posted by GraceLAX If an algorithm always converges would the Pr(f(x) ne g(x)) = 0?
You can see my replies here:

http://book.caltech.edu/bookforum/sh...31&postcount=4

Hope this helps.
__________________
When one teaches, two learn.
#16
04-08-2012, 04:59 PM
 IamMrBB Invited Guest Join Date: Apr 2012 Posts: 107
Re: Perceptron Learning Algorithm

For answering Q7 and Q9: (just as an example) is 25 closer to 5 or closer to 50?

In other words is "closest" in q7/q9 defined using the absolute or relative difference.

25/5 = 5 and 50/25=2 so 25 is closer to 50 than to 5 using relative difference, while using absolute distance, 25 is closer to 5 than to 50.

Hope the course staff can confirm which definition to use in answering the question.

Many thanks!
#17
04-08-2012, 05:01 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,478
Re: Perceptron Learning Algorithm

Quote:
 Originally Posted by IamMrBB For answering Q7 and Q9: (just as an example) is 25 closer to 5 of closer to 50? In other words is "closest" in q7/q9 defined using the absolute or relative difference. 25/5 = 5 and 50/25=2 so 25 is closer to 50 than to 5 using relative difference, while using absolute distance, 25 is closer to 5 than to 50. Hope the course staff can confirm which definition to use in answering the question. Many thanks!
Please use absolute distance, not ratio.
__________________
Where everyone thinks alike, no one thinks very much
#18
04-08-2012, 10:50 PM
 virginiatraweek@gmail.com Junior Member Join Date: Apr 2012 Posts: 7
Re: Perceptron Learning Algorithm

I understand how to write the code to generate a random line and random points, which are assigned +/- based on their location relative to the line. (I'm assuming that [-1,1]x[-1,1] means the x-y plane (the typical axis that I've been seeing since middle school... correct me if I'm wrong and that notation means something like binary space...)

I understand setting the initial weights to 0.

Here is where I'm getting confused:

When you say "sign(w0+w1x1+w2x2)", where if the function is positive, the outcome is +1 and visa versa, does the function itself actually generate a negative number? If so, how do you get it to generate a negative number when your learning algorithm takes steps of positive 1?

Let's say that my f function is something simple like y=2x. Let's say that my random points lie on each side of the line such that I end up with the following points:
(1,1,3), (1,3,7), (1,2,3), and (1,4,7). These map ++ and - -, since they are on opposite sides of the line.

During the initial step, setting the weights equal to zero yields zero on each of these functions. So, we iterate once by setting the weights equal to 1. Plugging the weights into the first two points yields a positive value. (1+1+3) and (1+3+7) Yet, the bottom two points are still positive. As long as my iterative step is a positive 1, I can't get a negative number in the bottom rows. How does that work? Is that even how the learning is supposed to function?
#19
04-09-2012, 01:25 AM
 jsarrett Member Join Date: Apr 2012 Location: Sunland, CA Posts: 13
Re: Perceptron Learning Algorithm

Quote:
 Originally Posted by virginiatraweek@gmail.com Let's say that my f function is something simple like y=2x. Let's say that my random points lie on each side of the line such that I end up with the following points: (1,1,3), (1,3,7), (1,2,3), and (1,4,7). These map ++ and - -, since they are on opposite sides of the line. During the initial step, setting the weights equal to zero yields zero on each of these functions.
Not quite. The "guess" made at each iteration puts these points at zero, but then you compare those zeros with your data, and you see that they should have been -1 or +1 depending on the point. Therefore your current hypothesis is bad, and should be improved, a la w += y*x[n]

Quote:
 Originally Posted by virginiatraweek@gmail.com So, we iterate once by setting the weights equal to 1.
The update step is to move your classifier line by considering *only* 1 mis-classified point. And importantly, to update the line in the specific way that makes sure that point will then be classified correctly.

Quote:
 Originally Posted by virginiatraweek@gmail.com Plugging the weights into the first two points yields a positive value. (1+1+3) and (1+3+7) Yet, the bottom two points are still positive. As long as my iterative step is a positive 1, I can't get a negative number in the bottom rows. How does that work? Is that even how the learning is supposed to function?
Take a closer look at the interpretation of w. w is a 3-vector that describes a line in 2-d. The augmentation we do to make PLA convenient to implement has a specific interpretation of w;
let k =<w[1], w[2]>. k is like a direction of a gradient, where it goes linearly from 0 to 1 in the length of k. w[0] is a distance along k we draw our line at.

This means that the dot product of x[n] and w can be thought of as a measure of "agreement". By the 2-d vector analogy from class(which holds in 3d), you can see that in one simple step we can improve this "agreement" from bad to good because we know which way in the 3-space must be better (y[n]*x[n]). The miracle of the Perceptron is that just by doing this several times, we *will always* arrive at an acceptable answer.
#20
04-09-2012, 05:26 AM
 fattie Junior Member Join Date: Apr 2012 Posts: 1
Re: Perceptron Learning Algorithm

Another question: My PLA converges, there's no problem with that. But given sample sizes (N = 10 and N = 100), I have to choose the same answer for both iterations questions. Is that OK?

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 07:53 PM.