The information theory box discussed how to represent information using bits. For $x\in domain(X)$, it is possible to build a code that, to identify $x$ uses $-{\log }_{2}P(x)$ bits (or the integer greater than this). The expected number of bits to transmit a value for $X$ is then

This is the information content or entropy of random variable $X$.

[Note that, unlike the notation used elsewhere in the book, $H$ is a function of the variable, not a function of the values of the variable. Thus, for a variable $X$, the entropy $H(X)$ is a number, unlike $P(X)$ which a function that given a value for $X$, returns a number.]

The entropy of $X$ given the observation $Y=y$ is

Before observing $Y$, the expectation over $Y$:

is called conditional entropy of $X$ given $Y$.

For a test that determines the value of $Y$, the information gain from this test is $H(X)-H(X\mid Y)$, which is the number of bits used to describe $X$ minus the expected number of bits to describe $X$ after learning $Y$. The information gain is never negative.

The notion of information is used for a number of tasks:

• •

  In diagnosis, an agent could choose a test that provides the most information.

• •

  In decision tree learning, information theory provides a useful criterion for choosing which property to split on: split on the property that provides the greatest information gain. The elements it must distinguish are the different values in the target concept, and the probabilities are obtained from the proportion of each value in the training set remaining at each node.

• •

  In Bayesian learning, information theory provides a basis for deciding which is the best model given some data.