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

• Название: Мивар: Линейный логический вывод
• Автор: Олег Варламов
• Жанр: Справочники

МИВАР: ПЕРЕХОД ОТ ПРОДУКЦИЙ К ДВУДОЛЬНЫМ МИВАРНЫМ СЕТЯМ И ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ АВТОМАТИЧЕСКОГО КОНСТРУКТОРА АЛГОРИТМОВ, УПРАВЛЯЕМОГО ПОТОКОМ ВХОДНЫХ ДАННЫХ И ОБРАБАТЫВАЮЩЕГО БОЛЕЕ ТРЕХ МИЛЛИОНОВ ПРАВИЛ. Показан теоретический переход от однодольных продукционных систем к двудольным миварным логико-вычислительным сетям. Приведены примеры реализации миварных сетей в формализмах матриц и графов. Теоретически обоснована линейная вычислительная сложность автоматического конструирования алгоритмов из переменных объектов и правил-процедур миварных сетей. В качестве миварных правил могут быть использованы различные сервисы, модули и вычислительные процедуры. Автоматический конструктор алгоритмов может использоваться для поиска логического вывода в области создания экспертных систем. На основе миварных сетей создан программный комплекс УДАВ, который обрабатывает более 1,17 млн переменных и более 3,5 млн правил на обычных компьютерах и ноутбуках. Приведены результаты практических расчетов и решений различных прикладных задач, которые на практике подтверждают линейную вычислительную сложность конструирования алгоритмов в формализме миварных сетей. Программный комплекс УДАВ используется как для решения логических, так и вычислительных задач. Приведены сведения о практической реализации нескольких миварных экспертных систем. Миварные сети позволяют перейти к новому поколению экспертных систем и интеллектуальных пакетов прикладных программ. Миварный подход позволил на практике создать автоматические обучаемые эволюционные активные логически рассуждающие информационные системы. В перспективе на основе миварных сетей будет создана глобальная мультипредметная активная экспертная система под названием Миварная активная энциклопедия.

---

Базы данных преимущественно использовались только для хранения и поиска требуемых данных, а системы логического вывода и вычислений применялись для обработки информации, поиска решений и т.п. Получалось, что эти области относительно слабо пересекались, хотя, в плане перспектив развития в каждой из них регулярно провозглашались цели объединения всех функций по накоплению и обработке информации в одной системе [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]. Этот факт будет очень важен для дальнейшего анализа.

Конец ознакомительного фрагмента.

Текст предоставлен ООО «ЛитРес».

Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.