LessWrong 2.0 Reader

The Padding Argument or Simplicity = Degeneracy

[I learned this argument from Lucius Bushnaq and Matthias Dellago. It is also latent already in Solomonoff's original work]

Consider binary strings of a fixed length $\{0,1{\}}^L$ 

Imagine feeding these strings into some turing machine; we think of strings as codes for a function. Suppose we have a function that can be coded by a short compressed string $s$ of length $k<<L$. That is, the function is computable by a small program. 

Imagine uniformly sampling a random code for $\{0,1{\}}^L$ . What fraction of the codes implement the same function as the string $s$? It's close to $2^{L-k}$. Indeed, given the string $s$ of length $k$  we can 'pad' it to a string of length $L$ by writing the code

"run $s$ skip $t$ "

where $t$ is an arbitrary string of length $L-k-c$ where $c$ is a small constant accounting for the overhead. There are approximately $2^{L-k}$ of such binary strings. If our programming language has a simple skip / commenting out functionality then we expect approximately $2^{L-k}$ codes encoding the same function as $s$. 

I find this truly remarkable: the degeneracy or multiplicity is inversely exponentially proportional to the minimum description length of the function! 

Just by sampling codes uniformly at random we get the Simplicity prior!!

Why do Neural Networks work? Why do polynomials not work?

It is sometimes claimed that neural networks work well because they are 'Universal Approximators'. There are multiple problems with this explanation, see e.g. here [LW · GW] but a very basic problem is that being a universal approximaton is very common. Polynomials are universal approximators!

Many different neural network architectures work. In the limit of large data, compute the difference of different architectures start to vanish and very general scaling laws dominate. This is not the case for polynomials.  

Degeneracy=Simplicity explains why: polynomials are uniquely tied down by their coefficients, so a learning machine that tries to fit polynomials is does not have a 'good' simplicity bias that approximates the Solomonoff prior. 

The lack of degeneracy applies to any set of functions that form an orthogonal basis. This is because the decomposition is unique. So there is no multiplicity and no implicit regularization/ simplicity bias. 

[I learned this elegant argument from Lucius Bushnaq.]

The Singular Learning Theory and Algorithmic Information Theory crossover 

I described the padding argument as an argument not a proof. That's because technically it only gives a lower bound on the number of codes equivalent to the minimal description code. The problem is there are pathological examples where the programming language (e.g. the UTM) hardcodes that all small codes $s$ encode a single function $f$. 

When we take this problem into account the Padding Argument is already in Solomonoff's original work. There is a theorem that states that the Solomonoff prior is equivalent to taking a suitable Universal Turing Machine and feeding in a sequence of (uniformly) random bits and taking the resulting distribution. To account for the pathological examples above everything is asymptotic and up to some constant like all results in algorithmic information theory. This means that like all other results in algorithmic information theory it's unclear whether it is at all relevant in practice.

However, while this gives a correct proof I think this understates the importance of the Padding argument to me. That's because I think in practice we shouldn't expect the UTM to be pathological in this way. In other words, we should heuristically expect the simplicity $K\left(f\right)$ to be basically proportional to the fraction of codes yielding $f$ for a large enough (overparameterized) architecture. 

The bull case for SLT is now: there is a direct equality between algorithmic complexity and the degeneracy. This has always been SLT dogma of course but until I learned about this argument it wasn't so clear to me how direct this connection was. The algorithmic complexity can be usefully approximated by the (local) learning coefficient $\lambda$!

The bull case for algorithmic information: the theory of algorithmic information, Solomonoff induction, AIXI etc is very elegant and in some sense gives answers to fundamental questions we would like to answer. The major problem was that it is both uncomputable and seemingly intractable. Uncomputability is perhaps not such a problem - uncomputability often arises from measure zero highly adversarial examples. But tractability is very problematic. We don't know how tractable compression is, but it's likely untractable. However, the Padding argument suggests that we should heuristically expect the simplicity $K\left(f\right)$ to be basically proportional to the fraction of codes yielding $f$ for a large enough (overparameterized) architecture - in other words it can be measured by the 

Do Neural Networks actually satisfy the Padding argument?

Short answer: No. 

Long answer: Unclear. maybe... sort of... and the difference might itself be very interesting...!

Stay tuned. 

But in this Eiffel Tower example, I’m not sure what is correlating with what

The physical object Eiffel Tower is correlated with itself.
 

However, I think the basic ability of an LLM to correctly complete the sentence “the Eiffel Tower is in the city of…” is not very strong evidence of having the relevant kinds of dispositions.

It is highly predictive of the ability of the LLM to book flights to Paris, when I create an LLM-agent out of it and ask it to book a trip to see the Eiffel Tower.
 

I think the question about whether current AI systems have real goals and beliefs does indeed matter

I dont think we disagree here. To clarify, my belief is there are threat models / solutions that are not affected by whether the AI has 'real' beliefs, and there are other threats/solutions where it does matter.

I think CGP Grey perspective puts more weight on Definition 3.

I actually do not understand the distinction between Definition 2 and Definition 3. Don't need to resolve it here. I've editted post to include my uncertainty on this.

It's a beautiful website. I'm sad to see you go. I'm excited to see you write more.

I have found that they mirror you. If you talk to them like a real person, they will act like a real person. Call them (at least Claude) out on their corporate-speak and cheesy stereotypes in the same way you would a person scared to say what they really think.

Neural Network have a bias towards Highly Decomposable Functions. 

tl;dr Neural networks favor functions that can be "decomposed" into a composition of simple pieces in many ways - "highly decomposable functions". 

Degeneracy = bias under uniform prior

Consider a space $W$ of parameters used to implement functions, where each element $w\in W$ specifies a function$f_w:X\to Y$ via some map $\pi$. Here, the set $W$ is our parameter space, and we can think of each $w$ as representing a specific configuration of the neural network that yields a particular function $f_w$. 

The mapping $\pi$ assigns each point $w\in W$ to a function $f_w$. Due to redundancies and symmetries in parameter space, multiple configurations $w$ might yield the same function, forming what we call a fiber, or the "set of degenerates." of $f$ ${\pi }^{-1}\left(f\right)=\{w\in W|\pi (w)=f_w=f\}$

 This fiber is the set of ways in which the same functional behavior can be achieved by different parameterizations. If we uniformly sample from codes, the degeneracy of a function $f$ counts how likely it is to be sampled. 

The Bias Toward Decomposability

Consider a neural network architecture built out of $l$ layers. Mathematically, we can decompose the parameter space $W$ as a product:

$W=W_1\times W_2\times ...\times W_l,$

where each $W_i$ represents parameters for a particular layer. The function implemented by the network, $f_w$, is then a composition:

$f_w=f_{w_1}\circ f_{w_2}\circ ...\circ f_{w_l}$

For a  function $f$ its degeneracy (or the number of ways to parameterize it) is 

$|{\pi }^{-1}\left(f\right)|={\sum }_{(f_1,...,f_l)\in V\left(f\right)}|{\pi }^{-1}\left(f_1\right)|\cdot |{\pi }^{-1}\left(f_2\right)|\cdot ...\cdot |{\pi }^{-1}\left(f_l\right)|$.

Here, $V\left(f\right)$ is the set of all possible decompositions $f=f_1\circ f_2\circ ...\circ f_l$,  of $f$. 

That means that functions that have many such decompositions are more likely to be sampled. 

In summary, the layered design of neural networks introduces an implicit bias toward highly decomposable functions. 

Them: The point of trade is that there are increasing marginal returns to production and diminishing marginal returns to consumption. We specialize in producing different goods, then trade to consume a diverse set of goods that maximizes utility.

Myself: Suppose there were no production possible, just some cosmic endowment of goods that are gradually consumed until everyone dies. Have we gotten rid of the point of trade?

Them: Well if people had different cosmic endowments then they would still trade to get a more balanced set to consume, due to diminishing marginal returns to consumption.

Myself: What if everyone has exactly the same cosmic endowment? And for good measure there are no diminishing returns, the tenth apple produces as much utility as the first.

Them: Well then there's no trade, what's the point? We just consume our cosmic endowment until we run out and die.

Myself: What if I like oranges more than apples, and you like apples more than oranges?

Them: Oh. I can trade one of my oranges for one of your apples, and we will both be better off. Darn it.

Zvi's latest newsletter has a section on this topic! https://thezvi.substack.com/i/151331494/good-advice

I have thought about the issue that you are outlining here and I can't see any possible solutions. Paired with steganography, that strategy indeed undermines that authors' strategy as far as I can see. I haven't been able to come up with any honeytraps either. This seems like a really big problem.

Am I missing something? Maybe one of the authors of the paper can clarify this issue?

I don't have a strong take haha. I'm just expressing my own uncertainty. 

Here's my best reasoning: Under Bayesian reasoning, a sufficiently small posterior probability would be functionally equivalent to impossibility (for downstream purposes anyway). If models reason in a Bayesian way then we wouldn't expect the deductive and abductive experiments discussed above to be that different (assuming the abductive setting gave the model sufficient certainty over the posterior). 

But I guess this could still be a good indicator of whether models do reason in a Bayesian way. So maybe still worth doing? Haven't thought about it much more than that, so take this w/ a pinch of salt. 

Ah I see ur point. Yh I think that’s a natural next step. Why do you think it not very interesting to investigate? Being able to make very accurate inferences given the evidence at hand seems important for capabilities, including alignment relevant ones?