====== Neuro-symbolic program synthesis ======

Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, Pushmeet Kohli. 2017. Neuro-symbolic program synthesis. ICLR 2017. https://arxiv.org/abs/1611.01855

===== Вступление =====
За последние годы методы генерации программ при помощи нейрометодов стали использоваться практически повсеместно. Однако у всех этих методов пока есть несколько важных недостатков: а) процесс обучения и подбора сети требует много времени и ресурсов, б) каждую отдельную задачу приходится решать отдельно, подбирая для неё архитектуру и приемы, в) очень часто непонятно, как оценивать качество решения. В этой статье описывается новейшая техника для избавления от вышеупомянутых проблем: Neuro-symbolic program synthesis. Метод будет базироваться на двух модулях: cross correlation I/O network и Recursive-Reverse-Recursive Neural Network (R3NN).
===== Изложение основной части =====

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

Для начала сформулируем задачу:

Пусть нам дан язык L и набора данных {(i1, o1), (i2, o2), ...}. От нас требуется спроектировать алгоритм A, который бы по этим данным вернул бы программу P из L, которая бы корректно преобразовывала бы входные данные в выходные.
Язык L мы будем представлять в виде набора правил контекстно независимой грамматики.

Обзор подхода:

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

Как уже было сказано, язык может быть представлен в виде контекстно свободной грамматики. Для наивной генерации программ нам было бы достаточно начать со стартовой вершины S и начать случайно ходить по правилам в следующие нетерминальные вершины, пока не придем в терминальную. Однако мы хотим обучить генератор, который бы построил соответствие между нетерминальными вершинами и вероятностями, с которыми они встречаются среди частичных выводов (в правилах языка L). В дальнейшем эти вероятности будут использоваться для нахождения нужного пути в дереве вывода.

Наш генератор будет использовать R3NN для кодирования дерева частичных выводов в языке L. Дерево будет строиться постепенно (точнее рекурсивно, что следует из названия сети). Каждая вершина дерева должна содержать информацию про все остальные вершины. Также наш генератор должен сопоставить векторное представление для каждого символа и каждого правила из языка. По данному дереву генератор строит векторное представление для его листьев, затем выполняя рекурсивный проход по дереву, пишем в корень информацию о всех вершинах. (Это как раз объясняет Reverse-Recursive часть названия сети).

{{:mdd:снимок_экрана_2017-12-25_в_12.09.02.png?600|}}

Наш генеративный процесс зависит от набора данных, чтобы в процессе сгенерировать программу, которая бы этим данным соответствовала бы. В статье экспериментируют с несколькими типами энкодеров, такими как LSTM (совмещается из скрытых векторов двух двунаправленных LSTM для входных и. выходных данных), а также Кросс-корреляционный энкодер, вычисляющий корреляцию между представлением, полученным в результате LSTM и входными данными. Эти данные потом используют как дополнительный набор данных для R3NN.
===== Заключение =====

В статье приводится подробный анализ нового метода Neuro-Symbolic Programm Synthesis, который позволяет создавать программу только на основе входных-выходных данных. Для того, чтобы это сделать, R3NN расширяет частичное дерево грамматики языка (на котором должна быть написана будущая программа) до полного дерева грамматики. Как показали эксперименты в статье, такой подход находит эффективные решения даже тогда, когда нужная программа не встречалась в процессе обучения.

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