Professor Strang thank you for a straight forward lecture on Gradient Descent: Downhill to a Minimum and its relationship with convex function. The examples are important for deep understanding of this topic in numerical linear algebra.
If in calc 1 they introduced the term argmin for the place where the minimum occurred there would be less confusion as students often mistake argmin for the actual min.
his picture with grad(f) pointing up is a bit misleading around 9:00 I think. grad(f) is a vector in the x-y plane, pointing in the direction you should move in the x-y plane to maximize increase in f.
I think both of you and Prof. Strang are right. Actually, what Prof. Strang plotted on the board is level graph (just like the previous comment mentioned about). While we have a function f(x, y) = ax + by, we can plot the level graph by setting the f(x, y) = C (some constant). If we increase the constant level by level, we could observe that we're actually shifting the level graph in the direction of grad(f). That direction is perpendicular to the level graph. In my point of view, Prof. Strang did want to show that the gradient is perpendicular to the level graph. However, he didn't notice that the arrow he drew is pointing upward. This is probably the point that confused you.
First of all, 2x + 5y = 0 is not a plane, as Professor Strang says. Rather, it is a level "curve" of the plane described by f(x,y) = 2x + 5y (with f(x,y) set to 0). The level "curves" of a plane in 3D are parallel lines on the xy plane. Then, Professor Strang really makes an error when he says that the gradient is somehow perpendicular to the plane. No, the gradient is perpendicular to the level "curves" of the plane, or the parallel lines in the xy plane. And, all movement to any new z value is in the plane. I also think the way he drew the plane was very confusing, as he didn't even try to approximate its actual orientation in 3D.
How did he get all the equations of xk, yk and fk at 45:35? Specifically, how did he get (b-1)/(b+1) and vice versa? I shifted the equation to make xk+1 and yk+1 the subjects of the equations but instead I got xk+1 = xk (1-2sk), where xk = x0 = b.
I think he have already use the optimized step size (sk) for the iterration. He didn't tell us what is the sk looks like, while he just show us the finally equation to explain the idea of good or bad convergance.
at the limit [x,y]=[x,y]-[sx,bsy] and to minimize f=0.5x^2+0.5y^2, we must have |x|=|y|. So |x-sx|=|y-bsy| s=2/(1+b) and [x,y]=[x,y]-[sx,bsy]=[(1-s)x,(1-bs)y]. we got x=(b-1)/(b+1)*x_old, y=(1-b)/(b+1)*y_old etc...
I am hoping for a discussion about conventions of derivatives. Much of the stuff I've seen would make the gradient a row vector, which leads to the derivatives being the transpose of what he shows. In his example, the derivative a'x is 'a' which is contrary to intuition from single variable calculus though he uses intuition for x'Sx.
Yes I had the same objection. I think he glossed over the 1/2 present in the function. It's a multiple of the same vector so in the grand scheme of things I don't think it matters too much but with that being said having [x by] would have eased my mind
if f(X) = -ln(det(X)), gradient(f) = (derivatives of det(X))/det(X) in matrix form, which is the same as a matrix of the entries of X^-1 for each entry. I'm also not too certain myself, but this does make sense to me.
He is too long winded. Why not use a simple function of x,y. Find the derivatives and start dong a few iteration. Finally he gets to gradient descent. Gradient descent works but the are better algorithms. The line search idea is a good start. WTF is wrong with this guy? A simple python program or even excel would be much more meaningful. Thumbs down.
Gradient Descent is at 34:33
that helped thank you
thank you.
Professor Strang thank you for a straight forward lecture on Gradient Descent: Downhill to a Minimum and its relationship with convex function. The examples are important for deep understanding of this topic in numerical linear algebra.
Very clear and natural to follow the lesson. Thank Professor Strang so much. Btw, his books are also very wonderful.
Very natural way of teaching. Thank you sir
If in calc 1 they introduced the term argmin for the place where the minimum occurred there would be less confusion as students often mistake argmin for the actual min.
Thanks for this lol
Thank you so much
his picture with grad(f) pointing up is a bit misleading around 9:00 I think. grad(f) is a vector in the x-y plane, pointing in the direction you should move in the x-y plane to maximize increase in f.
True, this has been bothering me since last year when I started cal 3/
I think both of you and Prof. Strang are right. Actually, what Prof. Strang plotted on the board is level graph (just like the previous comment mentioned about). While we have a function f(x, y) = ax + by, we can plot the level graph by setting the f(x, y) = C (some constant). If we increase the constant level by level, we could observe that we're actually shifting the level graph in the direction of grad(f). That direction is perpendicular to the level graph.
In my point of view, Prof. Strang did want to show that the gradient is perpendicular to the level graph. However, he didn't notice that the arrow he drew is pointing upward. This is probably the point that confused you.
First of all, 2x + 5y = 0 is not a plane, as Professor Strang says. Rather, it is a level "curve" of the plane described by f(x,y) = 2x + 5y (with f(x,y) set to 0). The level "curves" of a plane in 3D are parallel lines on the xy plane. Then, Professor Strang really makes an error when he says that the gradient is somehow perpendicular to the plane. No, the gradient is perpendicular to the level "curves" of the plane, or the parallel lines in the xy plane. And, all movement to any new z value is in the plane. I also think the way he drew the plane was very confusing, as he didn't even try to approximate its actual orientation in 3D.
Wow the video quality is awesome
and lecture of Professor Gilbert Strang is the best
Your lectures are a pleasure to watch (and learn from)!
34:36 gradient descent
Omg look at how clean those top boards are 🤩
what a beautiful functions. that's why i love linear algebra.
why in 42:25 insn't the gradient [x,by] since there is 1/2 multiplied at f?
How did he get all the equations of xk, yk and fk at 45:35? Specifically, how did he get (b-1)/(b+1) and vice versa? I shifted the equation to make xk+1 and yk+1 the subjects of the equations but instead I got xk+1 = xk (1-2sk), where xk = x0 = b.
Same question here. Post the answer if you found it please.
I think he have already use the optimized step size (sk) for the iterration. He didn't tell us what is the sk looks like, while he just show us the finally equation to explain the idea of good or bad convergance.
at the limit [x,y]=[x,y]-[sx,bsy] and to minimize f=0.5x^2+0.5y^2, we must have |x|=|y|. So |x-sx|=|y-bsy| s=2/(1+b) and [x,y]=[x,y]-[sx,bsy]=[(1-s)x,(1-bs)y]. we got x=(b-1)/(b+1)*x_old, y=(1-b)/(b+1)*y_old etc...
Around 40:27. Does anybody know how to derive the result of reduction rate of m/M (the condition number)? Any tip or reference?
By condition number I guess he meant (what I got)
lambda(max) / lambda(min)
max eigen value / min e value
which was 1/b for that example
Absolutely well done and definitely keep it up!!! 👍👍👍👍👍👍
I think the grad(f) at 16:00 should be 0.5(S+S tranpose)x-a , right? anyway, thank you for the amazing lecture!
Thanks, Teacher !
For those who have not taken the previous 22 lecture , This lecture wont much help them.
I am hoping for a discussion about conventions of derivatives. Much of the stuff I've seen would make the gradient a row vector, which leads to the derivatives being the transpose of what he shows. In his example, the derivative a'x is 'a' which is contrary to intuition from single variable calculus though he uses intuition for x'Sx.
To get the intuition you should try make the multiplication of a'x, arrive at a new matrix, and then calculate the derivative for x. Will be a
same. I feel alot of people are using different notations for these vector/matrix derivatives. Nobody takes the time to elaborate the details :(
Wonderful teaching
Isnt grad(f) supposed to be [x by] instead of [2x 2by]?
Yes I had the same objection. I think he glossed over the 1/2 present in the function. It's a multiple of the same vector so in the grand scheme of things I don't think it matters too much but with that being said having [x by] would have eased my mind
In 26:51, the professor writes Gradient(f) = entries of X^-1. Do anyone know how to get that equation? Thanks!
if f(X) = -ln(det(X)), gradient(f) = (derivatives of det(X))/det(X) in matrix form, which is the same as a matrix of the entries of X^-1 for each entry. I'm also not too certain myself, but this does make sense to me.
en.wikipedia.org/wiki/Adjugate_matrix this gives the answer
💯👍
❤️❤️❤️❤️❤️
He is too long winded. Why not use a simple function of x,y. Find the derivatives and start dong a few iteration. Finally he gets to gradient descent. Gradient descent works but the are better algorithms. The line search idea is a good start. WTF is wrong with this guy? A simple python program or even excel would be much more meaningful. Thumbs down.
What the hell is a Hessian?
This sounds like a bunch of non sense.
Wonderful fella professor ☺️