Калабухов Е.В. Курс лекций по дисциплине Базы данных, знаний и экспертные системы
Подождите немного. Документ загружается.
• PROSPECTOR — ЭС, созданная для содействия поиску коммерчески
оправданных месторождений полезных ископаемых;
•
G2 – базовый программный продукт фирмы Gensym Corp. (США),
представляющий собой графическую, объектно-ориентированную среду
для построения и сопровождения динамических ЭС реального времени,
предназначенных для мониторинга, диагностики, оптимизации,
планирования и управления динамическим процессом.
221
8. ЗНАНИЯ
В системах ИИ знания являются основным объектом формирования,
обработки и исследования. БЗ, наравне с БД, - необходимая составляющая
программного комплекса ИИ. Машины, реализующие алгоритмы ИИ,
называются машинами, основанными на знаниях, а подраздел теории ИИ,
связанный с построением ЭС, - инженерией знаний.
В ЭВМ знания так же, как и данные, отображаются в знаковой форме - в
виде формул, текста, файлов, информационных массивов и т.п. Поэтому можно
сказать, что знания - это особым образом организованные данные.
Свойства знаний, отличающие их от данных:
•
внутренняя интерпретируемость – кроме самой информации, в памяти
ЭВМ должна храниться информация о некоторой протоструктуре
информационных единиц (подобно метаданным в СУБД);
•
структурированность - информационные единицы должны обладать
гибкой структурой; при этом должна существовать возможность
рекурсивной вложенности одних информационных единиц в другие и
произвольного установления между отдельными информационными
единицами отношений типа "часть-целое", "род-вид" или "элемент-
класс";
•
связность - между информационными единицами должна быть
предусмотрена возможность установления связей различного типа; эти
связи могут характеризовать отношения между информационными
единицами (например, связь "причина-следствие" – декларативные
знания; связь "аргумент-функция" - процедурные знания, связанные с
вычислением определенных функций); различают отношения
структуризации (иерархии информационных единиц), функциональные
отношения (несут процедурную информацию, позволяющую вычислять
одни информационные единицы через другие), каузальные отношения
(задают причинно - следственные связи) и семантические отношения
222
(соответствуют всем остальным отношениям);
•
семантическая метрика - отношение, характеризующее ситуационную
близость информационных единиц (ассоциативную связь между
информационными единицами); такое отношение дает возможность
выделять в информационной базе некоторые типовые ситуации
(например, "покупка", "управление машиной") и позволяет находить
знания, близкие к некоторым, уже найденным;
•
активность – знания активны, появление в базе фактов или описаний
событий, установление связей может стать источником активности
системы.
В системах ИИ знания в основном можно разделить на две группы: факты
(фактические знания) и правила (знания для принятия решений).
В рамках работы со знаниями можно выделить следующие направления:
•
представление знаний - в рамках этого направления решаются задачи,
связанные с формализацией и представлением знаний в памяти системы
ИИ, (разработка специальных моделей представления знаний и языков
описания знаний);
•
манипулирование знаниями - в рамках данного направления
разрабатываются способы пополнения знаний на основе их неполных
описаний, создаются методы достоверного и правдоподобного вывода на
основе имеющихся знаний, предлагаются модели рассуждений,
опирающихся на знания и имитирующих особенности человеческих
рассуждений.
Манипулирование знаниями очень тесно связано с представлением
знаний, и разделить эти два направления можно лишь условно.
8.1. Модели представления знаний
Проблема представления знаний оказывает существенное влияние на
223
характеристики и свойства системы. Для возможности оперирования знаниями
из реального мира с помощью ЭВМ, необходимо осуществить их
моделирование (по аналогии с построением концептуальных и логических
моделей БД). При выполнении этого процесса следует учесть два важных
условия задания модели знаний:
•
однородность представления знаний - приводит к упрощению механизма
управления логическим выводом и управлением знаниями;
•
простота понимания знаний - доступность понимания представления
знаний и экспертам, и пользователем системы, в противном случае
затрудняется приобретение знаний и их оценка.
Различают три типа моделей представления знаний:
1) Формальные модели представления знаний.
Система ИИ в определенном смысле моделирует интеллектуальную
деятельность человека и, в частности, - логику его рассуждений. В упрощенной
форме логические построения человека сводятся к следующей схеме: из одной
или нескольких посылок (которые считаются истинными) следует сделать
"логически верное" заключение (вывод, следствие). Очевидно, для этого
необходимо, чтобы и посылки, и заключение были представлены на понятном
языке, адекватно отражающем предметную область, в которой проводится
вывод. В обычной жизни это наш естественный язык общения, в математике,
например, это язык определенных формул и т.п. Наличие же языка
предполагает, во-первых, наличие алфавита (словаря), отображающего в
символьной форме весь набор базовых понятий (элементов), с которыми
придется иметь дело, и, во-вторых, набор синтаксических правил, на основе
которых, пользуясь алфавитом, можно построить определенные выражения.
Логические выражения, построенные в данном языке, могут быть истинными
или ложными. Некоторые из этих выражений, являющиеся всегда истинными,
объявляются аксиомами. Они составляют ту базовую систему посылок, исходя
из которой и пользуясь определенными правилами вывода, можно получить
заключения в виде новых выражений, также являющихся истинными. Если
224
перечисленные условия выполняются, то говорят, что система удовлетворяет
требованиям формальной теории и считается формальной системой.
Логические модели, построенные на основе на исчислении высказываний или
исчислении предикатов, являются классическими примерами формальных
систем.
2) Неформальные модели представления знаний.
В отличие от формальных моделей, в основе которых лежит строгая
математическая теория, неформальные модели такой теории не
придерживаются. Каждая неформальная модель годится только для конкретной
предметной области и поэтому не обладает той универсальностью, которая
присуща моделям формальным. Логический вывод в формальных системах
строг и корректен, а вывод в неформальных системах во многом определяется
самим исследователем, который и отвечает за его корректность. К
неформальным моделям относятся:
•
модель семантической сети;
•
модель, основанная на использовании фреймов;
•
продукционная модель.
3) Интегрированные модели представления знаний.
Интегрированные МПЗ совмещают в себе модели различных типов.
Выбор модели представления знаний при построении системы ИИ
является ответственным этапом и выполняется инженером знаний.
8.1.1. Модель на базе логики
Одним из способов представления знаний является язык математической
логики – логики предикатов, позволяющий формально описывать понятия
предметной области и связи между ними. В отличие от естественного языка,
который очень сложен, язык логики предикатов использует только такие
конструкции естественного языка, которые легко формализуются.
225
Логика предикатов - это формальная языковая система, которая
оперирует с предложениями на естественном языке в пределах синтаксических
правил этого языка. Формально логическая модель задается четверкой вида:
M = <T, F, A, P>.
Здесь, T – алфавит (множество базовых элементов различной природы), F
– множество формул (задается в виде синтаксических правил), A – множество
аксиом, P – множество правил вывода. Существуют процедура П(X), которая
позволяет определить принадлежит или не принадлежит ее аргумент
множеству X (в качестве X могут использоваться T, F, A и P).
Для знаний, входящих в БЗ, можно считать, что множество A образуют
все информационные единицы, которые введены в БЗ извне, а с помощью
правил вывода из них выводятся новые производные знания. Другими словами
формальная система представляет собой генератор порождения новых знаний,
образующих множество выводимых в данной системе знаний. Это свойство
логических моделей делает их притягательными для использования в базах
знаний. Оно позволяет хранить в базе лишь те знания, которые образуют
множество A, а все остальные знания получать из них по правилам вывода.
Фактически язык логики предикатов использует слова, которые делятся
на следующие группы:
•
термы – описывают понятия и объекты изучаемой предметной области;
•
предикаты – задают свойства этих объектов и понятий, а также их
поведение и отношения между ними.
При логическом программировании пользователь описывает предметную
область совокупностью предложений в виде логических формул, а ЭВМ,
манипулируя этими предложениями, строит необходимый для решения задач
вывод.
Термы - это символы (или комбинация символов), являющиеся
наименьшим значимым элементом языка. К термам относятся:
•
константы - применяются для обозначения конкретных объектов
реального мира (например, «студент», «птица», «5» и т.п.);
226
• переменные - используются для обозначения некоторого из возможных
объектов реального мира или их совокупности (например, некто, вещь и
т.п.);
•
функции - последовательность из нескольких констант или переменных,
заключенных в круглые скобки, следующие за особым функциональным
символом - функтором (оператором, который после воздействия на
объект возвращает некоторое значение); например, сумма (1,2),
увеличить_на_единицу(X).
Предикат - это логическая функция, которая выражает отношение между
своими аргументами и принимает значение «истина», если это отношение
имеется, или «ложь», если оно отсутствует. Заключенная в скобки
последовательность из n термов, перед которой стоит предикатный символ,
называется n-арным предикатом, который принимает значения «истина» или
«ложь» в соответствии со значением термов, являющимися его аргументами.
Например,
студент (Иванов)
владелец (X, «А 1820 МС»)
Приведенные выше предикаты получили название атомарных предикатов
и соответствуют наиболее простым предложениям нашего разговорного языка -
нераспространенным предложениям. В обычном языке из нераспространенных
предложении с помощью соединительных местоимений, союзов, и других
частей речи строят более сложные конструкции - сложные предложения. В
логике предикатов сложными предложениями естественного языка
соответствуют предикатные формулы, которые образуются из атомарных
предикатов и логических связок (расположены по уменьшению приоритета):
⎤ - «не»
, - «и»;
∨ - «или»;
← - «если»;
↔ - «тогда и только тогда».
227
Пример предикатной формулы, соответствующей сложному
предложению «Некто является птицей, если некто имеет крылья и владеет
гнездом»:
является (Х, птица) ← имеет (Х, крылья), владеет (Х, гнездо)
где является(), имеет() и владеет() - атомарные предикаты, а - Х –
переменная, при подстановке в которую конкретного значения (например,
Х:=«орёл») можно оценить значение предикатной формулы (ложь или истина).
Здесь для истинности предиката является() должна быть истинной связка
имеет() и владеет(). Иногда можно определить значения предиката не делая
подстановок констант, а используя кванторы общности (∀ - «для всех») и
существования (∃ - «существует по крайней мере одно»), например «Любой
некто является птицей если некто имеет крылья и владеет гнездом»:
(∀X) [являться (Х, птица) ← имеет (Х, крылья), владеет (Х, гнездо)]
Кванторы ∀ и ∃ могут использоваться и для любого числа переменных.
Рассмотрим их различное использование на примере двухместного предиката
изучает (S, P), который описывает отношение «S изучает P» (S – переменная,
которая задает студента, а P - предмет):
•
(∀S) (∀P) изучает (S, P) - все студенты изучают все предметы;
•
(∃S) (∀P) изучает (S, P) – существует по крайней мере один студент,
который изучает все предметы;
•
(∀S) (∃P) изучает (S, P) - каждый студент изучает по крайней мере один
предмет;
•
(∃S) (∃P) изучает (S, P) - существует по крайней мере один студент,
который изучает по крайней мере хоть один предмет.
Для построения составных предикатных формул языка логики предикатов
первого порядка (или правильно построенных формул (ППФ или логических
формул)), задан следующий набор правил:
•
термом является либо константа, либо переменная, либо кортеж из n
термов, перед которым стоит функтор;
228
• предикат - это кортеж из n термов, перед которым стоит предикатный
символ;
•
атомарный предикат является логической формулой;
•
если F и G - логические формулы, то (F); F,G; F∨G; ⎤ F; F→G; F↔G -
также являются логическими формулами;
•
если F(X) - логическая формула, то оба выражения (∀Х) F(X), (∃X) F(X)
является логическими формулами;
•
все результаты, получаемые повторением конечного числа
перечисленных выше правил являются логическими формулами;
Например, ППФ предложения «Все люди смертны» будет записано в
виде: (∀X) [человек (Х) ← смертен].
В логической модели определен специальный механизм работы со
знаниями - логический вывод. Логический вывод - это процесс получения из
множества правильно построенных формул (S) некоторой новой ППФ (S`)
путем применения одного или нескольких правил вывода. Наиболее простой
метод логического вывода использует только одно правило вывода, называемое
резолюцией, которое применяют к логическим формулам вида:
факт: А
отрицание: ⎤ (А
1
, ... , А
n
)
импликация: А ← В
1
, ... , В
m
,
где А
i
(i = 1, n) и B
j
(j = 1, m) - произвольные предикаты.
Для S = { S
1
, S
2
}, для которых выполняются следующие условия:
S
1
(отрицание): ⎤ А,
S
2
(импликация): А ← В ,
предикат А из S
1
совпадает с предикатом А левой части S
2
,
можно по выше указанному правилу резолюций вывести новую ППФ
вида:
S`: ⎤ B
При этом ППФ S
1
и S
2
называются родительскими предложениями, а S` -
229
резольвентой, которая получается в результате применения резолюции к S
1
и
S
2
.
Резолюция в этом простейшем случае соответствует правилу вывода
modus tollens, которое записывается в виде:
⎤ B ← ⎤ A , A←B
и соответствует следующему умозаключению: допуская, что НЕ А и А ЕСЛИ
В, выводим НЕ В.
Применяя правило вывода modus tollens в случае, когда:
S
1
(отрицание): ⎤ А
S
2
(факт): А,
применение правила резолюции даст в качестве резольвенты пустое отрицание
S`: , что будет означать противоречие, т.е. допуская, что: НЕ А и А
выводим противоречие (⎤ (⎤ А) = А).
Для более общего случая, когда родительские предложения имеют вид
(причем предикат А
k
из отрицания S
1
совпадает с предикатом из левой части
S
2
):
S
1
: ⎤ (A
1
,... ,A
k
, ...,A
n
)
S
2
: A
k
← (B
1
, ...,B
m
) (где 1<k<n)
в качестве резольвенты будет получено следующее отрицание:
S`: ⎤ (A
1
, ..., A
k-1
, B
1
,..., B
m
, A
k+1
, ..., A
n
), т.е. в S
1
будет выполнена замена
A
k
на (B
1
, ...,B
m
).
Например, допуская, что «⎤ (темно, зима, холодно) и что зима ← январь»,
выводим, что ⎤ (темно, январь, холодно).
В случае, если родительские предложения имеют вид (А
k
является одним
из предикатов из S
1
):
S
1
(отрицание): ⎤ (A
1
,... ,A
k
, ...,A
n
)
S
2
(факт): A
k
в качестве резольвенты будет получено следующее отрицание:
S`: ⎤ (A
1
, ..., A
k-1
, A
k+1
, ..., A
n
), т.е. из S
1
будет удален А
k
.
230