Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

Ульяновский государсвенный университет

Факультет математики и информационных технологий

Кафедра телекоммуникационных технологий и сетей

А.С. Мельниченко

Представление знаний в интеллектуальных системах

Лабораторный практикум

Ульяновск

2010

Печатается по решению Ученого совета факультета математики

и информационных технологий

Ульяновского государственного университета

Рецензенты:

профессор кафедры информационных технологий Ульяновского государственного университета,

доктор технических наук К.В. Кумунжиев;

доцент кафедры телекоммуникационных технологий и сетей Ульяновского государственного университета, кандидат технических наук Е.Г.Чекал.

Представление знаний в интеллектуальных системах: лабораторный практикум / А.С. Мельниченко. – Ульяновск: УлГУ, 2010.

В издание включены лабораторные работы и необходимые методические материалы для практического освоения разделов курса «Представление знаний в ИС», являющегося теоретической основой интеллектуальных информационных систем. Материал носит учебно-практический и прикладной характер и способствует формированию знаний и практических навыков в области интеллектуальных информационных систем.

Практикум разработан в соответствии с государственными образовательными стандартами высшего профессионального образования (ГОС ВПО) для студентов, обучающихся по специальностям 08.08.01 - прикладная информатика, 07.19.00 - информационные системы и технологии, 351500 - математическое обеспечение и администрирование в ИС.

УДК 004.8(075.8)

ББК 32.813я73

© Ульяновский государственный университет, 2010

© Мельниченко А.С., 2010

СОДЕРЖАНИЕ

Предисловие

Лабораторная работа № 1. Логико-алгебраические модели представления знаний

Лабораторная работа № 2. Семантические модели представления знаний

Лабораторная работа № 3. Продукционные модели представления знаний

Лабораторная работа № 4. Фреймовые модели представления знаний

Лабораторная работа № 5. Нечеткие системы

Лабораторная работа № 6. Нейронные сети

Лабораторная работа № 7. Генетические алгоритмы

Лабораторная работа № 8. Гибридные системы

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Предисловие

Данный лабораторный практикум разработан в соответствии с государственными образовательными стандартами высшего профессионального образования (ГОС ВПО) для студентов, обучающихся по специальностям (08.08.01 - прикладная информатика, 07.19.00 - нформационные системы и технологии, 351500 - математическое обеспечение и администрирование в ИС.

Лабораторный практикум предполагает, что студенты названных специальностей освоили лекционный материал по курсу представление знаний в интеллектуальных системах и должны:

1. Знать теорию, методы построения систем представления знаний; классы, особенности и характеристики моделей представления знаний; способы представления и использования знаний в экспертных системах, нейрокомпьютерных экспертных системах, генетических алгоритмах и гибридных системах.

2. Уметь собирать и обрабатывать информацию, касающуюся систем представления знаний; осуществлять анализ информации по системам представления знаний и использовать результаты анализа в процессах создания интеллектуальных систем на всех этапах жизненного цикла; осуществлять поиск решения, используя модели знаний в предложенной проблемной области.

Лабораторный практикум имеют своей целью:

• закрепление, углубление и расширение знаний студентов по курсу представление знаний в информационных системах в процессе выполнения конкретных заданий;

• развитие у студентов профессиональных навыков, а также практическое овладение методами анализа результатов;

Основная форма выполнения лабораторных работ – поиск рационального решения с последующим анализом полученных результатов.

Лабораторная работа № 1 Логико-алгебраические модели представления знаний Теоретическая часть

1.Знания в интеллектуальных системах

Знание форма существования и систематизации результатов познавательной деятельности человека. Знание помогает людям рационально организовывать свою деятельность и решать различные проблемы, возникающие в её процессе.

Знание субъективный образ объективной реальности, то есть адекватное отражение внешнего и внутреннего мира в сознании человека в форме представлений, понятий, суждений, теорий.

Знание это связи и закономерности предметной области (принципы, модели, законы), полученные в результате практической деятельности и профессионального опыта, позволяющего специалистам ставить и решать задачи в данной области. В интеллектуальных системах знания представлены в виде базы знаний, где знания описаны на некотором языке представления знаний.

2. Классификация моделей представления знаний

При представлении знаний в памяти интеллектуальной системы традиционные языки, основанные на численном представлении данных, являются неэффективными. Для этого используются специальные языки представления знаний, основанные на символьном представлении данных. Они делятся на типы по формальным моделям представления знаний [1]. Наиболее часто используется на практике классификация, где модели представления знании делятся на детерминированные (жесткие) и мягкие.

Детерминированные модели включают в себя логико-алгебраические модели, семантические сети, фреймы и продукционные модели. Мягкие модели включают в себя нечеткие системы, нейронные сети, эволюционные модели, гибридные системы.

3. Логико - алгебраические модели знания

В логико - алгебраических моделях знания представляются в виде совокупности правильно построенных формул какой-либо формальной системы, которая задается четверкой:

S=<T, P, A, R >,

где Т - множество базовых (терминальных) элементов, из которых формируются все выражения; Р - множество синтаксических правил, определяющих синтаксически правильные выражения из терминальных элементов формальной системы; А - множество аксиом формальной системы, соответствующих синтаксически правильным выражениям, которые в рамках данной ФС априорно считаются истинными; R - конечное множество отношений {r₁, r₂, ... , r_n } между формулами, называемыми правилами вывода, позволяющих получать из одних синтаксически правильных выражений другие.

Простейшей логико - алгебраической моделью представления знаний являются исчисление высказываний. Развитие логики высказываний нашло отражение в исчислении предикатов первого порядка.

Под исчислением предикатов понимается формальный язык для представления отношений в некоторой предметной области. Основное преимущество исчисления предикатов хорошо понятный механизм математического вывода, который может быть непосредственно запрограммирован. Предикатом называют предложение, принимающее только два значения: истина или ложь. Для обозначения предикатов применяются логические связки между высказываниями: ¬ не, или, и, если, а также квантор существования и квантор всеобщности.

Допустимые выражения в исчислении предикатов называются правильно построенными формулами (ППФ), состоящими из атомных формул. Атомные формулы состоят из предикатов и термов, разделяемых круглыми, квадратными и фигурными скобками.

Предикатные символы представляются в основном глагольной формой, например: ПИСАТЬ, УЧИТЬ, ПЕРЕДАТЬ, но не только глагольной формой, а формами существительных и прилагательных, например: КРАСНЫЙ, ЗНАЧЕНИЕ, ЖЕЛТЫЙ.

Предикатные символы и константы, как правило, обозначаться заглавными символами, функциональные символы и переменные строчными.

В абстрактных примерах они обозначаются латинскими буквами f, g, h. В предложениях предикатной формы важны отношения и элементы. Определяя отношения, мы определяем значимость элементов выражения. Элементы могут быть предикатами и термами.

Объединение нескольких связанных между собой выражений исчисления предикатов в структуры большего размера называют блокам. Эти структуры отождествляются объектами в предметной области. Для подобных схем представления знаний используется термин структурированные объекты знаний, поскольку основной упор делается на структуру представления.

Рассмотрим простые примеры структуризации и эквивалентных преобразований ППФ по блочному принципу.

Пример

Пусть нам надо представить в виде фактов исчисления предикатов сле­дующие предложения:

Антон дал Ольге книгу.

Антон программист.

Ольга юрист.

Адрес Антона: Гоголя, 37, кв. 7.

Логическим представлением этих предложений являются следующие правильно построенные формулы:

ДАТЬ (АНТОН, ОЛЬГА, КНИГА)

ЗАНЯТИЕ (АНТОН, ПРОГРАММИСТ)

ЗАНЯТИЕ (ОЛЬГА, ЮРИСТ)

АДРЕС (АНТОН, Гоголя 37, кв. 7)

В этом примере для обозначения шести понятий мы исполь­зуем индивидуальные константные символы: АНТОН, ОЛЬГА, КНИГА, ПРО­ГРАММИСТ, ЮРИСТ и Гоголя 37, кв.7. Для удобства представления может оказаться полезным собрать все факты, относящиеся к данному понятию, в одну группу, которую мы назвали блоком. В нашем примере блок АНТОН ассоциируется со следующими фактами:

АНТОН

ДАТЬ (АНТОН, ОЛЬГА, КНИГА)

ЗАНЯТИЕ (АНТОН, ПРОГРАММИСТ)

АДРЕС (АНТОН, Гоголя 37, кв. 7)

Аналогичным образом блок ОЛЬГА ассоциируется со следующими фак­тами:

ОЛЬГА

ДАТЬ (АНТОН, ОЛЬГА, КНИГА)

ЗАНЯТИЕ (ОЛЬГА, ЮРИСТ)

Схема представления, в которой факты индексируются именами, обозна­чающими элементы или объекты предметной области, называется представ­лением, ориентированным на объекты.

Большинство обозначений для структурирования объектов выражаются через бинарные (двухаргументные) предикаты. Для записи произвольной ППФ с помощью только бинарных пре­дикатов можно применить простую схему эквивалентных преобразований. Чтобы, например, преобразовать трехаргументную формулу ДАТЬ (АНТОН, ОЛЬГА, КНИГА) в формулу, содержащую только бинарные предикаты, мы постулируем су­ществование конкретного факта передачи. Назовем это множество ПЕРЕ­ДАЧИ. Для каждого аргумента исходного предиката придумаем новый би­нарный предикат, соотносящий значение этого аргумента с постулированным в исходном предикате фактом. По этой схеме формула ДАТЬ (АНТОН, ОЛЬГА, КНИГА) должна быть преобразована к виду:

( х) [ЭЛЕМЕНТ (х, ПЕРЕДАЧИ) Λ ДАЮЩИЙ (х, АНТОН) Λ

ПОЛУЧАЮЩИЙ (х,ОЛЬГА) Λ ОБЪЕКТ (х, КНИГА)]

Предикат ЭЛЕМЕНТ (ЭЛ) используется для выражения факта принадлеж­ности множеству. Введение сколемовских выражений для переменных, от­носящихся к квантору существования наделяют постулированные нами события передачи некоторым именем ПЕР 1:

ЭЛ (ПЕР 1, ПЕРЕДАЧИ) Λ ДАЮЩИЙ (ПЕР 1,АНТОН) Λ

Λ ПОЛУЧАЮЩИЙ (ПЕР 1, ОЛЬГА) Λ ОБЪЕКТ (ПЕР 1, КНИГА)

Таким образом, трехаргументный предикат преобразован в конъюнкцию четырех бинарных.

Соотношения между ПЕР 1 и исходными аргументами предиката ДАТЬ можно выразить с помощью не предикатов, а функций над множеством ПЕРЕДАЧИ. Соответственно изменив обозначения, можно представить предложение «Антон дал Ольге книгу» такой формулой:

ЭЛ (ПЕР 1, ПЕРЕДАЧИ) Λ

Λ РАВ [дающий (ПЕР1), АНТОН] Λ

Λ РАВ [получающий (ПЕР1), ОЛЬГА] Λ

Λ РАВ [объект (ПЕР1), КНИГА]

Подразумевается, что предикат РАВ обозначает синтаксическое равенство выражений. В приведенном выражении используются некоторые функции, определенные на множестве ПЕРЕДАЧИ, значения которых дают имена других объектов, составляю­щих ПЕР 1.

Переход к представлению, в котором используются события и бинарные отношения, содержит некоторые преимущества. Из них главное для нас это модулярность. Пусть, к примеру, нам надо ввести информацию о том, когда произошел факт передачи. Прежде чем привести формулу к би­нарной форме, придется ввести в предикат ДАТЬ четвертый (временной) ар­гумент. Подобное изменение может потребовать перемен в про­дукциях, связанных с предикатом ДАТЬ. Напротив, если передача книги представлена понятием в предметной облас­ти, то информацию о ней можно легко расширить, введя новые бинарные отношения, функции и ассоциированные правила.

В этой части почти все суждения представлены терминами, обозна­чающими «события» или «ситуации», которые мы рассматриваем как эле­менты нашей предметной области. Нам нужно совсем немного предикатов: РАВ, чтобы выразить идентичность двух понятий; ПМ, чтобы указать, что одно множест­во является подмножеством другого; ЭЛ, чтобы сказать, что некоторое по­нятие является элементом некоторого множества. В предложениях нашего примера события состоят в том, что некие лица имеют некоторый род занятий (РЗ) и у некоторого лица есть адрес (АДР). Эти предложения можно представить так:

ПЕР 1

ЭЛ (ПЕР 1, ПЕРЕДАЧИ)

РАВ [(дающий (ПЕР 1), АНТОН]

РАВ [получающий (ПЕР 1), ОЛЬГА]

РАВ [объект (ПЕР 1), КНИГА]

РЗ 1

ЭЛ (РЗ 1, РОД ЗАНЯТИЙ)

РАВ [работающий (РЗ 1), АНТОН]

РАВ [профессия (РЗ 1), ПРОГРАММИСТ]

Р3 2

ЭЛ (РЗ 2, РОД ЗАНЯТИЙ)

РАВ [работающий (РЗ 2), ОЛЬГА]

РАВ [профессия (РЗ 2), ЮРИСТ]

АДР 1

ЭЛ (АДР 1, АДРЕСА)

РАВ [человек (АДР 1), АНТОН]

РАВ [место (АДР 1), Гоголя, 37, кв. 7].

В этих блоках для связи событий с другими понятиями нами произволь­но введены некоторые функции.

Заметим, что приведенные блоки обладают некоторой общей структурой. Во-первых, для указания на то, что определенный объект, описываемый блоком, является элементом некоторого множества, используется пре­дикат ЭЛ (если объект, представленный блоком, сам по себе является отдельным множеством, то для указания на то, что он был подмножеством некоторого другого множества, можно использовать предикат ПМ).

Во-вто­рых, значения разных функций от объекта, представленного блоком, имеют отношение и к другим объектам. Поэтому введем для блоков специальное обозначение, основывающееся на этой общей структуре.

В качестве сокращенной записи формулы типа РАВ [дающий (ПЕР 1, АНТОН)] мы используем такое выражение или пару: «дающий: АНТОН». Все предикаты РАВ, которые устанавливают связь между функциями от объ­екта, представленного блоком, и другими объектами, выражаются посред­ством таких пар, выписываемых под именем блока. Тогда для нашего при­мера получаем:

ПЕР 1

дающий: АНТОН

получающий: ОЛЬГА

объект: КНИГА

В тех системах искусственного интеллекта, которые используют блочную запись, конструкции типа «дающий : АНТОН» часто называют ячейками. Пер­вое выражение дающий называют именем ячейки, второе АНТОН значением ячейки.

Иногда значение ячейки представляет собой не константный символ (такой как АНТОН), а функциональное выражение. Эта функция, в частности, может относиться к имени ячейки другого блока. Рассмотрим, к приме­ру, предложения: «Антон дал Ольге книгу» и «Игорь дал ручку тому лицу, которому Антон дал книгу». Выразим эти предложения с помощью двух блоков:

ПЕР 1

ЭЛ (ПЕР 1, ПЕРЕДАЧИ)

дающий: АНТОН получающий: ОЛЬГА

объект: КНИГА ПЕР 2

ЭЛ (ПЕР 2, ПЕРЕДАЧИ)

дающий: ИГОРЬ получающий: получающий (ПЕР 1)

объект: РУЧКА

В этих примерах выражения получающий (ПЕР 1) и ОЛЬГА служат двумя способами называния одного и того же лица. Ниже мы рассмотрим, как мож­но «вычислить» функциональное выражение типа получающий (ПЕР 1), най­дя значение ячейки получающий в блоке ПЕР 1.

Значениями ячеек могут быть и переменные, относящиеся к квантору существования. Например, высказывание: «Некто дал Ольге книгу», запи­санное в исчислении предикатов, может содержать формулу ( х) РАВ [да­ющий (ПЕР 3), х]. Такую переменную можно подвергнуть сколемовскому преобразованию и получить выражение вида РАВ [дающий (ПЕР 3), S]. О переменной, относящейся к квантору существования, как правило, име­ется некоторая информация. В нашем примере может быть известно, что слово «некто» относится к человеку. Более удачный перевод предложения «Некто дал Ольге книгу» на язык исчисления предикатов должен содержать формулу

( х) {РАВ [дающий (ПЕР3), х] Λ ЭЛ (х, ЛЮДИ)] }, или просто

ЭЛ [дающий (ПЕР 3), ЛЮДИ]

Чтобы иметь возможность работать с такими формулами в нашей системе блочной записи, введем как некоторое псевдозначение ячейки специальную форму: (элемент множества ЛЮДИ). Такая форма служит сокращением формулы с предикатом ЭЛ. Выражение, в котором использована такая сокращенная форма, можно представлять как неопределенное описание значения ячейки.