Tivadar Danka Profile picture
Jun 22 27 tweets 8 min read Read on X
In machine learning, we take gradient descent for granted.

We rarely question why it works.

What's usually told is the mountain-climbing analogue: to find the valley, step towards the steepest descent.

But why does this work so well? Read on. Image
Our journey is leading through

• differentiation, as the rate of change,
• the basics of differential equations,
• and equilibrium states.

Buckle up! Deep dive into the beautiful world of dynamical systems incoming. (Full post link at the end.)
First, let's talk about derivatives and their mechanical interpretation!

Suppose that the position of an object at time t is given by the function x(t), and for simplicity, assume that it is moving along a straight line — as the distance-time plot illustrates below. Image
By definition, its derivative at a given time is given by the limit of difference quotients. Image
What do the difference quotients represent?

The average speed on a given interval!

(Recall that speed is the ratio of distance and time.) Image
The average speed has a simple geometric interpretation.

If you replace the object's motion with a constant velocity motion moving at the average speed, you'll end up at the same place.

The average speed is just the slope of the line connecting the start and endpoints.
By moving the endpoint closer and closer to the starting point, we obtain the speed at the exact time.

Thus, the derivative describes speed. Similarly, the second derivative describes acceleration.

How is this relevant for gradient descent? Enter dynamical systems. Image
As it turns out, the trajectory of a moving object can be described by its derivatives!

This is Newton's second law of motion. Image
Newton's second law describes mechanics in terms of ordinary differential equations, that is, equations involving derivatives whose solutions are functions.

For instance, this is the differential equation describing a swinging pendulum, as given by Newton's second law. Image
The simplest possible example: exponential growth.

If x(t) is the size of a bacterial colony, x′(t) = x(t) describes unlimited growth.

Think about x′(t) as the rate at which the population grows: without limitations in space and nutrients, cells can replicate whenever possible. Image
There are multiple solutions, each determined by the initial value x(0).

Here are some of them plotted below. Image
In general, differential equations are formulated as initial value problems, where we are given

1) a differential equation,
2) and an initial value. Image
For instance, with the choice f(x) = x (1 - x), we obtain the famous logistic equation.

This models the population growth under a resource constraint.

If we assume that 1 is the capacity of our population, growth becomes more difficult as the size approaches this limit. Image
Here comes the essential part: by studying the sign of f(x) = x (1 - x), we can describe the behavior of solutions! Why?

Because f(x(t)) determines x'(t), and the sign of the derivative x'(t) determines the monotonicity of the solution x(t). Image
This is visualized by the so-called phase portrait.

(The arrows on the x-axis indicate the direction of the solutions' flow.) Image
Here are some of the solutions, confirming what the phase portrait tells us. Image
There are two very special solutions: the constant functions x(t) = 0 and x(t) = 1.

These are called equilibrium points/solutions, and they are determined by the zeroes of f(x). Image
Why are these important?

Because the so-called stable equilibrium points attract the nearby solutions.

Again, check the stable equilibrium x₀ = 1 in the case of the logistic equation. Image
Let's talk about finding the solutions.

As differential equations are often not possible to solve explicitly, we resort to numerical methods.

The simplest one is replacing the derivative with finite differences to discretize the solution. Image
This means that if the step size h is small enough, the function f and the initial value x(0) can be used to approximate x(h). Image
Thus, by defining the recursive sequence below, we obtain a discretized solution.

This is called Euler's method. Image
The smaller the step size, the better the approximation.

Here are some of the discretized solutions for the logistic equation. Image
If the discretized solution looks familiar, it's not an accident.

If f is the derivative of some F, then this is gradient ascent, the algorithm that is used to maximize F.

In the case of the logistic equation, F takes the form of a simple third-degree polynomial. Image
We can easily obtain gradient descent: by maximizing -F, we minimize F.

Thus, gradient descent works because dynamical systems move towards stable equilibria.

(Of course, there are lots of nuances here, but this is the general idea.)
I have published an extensive 2500+ word post about this topic, so check it out for detailed explanations.

Read the full post here (and subscribe to get more posts like this one every week):

thepalindrome.org/p/why-does-gra…
This is also a part of my Mathematics of Machine Learning book.

Tons of intuitive explanations and hands-on examples, all with a focus on machine learning.

Get it here: amazon.com/Mathematics-Ma…
If you have enjoyed this thread, share it with your friends, follow me, and subscribe to my newsletter!

Understanding mathematics is a superpower. I'll help you get there, step by step.

thepalindrome.org

• • •

Missing some Tweet in this thread? You can try to force a refresh
 

Keep Current with Tivadar Danka

Tivadar Danka Profile picture

Stay in touch and get notified when new unrolls are available from this author!

Read all threads

This Thread may be Removed Anytime!

PDF

Twitter may remove this content at anytime! Save it as PDF for later use!

Try unrolling a thread yourself!

how to unroll video
  1. Follow @ThreadReaderApp to mention us!

  2. From a Twitter thread mention us with a keyword "unroll"
@threadreaderapp unroll

Practice here first or read more on our help page!

More from @TivadarDanka

Jul 1
The single most undervalued fact of linear algebra: matrices are graphs, and graphs are matrices.

Encoding matrices as graphs is a cheat code, making complex behavior simple to study.

Let me show you how! Image
If you looked at the example above, you probably figured out the rule.

Each row is a node, and each element represents a directed and weighted edge. Edges of zero elements are omitted.

The element in the 𝑖-th row and 𝑗-th column corresponds to an edge going from 𝑖 to 𝑗.
To unwrap the definition a bit, let's check the first row, which corresponds to the edges outgoing from the first node. Image
Read 18 tweets
Jun 30
In calculus, going from a single variable to millions of variables is hard.

Understanding the three main types of functions helps make sense of multivariable calculus.

Surprisingly, they share a deep connection. Let's see why! Image
In general, a function assigns elements of one set to another.

This is too abstract for most engineering applications. Let's zoom in a little! Image
As our measurements are often real numbers, we prefer functions that operate on real vectors or scalars.

There are three categories:

1. vector-scalar,
2. vector-vector,
3. and scalar-vector. Image
Read 16 tweets
Jun 30
Neural networks are stunningly powerful.

This is old news: deep learning is state-of-the-art in many fields, like computer vision and natural language processing. (But not everywhere.)

Why are neural networks so effective? I'll explain. Image
First, let's formulate the classical supervised learning task!

Suppose that we have a dataset D, where xₖ is a data point and yₖ is the ground truth. Image
The task is simply to find a function g(x) for which

• g(xₖ) is approximately yₖ,
• and g(x) is computationally feasible.

To achieve this, we fix a parametrized family of functions. For instance, linear regression uses this function family: Image
Read 19 tweets
Jun 28
One major reason why mathematics is considered difficult: proofs.

Reading and writing proofs are hard, but you cannot get away without them. The best way to learn is to do.

So, let's deconstruct the proof of the most famous mathematical result: the Pythagorean theorem. Image
Here it is in its full glory.

Theorem. (The Pythagorean theorem.) Let ABC be a right triangle, let a and b be the length of its two legs, and let c be the length of its hypotenuse.

Then a² + b² = c². Image
Now, the proof. Mathematical proofs often feel like pulling a rabbit out of a hat. I’ll go a bit overboard and start by pulling out two rabbits.

The first rabbit. Take a look at the following picture.

The depicted square’s side is a + b long, so its area is (a + b)². Image
Read 19 tweets
Jun 26
Problem-solving is at least 50% of every job in tech and science.

Mastering problem-solving will make your technical skill level shoot up like a hockey stick. Yet, we are rarely taught how to do so.

Here are my favorite techniques that'll loosen even the most complex knots: Image
0. Is the problem solved yet?

The simplest way to solve a problem is to look for the solution elsewhere. This is not cheating; this is pragmatism. (Except if it is a practice problem. Then, it is cheating.)
When your objective is to move fast, this should be the first thing you attempt.

This is the reason why Stack Overflow (and its likes) are the best friends of every programmer.
Read 18 tweets
Jun 25
What you see below is one of the most beautiful formulas in mathematics.

A single equation, establishing a relation between 𝑒, π, the imaginary number, and 1. It is mind-blowing.

This is what's behind the sorcery: Image
First, let's go back to square one: differentiation.

The derivative of a function at a given point describes the slope of its tangent plane. Image
By definition, the derivative is the limit of difference quotients: slopes of line segments that get closer and closer to the tangent.

These quantities are called "difference quotients". Image
Read 20 tweets

Did Thread Reader help you today?

Support us! We are indie developers!


This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3/month or $30/year) and get exclusive features!

Become Premium

Don't want to be a Premium member but still want to support us?

Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal

Or Donate anonymously using crypto!

Ethereum

0xfe58350B80634f60Fa6Dc149a72b4DFbc17D341E copy

Bitcoin

3ATGMxNzCUFzxpMCHL5sWSt4DVtS8UqXpi copy

Thank you for your support!

Follow Us!

:(