Содержание к диссертации
Введение
Глава 1. Принципы функционирования продукционных баз знаний 8
1.1. Системы продукций 8
1.2. Формальное определение продукции 11
1.3. Логический вывод в продукционных системах 17
1.4. Области применения продукционных систем 22
1.6. Выводы к первой главе 32
Глава 2. Модели представления продукционных баз знаний на ЭВМ 33
2.1. Синтаксис продукционной базы знаний 33
2.2. Модель представления продукционной базы знаний на ЭВМ, адаптированная для реализации обратной цепочки рассуждений 35
2.3. Модель представления продукционной базы знаний на ЭВМ, адаптированная для реализации прямой цепочки рассуждений 50
2.4. Обобщенная модель представления продукционных правил на ЭВМ .60
2.5. Программный комплекс «Интеллектуальный помощник» 65
2.6. Выводы ко второй главе 66
Глава 3. Контроль продукционных баз знаний 68
3.1. Методы контроля продукционных БЗ 68
3.2. Противоречивость .. 70
3.3. Полнота 77
3.4. Избыточность.. 86
3.5. Выводы к третьей главе 91
Заключение 93
Приложение 1 95
Библиографический список
- Формальное определение продукции
- Области применения продукционных систем
- Модель представления продукционной базы знаний на ЭВМ, адаптированная для реализации обратной цепочки рассуждений
- Противоречивость
Введение к работе
Актуальность темы. Системы баз знаний давно признаны одним из самых эффективных инструментов в проектировании информационных систем различного назначения, в том числе, систем управления, экспертных систем и т.д. При этом большая часть систем, встречающихся на практике, используют продукционную модель как наиболее подходящую для решения практических задач. Термин «продукция» введен Е. Постом. Модель использует представление знаний правилами вида ЕСЛИ ... ТО. Теоретическое обоснование принципов функционирования продукционных систем, описание продукционной модели и традиционных алгоритмов логического вывода было осуществлено в работах таких зарубежных и отечественных ученых как Фейгенбаум Е., Ныоэлл А., Саймон М., Поспелов Д.А., Ларичев О.И., Вагин В.Н., Попов Э.В., Стефанюк В.Л., Кирсанов Б.С. и другие.
Основным недостатком продукционных систем является резкое замедление проведения логического вывода при росте числа правил в базе знаний. При этом именно в системах, работающих в режиме реального времени, ключевую роль играет скорость обработки информации. Поэтому разработка математических моделей представления знаний, ускоряющих работу продукционных систем, является важной, актуальной и практически значимой задачей.
Предметом исследования является продукционная база знаний.
Цели и задачи исследования. Целью диссертации является разработка математических моделей и алгоритмов для ускорения вывода знаний в продукционных системах.
Для достижения указанной цели поставлены и решены следующие задачи:
разработка новой математической модели представления продукционных баз знаний;
разработка и обоснование для предложенной математической модели новых, более совершенных алгоритмов проведения логического вывода и проверки продукционных баз знаний на полноту и избыточность;
доказательство корректности и эффективности разработанных алгоритмов.
Методы исследований. В работе использованы методы теории управления, теории искусственного интеллекта, теории графов, теории алгоритмов, теории формальных языков и грамматик.
Научная новизна. В работе впервые получены следующие результаты:
разработана новая математическая модель представления продукционных баз знаний на ЭВМ, существенно ускоряющая проведение логического вывода, отличающаяся тем, что представляет собой гиперграф специального вида объединяющего в себе все сущности и зависимости, представляемые в БЗ;
в рамках предложенной математической модели разработаны специальные, более совершенные, чем ранее известные, алгоритмы прямого и обратного вывода, отличающиеся тем, что осуществляют поиск на полученном гиперграфе;
предложены новые, более совершенные алгоритмы проверки продукционной базы знаний, построенной на основе предложенной в диссертации математической модели, на полноту и избыточность. Алгоритмы выполняют автоматическое разбиение правил из БЗ на группы и, анализируя каждую группу отдельно, позволяют определить недостающие для полноты правила, или пары дублирующих друг друга правил;
разработан алгоритм поиска циклических зависимостей на указанной математической модели, представляющий собой поиск циклов в приведенном гиперграфе;
на основе полученных оценок вычислительной (временной и емкостной) сложности предложенных в диссертации алгоритмов работы продукционной системы доказано, что работа системы на предложенной математической модели эффективнее, чем основанная на существующих представлениях, что также подтверждается статистическими данными, полученными на основе проведенных экспериментов.
Практическая ценность основных результатов диссертационного исследования связана с созданием типового математического и программного обеспечения, используемого при оперативном управлении производственными процессами предприятия. Реализованная на основе предложенных в диссертации разработок оболочка продукционной системы используется в учебном процессе на факультете компьютерных наук и информационных технологий Саратовского государственного университета.
Тема диссертации непосредственно связана с приоритетными направлениями развития науки и техники в Российской Федерации, а также с критическими технологиями в следующих разделах и пунктах. Приоритетные направления развития науки, технологий и техники в Российской Федерации. 04 Информационно-телекоммуникационные системы
Перечень критических технологий Российской Федерации. 01 Базовые и критические военные, специальные и промышленные
технологии 23 Технологии создания интеллектуальных систем навигации и
управления
Кроме того, диссертационная работа соответствует темам основных научных исследований, проводимых в течение ряда лет на кафедре
математической кибернетики и компьютерных наук Саратовского государственного университета (темплан НИР, выполняемый по 47). Положения, выносимые на защиту:
Модель представления продукционных баз знаний для реализации прямой цепочки рассуждений позволяет существенно ускорить проведение обратного логического вывода. Модель представляет собой гиперграф специального вида, объединяющий в себе все сущности и зависимости, представляемые в БЗ.
Алгоритм прямого вывода, разработанный для предложенной модели, функционирует эффективнее алгоритмов вывода при традиционном представлении БЗ. Алгоритм производит вывод, реализуя поиск в предложенном гиперграфе.
Модель представления продукционных баз знаний на' ЭВМ, разработанная для реализации обратной цепочки рассуждений, позволяет существенно ускорить проведение прямого логического вывода. Модель представляет собой гиперграф специального вида, объединяющий в себе все сущности и зависимости, представляемые в БЗ.
Алгоритм обратного вывода, разработанный для предложенной модели, функционирует эффективнее алгоритмов вывода при традиционном представлении БЗ. Алгоритм производит вывод, реализуя поиск в предложенном гиперграфе.
Алгоритм проверки продукционной БЗ на полноту на предложенной модели. Алгоритм выполняет автоматическое разбиение правил из БЗ на группы и, анализируя каждую группу отдельно, позволяет определить недостающие для полноты правила.
Алгоритм проверки БЗ на избыточность на предложенной модели. Алгоритм выполняет автоматическое разбиение правил из БЗ на группы и, анализируя каждую группу отдельно, позволяет определить пары дублирующих друг друга правил.
Все результаты, вошедшие в диссертационную работу, получены соискателем самостоятельно.
Апробация. Результаты работы докладывались и обсуждались на следующих конференциях:
«Экспертные и обучающие системы» (Саратов, 1995);
Международные конференции «Компьютерные науки и информационные технологии», посвященные памяти проф. А.М. Богомолова (Саратов, 2002,2007);
5-ый международный симпозиум «Актуальные проблемы машиностроения и механики сплошных и сыпучих сред» (Москва, 2003);
Ежегодные научные конференции профессорско-преподавательского состава СГУ (Саратов, 2003-2007);
Научно-техническая конференция «Информационные системы и технологии 2007» (Обнинск 2007);
Международная конференция «Интеллектуальные системы» (Дивноморск, 2007).
Публикации. По результатам работы опубликовано 12 работ, одна из которых в соавторстве.
Формальное определение продукции
Определения продукции, приводимые в разных источниках, иногда существенно отличаются друг от друга.
Термин «продукция» был впервые введен Е. Постом [101], который под продукцией понимал некое преобразование строки символов. Оно обычно записывается в виде a .. -» b]b2...bn, где a,-, bj -любые, возможно повторяющиеся, символы некоторого заданного алфавита. Правило понимается так: если в строке содержится a .. , то ее следует заменить подстрокой bib2...bn.
В дальнейшем значение этого термина было расширено и относилось не только к последовательностям символов. Следующее определение продукции встречается в работе Д.А. Поспелова [54]. В общем виде под продукцией понимается выражение следующего вида: Q;P;A= B;N. Элемент Q характеризует сферу применения продукции. Разделение знаний на отдельные сферы позволяет экономить время на поиск нужных знаний. Основным элементом продукции является ее ядро А= В. Обычное прочтение ядра продукции выглядит так: «если А то В». В части «если» описано условие применения правила, в части «то» - заключение, которое делается в случае применения правила. Элемент Р есть условие применимости ядра продукции, обычно представляющее собой логическое выражение, разрешающее или запрещающее использование ядра. Элемент N описывает постусловие продукции. Это может быть, например, процедура, которую необходимо выполнить, если продукция была применена.
Такое определение хоть и дает объяснение понятию продукции, но не является достаточным образом формализованным.
В работах А.В. Жожикашвили и В.Л. Стефанюка [21-22] дается следующее формальное описание продукций.
Прежде всего, продукция действует на множестве ситуаций, получая в качестве исходных данных одну ситуацию и порождая в результате своих действий другую. Множество всех ситуаций, которые могут возникнуть при работе системы, обозначается символом S. Это множество синтаксически корректных ситуаций, а не тех, которые реально могут возникнуть.
Продукция рассматривается как объект, состоящий из двух однотипных частей. Первая часть - описание ситуации, к которой продукция может быть применима. Вторая - описание ситуации, которая возникает после ее применения.
При таком подходе при применении продукции к какой-то ситуации возникает некоторая другая ситуация. Ведь обе части продукции - это описание некоторых корректных ситуаций, то есть ничего, кроме корректной ситуации, в результате применения продукции возникнуть не может.
Однако возникает вопрос, как понимать описание ситуации. Если под описанием понимать точное описание конкретной ситуации, получим продукцию, которая применима только в одной этой ситуации. Ценность такой продукции будет невелика. В реальных системах каждая продукция применима к целому множеству ситуаций, возможно, даже бесконечному.
Такое обобщенное описание ситуации называется шаблоном ситуации или просто шаблоном. Грубо говоря, шаблон - это описание ситуации, в котором опущены некоторые несущественные в данный момент детали. Эти детали можно определять произвольно, при этом будут получаться различные ситуации, подходящие под данный шаблон. Такое доопределение элементов ситуации, опущенных в шаблоне, называется конкретизацией шаблона. Проверку того, подходит ли конкретная ситуация под шаблон, называется сопоставлением ситуации с шаблоном. Таким образом, ситуация сопоставима с шаблоном, если шаблон может быть конкретизирован так, чтобы в результате получилась эта ситуация. Так, конкретизацией обобщенного описания, соответствующего левой части продукции aia2...am -» bjb2...bn, является приписывание некоторых последовательностей символов (включая пустые последовательности) слева и справа к последовательности а г-.-ат- В результате такого приписывания получается некоторая строка, к которой данная продукция применима.
Конкретизация шаблона состоит в добавлении к нему некоторой информации. Такая информация называется конкретизатором. Конкретизация шаблона с помощью различных конкретизаторов превращает этот шаблон в различные ситуации. Для каждого шаблона можно определить множество всех возможных конкретизаторов. Поскольку конкретизатор левой части продукции a .-.am -» bib2...bn - пара строк, приписываемых слева и справа, то если S -множество всех строк, то множеством конкретизаторов данного образца является множество X = S х S.
Продукцией называется пара шаблонов, имеющих одно и то же множество конкретизаторов. Эти образцы по традиции называются левой и правой частью продукции. Продукция называется применимой в некоторой ситуации, если эта ситуация сопоставима с ее левой частью. Результатом применения продукции будет ситуация, являющаяся конкретизацией ее правой части с помощью того же конкретизатора, который был использован для конкретизации левой части при сопоставлении.
Области применения продукционных систем
Начиная с 80-х годов, широкое применение информационных технологий является одним из направлений повышения эффективности производства. При этом особое внимание уделяется созданию систем управления производственными процессами, сочетающих использование формализованных моделей и методов традиционных систем управления, с интеллектуальными средствами, основанными на знаниях [1,57, 73-75].
Рассмотрим наиболее часто используемые системы управления производственными процессами.
1. Система диспетчерского управления и сбора данных SCADA (Supervisory Control And Data Acquisition).
Под термином SCADA понимают инструментальную программу для разработки программного обеспечения автоматических систем управления технологическими процессами в реальном времени и удаленного сбора данных.
Основными задачами, решаемыми SCADA-системами, являются: - обмен данными с устройствами связи с объектом, т.е. с промышленными контроллерами и платами ввода/вывода в режиме реального времени; - обработка информации в режиме реального времени; - предоставление информации пользователю в понятной и удобной для него форме; - аварийная сигнализация и управление тревожными сообщениями; - подготовка и генерирование отчетов о ходе технологического процесса. На рис. 1.5 изображена типовая функциональная схема SCADA-системы. Однако использование SCADA систем сопряжено с рядом сложностей: - выбор системы представляет собой достаточно трудную задачу, аналогичную принятию решений в условиях многокритериальное, усложненную невозможностью количественной оценки ряда критериев из-за недостатка информации; - подготовка специалистов по разработке и эксплуатации систем управления на базе программного обеспечения SCADA представляет собой трудоемкий процесс, требующий серьезных финансовых затрат. В основном такая подготовка осуществляется на специализированных курсах различных фирм, курсах повышения квалификации и т.п.; - недостаток специальной литературы по SCADA-системам (имеются лишь отдельные статьи и рекламные проспекты) [2, 104].
Основными задачами, решаемыми MRP-системами, являются: удовлетворение потребности в материалах, компонентах и продукции для планирования производства и доставки потребителям; поддержка низких уровней запасов; планирование производственных операций, расписаний доставки, закупочных операций. Однако использование MRP-систем не лишено ряда недостатков: - значительный объем вычислений и предварительной обработки данных; - нечувствительность к кратковременным изменениям спроса; - большое количество отказов из-за большой размерности системы и ее комплексности [8].
3. Система планирования ресурсов предприятия MRP II (Manufacturing resource planning).
Система MRP II является дальнейшим развитием стандарта MRP. Задачей этой системы является оптимальное формирование потока материалов (сырья), полуфабрикатов (в том числе находящихся в производстве) и готовых изделий. Система класса MRP II - имеет целью интеграцию всех основных процессов, реализуемых предприятием, и служит для выполнения следующих функций: - планирование продаж и производства; - управление спросом; - составление плана производства; - планирование материальных потребностей; - спецификации продуктов; - управление складом; - плановые поставки; - управление на уровне производственного цеха; - планирование производственных мощностей; - контроль входа/выхода; - материально-техническое снабжение; - планирование ресурсов распределения; - планирование и контроль производственных операций; - управление финансами; - моделирование; - оценка результатов деятельности. На рис. 1.7 изображена типовая функциональная схема MRP II-системы. Недостаток системы заключается в ее сложности. Логика построения алгоритма MRP II основана на проведении множества вычислений, что означает необходимость развитой информационной системы. Кроме того, весьма высокие требования предъявляются к точности информации о состоянии предприятия, поставляемой в систему [8]. 4. Система планирования ресурсов предприятия ERP (Enterprise Resource Planning).
Модель представления продукционной базы знаний на ЭВМ, адаптированная для реализации обратной цепочки рассуждений
Обратный логический вывод реализует поиск от цели к данным. Традиционный алгоритм обратного ЛВ функционирует следующим образом. Сначала у пользователя запрашивается цель консультации, т.е. имя объекта, значение которого необходимо получить. Из базы знаний выбираются правила, в части «то» которых находится требуемый объект. Затем все части «если» выбранных правил сравниваются с содержимым рабочей области.
При обнаружении наличия всех элементов части «если» некоторого правила в рабочей области, правило выполняется и искомый объект получает определенное сработанным правилом значение. Если в процессе сравнении обнаружится объект, значение которого не известно, необходимо сначала установить его значение по этому же алгоритму, а затем вернуться к установлению значения исходного объекта. Очевидно, что многочисленные сравнения сильно замедляют работу алгоритма.
Предлагаемый ниже способ представления продукционной БЗ в виде мультиграфа специального вида существенно ускоряет работу ЛВ и позволяет повысить эффективность работы ПС [26,28,31,32].
Модель продукционной БЗ автором предлагается представить в виде конечного мультиграфа G=(VJZ), где V- множество вершин, а Е - множество дуг. Множество является объединением двух непересекающихся множеств: множества О вершин-объектов и множества В вершин-ветвлений. Таким образом, V=OKJB. Каждая вершина-объект ot соответствует конкретному объекту предметной области, для которой создана используемая БЗ.
Остановимся подробнее на том, каким образом продукционная БЗ будет представлена мультиграфом G. Пусть объект oj имеет разрешенные значения оц, о{:2, ... oi„\, о2 - оц, 02,2, 2» и т.д. В дальнейшем множество разрешенных значений для о будем обозначать через leg(ok), т.е. leg{Ok)={okl\, Ок,2, к,пк) Пусть продукция Р имеет вид: TO 0/=//,// Из структуры продукции видно, что она является объединением нескольких ШИТ-компонент, каждая из которых представлена набором пар (оь kit)» соединенных логической связкой И. Каждый набор пар, составляющий Я/7#-компоненту, далее интерпретируется как вершина-ветвление Ь. Множество всех вершин-ветвлений и есть упомянутое выше множество В.
Опишем теперь тип вершин мультиграфа G, составляющих множество О. Вершина-объект о є 9 является иерархической. Сама она считается вершиной нулевого уровня. В ее состав входит конечное число вершин 1-го уровня /jfci, 4,2, ..., lk,nh взаимно однозначно соответствующих возможным значениям объекта о .
Приведенной выше продукции Р в мультиграфе G=(V, Е) будет соответствовать подграф, конструируемый следующим образом.
Вначале среди вершин множества О выбирается вершина о,, которая фигурирует в части «ТО» продукции Р. Из вершины 1-го уровня этой вершины-объекта ltM проводятся дуги во все вершины-ветвления, порожденные продукцией Р.
Пусть Ь={{о\=1ц\\...,(k=h,ik)} является одной из упомянутых вершин-ветвлений. Для каждой пары (Oj=ljjj), где j=l,...,k, из этой вершины проводится дуга в вершину 1-го уровня Ijjj вершины-объекта о,-. Если в объекте Oj значение Ipj отсутствует, это свидетельствует об ошибке в описании продукции Р. Аналогичные построения проводятся для всех остальных вершин-ветвлений.
Противоречивость
Одной из важнейших проблем является проблема выявления разного рода противоречий в продукционной БЗ. По мнению Попова Э.В., Поспелова И.Г., Поспеловой Л.Я. противоречивость, «размытость» самой предметной области, наличие в ней исключений является источником ошибок при формировании БЗ [47,55].
Попытка создать инструмент выявления всевозможных противоречий описана в работе, классифицирующей противоречия в системе продукций и предлагающей некоторые способы их выявления на основе динамического описания систем продукций и введения понятия «множества достижимости продукционных систем».
Целью работы продукционной системы является нахождение цепочки, выводящей факт, интересующий пользователя, из некоторой цепочки исходных фактов. Каждая продукция в цепочке вывода устанавливает новый факт, т.е. расширяет набор исходных фактов. Применимость той или иной продукции не зависит от того, какие продукции выполнялись на предыдущих этапах, а зависит только от набора фактов, установленных системой. Это обстоятельство позволило Поспелову И.Г. и Поспеловой Л.Я. [55] рассматривать набор установленных на некотором этапе вывода фактов как состояние ПС, а продукции - как операторы, изменяющие это состояние. Введенные состояния описываются векторами Х={х\, Xi, ..., хп} из нулей и единиц, х=\, если факт/из списка F уже установлен, =0 - в противном случае. Продукция превращает состояние X в новое состояние Y=RX. Если условия продукции не выполнены, то состояние не изменяется. Рассматривая продукции, как операторы, изменяющие состояния, предлагается считать процесс вывода эволюцией динамической систем X=Rt, где X - состояние перед этапом t,a.Rt- применяемая на этапе t продукция.
Множество состояний Yk(X), достижимых не более чем за к шагов из какого-либо состояния множества, определяется как Yi{X)=Y1(YjC.}(X)), к \, где Yi(X)={y\(yeX)(reR)(xeX)(y=rx)} определяет совокупность всех состояний, которые можно получить из хєХие более чем за один шаг.
В работах содержательно показана возможность неверного решения, выдаваемого ПС за счет так называемого противоречия предметной области. Если все факты, которыми оперирует ПС, могут быть верны одновременно, то никаких противоречий в ней не возникнет. Противоречия возникают из-за содержательных связей между фактами, которые запрещают некоторые связи. В некоторых предметных областях существуют несовместимые системы взглядов, причем эта несовместимость может проявляться не сразу. Так, например, происходит в приведенном выше примере про летучую мышь.
Поспеловым И.Г. и Поспеловой Л.Я. предлагается следующее формальное описание противоречий в ПС.
Для выявления противоречий в ПС, необходимо описать (аксиоматически) содержательные связи между фактами из F и на основе этого выделить множество допустимых состояний X, которые сами по себе не могут быть логически противоречивыми (то есть необходимо, чтобы вместе с состоянием х в X входили и все его логические следствия и є X). Остальные состояния считаются недопустимыми и вывод любого из них, рассматривается как противоречие.
Любой вывод представляется как соединение независимых линий рассуждения (составных продукций) Q,. г и ... r(x=Qk ... Qjx, QiQjx=QjQjx для любого х. При этом:
а) Если каждая цепочка Qt работает, а цепочка Qi...Qm нет, то это означает, что каждая линия рассуждения имеет свою область применимости, а все они одновременно не применимы.
б) Если же не работает некоторая составная продукция Q, то это говорит о некотором дефекте в БЗ.
Учитывая вышесказанное, в работе введены базовые понятия непротиворечивости. Полной непротиворечивостью называется такое состояние системы продукций, если из всех допустимых состояний можно вывести только допустимые Yi(X)=X.
В работах Долининой О.Н. [13-16] разработан метод построения тестов для продукционной БЗ и введено понятие «забывание об исключении». Существует набор фактов /} ... f„, при одновременной установке которых логические следствия г І ... Гк не имеют место.
Доказывается, что ошибками типа «забывание об исключениях» исчерпываются ошибки в продукционных системах. Разработан алгоритм генерации тестов для продукционных БЗ [13,15].
Проверка базы знаний на наличие противоречий представляется сложной задачей, т.к. требует рассмотрение семантического значения содержимого баз знаний. В общем случае объект может принимать несколько значений (например, в случае консультации по поводу покупки какой-либо вещи или диагностировании какого-либо устройства). При наличии нечетких знаний результатом консультации могут стать даже противоположные по смыслу значения, выведенные с разным коэффициентом достоверности (например, ответ «да» с вероятностью 30% и «нет» с вероятностью 70%). Поскольку продукционные системы создаются, в основном, для трудно формализуемых областей человеческой деятельности, подобную задачу не удастся полностью переложить на ЭВМ. Необходимо присутствие эксперта-человека. Однако с рассмотрением отдельных аспектов проверки на наличие в базе знаний противоречий машина может справиться.
Тем не менее, и в этой хорошо исследованной области имеются аспекты, рассмотрению которых не уделялось должного внимания. Одним из возможных источников ошибок является наличие циклических зависимостей, когда используя значение некоторого объекта путем проведения логического вывода можно получить какое-нибудь значение (возможно то же самое) этого же объекта, (рис. 3.2) Это говорит либо о появлении ошибки, либо о наличии ряда эквивалентных утверждений вида «Если А то В» и «Если В то А» или более длинных цепочек. Для проведения поиска циклических зависимостей нами предлагается алгоритм поиска фундаментального множества циклов [11,24, 30,38]. В применении к модели, адаптированной к обратному логическому выводу, этот алгоритм будет выглядеть следующим образом.
Похожие диссертации на Математические модели и алгоритмы функционирования продукционных баз знаний
