information gain
In plain wordsHow much a question reduces uncertainty about the answer. A decision tree asks first the question that removes the most uncertainty, measured in bits.
The reduction in the entropyentropy, n.: A measure of unpredictability. A fair coin toss has more entropy than a rigged one; an AI that is unsure of its next word has high entropy. of the class labels achieved by partitioning a set of examples on an attribute: the entropy of the parent set minus the size-weighted average entropy of the resulting subsets. It is the splitting criterion of ID3ID3, abbr.: An early, influential method for automatically building a decision tree from examples, choosing at each step the question that most reduces uncertainty about the answer. and, in normalized form, of C4.5C4.5, prop. n.: A widely used 1990s program that learns decision trees and rule sets from data; unlike its predecessor, it trims away unhelpful branches, copes with gaps in the data and can split on measured numbers., and it equals the empirical mutual informationmutual information, n.: How much knowing one thing tells you about another — for example, how much a word reveals about the topic of a document. It is zero when the two are unrelated. between the attribute and the class. Because an attribute with a different value for nearly every example (a serial number, say) yields tiny pure subsets, and so a high gain, while predicting nothing about new cases, C4.5 normalizes the gain by the entropy of the partition itself (the split information), giving the gain ratio. Beyond trees, expected information gain is the quantity maximized in Bayesian experimental design and some active learningactive learning, n.: A way to train a model with fewer labeled examples by letting it choose which unlabeled examples a person should label next, usually the ones it is most unsure about. strategies, and it is used to rank features.
Outlook has the highest information gain, so it becomes the root of the tree.
Origin
Built on Claude Shannon's 1948 definition of entropy. J. Ross Quinlan made entropy reduction the attribute-selection criterion of ID3 (published 1979), following a suggestion of Peter Gács, and introduced the gain ratio in the mid-1980s; both are described in 'Induction of Decision Trees' (1986).
Usage note
In Bayesian statistics 'information gain' often denotes the Kullback–Leibler divergenceKullback–Leibler divergence, n.: A score for the cost of believing the wrong odds: on average, how much more surprised you will be by real outcomes than someone who knew the true probabilities. It is zero only when your odds are exactly right. from prior to posterior, a related but different quantity.
Related
- entropyentropy, n.: A measure of unpredictability. A fair coin toss has more entropy than a rigged one; an AI that is unsure of its next word has high entropy.
- ID3ID3, abbr.: An early, influential method for automatically building a decision tree from examples, choosing at each step the question that most reduces uncertainty about the answer.
- C4.5C4.5, prop. n.: A widely used 1990s program that learns decision trees and rule sets from data; unlike its predecessor, it trims away unhelpful branches, copes with gaps in the data and can split on measured numbers.
- decision treedecision tree, n.: A model that makes a prediction by asking a series of yes-or-no questions about the input, like a flowchart, with each answer leading to the next question until it reaches a final answer.
- Gini impurityGini impurity, n.: A score for how mixed a group is: zero when every item belongs to the same category, higher when categories are jumbled together. Decision trees choose splits that make groups purer.
- mutual informationmutual information, n.: How much knowing one thing tells you about another — for example, how much a word reveals about the topic of a document. It is zero when the two are unrelated.
- Kullback–Leibler divergenceKullback–Leibler divergence, n.: A score for the cost of believing the wrong odds: on average, how much more surprised you will be by real outcomes than someone who knew the true probabilities. It is zero only when your odds are exactly right.
- Gini impurityGini impurity, n.: A score for how mixed a group is: zero when every item belongs to the same category, higher when categories are jumbled together. Decision trees choose splits that make groups purer.
Sources
- Quinlan, J. R. (1986). Induction of Decision Trees. Machine Learning, 1, 81–106. rd.springer.com/article/10.1007/BF00116251
Mentioned in
decision treedecision tree, n.: A model that makes a prediction by asking a series of yes-or-no questions about the input, like a flowchart, with each answer leading to the next question until it reaches a final answer., entropyentropy, n.: A measure of unpredictability. A fair coin toss has more entropy than a rigged one; an AI that is unsure of its next word has high entropy., Gini impurityGini impurity, n.: A score for how mixed a group is: zero when every item belongs to the same category, higher when categories are jumbled together. Decision trees choose splits that make groups purer., C4.5C4.5, prop. n.: A widely used 1990s program that learns decision trees and rule sets from data; unlike its predecessor, it trims away unhelpful branches, copes with gaps in the data and can split on measured numbers., ID3ID3, abbr.: An early, influential method for automatically building a decision tree from examples, choosing at each step the question that most reduces uncertainty about the answer., mutual informationmutual information, n.: How much knowing one thing tells you about another — for example, how much a word reveals about the topic of a document. It is zero when the two are unrelated., Ross QuinlanRoss Quinlan, prop. n.: An Australian computer scientist who created ID3 and C4.5, influential programs that learn decision trees, flowchart-like rules for classifying examples.