3
$\begingroup$

Suppose I have a decision tree in which there is a label $L$ under which is the attribute $A$ as shown below. I am given that the Shannon entropy of label $L$ is $H(L) = 0.95$.

enter image description here

I must find the Shannon entropy of $L$ given $A$ ($H(L \mid A)$). Here's what I have tried.

\begin{eqnarray} H(L \mid A) &=& -(\frac{6}{8} \log_2 \frac{4}{6} + \frac{2}{8} \log_2 \frac{1}{2}) \\ &\approx& 0.69 \end{eqnarray}

However, $H(L \mid A) \approx 0.94$. Where did I err? Is my formula for Shannon entropy accurate?

$\endgroup$
  • $\begingroup$ The Shannon entropy is always non-negative. You must have got something wrong. $\endgroup$ – Yuval Filmus Feb 6 '13 at 2:40
  • $\begingroup$ I fixed my question. The problem still remains though. Thanks! $\endgroup$ – David Faux Feb 6 '13 at 2:48
  • $\begingroup$ You could also explain what that formula is. That would make the question easier and quicker to understand. $\endgroup$ – Juho Feb 6 '13 at 2:54
  • $\begingroup$ Good point. Sorry about not providing background on the formula. en.wikipedia.org/wiki/Entropy_(information_theory)#Rationale $\endgroup$ – David Faux Feb 6 '13 at 3:32
7
$\begingroup$

Back to the definitions: $$H(L\mid A) = \sum_a p(A=a) H(L \mid A=a).$$

As you compute, $P(A=true)=6/8$ and $P(A=false)=2/8$.

However, you don't compute $H(L\mid A=true)$ but instead compute $P(L=positive\mid A=true)$. [and the same for $A=false$.].

With standard definition of $H()$ we get,

$$H(L\mid A=true) = - 4/6\log_2(4/6) - 2/6\log_2(2/6) = 0.9182958$$ $$H(L\mid A=false) = H(1/2) = 1$$

And thus, $H(L\mid A) = 6/8 \times 0.918 + 2/8\times 1 = 0.938 \approx 0.94$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.