I am going to tell you the best-kept secret of linear algebra: matrices are graphs and graphs are matrices.
Encoding matrices as graphs is a cheat code, making complex behavior extremely simple to study.
Let me show you how!
🧵 👇🏽
If you looked at the example above, you probably figured out the rule.
Each row is a node, and each element of a row represents a directed edge.
The element in the 𝑖-th row, 𝑗-th column corresponds to the edge in the graph, going from 𝑖 to 𝑗.
(Formal definition below.)
Why is the directed graph representation beneficial for us?
The first example is that the powers of the matrix correspond to walks in the graph.
Take a look at how to calculate the elements of the square of a matrix.
If the directed graph represents the states of a Markov chain, the square of its transition probability matrix essentially shows the probability of the chain having some state after two steps.
There are more significant implications of this connection.
For instance, it gives us a deep result about the structure of nonnegative matrices.
According to the Frobenius theorem, every nonnegative matrix 𝐴 can be written in a very special form.
(Multiplying with a matrix 𝑃 and its transpose from left and right is called similarity transformation. This just means that we view the linear transformation 𝐴 in a different coordinate system.
Check this explanation, if you would like to see more!
This result is really hard to prove purely with algebra.
With graphs, it is much easier. You only have to prove that every directed graph can be partitioned into disjoint subsets where every two node of a given subset can be mutually reachable from each other.
I'll leave the details up to you, but here is an illustration to help.
This is a simple visual idea, opposed to the complex algebraic original proof.
To conclude, representations play an essential role in mathematics.
Often, solving a problem is not about finding a brilliant idea, but the right way to look at the objects.
Matrices as graphs is one of the prime examples for that.
• • •
Missing some Tweet in this thread? You can try to
force a refresh
You ask me so often for free online resources about deep learning that I decided to collect my favorite courses!
These topics interest you the most:
🟩 practical deep learning,
🟩 deep learning theory,
🟩 math resources to understand the two above.
Let's see them!
🧵 👇🏽
1️⃣ Practical deep learning.
If you want to take a deep dive straight into the field and want to start training your models right away, hands down the best course for you out there is Practical Deep Learning for Coders by fast.ai. (course.fast.ai)
To move beyond training models and learn about tooling and infrastructure, IMO the best course for you is the Full Stack Deep Learning course by @full_stack_dl.
Have you ever thought about why neural networks are so powerful?
Why is it that no matter the task, you can find an architecture that knocks the problem out of the park?
One answer is that they can approximate any function with arbitrary precision!
Let's see how!
🧵 👇🏽
From a mathematical viewpoint, machine learning is function approximation.
If you are given data points 𝑥 with observations 𝑦, learning essentially means finding a function 𝑓 such that 𝑓(𝑥) approximates the given 𝑦-s as accurately as possible.
Approximation is a very natural idea in mathematics.
Let's see a simple example!
You probably know the exponential function well. Do you also know how to calculate it?
The definition itself doesn't really help you. Calculating the powers where 𝑥 is not an integer is tough.