foundations of computational agents
The information theory box discussed how to represent information using bits. For , it is possible to build a code that, to identify uses bits (or the integer greater than this). The expected number of bits to transmit a value for is then
This is the information content or entropy of random variable .
[Note that, unlike the notation used elsewhere in the book, is a function of the variable, not a function of the values of the variable. Thus, for a variable , the entropy is a number, unlike which a function that given a value for , returns a number.]
The entropy of given the observation is
Before observing , the expectation over :
is called conditional entropy of given .
For a test that determines the value of , the information gain from this test is , which is the number of bits used to describe minus the expected number of bits to describe after learning . The information gain is never negative.
Suppose spinning a wheel in a game can produces a number in the set , each with equal probability. Let be the outcome of a spin. Then bits.
Suppose there is a sensor that detects whether the outcome is greater than 6. if . Then . The information gain of is thus bits. A fraction of a bit makes sense in that it is possible to design a code that uses 219 bits to predict 100 outcomes.
For an “even” sensor , where if is even, . The information gain of is thus bit.
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.