Entropy, and Short Codes

erratum: So -(1/8 * 3) = 0.375 is the contribution

Roland, I remember an erratum where I had that quantity equal to 0.475 instead of 0.375, but I also remember fixing it, and the web text seems to agree - are you perchance seeing 0.475 in an RSS feed?

Firstly, saying "you can define a word any way you want" is not the same thing as "any way which is meaningful to you". Secondly, I don't believe the development on entropy has anything to do with the convenience of using short words for often used concepts. "chair" is a meaningful piece of jointed reality not because of its intrinsic physical properties but because of its handiness for humans. A dolphin would find "chair" as a significant piece of jointed reality absurd. Thirdly, there is an obvious distinction bewteen using language descriptively and using it predictively. I would agree with you that mistakes often arise when moving from the descriptive to the predictive incautiously. That doesn't, however, make the descriptive use of language invalid, or even unwise, 98% of the use of language is descriptive. (I have proof of that statistic, but it won't fit in this margin).

"antidisestablishmentarianism way around" should be "antidisestablishmentarianism other way around".

Fixed.

It's called entropy because somebody told Shannon that the same mathematical quantity already existed in thermodynamics, when the question what to call it came up.

I don't know that there's any other operational connection.

Like there's no entropy gradient giving the arrow of time, or system-wide increase.

Okay, now let's code those factory objects! 1 bit for blue not red 1 bit for egg not cube 1 bit for furred not smooth 1 bit for flexible not hard 1 bit for opaque not translucent 1 bit for glows not dark 1 bit for vanadium not palladium

Nearly all objects we encounter code either 1111111 or 0000000. So we compress all objects into two categories and define: 1 bit for blegg (1111111) not rube (0000000). But, alas, the compression is not lossless, because there are objects which are neither perfect bleggs nor rubes: A 1111110 object will be innocently accused of containing vanadium, because it is guilty by association with the bleggs, subjected to unfair kin liability! Still, in an enviroment where our survival depends on how faithfully we can predict unobserved features of those objects we stand good chances:

Nature: "I have here an x1x1x1x object, what is at it's core?" We suspect a blegg and guess Vanadium - and with 98% probability we are right, and nature awards us a pizza and beer.

Now the evil supervillain, I-can-define-any-way-I-like-man (Icdawil-man, for short), comes by and says: "I will define my categories thus: 1 bit for regg (0101010) not blube (1010101)" While he will achieve the same compression ratio, he looses about 1/2 of the information in the process. He has failed to carve at the joint. So much the worse for Icdawil-man.

Nature: "I have here an x1x1x1x object, what is at it's core?" Icdawil-man suspects a regg, guesses Palladium, and with 98% probability starts coughing blood...

Next along comes the virtuous and humble I-refuse-to-compress-man:

Nature: "I have here an x1x1x1x object, what is at it's core?" Irtc-man refuses to speculate and is awarded a speck in his eye.

Next along comes the brainy I-have-all-probabilities-stored-here-because-I-can-man:

Nature: "I have here an x1x1x1x object, what is at it's core?" Ihapshbic-man also gets a pizza and beer, but will sooner be hungry again than we will. That's because of all the energy he needs for his humongous brain which comes in an extra handcart.

Any more contenders? =)

There is different-base-concepts-alien who views the world with radar, x rays and sonar

Dbc-alien says "I don't understand half of your coding (colour, translucency, glowingness) and the other things are high level concepts I don't tend to bother with. It is like trying to ask me to identify a cat by density, I can always tell between what has vanadium and palladium via the way they refract x rays".

There is also not-important-for-me ant who gives not a fig whether something is a blegg or a rube.

Nifm ant goes to eats remnants of the pizza and beer given to ihapshbic and us, and out can survive because it hasn't even bothered to try and build a big brain to remember anything.

Make attention to use the entropy . The entopy is based on the idea that the amount of information in binary string S is Log(S) , the number of bit to directly code the string . This is wrong , the correct information is the Kolmogorov complexity of S . Nowaday the scientific literature don't focus on this difference and very often use Log(S) instead of K(S) ( K is the Kolmogorov complexity function ) and justify this becouse K(X) is uncomputable and becouse for the major part of K(X) value it is approximable by Log(X) in a mathematical context . This wrong assumption is done becouse people think that every object , every binary string can happen . This is wrong , only few bit string with lenght 1000000 can happen becouse a system that produce 2^1000000 object , string can not exist. What this mean is that the object are always small ! The object stay in that value smaller than Log(X) in the function K(X) .

"This wrong assumption is done becouse people think that every object , every binary string can happen . This is wrong , only few bit string with lenght 1000000 can happen becouse a system that produce 2^1000000 object , string can not exist."

So these people are frauds?

erratum: So -(1/8 * 3) = 0.375 is the contribution

Eliezer, the problem is with the sign. You wrote: -(a) = a

Durr... fixed.

"Prosody too, for that matter - Tolkien once observed what a beautiful sound the phrase "cellar door" makes; that is the kind of awareness it takes to use language like Tolkien."

Out of curiosity, did you ever study Tolkien's languages.

"So these people are frauds?"

To answer your question , I think the card can be one of the better random generator existing, so it is absolutely not a frauds ( and pheraps I will buy one ... thank you for the link ) . But there are many definition of random . The only one theoretical random definition I accept as true is that a bit string S is random only if this string has K(S) >=Len(S) . My strong deterministic opinion is that in the real world these random objects exist only if we take short object , also for quantum field ( like Wolfram think ). I read articles where people reasoning on the quantum field and the relation on exponential or polynomial world , I don't know what is the answer but I don't think that quantum filed open the door for an exponential world. This opinion come to me from many discrepance I find in the mathematical description and what happen in practical . For example for the K function ( Kolmogorov complexity ) there are proof say that for major part of value we have K(X)>=Log(X) and if you watch on the function you can say it is absolutely correct , not only but for very very few case we have K(X)<Log(X) and also from a statistical point of view all is coherent. The probability to compress X using the optimal K function with a dimension of N bits into a Y with a dimension of N/2 bits is (2^(N/2))/(2^N) . This probability is exponential low! So for increasing value X the probability to have a small K(X) is very low. What this mean for practical point of view? This mean that if I take a file from my pc and then I try to compress this file using a very very bad compressor ( becouse the K function is an idealized compressor with an infinite power ) it is crazy to hope to compress it . But I absolutely sure that I am able to compress it and with high probability of 50% ! . Why? What happen ? There are many explanation we can give to this phenomena but the follow is my opinion. When we get an object , when we receive an input this object is only a representation of the information of the object computed by a program , every program has limited power , we can define this power as a limit on the size of the bitstring that this program can do . I call this limit M and using this limit something change , for examples the number of available bit string of lenght N in a mathematical view are 2^N , now become min( 2^N , M/N ) . The compression probability change ... The universal distribution change ... But the interesting property of this vision is that it make pactical aspecative coherent with theretical function . In the standard mathematical/statistical view is more easy to compress small string and become more difficult to compress large string in absolutely opposition in what happen in the real world! When I have a small file I think will be difficult to compress it and when I have a big file I think that I will get a big compression ratio.

If you watch this function min( 2^N , M/N ) what happen is this! for small string we have exponential behaviour and this is coherent with mathematical classical view but after a limit M what happen change and the probability to compress for example increase! .

Another important characteristic is that big variation on the parameter M make small variation on the behaviour of the function , so is more important to assume the existence of this behaviour also if we don't know M also if it is impossible to compute M !.

This cause a discrepance in the entropy , in the assumption of Log as function of information measurement , etc ... becouse this theories suppose an exponential world ! a very big world! ( exponential functions are very big and we can not underrate them ! )

There are many consequence of this simple observation and many to be investigate .

I don't know if quantum field will open the exponential door but the world behaviour seem to me polynomial.

Denis.

Frank, how about the way it actually happened; guy #5 bashes you over the head with a rube, and steals your beer, your pizza and your woman?

Suppose you have a system X that's equally likely to be in any of 8 possible states [...] on average, we'll have to ask 3 yes-or-no questions to find out X's value.

Eliezer: is there a formal connection between entropy and binary search? A binary search of that system would also terminate in three operations, right?

Very interesting article! It seemed very surprising to me that the information entropy can be interpreted as the (minimum average) number of yes/no-questions needed to fully determine the state of a system. Especially since the value of the entropy depends on the units (i.e. what logarithm base you use). Is the use of base two related to the fact that the answers can be either 'yes' or 'no' (binary)?

Another question. Suppose you have a system X in 4 possible states {X1,X2,X3,X4} with probabilities {3/8,2/8,2/8,1/8} respectively. The information entropy is about 1.91 bits. But I couldnt find any series of yes/no questions to ask that would give me 1.91 questions on average. An average of 2 questions is the best I could do. That is the same as the situation with probabilities {1/4,1/4,1/4,1/4} even though we have more information than that in our present case. Am I not looking hard enough?

I`m really trying to get a grasp on the concept of information entropy so I hope someone can answer my questions.

Great blog in any case. I`m glad I found it!

Is there a short, pronounceable word for the underscore symbol?

I'm confused. What makes "chair" the basic category? I mean, obviously more basic categories will have shorter words -- but who decided that "solid object taking up roughly a cubic meter designed to support the weight of a single sitting human" was a basic category?

The encoding scheme you're talking about is Huffman Coding, and the ambiguity you're trying to avoid explicitly occurs when one symbol is the prefix of another. The mechanism to build an optimal prefix(-free) code is called the Huffman Tree, and it uses a greedy algorithm that builds a full binary tree from the bottom up based on the frequencies of the symbols. Leaves are symbols, and the code for a symbol is the sequence of left or right branches you must traverse the reach that symbol.

To get more specific, you add all the symbols to a heap based on their frequency of appearance, lowest-at-the-front. You extract two symbols, foo and bar. These become children of a common parent node, the pseudosymbol baz. baz.freq = foo.freq + bar.freq. Add baz to the heap. Loop until the heap contains one node at the end of this process. That node is the root of the Huffman Tree.