В предыдущем NeuroNugget я рассказывал о трех работах Дмитрия Ветрова, которые были приняты на ICLR 2019 как повод для обсуждения байесовских методов в глубоком обучении. Сегодня мы рассмотрим еще одну тему, которая довольно широко обсуждалась на ICLR: захватывающее подразделение глубокого обучения, где нейронные сети учатся программировать. ICLR 2019 принял одну статью по индукции программ и три по синтезу программ, и оказалось, что, по сути, все эти методы обучаются на синтетических наборах данных, что является одним из основных направлений нейроматологии. Фактически, одна из рассматриваемых статей ICLR представляет улучшенный способ получения этих данных.

Итак, скоро ли разработчики программного обеспечения останутся без работы? Давайте разберемся. Мы начнем с обзора наиболее интересных идей и работ в данной области, а затем перейдем к более свежим разработкам.

Введение в программу и синтез программы

Исследователи искусственного интеллекта давно хотели научить компьютеры программировать. Еще в 1970 году два исследователя из Стэнфорда, Зохар Манна и Ричард Уолдингер, опубликовали статью под названием На пути к автоматическому синтезу программ. Они сделали это в соответствии с модой того времени, извлекая программу из формального доказательства теоремы, полученного из формальных спецификаций программы. Таким образом, теорема должна была доказываться автоматически. Уолдингер (в сотрудничестве с Ричардом Ли) даже реализовал этот подход, написав программу под названием PROW (от написания программ), которая использовала средство доказательства теорем на основе разрешения и могла выводить программы на LISP вместе с формальным доказательством их правильности.

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

Но сегодня мы будем говорить о другой постановке задачи, иногда называемой Программирование на примерах (PBE), при которой программа создается на основе набора ее результатов выборки и пар ввода-вывода. Дедуктивные подходы, впервые примененные Манной и Вальдингером, живы и хорошо применяются в PBE: например, эта область была в значительной степени инициирована статьей Сумита Гулвани под названием Автоматизация обработки строк в электронных таблицах с использованием примеров ввода-вывода. В этой статье Гулвани определил формальный язык для манипуляций со строками, который, с одной стороны, достаточно выразителен, чтобы быть полезным, а с другой стороны, достаточно простым, чтобы подойти для PBE.

Основная идея обучения программированию модели машинного обучения имеет две формы:

  • ознакомление с программой нацелено на обучение сквозной модели захвату алгоритма;
  • синтез программ пытается научить модель семантике некоторого (обычно довольно ограничительного) языка программирования, чтобы модель могла генерировать программы.

По сути, при вводе программы сеть является программой, тогда как при синтезе программы сеть пишет программу.

Интуитивно синтез программ кажется предпочтительным для реального использования, по крайней мере, потому, что его намного проще протестировать. При вводе программы вы должны постоянно тестировать черный ящик, и даже тогда вы никогда не сможете быть уверены в его правильности; в то время как при синтезе программ вы можете полагаться на широкий спектр методов проверки программ (которые исходят из математической логики), а для программ, о которых мы говорим в современных условиях, проверка почти всегда тривиальна (проблемы редко бывает сложнее простой арифметики). С другой стороны, синтез программ намного сложнее: выписать «смутное понимание» того, что может иметь черный ящик, само по себе звучит как очень сложная проблема.

Естественно, обе проблемы требуют больших наборов данных программ вместе с их парами ввода-вывода. В настоящее время таких больших наборов данных не существует, хотя были предприняты определенные усилия по сбору реальных программ путем извлечения фрагментов из соревнований по программированию и т.п., см. (Zavershynskyi et al., 2018). Но, к счастью, создание синтетических программ и их запуск относительно легко, возможно, даже проще, чем создание синтетических данных для компьютерного зрения. Итак, все современные подходы используют синтетические данные (случайно сгенерированные программы) для обучения своих нейронных компьютеров.

Введение в программу: от машин Тьюринга до сдачи экзамена по математике в старших классах

Все началось с статьи Алекса Грейвса и др. С интригующим названием Нейронные машины Тьюринга. Если вы новичок в информатике (добро пожаловать!), Машина Тьюринга - самая популярная и наиболее широко используемая элементарная формализация компьютера. У него есть лента с бесконечной памятью и головка, которая может перемещаться по ленте и читать и писать символы (см. Больше, например, в Википедии, и не пропустите визуализации). Программы - это правила перехода в наборе конфигураций машины; переход может зависеть от того, какой символ находится под лентой в любой момент, но это все.

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

Идея Graves et al. заключалась в использовании нейронных сетей для работы с внешней памятью, которая, подобно машинам Тьюринга, формализована как «лента» или набор ячеек памяти. Нейронная сеть служит контроллером, сообщая базовой архитектуре, что читать из памяти, что писать в нее и что выводить в среду.

Матрица памяти M t в момент t состоит из N ячеек памяти, каждая из которых содержит вектор размера M, и нейронный контроллер, основанный на взвешивание ячейки памяти w t (своего рода механизм внимания) дает два вектора управления:

  • e t, вектор стирания, который определяет, что удалять из памяти: M ' t (i): = M t-1 (i) (1- w t (i) e i);
  • a t, вектор add, который определяет, что удалять из памяти: M t (i): = M ' t (i) + w t (i) a я

Взвешивание w t производится отдельной частью контроллера (на самом деле это самая интересная часть архитектуры, но не будем сейчас на этом останавливаться).

Для обучения сеть получает входную «ленту» (последовательность символов) и выходную ленту и должна иметь возможность выдавать выходные данные из входа:

Graves et al. показали, что архитектуры NTM, особенно с рекуррентными (основанными на LSTM) конструкциями, способны хорошо обобщать, изучая идеи программ на примерах. Например, NTM, обученный копировать вектор из входа в выход (после того, как будет виден разделитель, поэтому вы должны сохранить последовательность в памяти, прежде чем записывать ее), смог обобщить примеры длиной 20, а затем скопировать последовательности длины до 120. И если вы посмотрите на то, что научился делать NTM, это действительно выглядит как простой алгоритм для управления массивами: сначала считайте входную ячейку за ячейкой в ​​память, затем считайте ячейки памяти одну за другой, копируя их в выходную ленту. Вот карта использования памяти для чтения и записи:

Следующая разработка Graves et al. пришел в 2016 году, когда они разработали НТМ в дифференцируемый нейронный компьютер (DNC), архитектура которого представлена ​​в Nature (Graves et al., 2016). Они добавили временные ссылки, которые могут сказать, в какие ячейки памяти были записаны ранее или позже, и информацию об использовании памяти, которая может информировать контроллер о состоянии памяти более прямым и простым способом. Результирующая архитектура (показанная ниже) позволяет изучать простые программы еще лучше, хотя обучение еще труднее.

Еще один успешный подход к индукции программ - это создание нейронных графических процессоров (Kaiser and Sutskever, 2015). Они отмечают, что нейронные машины Тьюринга трудно обучить из-за их последовательной природы: НТМ пытаются имитировать машины Тьюринга, которые являются обычными последовательными компьютерами с очень ограниченными вычислениями, выполняемыми на каждом шаге. Но программы с большим количеством шагов (т.е. любые реалистичные) очень сложно обучить таким образом. Нейронные модели гораздо больше подходят для вычислений, подобных GPU, относительно короткой последовательности высокопараллельных и мощных вычислений. Архитектура основана на применении последовательности сверточных ГРУ, радикально более простой идее, которую можно сравнить с обычными или многослойными RNN, а не с задействованными архитектурами, такими как нейронная машина Тьюринга. См. ниже:

Несмотря на свою простоту, Neural GPU смогли удивительно хорошо обучаться, научившись выполнять как двоичное сложение, так и даже двоичное умножение - очень сложная проблема! Умножение - это в высшей степени нетривиальный суперлинейный алгоритм, и предыдущие модели не имели с ним абсолютно никакого успеха.

Конечно, было больше разработок в области индукции программ, но давайте перейдем к статье ICLR 2019 исследователей DeepMind Saxton et al. (2019) . В работе под названием Анализ математических способностей нейронных моделей к рассуждению они добавляют еще один уровень косвенности к проблеме индукции программы, предлагая моделям отвечать на математические вопросы, сформулированные на естественном языке. То есть входы могут выглядеть так:

  • Решите 2 (x-5) + 5 = 10-x относительно x
  • Разложите на множители 2x²-x-1.
  • Вычислите -841880142,544 + 411127.
  • Три буквы выбрал без замены из qqqkkklkqkkk. Дайте пробу последовательности qql.
  • Пусть u (n) = -n ** 3 - n ** 2. Пусть e (c) = -2 * c ** 3 + c. Пусть l (j) = -118 * e (j) + 54 * u (j). Какая производная от l (a)?
  • 106033 простое?

Звучит довольно сложно, правда? Например, тестирование простоты - действительно сложный алгоритм, и нельзя ожидать, что рекуррентная нейронная сеть подберет его из примеров. Тем не менее, Saxton et al. показывают, что стандартная современная архитектура, основанная на внимании, Transformer (впервые представленная для машинного перевода в разделе Внимание - это все, что вам нужно и с тех пор широко используется при обработке естественного языка) работает довольно хорошо, давая правдоподобные ответы даже по очень сложным вопросам!

Самым интересным тестом для Transformer стал стандартный экзамен по математике для 16-летних британских школьников. Saxton et al. исключили проблемы с графиками или таблицами и придумали 40 задач, которые охватывают такой же круг проблем, как они тренировались. Обученная модель, основанная на трансформаторе, получила 14/40 правильных вопросов, что эквивалентно ученику E-класса! Итак, пока мы еще не дошли до этого, довольно скоро некоторая коллекция моделей глубокого обучения сможет закончить среднюю школу, по крайней мере, по математике.

Синтез нейронных программ

Хорошо, это была индукция программы, но что, если мы хотим, чтобы модели действительно написали программу? Обычно модели синтеза программ изучают алгоритм на примерах в форме абстрактного синтаксического дерева (AST). AST - это естественное внутреннее представление алгоритмов в виде дерева выполнения, которое создается синтаксическими анализаторами языков программирования. Например, вот пример из Википедии, AST для алгоритма Евклида, который находит наибольший общий делитель:

Первые попытки решить проблему с глубоким обучением использовали усовершенствования известного алгоритма Flash Fill (Gulwani, 2011), предназначенного для вывода алгоритма преобразования строк в виде AST. Flash Fill был разработан исследователем Microsoft Самитом Гулвани и пользуется большей популярностью, чем вы можете себе представить: он устанавливается в каждую копию Microsoft Excel! Flash Fill - это алгоритм, который заполняет ячейки Excel по заданному шаблону (см., Например, здесь).

Parisotto et al. (2016) представили то, что они назвали методом нейросимвольного синтеза программ на основе рекурсивно-обратно-рекурсивных нейронных сетей (R3NN). Проблема, опять же, в том, чтобы создать AST для обработки строк. Вот пример, в котором нам нужно преобразовать примеры слева в программу справа, которая преобразует полное имя в фамилию с первым инициалом:

Модель постепенно строит AST, совместимый с примерами входных данных, путем построения частичных деревьев и расширения их листьев один за другим, пока все листья не будут представлять собой терминалы. Для этого R3NN выполняет два прохода по дереву, сначала вычисляя внутренние представления (вложения) для каждого узла от листьев до корня, а затем вычисляя вероятности действительных расширений во время обратного прохода. Мы не будем вдаваться в подробности, но вот общая идея:

Balog et al. (2016) представляют так называемую модель DeepCoder. Идея здесь в том, что на самом деле проблема синтеза программ может быть решена с помощью методов, основанных на поиске: можно просто попытаться перечислить все возможные AST, отбросив те, которые не соответствуют имеющимся примерам. Естественно, даже для языков с ограниченной предметной областью такой поиск требует больших вычислительных ресурсов, не говоря уже о языках программирования общего назначения, и может выполняться только для очень коротких программ. Но тогда это не похоже на то, что сквозные методы могут найти длинные программы, и есть место для машинного обучения в методах, основанных на поиске: модели могут узнать, какие типы узлов (функций) или древовидных структур более вероятны с учетом доступные примеры и тем самым направляют поиск. В частности, DeepCoder прогнозирует вероятность того, что данная функция появится в коде, учитывая примеры ввода-вывода:

Балог и др. сообщают, что полученная в результате система на основе управляемого поиска ускоряет обычный поиск на несколько порядков и может даже решить некоторые проблемы из реальных соревнований по программированию (отсюда DeepCoder, который напоминает TopCoder).

Поисковое направление было продолжено в (Vijayakumar et al., 2018), другом издании, аффилированном с Microsoft Research. Там авторы возвращаются к области преобразования строк и используют нейронные сети, чтобы конкретно предсказать, как расширить текущий узел, с такой моделью на основе LSTM:

На ICLR 2019 есть три статьи, посвященные синтезу нейронных программ. Chen et al. (2019) из Калифорнийского университета в Беркли предлагает идею управляемого выполнением синтеза: кодируя текущее состояние программы, мы можем выполнять частичные программы и обусловливать следующий шаг синтезатора на представлении промежуточного состояния. С другой стороны, Si et al. (2019) рассмотрим так называемый управляемый синтаксисом синтез, где пространство возможных программ ограничено грамматикой и логической формулой (спецификацией). Формально говоря, это обобщение традиционного программного синтеза, потому что вы можете записать набор данных пар ввода-вывода в виде логической формулы, но на самом деле это совершенно другая проблема. Si et al. используйте обучение с подкреплением для совместного обучения кодировщика и сети политик.

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

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

Синтетические данные для индукции и синтеза программ

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

В одной из рассмотренных выше работ Saxton et al. (2019) пришлось создать набор данных математических задач на естественном языке. Исследователи DeepMind резюмируют свои варианты следующим образом:

Есть два варианта получения математических вопросов: либо из краудсорсинга, либо синтетически. Хотя краудсорсинг имеет то преимущество, что привносит языковое разнообразие, а также разнообразие типов проблем, сложно собрать и проверить такие данные в масштабе. Напротив, процедурная генерация достаточна для наших целей во многих отношениях: она (1) легко предоставляет большее количество обучающих примеров с (2) точным контролем уровней сложности, позволяя (3) анализировать результативность по типам вопросов и ( 4) лучшие гарантии правильности вопроса с (5) потенциалом для более эффективного обучения модели за счет изменения времени, затрачиваемого на каждый модуль, и (6) простотой обобщения тестирования (поскольку можно точно варьировать разные оси сложности в разных типах вопросов) .

Я сам не мог бы выразить это лучше.

Что касается синтеза программ, то здесь, наконец, есть место для обзора еще одной статьи из ICLR 2019. Раньше синтетические данные для нейронного программирования генерировались просто и более или менее случайно. Но исследователи из Калифорнийского университета в Беркли и Google Brain Shin et al. (2019) показывают, что общие алгоритмы генерации синтетических данных, в том числе алгоритм из популярной библиотеки tensor2tensor , имеют смещения, которые не охватывают важные части программного пространства и, таким образом, ухудшают конечный результат. Shin et al. представить новую методологию выборки случайных программ и показать значительные улучшения для двух важных областей: Calculator (который вычисляет результаты арифметических выражений) и Karel (который достигает заданной цели с помощью робота, перемещающегося по двумерной сетке со стенами и маркерами) .

Мы рады видеть новые статьи, в которых создание синтетических данных рассматривается как самостоятельная интересная проблема. Еще более захватывающе видеть, как их принимают на такие крупные мероприятия, как ICLR. Но в статьях, принятых на ICLR 2019, есть еще много интересных идей, так что следите за нашими следующими выпусками!

Сергей Николенко
Главный научный сотрудник, Neuromation