Jump to content

User:JeffAEdmonds/Sandbox

From Wikipedia, the free encyclopedia

I am hoping that this page will give some extra understanding of Gradient Descent. As such, it is talking about the same topic. Hence the critique "The first is whether this is a duplicate of the topic at Gradient descent." I do prefer explanations to a list of facts. Given that, I would love to better understand the critique "The second is that it appeared to be written more like a textbook than an encyclopedia article. I could use this textbook approach but it's not necessarily our "house style"."

---


Gradient descent is based on the observation that multi-variable function decreases fastest from a point by heading in the direction of the negative of the gradient Though this is true, it is neither obvious what it means nor why it is true.

Illustration of gradient descent on a series of level sets
Contour Lines
File:Steepest ascent 6.JPG
Partials
File:Steepest ascent 7.JPG
Perpendicular


Suppose you are standing on some hilly terrain. Denote your east/north coordinate as and your height as Traveling a path across the hill is not as steep as going straight down because for the same horizontal distance traveled, you do not go down as far vertically. The direction of steepest decent is the direction that water flows and the scariest direction if you are skiing. Your location on a contour map is on the contour curve of points whose height is exactly the same as your own location and the next contour curve is that whose height is one unit less. If instead, you are on a curve staircase such that each step has height one, then the contour lines are the edges of the stairs. The goal of steepest decent is choose the direction that crosses as many of these contour curves while traveling a fixed horizontal distance or conversely is to reach the first of these contour curves while travel a minimum horizontal distance. It is reasonable that this direction is that perpendicular to the contour line.

Now suppose you are in a deep fog with a compass, a ruler, and an altimeter. You measure that moving one unit east increases your height by 4, i.e. and that moving one unit north increases your height by 7, i.e. . From this, we can determine that the direction of steepest accent is given by the vector This means that your height decreases fastest by moving to from your current location to for some small value . We will prove this in three ways.

Proof 1: Perpendicular to the contour lines

[edit]

We have argued that the direction of steepest accent/descent is that perpendicular to the contour curve. Let us calculate this. Knowing and give us that the plain approximating the terrain is defined by the equation . The contour line that you are standing on has the equation . Another point on this contour line is . Hence, direction of the line is the vector . Drawing a picture of triangles can convince you that the vector perpendicular to the vector is . This gives our result.

If depends on your location within an -dimensional space, then the contour "curve" will be an -dimensional sub-space. The direction of steepest ascent is the vector that is perpendicular to this. This can be formalized more as follows. Consider 's linear approximation . The equation of the contour plane, shifted to go through the origin is . I claim that the vector is perpendicular to this plain because the dot product between it and any vector in the contour plane is which by the definition of the conture plane is always zero.

Proof 2: Calculous

[edit]

Lets again assume terrain is the plain . Lets move in the direction from . This increases our height from by from to . The distance traveled horizontally . Hence, the slope traversed is

Steepest ascent chooses the direction in order to maximize this slope.

Again giving us the result.

Proof 3: Lagrange

[edit]

Suppose we wish to maximize subject to the constraint . The feasible set is the unit circle, and the level sets of f are diagonal lines (with slope −1), so we can see graphically that the maximum occurs at , and that the minimum occurs at .

For the method of Lagrange multipliers, the constraint is

hence

Now we can calculate the gradient:

and therefore:

Notice that the last equation is the original constraint.

The first two equations yield

By substituting into the last equation we have:

so

which implies that the stationary points of are

Evaluating the objective function f at these points yields

Thus the constrained maximum is and the constrained minimum is .