Intelligent Agent Foundations Forumsign up / log in
Stationary algorithmic probability
link by Jacob Hilton 1260 days ago | Janos Kramar and Patrick LaVictoire like this | 7 comments


by Jacob Hilton 1260 days ago | Jessica Taylor and Patrick LaVictoire like this | link

This is a follow-up note to a nice paper of Markus Mueller on the possibility of a machine-invariant notion of Kolmogorov complexity, available here: http://www.sciencedirect.com/science/article/pii/S0304397509006550

reply

by Janos Kramar 1257 days ago | Jessica Taylor and Patrick LaVictoire like this | link

It may still be possible to get a unique (up to scaling) invariant measure (with infinite sum) over the UTMs by invoking something like the Krein-Rutman theorem and applying it to the Markov chain’s transition operator. I haven’t yet verified that all the conditions hold.

This measure would then be an encoding-invariant way to compare UTMs’ “intrinsic complexity” in the sense of “number of bits needed to simulate”.

reply

by Janos Kramar 1243 days ago | Patrick LaVictoire likes this | link

Consider the function \(a(M_1,M_2)=2^{-d(M_1,M_2)-d(M_2,M_1)}\) where \(d(M_1,M_2)=\min\left(|x|\middle|x\in\{0,1\}^*:\forall y\in\{0,1\}^*: M_1(xy)=M_2(y)\mbox{ unless neither of these halts}\right)\). The reversible Markov chain with transition probabilities \(p(M_1,M_2)=\frac{a(M_1,M_2)}{\sum_{M'_2}a(M_1,M'_2)}\) has a bounded positive invariant measure \(\mu(M)=\sum_{M'}a(M,M')\). Of course, as the post showed, the total measure is infinite. Also, because the chain is reversible and transient, the invariant measure is far from unique - indeed, for any machine \(M_0\), the measure \(\mu(M)=p^{(0)}(M,M_0)+2\sum_{n=1}^\infty p^{(n)}(M,M_0)\) will be a bounded positive invariant measure.

It seems tempting (to me) to try to get a probability measure by modding out the output-permutations (that the post uses to show this isn’t possible for the full set of UTMs). To this end, consider the set of UTMs that have no output. (These will be unaffected by the output-permutations.) We can try to use the induced sub-digraph on these to build a probability measure \(\mu\). The measure of each UTM should be a function of the rooted edge-labeled digraph \(G_M\) rooted at that UTM.

The most natural topology on rooted edge-labeled infinite digraphs is the one generated by the sets \(\{G:G'\mbox{ is isomorphic to an induced rooted edge-labeled subgraph of G}\}\) where \(G'\) ranges over finite rooted edge-labeled digraphs - we could hope that \(\mu\) is continuous according to this topology. Unfortunately, this can’t work: if \(\mu(M)>0\) then \(\mu^{-1}((\frac{1}{2}\mu(M),\infty))\) must be open, and so it must contain some finite intersection of the generating sets; however, every such intersection that’s nonempty (as this one is) contains infinitely many UTMs, so the total measure must be infinite as well.

reply

by Janos Kramar 1243 days ago | Patrick LaVictoire likes this | link

In order to understand what the measure \(\mu\) that was constructed from \(d\) will reward, here’s the sort of machine that comes close to \(\sup_M\mu(M)=3\):

Let \(M_0\) be an arbitrary UTM. Now consider the function \(r(n)=n-2^{\lfloor \lg n \rfloor}\) (or, really, any function \(r:\mathbb{N}^+\rightarrow\mathbb{N}^0\) with \(r(n)<n\) that visits every nonnegative integer infinitely many times), and let \(L=\{x\in\{0,1\}^*:|x|>2,x_{|x|-1}=x_{r(|x|-1)},x_{|x|-2}=x_{r(|x|-2)}\}\). (The indices here are zero-based.) Choose \(x_0\in L\) such that \(x_0\) has no proper prefix in \(L\). Then, construct the UTM \(M\) that does:

repeat:
    s := ""
    while s not in L:
        # if there is no next character, halt
        s := s + readchar()
    if s == x0:
        break
M0()

This \(M\) will have \(\mu(M)>3-2^{-|x_0|}+d(M_0,M)2^{-|x_0|-d(M_0,M)}\).

\(M\) here is optimized for building up internal states (that are then UTMs that are efficiently encoded), while also being very easy to reset from these internal states; in other words being easy to “encode” from the UTMs it efficiently encodes, using at most 2 bits (an average of \(\frac{1+\sqrt{5}}{2}\)). This is somewhat interesting, but clearly doesn’t capture the kind of computational expressivity we’re primarily interested in.

reply

by Janos Kramar 1239 days ago | Patrick LaVictoire likes this | link

These results are still a bit unsatisfying.

The first half constructs an invariant measure which is then shown to be unsatisfactory because UTMs can rank arbitrarily high while only being good at encoding variations of themselves. This is mostly the case because the chain is transient; if it was positive recurrent then the measure would be finite, and UTMs ranking high would have to be good at encoding (and being encoded by) the average UTM rather than just a select family of UTMs.

The second half looks at whether we can get better results (ie a probability measure) by restricting our attention to output-free “UTMs” (though I misspoke; these are not actually UTMs but rather universal semidecidable languages (we can call them USDLs)). It concludes that we can’t if the measure will be continuous on the given digraph - however, this is an awkward notion of continuity: a low-complexity USDL whose behavior is tweaked very slightly but in a complex way may be very close in the given topology, but should have measure much lower than the starting USDL. So I consider this question unanswered.

reply

by Jonathan Lee 1249 days ago | Jessica Taylor and Patrick LaVictoire like this | link

It looks like Theorem 1 can be improved slightly, by dropping the “only if” condition on \(p_{CD} > 0\). We can then code up something like Kolmogorov complexity by adding a probability \(\frac{1}{2}\) transition from every site to our chosen UTM.

If you only want the weaker statement that there is no stationary distribution, it looks like there’s a cheaper argument: Since \(\Phi\) is aperiodic and irreducible the hypothetical stationary distribution \(\pi\) is unique. \(\Phi\) is closed under the action of \(\Delta\), and (2) implies that for any \(g \in \Delta\), the map \(\Gamma_g\) is an automorphism of the Markov chain. If the (infinite) transition matrix is \(T\), then \(\Gamma_g\) can be considered as a permutation matrix with (abusing notation) \(\Gamma_g^{-1}T\Gamma_g = T\). Then \(T\Gamma_g\pi = \Gamma_g\pi\) and so \(\Gamma_g\pi = \pi\) by uniqueness. So \(\pi\) is constant on orbits of \(\Gamma_{\Delta}\), which are all countably infinite. Hence \(\pi\) is everywhere \(0\), a contradiction.

The above still holds if (2) is restricted to only hold for a group \(G < \Delta\) such that every orbit under \(\Gamma_G\) is infinite.

I think the above argument shows why (2) is too strong; we shouldn’t expect the world to look the same if you pick a “wrong” (ie. complicated) UTM to start off with. Weakening (2) might mean saying something like asserting only \(p_{CD} = \sum \mu(\Gamma) p_{\Gamma(C)\Gamma(D)}\). To do this, we might define the measures \(\mu\) and \(p\) together (ie. finding a fixed point of a map from pairs \((p, \mu)\) to \((p', \mu')\)). In such a model, \(\mu\) constraints the transition probabilities, \(p'\) is stationary; it’s not clear how one might formalise a derivation of \(\mu'\) from \(p'\) but it seems plausible that there is a canonical way to do it.

reply

by Patrick LaVictoire 1260 days ago | link

Context: At this weekend’s MIRI workshop on logical uncertainty, we were talking about Markus Mueller’s paper on priors over Turing machines and bitstrings (as those seem analogous to priors over logical statements).

Mueller’s original result examined a directed graph structure over prefix computers, where an edge is given by a prefix that causes one computer to simulate another. This gave rise to a Markov chain structure, but Mueller showed in two different ways that this Markov chain was not positive recurrent, and thus that it would not give rise to a non-arbitrary prior.

However, I noted that the Markov chain structure was set up to punish computers that were difficult to simulate, but not to punish computers that were bad at simulating others. Some natural ways to modify the transition probabilities defeated Mueller’s more direct counterexample.

However, in this draft Jacob and Janos showed that no stationary transition matrix (with nonzero coefficients) on that digraph of universal prefix computers could be positive recurrent, or even null recurrent (going beyond Mueller’s result).

reply



NEW LINKS

NEW POSTS

NEW DISCUSSION POSTS

RECENT COMMENTS

[Note: This comment is three
by Ryan Carey on A brief note on factoring out certain variables | 0 likes

There should be a chat icon
by Alex Mennen on Meta: IAFF vs LessWrong | 0 likes

Apparently "You must be
by Jessica Taylor on Meta: IAFF vs LessWrong | 1 like

There is a replacement for
by Alex Mennen on Meta: IAFF vs LessWrong | 1 like

Regarding the physical
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think that we should expect
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

I think I understand your
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

This seems like a hack. The
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

After thinking some more,
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yes, I think that we're
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

My intuition is that it must
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

To first approximation, a
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Actually, I *am* including
by Vadim Kosoy on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

Yeah, when I went back and
by Alex Appel on Optimal and Causal Counterfactual Worlds | 0 likes

> Well, we could give up on
by Jessica Taylor on The Learning-Theoretic AI Alignment Research Agend... | 0 likes

RSS

Privacy & Terms