Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

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

1 Answer 1

up vote 6 down vote accepted

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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