Dream Coder - Algorithm 3

Let us say you have a sample space $S$ and $s$ is an event in $S$ that occurs with probability $P(s)=\frac{1}{2}$. so if we observe the event $s$, we are effective cutting the sample space in half. So this event carries $1$ bit of information.
Similarly, an event $p$ with probability $P(p)=\frac{1}{4}$ carries two bits of information, because observing it effectively cuts the sample space into a quarter.

So less likely events carry more information when they occur. in general, if $x\in S$ and $P:S\to [0,1]$ is a probability function, $I(x)=-lo{g}_2(P(x))$.

Description of the Enumerate Algorithm

Setup and Notation

Let $S$ denote the sample space of all possible programs, and let $\mu :S\to [0,1]$ be a probability distribution over programs, such that $\mu (x)$ represents the probability of program $x\in S$. The information content of a program $x$ is defined as:

This measures the amount of information carried by observing $x$, and less probable events carry more information. For example:

• If $P(x)=\frac{1}{2}$, then $I(x)=1$ bit.

• If $P(x)=\frac{1}{4}$, then $I(x)=2$ bits.

The goal of the enumerate procedure is to generate programs in approximately decreasing order of probability (or equivalently, increasing order of information) under $\mu$. The algorithm works in two phases: a Heap Search Phase followed by a Parallel DFS Phase.

Heap Search Phase

Initialization

1. Define a lower bound $\text{lowerBound}=0$ and an upper bound $\text{upperBound}=\mathrm{\Delta }$, where $\mathrm{\Delta }>0$ is a hyperparameter controlling the granularity of the search.

2. Initialize a max-heap, where programs are ordered by their priority, defined as $\text{priority}(x)={\log }_2(\mu (x))$ (equivalently, higher probabilities are prioritized).

3. Insert the initial empty program (or syntax tree) into the heap with priority $0$.

Iterative Heap Processing

While the heap size is manageable (specifically, $|\text{heap}|\le 10\times \text{CPUs}$):

1. Pop a program $\rho$ from the heap:

   • If $\rho$ is complete (a fully-specified program):

     • Check whether $\text{lowerBound}\le I(\rho )\le \text{upperBound}$. If true, yield $\rho$.

   • Otherwise, compute the set of children $\text{children}(\rho )$, where each child $c\in \text{children}(\rho )$ fills in the next "hole" in $\rho$'s syntax tree.

2. For each child $c$:

   • Compute its information $I(c)=-{\log }_2(\mu (c))$.

   • If $I(c)\le \text{upperBound}$ (i.e., $c$ is not too improbable), insert $c$ into the heap with priority ${\log }_2(\mu (c))$.

If the heap grows too large ($|\text{heap}|>10\times \text{CPUs}$), transition to the Parallel DFS Phase.

Parallel DFS Phase

Task Distribution

1. Distribute up to $10\times \text{CPUs}$ programs from the heap to the CPUs for processing. Each CPU receives approximately $10$ programs (partial programs) as independent tasks.

2. Set the initial search bounds for the DFS to $\text{lowerBound}=0$ and $\text{upperBound}=\mathrm{\Delta }$.

Per-CPU DFS Procedure

Each CPU processes its assigned tasks sequentially. For each partial program $\rho$:

1. Perform a depth-first search (DFS) to explore all completions of $\rho$.

2. When a completion $c$ is found:

   • Check if $\text{lowerBound}\le I(c)\le \text{upperBound}$.

   • If true, yield $c$.

3. For incomplete programs:

   • Compute their children $\text{children}(\rho )$.

   • For each child $c$:

     • Compute its information $I(c)$.

     • If $I(c)\le \text{upperBound}$, push $c$ onto the local DFS stack for further exploration.

Each CPU finishes all of its $10$ assigned jobs sequentially but operates in parallel with other CPUs.

Lower Bound Adjustment

Once all CPUs complete their assigned jobs:

1. Increase the lower bound by $\mathrm{\Delta }$, i.e., set $\text{lowerBound}\leftarrow \text{lowerBound}+\mathrm{\Delta }$.

2. Adjust the upper bound accordingly, i.e., $\text{upperBound}\leftarrow \text{upperBound}+\mathrm{\Delta }$.

3. Reuse the same set of programs from the heap for the next DFS phase, but now search for completions with higher information (i.e., less probable programs).

Summary of the Algorithm

1. The algorithm starts with a Heap Search Phase, which uses a max-heap to explore programs with information $I(\rho )\le \mathrm{\Delta }$.

2. When the heap grows too large, the algorithm transitions to a Parallel DFS Phase:

   • Each CPU explores its assigned programs in parallel, searching for completions within the current information bounds $[\text{lowerBound},\text{upperBound}]$.

   • The bounds are incrementally shifted by $\mathrm{\Delta }$ after each round, allowing the algorithm to progressively explore less probable programs.

This approach efficiently enumerates programs in decreasing order of probability while balancing parallelism and memory constraints.

A note on (MDL) or minimum description length:

Basically, the information of a program is an estimate of its MDL, that is what the upper bound is for, highly informative programs are longer and are lower probability.