Tivadar Danka Profile picture
Dec 27, 2021 15 tweets 4 min read Read on X
Entropy is not the easiest thing to understand.

It is rumored to describe something about information and disorder, but it is unclear why.

What do logarithms and sums have to do with the concept of information?

Let me explain!

↓ A thread. ↓ Image
I have randomly selected an integer between 0 and 31.

Can you guess which one? You can ask as many questions as you want.

What is the minimum number of questions you have to ask to be 100% sure?

You can start guessing the numbers one by one, sure. But there is a better way!
If you ask, "is the number larger or equal than 16?" you immediately eliminate half the search space!

Continuing with this tactic, you can find the number for sure in 5 questions.
In other words, we need to take the base two logarithm of 32 to get the number of questions required.

This logic applies to all numbers! If I pick a number between 0 and 𝑛-1, you need 𝑙𝑜𝑔(2, 𝑛) questions to find it for sure, by cutting the possibilities in half with each.
Because the answers are yes-or-no questions, we can encode each with a 0 or 1.

If we write down the answers in a row, we effectively encode the numbers in 𝑛 bits!

𝟎: 00000
𝟏: 00001
𝟐: 00010
...
𝟑𝟏: 11111

Each "code" is simply the number in base 2!
No matter which number I pick, five questions are needed to find it.

So, the average number of bits needed is also five.

However, we use a critical assumption here: I pick each number with an equal probability.

What if that is not the case?
Let's say I am picking between 0, 1, and 2, but I am picking 0 at 50% of the time, while 1 and 2 only 25% of the time.

We should put this into mathematical form!

Let's denote the number I pick with 𝑋. This is a random variable.

How many bits do we need now? Image
We can be more bit-efficient than before! Consider this.

1st question: did you pick 0?
If the answer is yes, the 2nd question is not needed. If not, we proceed!

2nd question: did you pick 1?
No matter what the answer is, we know the solution! Yes implies 1, no implies 2.
Following this idea, we can calculate the average number of bits as below. Image
(This is just the expected value of the number of bits.

If you didn't understand this step, check out my explanation about the expected value!)

)
Now we are almost there! Let's see the general case.

Suppose I pick between 𝑥₁, 𝑥₂, ..., 𝑥ₙ, and I pick 𝑥ₖ with probability 𝑝ₖ.

As before, the number of questions needed to find 𝑘 is the base two logarithm of 1/𝑝ₖ! Image
So, the entropy of a random variable is simply the average bits of information needed to guess its value successfully! Even though the formula is complicated, its meaning is simple.

Entropy is simpler than you thought! (And probably also simpler than what you were taught.) Image
Having a deep understanding of math will make you a better engineer. I want to help you with this, so I am writing a comprehensive book about the subject.

If you are interested in the details and beauties of mathematics, check out the early access!

tivadardanka.com/book
A few extra comments!

1. What happens if the logarithm of the probability is not an integer?

Not all questions provide 100% new information. Sometimes, the answer is partially contained in other bits.

Hence, the "amount of new information" is not always an integer.
2. Does the base of the logarithm matter?

In general, we can easily swap the base of the logarithms, as shown below.

Thus, swapping bases in the entropy formula is just multiplication with a constant. Image

• • •

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 7
In machine learning, we use the dot product every day.

However, its definition is far from revealing. For instance, what does it have to do with similarity?

There is a beautiful geometric explanation behind. Image
By definition, the dot product (or inner product) of two vectors is defined by the sum of coordinate products. Image
To peek behind the curtain, there are three key properties that we have to understand.

First, the dot product is linear in both variables.

This property is called bilinearity. Image
Read 15 tweets
Jul 5
If I had to learn Math for Machine Learning from scratch, this is the roadmap I would follow: Image
1. Linear Algebra

These are non-negotiables:

• Vectors
• Matrices
• Equations
• Factorizations
• Matrices and graphs
• Linear transformations
• Eigenvalues and eigenvectors

Now you've learned how to represent and transform data. Image
2. Calculus

Don't skip any of these:

• Series
• Functions
• Sequences
• Integration
• Optimization
• Differentiation
• Limits and continuity

Now you understand the math behind algorithms like gradient descent and get a better feeling of what optimization is. Image
Read 6 tweets
Jul 3
Behold one of the mightiest tools in mathematics: the camel principle.

I am dead serious. Deep down, this tiny rule is the cog in many methods. Ones that you use every day.

Here is what it is, how it works, and why it is essential. Image
First, the story.

The old Arab passes away, leaving half of his fortune to his eldest son, third to his middle son, and ninth to his smallest.

Upon opening the stable, they realize that the old man had 17 camels. Image
This is a problem, as they cannot split 17 camels into 1/2, 1/3, and 1/9 without cutting some in half.

So, they turn to the wise neighbor for advice. Image
Read 18 tweets
Jul 3
The single biggest argument about statistics: is probability frequentist or Bayesian?

It's neither, and I'll explain why.

Buckle up. Deep-dive explanation incoming. Image
First, let's look at what is probability.

Probability quantitatively measures the likelihood of events, like rolling six with a dice. It's a number between zero and one.

This is independent of interpretation; it’s a rule set in stone. Image
In the language of probability theory, the events are formalized by sets within an event space.

The event space is also a set, usually denoted by Ω.) Image
Read 33 tweets
Jul 2
Matrix multiplication is not easy to understand.

Even looking at the definition used to make me sweat, let alone trying to comprehend the pattern. Yet, there is a stunningly simple explanation behind it.

Let's pull back the curtain! Image
First, the raw definition.

This is how the product of A and B is given. Not the easiest (or most pleasant) to look at.

We are going to unwrap this. Image
Here is a quick visualization before the technical details.

The element in the i-th row and j-th column of AB is the dot product of A's i-th row and B's j-th column. Image
Read 16 tweets
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

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!

:(