Мивар: Линейный логический вывод - Олег Варламов

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]. Кроме того, разделяли проблемы обработки и хранения различных данных.