Лекция 8 (Гиренко - Лекции)
Описание файла
Файл "Лекция 8" внутри архива находится в папке "Лекции Гиренко". Документ из архива "Гиренко - Лекции", который расположен в категории "". Всё это находится в предмете "информационные технологии" из 2 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "информационные технологии" в общих файлах.
Онлайн просмотр документа "Лекция 8"
Текст из документа "Лекция 8"
Лекция 8.
Логический подход к построению систем ИИ. Модели представления знаний.
Данные и знания
Данные - это отдельные факты, характеризующие объекты, процессы и явления в предметной области, а также их свойства.
Знания связаны с данными, основываются на них, но представляют результат мыслительной деятельности человека, обобщают его опыт, полученный в ходе выполнения какой-либо практической деятельности. Они получаются эмпирическим путем. Итак, Знания - это выявленные закономерности предметной области (принципы, связи, законы), позволяющие решать задачи в этой области.
Поле знаний - условное описание основных объектов предметной области, их атрибутов и закономерностей, их связывающих;
Знания могут быть классифицированы по следующим категориям:
-
поверхностные - знания о видимых взаимосвязях между отдельными событиями и фактами в предметной области;
-
глубинные - абстракции, аналогии, схемы, отображающие структуру и процессы в предметной области.
Существуют десятки моделей (или языков) представления знаний для различных предметных областей. Большинство из них может быть сведено к следующим классам:
-
алгоритмические модели;
-
семантические сети;
-
продукционные;
-
фреймы;
-
формальные логические модели.
Неформальные процедуры
Прежде, чем приступить к описанию моделей представления данных рассмотрим понятие – «неформальная процедура».
Говоря о неформальных процедурах, мы обычно хорошо понимаем, что имеется в виду, и без затруднений можем привести примеры таких процедур, связанных с пониманием текстов естественного языка, переводом с одного естественного языка на другой, информационным поиском по смыслу и т. д.
Трудности возникают при попытке точного определения подобных процедур. Так, если рассматривать неформальные процедуры всего лишь как абстрактные функции, которые для каждого значения аргумента "выдают" некоторое значение, то категория неформальности вообще исчезает из рассмотрения.
Неформальная процедура — это особый способ представления функций. Чтобы в какой-то степени приблизиться к этому "человеческому" способу представления функций, рассмотрим прежде всего традиционные алгоритмические модели и попытаемся понять, в чем состоит основная трудность их применения для имитации неформальных процедур.
Алгоритмические модели
Алгоритмические модели основаны на понятии алгоритма. Исторически первые точные определения алгоритма, возникшие в 30-х годах, были связаны с понятием вычислимости. С тех пор было предложено множество, как выяснилось, эквивалентных определений алгоритма.
В практике программирования алгоритмы принято описывать с помощью алгоритмических языков программирования. Широко используются также разного рода блок-схемы алгоритмов, позволяющие представить алгоритмы в наглядном и общедоступном виде, не привлекая в тоже время сложных конструкций из конкретных языков программирования.
Блок-схемы
Приведем наиболее часто употребляемые символы в блок-схемах.
Название символа | Обозначение и пример заполнения | Пояснение |
Процесс | Вычислительное действие или последовательность действий | |
Решение |
| Проверка условий |
Модификация |
| Начало цикла |
Предопределенный процесс |
| Вычисления по подпрограмме, стандартной подпрограмме |
Ввод-вывод |
| Ввод-вывод в общем виде |
Пуск-останов |
| Начало, конец алгоритма, вход и выход в подпрограмму |
Документ |
| Вывод результатов на печать |
Пример вложенных циклов пока. Вычислить произведение тех элементов заданной матрицы A(10,10), которые расположены на пересечении четных строк и четных столбцов.
С точки зрения программирования на алгоритмических языках достоинства подобного представления очевидны — эта блок-схема без затруднений переводится в текст программы, например, на языке Ассемблер или С++. Однако само составление подобной блок-схемы при появлении новых условий становится, очевидно, все более и более утомительным занятием.
Разумеется, программист без особого труда составит достаточно сложную блок-схему алгоритма. И все же, если учесть, что дополнительные изменения и расширения алгоритма при программировании неформальных процедур происходят многократно (реальная сложность неформальной процедуры как раз и проявляется в практической невозможности предусмотреть заранее все случаи), следует признать, что, вполне правильное в статике решение в динамике – неудачно.
Семанти́ческая сеть
Семанти́ческая сеть — информационная модель предметной области, имеющая вид ориентированного графа, вершины которого соответствуют объектам предметной области, а дуги (рёбра) задают отношения между ними. Объектами могут быть понятия, события, свойства, процессы. Таким образом, семантическая сеть является одним из способов представления знаний. В названии соединены термины из двух наук: семантика в языкознании изучает смысл единиц языка, а сеть в математике представляет собой разновидность графа — набора вершин, соединённых дугами (рёбрами). В семантической сети роль вершин выполняют понятия базы знаний, а дуги (причем направленные) задают отношения между ними. Таким образом, семантическая сеть отражает семантику предметной области в виде понятий и отношений. См. пример на рис. 1.
Рис.1
Продукционные модели
Продукционная модель, или модель, основанная на правилах, позволяет представить знания в виде предложений типа: Если (условие), то (действие).
Под, условием понимается некоторое предложение-образец, по которому осуществляется поиск в базе знаний, а под действием - действия, выполняемые при успешном исходе поиска (они могут быть промежуточными, выступающими далее как условия, и терминальными или целевыми, завершающими работу системы).
При использовании продукционной модели база знаний состоит из набора правил, Программа, управляющая перебором правил, называется машиной вывода. Чаще всего вывод бывает прямой (от данных к поиску цели) или обратный (от цели для ее подтверждения - к данным). Данные - это исходные факты, на основании которых запускается машина вывода - программа, перебирающая правила из базы.
Пример
Имеется фрагмент базы знаний из двух правил:
П1: Если "отдых - летом" и "человек - активный", то "ехать в горы",
П2: Если "любит солнце", то "отдых летом",
Предположим, в систему поступили данные - "человек активный" и "любит "солнце"
Прямой вывод - исходя из данных, получить ответ.
1-й проход.
Шаг 1. Пробуем П1, не работает (не хватает данных "отдых - летом").
Шаг 2. Пробуем П2, работает, в базу поступает факт "отдых - летом".
2-й проход.
Шаг 3. Пробуем П1, работает, активируется цель "ехать в горы", которая и выступает как совет, который дает экспертная система.
Обратный вывод - подтвердить выбранную цель при помощи имеющихся правил и данных.
1-й проход.
Шаг 1. Цель - "ехать в горы": пробуем П1 - данных, "отдых - летом" нет, они становятся новой целью, и ищется правило, где она в правой части.
Шаг 2. Цель "отдых - летом": правило П2 подтверждает цель и активирует ее.
2-й проход.
Шаг 3. Пробуем П1, подтверждается искомая цель.
Продукционная модель чаще всего применяется в промышленных экспертных системах. Она привлекательна своей наглядностью, высокой модульностью, легкостью внесения дополнений и изменений и простотой механизма логического вывода.
Рост противоречивости продукционной модели может быть ограничен путём введения механизмов исключений и возвратов.
Режим возвратов
Механизм возвратов же означает, что логический вывод может продолжаться в том случае, если на каком-то этапе вывод привёл к противоречию. Просто необходимо отказаться от одного из принятых ранее утверждений и осуществить возврат к предыдущему состоянию.
В общем случае неформальные процедуры являются многозначными, а правильность конкретного выбора, сделанного на некотором шаге, проверяется на следующих шагах.
Пример:
-
ПАПА ——————> ЛЮБИТ ——————> ?
-
что делать? кого?
-
ПАПА <—————— ЛЮБИТ <—————— ?
-
кого? что делать?
Пусть предложение начинается со слов МАТЬ ЛЮБИТ ... . Проанализировав эти слова в первоначальном предположении именительного падежа для слова ПАПА, система вправе построить структуру, представленную в случае 1). Если следующее слово после слова ЛЮБИТ представляет собой существительное в винительном падеже, например, вся фраза имеет вид ПАПА ЛЮБИТ СЫНА, то эта структура является окончательной. Если же фраза имеет вид ПАПА ЛЮБИТ СЫН, то возникает противоречие или, как говорят, сигнал неуспеха — очередное слово СЫН противоречит ожиданию прямого дополнения. В этом случае система должна вернуться на ближайший из предыдущих шагов, где можно принять другую альтернативу анализа. В данном примере это шаг анализа слова ПАПА — система должна принять теперь альтернативу винительного падежа для этого слова. Далее будет построена структура, указанная в случае 2).
Тривиальность рассмотренного примера убеждает в необходимости режима возвратов при реализации неформальных процедур.
Продукционные системы с исключениями
Механизм исключений означает, что вводятся специальные правила-исключения. Их отличает большая конкретность в сравнении с обобщёнными правилами. При наличии исключения основное правило не применяется.
Если отношение "правило—исключение" встроено в систему, она сама может понять, что преобразование ПАЛКА -> ПАЛКЫ незаконно. При этом система должна руководствоваться простым принципом: если применимо исключение, общее правило запрещено. Соответствующие системы будем называть системами с исключениями.
Отношение "общее правило — исключение" безусловно полезно для понимания системой уместности правил. Можно сказать, что это отношение устанавливает автоматически (по умолчанию) наиболее типичное для неформальных процедур взаимодействие правил:
-
исключение "вытесняет" общее правило;
-
при пересечении разрешены оба правила.
Разумеется, возможны ситуации, когда необходимо поступать наоборот:
-
исключение не запрещает общего правила;
-
при пересечении одно из правил запрещено.
Пусть дано, например, общее правило и его исключение . Таким образом, для произвольного слова необходима реакция р1. Для слова же, начинающегося с буквы А, исполняется реакция р2 — по умолчанию для таких слов реакция р1 незаконна.
Предположим, однако, что по условию конкретной задачи для слов, начинающихся с А, реакция р1 также допустима. В этом случае введение нового правила снимает запрет на реакцию р1 в ситуации Ах.
Аналогичный способ годится для пересечения правил.
Таким образом, аппарат исключений позволяет устанавливать произвольные способы взаимодействия правил, в том числе и отличные от взаимодействия по умолчанию.
При развитии продукционной системы с исключениями программист сосредотачивает свое внимание на выявлении новых правил и на обобщении уже имеющихся. Аппарат исключений освобождает программиста от решения трудоемких вопросов согласования правил — распознавание и интерпретация исключений осуществляется автоматически.
Логический вывод
Важность логического вывода становится очевидной уже при рассмотрении простейших информационно-логических процедур. Предположим, что некоторая база данных содержит сведения об отношениях "х — ОТЕЦ у" и "х — МАТЬ у". Чтобы обработать запросы типа:
ИВАНОВ А.И. — ДЕД ПЕТРОВА В.А.?
ПЕТРОВ В.А. — ВНУК ИВАНОВА А.И.?
необходимо либо ввести в базу данных также и сведения об отношениях "х — ДЕД у" и "х — ВНУК у", либо объяснить системе, как из отношений ОТЕЦ, МАТЬ извлечь искомую информацию. Реализация первой возможности связана с неограниченным ростом избыточности базы данных. Вторая возможность при традиционном алгоритмическом подходе требует написания все новых и новых программ для реализации новых типов запросов.