Hypothesis Space Entropy

[lsusr]

In Why quantitative finance is so hard I explained why the entropy of your dataset must exceed the entropy of your hypothesis space. I used a simple hypothesis space with $n$ equally likely hypotheses each with $m$ tunable parameters. Real life is not usually so homogeneous.

No Tunable Parameters

Consider an inhomogeneous hypothesis space with zero tunable parameters. Instead of $H=\log n$ which works for homogeneous hypothesis spaces, we must use more complicated entropy equation.

$$H=-\sum _{i=1}^n{\rho }_i\ln {\rho }_i$$

This equation makes intuitive sense. It vanishes when one ${\rho }_{i=j}$ equals 1 and all other ${\rho }_{i\ne j}$ equal 0. Our equation is extremized when all ${\rho }_i$ are equal at $\frac{1}{n}$. $H=\log n$ is the maximal case when ${\rho }_i=\frac{1}{n}\forall i\in \{1,\dots ,n\}$^[1].

With Tunable Parameters

Suppose each hypothesis $i$ has $m_i$ tunable parameters. We can plug $m_i$ into our entropy equation.

$$H=\sum _{i=1}^n{\rho }_i(m_i-\ln {\rho }_i)$$

Our old equation $H=m+\log n$ is just the special case where all ${\rho }_i$ are homogenous and $m_i$ are homogeneous too.

We have so far treated $m_i$ as representative of each hypothesis’s tunable parameters. More generally, $m_i$ represents each hypothesis’s internal entropy. If we think of hypotheses as a weighted tree, $m_i$ is what you get when you iterate one level down the tree. Our variable $H$ identifies the root of the tree. Suppose $i$th branch of the next level down is called $H_i$.

$$H=\sum _{i=1}^n{\rho }_i(H_i-\ln {\rho }_i)$$

We can define the entropy of the rest of the tree with a recursive equation.

$$\begin{array}{ccc}{H}_{\mu }& =& \sum _{i=1}^n{\rho }_i(H_{\mu ,i}-\ln {\rho }_i)\\ & =& \sum _{i=1}^n({\rho }_i{H}_{\mu ,i}-{\rho }_i\ln {\rho }_i)\end{array}$$

There are two parts to this equation: the recursive component ${\rho }_i{H}_{\mu ,i}$ and the branching component $-{\rho }_i\ln {\rho }_i$.

Branching component $-{\rho }_i\ln {\rho }_i$

The $-{\rho }_i\ln {\rho }_i$ component is maximized when ${\rho }_i=\frac{1}{e}$.

$$\begin{array}{ccc}-{\rho }_i\ln {\rho }_i& =& -\frac{1}{e}\ln \frac{1}{e}\\ & =& \frac{1}{e}\ln e\\ & =& \frac{1}{e}\end{array}$$

The branching component tops out at $\frac{1}{e}$. It can never contribute a massive quantity of entropy to your hypothesis space because it is limited to $\frac{1}{e}$ entropy per level of the tree.

$$0\le -{\rho }_i\ln {\rho }_i\le \frac{1}{e}$$

The branching factor is mostly unimportant. The bulk of our entropy comes from the recursive component.

Recursive component ${\rho }_i{H}_{\mu ,i}$

Fix ${\rho }_i$ at a positive value. There is no limit to how big $H_{\mu ,i}$ can become. You can make it arbitrarily large just by adding parameters. Consequently ${\rho }_i{H}_{\mu ,i}$ can become arbitrarily large too. In real world situations we should expect the recursive components of our hypothesis space to dominate the branching components.

If ${\rho }_i$ vanishes then the recursive component disappears. This might explain why human minds like to round “extremely unlikely” $ϵ>{\rho }_i>0$ to “impossible” ${\rho }_i=0$ when $H_{\mu ,i}$ is large. It removes lots of entropy from our hypothesis space still being right almost all of the time. This may be related to synaptic pruning.

Lessons for Hypothesis Space Design

Once again, we have confirmed that having hypotheses with lots of parameters is a worse problem that having lots of hypotheses to choose between. More generally, one or more hypotheses with exceptionally high entropy dominate the total entropy of your hypothesis space. If you want better priors then the first step of your optimization should be to eliminate these complex subtrees from your hypothesis space.

---

1. ↩︎

   Proof: $$\begin{array}{ccc}H& =& -\sum _{i=1}^n{\rho }_i\ln {\rho }_i\\ & =& -\sum _{i=1}^n\frac{1}{n}\ln \frac{1}{n}\\ & =& -\ln \frac{1}{n}\\ & =& -\ln \left(n^{-1}\right)\\ & =& \ln n\end{array}$$

[Alexander Gietelink Oldenziel]

I am confused what is meant by a ‘hypothesis’.

Is this a probability distribution? What is the mathematical object that you denote by hypothesis?

[lsusr]

It’s a probability distribution. A hypothesis space is a probability distribution of probability distributions.