LFD Book Forum PLA - Need Guidance
 User Name Remember Me? Password
 FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
07-11-2012, 03:48 PM
 samirbajaj Member Join Date: Jul 2012 Location: Silicon Valley Posts: 48
PLA - Need Guidance

Greetings!

I am working on the Perceptron part of the homework, and having spent several hours on it, I'd like to know if I am proceeding in the right direction:

1) My implementation converges in 'N' iterations. This looks rather fishy. Any comments would be appreciated. (Otherwise I may have to start over :-( maybe in a different programming language)

2) I don't understand the Pr( f(x) != g(x) ) expression -- what exactly does this mean? Once the algorithm has converged, presumable f(x) matches g(x) on all data, so the difference is zero.

Thanks.

-Samir
#2
07-11-2012, 05:13 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: PLA - Need Guidance

Quote:
 Originally Posted by samirbajaj I don't understand the Pr( f(x) != g(x) ) expression -- what exactly does this mean? Once the algorithm has converged, presumable f(x) matches g(x) on all data, so the difference is zero
On all data, yes. However, the probability is with respect to over the entire input space, not restricted to being in the finite data set used for training.
__________________
Where everyone thinks alike, no one thinks very much
#3
07-12-2012, 07:30 AM
 jakvas Member Join Date: Jul 2012 Posts: 17
Re: PLA - Need Guidance

If we try to evaluate Pr(f(x)!=g(x)) experimentaly how many random verification points should we use to get a significant answear?

I am tempted to believe that Hoeffding's inequality is applicable in this case to a single experiment but since we are averaging out over very many experiments I'm not sure on how to choose the amount of those verification data points (I ultimately worked with 10000 per experiment just to be sure).
#4
07-12-2012, 09:56 AM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: PLA - Need Guidance

Quote:
 Originally Posted by jakvas I am tempted to believe that Hoeffding's inequality is applicable in this case to a single experiment but since we are averaging out over very many experiments I'm not sure on how to choose the amount of those verification data points (I ultimately worked with 10000 per experiment just to be sure).
Indeed, the average helps smooth out statistical fuctuations. Your choice of 10000 points is pretty safe.
__________________
Where everyone thinks alike, no one thinks very much
#5
07-16-2012, 09:19 PM
 jtwang Junior Member Join Date: Jul 2012 Posts: 1
Re: PLA - Need Guidance

How would you determine f(x) == g(x) exactly - since the set of possible hypotheses is infinite (3 reals), wouldn't Pr(f(x) != g(x)) == 1? Obviously you could choose some arbitrary epsilon but then that wouldn't be "exactly."
#6
07-16-2012, 09:39 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: PLA - Need Guidance

Quote:
 Originally Posted by jtwang How would you determine f(x) == g(x) exactly - since the set of possible hypotheses is infinite (3 reals), wouldn't Pr(f(x) != g(x)) == 1? Obviously you could choose some arbitrary epsilon but then that wouldn't be "exactly."
is per point . It may be true for some 's and false for others, hence the notion of probability that it's true (probability with respect to ). We are not saying that is identically equal to .
__________________
Where everyone thinks alike, no one thinks very much
#7
01-15-2013, 07:20 PM
 gah44 Invited Guest Join Date: Jul 2012 Location: Seattle, WA Posts: 153
Re: PLA - Need Guidance

Quote:
 Originally Posted by jtwang How would you determine f(x) == g(x) exactly - since the set of possible hypotheses is infinite (3 reals), wouldn't Pr(f(x) != g(x)) == 1? Obviously you could choose some arbitrary epsilon but then that wouldn't be "exactly."
There are two lines, the original line that determines the separation between +1 and -1, and the line determined by the PLA. The questions ask what fraction of the space is different between the two lines. If they don't cross, that is the area between the two lines (divided by four, the total area). If they do cross, it is the area of two triangles (or, sometimes, quadrilaterals).

Each line can crosses two of the sides of the square. (I suppose it could also go right through a corner, but not likely). Handling all the possible combinations of the two lines is a lot of work.

In another thread I discussed how I did it, only counting, and computing the area of, cases where both lines go through the top and bottom. That is about 30% in my tests. By symmetry, there should also be 30% where both go through the left and right sides of the square The remaining cases might have a little less area, but I based my answer on just the lines going through the top and bottom of the square. Seemed more interesting than the choose random point method.
#8
01-14-2013, 07:18 PM
 vbipin Member Join Date: Jan 2013 Location: Shanghai Posts: 18
Re: PLA - Need Guidance

Quote:
 Originally Posted by yaser Indeed, the average helps smooth out statistical fuctuations. Your choice of 10000 points is pretty safe.
Dear Professor,

Can you kindly explain how we can calculate this number. How can we ensure that the number is "sufficiently large"

Thanks,
Bipin
#9
01-14-2013, 07:40 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: PLA - Need Guidance

Quote:
 Originally Posted by vbipin Dear Professor, Can you kindly explain how we can calculate this number. How can we ensure that the number is "sufficiently large" Thanks, Bipin
The probability for a single random point to be misclassified is, say, . Therefore the variance for one point (1 if misclassified, 0 if classified correctly) is which is at most 0.25 independently of . If you average the misclassification value of 10000 points, the expected value will be (which is what you want) and the variance will be at most 0.25/10000 (because of independence). The standard deviation which is the square root of this variance gives you an indication of the "error bar" around the expected value that you are likely to get in your estimate. In the multiple-choice setup, we want the error bar to be small enough to make it highly unlikely that your estimate will take you away from the correct answer to the nearest incorrect answer. This is why 10000 is "sufficiently large" in this case.
__________________
Where everyone thinks alike, no one thinks very much
#10
01-08-2013, 02:15 PM
 dobrokot Junior Member Join Date: Jan 2013 Posts: 3
Re: PLA - Need Guidance

Quote:
 Originally Posted by jakvas I'm not sure on how to choose the amount of those verification data points (I ultimately worked with 10000 per experiment just to be sure).
Hoeffding inequality given in same lesson can help to choose number of points. g(x)!=f(x) can be thinked as red marble

 Tags convergence, iterations, perceptron, pla

 Thread Tools Display Modes Hybrid 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 12:30 AM.

 Contact Us - LFD Book - Top