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

Модели представления знаний

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

 

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

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

Декларативные знания (ДЗ) – это все знания, не являющиеся процедурными, а именно: статьи в энциклопедиях, формулировки законов в физике, химии, других науках и т.д.

Различие между ДЗ и ПЗ можно выразить как различие между “ЗНАТЬ, ЧТО” и “ЗНАТЬ, КАК”. ПЗ основано на предпосылке, что интеллектуальная деятельность есть знание проблемной среды, вложенное в програм­мы, т.е. знание о том, как можно использовать те или иные сущности. ДЗ основано на предпосылке, что знание неких сущностей (“ЗНАТЬ, ЧТО”) не имеет глубоких связей с процедурами, исполь­зуемыми для обработки этих сущностей. При использовании ДЗ счи­тается, что интеллектуальность базируется на некотором универсаль­ном множестве процедур, обрабатывающих факты любого типа, и на множестве специфических фактов, описывающих частную область знаний. Основное достоинство ДЗ по сравнению с ПЗ в том, что в ДЗ нет необходимости указывать способ использования конкретных фрагментов знания. Простые утверждения могут ис­пользоваться несколькими способами, и окажет неудобным фиксировать эти способы заранее. Указанное свойство обеспечивает гибкость и экономичность ДЗ, так как позволяет по-разному исполь­зовать одни и те же факты.

В ДЗ знание рассматривается как множество независимых или слабо зависимых фактов, что позволяет осуществлять модификацию знаний и обучение простым добавлением или устранением утверж­дений. Для ПЗ проблема модификации значительно сложнее, так как здесь необходимо учитывать, каким образом используется дан­ное утверждение. Однако известно, что существует значительное ко­личество сущностей, которые удобно представить в виде процедур и весьма трудно – в чисто декларативном представлении. Желание использовать достоинства ДЗ и ПЗ привело к разработке форма­лизмов, использующих смешанное представление: декларативное с присоединенными процедурами (например, фрейм-представление или сети с присоединенными процедурами) или процедурное в виде модулей с декларативными образца­ми. В наиболее совершенном виде эта проблема реализована в объ­ектно-ориентированном подходе.

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

Продукционная модель представления знаний одна из самых распространенных в интеллектуальных системах. Основу модели составляют системы продукций.

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

Фреймовая модель также широко используется в системах искусственного интеллекта (например в экспертных системах (ЭС)). Фрейм представляет собой минимально возможное описание сущности какого-либо явления, события, ситуации, процесса или объекта.

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

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

Каждая из рассмотренных моделей представления знаний может служить основой для создания языка программирования, ориентированного на работу со знаниями. Такими языками являются язык FRL (Frame Representation Language), основанный на фреймовых представ­лениях, и язык Пролог, опирающийся на модель представления в виде продукций. Однако разные модели представления знаний имеют свои преимущества и недостатки. Поэтому в конце 80-х гг. наметилась тенденция создавать комбинированные языки представления знаний. Чаще всего комбинируются фреймовые и продукционные модели.

 

Алгоритмические модели

Рассмотрим предварительно простую жизненную си­туацию: что следует сделать, если нужно привлечь к ре­шению задачи человека, не знакомого с ее решением:

а) выбирают способ (метод, порядок) решения зада­чи и изучают его во всех подробностях;

б) сообщают исполнителю выбранный метод в абсо­лютно понятном для него виде;

в) исполнитель решает задачу строго в соответствии с методом.

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

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

Второй этап значительно сложнее. Если способ (метод) решения задачи описан произволь­но, то нет гарантии, что он будет верно понят исполните­лем. Поэтому описание метода следует выполнять в со­ответствии с определенными правилами, а именно:

—    выделить величины, являющиеся исходными для задачи;

—    разбить процесс решения задачи на такие этапы, которые известны исполнителю и мо­жно выполнить без всяких пояснений;

—    указать порядок выполнения этапов;

—    указать признак окончания процесса решения за­дачи;

—    указать во всех случаях, что является результатом решения задачи.

Описание метода, выполненное в соответствии с эти­ми правилами, называется алгоритмом решения задачи. Составить такое описание обычно нелегко, но, следуя ему, механически выполняя все указанные в нем этапы в тре­буемом порядке, исполнитель может всегда правильно решить задачу.

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

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

Рассмотрим простейший алгоритм — алгоритм завар­ки чая:

1. Подготовить исходные величины — чай, воду, чай­ник, стакан, ложку.

2. Налить в чайник воду.

3. Довести воду до кипения и снять с огня.

4. Всыпать в чайник чай.

5. Довести воду до кипения (но не кипятить), снять с огня.

6. Чай готов. Процесс прекратить.

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

 

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

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; просмотров: 959; Мы поможем в написании вашей работы!

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

---

---

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