DreamCoder [2020] - воплощение моей мечты

Алгоритмическое решение задач сводится к нахождению программы (последовательности операций), которая удовлетворяет какому-то критерию решения. Это нужно при поиске доказательства теоремы, кодогенерации для решения задач, ARC-тесте на IQ и т.д.

Когда мы конструируем какой-то Domain Specific Language - набор элементарных команд, который мы используем для перебора, мы должны учитывать 2 ограничения:
1) Чем базовые команды сложнее, тем меньший класс задач мы можем решить с помощью них
2) Чем базовые команды проще, тем длиннее итоговая программа
В результате, мы сильно ограничены в разнообразии или сложности решаемых задач.

Я давно думал о том, как это можно обойти, и внезапно оказалось, что эти идеи были реализованы в статье DreamCoder.

Предположим, что мы работаем с каким-то классом задач X.

1) Определим набор самых базовых операций в домене X.
2) Будем сэмплировать задачи класса X и пытаться собрать программу из нашего набора для этих задач. Для каких-то хотя бы сможем собрать.
3) Анализируя успешные программы, находим часто встречающиеся комбинации операций и составляем из них новую операцию, добавляя в наш набор.
4) Обучаем нейросеть, которая будет направлять наш перебор программ.

Я верю в силу подобного фреймворка, и я с нетерпением жду, когда его смогут применить к более мощным классам задач, про которые я упоминал в начале поста. Я думаю, что это тот подход, который позволит получить в них сверхчеловеческую производительность.
Часовой обзор статьи от Янника.

@knowledge_accumulator