昨日
LW - A Solomonoff Inductor Walks Into a Bar: Schelling Points for Communication by johnswentworth
Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: A Solomonoff Inductor Walks Into a Bar: Schelling Points for Communication, published by johnswentworth on July 26, 2024 on LessWrong.
A Solomonoff inductor walks into a bar in a foreign land. (Stop me if you've heard this one before.) The bartender, who is also a Solomonoff inductor, asks "What'll it be?". The customer looks around at what the other patrons are having, points to an unfamiliar drink, and says "One of those, please.". The bartender points to a drawing of the same drink on a menu, and says "One of those?". The customer replies "Yes, one of those.".
The bartender then delivers a drink, and it matches what the first inductor expected.
What's up with that?
The puzzle, here, is that the two Solomonoff inductors seemingly agree on a categorization - i.e. which things count as the Unnamed Kind Of Drink, and which things don't, with at least enough agreement that the customer's drink-type matches the customer's expectations.
And the two inductors reach that agreement without learning the category from huge amounts of labeled data - one inductor points at an instance, another inductor points at another instance, and then the first inductor gets the kind of drink it expected. Why (and when) are the two inductors able to coordinate on roughly the same categorization?
Most existing work on Solomonoff inductors, Kolmogorov complexity, or minimum description length can't say much about this sort of thing. The problem is that the customer/bartender story is all about the internal structure of the minimum description - the (possibly implicit) "categories" which the two inductors use inside of their minimal descriptions in order to compress their raw data.
The theory of minimum description length typically treats programs as black boxes, and doesn't attempt to talk about their internal structure.
In this post, we'll show one potential way to solve the puzzle - one potential way for two minimum-description-length-based minds to coordinate on a categorization.
Main Tool: Natural Latents for Minimum Description Length
Fundamental Theorem
Here's the main foundational theorem we'll use. (Just the statement for now, more later.)
We have a set of n data points (binary strings) {xi}, and a Turing machine TM. Suppose we find some programs/strings Λ,{ϕi},Λ',{ϕ'i} such that:
Mediation: (Λ,ϕ1,…,ϕn) is an approximately-shortest string such that (TM(Λ,ϕi) = xi for all i)
Redundancy: For all i, (Λ',ϕ'i) is an approximately-shortest string such that TM(Λ',ϕ'i) = xi.[1]
Then: the K-complexity of Λ' given Λ,K(Λ'|Λ), is approximately zero - in other words, Λ' is approximately determined by Λ, in a K-complexity sense.
(As a preview: later we'll assume that both Λ and Λ' satisfy both conditions, so both K(Λ'|Λ) and K(Λ|Λ') are approximately zero. In that case, Λ and Λ' are "approximately isomorphic" in the sense that either can be computed from the other by a short program.
We'll eventually tackle the customer/bartender puzzle from the start of this post by suggesting that Λ and Λ' each encode a summary of things in one category according to one inductor, so the theorem then says that their category summaries are "approximately isomorphic".)
The Intuition
What does this theorem mean intuitively?
Let's start with the first condition: (Λ,ϕ1,…,ϕn) is an approximately-shortest string such that (TM(Λ,ϕi) = xi for all i). Notice that there's a somewhat-trivial way to satisfy that condition: take Λ to be a minimal description of the whole dataset {xi}, take ϕi=i, and then add a little bit of code to Λ to pick out the datapoint at index ϕi[2]. So TM(Λ,ϕi) computes all of {xi} from Λ, then picks out index i.
Now, that might not be the only approximately-minimal description (though it does imply that whatever approximately-minimal Λ,ϕ we do use is approximately a minimal description for all of x). ...
