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

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

S= <В, F, A, R>,

где В – счетное множество базовых символов (алфавит) теории S;

F – подмножество выражений теории S, называемых формулами теории (под выражениями понимаются конечные последовательности базовых символов теории S); А – выделенное множество формул, называемых аксиомами теории S, т.е. множество априорно истинных формул; R – конечное множество отношений {r1,..., rn} между формулами, называемыми правилами вывода.

Обычно существует эффективная процедура (множество синтаксических правил), позволяющая строить из В синтаксически правильные выражения – формулы;

Для каждого ri существует целое положительное число j, при котором для каждого множества, состоящего из j формул, и для каждой формулы f эффективно решается вопрос о том, находятся ли данные j формул в отношении ri с формулой f. Если отношение riвыполняется, то f называется непосредственнымследствием данных j формул по правилу ri. Следствием (выводом) формулы fn в формальной теории S называется всякая последовательность f1,...,fnформул, при которой для любого i формула fi есть либо аксиома теории S, либо непосредственное следствие каких-либо предыдущих формул по одному из правил вывода. Правила вывода позволяют расширять множество формул, которые считаются истинными в рамках данной теории.

Из символов алфавита можно строить различные выражения. Выделяют термы, элементарные формулы (атомы) и правильно построенные формулы (или просто формулы). Всякий символ переменной или константной буквы есть терм. Если t1,... ,tn (n і 1) – термы, то и fkn (t1,... ,tn) является термом.

Если pkn – предикатная буква, а t1,...,tn – термы, то pkn(t1,...,tn) – элементарная формула (атом). Атом – простейший неделимый элемент. Атом – правильно построенная формула. Если А и В – правильно построенные формулы, то щА, AЪВ, АЩВ, АЙВ есть правильно построенные формулы. Если А – правильно построенная формула и х – переменная в А, то конструкции (х) А и ($х) А – правильно построенные формулы. Выражение является правильно построенной формулой, в том случае, если оно получено с соблюдением приведенных выше правил.

Для того чтобы придать формуле содержание, ее интерпретируют как утверждение, касающееся рассматриваемой предметной области. Под интерпретацией понимают всякую систему, состоящую из непустого множества D, называемого областью интерпретации, и какого-либо соответствия, относящего каждой предикатной букве pkn некоторое n – местное отношение в D; каждой функциональной букве fkn – некоторую n – местную функцию, отображающую Dn®D, и каждой константной букве fk0 – некоторый элемент из D. При заданной интерпретации переменные мыслятся “пробегающими” все значения из области D этой интерпретации, а всякой элементарной формуле приписывается значение “истинно” (И) или “ложно” (Л). Приписывание значения элементарной формуле pkn(t1,...,tn) осуществляется по следующему правилу: если термы предикатной буквы соответствуют элементам из D, удовлетворяющим отношению, определяемому данной интерпретацией, то значением элементарной формулы будет истина, в противном случае – ложь. Значение неэлементарной формулы вычисляется рекуррентно, исходя из значений составляющих ее формул. Очевидно, что значения формул могут быть истинными или ложными в зависимости от выбранной интерпретации.

Основной задачей, решаемой в рамках исчисления предикатов, является выяснение истинности или ложности заданной формулы на некоторой области интерпретации. При этом особая роль отводится общезначимым формулам, т.е. формулам, истинным при любой интерпретации, и невыполнимым формулам, т.е. формулам, ложным при любой интерпретации. Справедлива следующая основополагающая теорема дедукции: пусть даны формулы B1,...,Bn и формула А. Формула А – логическое следствие B1,...,Bn тогда и только тогда, когда формула B1Щ…ЩBnЙА общезначима, т.е. |=(В1Щ...ЩВn)ЙА. Напомним, что формула А логически следует из формул B1,...,Вn тогда и только тогда, когда всякая интерпретация I, удовлетворяющая В1Щ...ЩВn, удовлетворяет также и А. Формулы B1,...,Вn называют посылками, а А – заключением логического следования и обозначают B1,...,Вn |=А.

Задачей доказательства теоремы называют выяснение вопроса логического следования некоторой формулы А из заданного множества формул B1,...,Вn, что равносильно доказательству общезначимости формулы В1Щ...ЩВnЙА или невыполнимости формулы B1Щ…ЩBnЩ|А.

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

Приведем пример записи некоторого факта в виде формулы исчисления предикатов:

ДАТЬ (МИХАИЛ, ВЛАДИМИРУ, КНИГУ);

($х) (ЭЛЕМЕНТ (х, СОБЫТИЕ-ДАТЬ) Щ ИСТОЧНИК (х, МИХАИЛ) Щ

АДРЕСАТ (х, ВЛАДИМИР) Щ ОБЪЕКТ (х, КНИГА).

Здесь описаны два способа записи одного факта: “Михаил дал книгу Владимиру”.

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

Стремление устранить недостатки формальных систем при их использовании в качестве моделей представления привело к появлению семиотических систем. Семиотическая система формально задается восьмеркой:

S = < В, F, A, R, Q(B), Q(F), Q(A), Q(R) >.

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

Семантические сети

Сетевые модели – структуры, состоящие из наборов – поименованных взаимосвязанных двухуровневых деревьев.

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

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

На рис. 2.1 изображен фрагмент простой семантической сети, выражающий примерно следующую информацию: “Михаилу в течение интервала времени [t1,t2] принадлежат ЖИГУЛИ № 25-15”. Михаил есть агент (собственник) в событии В1. Михаил является элементом (э) множества ЧЕЛОВЕК. ЖИГУЛИ № 25-15 – элемент множества МАШИНЫ. Событие В1 – элемент множества всех событий ВЛАДЕТЬ, которое является подмножеством (п) множества СИТУАЦИИ и т.д. Использованные на рис. 2.1 дуги “э” (элемент) и “п” (подмножество) служат для выражения таксономии понятий, представленных вершинами. Важность таксономии заключается в том, что множества обычно имеют свойства, присущие всем элементам данного множества. Эти свойства связываются в сети не с конкретными элементами, а с вершинами, сопоставляемыми всему множеству. Так, дуга “п” указывает отношение быть “подмножеством”. В связи с тем, что большинство подмножеств являются различными, т.е. непересекающимися, для их представления удобно ввести дугу специального вида – “пр” (подмножество различное). Дуга “пр”, идущая из вершины х (например, люди) в вершину z (например, официальные лица), указывает, что множество, представленное вершиной х (люди), есть подмножество множества, представленного вершиной z (официальные лица), и что х (люди) не пересекается ни с каким другим подмножеством, представляемым вершиной r (например, предприятия) и имеющим дугу “пр” из r (предприятия) в z (официальные лица). По аналогии можно ввести и отношение “эр”.

Рис. 2.1. Фрагмент семантической сети

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

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

На рис. 2.2 приведен пример дерева пространств, в соответствии с которым, из пространства Р6 (пространство-потомок) видимы все вершины и дуги, лежащие в пространствах-предках Р4, Р2, Р0, а остальные пространства невидимы. Отношение видимости позволяет сгруппировать пространства в упорядоченные множества –перспективы. Перспектива обычно используется для ограничения сетевых сущностей, видимых некоторой процедурой, работающей с сетью. Обычно в перспективу включают не любые, а иерархически сгруппированные пространства.

Рис. 2.2. Пример разбиения сети на пространства

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

1) вершины и дуги, лежащие в одном пространстве, ограничиваются на рисунках многоугольником (обычно прямоугольником);

2) дуга принадлежит тому пространству, в котором находится имя дуги;

3) пространство Pi (точнее, ограничивающий его многоугольник), изображаемое внутри пространства Pj, считается потомком (внутренним уровнем), т.е. из Pi видимо Pj). Отметим, что пространство Рi может рассматриваться как супервершина, которая лежит в Pj. Свойство невидимости позволяет повысить эффективность операции поиска в сети. Например, при поиске конкретных фактов информация из кванторных утверждений и правил невидима, так как она заключена в пространствах, ограничивающих эти утверждения и правила.

При необходимости в иерархических сетях можно представить любые логические связки и кванторы. На рис. 2.3 и 2.4 приведены представление выражений, содержащих импликацию и квантор всеобщности (выраженный через импликацию) соответственно. Кроме представления логических связок и кванторов сеть может быть использована также для кодирования других структур высших порядков.

Рис. 2.3. Сетевое представление импликации

Рис. 2.4. Изображение в сети квантора всеобщности с использованием импликации

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

Фреймы

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

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

Итак, фрейм-пример может быть представлен в виде следующей конструкции:

f=[<r₁,v₁>,<r₂,v₂>,…,<r_n,v_n>],

где f – имя фрейма, r_i – имя слота, a v_i – значение слота. В качестве значений слотов могут выступать имена других фреймов, что обеспечивает связь между фреймами.

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

Рассмотрим пример фрейма в системе моделирования процесса выдачи банковского кредита под залог (рис. 2.5). Эта система содержит фрейм “Клиент”, который представляет собой класс заемщиков кредита. Он содержит такую информацию, относящуюся к человеку-клиенту, как обеспечение клиента, его ответственность, имущество и т.д.

Фрейм имеет сложную структуру данных, в которой атрибуты фрейма сами являются фреймами. Например, слот “Прилагается к закладной “ сам является фреймом “Кредит под залог” с присущими ему атрибутами.

Значение в слоте “Месячная плата” может быть результатом вычисления по формуле, в которой используются слоты “Количество”, “Ставка” и “Продолжительность”.

Феноменологическая сила фрейм-представления во многом основывается на включении в него предположений и ожиданий. Слотам фрейма могут быть заранее приписаны по умолчанию некоторые стандартные значения. Это позволяет анализировать с помощью фреймов ситуации, в которых отсутствует упоминание о ряде деталей. Стандартные значения, присвоенные по умолчанию, не жестко связаны со своими слотами и могут быть заменены более подходящими значениями, если они найдены в обрабатываемой ситуации. Использование концепции “умолчания” часто позволяет исключить необходимость в кванторных утверждениях.

Рис 2.5. Пример фрейма

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

Необходимо отметить, что фрейм-представление (так же, как декларативное и процедурное представление) является не конкретным языком для представления знаний, а некой концепцией, реализуемой по-разному в таких конкретных языках, как KRL, FRL, K-NET и т.п. В частности, фреймы могут быть представлены с помощью иерархических семантических сетей, как это сделано в K-NET, где некоторое пространство в сети рассматривается как фрейм, а дуги, связывающие это пространство с остальной сетью, рассматриваются как слоты.

Дата добавления: 2019-07-15; просмотров: 196; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 3 4 5 6 789 10 11 12 Следующая ⇒

Мы поможем в написании ваших работ!