Математические модели и алгоритмы функционирования продукционных баз знаний
На правах рукописи
ИВАНОВ АЛЕКСАНДР СЕРГЕЕВИЧ
МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ ФУНКЦИОНИРОВАНИЯ ПРОДУКЦИОННЫХ БАЗ ЗНАНИЙ
05.13.18 – Математическое моделирование, численные методы и комплексы программ
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата физико-математических наук
Саратов – 2007
Работа выполнена в ГОУ ВПО «Саратовский государственный университет им. Н.Г. Чернышевского»
Научный руководитель: доктор технических наук, профессор
Сперанский Дмитрий Васильевич
Официальные оппоненты: доктор технических наук, профессор
Кушников Вадим Алексеевич
кандидат физико-математических наук, доцент Сагаева Ирина Дмитриевна
Ведущая организация: Санкт-Петербургский университет
информационных технологий, механики и оптики
Защита диссертации состоится 23 января 2008 г. в 15:00 часов на заседании диссертационного совета Д 212.242.08 при ГОУ ВПО «Саратовский государственный технический университет» по адресу: 410054, г.Саратов, ул. Политехническая, 77, Саратовский государственный технический университет, корп. 1, ауд. 319.
С диссертацией можно ознакомиться в научно-технической библиотеке ГОУ ВПО «Саратовский государственный технический университет».
Автореферат разослан декабря 2007 г.
Ученый секретарь
диссертационного совета Терентьев А.А.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Системы баз знаний давно признаны одним из самых эффективных инструментов в проектировании информационных систем различного назначения, в том числе систем управления, экспертных систем и т.д. При этом большая часть систем, встречающихся на практике, используют продукционную модель как наиболее подходящую для решения практических задач. Термин «продукция» введен Е. Постом. Модель использует представление знаний правилами вида ЕСЛИ … ТО. Теоретическое обоснование принципов функционирования продукционных систем, описание продукционной модели и традиционных алгоритмов логического вывода было осуществлено в работах таких зарубежных и отечественных ученых как Фейгенбаум Е., Ньюэлл А., Саймон М., Поспелов Д.А., Ларичев О.И., Вагин В.Н., Попов Э.В., Стефанюк В.Л., Кирсанов Б.С. и другие.
Основным недостатком продукционных систем является резкое замедление проведения логического вывода при росте числа правил в базе знаний. При этом именно в системах, работающих в режиме реального времени, ключевую роль играет скорость обработки информации. Поэтому разработка математических моделей представления знаний, ускоряющих работу продукционных систем, является важной, актуальной и практически значимой задачей.
Предметом исследования является продукционная база знаний.
Цель и задачи исследования. Целью диссертации является разработка математических моделей и алгоритмов для ускорения вывода знаний в продукционных системах.
Для достижения указанной цели поставлены и решены следующие задачи:
- разработка новой математической модели представления продукционных баз знаний;
- разработка и обоснование для предложенной математической модели новых, более совершенных алгоритмов проведения логического вывода и проверки продукционных баз знаний на полноту и избыточность;
- доказательство корректности и эффективности разработанных алгоритмов.
Методы исследований. В работе использованы методы теории управления, теории искусственного интеллекта, теории графов, теории алгоритмов, теории формальных языков и грамматик.
Научная новизна. В работе впервые получены следующие результаты:
- разработана новая математическая модель представления продукционных баз знаний, существенно ускоряющая проведение логического вывода, отличающаяся тем, что представляет собой гиперграф специального вида, объединяющего в себе все сущности и зависимости, представляемые в базе знаний;
- в рамках предложенной математической модели разработаны специальные, более совершенные, чем ранее известные, алгоритмы прямого и обратного вывода, отличающиеся тем, что осуществляют поиск на полученном гиперграфе;
- предложены новые, более совершенные алгоритмы проверки продукционной базы знаний, построенной на основе предложенной в диссертации математической модели, на полноту и избыточность, отличающиеся тем, что выполняют автоматическое разбиение правил из базы знаний на группы и, анализируя каждую группу отдельно, позволяют определить недостающие для полноты правила или пары дублирующих друг друга правил;
- разработан алгоритм поиска циклических зависимостей на указанной математической модели, представляющий собой поиск циклов в приведенном гиперграфе;
- на основе полученных оценок вычислительной (временной и емкостной) сложности предложенных в диссертации алгоритмов работы продукционной системы доказано, что работа системы на предложенной математической модели эффективнее, чем основанная на существующих представлениях, что также подтверждается статистическими данными, полученными на основе проведенных экспериментов.
Практическая ценность основных результатов диссертационного исследования связана с созданием типового математического и программного обеспечения. Оно может использоваться при оперативном управлении производственными процессами предприятия, в экспертных системах и др. Реализованный на основе предложенных в диссертации разработок комплекс программ «интеллектуальный помощник» используется в учебном процессе на факультете компьютерных наук и информационных технологий Саратовского государственного университета.
Тема диссертации непосредственно связана с приоритетными направлениями развития науки и техники в Российской Федерации, а также с критическими технологиями в следующих разделах и пунктах.
Приоритетные направления развития науки, технологий и техники в Российской Федерации.
04 Информационно-телекоммуникационные системы
Перечень критических технологий Российской Федерации.
01 Базовые и критические военные, специальные и промышленные технологии
23 Технологии создания интеллектуальных систем навигации и управления
Кроме того, диссертационная работа соответствует темам основных научных исследований, проводимых в течение ряда лет на кафедре математической кибернетики и компьютерных наук Саратовского государственного университета (темплан НИР, выполняемый по §47).
Положения, выносимые на защиту:
- Модель представления продукционных баз знаний для реализации прямой цепочки рассуждений позволяет существенно ускорить проведение прямого логического вывода. Модель отличается тем, что представляет собой гиперграф специального вида, объединяющий в себе все сущности и зависимости, представляемые в базе знаний.
- Алгоритм прямого вывода, разработанный для предложенной модели, функционирует эффективнее алгоритмов вывода при традиционном представлении баз знаний. Алгоритм производит вывод, реализуя поиск в предложенном гиперграфе.
- Модель представления продукционных баз знаний, разработанная для реализации обратной цепочки рассуждений, позволяет существенно ускорить проведение обратного логического вывода. Модель отличается тем, что представляет собой гиперграф специального вида, объединяющий в себе все сущности и зависимости, представляемые в базах знаний.
- Алгоритм обратного вывода, разработанный для предложенной модели, функционирует эффективнее алгоритмов вывода при традиционном представлении баз знаний. Алгоритм производит вывод, реализуя поиск в предложенном гиперграфе.
- Алгоритм проверки продукционной базы знаний на полноту на предложенной модели выполняет автоматическое разбиение правил из базы на группы и, анализируя каждую группу отдельно, позволяет определить недостающие для полноты правила.
- Алгоритм проверки базы знаний на избыточность на предложенной модели отличается тем, что выполняет автоматическое разбиение правил из базы знаний на группы и, анализируя каждую группу отдельно, позволяет определить пары дублирующих друг друга правил.
Все результаты, вошедшие в диссертационную работу, получены соискателем самостоятельно.
Апробация. Результаты работы докладывались и обсуждались на следующих конференциях: Международной конференции «Экспертные и обучающие системы» (Саратов, 1995); Международных конференциях «Компьютерные науки и информационные технологии», посвященных памяти проф. А.М. Богомолова (Саратов, 2002, 2007); 5-м Международном симпозиуме «Актуальные проблемы машиностроения и механики сплошных и сыпучих сред» (Москва, 2003); ежегодных научных конференциях профессорско-преподавательского состава СГУ (Саратов, 2003-2007); научно-технической конференции «Информационные системы и технологии 2007» (Обнинск, 2007); Международной конференции «Интеллектуальные системы» (Дивноморск, 2007).
Публикации. По результатам работы опубликовано 12 работ, одна из которых в соавторстве.
Структура и объем диссертации. Диссертация содержит 117 страниц, состоит из введения, трех основных глав, приложения и списка использованной литературы.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность диссертационного исследования автора, формулируются цели и задачи исследования.
В первой главе приведен обзор известных и используемых в настоящее время принципов организации и функционирования продукционных систем, проанализированы их достоинства и недостатки.
На основе проведенного анализа современного состояния продукционных систем сформулированы возможные направления их совершенствования, которые и реализованы в последующих главах диссертации.
В этой главе также рассматриваются возможности использования продукционных систем в современных комплексах программных средств систем управления предприятием, центром управления сетями и др.
Основное содержание диссертационной работы составляют вторая и третья ее главы.
Во второй главе предлагаются модели представления продукционных баз знаний, разработанные для прямого и обратного логического вывода.
Механизм или аппарат логического вывода продукционной модели циклически выполняет 4 этапа: выборку, сопоставление, разрешение конфликта, действие (рис. 1).
На каждом из перечисленных этапов интерпретатор работает с базой знаний и рабочей памятью.
Схему одного цикла работы интерпретатора можно описать следующим образом:
Этап выборки. На этапе выборки производится активизация той части данных и знаний, на основании которых может быть реализован запрос пользователя.
Рис. 1
Этап сопоставления. Выбранное на предыдущем этапе множество активных правил Рv приводится в соответствие выбранному множеству элементов рабочей памяти Fv и определяется конфликтный набор правил, то есть правил из Рv и данных из Fv, на которых эти правила определены.
В результате сопоставления получается конфликтный набор {Pi, Pj, …, Pk}.
Этап сопоставления требует проведения значительного количества операций, так как для конфликтного набора следует проверить все условия активных правил на всех сочетаниях активных элементов рабочей памяти. В связи с тем, что скорость работы является одной из главных проблем продукционных систем, необходимо обеспечить эффективность операции сопоставления в условиях большого количества правил и данных.
Этап разрешения конфликтов. В ходе разрешения конфликта интерпретатор выбирает одну или несколько продукций, которые должны быть выполнены в текущем цикле.
Этап выполнения. Этот этап заключается в активизации выбранных правил и внесении соответствующих изменений в рабочую память.
Модель продукционной БЗ предлагается представить в виде конечного мультиграфа G=(V,E), где V - множество вершин, а E – множество дуг. Множество V является объединением двух непересекающихся множеств: множества О вершин-объектов и множества В вершин-ветвлений. Таким образом, V=OB. Каждая вершина-объект oi соответствует конкретному объекту предметной области, для которой создана используемая БЗ.
В существующих продукционных системах условия и заключения правил представляются в виде троек <объект, атрибут, значение>. В данной работе во всех рассматриваемых моделях будет говориться только о парах <атрибут объекта, значение>. В дальнейшем элементы модели, описывающие атрибуты одного и того же объекта, можно объединить в общую группу. Это позволит ускорить процесс поиска элемента в модели, так как нам вместо того, чтобы просматривать все атрибуты всех объектов в поисках нужного, придется сначала отыскать объект, а затем, среди его атрибутов, требуемый атрибут. Далее будем говорить только об объектах, подразумевая при этом атрибуты объектов.
Остановимся подробнее на том, каким образом продукционная БЗ будет представлена мультиграфом G.
Пусть объект о1 имеет разрешенные значения о1,1, о1,2, … о1,n1, o2 – o2,1, о2,2, o2,n2, и так далее. В дальнейшем множество разрешенных значений для ok будем обозначать через leg(ok).
Пусть продукция P имеет вид:
ЕСЛИ o1=l1,i1 И
o2=l2,i2 И
…
ok=lk,ik ИЛИ
o’1=l’1,j1 И
…
o’m=l’m,im ИЛИ
…
ТО оt=lt,it.
Из структуры продукции видно, что она является объединением нескольких ИЛИ-компонент, каждая из которых представлена набором пар (оt, lt,it), соединенных логической связкой И. Каждый набор пар, составляющий ИЛИ-компоненту, далее интерпретируется как вершина-ветвление b. Множество всех вершин-ветвлений и есть упомянутое выше множество B.
Опишем теперь тип вершин мультиграфа G, составляющих множество О. Вершина-объект оkO является иерархической. Сама она считается вершиной нулевого уровня. В ее состав входит конечное число вершин 1-го уровня lk,1, lk,2, …, lk,nk, взаимно однозначно соответствующих возможным значениям объекта ok.
Приведенной выше продукции P в мультиграфе G=(V, E) будет соответствовать подграф, конструируемый следующим образом.
Вначале среди вершин множества О выбирается вершина or, которая фигурирует в части «ТО» продукции P. Из вершины 1-го уровня этой вершины-объекта lr,ir проводятся дуги во все вершины-ветвления, порожденные продукцией P.
Пусть b={(o1=l1,i1),…,(ok=lk,ik)} является одной из упомянутых вершин-ветвлений. Для каждой пары (oj=lj,ij), где j=1,…,k, из этой вершины проводится дуга в вершину 1-го уровня lj,ij вершины-объекта oj. Если в объекте oj значение lj,ij отсутствует, то это свидетельствует об ошибке в описании продукции P. Аналогичные построения проводятся для всех остальных вершин-ветвлений.
Для рассматриваемой в качестве примера продукции P соответствующий ей подграф мультиграфа G=(V, E) изображен на рис. 2.
Рис. 2
Модель БЗ в целом представляет собой объединение всех подграфов описанного вида, каждый из которых соответствует некоторой продукции, входящей в состав БЗ.
Как видно из изложенного, в построенном подграфе имеется два типа дуг. К первому типу относятся дуги, ведущие из вершины-объекта в вершину-ветвление, ко второму – дуги, ведущие из вершины-ветвления в вершину-объект. Условимся дуги первого типа обозначать в виде тройки ((ok, lk,ik), bm), где ok - вершина-объект, lk,ik конкретное значение из множества leg (ok), bm - вершина-ветвление, являющаяся одним из ИЛИ-компонент в продукции P. Отметим, что начало этой дуги однозначно определяется парой (ok, lk,ik). Далее, дуги второго типа условимся обозначать тройкой (bm,(ok, lk,ik)), где bm – вершина-ветвление, из которой исходит дуга, ok - вершина-объект и входящая в ее состав вершина 1-го уровня lk,ik, в которую дуга заходит. При этом должно удовлетворяться следующее условие: среди всех пар, составляющих вершину-ветвление bm, есть пара (ok, lk,ik).
Введем следующие определения.
Вершину-объект о назовем невыводимой, если из нее не исходит дуг первого типа. Все остальные вершины-объекты будем считать выводимыми.
Каждой вершине ok поставим в соответствие множество VL(ok) leg(ok), которое формируется в процессе проведения ЛВ и представляет собой множество установленных значений объекта ok.
Отметим, что для выводимых вершин имеет место следующее утверждение:
(lk,ik ok) ((ok, lk,ik), bj) ( bj, (op, lp, ip)) (lp, ip op).
Условимся, что для невыводимой вершины о множество ее значений VL(о) должно быть запрошено у пользователя до начала ЛВ.
В диссертации разработан алгоритм А1.1 для проведения обратного логического вывода. На вход алгоритма подается стартовая вершина. По окончании его работы множества VL(o) будут содержать в себе результаты проведенного вывода. Если для некоторой вершины-объекта o множество VL(о) пусто, то это означает, что значение для данного объекта при проведении консультации установить не удалось.
На рис. 3 изображен способ представления правил продукций на ЭВМ для проведения логического вывода путем построения обратной цепочки рассуждений.
Рис. 3
Множество всех объектов БЗ будем представлять в виде линейного односвязного списка obj_list вершин-объектов графа G. Каждый элемент списка взаимно однозначно соответствует вершине-объекту модели и включает в себя поля:
- name - название объекта;
- question - вопрос о значении объекта, задаваемый пользователю;
- legal-list – ссылка на список разрешенных значений (соответствует множеству leg);
- value-list – ссылка на список полученных в результате консультации значений (соответствует множеству VL).
Перед началом консультации все списки VL должны быть пусты. Их заполнение будет происходить во время проведения ЛВ.
Список разрешенных значений состоит из двух составляющих:
- legal-value - разрешенного значения;
- or-list - списка ссылок на вершины-ветвления, в которые ведут дуги первого типа, начинающиеся в вершине первого уровня legal_value вершины-объекта name.
Вершина-ветвление на рис. 2 обозначена как and-list и представляет собой список пар вида [объект] = [значение], являющихся частью дуг второго типа, исходящих из данной вершины-ветвления. Каждая пара [объект] = [значение] из списка, в дальнейшем называемая просто парой, есть пара ссылок на соответствующую вершину-объект obj и соответствующее ей разрешенное значение value.
Для предложенных модели и алгоритма доказаны следующие утверждения.
Теорема 2.1. Вычислительная сложность алгоритма А1.1 проведения обратного ЛВ есть величина порядка O(n+t), где n – количество вершин графа, т.е. количество объектов в предметной области, а t – количество ребер графа, т.е. правил в БЗ.
Теорема 2.2. Пусть имеется n объектов, m разрешенных значений для всех объектов, l троек в части «если» продукции и k троек в части «то» продукции. Тогда общее количество ссылок в модели равно О(n+m+l+k).
Приведенная теорема определяет емкостную сложность модели, то есть размеры памяти, требующейся для хранения БЗ. Основу модели составляют ссылки на различные элементы модели. Поэтому размер модели определяется количеством ссылок в ней и пропорционален размеру БЗ.
Для прямого ЛВ аналогичным образом строится модель представления и разрабатывается алгоритм вывода.
Отличия этой и предыдущей модели рассмотрим на списочном представлении. Для реализации этого представления выберем структуру - списки. На рис.4 представлены основные элементы модели и отношения между ними.
Множество всех объектов БЗ будем представлять в виде линейного односвязного списка obj_list вершин-объектов графа G. Каждый элемент списка взаимно однозначно соответствует вершине-объекту модели и включает в себя поля:
- name - название объекта;
- question - вопрос о значении объекта, задаваемый пользователю;
- legal-list – ссылка на список разрешенных значений;
- value-list – ссылка на список полученных в результате консультации значений.
Рис. 4
Перед началом консультации все списки VL должны быть пусты. Их заполнение будет происходить во время проведения ЛВ.
Список разрешенных значений состоит из двух составляющих:
- legal-value - разрешенного значения;
- rule-list - списка ссылок на вершины-ветвления, в которые ведут дуги первого типа, начинающиеся в вершине первого уровня legal_value вершины-объекта name.
Вершина-ветвление обозначена как fact-list и представляет собой два списка. Первый - список пар вида [объект]=[значение], являющихся частью дуг первого типа, входящих в данную вершину-ветвление и пометки окрашенности дуги znach. Второй - список пар вида [объект]=[значение], являющихся частью дуг второго типа, исходящих из данной вершины-ветвления. Принадлежность к одному из этих списков определяется полем If_Then. Если поле имеет значение «истина», то элемент относится к первому списку, если «ложь» - ко второму. Каждая пара [объект]=[значение] из этих списков - это пара ссылок на соответствующую вершину-объект obj и соответствующее ей разрешенное значение value.
Для предложенных модели и алгоритма доказаны следующие утверждения.
Теорема 2.3. Пусть имеется n объектов, m разрешенных значений для всех объектов, l троек в части «если» продукции и k троек в части «то» продукции. Тогда общее количество ссылок равно О(n+m+l+k).
Теорема 2.4. Пусть р – средний размер правила, f – количество участвовавших в выводе правил, а l – количество правил, в части «если» которых присутствует хотя бы один из установленных фактов. Тогда время работы алгоритма А1.2 будет О(f*p*l).
Таким образом, время работы алгоритма А1.2 в худшем случае будет иметь порядок О(t*р*t), где t – общее количество правил в БЗ.
Все предложенные модели и алгоритмы были реализованы программно. Кроме того, для сравнения были реализованы простые алгоритмы ЛВ. В диссертации приведены экспериментальные данные, позволяющие оценить эффект от применения предложенных в диссертации моделей и алгоритмов.
В табл. 1 приведены экспериментальные данные, отражающее время, затраченное на работу рассматриваемых в диссертации алгоритмов обратного ЛВ. Для сравнения приведены три характеристики:
- время, затраченное на конвертирование базы знаний из текстового файла в предложенную модель;
- время, затраченное на проведение ЛВ на предложенной модели;
- время, затраченное на проведение ЛВ без использования предложенной модели.
Поскольку время может колебаться в зависимости от исходных данных, алгоритм выполнялся многократно при различных наборах входных данных. В таблице приводится среднее время. В последнем столбце приведено отношение времени проведения ЛВ на предложенной модели ко времени такого же ЛВ, но без ее использования.
Таблица 1
| Кол-во правил в базе знаний | Кол-во объектов в базе знаний | Время, затрачен-ное на создание модели (мс) | Время проведения ЛВ на предложен-ной модели (мс) | Время проведения традици-онного ЛВ (мс) | Отношение времени проведения традицион-ного ЛВ ко времени ЛВ на модели |
| 5621 | 1728 | 10420 | 17 | 12420 | 731 |
| 2805 | 864 | 3807 | 11 | 2802 | 255 |
| 1397 | 432 | 1560 | 5 | 613 | 123 |
| 693 | 216 | 685 | 2 | 135 | 68 |
| 341 | 108 | 165 | 1 | 33 | 33 |
| 165 | 54 | 70 | 1 | 9 | 9 |
На рис. 5 приведены графики зависимости времени, затраченного на выполнение трех описанных выше алгоритмов, от количества правил в БЗ. На этом рисунке на горизонтальной оси откладывается количество продукционных правил в БЗ, на вертикальной – натуральный логарифм времени, затраченного на выполнение соответствующего алгоритма (время измеряется в миллисекундах).
Рис. 5
В табл. 2 приведены экспериментальные данные, отражающее время, затраченное на работу рассматриваемых алгоритмов прямого ЛВ. Для сравнения приведены четыре характеристики:
- время, затраченное на конвертирование базы знаний из текстового файла в предложенную модель;
- время, затраченное на проведение ЛВ на предложенной модели;
- время, затраченное на проведение ЛВ без использования предложенной модели;
- в последнем столбце приведено отношение времени проведения ЛВ на предложенной модели ко времени такого же ЛВ, но без ее использования.
Таблица 2
| Кол-во правил в базе знаний | Кол-во объек-тов в базе знаний | Время, затрачен-ное на создание модели (мс) | Время проведения ЛВ на предложен-ной модели (мс) | Время проведения традицион-ного ЛВ (мс) | Отношение времени проведения ЛВ на модели ко времени тра-диционного ЛВ |
| 5621 | 1728 | 11423 | 37 | 18420 | 497 |
| 2805 | 864 | 4215 | 19 | 4169 | 219 |
| 1397 | 432 | 1675 | 9 | 952 | 105 |
| 693 | 216 | 737 | 4 | 168 | 42 |
| 341 | 108 | 188 | 1 | 38 | 38 |
| 165 | 54 | 84 | 1 | 8 | 8 |
Рис. 6
На рис. 6 приведены графики зависимости времени, затраченного на выполнение трех описанных выше алгоритмов, от количества правил в БЗ. На этом рисунке на горизонтальной оси откладывается количество продукционных правил в БЗ, на вертикальной – натуральный логарифм времени, затраченного на выполнение соответствующего алгоритма (время измеряется в миллисекундах).
Анализ приведенных экспериментальных данных показывает, что время, затрачиваемое на построение модели, имеет тот же порядок, что и время, необходимое для проведения традиционного логического вывода.
Эти данные также наглядно демонстрируют, что время проведения ЛВ на предложенной модели значительно ниже, чем без ее использования. Отсюда вытекает, что применение такой модели представления продукционной БЗ на ЭВМ позволит существенно повысить эффективность логического вывода.
В третьей главе диссертации рассматриваются вопросы контроля продукционных БЗ.
Работы в области контроля БЗ традиционно ведутся в двух направлениях. Одно из них основано на использовании статического анализа БЗ, когда проверка качества БЗ осуществляется без запуска интерпретатора системы. Второе направление – тестирование БЗ, предполагающее анализ результатов работы машины логического вывода на достаточно большом множестве различных наборов исходных данных.
На различных этапах жизненного цикла продукционных систем источниками ошибок в БЗ являются:
- ошибки, возникающие при непосредственном внесении информации в БЗ пользователем;
- ошибки, появляющиеся в процессе поступления запросов к БЗ непосредственно от пользователя;
- ошибки, возникающие в процессе вывода решения и добавления к БЗ новых знаний;
- ошибки, являющиеся результатом недостаточной проработки предметной области.
Принято выделять следующие основные классы ошибок в продукционных БЗ:
- Избыточность, т.е. наличие нескольких цепочек рассуждений, позволяющих сделать один и тот же вывод.
- Неполнота, т.е. невозможность получения результата при некоторых наборах исходных данных.
- Противоречивость, т.е. возможность при одном и том же наборе исходных данных получить несколько противоречащих друг другу результатов.
Заметим, что в процессе проведения логического вывода может возникнуть ситуация, когда некоторое значение рассматриваемого объекта выражается через какое-либо значение (возможно, то же самое) этого же объекта. Появление такой ситуации говорит либо о появлении ошибки, либо о наличии ряда эквивалентных утверждений вида «Если А то В» и «Если В то А» или более длинных цепочек. В диссертации предложены алгоритмы А3.1 – А3.3 поиска таких циклических зависимостей. Алгоритмы А3.1 и А3.3 рассматривают нахождения некоторого множества циклических зависимостей на моделях для обратного и прямого ЛВ соответственно. Алгоритм А3.2 производит поиск всех возможных циклических зависимостей.
Теорема 3.1. Вычислительная сложность алгоритмов А3.1 и А3.3 равна O(n*t), где n – количество объектов, а t – количество правил в базе знаний.
В этой главе диссертации также предлагаются два алгоритма (А3.4 и А3.5) проверки на неполноту в продукционной базе знаний. Алгоритмы разбивают базы знаний на группы связанных друг с другом знаний. Анализируя каждую группу отдельно, алгоритмы выводят комбинации входных данных, при которых невозможно получение результата. При этом алгоритм А3.5 работает быстрее, чем алгоритм А3.4, но требует больше оперативной памяти. Алгоритм А3.4, напротив, требует оперативной памяти меньшего объема, но он уступает алгоритму А3.5 по быстродействию. Таким образом, пользователю предоставляется возможность выбора подходящего алгоритма в зависимости от критичности двух упомянутых параметров – времени и оперативной памяти.
В этой же главе предложен алгоритм А3.6 проверки БЗ на избыточность. Идея алгоритма заключается в поиске среди множества правил БЗ таких их комбинаций, для которых имеет место теоретико-множественное включение одной в другую. Этот факт является подтверждением избыточности информации.
Для предложенных алгоритмов получены оценки их временной сложности. Пусть в БЗ имеется r объектов, влияющих на целевой объект, причем каждый из этих объектов имеет in (n=1..r) разрешенных значений. Тогда справедливы следующие утверждения.
Теорема 3.2. Время проверки БЗ на полноту алгоритмом А3.4 равно О((
)*H), где H - количество правил, влияющих на данный объект.
Теорема 3.3. Время проверки БЗ на полноту алгоритмом А3.5 равно О(
*r).
Теорема 3.4. Время проверки на избыточность алгоритмом 3.6 равно О(
*r).
В этой же главе диссертации исследованы вопросы оптимизации предложенных выше алгоритмов. В частности, приводятся ситуации, в которых сокращение времени работы приведенных алгоритмов оказывается не только возможным, но и весьма эффективным.
В табл. 3 приведено время работы трех алгоритмов:
- проверки БЗ на полноту полным перебором (алгоритм А3.4);
- проверки БЗ на полноту ускоренный (алгоритм А3.5);
- проверки БЗ на избыточность (алгоритм А3.6).
Так же как и в табл. 1-2 время приводится в миллисекундах. Тестирование проводилось при тех же условиях.
Таблица 3.
| Кол-во правил в базе знаний | Кол-во объектов в базе знаний | Проверка на избыточ-ность (мс) | Проверка на полноту полным перебо-ром (мс) | Проверка на полноту с ускорением (мс) | Сокращение времени проверки на полноту за счет ускорения |
| 5621 | 1728 | 114 | 1198 | 101 | в 11 раз |
| 2805 | 864 | 57 | 403 | 51 | в 8 раз |
| 1397 | 432 | 28 | 158 | 24 | в 7 раз |
| 693 | 216 | 12 | 67 | 12 | в 6 раз |
| 341 | 108 | 7 | 32 | 6 | в 6 раз |
| 165 | 54 | 4 | 16 | 3 | в 5 раз |
На рис. 7 приведены графики зависимостей времени выполнения алгоритмов А3.4, А3.5 и А3.6 от количества правил в БЗ.
Рис.7
Приведенные данные свидетельствуют, что предложенные в диссертации алгоритмы позволяют эффективно проводить статическую верификацию продукционной БЗ.
Заключение
В работе обоснована актуальность исследования, сформулированы возможные направления совершенствования продукционных систем.
К числу основных результатов работы относятся:
- Разработана новая математическая модель представления продукционных баз знаний на ЭВМ, представляющая собой гиперграф специального вида, объединяющий в себе все сущности и зависимости, представляемые в БЗ. Это позволяет существенно ускорить проведение логического вывода.
- В рамках предложенной математической модели разработаны специальные алгоритмы прямого и обратного логического вывода, представляющие собой алгоритмы поиска на полученном гиперграфе.
- Предложены новые, более совершенные алгоритмы проверки продукционной базы знаний, построенной на основе предложенной в диссертации математической модели, на полноту и избыточность. Алгоритмы выполняют автоматическое разбиение правил из БЗ на группы и, анализируя каждую группу отдельно, позволяют определить недостающие для полноты правила или пары дублирующих друг друга правил.
- Разработан алгоритм поиска циклических зависимостей на указанной математической модели, представляющий собой поиск циклов в приведенном гиперграфе.
- Получены оценки вычислительной (временной и емкостной) сложности предложенных в диссертации алгоритмов работы продукционной системы. На их основе доказано, что работа продукционной системы на предложенной математической модели эффективнее, чем основанная на существующих представлениях, что также подтверждается статистическими данными, полученными на основе проведенных экспериментов.
- Создано программное обеспечение, реализующее разработанную модель и предложенные алгоритмы.
Перспективным направлением развития данной тематики автору видится создание аппаратно-программного обеспечения для работы продукционных систем.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
- Публикации в изданиях, рекомендованных ВАК РФ:
1. Иванов А.С. Модель представления продукционных баз знаний на ЭВМ /А.С. Иванов //Известия Саратовского университета. Серия «Математика. Механика. Информатика». 2007. Т.7. Вып. 1.- С.83-88.
- Публикации в других изданиях:
- Иванов А.С. Синтаксический и семантический анализ продукционных баз знаний /А.С.Иванов, С.П. Шевырев //Искусственный интеллект: сб. трудов.- Саратов: Изд-во Сарат. ун-та, 1995.- С. 40-45.
- Иванов А.С. Анализ семантики продукционных баз знаний /А.С.Иванов //Теоретические проблемы информатики и ее приложений. 1997. Вып. 1.- С. 74-79.
- Иванов А.С. Конвертирование баз знаний /А.С.Иванов //Теоретические проблемы информатики и ее приложений. 2001. Вып. 4.- С. 82-88.
- Иванов А.С. Представление продукционных баз знаний в экспертных системах /А.С.Иванов //Компьютерные науки и информационные технологии: сб. трудов.- Саратов: Изд-во Сарат. ун-та, 2002.- С.30-31.
- Иванов А.С. Модель представления продукционных баз знаний на ЭВМ /А.С.Иванов //Теоретические проблемы информатики и ее приложений. 2003. Вып. 5.- С. 63-68.
- Иванов А.С. Модели представления продукционных баз знаний на ЭВМ /А.С.Иванов; Сарат. гос. ун-т им. Н. Г. Чернышевского.- Саратов, 2004.- 16 с.- Библ. 5. - Рус. - Деп. в ВИНИТИ 27.02.2004, № 350-В2004.
- Иванов А.С. Модель представления продукционных баз знаний на ЭВМ /А.С.Иванов //Теоретические проблемы информатики и ее приложений. 2004. Вып. 6.- С.95-100.
- Иванов А.С. К вопросу верификации продукционных баз знаний /А.С.Иванов //Теоретические проблемы информатики и ее приложений. 2006. Вып. 7.- С.52-59.
- Иванов А.С. Графовая модель продукционной базы знаний /А.С.Иванов //Информационные системы и технологии 2007: сб. трудов.- Обнинск: Изд-во ИАТЭ, 2007.- С.33-34.
- Иванов А.С. Модель представления продукционных баз знаний /А.С. Иванов //Компьютерные науки и информационные технологии: сб. трудов.- Саратов: Изд-во Сарат. ун-та, 2007.- С. 50-51.
- Иванов А.С. Графовая модель представления продукционных баз знаний /А.С. Иванов //Труды конф. AIS’07: в 3 т.- М.:Физматлит, 2007. Т.2.- С. 176-182.
Подписано в печать Формат 60х84 1/16
Бум. офсет. Усл. печ. л. Уч.-изд. л.
Тираж 100 экз Заказ Бесплатно
Саратовский государственный технический университет
410054, Саратов, Политехническая ул., 77
Отпечатано в РИЦ СГТУ. 410054, Саратов, Политехническая ул., 77
