Hypothesis Space Entropy

post by lsusr · 2021-05-14T07:21:21.349Z · LW · GW · 2 comments

Contents

  No Tunable Parameters
  With Tunable Parameters
    Branching component −ρilnρi
    Recursive component ρiHμ,i
  Lessons for Hypothesis Space Design
None
2 comments

In Why quantitative finance is so hard [LW · GW] 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}$$ ↩︎

2 comments

Comments sorted by top scores.