Q: I am working on homework4 and came across a minor discrepency in the description. According to the contour map in section 3 it appears that the start point is at ~ (2.0,0.6,0.5) and the finsih is at ~ (2.4,0.7,0.5) (which is what I based my raw data plot on). However, later in the homework description in section 4.4.2 it references the location of food and start points oppositely.
Just wanted to know which data to use or if it matters.

A: The BOBposition data has the start and end points contained in it. The first point is the start, the last is the end, go ahead and base your analysis on those points.

Q: I think I understand what gradient descent does: if y=x^2, G.D. will take you to the point (0,0) which is the local (and global) minimum of the function, is this right?

Now, I think it makes sense to assume that in HW 4 G.D. does not take you to the bottom of the terrain, rather, it's minimizing something else.
Let's say it minimizes the energy, that would be the 'z' components of the terrain matrix.
But, if it's minimizing time, then, considering that we have no information about the time, nor anything like 't(x,y)', how can we minimize it? At first I thought that minimizing the time would be to take the straight line between the 2 points, but since the terrain is rather complex, the shortest path might be a path other than the straight line. So, how does G.D. minimize time?

And,

BOB's movement toward the food has a definite path: BOBposition matrix.Therefore there's nothing to be minimized to it. So my guess is that we're trying to compare BOB's path to the minimum energy (or time) path that we get through G.D. The one that has a smaller difference, is the one that BOB is optimizing (energy or time). Is this correct?
But then again if we can't minimize time, how can we compare it to BOB's path?

A: I think I can clear up your confusion by helping you see how we are applying gradient descent in this case. Think of gradient descent as similar to least squares - in this case we are using it for fitting a function to our data. We choose an equation with unknown parameters, then use gradient descent to fit that function to our data. So we might have y = ax + b, with a and b unknown, and we have data for x and y. We can use gradient descent to solve that problem quickly. Also, gradient descent has advantages when dealing with many many parameters. The minimum gradient descent tries to find is the minimum error between the fit and the data.

The equation we choose to attempt to fit is up to us. ie, I gave you the suggestions of the fits. You try to fit them (if you follow the steps you will do so), then whichever one fits better shows you which is more likely to be optimized - the equation for energy, or the equation for time.

For time, you DO have that information, if you read the description is states that time starts at 0, and increments at each data point by 10 seconds. You have the right instinct, if BOB moves straight towards the food (straight in an x,y sense, since he would have to climb the mountain to go straight toward the food), he's optimizing time, since it takes less steps to get there than to go around at a constant z.

The item you compare is just error between the equation you predict and the data for each equation (the linear, and the nonlinear one). No numerical value of time comparisons is needed, since it is not asked for. Remember also that you are only using G.D. on the linear case, for simplicity, and you'll use fminsearch for the nonlinear case. Just read the description carefully on that one, it's meant to tell you almost exactly each step to make in matlab.

Q: For problem 4.4.2, you said "beginning a new m-file such as BOBModel.m". What's the prupose of doing that? Is it served as a function to calculate Ax=b? Also, what should be inside the m-file function? Is it the gradient descend code only?

I tried to run the whole statement u provided , but get some thing like "Error: "res" was previously used as a variable, conflicting with its use here as the name of a function or command."

A: I was suggesting you put all the code into one file for your assignment, gradient descent and all. I fixed the link. Sorry about that, somehow the files were deleted on the server, perhaps due to the maintenance they were just doing. With the res error, watch out for a missing *, as it sounds like you have something like this: res( blah), and then matlab thinks you're calling a function.

Q: In the background info section to tell us that the food BOB is trying to get to is at a location (2.4, 0.7 , 0.5). I assume this is the actual point coordinates that you want us to use and not just a random example.

I then plotted the data using surf and plotted a starting point with the SAME altitude as the food (zpoint = 0.5) but different x and y values. I used the food location as the endpoint.

My problem: The starting point I plotted is above the terrain (like in the air) and the endpoint that you gave us for the food location is underneath the ground. This seems incorrect b/c BOB should be travelling on the actually terrain, not above and below it, and it is hard to show 2 points that are on different sides of the surface of the terrain. I could alter my starting point to be under the ground like the food point, but that still is not ON the terrain. If we are supposed to be using points exactly on the terrain, then how do we find those? If not, what am I doing wrong?

A: You're problem is just that you're using the wrong points. Use the two points given in the document as 'start' and 'location.' They are the same as the first and last point in BOBposition. Plot them as explained in the assignment document, using plot3 and the line type as '*'. Try to follow along with the code samples (type them in rather than copying and pasting).

Q: I'm having trouble in the computer lab right now with BOBModel. I can get it to run, and then I get 2 values for x. Then I switched the program to run for y.....and it will return 2 values for y. The problem is I'm not sure what to do with these points to have them 'fit the graph'. I was in class today but still am having problems...Help?

A: 1) Come to office hours at the muir woods coffee shop, 1-2 tomorrow for help. I'll also be coming by the CSB115 lab periodically during the day, and I may arrange a help session in the evening as well, but my schedule of the day isn't set yet.

2) those values you get are like the coefficients we got for the least squares homework. Those are the coefficients of the line. So the line is defined as

y_model= x(1) + x(2)*time

where x(1) and x(2) are the coefficients you computed, not the xposition values of the data. Then you have a model, and you can use that to compute y's by putting the time array into the equation I just wrote. The questions then ask you to compare those y's you calculated with the actual data values by E = norm(y_data - y_model);

Q:I understand that we are to plot the results in terms of (res_save), but i am unclear exactly how to go about that. When i enter

plot(res_save(1,:),'r');

a very strange line shows up my plot.

A: I think I can clear up your question. res_save is a record of the residual error in the approximated solution to Ax=b, ie r = Ax - b, and res = r^T * r (so you get one number). The smaller that difference is, the closer you are to solving Ax=b. This plot is not required unless explicitly mentioned in the homework, though you can include it.
In terms of plots, just give what was asked for in the questions. If you want, you might want to plot the actual data and the fit on the same plot (i.e. plug the time array into the equation for the line y = a(1) + a(2)*t, x = .... That will give you a 'sanity check' to see how close you are to fitting your data.
The error is determined quantitatively in this case as E=norm(y_data-y_model) + norm(x_data-x_model). That is your criterion for fitting the data. The residuals are for how close your gradient descent algorithm is to finding the unknown coefficients. It doesn't say anything about the actual fit to the data - if you had data moving up and down wildly, the best linear fit you could get might converge nicely to something very small for res_save, but the straight line can only fit the curved data so closely, res_save doesn't account for that, that is why we look at the difference at every point between the square of the data minus the model fit.

Please come to office hours to discuss it if there is any confusion. Also I'm going to try to arrange a help session for tomorrow night after 6:30 or so. My schedule is still in flux for tomorrow so I'll post something on the web site when I know.

Q: IM having alot of trouble figuring out how to visualize the gradient
decent graph. My code doesnt differ from the stuff that was given but i
dont know why i can't see the graph. Any segestions of points to other
referances?

A: What are you trying to plot is the question to ask yourself. Gradient descent is giving you the coefficients of a line fit like least squares, y = a(1) + a(2) * time, where you are determining a(1) and a(2) so that you fit the y data vs. time or x data vs. time the best possible way you can. So if you wanted to plot the fit vs. the data, you might want to do

plot(time, BOBposition(:,1) )
hold on;
xfit = x(1) + x(2)*time; %where x here is the coefficient you found in gradient descent...
plot(time, xfit,'r')

Please see chapter 5 of the numerical methods book posted on the website. You can also search for gradient descent, least squares, and other questions at www.mathworld.com since they have some useful definitions and short descriptions.

Please come to office hours 1-2 at muir woods tomorrow for more discussion in depth, other questions, etc. Also I'm trying to arrange an evening help session after 6:30pm tomorrow. I spent some time on this in lecture, and if you couldn't make it please get notes from someone as I gave many hints. If you did come and were still confused just come to office hours for direct discussion, or check on the web page for the help session information post.

Q: did you want us to use the points that you gave us in the beginning of the assignment as our endpoint?-- im talking about 2.4, 0.7,0.5

A: Just use the points as they appear in the code example lines.  That's best.  They are the same as the first and last data point in the BOBposition data.

Q: On the homework on section 4.4.4. I'm doing actually what you describe on the sheet and I keep getting the same errors as follows.

??? Undefined function or variable 'y'.

Error in ==> NLBOBFit>@(x) bobnonlinearfunction(x,t,y) at 9
[estimated_C, n,m, output ]= fminsearch(@(x)
bobnonlinearfunction(x,t,y),initialguess,options);

Error in ==> fminsearch at 175
fv(:,1) = funfcn(x,varargin{:});

Error in ==> NLBOBFit at 9
[estimated_C, n,m, output ]= fminsearch(@(x)
bobnonlinearfunction(x,t,y),initialguess,options);

A: y is the data, so I started this one off with passing in the y data for BOBposition - ie

y=BOBposition(:,2);

Then make the function call. That should clear up your error. Also be sure to clear the variables x and y from the gradient descent algorithm before calling this function.

Q: I'm at the end of 4.4.2 and I don't know exactly how to change matrix A to be for the y data. Ax=b needs to be changed, right? To By=something? What else do I need to change?

A: for the A matrix, when you build it, no change is needed, since time is the same either way.

A = [ones(size(BOBposition(:,1)) t'];

The b array is the change...

b= BOBposition(:,2); % so change the column to 2 instead of 1. That's it!!!

Q: So I did the gradient descent for fitting x, and the output in Matlab was:

A =

6         180
180        7920

Is that correct? If it is, great. If not, what's going on, I did exactly what the assignment asked

A: The A matrix doesn't change because that's what you physically entered, after you multiplied by the transpose of A.  What you are looking for is the x that pops out of the gradient descent code.  Look at that, and let me know what you see.  Yes, computing the y coefficients is the simple change of that one little number:)

Q: Near the middle of page six you state that equations need to be created
for each x, y, and z variable, but after the gradient descent script it
says only y has to be done. I think I'm just confusing myself, because
we're supposed to be doing gradient descent in x and y in regards to z. So
gradient descent doesn't actually have to be done on z does it?

A: Yes you're just finding xdata and ydata fits, no need for z on the gradient descent code. Just find what it asks for. Basically if he's going straight for the food, he's not concerned about z, so we neglect fitting that in the linear case.

Q: For the gradient descent it says we need the start and location
variables, although I don't understand how they actually play into the
gradient decent. We just end up creating an A and b matrix, but never
actually use the start and location specifically. I was looking at the
"steepest_descent.m" code you provided, and it's a somewhat similar
situation. Are the start and location just erroneous?

A: The start and location variables don't actually come into play except for the plots (when plotting the terrain), so yes those aren't absolutely necessary in the GD code. It's just the first and last data point of BOBposition.

Q: The last question is that when I get the gradient descent script working,
the values returned for x and y are a 2 x 1 matrix. Shouldn't there only
be one value returned? Or is it the distance and direction of each
variable? (I pulled that from the lecture 14 notes).

A: For the x fit and y fit of GD, you are, for each, fitting a line for the relationship of xdata vs. time and ydata vs. time. The line is defined by the two coefficients, a(1) and a(2). In the GD code we use x as the coefficient name. So you find x(1) and x(2), and that corresponds to the coefficient you're trying to find for the line:

Y_model = x(1) + x(2)*time

or

X_model = x(1) + x(2)*time

You could just as easily replaced x with a in the GD code for clarity. So the x is the same as computing the a from linear least squares (in the sense of what it represents, not how you compute it):

x = A\b or equivalently a = A\b

I'm trying to break the habits of people getting stuck with intrinsic meanings for variables. It's just a space to fill. But I apologize for any confusion.

oh and the statement I made about the coefficients I just realized could be confusing in one regard specifically - realize there are different coefficients for the x_model fit and the y_model fit (i.e. each has a 2x1 vector that pops of of the GD code which can be different).

Q: In the linear fit, the output for x and y are 2X1 and the BOBposition(:,1)
and BOBposition(:,2) are 6X1 so the dimensions do agree. so the norm
cannot be computed since they dont agree.

A: The output of the linear fits (the 2x1 vectors, in this case I'm calling them a to avoid confusion right now) are the unknown coefficients of the line:

Y_model = a(1) + a(2)*time

Once you have those coefficients you have to put the time array t into the above equation and you get Y_model the size of Y_data. Then you do the norm on Y_model - Y_data. Does that make sense? So you find the line, then compute what the line predicts at each time value, and compare that to the actual recording.

So the x and y coming out of gradient descent, the ones that are 2x1, are not the same as the actual fitted data. They are the coefficients that determine the line fit. So once you have those coefficients you have to do what I said above and compute the fitted model.

Q: I got my gradient descent code to work, but I'm not completely sure what those numbers are though, they're the coefficients right?

A: Yes, coefficients of the line, you've got it,

y_model = a(1) + a(2)* time

So now that you have those, put the time through to compute y_model.  Then you'll compare that with the y of the data using the E= norm(y-y_model) equation.  The questions ask specifics about the calculations.