Information Entropy

$H(X)\equiv -\mathbb{E}[\log p(X)]$

• $H(X)$ is the entropy of a random variable $X$ and heuristically gives the average level of information/surprise/uncertainty of the variable’s outcomes
• E.g. entropy of a discrete uniform random variable $X\sim \text{Uniform({1,2,...,m}})$:
  • $H(X)=-\sum _{x\in X}p(x)\log (p(x))=-\sum _{x=1}^m\frac{1}{m}\log \left(\frac{1}{m}\right)=-\log \left(\frac{1}{m}\right)$
  • Increasing with respect to $m$
  • There is more uncertainty when there are more choices

Topics

• Decision Tree