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

University of Michigan - Ann Arbor

It is useful and necessary to talk about conditional entropy, instead of leaving the subject where the textbook drops off. 
Let $$Y$$ be the set of labels, and let $$X$$ be the set of features. 

**Conditional Entropy** 
We now define conditional entropy as $$H(Y \mid X=x) = -\sum_{y\in Y} \Pr(Y=y)\log \Pr(Y=y \mid X=x)$$. 

We interpret the conditional entropy as the variability in the label, given the feature $$X=x$$. In context: how uncertain are we about a person’s health, given that we know how many times a year they go to the doctors office. 


Conditional Entropy

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. 


Learn Before

Related