Содержание к диссертации
Введение 5
Глава 1. Анализ методов и машин логического вывода и систем обработки знаний 14
1.1 Методы и машины логического вывода 14
1.1.1 Классификация видов логического вывода 14
1.1.2 Классификация методов логического вывода 16
1.1.3 Метод деления дизъюнктов 19
1.1.4 Машины логического вывода 23
1.2 Системы обработки знаний (СОЗ) 25
1.2.1 Определение и структура 25
1.2.2 Классификация 29
1.2.3 Режимы функционирования 31
1.2.4 Оценка эффективности 33
1.3 Выводы по главе 1 35
Глава 2. Разработка метода логического вывода модифицируемых заключений 36
2.1 Формальные системы 36
2.2 Постановка задачи логического вывода 37
2.3 Расширение формулы заключения
2.3.1 Унификация литералов 39
2.3.2 Согласование решений 40
2.3.3 Согласование значений общих переменных в конъюнкциях дизъюнктов 43
2.3.4 Частичное деление дизъюнктов 45
2.3.5 Полное деление дизъюнктов 47
2.3.6 Процедура вывода 49
2.3.7 Построение абдуктивных объяснений
2.3.8 Метод параллельного вывода с расширением формулы заключения
2.4 Минимизация формулы заключения 65
2.4.1 Процедура минимизации заключения 65
2.4.2 Метод минимизации заключения
2.5 Выбор вариантов модификации 69
2.6 Особенности вывода в исчислении высказываний 72
2.7 Пример вывода 73
2.8 Выводы по главе 2 77
Глава 3. Разработка системы логического вывода модифицируемых заключений 80
3.1 Структура системы логического вывода 80
3.1.1 Обобщенная структура системы 80
3.1.2 Детализованная структура системы 82
3.2 Режимы работы системы логического вывода 85
3.2.1 Режим вывода модифицируемых заключений 86
3.2.2 Режим дедуктивного вывода 88
3.2.3 Режим абдуктивного вывода 88
3.2.4 Режим настройки 88
3.2.5 Режим непосредственного доступа к базам знаний 89
3.2.6 Создание базы знаний
3.3 Машина логического вывода модифицируемых заключений 90
3.4 Язык декларативного логического программирования
3.4.1 Структура логической программы 96
3.4.2 Идентификаторы и константы 99
3.4.3 Комментарии 100
3.4.4 Пример логической программы 101
3.5 Оценка эффективности систем логического вывода 102
3.5.1 Критерии оценки эффективности 102
3.5.2 Расчет времени вывода 103
3.5.3 Расчет степени модификации заключения 108
3.6 Выводы по главе 3 110
Глава 4. Применение систем логического вывода модифицируемых заключений ИЗ
4.1 Области применения 113
4.2 Интеллектуальные обучающие системы 114
4.3 Экспертные системы 119
4.4 Интеллектуальное управление вычислительными процессами 121
4.5 Модуль логического вывода модифицируемых заключений 1
4.5.1 Общая характеристика разрабатываемого программного обеспечения 127
4.5.2 Структура модуля вывода 128
4.5.3 Язык описания базы знаний и заключения 129
4.5.4 Реализация блоков модуля 130
4.6 Учебная программа логического вывода «Логика-В» 134
4.6.1 Структура программы 134
4.6.2 Язык описания исходных данных 135
4.6.3 Интерфейс пользователя 136
4.6.4 Пример использования программы 141
4.7 Выводы по главе 4 149
Заключение 152
Список сокращений 155
Библиографический список 156
Приложения 1
Введение к работе
Данная диссертационная работа посвящена разработке нового метода логического вывода модифицируемых заключений на знаниях, представленных в виде формул исчисления высказываний и исчисления предикатов первого порядка, а также системы логического вывода модифицируемых заключений. Рассматриваются вопросы построения систем обработки знаний и машин логического вывода, использующих данный метод, в том числе особенности их программной реализации на современных параллельных вычислительных платформах. Приводятся области возможного применения данного метода логического вывода, рассматривается применение логического вывода модифицируемых заключений для интеллектуального управления вычислительными процессами, в обучающих системах и в экспертных системах.
Актуальность темы исследования. Одним из многообещающих направлений в вычислительных системах сегодня являются системы обработки знаний (СОЗ). Уже сейчас они имеют широкое распространение (особенно это справедливо для экспертных систем (ЭС)), а в перспективе смогут применяться практически повсеместно, повышая интеллектуальный уровень вычислительных систем практически всех видов. Однако, несмотря на имеющиеся успехи, современные СОЗ имеют ряд недостатков. В частности, они не способны решать задачи, требующие наличия достоверного заключения при имеющемся недостоверном. Кроме того, современные СОЗ работают неэффективно на параллельных платформах.
В отличие от данных, которые представляют собой операнды для каких-либо формализованных действий по их обработке и не имеют смыслового наполнения с точки зрения обрабатывающей системы, знания отражают те или иные аспекты реального мира и изначально имеют смысловое содержание. Самой лучшей известной на сегодня системой обработки знаний является мозг человека. Однако и он обладает некоторыми недостатками. В частности, он имеет низкое быстродействие при решении многих задач, на работу мозга влияет множество факторов, он подвержен ошибкам. Кроме того, часто условия среды не позволяют использовать человека в качестве системы обработки знаний и принятия решений. Возникает необходимость моделирования поведения человека.
Можно выделить два основных подхода к моделированию поведения естественного интеллекта. Первый из них заключается в моделировании работы отдельных элементов структуры мозга - нейронов и их связей (нейро-сетевой подход). Его характерным недостатком является сложность (часто -невозможность) построения семантической картины хода рассуждений. Второй подход предполагает моделирование интеллектуальных аспектов функционирования мозга: системы понятий (семантической сети), построения рассуждений и других. При этом наиболее часто сейчас используется моделирование рассуждений человека, поскольку имитирует высокоуровневые мыслительные процессы по определенным правилам (например, по правилам логики) и позволяет достаточно просто описывать исходные данные и интерпретировать результат, а также отслеживать ход моделирования.
Моделирование рассуждений средствами логики является одним из приоритетных направлений науки, изучающей методы и средства искусственного интеллекта [86]. Рассуждения, записанные в виде формул логики предикатов первого порядка или логики высказываний, представляются достаточно естественным для человека образом. Интерпретация формулы при этом проста и заключается в замене литералов заранее заданными выражениями, а связок - соответствующими их значению словами.
Логика высказывания представляет собой достаточно простой математический аппарат, обладающий не слишком большими выразительными возможностями. Однако благодаря простоте обработки формул логика высказываний находит широкое применение. Гораздо большими выразительными возможностями обладает логика предикатов первого порядка. Но обработка формул в исчислении предикатов гораздо сложнее, так как требует учитывать зависимость значения предикатных констант от наборов термов, согласовывать значения предметных переменных, учитывать возможность наличия функциональных констант.
Само моделирование рассуждений осуществляется посредством логического вывода (ЛВ). Исходными данными для логического вывода служат формулы посылок и заключения. Посылки представляют собой набор фактов и правил вывода и составляют в совокупности базу знаний. Заключение записывается в виде формулы логики и поступает (как правило) извне в систему логического вывода. Процедуры логического вывода обрабатывают заключение и исходные посылки, и результатом работы может стать сообщение о корректности заключения или модификация исходных посылок.
Обычно выделяют следующие основные виды логического вывода: дедуктивный, абдуктивный и индуктивный. Дедуктивный вывод используется для ответа на вопрос, является ли указанное заключение логическим следствием исходных посылок. Абдуктивный вывод в случае, если заключение не выводится из исходных посылок, позволяет пополнить набор исходных посылок фактами так, чтобы заключение стало выводимым. Индуктивный вывод, в отличие от абдуктивного, позволяет пополнить набор исходных посылок общими правилами.
Данные виды вывода известны достаточно давно и могут применяться для решения широкого круга задач. Однако существует класс задач, решить которые применением указанных видов вывода невозможно или затруднительно. Данный класс задач предполагает наличие корректной и полной БЗ для некоторой предметной области и недостоверное заключение, требующее преобразования. Следовательно, появляется принципиально новая постановка задачи логического вывода: модифицировать исходно невыводимое заключение с целью сделать его следствием исходных посылок. Данная задача решается посредством применения нового вида ЛВ - логического вывода модифицируемых заключений. В качестве областей применения данного вида вывода можно отметить следующие: - системы автоматического регулирования. Состояние объекта управления в такой системе описывается логической формулой заключения, а допустимый диапазон состояний задается в виде формул исходных посылок. Если состояние объекта выходит за допустимые пределы, производится модификация заключения для возвращения объекта в допустимое состояние;
- системы корректирующего обучения. База исходных посылок содержит знания из некоторой предметной области. Обучаемый вводит утверждение, которое проверяется на истинность (выводимость из исходных посылок), и если оно неверно, производится его коррекция;
- грамматический разбор предложений [130]. Логический вывод мо-дифицируемых заключений может быть использован для восстановления предложения и построения новых предложений;
- вычислительные комплексы с динамической архитектурой [139]. Логический вывод модифицируемых заключений может применяться для диспетчеризации вычислительных процессов в системах с динамически изменяющимися составом и связями вычислительных средств;
- экспертные системы. Если начальное заключение пользователя неполно или неверно, логический вывод модифицируемых заключений позволит уточнить (откорректировать) заключение, а в некоторых случаях указать на необходимость исследования дополнительных признаков.
Существует достаточно большое количество методов логического вывода. Основной недостаток значительной их части - последовательный принцип обработки знаний. Это сильно снижает производительность систем логического вывода, использующих данные методы. В связи с этим заслуживают внимания методы параллельного логического вывода, основанные на процедуре деления дизъюнктов [123]. Каждый шаг такого вывода может включать достаточно много операций, большинство из которых может вы 9 подняться параллельно. Это особенно актуально в настоящее время, поскольку сейчас в большинстве случаев производительность ЭВМ наращивается не только и не столько за счет улучшения архитектуры и микроархитектуры процессоров, повышения тактовых частот, сколько за счет увеличения количества процессорных элементов (процессоров и ядер).
Таким образом, является актуальной задача разработки метода и системы параллельного логического вывода модифицируемых заключений на знаниях, представленных в виде формул исчисления высказываний и исчисления предикатов первого порядка, что позволит расширить класс задач, решаемых СОЗ, построенных на основе системы логического вывода, и повысить скорость их работы.
Значительный вклад в разработку и исследование методов и средств логического вывода внесли М. Л. Цетлин, М. М. Бонгард, Я. 3. Цыпкин, Д. А. Поспелов, В. К. Финн, Г. С. Осипов, В. Н. Вагин, Т. А. Гаврилова, В. Ф. Хорошевский, П. Гаек, Т. Гавранек, С. Осуга (S. Osuga), Ю. Саэки (U. Saeki), А. Сэмюэль (A. Samuel), Э. Хант (Е. Hunt), Д. Марин (J. Marin), Ф. Стоун (P. Stone), Р. Михальски (R. Michalski), Д. Карбонелл (J. Carbonell), Т. Митчелл (Т. Mitchell), Д. Куинлан (J. Quinlan). Абдуктивный ЛВ исследовался в работах Ч. С. Пирса (С. S. Pierce), В. К. Финна, В. Н. Вагина, Е. Ю. Головиной, Д. А. Страбыкина, М. Л. Долженковой, Д. Габбая (D. Gabbay), П. Сметса (P. Smets), К. Бутилье (С. Boutilier), П. Флеча (P. Flach), А. Какаса (A. Kakas), К. Иноуэ (К. Inoue), Ч. Сакама (С. Sakama), Дж. Джозефсона (J. Josephson), С. МакИлрайта (S. Mcllraith), Дж. Пола (G. Paul) и др.
Целью исследования является разработка метода параллельного логического вывода модифицируемых заключений для исчисления высказываний и исчисления предикатов первого порядка и построение на его основе системы и машины ЛВ модифицируемых заключений. Для достижения цели необходимо решить следующие задачи.
1. Разработать метод параллельного логического вывода модифицируемых заключений для исчисления высказываний и исчисления предикатов первого порядка, позволяющий модифицировать не выводимое заключение и сделать его следствием исходных посылок.
2. Разработать машину параллельного логического вывода модифицируемых заключений.
3. Разработать систему параллельного логического вывода на основе машины логического вывода модифицируемых заключений.
4. Разработать критерии оценки эффективности работы системы и машины параллельного логического вывода модифицируемых заключений.
Методы исследования. Для достижения поставленной в работе цели исследований использовались методы анализа алгоритмов, теории множеств, теории графов, математической логики, теории логического вывода, логического и объектно-ориентированного программирования.
Научная новизна исследования состоит в следующем.
1. Разработан метод параллельного логического вывода модифицируемых заключений для логики высказываний и логики предикатов первого порядка, отличающийся от известных методов тем, что к полученным в результате абдуктивного вывода дополнительным посылкам применяются: специальная процедура преобразования, позволяющая построить из них дополнения дизъюнктов заключения, метод минимизации заключения, а также параллельный алгоритм оценки вариантов модификации заключения. Это позволяет преобразовать невыводимое заключение с целью сделать его следствием исходных посылок.
2. Разработан метод минимизации заключения для исчисления высказываний и исчисления предикатов первого порядка, отличающийся от известных методов вывода тем, что для поиска решений использует параллельный поиск по дереву решений с отсечением части ветвей. При этом из дизъюнктов заключения удаляются литералы, не участвующие в процессе вывода, тем самым повышая эффективность работы системы логического вывода модифицируемых заключений.
3. Разработан параллельный алгоритм оценки и отбора вариантов модификации дизъюнктов заключения, отличающийся тем, что каждому дизъюнкту ставится в соответствие некоторое числовое значение, полученное применением к дизъюнкту специальной функции оценки. Это позволяет из всего множества вариантов модификации исходных дизъюнктов выбрать наилучшие в соответствие с выбранной функцией оценки дизъюнкта.
4. Разработаны критерии и способы оценки эффективности работы системы и машины логического вывода модифицируемых заключений, учитывающие особенности логического вывода делением дизъюнктов, выбранную степень параллелизма, архитектуру вычислительной машины, виды модификации заключения, что позволяет оценить время, затрачиваемое на логический вывод и степень модификации заключения.
Практическая ценность исследования состоит в следующем:
1. Разработана система параллельного, логического вывода модифицируемых заключений, отличительными особенностями которой являются: использование методов и машины параллельного ЛВ, использование двухуровневой базы знаний, наличие блока интерпретации формул, что позволяет строить на основе разработанной системы логического вывода высокопроизводительные СОЗ различного назначения. Процесс вывода может быть распараллелен вплоть до уровня операций унификации литералов, что повышает скорость логического вывода на параллельных вычислительных платформах.
2. Разработан язык декларативного логического программирования, позволяющий описывать знания формулами исчисления высказываний и исчисления предикатов первого порядка, использовать функторы и предполагающий возможность интерпретации логических формул на естественном языке.
3. Разработана учебная программа логического вывода, отличительными чертами которой являются: реализация нескольких видов логического вывода делением дизъюнктов для исчисления высказываний, в том числе логического вывода модифицируемых заключений, наличие механизма преобразования формул во множество дизъюнктов, интерпретация формул на естественном языке, подробный отчет о ходе вывода. Особенности системы позволяют применять ее для изучения видов и методов логического вывода.
4. Разработаны рекомендации по применению метода и системы параллельного логического вывода модифицируемых заключений для интеллектуального управления вычислительными процессами, в интеллектуальных обучающих системах, в экспертных системах.
На защиту выносятся:
1. Метод параллельного логического вывода модифицируемых заключений для логики высказываний и логики предикатов первого порядка, позволяющий преобразовать невыводимое заключение с целью сделать его следствием исходных посылок.
2. Метод минимизации заключения для исчисления высказываний и исчисления предикатов первого порядка, позволяющий удалить литералы, не участвующие в процессе вывода, тем самым повышая эффективность работы системы логического вывода.
3. Параллельный алгоритм оценки и отбора вариантов модификации дизъюнктов заключения, позволяющий из всего множества вариантов модификации исходных дизъюнктов выбрать наилучшие в соответствие с выбранным правилом поиска оптимальных решений.
4. Критерии и способы оценки эффективности работы системы и машины логического вывода модифицируемых заключений, учитывающие особенности логического вывода делением дизъюнктов, выбранную степень параллелизма, архитектуру ЭВМ, виды модификации заключения.
5. Параллельная система логического вывода модифицируемых заключений на основе машины параллельного логического вывода, способная выполнять основные виды логического вывода, а также логический вывод модифицируемых заключений. Внедрение результатов исследования. Полученные теоретические и практические результаты использованы в НИР «Теория и применение логического вывода с модификацией заключений» (грант Министерства Образования РФ Е02-2.0-93), в НИР «Разработка среды декларативного логического программирования для кластерной вычислительной системы» (ВятГУ, НИР №412). Учебная программа логического вывода внедрена в учебный процесс в Вятском государственном и Вятском государственном гуманитарном университетах.
Апробация работы. Основные положения и результаты исследования докладывались и обсуждались на 5-й международной конференции «Interactive Systems: The Problems of Human-Computer Interaction» («Интерактивные системы: Проблемы взаимодействия человек - компьютер»), Ульяновск, УлГТУ, 2003; 9-й «Национальной конференции по Искусственному Интеллекту КИИ-2004», Тверь, 2004; Всероссийской ежегодной научно-технической конференции ВятГУ «Наука-производство-технологии-экология», Киров (2004,2007,2008 гг.)
Публикации. Результаты исследования представлены в 13 работах, из них 11 статей, 2 тезисов докладов. Четыре работы опубликованы в научных изданиях, рекомендуемых ВАК для опубликования основных научных результатов диссертации (три работы в российских изданиях и одна в зарубежном).
Структура и объем исследования. Диссертационная работа состоит из введения, четырех глав, заключения, списка сокращений, библиографического списка (включающего 163 наименования) и 2 приложений. Основная часть работы изложена на 170 страницах и содержит 33 рисунка и 5 таблиц.
