А что на противоположном фланге в синтезе программ?

Помимо AlphaDev, в которой ключевой компонентой является нейросеть, оптимизирующая поиск, существуют и принципиально другие направления исследований.

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

Данное направление не стоит на месте, и в начале этого года вышла статья Top-Down Synthesis for Library Learning. Алгоритм из неё работает быстрее, чем DreamCoder, на несколько порядков. Основное нововведение состоит в альтернативном подходе к тому, как, имея датасет готовых программ, синтезировать новые операции?

DreamCoder использовал подход, близкий к полному перебору всевозможных абстракций. Авторы нового алгоритма Stitch формулируют задачу как поиск абстракций по дереву всевозможных вариантов. При поиске максимизируется "полезность" абстракции, измеряемая тем, насколько сократится длина всего датасета программ при её использовании. В перебор добавляют оптимизации из области методов решения NP-задач (например, Branch-and-bound). Этого хватает, чтобы совершить прорыв в скорости построения новых абстракций, к тому же более высокого качества.

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

Stitch способен решать куда более сложные задачи, чем DreamCoder, но мы всё ещё далеки от уровня человека. Однако, постановка решаемой задачи очень напоминает сферу доказательств теорем в математике. Ждём, когда это всё смогут масштабировать! А я буду держать вас в курсе.

@knowledge_accumulator