RobustFill: Neural Program Learning under Noisy I/O

Devlin, Jacob, et al. 2017. RobustFill: Neural Program Learning under Noisy I/O. arXiv preprint arXiv:1703.07469 (March 2017)

Задача генерации программ одна из самых старых задач в машинном обучении. Классический подход требовал вручную задавать спецификацию, что было делать сложнее, чем написать саму программу. Современные методы генерации программ опираются на примеры входных и выходных данных. В последнее время набирают популярность статистические методы, в частности нейронные сети. В этой работе будет рассмотрено два подхода: генерация программы и генерация непосредственно выходных данных (индуктивный подход).

Есть множество пар входных и выходных строк <latex>(I_1, O_1), \dots, (I_n, O_n)</latex>. Они разбиваются на наблюдаемые примеры и контрольные.

В подходе генерации программ по наблюдаемым примерам посимвольно создается программа P. Она называется консистентной, если выдает правильные результаты на всех наблюдаемых примерах, а если корректные результаты получены и на контрольных примерах, то программа считается правильной.

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

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

Выборка для обучения была создана следующим образом. Вначале программы случайно генерировались из DSL с ограничением на длину. После этого выбирались случайные корректные для данной программы входные строки. После применения к ним программы, были получены выходные строки. Выборка для тестирования состоит из настоящих примеров из Excel таблиц, FlashFillTest.

Для начала рассмотрим подход генерации программ. Вначале для каждой наблюдаемой пары генерируется своя программа. Для этого использовались разные архитектуры, изображенные на рисунке. Каждый прямоугольник это LSTM, пунктирные стрелки показывают, куда смотрит эта ячейка в рамках attention. Далее программы для разных наблюдаемых пар объединяются с помощью посимвольного пулинга. И в конечном итоге вероятность поставить на данное место в программе данный символ определяется с помощью softmax.

На тесте для генерации программы используется beam search. Причем в нашем случае не просто берется лучшая программа из луча, а лучшая из консистентных. Так же рассматривается алгоритм DP-Beam, который хорошо работает, благодаря обилию конкатенаций в DSL.

В индуктивном подходе использовалась та же архитектура только с двумя изменениями: вместо программы генерируются выходная строка, и добавляется дополнительный LSTM, обрабатывающий входную строку.

Измерялось какая доля программ правильные. Лучше всего себя показала архитектура генерирующая программу с Attention-C. При использовании DP-Beam она достигнула 92%, как и алгоритм FlashFill с подобранными вручную отсечениями и эвристиками, а лучшая нейросетевая модель в этой области показывала лишь 34%. Индуктивный же подход хорошо себя показывает если измерять долю верно угаданных контрольных примеров. Также все представленные модели робастные, в отличие от FlashFill.

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

Саму статью можно прочитать здесь.