https://github.com/eecs445-f16/umich-eecs445-f16/blob/master/lecture11_info-theory-decision-trees/lecture11_info-theory-decision-trees.pdf

Open Source EECS 445 Slides from 2016


We define information gain as $$IG(X,Y) = H(Y) - H(Y\mid X)$$. 

We interpret information gain as the amount of information we learn about the label $$Y$$, given a specific feature $$X$$. 

Note that if the feature $$X$$ is completely uncorrelated with the label $$Y$$, then $$H(Y\mid X) = H(Y)$$. Therefore $$IG(X,Y) = 0$$. 

As such when we choose the next feature to split on we should choose the one that maximizes information gained. 


Information Gain

Conditional entropy quantifies the remaining uncertainty in a label $$Y$$ after observing a feature $$X$$. Let $$Y$$ be the set of possible labels and $$X$$ be the set of possible feature values.

For a fixed feature value $$X=x$$, the conditional entropy is $$H(Y \mid X=x) = -\sum_{y\in Y} \Pr(Y=y \mid X=x)\log \Pr(Y=y \mid X=x)$$.

Averaging over all values of $$X$$ gives the overall conditional entropy $$H(Y\mid X) = \sum_{x\in X} \Pr(X=x)\, H(Y\mid X=x)$$, which is the quantity used when computing information gain.

Intuitively: how uncertain are we about a person's health outcome, given that we know how many times a year they visit the doctor?

University of Michigan - Ann Arbor

Google

Similar to the Gini index numerically, entropy reflects node purity in a classification tree. A small value implies that one class dominates the region. Entropy is defined as: $$ D=-\sum_{k=1}^{K} \hat{p}_{m k} \log \hat{p}_{m k} $$ where $$\hat{p}_{m k}$$ denotes the proportion of training observations in the $$m$$th region that belong to the $$k$$th class.

Learn Before

Related

Learn After