Entropy: An Introduction

https://homes.cs.washington.edu/~ewein/blog/2020/07/14/entropy/

by aishwarya_m • 6 years ago

155 32 6 years ago

homes.cs.washington.edu

Analog243• 6 years ago

Might be worth clarifying in the title that this is about entropy in the context of information theory.

jbay8083• 6 years ago

In which context is it a different concept?

hexxiiiz2• 6 years ago

In thermodynamics there are two other formulations of entropy: the Clausius one in terms of temperature and heat, and the Boltzmann one. The latter defines entropy as the log of the number of microstates a system could be in a particular macrostate.

The Shannon definition is equivalent to the Boltzmann def only in the case that the micro state consists of infinitely many identical subsystems. If there are only finitely many, for instance, the log of the quantity does not correspond to the same "-p log p".

The Clausius def can be derived from the Boltzmann one, but they are nevertheless also distinct formulations.

Analog243• 6 years ago

"Entropy" has been a concept in physics for a long time. Far longer than the concept of information entropy.

cmehdy• 6 years ago

I imagine the timing of this post is correlated with release of the documentary Bit Player about Claude Shannon. Haven't seen it yet but looking forward to it.

The article does a decent job at graphing and laying out some of the concepts of entropy for information theory, but I'm not sure who the target reader is, since prereqs are perhaps only slightly narrower than what one needs to read Shannon's paper[0] and the article is really illustrating only a fraction of the concept.

It can perhaps work as a primer for what shows up starting on pages 10-11 of the original document, in any case, provided you grasp the mathematical definition of entropy through thermodynamics, and the microstates-based definition through Boltzman, as well as "basic probabilities" (expected value, typical discrete distributions, terms like "i.i.d"), you should be good to go. But then you might already know all this..

And if you do, and you like what you read, then the full original thing by Shannon is a delight to explore to truly grasp what has been so foundational to a lot of things since 1948.

[0] http://people.math.harvard.edu/~ctm/home/text/others/shannon...

ethanweinberger4• 6 years ago

Hi HN, I'm the author of this piece (Ethan Weinberger). I wrote this originally as a set of notes for myself when brushing up on concepts in information theory the past couple of weeks. I found the presentations I was reading of the material to be a little dry for my taste, so I tried to incorporate more visuals and really emphasize the intuition behind the concepts. Glad to see others are finding it useful/interesting! :)

sohamsankaran• 6 years ago

Ethan also writes about machine learning at https://honestyisbest.com/kernels-of-truth each week -- his most recent piece there (https://honestyisbest.com/kernels-of-truth/2020/Jul/14/facia...) has a neat explanation of how convolutional neural networks (CNNs) work.

spinningslate2• 6 years ago

Thanks, I enjoyed reading. As an electronic engineering student, I remember grappling with information theory in the abstract: it was a weather example very similar to yours that gave me the intuition I was missing.

An observation/suggestion. The intro is accessible to many people; that drops off a steep cliff when you hit the maths. Now, I'm not complaining about that: it's instructive and necessary to formalise things. Where I struggle is in reading the equations in my head when I don't know what words to use for the symbols. For example, that very first `X ~ p(x)`. I didn't know what to say for the tilde character, so couldn't verbalise the statement. I do know that $\in$ (the rounded 'E') means 'is a member of' so I could read the next statement. The problem gets even more confusing for a non-mathematician as the same symbol is used with different meaning in different branches of maths/science (e.g. $\Pi$).

I get that writing out every equation in English isn't feasible (or, at least, is asking a lot of the writer). But I wonder if there's middle way, e.g. through hyperlinking?

As I say: not a criticism and I don't have a good solution. Just an observation from a non-mathematician. Enjoyed the piece anyway.

jessriedel2• 6 years ago

"X ~ p(x)" means "X is a random variable drawn from the probability distribution p(x)" or maybe "X is drawn from p(x)" for short.

Are you sure it's a matter of knowing what to say (in your head) vs knowing the definition of the notation in the first place? I am pretty familiar with this notation, but I rarely verbalize it mentally. I can tell because I read and understand it quickly without problem, but on the rare occasion when I have to read it aloud I realize I'm not sure how I should pronounce it.

canjobear2• 6 years ago

I read X ~ p(x) as "X is distributed as p of x"

windsignaling• 6 years ago

I don't think a piece on information theory should necessarily be "accessible to many people". It's a topic which is normally taught in grad school.

Something like X ~ p(x) would be seen all over the place in probability, stats, ML, and related courses such as info theory, detection and estimation, etc. Likely by the time someone is interested in info theory this notation would be permanently etched into their minds. So for this article it is very "audience appropriate".

not a criticism and I don't have a good solution

Having a mental map of how different subjects fit together (without actually having to studying them in-depth) is a good start.

I've seen so many people crash and burn with machine learning because they were unaware that it depends on linear algebra, calculus, and probability.

With a mental map there is less "surprise" and it's more a matter of simply understanding that they didn't have the right dependencies.

wcookeverton• 6 years ago

Awesome paper Ethan!!!

onurcel• 6 years ago

Thank you for the great article. I believe there is a typo in "we assign a value of 0 to p(x) log p(x) when x=0", it should be "when p(x) = 0".

ethanweinberger4• 6 years ago

Thanks for the catch. Fixed!

canjobear2• 6 years ago

You might want to give more conditions for the claim that the self-information gives the length of the shortest possible code.

In particular the condition isn't only that it's the shortest code, it's the shortest self-delimiting code. In your example with probabilities {1/2, 1/4, 1/8, 1/8}, someone could come in and say let's code it as {0,1,01,00}, which would appear to encode the latter two outcomes 2 bits rather than 3. The problem, of course, is that {0,1,01,00} is not a self-delimiting code: after you receive the bit 0, you don't know if you're done or if you should wait for another bit to form 01. But the code {0,10,110,111} is self-delimiting, because after you get a 0 or a 10, etc., you know you're done.

I've found that when I teach this material, if I don't mention the self-delimiting condition, then a clever student in the class always thinks of the {0,1,01,00}-type code. (This can be a good way to identify clever students in an intro information theory class!)

abetusk• 6 years ago

Not sure if it's appropriate but here's my own take at a very terse restatement of Shannon's original paper [1]:

    https://mechaelephant.com/dev/Shannon-Entropy/

I recommend everyone that's interested to read Shannon's original paper. It's one of the few examples of an original paper that's both clear and readable.

[1] https://homes.cs.washington.edu/~ewein/blog/2020/07/14/entro...

danielrk• 6 years ago

Love the post. Just FYI, your post is not mobile-friendly. When scrolling down on iPhone it’s impossible not to accidentally shift the viewport away from the left margin making the left side hard to read

wsowens• 6 years ago

For the example of H(X) where X ~ Geom(p), shouldn't the second term be multiplied by (k-1) after breaking up the logarithm? That is, shouldn't

  pq^(k-1)log(q)

  (k-1)pq^(k-1)log(q)

Apologies if I'm off base here, I'm pretty rusty on infinite series.

Great piece, this is really making this concept more intuitive for me.

ethanweinberger4• 6 years ago

You're 100% right. Fixed!

narayan_s• 6 years ago

Possibly unrelated, but I love the simple an clean layout of the website. Does anyone know how to create something similar to this?

ethanweinberger4• 6 years ago

I (shamelessly) stole the layout from Gregory Gundersen's wonderful research blog (https://gregorygundersen.com/blog/). He has instructions on how to replicate it here https://gregorygundersen.com/blog/2020/06/21/blog-theme/

mercer• 6 years ago

If you do, please make it 'zoomable' (and as a result mobile-friendly). I tend to prefer reading larger size and fewer words per line, but zooming in just kept everything the same, except bigger.

Not that it wasn't a great article though :).

yters• 6 years ago

Neat fact: entropy and expected algorithmic information are asymptotically equivalent. Two quite different approaches to information theory converge.

Entropy: An Introduction

Related Stories