Neural Networks and Solomonoff Induction

Thank you for your insightful comments about our paper. We streamlined the paper thanks to your comments making it more readable and understandable. In particular, we have added to the revised manuscript:

• We added more information on why some of our definitions are needed.

• What we mean by “probability gap”: Let $\mu(x)$ be the probability that an (in)finite sequence starts with $x$. While probability distributions satisfy $\sum_{a\in\mathcal{X}}\mu(xa) = \mu(x)$, semimeasures exhibit probability gaps and only satisfy $\sum_{a\in\mathcal{X}}\mu(xa)\leq\mu(x)$.

• We added what we mean by “data source”, which is simply an object that generates data, and replaced “universally valid approximation to \mu” with a better description of Solomonoff Induction.

• We added a Summary to Section 3 explaining why Propositions 4, 6 and 8 are useful.

• Added more intuition to the Variable Order Markov Source in the main manuscript and in the appendix. See response to reviewer Mfzf for an expanded intuition for the variable-order Markov source.

• We added a sentence explaining how Stack-rnn and Tape-rnn are just RNNs augmented with a stack and tape memory.

• We do have a definition of what we mean by in- and out-of-distribution in the “Evaluation procedure” paragraph of Section 4. In the revised version we emphasize it better.

• We respond to all your questions below.

“[...] Could the authors clarify whether $\pi_\theta$ is also a function of $\tau$, and if not, what are the assumptions on the data that make this statement true?”

$\pi$ has no dependency on $\tau$. In addition, the aim of $\pi$ is to approximate the mixture distribution (over $\sum_\tau p(x | \tau)p(\tau)$). Since this is fairly standard we talked about this in the Background section on Meta-learning.

“Out-of-distribution" appears twice in the main text, including in the qualification of a test distribution.[…] Usually it's really important to mention training versus test distribution details [...] Could you please explain the precise experimental setup including data generation in more detail, in the main text?”

Our definition of in- and out-of-distribution is located on “Evaluation procedure” in Section 4. We highlighted this better. We added more intuition and detail in the main text about the experimental setting.

“Finally, experimentally, it's not clear that the experiments run were anything different than running log likelihood optimization on a mixture of datasets. What's the practical/algorithmic difference or significance in what was run, and what should the takeaways be? If there is no difference, is the significance in the connection to the theoretical results? If so, what is that connection?”

Thanks for the comment, this is exactly the point that we are trying to make. That is, learning from the log-loss on a distribution of tasks leads to an approximation of Solomonoff Induction in a similar fashion as Ortega et al 2019, but only when the “data-mixture” is of a particular form, generated by UTMs, as described by our Section 3. This is exactly the theoretical takeaway. Furthermore, Thm 9 allows for more flexibility in generating this type of data, in which changing the distribution over programs may unblock generating the most important data quicker, which could lead to better performance. We use this fact in our experiments to generate better outputs while maintaining universality. On the experimental side, we show mainly two things: 1) some networks are capable of achieving close to the Bayes-optimal solution for data sources that involve a mixture over programs (in this case Variable-Order Markov Data is generated by mixing trees which can be effectively thought of as programs). 2) Training networks on UTM data exhibits transfer to the other tasks we considered. This is a hint that the UTM data exhibits rich transferable patterns. We believe that designing better UTMs or distribution over programs might lead to even more transfer to more complex domains.

“Second RNN and transformers are turing complete comes from a unrealistic assumptions [...]“

We wholeheartedly agree with the reviewer. Unfortunately, there is no universally accepted universal architecture that practitioners use effectively without unrealistic assumptions. In fact, we believe this is an actual open problem and not the focus of our paper. We are simply concerned with “how good widely used architectures (rnns, lstms transformers etc) are when approximating our data generating sources?”.

“Third when we move to UTM space and show RNN is equivalent to UTM will also work in infinite space and time.” We agree that this could be the case.

“Fourth Solomonoff induction also requires infinite samples [...]” This is an interesting question. We agree that our way of approximating Solomonoff Induction requires infinite samples, and that even if we would have a universal architecture (realizability) which can be easily trained (learnability), one can we can never guarantee that any approach (including ours) is exactly mimicking the universality of a Solomonoff Inductor (since it is uncomputable). However, our theory shows that in the limit this universality should be achieved. We also consider the finite space case in Definition 5 that uses limited resources (bounded time and space). We added a “Limitations” section explaining these nuances. Note that, we are not aware of any practical work that generates samples directly from a UTM according to our Definition 5, and then uses these samples to learn a predictor. So, our way of approximating Solomonoff Induction is novel, as far as we can tell.

“It would benefit if authors can provide insight how transformers and RNNs LM can benefit. For instance, by showing how they work when state space is small vs large, symbols are increased,

We conducted experiments with small and large state spaces (our architectures range from small , medium and large sizes). W.r.t. Alphabet sizes we opted for a fixed alphabet size of 17 for most tasks since this allows comparing transfer performance across tasks as we do in our experiments. When having small alphabet sizes, certain computations might require longer sequences when compared to the same setting with large alphabet sizes, this is because large alphabets in a sense have more bandwidth.

“model is trained on short strings and tested on longer. “ We do have these experiments for all tasks, see Figures 1,2 and 3 right panels. Basically, our conclusions are that LSTMs do very well when tested on longer sequences, whereas transformers fail to do so.

How do attention weights attend in such scenarios, how does LSTM memory adapt to these changes? Do you observe any tape-like or even stack-like behaviour [...]” These are interesting questions, but they fall beyond the scope of this paper, and we refer the reviewer to (Deletang et al 2022) where there is an exploration of such kinds of questions. In summary, given that RNNs cannot solve the tasks that a Stack-RNN or Tape-RNN can solve, this means that they are likely not implementing a stack or a tape under the hood in their internal activations.

We thank the reviewer for the insightful comments and references. We cited all suggested papers, added a limitation section in the Discussion and highlighted better our novel contributions.

“... tensor RNNs with and without memory are shown to be equivalent to TM with finite precision [5,6]...” Thank you for the comment; we will add these references to our manuscript.

“Lemma 10, Corollary 11, Lemma 12-14 [ 1-2] – Theorem 9 in paper shares some similarities …” and “Generalized Solomononff semimeasures definition and Theorem 9 in the paper also share similarity with [3]...”

Thank you for the references. While references 2 and 3 indeed talk about basic and fundamental ideas around Solomonoff Induction they only contain the statement that M is universal, they do not contain any discussion of M^Q (the non uniform case). With respect to reference 1, which we were unaware of, indeed shows similarity to our Thm 9. This means that the conclusions obtained by our Thm 9 are not novel. It seems we have independently discovered similar conclusions to reference 1, though our proof seems to be more self-contained and short when compared to ref 1. We have adapted our claims in the revised version of the manuscript stating the above.

Theorem 3 Linear separation [4] – the paper could benefit by showing… This would definitely be an interesting element to investigate to better understand transformers, however, we think it falls outside the scope of this paper.

“Authors should cite these line of work. Thus it seems the current manuscript is more incremental aligned with the experimental setup in the meta-learning space using modern NNs.” We added all citations since, indeed, they are related to our work. It is true that a major part of our work is to experimentally try to get closer to Solomonoff Induction by meta-learning neural networks (see our general response for an argument why we believe the empirical work is important). We think that this is aligned with ICLRs audience and topics. We also believe the ICLR audience would greatly benefit from thinking more about the links between empirical ML and the strong theory of Solomonoff Induction, which is one of the subgoals of this paper.

“theorem 11 in [7] proves that equivalence between two RNN is undecidable […] Given we know above properties for RNN […] I am not sure Solomonoff induction would help in getting universal capability of the modern day NNs” If the reviewer’s comment refers to the fact that a non-universal model could fail in approximating SI when training on our universal data, we agree that this is the case and it is not a surprise (i.e. non-realizability). If, instead, the reviewer means that this could also happen even if we have universal architectures, we are not so sure about this. The mentioned properties for RNNs (useful citations we add to the revised version), can possibly translate to transformers, however, we note that our work simply takes current neural networks architectures and tests them empirically on various data sources including UTMs. In this work, we are not concerned about how to develop easily-trainable universal architectures as we mention in the introduction, which would be a major breakthrough and a paper on its own. We note that while neural network universality is necessary for full Solomonoff Induction, universality won’t help with the fact that Solomonoff Induction is uncomputable/undecidable. Nevertheless, more compute and bigger universal architectures should help when aiming at approximating Solomonoff Induction (that is computable/decidable for bounded time/space versions). This is the aim of our paper, and in line with our experiments, we show that increasing neural network size leads to better performance and transfer.

We thank the reviewer for the helpful comments and positive feedback. Below we provide detailed responses.

“... I suggest that the authors provide the necessary context to aid unfamiliar readers…” :
We rephrased the description of Semimeasures to be more accessible to readers.. We also provide further explanations about Solomonoff Induction to be more easily understood by ML practitioners. We emphasize in the introduction that the focus of the paper is not to develop a novel architecture but to study more empirical versions of Solomonoff Induction using modern neural networks.

“... The experimental setup is missing some details, e.g., how many training examples are there?..”: In the Neural Predictors section we describe how we used 500k iterations with a batch size of 128. Since we use data generators (not fixed datasets) we effectively generated 500k*128 sequences of various lengths depending on the experiments. We are happy to clarify other details that the reviewer thinks are missing.

“I don't really have good intuition about how varied the prediction tasks are. Can you provide a bit more intuition here?”: We added intuitions in the revised version of the manuscript for all tasks, see below.

• The Chomsky tasks are tasks that manipulate strings, for example, reversing an input string, or computing modular arithmetic operations. More details n our Appendix D3.

• For the UTM (BrainF*ck/BrainPhoque) tasks we generate random programs (that can effectively encode any structured sequence generation process) and run them in our UTM and get the outputs. For example, in principle a program could generate the image of a cow, a chess program, or the books of Shakespeare. But of course these programs are extremely unlikely to be sampled. In practice, the generated programs are short and their outputs bear more resemblance with regular or context-free languages, which explains partly why transfer to the Chomsky tasks is possible at all. See Figure 5 in the Appendix for some examples.

• A Markov model of order k sequentially assigns probabilities to a string of characters by looking, at step t in the sequence, at the suffix string from t-k to t. This suffix is used to lookup the model parameters to make a prediction of the next character. A variable Markov model (VMM) is a Markov model where the value of k can vary depending on the suffix. A VMM makes its prediction using a suffix tree. CTW is a variable Markov model predictor that performs Bayesian inference efficiently over all possible suffix trees as it reads and predicts the sequence. Additionally, any predictor (such as CTW) can be used as a generator, by sampling sequentially from the predictive probabilities.
  Lastly, the task on variable-order Markov sources considers data generated from tree structures. For example, given the binary tree

         Root
  0/                \1
Leaf_0       Node
		0/         \1
        Leaf_10       Leaf_11

And given the history of data “011“ (where 0 is the first observed datum and 1 is the last one) the next sample uses Leaf_11 (because the last two data points in history were 11) to draw the next datum using a sample from a Beta distribution with parameter Leaf_11. Say we sample a 0, thus history is then transformed into “0110” and Leaf_10 will be used to sample the next datum (because now the last two datapoints that conform to a leaf are 10), and so forth. This way of generating data is very general and can produce many interesting patterns ranging from simple regular patterns like 01010101 or more complex ones that can have stochastic samples in it. Larger trees can encode very complex patterns indeed. For more information about the way we generate this data you can check the Appendix D2.

… Can you talk a bit more about data sizes, and why the results are or are not expected?” We train for 500k iterations with batches of 128 sequences of length 256 in most experiments. That means we use around 16 Billion “tokens” to train our models. Large language models are trained using datasets sizes of the order of Trillions of tokens e.g. Mistral 7B uses about 8 Trillion tokens. Given this context, our models could still be trained further if we make them bigger, specially in the case of UTM data where we can generate at will any number of sequences. Our results on Variable Order Markov Sources are novel and somewhat reassuring since no previous work has shown the capabilities of neural networks to reach Bayes-optimal performance on such type of algorithmic universal data. The results on UTM data are a positive surprise since they demonstrate our hypothesis that practical UTM data contains useful transferable patterns to improve performance on other tasks. What we expect is that using better UTMs and training on the order of Trillions of tokens could significantly improve transfer to more “real-world” tasks including vision and language.