Текст книги "Мивар: Линейный логический вывод"

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

Варламов Олег Олегович, Московский автомобильно-дорожный государственный технический университет (МАДИ), Московский физико-технический институт (государственный университет) (МФТИ) ([email protected]; [email protected])

Аннотация

Показан теоретический переход от однодольных продукционных систем к двудольным миварным логико-вычислительным сетям. Приведены примеры реализации миварных сетей в формализмах матриц и графов. Теоретически обоснована линейная вычислительная сложность автоматического конструирования алгоритмов из переменных-объектов и правил-процедур миварных сетей. В качестве миварных правил могут быть использованы различные сервисы, модули и вычислительные процедуры. Автоматический конструктор алгоритмов может использоваться для поиска логического вывода в области создания экспертных систем.

На основе миварных сетей создан программный комплекс УДАВ, который обрабатывает более 1,17 млн переменных и более 3,5 млн правил на обычных компьютерах и ноутбуках. Приведены результаты практических расчетов и решений различных прикладных задач, которые на практике подтверждают линейную вычислительную сложность конструирования алгоритмов в формализме миварных сетей. Программный комплекс УДАВ используется как для решения логических, так и вычислительных задач. Приведены сведения о практической реализации нескольких миварных экспертных систем.

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

Ключевые слова: мивар, миварные сети, логический вывод, вычислительная сложность, искусственный интеллект, интеллектуальные системы, экспертные системы, представление знаний, продукционные системы, сети Петри, Универсальный решатель задач, интеллектуальные пакеты прикладных программ, логический вывод с линейной вычислительной сложностью.

Введение

Проблема создания интеллектуальных систем остается актуальной и практически значимой. Создание экспертных систем нового поколения позволит автоматизировать решение различных сложных интеллектуальных задач и повысит конкурентоспособность своих пользователей. Миварный подход позволил предложить новые модели и методы обработки информации и управления [1-22]. Миварные технологии накопления и обработки информации разрабатываются в России достаточно давно. Первые статьи были посвящены исследованию некоторых задач теории графов и разработке линейного матричного метода определения маршрута логического вывода на адаптивной сети правил [1-3]. Затем были работы по созданию миварного информационного пространства и эволюционных баз данных и правил [4-5]. Наиболее строгое формализованное и теоретическое оформление мивары получили в работах [6-7]. Затем были рассмотрены вопросы развития миваров [8-10] и их применения для создания различных тренажеров и обучающих систем [11-22]. Наиболее полно обзор теории и последних достижений миваров приведен в работах [4, 6, 10, 15, 18].

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

Миварный подход объединяет и развивает достижения в научных областях: баз данных, вычислительных задач, логической обработки и включает две основные технологии.

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

2) Миварная технология обработки информации – это способ создания системы логического вывода или «автоматического конструирования алгоритмов из модулей, сервисов или процедур» на основе активной обучаемой миварной сети правил с линейной вычислительной сложностью.

Мивары быстрее, чем продукции, потому что:

1) в продукциях за основу поиска были взяты правила, которые перебирались для поиска решения, что порождало полный перебор, факториальную сложность и циклы;

2) в миварных сетях явно выделены две доли: "правила" и "объекты" ("переменные"), а за основу поиска алгоритма логического вывода взяты именно "объекты", которые могут иметь только одно значение и их можно найти только один раз, что исключает циклы и полный перебор;

3) Миварная сеть может быть задана двухмерной матрицей, в которой каждое правило знает все свои входные и выходные объекты, а каждый объект, соответственно, знает все свои правила и свои роли в них ("вход" или "выход"), что позволяет избежать перебора и постепенно выявляя новые известные объекты через соответствующие правила, постоянно сокращать размерность исходной миварной матрицы обеспечивая линейную вычислительную сложность логического вывода относительно общего количества правил в матрице.

Миварная технология накопления информации предназначена для хранения любой информации с возможным эволюционным изменением структуры и без ограничений по объему и формам представления.

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

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

В настоящее время "движок" УДАВ выполняет поиск логического вывода и автоматически конструирует алгоритмы решения задач из готовых модулей-сервисов, управляемые потоком входных данных. На обычном ноутбуке УДАВ обрабатывает более 1,17 млн переменных и 3,5 млн правил. Программная реализация наглядно доказывает на практике линейную сложность поиска логического вывода, эволюционность и активность работы миварных экспертных систем нового поколения.

Анализ существующих парадигм и моделей обработки данных

Традиционно выделяют следующие парадигмы и модели обработки данных: исчисление высказываний, исчисление предикатов, продукции, семантические сети, онтологии и др. У продукционного подхода есть важные преимущества. Поспелов Д.А. писал, что знания о внешнем мире могут иметь двоякую природу:

1) могут содержать декларативное описание фактов и явлений внешнего мира, фиксирующее их наличие или отсутствие, а также основные связи и закономерности, в которые эти факты и явления входят;

2) могут содержать и процедурные описания того, как надо манипулировать с этими фактами и достигать целей, интересных для системы [23].

Продукции в общем виде записывают в форме "Если… то…". Часть специалистов по интеллектуальным системам считает, что запись знаний в виде систем продукций носит универсальный характер – любые знания можно записать в такой форме. В системе продукций можно представлять самые разнообразные правила, процедуры, формулы или сервисы. К ним, по сути, сводятся все каузальные, т.е. причинно-следственные утверждения. Поспелов Д.А. делает совершенно обоснованный вывод: "Продукционные системы получили при представлении знаний в последнее время наибольшее распространение". Следовательно, применение продукционного подхода для логико-вычислительной обработки разнообразных данных является вполне обоснованным и целесообразным.

Для решения многих практических задач применения информационных систем и процессов требуется проводить как логическую, так и вычислительную обработку данных. Исторически так сложилось, что области логического вывода и вычислительной обработки развивались самостоятельно и успешно решали различные классы задач. В некотором смысле, даже существовало противоречие между этими подходами [2, 3, 4, 10-17, 23-32]. Кроме того, разделяли проблемы обработки и хранения различных данных.

Базы данных преимущественно использовались только для хранения и поиска требуемых данных, а системы логического вывода и вычислений применялись для обработки информации, поиска решений и т.п. Получалось, что эти области относительно слабо пересекались, хотя, в плане перспектив развития в каждой из них регулярно провозглашались цели объединения всех функций по накоплению и обработке информации в одной системе [4, 10, 23-32].

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

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

Возможности и ограничения продукционного подхода

Для анализа проблем метода логико-вычислительной обработки данных и его возможных применений очень важным является следующее заключение Поспелова Д.А.: «Мы хотим отметить, что ядром всех основных типов рассмотренных интеллектуальных систем являются база знаний и блок, осуществляющий вывод с помощью знаний (решатель, планировщик или логический блок). Этот вывод составляет основную процедуру, реализуемую в интеллектуальных системах» [23, стр. 129].

В настоящее время продолжается дискуссия о роли и возможных применениях различных логических механизмов и, прежде всего, исчисления высказываний и исчисления предикатов и продукций. У продукционного подхода есть важные преимущества. Приведем мнение Поспелова Д.А.: "Для описания знаний в интеллектуальных системах используются специальные языки описания знаний (ЯОЗ). … Простейшими видами таких ЯОЗ являются языки исчисления высказываний или исчисления предикатов вместе с теми процедурами вывода, которые для них известны. Однако в современных интеллектуальных системах такие языки используются довольно редко. Куда более распространены в них языки, основанные на продукциях. … Продукции в общем виде можно записать в форме «если… то…», но к продукциям относятся не только выражения, имеющие эту форму, но и многие другие" [23, стр. 129]. У Поспелова Д.А. приведены 9 типов продукций и специально подчеркнуто, что возможны продукции и других типов [23, стр. 131-134]. Далее делается вывод: «… продукции могут иметь весьма различное значение. В качестве их левых и правых частей могут выступать и некоторые утверждения, и действия» [23, стр. 134]. Также «…приводят немало примеров, когда знания, внешне не имеющие продукционной формы, удается перевести в систему продукций» [23, стр. 129-130]. Далее там же приведен пример перевода в продукционную форму записи химических реакций, для чего используются различные виды продукций. «К ним (продукциям), по сути, сводятся все каузальные, т.е. причинно-следственные утверждения…» [23, стр. 130]. Отметим, что Кузнецов О.П. в [24, стр. 282-283] под продукциями понимает множество правил вывода в канонических системах (системах продукций Поста), в которых есть посылки и следствия. С точки зрения анализа метода логико-вычислительной обработки данных принципиально важным является то, что в системе продукций можно представлять самые разнообразные правила, процедуры, формулы или сервисы. Следовательно, применение продукционного подхода для логико-вычислительной обработки разнообразных данных является целесообразным.

Также Поспеловым Д.А. дается определение: "Продукционной системой будем называть любую совокупность продукций, в которую могут входить продукции любого из перечисленных выше типов" [23, стр. 134]. Существуют различные конструкции продукций. В наиболее общем виде "вместо продукций типа a=>b рассматривают более сложные конструкции. В общей форме продукции имеют вид:

i, П, Р, A=>B, Q.

Здесь A=>B– обычная продукция «если … то …», которая носит название ядра продукции. Элемент Р характеризует внешние условия или условия применимости продукции, определяемые факторами, не входящими непосредственно в A, например, целями, которые стоят перед рассуждающей системой. Условия Р позволяют из всех продукций, у которых в левой части ядра стоит A, отбирать нужную часть продукций. Элемент П характеризует сферу проблемной области базы знаний, или предусловия применимости продукции. Эти предусловия ничем не отличаются от Р, но выделяют подсистемы продукций на ранг выше тех, которые выделяют условия. Предусловия задают формальную систему, в рамках которой будут проводиться логические рассуждения… Наконец, Q характеризует постусловия продукции, указывающие на те изменения, которые необходимо внести в базу знаний и в систему продукций после реализации данной продукции" [23, стр. 134-135].

В общем виде продукции встречаются весьма редко. Отметим, что существует аналогичный подход, основанный на гиперправилах с мультиактивизаторами [4]. Хорошевский В.Ф. в [31, стр. 82-83] при описании "слоеного пирога"SemanticWeb выделяет промежуточный "слой правил", для которого ведутся исследования различных систем вывода на правилах.

Под логической обработкой принято понимать некий вывод, лежащий в основе человеческих рассуждений. Для проведения анализа используем описания и исходную информацию из широко известных источников. В работе Поспелова Д.А. выдвинуто следующее основополагающее положение: "Всякий вывод, как бы он не был организован, носит переборный характер. … программа вынуждена перебирать варианты, заходить в тупики, проходить циклы прежде, чем она сможет найти правильный путь решения. Повышение эффективности процесса вывода – центральная проблема всех автоматизированных систем дедуктивного вывода" [23, стр. 79].

Особый интерес представляет описание общей схемы выводов, лежащей "в основе большого количества моделей человеческих достоверных рассуждений" [23, стр. 83]. Сначала Поспелов Д.А. приводит такое описание в виде некоторого дерева вывода: "Вершинам этого дерева соответствуют определенные утверждения Fi, а дуги определяют порядок получения новых утверждений. Те дуги, которые сходятся в зачерненные точки, образуют конъюктивные условия вывода, а те дуги, которые между собой соединены «дужкой», образуют дизъюнктивные условия вывода. … Дерево вывода с такими условиями переходов от вершины к вершине носит название И-ИЛИ дерева. В И-ИЛИ дереве ориентация дуг показывает направление вывода. Естественное разбиение вершин дерева по ярусам отражает глубину вывода (число шагов, необходимых для получения утверждений данного яруса). Первый ярус дерева образуют вершины… играющие роль аксиом или утверждений, истинность которых задается извне" [23, стр. 83-84]. Однако далее Поспелов Д.А. пишет: «Схема вывода не обязательно описывается в виде дерева. Она может иметь вид произвольной сети, ориентированной, неориентированной или частично ориентированной» [23, стр. 84]. На рисунке 1 показан пример неориентированной сети, аналогичный рисунку в [23, стр. 83]. "Такая сеть (наличие или отсутствие ориентации не играет здесь роли) называется И-ИЛИ сетью. Процесс вывода на И-ИЛИ сети протекает следующим образом. Пусть мы хотим доказать утверждение F6 (на рисунке 1 этому соответствует целевая вершина (выделена двойным контуром)). В качестве априорно доказанного задано утверждение F1 (ему соответствует начальная вершина, которая на рисунке 1 заштрихована). Как из F1 можно получить F6? Если считать, что все связи допускают ориентацию в нужную сторону, то из F1 можно получить F3, затем F5 и, наконец, F6. Но этот путь нам удалось отыскать потому, что сеть, показанную на рисунке 9, мы видим «с высоты птичьего полета». Лабиринт поиска лежит в виде чертежа перед нами. Именно это позволяет нам не делать лишних попыток, не двигаться в ненужную сторону, а идти кратчайшим путем к цели" [23, стр. 84]. Это выражало общее мнение ученых. Отметим, что на рисунке 1 фактически изображен однодольный граф, т.е. все вершины графа принадлежат одному классу [24, стр. 125]. Этот факт будет очень важен для дальнейшего анализа.

Рисунок 1. Пример однодольного графа неориентированной «И-ИЛИ сети».

Поспелов Д.А. описал два метода логического вывода. "Эта процедура известна среди специалистов под названием метода прямой волны. Волна поиска путей к целевой площадке распространяется от всех площадок, играющих роль начальных. … Возможен и другой способ поиска доказательства. Он носит название метода обратной волны. В этом методе волна начинает свое движение от целевых площадок и движется в направлении начальных площадок лабиринта. … Различие между прямой и обратной волной состоит в том, что они порождают в процессе своего движения различные промежуточные «фронты» площадок, что приводит к различному числу шагов при поиске. Часто используется смешанный метод вывода, при котором одновременно движутся прямая и обратная волны. При встрече этих волн формируется путь вывода от начальных аксиом к целевым выражениям" [23, стр. 85].

Отметим, что эти работы не нашли широкого практического применения в прошлом веке. Это обусловлено тем, что не было предложено метода быстрой логической обработки данных. Как было показано выше, ученые исходили из предпосылки, что любой вывод носит переборный характер, что означает факториальный рост вычислительной сложности при увеличении количества правил. Даже современные суперкомпьютеры при таком подходе позволяют обрабатывать в реальном масштабе времени лишь 20 правил. Фактически, это позволяет решать только "игрушечные" модельные задачи, т.к. современные требования начинаются с сотен и достигают десятков тысяч переменных и правил даже для относительно простых предметных областей. Миварный подход и создание логико-вычислительных сетей позволил эффективно реализовать предложенные для продукций Поспеловым Д.А. методы прямой и обратной волны [23, стр. 85].

Системы искусственного интеллекта и мивары

Рассмотрим основные подходы к созданию искусственного интеллекта (ИИ) и экспертных систем. Приведем мнение Дж. Люгера, который считал «… объединение разрозненных областей искусственного интеллекта с помощью детального описания его теоретических основ … Интеллект – это сложная область знаний, которую невозможно описать с помощью какой-то одной теории. Ученые строят целую иерархию теорий, характеризующие его на разных уровнях абстракции» [32, стр. 20]. Формальный подход Рассела и Уайтхеда к математическим умозаключениям сделал возможной его автоматизацию в реальных вычислительных машинах. Логический синтаксис и формальные правила вывода, разработанные Расселом и Уайтхедом, лежат в основе систем автоматического доказательства теорем и составляют теоретические основы искусственного интеллекта [32, стр. 34-35]. Однако, с другой стороны, это наложило и важные ограничения на возможности описания реальных предметных областей: формализм, как выясняется, тоже имеет свои недостатки вместе с преимуществами. Нельзя не отметить и роль А. Тарского, чья теория ссылок сыграла принципиальную роль в процессе формирования ИИ. Согласно этой теории, правильно построенные формулы Фреге или Рассела-Уайтхеда определенным образом ссылаются на объекты реального мира, а эта концепция лежит в основе большинства теорий формальной семантики. Люгер справедливо отмечает, что ИИ не стал жизнеспособной научной дисциплиной до появления цифровых вычислительных машин.

Однако архитектура цифровых компьютеров наталкивает на специфичное представление теории ИИ. Получается, что интеллект – это способ обработки информации. Далее Люгер формулирует замечательную мысль, к которой мы с удовольствием присоединяемся: "Мы часто забываем, что инструменты, которые мы создаем для своих целей, влияют своим устройством и ограничениями на формирование наших представлений о мире". Такое, казалось бы, стесняющее наш кругозор взаимодействие является важным аспектом развития человеческого знания: инструмент (а научные теории, в конечном счете, тоже инструменты) создается для решения конкретной проблемы. По мере применения и совершенствования инструмент подсказывает другие способы его использования, которые приводят к новым вопросам и, в конце концов, разработке новых инструментов [32, стр. 35]. Если говорить о миварах и перечисленных выше формализмах Фреге, Рассела и Уайтхеда, Тарского и многих других, то надо помнить, что наука развивается по спирали и старые формализмы требуют своего продолжения на новом витке. Упомянутые выше исчисление предикатов и другие ранние фундаментальные формализмы при необходимости могут быть реализованы и в правилах (отношениях) миварных сетей. Только надо помнить, что есть и другие формализмы представления информации для ИИ, а у исчисления предикатов первого порядка есть достаточно жесткие ограничения и не очень большие возможности, если вспоминать не об "игрушечных" задачах, а говорить о создании глобальных познающе-диагностических систем, решающих сложные логико-вычислительные задачи в реальном времени. Как видно из [23-32], в современной теории ИИ кроме предикатного подхода уже разработано большое количество других подходов, кардинально отличающихся от исчисления предикатов и т.п. Подчеркнем, что продукционный подход и его развитие в миварных сетях являются еще одной альтернативой исчислению предикатов при создании искусственного интеллекта.

В области ИИ существует две фундаментальные проблемы – это представление знаний и поиск [32, стр. 42]. Первая проблема относится к получению новых знаний с помощью формального языка. Поиск – это метод решения проблемы, в котором систематически просматривается пространство состояний задачи, т.е. альтернативных стадий ее решения. Автоматическое доказательство теорем – одна из старейших областей возможного применения ИИ, где было много достижений, исследований и программ, включая Универсальный решатель задач Ньюэлла и Саймона. Дж. Люгер подчеркивает, что именно "…эта ветвь принесла наиболее богатые плоды…" [32, стр. 44]. Благодаря исследованиям в этой области были формализованы алгоритмы поиска и разработаны языки формальных представлений, такие как исчисление предикатов и логический язык программирования Prolog.

Приведем обоснование Дж. Люгера: "… привлекательность автоматического доказательства теорем основана на строгости и общности логики. В формальной системе логика располагает к автоматизации. Разнообразные проблемы можно попытаться решить, представив описание задачи и существенно относящуюся к ней информацию в виде логических аксиом и рассматривая различные случаи задачи как теоремы, которые нужно доказать. Этот принцип лежит в основе автоматического доказательства теорем и систем математических обоснований" [32, стр. 44]. Далее следует вывод в этой наиболее богатой ветви: "К сожалению, в ранних пробах написать программу для автоматического доказательства, не удалось разработать систему, которая бы единообразно решала сложные задачи" [32, стр. 44]. Таким образом, Дж. Люгер подтверждает наш тезис о том, что в прошлом веке даже в самых передовых областях ИИ ученые не смогли решить сложные задачи, а значит, нужны принципиально новые подходы и исследования, к числу которых относится и миварный подход. Приведем обоснование ограниченности возможностей автоматического доказательства теорем. "Это было обусловлено способностью любой относительно сложной логической системы сгенерировать бесконечное количество доказуемых теорем: без мощных методик (эвристик), которые бы направляли поиск, программы доказывали большие количества не относящихся к делу теорем, пока не натыкались на нужную. Из-за этой неэффективности многие утверждают, что чисто формальные синтаксические методы управления поиском в принципе не способны справиться с такими большими пространствами, и единственная альтернатива этому – положиться на неформальные, специально подобранные к случаю (лат "adhoc") стратегии, как это, похоже, делают люди. Это один из подходов, лежащих в основе экспертных систем… и он оказался достаточно плодотворным" [32, стр. 44].

Таким образом, возникают новые проблемы: работа с бесконечными множествами теорем и разработка эвристик, про которые ранее было показано, что они не гарантируют решение задачи. Конечно, за прошедшее время ученым удалось разработать мощные эвристики, основанные на оценке синтаксической формы логического выражения, которые в результате понижают сложность пространства поиска. Кроме того, пришло понимание, что системе не обязательно решать особо сложные проблемы без человеческого вмешательства. "Многие современные программы доказательств работают как умные помощники, предоставляя людям разбивать задачи на подзадачи и продумывать эвристики для перебора в пространстве возможных обоснований" [32, стр. 44]. Этот вывод может служить обоснованием нашего утверждения, что ИИ – это усилитель человеческих способностей и автоматизация мыслительных процессов. Кроме того, это косвенно подтверждает необходимость введения шкалы измерений интеллектуальности автоматических систем и наличие относительно слабых форм интеллекта у уже существующих компьютерных программ и устройств. Значит, в таком смысле ИИ уже существует и продолжает развиваться, помогая человеку решать сложные задачи.

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

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

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