LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Homework 1

Reply
 
Thread Tools Display Modes
  #1  
Old 04-07-2012, 12:35 AM
GraceLAX GraceLAX is offline
Junior Member
 
Join Date: Apr 2012
Location: LAX
Posts: 4
Post 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?
Reply With Quote
  #2  
Old 04-07-2012, 12:51 AM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Perceptron Learning Algorithm

Quote:
Originally Posted by GraceLAX View Post
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 View Post
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 View Post
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.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #3  
Old 04-07-2012, 10:52 AM
lacamotif lacamotif is offline
Junior Member
 
Join Date: Apr 2012
Posts: 9
Default 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!
Reply With Quote
  #4  
Old 04-07-2012, 12:08 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Perceptron Learning Algorithm

Quote:
Originally Posted by lacamotif View Post
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.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #5  
Old 04-07-2012, 08:29 PM
lacamotif lacamotif is offline
Junior Member
 
Join Date: Apr 2012
Posts: 9
Default 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?
Reply With Quote
  #6  
Old 04-07-2012, 11:22 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Perceptron Learning Algorithm

Quote:
Originally Posted by lacamotif View Post
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.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #7  
Old 04-08-2012, 10:50 PM
virginiatraweek@gmail.com virginiatraweek@gmail.com is offline
Junior Member
 
Join Date: Apr 2012
Posts: 7
Default 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?
Reply With Quote
  #8  
Old 04-09-2012, 01:25 AM
jsarrett jsarrett is offline
Member
 
Join Date: Apr 2012
Location: Sunland, CA
Posts: 13
Default Re: Perceptron Learning Algorithm

Quote:
Originally Posted by virginiatraweek@gmail.com View Post
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 View Post
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 View Post
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.
Reply With Quote
  #9  
Old 04-11-2012, 03:36 PM
shockwavephysics shockwavephysics is offline
Member
 
Join Date: Apr 2012
Posts: 17
Default Re: Perceptron Learning Algorithm

Quote:
Originally Posted by yaser View Post
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?
Reply With Quote
  #10  
Old 04-12-2012, 09:43 AM
mephistoyourfriend mephistoyourfriend is offline
Junior Member
 
Join Date: Apr 2012
Posts: 1
Default Re: Perceptron Learning Algorithm

Quote:
Originally Posted by shockwavephysics View Post
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.
Reply With Quote
Reply

Thread Tools
Display Modes

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 Jump


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