UPENN | ML | DECISION TREE

Question

Given the following table of observations, calculate the information gain $IG(Y |X)$ that would result from learning the value of $X$.

X	Y
Red	True
Green	False
Brown	False
Brown	False

 

(a) 1/2
(b) 1
(c) 3/2
(d) 2
(e) none of the above

 

Answer 1

Information Gain \( IG(Y | X) = \frac{1}{2} \)

Calculate \( H(Y) \), the entropy of \( Y \): \[ \begin{aligned} P(Y = \text{True}) &= \frac{2}{4} = 0.5 \\ P(Y = \text{False}) &= \frac{2}{4} = 0.5 \\ H(Y) &= -\left(0.5 \cdot \log_2(0.5) + 0.5 \cdot \log_2(0.5)\right) = 1 \end{aligned} \] Calculate the entropy of \( Y \) conditioned on each value of \( X \): For \( X = \text{Red} \): \[ \begin{aligned} P(Y = \text{True} | X = \text{Red}) &= 1 \\ P(Y = \text{False} | X = \text{Red}) &= 0 \\ H(Y | X = \text{Red}) &= -\left(1 \cdot \log_2(1) + 0 \cdot \log_2(0)\right) = 0 \end{aligned} \] For \( X = \text{Green} \): \[ \begin{aligned} P(Y = \text{True} | X = \text{Green}) &= 0 \\ P(Y = \text{False} | X = \text{Green}) &= 1 \\ H(Y | X = \text{Green}) &= -\left(0 \cdot \log_2(0) + 1 \cdot \log_2(1)\right) = 0 \end{aligned} \] For \( X = \text{Brown} \): \[ \begin{aligned} P(Y = \text{True} | X = \text{Brown}) &= 0.5 \\ P(Y = \text{False} | X = \text{Brown}) &= 0.5 \\ H(Y | X = \text{Brown}) &= -\left(0.5 \cdot \log_2(0.5) + 0.5 \cdot \log_2(0.5)\right) = 1 \end{aligned} \] Calculate the weighted average of the conditional entropies: \[ H(Y | X) = \frac{1}{4} \cdot 0 + \frac{1}{4} \cdot 0 + \frac{2}{4} \cdot 1 = \frac{1}{2} \] Calculate the information gain: \[ IG(Y | X) = H(Y) - H(Y | X) = 1 - \frac{1}{2} = \frac{1}{2} \]

Comments

But here P(Y = True) = 1/4

and P(Y = False) = 2/4

Like this IG(Y|X) = H(Y) only as after calculating H(Y|X) = 0

and H(Y) =