Титенко Е

К.т.н. Сазонов С.Ю., , к.т.н. Титенко Е.А., Гришин Д.С., Крипачев А.В.

Юго-Западный государственный университет, Россия

МОДИФИЦИРОВАННАЯ ПРОДУКЦИОННАЯ СИСТЕМА ДЛЯ ПАРАЛЛЕЛЬНЫХ СТРАТЕГИЙ

Одним из приоритетных направлений развития современной информатики являются теоретические и прикладные средства высокопроизводительной обработки знаний. Модели и методы обработки знаний ориентированы под решение слабо формализованных и проблемно-поисковых задач, доля которых постоянно растет в современных научных исследованиях (структурное распознавание образов, динамические экспертные системы, машинный перевод, естественно-языковые системы, базы знаний, интеллектуальный анализ данных и их кластеризация, сжатие данных и др.) [1].

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

В рамках теории алгоритмов для задания прикладных поисково-вычислительных процессов с неизвестной последовательностью команд адекватной моделью считаются исчислительные системы, задающие ветвящиеся конструктивные процессы [2]. Аппарат исчислительных систем или систем, использующих параллелизм потока данных, представляется различными формализмами: логические системы, продукционные исчисления, алгебраические исчисления, нейронные сети, генетические алгоритмы и др. [1].

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

ПС имеют преимущественно программную реализацию (языки программирования SNOBOL-4, OPS-5 с поддержкой поиска по образцу, объектно-ориентированная среда CLIPS для разработки экспертных систем, язык Рефал и его модификация с поддержкой функций библиотеки MPI, инструментальные средства для задач искусственного интеллекта ART, KEE, G2 и др.) [3]. Программная реализация ПС на существующих традиционных архитектурах вычислительных устройств и систем (ВУ и ВС) приводит к неудовлетворительным временным характеристикам при решении задач ОСИ реального уровня сложности. Основной причиной возникновения избыточных временных затрат являются стратегии последовательного с возвратами поиска по графу решений (поиск в глубину/в ширину, поиск от цели/от данных и их различные модификации). Данные стратегии выводов не учитывают естественный параллелизм потока данных, свойственный для исчислительных ПС. В тоже время многочисленные известные архитектуры параллельных ВУ и ВС, в первую очередь, ориентированы на разрешение конфликтов по управлению. Они не учитывают специфических (структурных) конфликтов по данным, возникающих при параллельном исполнении продукций и организации поиска по графу решений. Таким образом, создание модифицированных стратегий выводов с разрешением структурных конфликтов по данным является необходимым условием организации параллельных символьных вычислений на основе ПС.

В общем виде исчислительная ПС задается как

(A, Á ) (1),

где A – рабочий алфавит, Á – определяющее множество продукций количеством t продукций.

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

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

1) отношение линейного вывода (стандартный последовательный вывод);

2) p-значное отношения равноправного вывода (ИЛИ- вывод);

3) p- значное отношения независимого вывода (И- вывод).

Равноправное и независимое срабатывание продукций основано на использовании дополнительной информации о структурных конфликтах по данным между продукциями изÁ. Дополнительная информация представляется в виде счетного множества конфликтных слов I, формируемых на основе анализа структурных отношений (вхождение, пересечение, дополнение) между продукциями. Главная особенность I заключается в том, что конфликтные слова формируются до начала генерации графа решений. По существу, они являются характеристикой самой ПС и параллельных процессов, порождаемых ПС. Корректность синтеза конфликтных слов из I подтверждена доказательствами логических условий пересечения слов в рамках конструктивной логики [4].

В итоге, модифицированная ПС описывается как

(A, Á, I) (2).

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

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

Работа выполнена в рамках государственного задания Министерства образования и науки Российской Федерации №8.8482.2013.

Литература

1. Люгер Дж. Ф. Искусственный интеллект: стратегии и методы решения сложных проблем. - М.: Издательский дом «Вильямс». 2003. - 864 с.

2. Успенский, В.А. Теория алгоритмов: основные открытия и приложения / В.А. Успенский, А.Л. Семенов. - М.: Наука, 1987. - 288с.

3. Базы знаний интеллектуальных систем / Т.А. Гаврилова, В.Ф. Хорошевский.- СПб.: Питер, 2001. - 384 с.

4. Титенко Е.А. Исчислительная система продукций и процедура распознавания конфликтов данных // Вестник компьютерных и информационных технологий. 2012. - №2. - С.24-29.