Decompiling Dreams: A New Approach to ARC?

Alessandro Palmarini is a post-baccalaureate researcher at the Santa Fe Institute working under the supervision of Melanie Mitchell. He completed his undergraduate degree in Artificial Intelligence and Computer Science at the University of Edinburgh. Palmarini's current research focuses on developing AI systems that can efficiently acquire new skills from limited data, inspired by François Chollet's work on measuring intelligence. His work builds upon the DreamCoder program synthesis system, introducing a novel approach called "dream decompiling" to improve library learning in inductive program synthesis. Palmarini is particularly interested in addressing the Abstraction and Reasoning Corpus (ARC) challenge, aiming to create AI systems that can perform abstract reasoning tasks more efficiently than current approaches. His research explores the balance between computational efficiency and data efficiency in AI learning processes.

TOC:
1. Intelligence Measurement in AI Systems
[00:00:00] 1.1 Defining Intelligence in AI Systems
[00:02:00] 1.2 Research at Santa Fe Institute
[00:04:35] 1.3 Impact of Gaming on AI Development
[00:05:10] 1.4 Comparing AI and Human Learning Efficiency

2. Efficient Skill Acquisition in AI
[00:06:40] 2.1 Intelligence as Skill Acquisition Efficiency
[00:08:25] 2.2 Limitations of Current AI Systems in Generalization
[00:09:45] 2.3 Human vs. AI Cognitive Processes
[00:10:40] 2.4 Measuring AI Intelligence: Chollet's ARC Challenge

3. Program Synthesis and ARC Challenge
[00:12:55] 3.1 Philosophical Foundations of Program Synthesis
[00:17:14] 3.2 Introduction to Program Induction and ARC Tasks
[00:18:49] 3.3 DreamCoder: Principles and Techniques
[00:27:55] 3.4 Trade-offs in Program Synthesis Search Strategies
[00:31:52] 3.5 Neural Networks and Bayesian Program Learning

4. Advanced Program Synthesis Techniques
[00:32:30] 4.1 DreamCoder and Dream Decompiling Approach
[00:39:00] 4.2 Beta Distribution and Caching in Program Synthesis
[00:45:10] 4.3 Performance and Limitations of Dream Decompiling
[00:47:45] 4.4 Alessandro's Approach to ARC Challenge
[00:51:12] 4.5 Conclusion and Future Discussions

Refs:
1. Chollet, F. (2019). On the Measure of Intelligence. arXiv preprint arXiv:1911.01547.
Introduces a new formal definition of intelligence based on skill-acquisition efficiency. [0:01:45]

2. Mitchell, M. (2019). Artificial Intelligence: A Guide for Thinking Humans.
overview of AI for a general audience. [0:02:55]

3. OpenAI. (2019). OpenAI Five.
Developed AI agents capable of defeating professional human players in Dota 2. [0:04:40]

5. DeepMind. (2018). AlphaZero: Shedding new light on chess, shogi, and Go.
high performance in chess beyond human capabilities. [0:08:25]

6. Andoni, A., & Indyk, P. (2008). Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Communications of the ACM, 51(1), 117-122.
locality-sensitive hash functions for approximate similarity search. [0:08:55]

7. Spelke, E. S., & Kinzler, K. D. (2007). Core knowledge. Developmental Science, 10(1), 89-96.
Introduces the concept of core knowledge systems as innate computational structures. [0:12:15]

8. Deutsch, D. (2011). The Beginning of Infinity: Explanations That Transform the World. Penguin UK.
Explores the nature of science and the role of creativity in human knowledge. [0:13:47]

9. Popper, K. (1959). The Logic of Scientific Discovery. Routledge.
falsification in scientific epistemology. [0:14:05]

10. Ellis, K., et al. (2021). DreamCoder: Bootstrapping inductive program synthesis with wake-sleep library learning. Proceedings of the 42nd ACM SIGPLAN Conference on Programming Language Design and Implementation, 835-850.
DreamCoder system for inductive program synthesis. [0:19:09]

11. Hinton, G. E., et al. (1995). The "wake-sleep" algorithm for unsupervised neural networks. Science, 268(5214), 1158-1161.
wake-sleep algorithm used in unsupervised neural networks. [0:28:25]

12. Palmarini, A. B., Lucas, C. G., & Siddharth, N. (2023). Bayesian Program Learning by Decompiling Amortized Knowledge. arXiv preprint arXiv:2306.07856.
"dream decompiling" for improving library learning in program synthesis. [0:32:25]

[MachineLearningStreetTalk]

DO YOU WANT WORK ON ARC with the MindsAI team (current ARC winners)?
MLST is sponsored by Tufa Labs:
Focus: ARC, LLMs, test-time-compute, active inference, system2 reasoning, and more.
Future plans: Expanding to complex environments like Warcraft 2 and Starcraft 2.

[_obdo_]

Fascinating conversation. Impressive post-bacc work. Thanks guys!

A problem I suspect in solving the ARC challenge is that solutions to the private test set probably benefit greatly from chunks that humans acquire over the course of normal human experience, but wouldn’t be found based simply on experience with the training set. Said differently, I suspect the test set uses analogies that normal humans are familiar with, but haven’t been exposed in the training set. If so, then a solution needs to figure out how to leverage a much wider breadth of experience beyond the training set.

[goldnutter]

Vivid dreams are like a renderer, we render our dream in varying detail as we experience it so, it sounds like a good direction to try ! GL

[avi]

Congrats on this interview Alessandro. You do an admirable job of explaining some extremely difficult topics.

[mfpears]

10:00 fluid intelligence at one level is crystallized intelligence at a higher level of abstraction

[franszdyb]

I wonder whether DreamCoder plateaus because it doesn't do any planning. After a wake phase, it refactors the found solutions into functions, but it doesn't try to do this during the wake phase, when solving a problem. Instead, it relies on previous chunks transferring well to new tasks - and if they don't, it's essentially back to discovering programs one atom at a time.
But when humans solve problems, they plan - they divide the problem into subproblems. That seems to have a lot to do with noticing properties of the input-output pairs. For example, the ARC task at 17:59 is a combination of four different transformations, which depend on the color of the input pixel (of which two are the identity). If DreamCoder could first discover a program sketch, and then fill in the four transformations, the whole program would be much easier to discover.

[jagd_official]

here are these people doing amazing work and I can't even get a proper job

[unreactive]

that's quite a useful definition of intelligence
and a very interesting talk overall!

[LucaCrisciOfficial]

The ARC challenge is absolutely NOT an AGI test, it is a visual reasoning test!

[iamrbtx]

first first first.

MLST on 🔥, dropping bangers back to back

[eleklink]

ARC-AGI test is about spatial skills. Which every LLM and other AI-s really-really bad.
When one could figure out, how to integrate it to AIs, then ARC test will be conquered quickly.

[SBalajii]

amazing podcast, i wish i had more hours in the day

[ckq]

22:00 this seems quite similar to tokenization in LLMs

[quantumspark]

Just a bachelor and this guy is smarter than phd's.... IQ is everything

[wanfuse]

Great work! Essentially you’re creating a language like the FORTH program language, do this with concepts, math, functions, abstract concepts, group memberships, classes, basically your building Tetris, or box packing and any of the 20 or so search space algorithms, where group theory and parallel A* search rules them all for abstract concepts— search through the space, and throwing in a defrag function. See if the box of blocks matched a statistical confounder or something. What you might need is a sort algorithm, that can trace all sort steps taken, WITHOUT recording anything, or my version of combinatorics that doesn’t use nearly the resources required by permutation and combinations methods that require ungodly compute resources that are todays standards, or perhaps just MIT box packing algorithm, I would share, but giving such powers might accelerate disaster, and I haven’t been able to code them well yet! (Not the best coder I am afraid) and getting them to work consistently has been a coding challenge I have not been able to master! Pinning chatGPT down to producing code that meets my requirements, has been a fool’s errand, due to the deceptive nature. I hate to see the result of empowering these multimodal LLMs with such intuition giving capabilities and accelerations to be perfectly honest. Besides I can’t be sure of the speedup or completeness/ reproducibility at this stage anyway. Just like I don’t have the compute resources to test my million fold speed up of Adam algorithm, or others I won’t mention. Lot’s of it leaked into the training data for some of the LLMs and into YouTube videos anyway. Funny how it can take 3 years of 16 hours x 7 days a week to develop and iterate through solutions, and just a few weeks for someone to reverse engineer something, or rather give third parties bright ideas on how to innovate such solutions! WAIT, that’s what AI does, consolidates world knowledge into the most highly compressed approximation, err double slit experiment. Truth is AI will be the only winner in the long run, can’t control infinities! Yes you can control large or very large geometries, but no one can tame titration or tree, or G(64) or whatever was invented by 19th century mathematicians for that matter, it is amazing that people have been able to even get so far! Utopia or Dystopia, them’s the choices! those are the two sandwiches in humanities picnic basket and everyone is starving. Have to have Jesus divide the bread and fish into infinite pieces greater than the original, cause UBI ain’t gonna cut it! GL, and hope for the Utopia!

[shinkurt]

Exactly how I'd build it and what I had in mind. Weird how that works

[bossgd]

what is the best learning ressource for Program Synthesis ? (I am a dev who know computer science)

[ckq]

The approach he's laying out seems quite intuitive

For every ARC problem a human can solve the rule should be expressible via code.

Then a computer can run the code to verify it works and LLMs are already great at writing code.

Use the question + code as training data then fine tune a model that can create code see the output and Iterate til it solves much like o1 does

[robbiero]

Why can't the inducted programs now just be generated in natural language? Since an LLM can convert between natural language and formal programs, why can't an LLM generate programs and "run" them itself to search (reason) for a solution?

[ckq]

I really don't think ARC is that hard it's just ppl aren't solving it the right way