Tivadar Danka Profile picture
Aug 9 14 tweets 5 min read Read on X
Graph theory will seriously enhance your engineering skills.

Here's why you must be familiar with graphs: Image
What do the internet, your brain, the entire list of people you’ve ever met, and the city you live in have in common?

These are all radically different concepts, but they share a common trait.

They are all networks that establish relationships between objects. Image
As distinct as these things seem to be, they share common properties.

For example, the meaning of “distance” is different for

• Social networks
• Physical networks
• Information networks

But in all cases, there is a sense in which some objects are “close” or “far”. Image
What if we could study this abstract notion of networks of interconnected elements and understand the fundamental properties of all sorts of networks all at once?

This is the purpose of graph theory, and we’re here to open a window for you to dive into this universe.
Intuitively, a graph is just a (finite) collection of elements — vertices, or sometimes nodes — connected by edges.

Thus, a graph represents an abstract relation space, in which the edges define who’s related to whom, whatever the nature of that relation is. Image
There is nothing intrinsic to names or the exact locations of the vertices in the drawing.

The layout of a graph is arbitrary, and thus, the same graph can be represented in an infinite number of ways. Image
In the study of networks, indirect connections are as important as direct ones.

Speaking in the language of graphs, indirect connections are formalized by walks. A walk is simply a finite sequence of connected nodes.

For example, (a, b, a, e, c, d) is a walk on the graph below. Image
If we never repeat an edge, then we have a trail.

The previous walk is not a trail because we backtrack through ab.

In contrast, (a, e, c, d, e) is a valid trail in our example graph, because although e appears twice, we get to it via different edges each time. Image
If we never repeat a vertex, then we have a path.

For instance, (c, d, e, a, b) is a path that happens to involve all vertices.

However, if the path loops over from the final vertex back into the first one, so the start and end are the same vertex, we call it a cycle. Image
So, vertices and edges are the building blocks of graphs, giving rise to walks, trails, and paths.

With these notions, we can start to ask general questions about the structure of a graph.

One question is connectivity, that is, which vertices are reachable from each other. Image
An interesting question regarding connectivity is how critical a vertex or edge is regarding connectivity.

If removing a single vertex (or edge) from a graph splits a connected component into two or more, then that vertex is called a cut vertex (or cut edge). Image
In the previous graph, the removal of vertex a (and its corresponding edges) produces five connected components, while the removal of vertex b produces two. Image
The removal of the edge ab produces two connected components. Image
Join 20,000+ ML practitioners who get 2 actionable emails every week to help them understand the math behind ML, make smarter decisions, and avoid costly mistakes.

Subscribe here (it’s free): 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

Aug 9
Differentiation reveals much more than the slope of the tangent plane.

We like to think about it that way, but from a different angle, differentiation is the same as an approximation with a linear function. This allows us to generalize the concept.

Let's see why: Image
By definition, the derivative of a function at the point 𝑎 is defined by the limit of the difference quotient, representing the rate of change. Image
In geometric terms, the differential quotient represents the slope of the line between two points of the function's graph. Image
Read 12 tweets
Aug 8
I have spent at least 50% of my life studying, practicing, and teaching mathematics.

The most common misconceptions I encounter:

• Mathematics is useless
• You must be good with numbers
• You must be talented to do math

These are all wrong. Here's what math is really about: Image
Let's start with a story.

There’s a reason why the best ideas come during showers or walks. They allow the mind to wander freely, unchained from the restraints of focus.

One particular example is graph theory, born from the regular daily walks of the legendary Leonhard Euler.
Here is the map of Königsberg (now known as Kaliningrad, Russia), where these famous walks took place.

This part of the city is interrupted by several rivers and bridges.

(I cheated a little and drew the bridges that were there in Euler's time, but not now). Image
Read 15 tweets
Aug 8
Conditional probability is the single most important concept in statistics.

Why? Because without accounting for prior information, predictive models are useless.

Here is what conditional probability is, and why it is essential: Image
Conditional probability allows us to update our models by incorporating new observations.

By definition, P(B | A) describes the probability of an event B, given that A has occurred. Image
Here is an example. Suppose that among 100 emails, 30 are spam.

Based only on this information, if we inspect a random email, our best guess is a 30% chance of it being spam.

This is not good enough. Image
Read 10 tweets
Aug 7
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 18 tweets
Aug 6
Logistic regression is one of the simplest models in machine learning, and one of the most revealing.

It shows us how to move from geometric intuition to probabilistic reasoning. Mastering it sets the foundation for everything else.

Let’s dissect it step by step! Image
Let’s start with the most basic setup possible: one feature, two classes.

You’re predicting if a student passes or fails based on hours studied.

Your input x is a number, and your output y is either 0 or 1.

Let's build a predictive model! Image
We need a model that outputs values between 0 and 1.

Enter the sigmoid function: σ(ax + b).

If σ(ax + b) > 0.5, we predict pass (1).

Otherwise, fail (0).

It’s a clean way to represent uncertainty with math. Image
Read 15 tweets
Aug 6
The way you think about the exponential function is (probably) wrong.

Don't think so? I'll convince you. Did you realize that multiplying e by itself π times doesn't make sense?

Here is what's really behind the most important function of all time: Image
First things first: terminologies.

The expression aᵇ is read "a raised to the power of b."

(Or a to the b in short.) Image
The number a is called the base, and b is called the exponent.

Let's start with the basics: positive integer exponents. By definition, aⁿ is the repeated multiplication of a by itself n times.

Sounds simple enough. Image
Read 18 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!

:(