Defining Optimization in a Deeper Way Part 1

[J Bostock]

My aim is to define optimization without making reference to the following things:

1. A “null” action or “nonexistence” of the optimizer. This is generally poorly defined, and choices of different null actions give different answers.

2. Repeated action. An optimizer should still count even if it only does a single action.

3. Uncertainty. We should be able to define an optimizer in a fully deterministic universe.

4. Absolute time at all. This will be the hardest, but it would be nice to define optimization without reference to the “state” of the universe at “time t”.

Attempt one

First let’s just eliminate the concept of a null action. Imagine the state of the universe at a time $t$.

Let’s divide the universe into two sections and call these $A$ and $B$. They have states $S^A$ and $S^B$. If we want to use continuous states we’ll need to have some metric $D(s_1,s_2)$ which applies to these states, so we can calculate things like the variance and entropy of probability distributions over them.

Treat $S^A$ and $S^B$ as part of a Read-Eval-Print-Loop. Each $S_t^A$ produces some output $O_t^A$ which acts like a function mapping $S_t^B\to S_{t+1}^B$, and vice versa.$O_t^A$ can be thought of as things which cross the Markov blanket.

Sadly we still have to introduce probability distributions. Let’s consider a joint probability distribution $P_t^{AB}(s^A,s^B)$, and also the two individual probability distributions $P_t^A\left(s^A\right)$ and $P_t^B\left(s^B\right)$.

By defining distributions over $O$ outputs based on the distribution $P_t^{AB}$, we can define $P_{t+1}^{AB}(s^A,s^B)$ in the “normal” way. This looks like integrating over the space of $s_A$ and $s_B$ like so:

$P_{t+1}^{AB}(s_{t+1}^A,s_{t+1}^B)=\int P_t^{AB}(s_t^A,s_t^B)\delta (O_t^A\left(s_t^B\right)-s_{t+1}^B)\delta (O_t^B\left(s_t^A\right)-s_{t+1}^A)d{s}_t^{A}d{s}_t^B$

What this is basically saying is that to define the probability distribution of states $s_{t+1}^A$ and $s_{t+1}^B$, we integrate over all states $s_t^A$ and $s_t^B$ and sum up the states where the $O_t^A$ corresponding to $s_t^A$ maps $s_t^B$ to the given $s_{t+1}^B$.

Now lets define an “uncorrelated” version of $P_{t+1}^{AB}$, which we will refer to as $P_{t+1}^{\prime AB}$.

$P_{t+1}^{\prime AB}(s_{t+1}^A,s_{t+1}^B)=\int P_t^A\left(s_t^A\right)P_t^B\left(s_t^B\right)\delta (O_t^A\left(s_t^B\right)-s_{t+1}^B)\delta (O_t^B\left(s_t^A\right)-s_{t+1}^A)d{s}_t^{A}d{s}_t^B$

This loosely represents what happens if we decorrelate $s^A$ and $s^B$. In the language of humans, this is like an agent taking a random move from a selection.

We can refer to a probability distribution $P_t^{AB}$ as an “optimizing” probability distribution if $P_{t+1}^{\prime AB}$ is higher entropy than $P_{t+1}^{AB}$.

---

For an example, imagine the universe is divided into two parts: a room $R$ and a thermostat $T$. The room can have states in the set $s^R\in \{hot,lukewarm,cold\}$, and the thermostat can have states $s^T\in \{high,low,off\}$. Imagine that $O^R$ and $O^T$ are defined as follows:

$O^T\left[high\right]:\{\begin{array}{c}hot\to hot\\ warm\to hot\\ cold\to warm\end{array}$
$O^T\left[low\right]:\{\begin{array}{c}hot\to hot\\ warm\to warm\\ cold\to cold\end{array}$
$O^T\left[off\right]:\{\begin{array}{c}hot\to warm\\ warm\to cold\\ cold\to cold\end{array}$

$O^R\left[hot\right]:\{\begin{array}{c}high\to off\\ low\to off\\ off\to off\end{array}$
$O^R\left[warm\right]:\{\begin{array}{c}high\to low\\ low\to low\\ off\to low\end{array}$
$O^R\left[cold\right]:\{\begin{array}{c}high\to high\\ low\to high\\ off\to high\end{array}$

Basically the thermostat decides whether the room gets warmer, stays the same, or gets colder, and the thermostat.

We can also consider the probability mass flowing from each of the nine states to another one:

	$hot$	$warm$	$cold$
$high$	$(hot,off)$	$(hot,low)$	$(warm,high)$
$low$	$(hot,off)$	$(warm,low)$	$(cold,high)$
$off$	$(warm,low)$	$(cold,low)$	$(cold,high)$

Imagine the following $P_0^{TR}(s^T,s^R)$:

	$hot$	$warm$	$cold$
$high$	0	0	$1/3$
$low$	0	$1/3$	0
$off$	$1/3$	0	0

This will give us the following $P_1^{TR}(s^T,s^R)$:

	$hot$	$warm$	$cold$
$high$	0	$1/3$	0
$low$	0	$1/3$	0
$off$	0	$1/3$	0

Which has 1.6 bits of entropy.

And the following $P_1^{\prime TR}(s^T,s^R)$:

	$hot$	$warm$	$cold$
$high$	$0$	$1/9$	$2/9$
$low$	$1/9$	$1/9$	$1/9$
$off$	$2/9$	$1/9$	$0$

Which has 2.7 bits of entropy.

This means that the joint-ness of the probability distribution $P_0^{RT}$ has removed 1.1 bits of entropy from the system. We say that our choice of $P_0^{RT}$ is optimizing, with an optimizing strength of 1.1 bits.

---

But what if we consider a “smarter” thermostat, which turns off just before the temperature changes.

$O^R\left[hot\right]:\{\begin{array}{c}high\to off\\ low\to off\\ off\to low\end{array}$
$O^R\left[warm\right]:\{\begin{array}{c}high\to low\\ low\to low\\ off\to low\end{array}$
$O^R\left[cold\right]:\{\begin{array}{c}high\to low\\ low\to high\\ off\to high\end{array}$

	$hot$	$warm$	$cold$
$high$	$(hot,off)$	$(hot,low)$	$(warm,low)$
$low$	$(hot,off)$	$(warm,low)$	$(cold,high)$
$off$	$(warm,off)$	$(cold,low)$	$(cold,high)$

With the same choice of $P_0^{TR}(s^T,s^R)$:

	$hot$	$warm$	$cold$
$high$	0	0	$1/3$
$low$	0	$1/3$	0
$off$	$1/3$	0	0

This will give us the following $P_1^{TR}(s^T,s^R)$:

	$hot$	$warm$	$cold$
$high$	0	0	0
$low$	0	1	0
$off$	0	0	0

With an entropy of zero.

And the following $P_1^{\prime TR}(s^T,s^R)$:

	$hot$	$warm$	$cold$
$high$	$0$	$0$	$2/9$
$low$	$1/9$	$1/3$	$1/9$
$off$	$2/9$	$0$	$0$

Which has 2.2 bits of entropy.

In the new system, $P_0^{RT}$ has an optimizing strength of 2.2 bits, approximately twice as much. This indicates that the latter system is “better” at optimizing the distribution $P_0^{RT}$ in some way.

---

So we have eliminated the idea of needing the optimizer to have clearly-defined existence/​nonexistence cases, or needing some “null” action to compare its outputs to. This is good. We have also eliminated the concept of repeated action.

Next I will attempt to eliminate the need to start with a probability distribution. In both of the examples above, our choice of $P_0^{RT}$ was important. I want to find a more “natural” way of defining probability distributions.