LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 1 (http://book.caltech.edu/bookforum/forumdisplay.php?f=130)
-   -   Perceptron Learning Algorithm (http://book.caltech.edu/bookforum/showthread.php?t=284)

GraceLAX 04-07-2012 12:35 AM

Perceptron Learning Algorithm
 
I'm trying to program the perceptron example but can't figure out how to assign the sign of the first step.

I drew a line between two points on the xy plane [-1,1] in both directions.

Then I randomly generated another 10 points, assigning them +1 if they fell above the line and -1 if they fell below the line. I stored those values in ideal function g.

Then I gave each point a random first guess of +1/-1 as my initial function h.

If I start with all the weights as 0, then w*x = 0 for all points.
At that rate, PLA will never converge.

What is my conceptual error?

yaser 04-07-2012 12:51 AM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by GraceLAX (Post 1015)
I drew a line between two points on the xy plane [-1,1] in both directions.

Then I randomly generated another 10 points, assigning them +1 if they fell above the line and -1 if they fell below the line. I stored those values in ideal function g.

That would be f (the target function). The symbol g is reserved for the final hypothesis that the PLA will produce (which should be close to f).

Quote:

Originally Posted by GraceLAX (Post 1015)
Then I gave each point a random first guess of +1/-1 as my initial function h.

The initial function h must be a perceptron rather than a random assignment of \pm 1's.

Quote:

Originally Posted by GraceLAX (Post 1015)
If I start with all the weights as 0, then w*x = 0 for all points.
At that rate, PLA will never converge.

If you start with a zero weight vector, and take {\rm sign}(0)=0, pick any point for the first iteration. When you update the weight vector, {\bf w}+{\bf x}_n y_n uses the target y_n, so that won't be zero.

lacamotif 04-07-2012 10:52 AM

Re: Perceptron Learning Algorithm
 
Hi

I have a question about how weighting is assigned and the meaning of the PLA . For point a1 which has assignment 1, does w(a1.y) + w(a1.x) = 1 ? ( '.' denotes subscript)

And then, for point a2 which has assignment -1, would
w(a1.y) + w(a1.x) + w(a1.x) + w(a2.x) = -1 , and so on?

To adjust weighting of w for misclassified points, is w.x2 = w.x1 + x.2 * y.2

Thank you for the help!

yaser 04-07-2012 12:08 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by lacamotif (Post 1017)
Hi

I have a question about how weighting is assigned and the meaning of the PLA . For point a1 which has assignment 1, does w(a1.y) + w(a1.x) = 1 ? ( '.' denotes subscript)

And then, for point a2 which has assignment -1, would
w(a1.y) + w(a1.x) + w(a1.x) + w(a2.x) = -1 , and so on?

To adjust weighting of w for misclassified points, is w.x2 = w.x1 + x.2 * y.2

Thank you for the help!

Let me use the book notation to avoid confusion. You have two points {\bf x}_1 and {\bf x}_2 (which you called a1 and a2) and their target outputs (which you called assignment) are f({\bf x}_1)=+1 and f({\bf x}_2)=-1.

Either point, call it just {\bf x} for simplicity, is a vector that has d components {\bf x}=x_1,x_2,\cdots,x_d. Notice that bold {\bf x} denotes a full data point, while italic x denotes a component in that data point. We add a constant 1 component to each data point {\bf x} and call the component x_0 to simplify the expression for the perceptron. If the weight vector of the perceptron is {\bf w}=w_0,w_1,w_2,\cdots,w_d (where w_0 takes care of the threshold value of that perceptron), then the perceptron implements

{\rm sign}(w_0x_0+w_1x_1+w_2x_2+\cdots+w_dx_d)

where `{\rm sign()}' returns +1 if its argument is positive and returns -1 if its argument is negative.

Example: Say the first data point {\bf x}_1=(3,4) (two dimensional, so d=2). Add the constant component x_0=1 and you have {\bf x}_1=(1,3,4). Therefore, the percepton's output on this point is {\rm sign}(w_0+3w_1+4w_2). If this formula returns -1 which is different from the target output +1, the PLA adjusts the values of the weights trying to make the perceptron output agree with the target output for this point {\bf x}. It uses the specific PLA update rule to achieve that.

lacamotif 04-07-2012 08:29 PM

Re: Perceptron Learning Algorithm
 
Thank you for your reply!
So, y.n for point 2 has nothing to do with point 1, correct?

Also, since w.0, w.1 and w.2 are different numbers, do you need multiple points to assess the values of the three w's?

Further, is updated w like an array, dependent on which n is being chosen, or is it one uniform number that is applied to all x's?

yaser 04-07-2012 11:22 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by lacamotif (Post 1023)
Thank you for your reply!
So, y.n for point 2 has nothing to do with point 1, correct?

Also, since w.0, w.1 and w.2 are different numbers, do you need multiple points to assess the values of the three w's?

Further, is updated w like an array, dependent on which n is being chosen, or is it one uniform number that is applied to all x's?

Indeed, the different points in the training data set are treated one at a time by PLA, independently of the rest of the points.

All three components of the weight vector {\bf w}=w_0,w_1,w_2 are simultaneously updated by PLA at each iteration, and there is more than one data point to update {\bf w} depending on which points are misclassified at a given time as the algorithm runs.

Mikhail 04-08-2012 02:05 AM

Re: Perceptron Learning Algorithm
 
Hello!
I have some misuderstandings with PLA.

Should we update w accordings to only one misclassified point at an iteration or through all the misclassified points at the given iteration?

thanks

yaser 04-08-2012 02:30 AM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by Mikhail (Post 1028)
Hello!
I have some misuderstandings with PLA.

Should we update w accordings to only one misclassified point at an iteration or through all the misclassified points at the given iteration?

thanks

One misclassified point at a time, and that's what counts as an iteration.

GraceLAX 04-08-2012 04:22 AM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by yaser (Post 1016)
That would be f (the target function). The symbol g is reserved for the final hypothesis that the PLA will produce (which should be close to f).


The initial function h must be a perceptron rather than a random assignment of \pm 1's.



If you start with a zero weight vector, and take {\rm sign}(0)=0, pick any point for the first iteration. When you update the weight vector, {\bf w}+{\bf x}_n y_n uses the target y_n, so that won't be zero.

Thanks for the clarification. That helped quite a bit.

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'm shocked by the speed with which PLA converges. I never would have
guessed that until I actually coded it up. This is a very interesting and
intellectually satisfying exercise!

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?

If an algorithm always converges would the Pr(f(x) ne g(x)) = 0?

kkkkk 04-08-2012 04:40 AM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by yaser (Post 1029)
One misclassified point at a time, and that's what counts as an iteration.

Hi Prof,

For my code, I consider 1 iteration as a scan from beginning to end through the entire data set x and correcting any misclassified points.

I have already submitted my homework and I believe I cannot resubmit.

Thanks,
KK.

tcristo 04-08-2012 08:46 AM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by GraceLAX (Post 1033)

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 :D

cool8137 04-08-2012 11:13 AM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by GraceLAX (Post 1033)
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.

htlin 04-08-2012 03:39 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by tcristo (Post 1038)
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 :D

This is what I'd do, too. :)

htlin 04-08-2012 03:41 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by cool8137 (Post 1048)
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

htlin 04-08-2012 03:49 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by GraceLAX (Post 1033)
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 (Post 1033)
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 (Post 1033)
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.

IamMrBB 04-08-2012 04:59 PM

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!:bow:

yaser 04-08-2012 05:01 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by IamMrBB (Post 1062)
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!:bow:

Please use absolute distance, not ratio.

virginiatraweek@gmail.com 04-08-2012 10:50 PM

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?

jsarrett 04-09-2012 01:25 AM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by virginiatraweek@gmail.com (Post 1073)
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 (Post 1073)
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 (Post 1073)
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.

fattie 04-09-2012 05:26 AM

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?

htlin 04-09-2012 12:21 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by fattie (Post 1078)
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?

The homework asks you to choose whatever you observe. It is hard to comment on the correctness here before the deadline. ;)

kurts 04-09-2012 12:31 PM

Re: Perceptron Learning Algorithm
 
I also had mixed feelings about the choices we were given on problem #9. My result from simulation was right between two answers, and, strictly speaking, if I were to take the absolute closest answer, I got an answer that I felt was wrong, so I chose the other one. I felt that the purpose of the question was to highlight what, if any, difference N makes in the number of steps to converge. So, based on the professor's response about choosing the absolute closest answer, I think I chose poorly.

davies 04-09-2012 01:58 PM

Re: Perceptron Learning Algorithm
 
Hello Professor,

I have a question regarding updating w on each PLA iteration. If we always assign x0 = 1, how are we reasonably updating w0? By the vector addition, it will always be updated by the value y * x0 = -1 or +1, and if the true w0 is not an integer the PLA will never be able to converge to that value.

Would it be more appropriate to setup such that we divide each component of the true w by w0, so that w0 = 1 always? This way I know it is an integer and my PLA does not have to wander for a non-integer value. Or even, if I know w0 is always 1, I might not even include it in the PLA since I know it is 1 by setup.

Thank you,
-Aaron

mlore 04-09-2012 05:06 PM

Re: Perceptron Learning Algorithm
 
Hmm, I have the same problem. The average number of iterations for the case where N = 10 and the case where N = 100 are clearly "different" in the way that one would expect, but with respect to the answer choices they are different relatively but identical absolutely.

virginiatraweek@gmail.com 04-09-2012 06:43 PM

Re: Perceptron Learning Algorithm
 
Can you explain the math in terms of the points I listed?

(1,1,3), (1,3,7), (1,2,3), and (1,4,7). These map ++ and - -

What exactly happens? During the first iteration, what actual numbers does the computer compare?

My eventual f vector should be (1,2,-1),right? That represents the line y=2x when rewritten 0=2x-y in matrix notation. Shouldn't my eventual result look pretty darn similar to that?

I really am trying on this, and I've literally taken all of the required prereq. courses. It's just that I'm not an engineer. The notations don't make as much sense unless I see it in some sort of context. I copied a python PLA script from the net, but python isn't my "native" language, so I'm still trying to figure out exactly what it does.

tcristo 04-09-2012 08:14 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by virginiatraweek@gmail.com (Post 1100)
Can you explain the math in terms of the points I listed?

(1,1,3), (1,3,7), (1,2,3), and (1,4,7). These map ++ and - -

What exactly happens? During the first iteration, what actual numbers does the computer compare?

My eventual f vector should be (1,2,-1),right? That represents the line y=2x when rewritten 0=2x-y in matrix notation. Shouldn't my eventual result look pretty darn similar to that?

I really am trying on this, and I've literally taken all of the required prereq. courses. It's just that I'm not an engineer. The notations don't make as much sense unless I see it in some sort of context. I copied a python PLA script from the net, but python isn't my "native" language, so I'm still trying to figure out exactly what it does.

There is a nice writeup in the Wiki which might help.

http://en.wikipedia.org/wiki/Perceptron

In particular, look at the section called Learning Algorithm Steps. It hopefully will get you started.

eghri 04-09-2012 08:53 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by davies (Post 1092)
Hello Professor,

I have a question regarding updating w on each PLA iteration. If we always assign x0 = 1, how are we reasonably updating w0? By the vector addition, it will always be updated by the value y * x0 = -1 or +1, and if the true w0 is not an integer the PLA will never be able to converge to that value.

Would it be more appropriate to setup such that we divide each component of the true w by w0, so that w0 = 1 always? This way I know it is an integer and my PLA does not have to wander for a non-integer value. Or even, if I know w0 is always 1, I might not even include it in the PLA since I know it is 1 by setup.

Thank you,
-Aaron

I had the exact same question. I believe your method of updating is the correct way:

w_0 = w_0 + y_i

However, there is usually a learning rate associated with the perceptron such as alpha, which would make the update on the intercept:

w_0 = w_0 + alpha * y_i

So you can see here that the algorithm would accommodate non-integer values. In our case, without a learning rate, we just have to hope it converges with an integer value intercept.

I actually had one case myself where it wouldn't converge. To avoid biasing my average results, I'm going to just run the algorithm to 100k iterations and throw out anything that doesn't fully converge.

tcristo 04-09-2012 09:27 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by eghri (Post 1105)
However, there is usually a learning rate associated with the perceptron such as alpha, which would make the update on the intercept:

w_0 = w_0 + alpha * y_i

So you can see here that the algorithm would accommodate non-integer values. In our case, without a learning rate, we just have to hope it converges with an integer value intercept.

Take a look at this thread. http://book.caltech.edu/bookforum/sh...43&postcount=6. Using the default alpha of 1 shouldn't have any effect on the number of iterations required to converge.

Quote:

Originally Posted by eghri (Post 1105)
I actually had one case myself where it wouldn't converge. To avoid biasing my average results, I'm going to just run the algorithm to 100k iterations and throw out anything that doesn't fully converge.

Assuming the data classes are linearly separable, the PLA should always converge. You might want to plot the training data for those cases where it won't converge. I had a problem during my initial implementation and after reviewing the plot realized that I had a bug in my update method.

virginiatraweek@gmail.com 04-09-2012 10:50 PM

Re: Perceptron Learning Algorithm
 
How do you calculate the desired output (dj), as shown on the wikipedia page?

ManUtd 04-09-2012 11:08 PM

Re: Perceptron Learning Algorithm
 
Virginia -

Desired output is a set of -1/+1 based on the signum function on N (x,y) points compared to the original line in the x-y plane.

mbell 04-10-2012 01:01 AM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by virginiatraweek@gmail.com (Post 1109)
How do you calculate the desired output (dj), as shown on the wikipedia page?

d_j is the same as y_j in our formulation - it's the known output value for x_j

A word of warning to others (although it sounds like everyone else on the forums is already past this point): You do in fact need to include w_0 (with x_i,0 = 1). I spent quite a while wrestling with my non-converging PLA until I realized this was the issue (and then some more time wondering why my P(f(x) != g(x)) values were so weird, until I realized that I'd failed to account for the extra w_0 when computing f(x) using a 2D x instead of the appropriate 3D version...)

I'd interpreted the value of w_0 from the in-class example as a threshold set by the bank for a credit-worthy customer, but now I realize that in fact it's one of the learned parameters, which makes perfect sense in retrospect. :o

rukacity 04-10-2012 06:58 AM

Re: Perceptron Learning Algorithm
 
While running through the population I first collect all the misfit points and then choose a random point to adjust the weights. The other approach could be to stop at the first misfit and correct the weights. What is practiced?

mariovela 04-10-2012 02:42 PM

Re: Perceptron Learning Algorithm
 
I chose to correct the weights at the first misfit, increase the count of iterations and start the algorithm again from the first point... it works fast so far... but I'm wondering if I should continue with the algorithm without re-starting again and stopping only when all points satisfy h(x)=g(x)...

shockwavephysics 04-11-2012 03:36 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by yaser (Post 1018)
Let me use the book notation to avoid confusion. You have two points {\bf x}_1 and {\bf x}_2 (which you called a1 and a2) and their target outputs (which you called assignment) are f({\bf x}_1)=+1 and f({\bf x}_2)=-1.

Either point, call it just {\bf x} for simplicity, is a vector that has d components {\bf x}=x_1,x_2,\cdots,x_d. Notice that bold {\bf x} denotes a full data point, while italic x denotes a component in that data point. We add a constant 1 component to each data point {\bf x} and call the component x_0 to simplify the expression for the perceptron. If the weight vector of the perceptron is {\bf w}=w_0,w_1,w_2,\cdots,w_d (where w_0 takes care of the threshold value of that perceptron), then the perceptron implements

{\rm sign}(w_0x_0+w_1x_1+w_2x_2+\cdots+w_dx_d)

where `{\rm sign()}' returns +1 if its argument is positive and returns -1 if its argument is negative.

Example: Say the first data point {\bf x}_1=(3,4) (two dimensional, so d=2). Add the constant component x_0=1 and you have {\bf x}_1=(1,3,4). Therefore, the percepton's output on this point is {\rm sign}(w_0+3w_1+4w_2). If this formula returns -1 which is different from the target output +1, the PLA adjusts the values of the weights trying to make the perceptron output agree with the target output for this point {\bf x}. It uses the specific PLA update rule to achieve that.

I have been trying to figure out why updating using w -> w + y_n * x_n works at all. I looked up the relevant section in the text, and there are a series of questions for the student that hint at the answer. I followed that logic to it's conclusion and it does seem to show that updating in that way will always give a w that is better (for the misclassified point) than the previous w. However, I cannot figure out how one comes up with this formulation in the first place. Is there a reference to a derivation I can read?

julien 04-11-2012 04:20 PM

Re: Perceptron Learning Algorithm
 
I think it would be interesting to obtain a detailed example with the first few steps used to initialize and train the perceptron. Or a complete example if anybody is willing to share their code.

I was unable to implement correctly the perceptron before the deadline, and after spending an additional 5h in this exercise today, I still don't have a proper implementation.
Programming is not the issue, I'm a developer, but my issue is how to apply the theory.

I feel it's important to successfully code this algorithm, so I can successfully apply the theories we will learn in the next few lectures.

mephistoyourfriend 04-12-2012 09:43 AM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by shockwavephysics (Post 1216)
I have been trying to figure out why updating using w -> w + y_n * x_n works at all. I looked up the relevant section in the text, and there are a series of questions for the student that hint at the answer. I followed that logic to it's conclusion and it does seem to show that updating in that way will always give a w that is better (for the misclassified point) than the previous w. However, I cannot figure out how one comes up with this formulation in the first place. Is there a reference to a derivation I can read?

The scalar product between x and w+x is always greater than the scalar product between x and w (unless x is a zero vector), which is obvious once you express it in terms of angles between the vectors and their lengths. Similarly, the product <x,w-x> is always less than <x,w>. Since the sign of the scalar product is the only thing you're interested in, then changing the sign from -1 to +1 is achieved by making the scalar product more positive (rather, less negative), which you do by adding x to w. It's not guaranteed that you can accomplish that in one step (if the length of x is smaller than the length of w and the angle between them is 180 degrees, you certainly can't), but given a sufficient number of steps, you will be able to nudge it into submission. That's how I see it at least.

zsero 04-15-2012 05:43 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by mephistoyourfriend (Post 1238)
The scalar product between x and w+x is always greater than the scalar product between x and w (unless x is a zero vector), which is obvious once you express it in terms of angles between the vectors and their lengths. Similarly, the product <x,w-x> is always less than <x,w>. Since the sign of the scalar product is the only thing you're interested in, then changing the sign from -1 to +1 is achieved by making the scalar product more positive (rather, less negative), which you do by adding x to w. It's not guaranteed that you can accomplish that in one step (if the length of x is smaller than the length of w and the angle between them is 180 degrees, you certainly can't), but given a sufficient number of steps, you will be able to nudge it into submission. That's how I see it at least.

There is a point what I think is not clearly explained. It took me a long time to realize that it's not true that exactly one point gets corrected in each step. The true statement is that at most one point gets corrected in each step. The illustration in the lecture as well as various comments in this forum would suggest that the vector addition will always "correct" a vector. It is not true. The vector addition will always "tune" the weights such that one vector gets "better", but it doesn't mean that it will be correct after that step.

zsero 04-15-2012 05:47 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by julien (Post 1220)
I think it would be interesting to obtain a detailed example with the first few steps used to initialize and train the perceptron. Or a complete example if anybody is willing to share their code.

I was unable to implement correctly the perceptron before the deadline, and after spending an additional 5h in this exercise today, I still don't have a proper implementation.
Programming is not the issue, I'm a developer, but my issue is how to apply the theory.

I feel it's important to successfully code this algorithm, so I can successfully apply the theories we will learn in the next few lectures.

I've written the algorithm just based on the lecture and it worked. Here is the "core" of the algorithm (written in Python / Numpy):

Code:

w = np.zeros( 3 )
done = False

while not done:
    wrongpoints = 0
    for p in points:
        if np.sign( np.dot(w, p) ) != targetFunction( p ):
            w = np.add( w, targetFunction( p ) * p )
            wrongpoints += 1
            break
    if wrongpoints == 0:
        done = True

If anyone is interested in the Python implementation, here is my full code with plotting:
https://gist.github.com/2395395

and the one for the experiments:
https://gist.github.com/2395409

rukacity 04-17-2012 02:33 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by zsero (Post 1306)
I've written the algorithm just based on the lecture and it worked. Here is the "core" of the algorithm (written in Python / Numpy):

Code:

w = np.zeros( 3 )
done = False

while not done:
    wrongpoints = 0
    for p in points:
        if np.sign( np.dot(w, p) ) != targetFunction( p ):
            w = np.add( w, targetFunction( p ) * p )
            wrongpoints += 1
            break
    if wrongpoints == 0:
        done = True

If anyone is interested in the Python implementation, here is my full code with plotting:
https://gist.github.com/2395395

and the one for the experiments:
https://gist.github.com/2395409

Argh! I am new to Python and did not know about numpy. It looks so much more concise than my code that has all the vector multiplication and what not. One thing I noticed is that you keep adding to weights for each wrongpoint whereas Yaser had mentioned to adjust it only once per iteration.

Correction: My bad! Missed the 'break' statement ;)

zsero 04-17-2012 02:35 PM

Re: Perceptron Learning Algorithm
 
Quote:

Originally Posted by rukacity (Post 1369)
Argh! I am new to Python and did not know about numpy. It looks so much more concise than my code that has all the vector multiplication and what not. One thing I noticed is that you keep adding to weights for each wrongpoint whereas Yaser had mentioned to adjust it only once per iteration.

No, that's what the break statement does. Once it found a wrong point, it corrects and then brakes the cycle and then the whole loop starts again.

Yes, numpy is the best thing ever made for Python! Pseudoinverse of a matrix? np.pniv :-)


All times are GMT -7. The time now is 12:16 AM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.