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-06-2012 11:35 PM

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-06-2012 11:51 PM

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 09: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 11:08 AM

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 07: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 10: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 01: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 01: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 03: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 03: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.


All times are GMT -7. The time now is 06:31 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.