Ссылка на статью: 2303.06018.pdf (arxiv.org)

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

Ключевые идеи

  • В документе предлагается новая структура под названием Hierarchical Neural Program Synthesizer (HNPS) для автоматического синтеза длинных сложных программ из высокоуровневых спецификаций, таких как примеры ввода/вывода.
  • Большинство существующих методов синтеза нейронных программ генерируют программы токен за токеном. Это может затруднить масштабирование до более длинных и сложных программ.
  • Вместо этого HNPS использует иерархический подход — он учится составлять короткие простые программы, чтобы формировать более длинные и сложные программы.
  • Во-первых, пространство для встраивания задачи и программный декодер обучаются на наборе данных коротких программ и примерах ввода/вывода. Это позволяет декодировать встраивание задачи в короткую программу.
  • Затем модуль компоновщика программ обучается принимать спецификацию и создавать последовательность вложений задач, которые декодируются в короткие программы и составляются для формирования окончательной длинной программы.
  • Используются две потери: потеря токена программы, чтобы максимизировать вероятность токенов наземной истины, и потеря встраивания программы, чтобы сопоставить вложения композитора с вложениями наземной истины.
  • Эксперименты проводятся в области преобразования строк, где спецификациями являются пары строк ввода/вывода. HNPS значительно превосходит базовые показатели по длинным программам (до 63 токенов).
  • Исследования абляции подтверждают иерархический дизайн и преимущества составленного программного набора данных для обеспечения промежуточного наблюдения. Программа, включающая потери, наиболее полезна, когда обучающие данные ограничены.

ГНПС

Разучивание задачи встраивания пространства

Первым шагом в HNPS является изучение задачи встраивания пространства с использованием набора данных коротких простых программ. Это делается путем выборки программ из грамматики DSL и создания примеров ввода/вывода для каждой программы. Затем на этом наборе данных обучаются кодировщик задач и декодер программ. Кодер задач использует GRU для кодирования строк ввода/вывода в вектор внедрения. Программный декодер использует GRU, обусловленный внедрением, для создания программных токенов. Кодер задачи и программный декодер обучаются вместе, используя кросс-энтропийную потерю токена, чтобы реконструировать наземные программы. Это позволяет сопоставлять примеры ввода/вывода с пространством встраивания задачи и декодировать вложения в программы.

Составление набора данных длинной программы

Чтобы обеспечить иерархический синтез программ, набор данных длинных программ составляется путем случайного объединения последовательностей коротких программ. Примеры ввода/вывода генерируются для каждой составленной длинной программы. Обученный кодировщик задач из предыдущего шага затем используется для извлечения вложений задач для каждой короткой программы в длинных программах.

Иерархический программный синтез

Модуль иерархического синтеза состоит из трех основных компонентов. Составной кодировщик задач инициализирует веса из обученного кодировщика задач. Составитель программы использует GRU для последовательного прогнозирования встраивания задач на основе кодировки ввода/вывода. Декодер предварительно обученной программы декодирует каждое встраивание в короткие программы. Короткие программы складываются в финальную длинную программу. Используются две потери — потеря токена, чтобы максимизировать вероятность токенов наземной истины, и потеря встраивания, чтобы сопоставить предсказанные вложения с вложениями короткой программы наземной истины.

Таким образом, ключевыми идеями являются изучение пространства встраивания в коротких программах, составление длинных программ для иерархического контроля и использование модулей компоновщика/декодера с двумя потерями для реализации иерархической генерации. Компоненты работают вместе, позволяя масштабировать длинные и сложные программы.

Эксперименты

HNPS значительно превзошла базовые показатели в длинных программах, достигнув точности 9,7 % в программах с 40–55 токенами по сравнению с 0–2 % для базовых показателей. Метод восходящего поиска достиг точности всего 0,13% в программах с 25–40 токенами. Удаление HNPS без иерархической архитектуры работало намного хуже в программах с 55–70 токенами. Удаление потерь при встраивании больше навредило HNPS, когда обучающие данные были ограничены. Анализ показал, что изученное пространство встраивания хорошо улавливает семантику и важные токены. HNPS допустил меньше критических ошибок токена, чем синтез токена за токеном. HNPS также лучше обобщала от поезда к тесту, чем абляции.

Таким образом, результаты показали, что HNPS может достичь гораздо более высокой точности в длинных программах с использованием до 63 токенов по сравнению с другими методами. Было показано, что иерархический подход и составленный набор данных с промежуточным наблюдением являются важными компонентами. Результаты выявили преимущества HNPS по сравнению с неиерархическим программным синтезом токена за токеном.