liveBook · Manning

Entropy

As explained in Timeless Algorithms, The Foundational Ideas

Entropy is a quantitative measure of uncertainty across the possible outcomes of an information source and their probabilities.

Before a coin lands, uncertainty remains about its outcome. Entropy measures that uncertainty across all possible outcomes and their probabilities, before any particular outcome is observed. It is an average for the source, not the information conveyed by one observed outcome. section 5.1.2 section 5.1.3

H(X)=-∑p(x)log2p(x)

For a source X, p(x) is the probability of outcome x, and the sum runs over its possible outcomes. The base-2 logarithm expresses entropy H(X) in bits. Each term weights an outcome’s information by its probability. section 5.1.2 section 5.1.3

Fair and biased coins

A fair coin has entropy of 1 bit: heads and tails are equally likely. A coin with probabilities 0.9 and 0.1 has entropy of about 0.47 bits because its outcome is more predictable. A fair six-sided die has about 2.59 bits, and a standard deck of equally likely cards about 5.7 bits. section 5.1.3 section 5.1.4

Shannon’s 1948 theory treated information in terms of uncertainty resolved, rather than meaning or physical message length. Its mathematical structure drew on earlier work by Boltzmann and Gibbs on physical entropy. For a fixed set of outcomes, entropy is higher when probabilities are more evenly distributed; the number of possible outcomes also matters. section 5.0 section 5.1.2 section 10.2.4

Predictable redundancy creates opportunities for lossless compression: AAAAAA can be represented as A × 6. Less predictable content offers fewer such opportunities. Redundancy can also be added deliberately to detect and correct transmission errors; compression and error protection use redundancy for different purposes. section 5.1.4 section 10.2.4

Choosing a decision-tree split

A group evenly divided between two classes has entropy of 1 bit. Suppose a split produces two equally sized groups with entropies of 0.72 and 0.88 bits. Their weighted average is 0.80 bits, so the information gain is 1.00 − 0.80 = 0.20 bits. Comparing candidate splits this way favors reductions in class uncertainty. section 5.3.1

Entropy also underlies mutual information, which measures how much knowing one variable reduces uncertainty about another and can help select predictors. Information content is not the same as decision value: evidence can reduce uncertainty substantially without changing the preferred action, while a small update can change a decision. section 5.3.3 section 7.1.3

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Defines entropy mathematically and works through bit calculations, compression, and information gain.
Examples
Compares fair and biased coins, a die, and a deck of cards, then calculates a decision-tree split.
What you can do after
Evaluate and understand source uncertainty and compare candidate decision-tree splits using entropy and information gain.
How it connects
Connects entropy to redundancy, compression, information gain, mutual information, and decision value.

Also explained in

Compare how 19 books explain entropy →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.