Epistemic status: This first collaboration between Daniel Chiang (who is interested in the algorithmic information theory of incrementally constructed representations) and myself (Cole Wyeth) contains some fairly simple but elegant results that help illustrate differences between ordinary and reflective Oracle Solomonoff Induction.

Practical reasoning relies on context-specific prediction rules, which can be described as "incomplete models" or "partial experts." One simple example is "sleeping experts" which make predictions only at certain times (when they are "awake"), discussed here: https://www.lesswrong.com/posts/CGzAu8F3fii7gdgMC/a-simple-explanation-of-incomplete-models

Can Solomonoff's universal distribution take advantage of sleeping experts? We argue that the ordinary universal distribution has only a weak version of this property, while reflective Oracle Solomonoff Induction (rOSI) is perfectly capable of representing sleeping experts.

Note on inequalities: Globally assume that $+ \leq$ is up to a small additive constant independent of all measures and sequences but possibly depending on the choice of UTM.

Independent Sub-Environments with M

We first prove a simple lemma which we call "modular loss bound" for the ordinary universal distribution $M (x)$ where $x$ is a binary string. The rough idea is that if we have a true environment $μ (x)$ , while $ν (x)$ is a simpler environment which agrees with $μ (x)$ on the first $n$ bits, then we should we be able to bound the KL divergence between $μ (x)$ and $M (x)$ for the first $n$ bits using $K (ν)$ , since both environments have identical behavior on the first $n$ bits. Let $M$ be the set of lower semicomputable semimeasures.

Lemma 1 (Modular loss bound): Denote $D_{n} = \sum_{t = 1}^{n} E_{μ} [d_{t} (\cdot)]$ where $d_{t} (x_{< t}) := \sum_{x_{t} \in X} μ (x_{t} | x_{< t}) ln (\frac{μ (x_{t} | x_{< t})}{M (x_{t} | x_{< t})})$ as the KL divergence between $μ (x)$ and $M (x)$ for the first $n$ bits, let $M_{μ}^{n} = {ν \in M | \forall x_{1 : n} \in B^{n}, ν (x_{1 : n}) = μ (x_{1 : n})}$ and $ν = argmin ν^{'} \in M_{μ}^{n} K (ν^{'})$ , then we have $D_{n} \leq l n (2) K (ν)$ with $K (ν) \leq K (μ)$ by definition.

Proof:

Define $ξ (x) = \sum_{ν \in M} 2^{- K (ν)} ν (x)$

By universality, we have

$M (x) \times = ξ (x) \geq 2^{- K (ν)} ν (x)$ $⟹ l n \frac{ν (x)}{M (x)} \leq l n (2) K (ν)$

The first equality can be made exact to avoid introducing an additive constant on the right. This is possible by ...

Posts

Wikitag Contributions

Comments