Реферат: Г. М. Сергиевский

Г. М. СЕРГИЕВСКИЙ

Национальный исследовательский ядерный университет «МИФИ»

latemmephi@yandex.ru


МОДЕЛИРОВАНИЕ ЭТАПОВ ОБУЧЕНИЯ СЛОЖНЫМ СИМВОЛЬНЫМ ПРЕОБРАЗОВАНИЯМ НА ОСНОВЕ КОНЦЕПЦИИ ИНДУКТИВНОГО СИНТЕЗА ПРОГРАММ


Обсуждается, предложенная автором, концепция обучения на основе методов индуктивного синтеза программ - TunISyS. В соответствии с концепцией система синтеза разбивается на базовую и прикладную части. Базовая часть, выполняющая собственно синтез и независящая от предметной области, использует в качестве спецификации синтезируемой программы ее «протоколы вычислений». Прикладная часть, зависящая от предметной области, реализуется в форме прикладного транслятора с входного языка описания примеров в язык представления протоколов вычислений. Обсуждается модель выполнения отдельных этапов прикладной трансляции. Модель основана на представлении процесса формирования знаний как, последовательности трансформаций обучающих примеров, завершающим этапом которой является формирование протоколов вычислений.


Введение

Целью настоящего исследования является создание программно реализованной модели обучения с учителем, способной с помощью набора примеров обучиться сложным символьным преобразованиям. При разработке модели автор исходил из необходимости удовлетворения двух требований. Первое требование носит утилитарный характер и состоит в обеспечении в дальнейшем возможности создании на основе модели программного продукта, который можно было бы использовать для решения практических задач. Этот продукт будет представлять собой реализацию метаязыка SEML, программирование на котором может выполняться не только в традиционной форме написания определений процедур, но также в форме описания только примеров работы таких процедур. Второе требование состоит в построении модели таким образом, чтобы бы ее можно было бы использовать для моделирования когнитивных процессов у лабораторных животных и человека. И, хотя предлагаемая модель определена на основе программистских примитивов (и не может поэтому претендовать на описание когнитивных процессов в терминах примитивов «биологического компьютера»), автор надеется, что она может быть полезна и для решения вышеупомянутой задачи.


^ Индуктивное обучение


Вообще проблема индуктивного обучения (понимаемого в данном контексте в широком смысле – как построение общих моделей по частным примерам) не смотря на ее чрезвычайную важность, исследована достаточно слабо и преимущественно только в постановке «распознавания образов». Исследования же обучения «процедурным знаниям» вообще находятся в начальной стадии. Сегодня в этом направлении исследования проводятся в двух парадигмах: нейросетевой (основная масса работ, использующих различные расширения базовых сетевых моделей [1, 2]) и в парадигме индуктивного программирования (отдельные работы [3]). Справедливости ради, нужно отметить, что как в первом, так и во втором направлениях пока не получено существенных результатов. По мнению автора, во втором направлении главная проблема состоит в ограниченности исходной постановки задачи [4, 5], в соответствии с которой задача индуктивного программирования ставится как задача синтеза программы по множеству пар {вход, выход}, при условии, что входные и соответствующие им выходные значения принадлежат алгебраическому типу данных (обычно, спискам). В этой постановке имеется два основных недостатка: не определен класс программ, среди которых ищется решение, и в применяемой спецификации содержится слишком мало информации для выполнения синтеза с помощью достаточно понятного алгоритма.

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


^ Протокол вычислений


Понятие протокола (траектории, истории) вычислений разными авторами понимается по разному. Из-за ограниченности объема опустим аналитический обзор данной темы и приведем сразу основные элементы предлагаемого подхода. Как известно, программу на процедурном языке (именно о таких программах будет идти речь) можно изобразить в виде блок-схемы. Перефразируя немного традиционное определение, определим блок-схему программы как граф, имеющий: одну начальную вершину, одну заключительную вершину, произвольное число операторных вершин с одним входом и одним выходом и произвольное число вершин-распознавателей с одним входом и двумя выходами (в наших целях удобнее сразу допустить несколько выходов). Операторные вершины соответствуют действиям, совершаемым в ходе вычислений (присваиваниям, вызовам других программ, командам для исполнительных органов и т.п.), вершины-распознаватели анализируют значения переменных (набор которых задан для каждой вершины) и в зависимости от их значений выбирают вариант продолжения вычислений. Выбор продолжения определяется вычислением логических выражений, определенных для каждого выхода в виде логических формул над базовыми предикатами. В ходе вычислений выбирается тот выход, для которого оказалось истинным логическое выражение (предполагается, что одновременно истинным может не более одного выражения). На рис. 1 приведен пример блок-схемы.





Рис. 1 Пример блок схемы программы


Для наших целей удобнее представлять блок-схему в виде предлагаемого автором «автоматного графа программы» (АГФ) - графа с помеченными дугами и непомеченными вершинами. В качестве меток на дугах выступают:

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

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

На рис. 2 исходная блок-схема переписана в форме «автоматного графа программы».




Рис. 2 Автоматный граф программы для блок-схемы на рис. 1


Процесс вычислений при заданных исходных значениях переменных можно представить, как движение по автоматному графу программы. Если из вершины выходит несколько дуг, то проход осуществляется по той дуге, условия на которой истинны. Таким образом, каждому завершенному вычислению будет соответствовать путь в автоматном графе, начинающийся в начальной и заканчивающийся в заключительной вершине. Протоколом вычислений называется любой путь из начальной вершины в заключительную, представленный в форме автоматного графа без контуров и разветвлений . При этом имена переменных в протоколе, указанные в условиях и действиях, обозначаются новыми идентификаторами при каждом новом проходе по ранее пройденным дугам исходного АГФ. На рис.3 показан пример протокола вычислений, порожденный автоматным графом, представленным на рис. 2.





Рис. 3 Пример протокола вычислений


Относительно записи условий на дугах автоматного графа протокола возможны варианты:

На дуге (АГФ протокола) записывается полное логическое выражение, помечающее соответствующую дугу АГФ порождающей программы, вместе со значением его истинности (в этом случае говорим о полном протоколе).

На дуге записываются только базовые предикаты, помечающие соответствующую дугу АГФ порождающей программы, вместе со значениями их истинности (в этом случае говорим о логически неполном протоколе).

На дуге записываются только значения переменных, на которых определены базовые предикаты, помечающие соответствующую дугу АГФ порождающей программы (в этом случае говорим о предикатно неполном протоколе).

Если имеется несколько протоколов (соответствующих разным исходным данным), то их можно объединить в дерево, совместив общие начала протоколов. Именно дерево протоколов является исходным данным для процедуры автоматического синтеза программы, которую будем называть процедурой «генерализации». Задача процедуры генерализации состоит в построении по заданному дереву протоколов неизвестного АГФ, АГФ минимальной сложности, который может породить заданное дерево. В зависимости от варианта протокола (А, В или С) дополнительно может требоваться синтез минимальных логических выражений над базовыми предикатными символами (случай В) или не только синтез минимальных логических выражений, но и самих базовых предикатов (случай С). Выполнение синтеза для случая В и, возможно, для случая С может быть осуществлено с привлечением нейросетевой технологии, так как здесь имеет место классическая задача классификации. Отметим, что синтезированный в результате генерализации автоматный граф, обеспечит те же самые результаты вычислений, что и исходное дерево, но дополнительно будет способен обрабатывать исходные данные, которые не входили в обучающую выборку. Гипотеза: процедуру генерализации можно считать проявлением фундаментального закона живых организмов – закона минимизации объема хранимой информации при сохранении функциональности поведения. Эту задачу, по смыслу, с успехом умеет решать «биологический компьютер», использующий при этом свои вычислительные примитивы, из-за которых сам процесс минимизации с точки зрения реализации может выглядеть совершенно по иному.


^ Схема обучения с учителем


Если рассматривается задача обучения с подкреплением, то протоколы формируются естественным образом – это запись вложенных друг в друга конструкций «если … то .. » (если имело место (справедливо) некоторое условие1, то было выполнено действие1 и, если далее при этом имело место условие2, то было выполнено действие2 и т.д.). Генерация указанной истории происходит случайным и/или детерминированным образом в соответствии с процедурой поиска решений в проблемной ситуации [моя статья], которая заложена с субъект обучения. В режиме обучения с учителем, как указывалось выше, должен использоваться «прикладной транслятор». Необходимость подобного транслятора является принципиальным моментом процесса обучения с учителем, т.е. требуются некоторые априорные знания, без которых невозможно обучение. Рассмотрим более подробно всю схему. В предлагаемой постановке выделяются следующие объекты:

субъект обучения (СО)

учитель (У)

сцена, на которой размещаются объекты, с помощью которых учитель демонстрирует обучающие примеры

метаязык для описания примеров.

В качестве сцены в нашем случае выступает потенциально бесконечная лента с ячейками, в которые можно записывать символы из некоторого алфавита. Объектами, размещаемыми на сцене, служат строки символов. Данный тип сцены обладает принципиальным свойством – объекты на ней принадлежат к классу, так называемых, «конструктивных объектов» т.е. объектов, манипулирование которыми выполняется по строго определенным правилам. С помощью «конструкторов» из отдельных частей конструируется целое (таким конструктором в нашем случае является операция конкатенации или сцепления, создающая целую строку из начала и хвоста), с помощью селекторов из целого выделяются отдельные компоненты (в данном случае это операции выделения первого символа и остатка строки), с помощью базовых предикатов классифицируются кортежи объектов (в данном случае это отношение «=» , с помощью которого можно определять равенство двух строк) (в общем случае примитивы, используемые учителем и СО могут не совпадать, но в совокупности обладать одной и той же полнотой). Благодаря указанным свойствам состояние сцены может быть взаимно однозначно отображено во внутреннее представление субъекта обучения (СО), поэтому сформированные в результате обучения правила могут в дальнейшем исполняться без обращения к объектам сцены, а путем манипулирования ими во внутренней форме, т.е. метафорически выражаясь, «в уме». Данная возможность является общим свойством при работе со знаковыми системами.

Метаязык это соглашения об обозначениях, которые предполагаются одинаково известными и учителю и СО. В данном случае это «=>», «{» и «}», «<» и «>». Знак «=>» формирует из двух объектов пример. Объект, стоящий слева от данного знака, представляет исходную строку, а стоящий справа – результирующую. Именно формирование процедуры, преобразующей исходную строку в результирующую, есть цель обучения. В данной постановке используются «размеченные» примеры. Это значит, что в левой части выделены некоторые подстроки (называемые фрагментами) с помощью скобок «<» и «>», например:


<121> + <22>.


Фрагменты используются для обозначения тех подстрок, которые могут меняться от примера к примеру, при сохранения общей структуры. Правая часть состоит из комбинации фрагментов и, возможно, других строк. Скобки «{» и «}» используются для обозначения необходимости вычислить (т.е. применить правила, которые известны системе к этому моменту) к строке внутри них. Возможный вид полного примера:


<121> + <22> => {add(<121>, <22>)}.


Он означает, что любая строка, образец которой представлен левой частью (т.е. представляет собой две последовательности цифр, между которыми находится знак +) должна быть преобразована в строку, представленную правой частью (т.е. в add(arg1, arg2) ) и потом сформированная строка должна быть вычислена. Более сложные примеры, которые позволяют обучить систему вычислениям произвольных выражений, содержащих любое количество операндов и знаков операций c некоторыми упрощениями, приведены ниже:


<11> + <12> => {add (<11>, <12> )}

<11> + <12> + <13> => {{ <11> + <12> } + <13> }

<11>* <12> => {mult (<11>, <12> )}

<11> * <12> * <13> => {{ <11> * <12> } * <13> }

<11> * <12> + <13> => {{ <11> * <12> } + <13> }.


Примеры, представленные на сцене, могут быть двух типов: демонстрирующие процесс обработки входной цепочки для получения выходной (т.е. процесс преобразования) и демонстрирующие результаты преобразований. Представленные выше примеры относятся ко второму случаю. Это значит, что схема проведения анализа входной цепочки для выделения фрагментов, а также схема формирования результирующей цепочки (вид которой представлен правой частью примера) должны быть восстановлены по примерам. Именно для этого нужна априорная информация, которая позволяет перейти от предъявленного результата к способу его получения. В рассматриваемых примерах в качестве такой априорной информации выступала широко известная «методика проведения нисходящего анализа при просмотре цепочки слева направо» [ахо] (отметим, что данная методика анализа является далеко не единственной, которую можно использовать для реализации анализа). Выражаясь метафорически, априорная информация отражает способность СО, воспроизводить примеры, которые он наблюдает.


^ Схема трансляции

Как показал наш анализ, при выполнении «трансляции» для получения «протоколов вычислений» должны быть выполнены семь последовательных трансформаций:

Разметка (задана изначально),

Проекция

Распознавание выделенных фрагментов

Частичные вычисления правой части обучающего примера

Собственно трансляция полученной формы обучающего примера в протоколы вычислений

Слияние

Устранение недетерминизма.

Второй этап (проекция) состоит в переносе информации о структуре анализируемой цепочки (представленной скобочной структурой из { и } в правой части примера) в левую. Так после проекции левая часть второго примера будет иметь вид:


<<11> + <12>> + <13>.


Третий этап (распознавание выделенных фрагментов) метафорически соответствует «узнаванию знакомых объектов» (предполагается, что для них уже сформированы внутренние программы для их выделения). Он состоит в подстановке в генерируемую программу разбора соответствующие им внутренние программы.

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


{add ({add (<11>, <12> )}, <13>)}.


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

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

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

Выводы


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

Список литературы

Р. Каллан Основные концепции нейронных сетей Изд. дом Вильямс, М.: 2001 г.

В.Г. Редько, Проблемы адаптивного поведения и подходы к моделированию мышления, http://wsni2003.narod.ru/Intro.htm

Сергиевский Г.М. Об одном варианте использования процедурного подхода для моделирования адаптивного поведения//Сб. трудов всерос. научно-тех. конф. «Нейроинформатика-2010»: М: МИФИ,т.1 2010 г.

Сайт по индуктивному программированию http://www.inductive-programming.org/

Emanuel Kitzelmann. Inductive Synthesis of Functional Programs: An Explanation Based Generalization Approach, http://portal.acm.org/citation.cfm?id=1248562



1 Частичными вычислениями называются специальные способы исполнения программ с неполностью означенными формальными параметрами
13>12>11>13>12>11>13>12>11>13>12>11>13>12>11>13>12>11>12>11>12>11>13>12>11>13>12>11>12>11>12>11>22>121>22>121>22>121>