Entropy

Definition:

• Measures impurity

Sample Entropy:

• Measures impurity of a sample
  • 
• $H(X)=-{\sum }_{i}P(X=i)\ast {\log }_2(P(X=i))$
  • $0\le H(X)\le {\log }_2(N)$
  • the number of expected bits needed to encode a randomly drawn value of $X$ (under most efficient code)
  • $-{\log }_2(P(X=i))$ represents the number of bits needed to encode the event “X=i” if it were a binary event. \
    • For example, if the probability is 1/4, then log2​(1/4)=−2, implying that 2 bits are needed to encode this event.
  • $P(X=i)\ast {\log }_2(P(X=i))$ calculates the expected number of bits needed to encode the event “X=i”.
  • Sums up the expected number of bits for all possible values of X

Conditional Entropy:

• Of a variable $Y$ conditioned on a random variable $X$
• $H(Y|X)=-{\sum }_{j=1}^n[P(X=j){\sum }_{i=1}^{m}P(Y=i|X=j){\log }_{2}P(Y=i|X=j)]$
  • $H(Y|X)={\sum }_j^{m}P(X=j)H(Y|X=j)$
  • $H(Y|X=j)=-{\sum }_j^{m}P(Y=i|X=j){\log }_{2}P(Y=i|X=j)$ by def

Information Gain:

• Decrease in entropy (less random) after knowing $X$
• $IG(X)=H(Y)-H(Y|X)$