Проблемы представления и моделирования знаний.

где F_k - - факт отношения R_j, задаваемый в виде совокупности пар вида «атрибут» — «значение».

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

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

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

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

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

В качестве примера, рассмотрим представление знаний, содержащихся в высказывании «Поставщик N отгрузил товар из склада M автотранспортом». На рис. 5.2. представлена интенсиональная, а на рис. 5.3. – экстенсиональная семантическая сеть. Факты обозначим овалом, а понятия и объекты прямоугольником.

Рис.5.2. Интенсиональная семантическая модель.

Рис.5.3. Экстенсиональная семантическая сеть.

Продукционные модели.

Продукционные модели в последнее время широко использу­ются в системах представления знаний. Первоначально предло­женные Постом в 1943 г. [118], они были впервые применены в системах ИИ в 1972 г. [116].

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

Продукционные модели — это набор, правил вида «условия — действие», где условиями являются утверждения о содержимом некой базы данных, а действия представляют собой про­цедуры, которые могут изменять содержимое БД.

В продукционных системах можно выделить три основные компоненты:

1. Неструктурированная или структурированная БД.

2. Некоторое число продукционных правил или просто продукций. Каждая продукция состоит из двух частей:

условий (антецендент); в этой части определяются некоторые условия, которые должны выполняться в БД для того, чтобы бы­ли выполнены соответствующие действия;

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

3. Интерпретатор, который последовательно определяет, какие продукции могут быть активированы в зависимости от условий, в них содержащихся; выбирает одно из применимых в данной ситуации правил продукций; выполняет действие из выбранной процедуры.

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

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

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

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

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

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

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

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

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

Рассмотрим более подробно некоторые основные формы пред­ставления знаний.

В настоящее время разработано множество моделей представления знаний, используемых для реализации систем, основанных на знаниях, в которых знания представлены с помощью правил вида если-тогда (явление – реакция, условие – действие). Систему продукций можно считать наиболее распространенной моделью представления знаний. Примерами реальных систем, основанных на знаниях, в которых в качестве основной модели представления знаний использовалась система продукций, являются EMYCIN, OPS-5, AGE.

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

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

Исчисление предикатов

Классическим механизмом представления знаний в системах является исчисление предикатов (использовалось уже в 50-х годах в исследованиях по ИИ). В системах, основанных на исчислении предикатов, знания представляются с помощью перевода утверждений об объектах некоторой предметной области в формулы логики предикатов и добавления их как аксиом в систему. Рассмотрим основные положения логики предикатов.

Пусть имеется некоторое множество объектов, называемых предметной областью М. Знаки, обозначающие элементы этого множества, называют предметными константами, а знак, обозначающий произвольный элемент этого множества, – предметной переменной. Терм – это всякая предметная область или предметная константа если f – функциональная n-местная буква, и t₁, t_2, …, t _n – термы, то f(t_1, …, t _n) есть терм.

Выражение Р (x₁, x₂, …, x_n), где x_i, i= - предметные переменные, а Р принимает значения 0 и 1, называется логической функцией или предикатом. Переменные принимают значения из произвольного конечного и бесконечного множества М.

Предикатом или логической функцией называется функция от любого числа аргументов, принимающая истинные значения 1 и 0. Если в данном выражении заменить x_i на y_i, где y_i – предметные константы, то получим элементарную формулу, т.е. предикатные буквы применимы также и к предметным константам. Элементарные формулы иногда называют атомными. Из элементарных формул с помощью логических связок Ú (или), Ù (и), Ø (отрицание), ® (импликация) строят предметные формулы (иногда их называют правильно построенными формулами - ППФ). ППФ – один из важных классов выражений в исчислении предикатов. Кроме логических связок в рассмотрение вводят кванторы общности " или существования $.

Если Р – предметная формула, а х – предметная переменная, то выражения

" х Р(х) и $ х Р(х) также считаются предметными формулами. В логике предикатов для компактной записи высказываний типа: “для любого х истинно Р(х)” и “существует такое х, для которого истинно Р(х)” вводится две новые дополнительные операции: кантор общности " и квантор существования $. Посредством этих операций приведенные выше высказывания записываются в виде " х Р(х) и $ х Р(х). Выражение " х Р(х) обозначает высказывание истинное, когда Р(х) истинно при всех х Î М и ложно в противном случае.

Если P(x) в действительности не зависит от x, то выражения " х Р(х) и $ х Р(х) обозначают то же, что и P(x).

Конкретное вхождение переменной x в формулу P называется связанным, если оно либо непосредственно следует за каким-либо квантором, либо содержится в области действия некоторого квантора " или $. Вхождение переменной является свободным, если оно не является связанным. В выражении " x P(x, y) x- связанная, y- связанная.

Связанной переменной называется переменная, если в P имеется вхождение этой переменной.

Использование обоих кванторов не является обязательным. Рассмотрим выражение , оно обозначает высказывание « ложно», равносильное высказыванию «существует элемент x, для которого P(x)» ложно или, что тоже «существует элемент x, для которого истинно». Следовательно, равносильно выражению : = .

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

Вывод на предикатах.

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

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

Определим основные формы логического вывода.

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

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

Последовательность дедукции определяет “план” того, как достигнуть цели из начального состояния.

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

Процесс стандартизации.

Любую ППФ исчисления предикатов можно представить в виде предложения, применяя к ней последовательность простых операций. Задача состоит в том, чтобы показать, как придать произвольной ППФ форму предложения. Этот процесс (преобразования ППФ в форму предложения) состоит из следующих этапов:

1. Исключение знаков импликации. В форме предложения в исчислении предикатов явно используются лишь связки Ú и Ø . Знак импликации можно исключить в исходном утверждении вместо A®B Ø A \/ B.

2. Уменьшение области действия знаков отрицания. Необходимо, чтобы знак отрицания Ø применялся не более чем к одной предикатной букве.

3. Стандартизация переменных, при которой осуществляется переименование переменных с тем, чтобы каждый квантор имел свою переменную. Так, вместо (" x){P(x) ® ($x)Q(x)} следует написать (" x){P(x) ® ($y)Q(y)}.

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

1. Исключение кванторов существования. Рассмотрим ППФ (" y$x)P(x, y), которую можно интерпретировать, например, так: для всех y существует такой x (возможно, зависящий от y), что x больше y. Заметим, что так как квантор существования ($x) находится внутри области действия квантора общности (" y), допускается, что значение x может зависеть от значения y в x. Пусть эта зависимость определяется явно с помощью некоторой функции g(y), отражающей каждое значение у в х, который «существует». Такая функция называется функцией Сколема. Если вместо x, который “существует”, взять функцию Сколема, то можно исключить квантор существования: (" y) P(g(y), y). Общее правило исключения из ППФ квантора существования состоит в замене в ней всюду переменной, относящейся к квантору существования, функцией Сколема, аргументами которой служат переменные, относящиеся к тем кванторам общности, области действия которых охватывают области действия исключамого квантора существования.

Функциональные буквы для функций Сколема должны быть “новыми”, в том смысле, что они не должны совпадать с теми буквами, которые уже имеются в ППФ. Если исключаемый квантор существования не принадлежит области действия ни одного из кванторов всеобщности, то функция Сколема не содержит аргументов, т.е. является постой константой: так ППФ ($x)P(x) превращается в P(a), где а - константа, про которую известно, что она существует. Чтобы исключить все переменные, относящиеся к кванторам существования, надо применить описанную ранее процедуру по очереди к каждой переменной.

2. Приведение к предваренной нормальной форме (ПНФ).На этом этапе уже не осталось кванторов существования, а каждый квантор общности имеет свою переменную. Теперь можно перенести все кванторы общности (" ) в начало ППФ и считать областью действия каждого квантора часть ППФ. Про полученную таким образом ППФ говорят, что она имеет предваренную нормальную форму (ПНФ). ППФ в ПНФ состоит из цепочки кванторов, называемой префиксом, и расположенной за ней формулы, не содержащей кванторов, называемой матрицей.

3. Приведение матрицы к конъюнктивной нормальной форме (КНФ). Любую матрицу можно представить в виде конъюнкций конечного множества дизъюнкций предикатов и (или) их отрицаний. Говорят, что такая матрица имеет КНФ. Заменить AÚ {BÙ C} на {AÚ B}Ù {AÚ C}.

4. Исключение кванторов общности. Так как все переменные ППФ должны быть связанными, то все оставшиеся на этом этапе переменные относятся к " (общности). Так как порядок расположения кванторов общности несущественен, то эти кванторы можно явным образом не указывать, условившись, что все переменные в матрице относятся к кванторам общности. Таким образом остается лишь матрица в КНФ.

5. Исключение связок Ù, заменой AÙ B двумя ППФ A и B. Результатом многократной замены будет конечное множество ППФ, каждая из которых представляет дизъюнкцию атомных формул и (или) их отрицаний. Атомную формулу или ее отрицание называют литерой (литералом), а ППФ, состоящую лишь из дизъюнкций литер, предложением. Этот процесс называется стандартизацией (т.е. преобразование формул в предложения).

Процесс, демонстрирующий, что некоторое множество F ППФ неудовлетворимо (невыполнимо), начинается с превращения каждой ППФ из множества F в предложение. В результате возникает некоторое множество S предложений. Можно показать, что если множество S неудовлетворимо, то неудовлетворимо и множество F.

Далее используется метод Эрбрана, т.е.к стандартной форме формулы применяют процедуры поиска опровержения, это делается для удобства реализации поиска, т.е. вместо доказательства общезначимости формулы доказывается, что отрицание формулы противоречиво. Возможно использование метода резолюций Робинсона [122].

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

1. Они достаточно хорошо исследованы как формальная система.

2. Существуют яcные правила, т.е. результаты операций над БЗ также достаточно ясно определены.