Скачать 1.04 Mb.
|
2.8. Модели представления знанийОсновными классическими моделями на сегодняшний день являются фреймы, семантические сети, исчисления предикатов первого порядка, комбинация трех перечисленных моделей, продукционные системы. Фреймы Фрейм - структура данных для представления стереотипной ситуации. Фрейм определяется имением и совокупностью слотов. Слоты могут иметь различные значения и оставаться незаполненными для конкретной ситуации. Слоты могут характеризовать объекты, классы и утверждения. Значением слота может быть имя другого фрейма. Слоты фрейма, кроме декларативного и процедурного назначения, могут определяться принудительно следующим образом:
Таким образом, фрейм может определять исходные состояния, например, состояние А и переход в новое состояние В на основе исходного описания с помощью фрейма А’ в новое состояние, описываемое фреймом В’. При использовании фреймового представления предполагается, что значения верхних слотов фрейма заданы, а значения нижних слотов фрейма заполняются в соответствии с ситуацией. Использование фреймов можно сравнить с использованием процедур в традиционных языках программирования. Описание процедуры в программе представляет собой фрейм-прототип. Действие, выполняемое процедурой, соответствует понятию фрейм-реализации. Использование фреймов предполагает реализацию в информационной системе на основе объектно-ориентированного подхода, где классы объединяют в совокупности однотипных объектов. Объекты имеют свойства, характерные для данного класса. При построении иерархии классов устанавливается соответствие между классами и фреймами и характеристиками объектов со слотами. Родственные свойства объектов наследуются, то есть объект, находящийся на нижнем уровне классификации, имеет все свойства, присущие данному классу объектов. Свойства объектно-ориентированной технологии:
В отличие от описания процедур в традиционных языках программирования использование фреймов осуществляется не только по имени, но и по состоянию фрейма, описывающего ситуацию. Таким образом можно получить модель состояния В’, имея только часть информации о состоянии А’. Все модели представления данных предназначены для воплощения в правилах логического вывода. Этот основное назначение модели. Модели в правилах представляются утверждениями. Фрейм — информационная структура, содержащая описание объекта в виде атрибутов и их значений. В отличие от моделей других типов во фреймовых моделях фиксируется жесткая структура информационных единиц, которая называется протофреймом. В общем виде она выглядит следующим образом: (Имя фрейма: Имя слота 1(значение слота 1) Имя слота 2(значение слота 2) . . . . . . . . . . . . . . . . . . . . . . Имя слота К (значение слота К)). Значением слота может быть практически что угодно (числа или математические соотношения, тексты на естественном языке или программы, правила вывода или ссылки на другие слоты данного фрейма или других фреймов). В качестве значения слота может выступать набор слотов более низкого уровня, что позволяет во фреймовых представлениях реализовать "принцип матрешки". При конкретизации фрейма ему и слотам присваиваются конкретные имена и происходит заполнение слотов. Таким образом, из протофреймов получаются фреймы - экземпляры. Переход от исходного протофрейма к фрейму - экземпляру может быть многошаговым за счет постепенного уточнения значений слотов. Пример. Рассмотрим структуру фрейма табл. 2: Таблица 2.
(Список работников: Фамилия (значение слота 1); Год рождения (значение слота 2); Специальность (значение слота 3); Стаж (значение слота 4)). Если в качестве значений слотов использовать данные табл. 2.1, то получится фрейм – экземпляр. (Список работников: Фамилия (Попов - Сидоров - Иванов - Петров); Год рождения (1965 - 1946 - 1925 - 1937); Специальность (слесарь - токарь - токарь - сантехник); Стаж (5 - 20 - 30 - 25)). Связи между фреймами задаются значениями специального слота с именем "Связь". Фрейм-реализация - это внешние ссылки пространства и настройка на конкретную ситуацию. Семантические сети В традиционном понимании семантическая сеть - это конструкция двух основных компонентов: узлов и дуг. Узлы моделируют понятия предметной области, дуги моделируют отношения между парой понятий. Пример: Петр работает Отдел С помощью семантической сети можно промоделировать достаточно сложные отношения между различного рода понятиями, описывающими достаточно много состояний проблемной области. Рассмотрим Рис. 5. является имеет имеет является руководит гараж Петр 1 Петр 2 имеет работает имеет не имеет администрация адрес возраст стоянка для машины служащие «Петрова 5» Таб. № находится Рис.5. Пример семантической сети Отношения между объектами в семантической сети можно установить как «все со всеми», то есть каждый узел семантической сети может иметь отношение с каждым ее узлом. Семантическую сеть можно представить в виде бинарного предиката, или в виде отношения с двумя аргументами ( работает (Петр, отдел), в общем виде – работает (Х,Т) ). Представить эту информацию можно в списковой структуре данных. Кроме того, описание семантической сети можно представить в виде n - аргументного отношения между понятиями при условии, что имя отношения будет иметь одно и то же значение. При реализации семантической сети в Базе Данных (БД) информация описывается в виде троек: объект, атрибут, значение (то, что присуще БД). Недостатки использования семантической сети:
Семантические сети используются в основном для представления декларативной информации. Основные виды отношений, используемых в моделях представления знаний:
а) причина и следствие (в прямой цепочке логических рассуждений); б) следствие и причина (в обратной цепочке логических рассуждений);
а) арифметические; б) логические;
а) отношение принадлежности - это часть целого или целое части;
а) атрибутивные иметь свойство быть свойством б) идентифицирующие быть именем иметь имя
а) иметь количественное значение; б) иметь лингвистическое значение;
а) изменить положение; б) изменить ориентацию (на 900);
а) быть раньше; б) быть позже; в) быть одновременно;
а) быть расположенным; б) расстояние между;
выполняться с помощью Исчисление предикатов I-го порядка Основные компоненты данной модели являются:
Факт является основной единицей модели представления знаний. Факт - это отношение (предикат), которое представляет объект и совокупность свойств объекта или процедур, которые определяются аргументами. Аргументы в предикатах задаются с помощью констант или с помощью переменных. Пример: является (Петр, Х) живет (У, Йошкар-Ола, Т) где Х, У, Т - переменные, которые определяют интерпретацию факта в утверждении. Аналогом утверждения в исчислении предикатов является понятие «высказывание». Высказывание - это элементарное утверждение для использования в сложном предложении. Правила формирования предикатов:
Простейшим видом утверждений в модели представления знаний являются правила. В общем смысле, правила - это сложные умозаключения или высказывания, которые формируются из простых высказываний с помощью соответствующих связок &(and), (or), ~(not), (импликация). Связка импликация () предназначена для формирования каузального отношения. Пример:
Используют для утверждения истинности на основе фактов, заданных в исходных данных (база данных) или на основе интерпретации значений переменных при доказательстве. Мерой истинности переменных, используемых при доказательстве правила или сложного высказывания являются кванторы. квантор общности; квантор существования. Квантор общности читается: «Для всех Х» и определяет область «все». Квантор существования читается, как «Существует значение переменных Х» и определяется как «некоторые». Замечание: между кванторами не допустимо использование связок. Связки используются только между высказываниями. Пример: - руководит (Y,X) & отчитывается (X,Y) - руководит (Y,X) & отчитывается (X,Y). 4.Утверждения На языке логики предикатов утверждения могут быть представлены:
Правила вывода - это сложные предложения, которые определяют новые правила и факты, то есть правила вывода предназначены для задания новых стратегий с использованием новых фактов. Рассмотрим выводы: -(X) руководит (X,Y) отчитывается (Y,X) (правило) -(X,Y,Z) руководит (X,Y) & руководит (X,Z) отчитывается (Z,Y) (правило вывода), то есть отсюда выводится новое правило: руководит(Y,Z) Логика предикатов, называемая также логикой первого порядка, допускает четыре типа выражений.
Символы, которые применяются для представления констант, переменных, предикатов и функций, не являются "словами русского языка". Они суть символы некоторого представления - слова "объектного языка" (в нашем случае языка предикатов). Представление должно исключать всякую двусмысленность языка. Поэтому имена индивидуумов содержат цифры, приписываемые к именам совокупностей. Жак_1 и Жак_2 представляют двух людей с одинаковыми именами. Эти представления суть конкретизации имени совокупности "Жак". Предикат - это предикатное имя вместе с подходящим числом термов. Примеры применения логики для представления знаний Проиллюстрируем синтаксис логики предикатов, сопоставляя нескольким русским фразам их перевод на язык логического формализма.
Логически: Посылка (Жак_2, Мари_4, Книга_22).
Логически: " x ( Человек(x) É Прогуливается(x)).
Логически: $ x (Человек(x) Ù Прогуливается(x)). Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. Сравнивая два последних примера, видим, что замена прилагательного "каждый" на "некоторые" влечет при переводе не только замену квантора " на $, но и замену связки É на Ù. Это иллюстрирует тот факт, что перевод фразы естественного языка на логический, вообще говоря, не является трафаретной операцией. По русски: Ни один человек не прогуливается, Логически: Ø ($ x (Человек(x) Ù Прогуливается(x))). В исчислении предикатов имеется множество правил вывода. В качестве примера приведем классическое правило отделения : (A, A -> B) / B которое читается так "если истинна формула A и истинно, что из A следует B, то истинна и формула B ".Формулы, находящиеся над чертой, называются посылками вывода, а под чертой - заключением. Это правило вывода формализует основной закон дедуктивных систем: из истинных посылок всегда следуют истинные заключения. Аксиомы и правила вывода исчисления предикатов первого порядка задают основу формальной дедуктивной системы, в которой происходит формализация схемы рассуждений в логическом программировании. Можно упомянуть и другие правила вывода.
Решаемая задача представляется в виде утверждений (аксиом) f1, f2... fn исчисления предикатов первого порядка. Цель задачи B также записывается в виде утверждения, справедливость которого следует установить или опровергнуть на основании аксиом и правил вывода формальной системы. Тогда решение задачи (достижение цели) сводится к выяснению логического следования (выводимости) целевой формулы B из заданного множества формул (аксиом) f1, f2... fn. Такое выяснение равносильно доказательству значимости (тождественно- истинности) формулы f1& f2&... & fn -> B или невыполнимости (тождественно- ложности) формулы Из практических соображений удобнее использовать доказательство от противного, то есть доказывать невыполнимость формулы. На доказательстве от противного основано и ведущее правило вывода, используемое в логическом программировании, - принцип резолюции. Робинсон открыл более сильное правило вывода, чем modus ponens, которое он назвал принципом резолюции (или правилом резолюции ). При использовании принципа резолюции формулы исчисления предикатов с помощью несложных преобразований приводятся к так называемой дизъюнктивной форме, то есть представляются в виде набора дизъюнктов. При этом под дизъюнктом понимается дизъюнкция литералов, каждый из которых является либо предикатом, либо отрицанием предиката. Приведем пример дизъюнкта: Пусть P- предикат уважать, c1- Ключевский, Q- предикат знать, c2- история. Теперь данный дизъюнкт отражает факт "каждый, кто знает историю, уважает Ключевского". Приведем еще один пример дизъюнкта: Пусть P- предикат знать, c1- физика, c2- история. Данный дизъюнкт отражает запрос "кто знает физику и историю одновременно". Таким образом, условия решаемых задач (факты) и целевые утверждения задач (запросы) можно выразить в дизъюнктивной форме логики предикатов первого порядка. В дизъюнктах кванторы всеобщности , обычно опускаются, а связки заменяются на импликацию. Вернемся к принципу резолюции. Главная идея этого правила вывода заключается в проверке того, содержит ли множество дизъюнктов R пустой (ложный) дизъюнкт. Обычно резолюция применяется с прямым или обратным методом рассуждения. Прямой метод из посылок A, A -> B выводит заключение B (правило modus ponens). Основной недостаток прямого метода состоит в его не направленности: повторное применение метода приводит к резкому росту промежуточных заключений, не связанных с целевым заключением. Обратный вывод является направленным: из желаемого заключения B и тех же посылок он выводит новое подцелевое заключение A. Каждый шаг вывода в этом случае связан всегда с первоначально поставленной целью. Существенный недостаток метода резолюции заключается в формировании на каждом шаге вывода множества резольвент - новых дизъюнктов, большинство из которых оказывается лишними. В связи с этим разработаны различные модификации принципа резолюции, использующие более эффективные стратегии поиска и различного рода ограничения на вид исходных дизъюнктов. В этом смысле наиболее удачной и популярной является система ПРОЛОГ, которая использует специальные виды дизъюнктов, называемых дизъюнктами Хорна. Процесс доказательства методом резолюции (от обратного) состоит из следующих этапов:
Рассмотрим примеры применения методов поиска решений на основе исчисления предикатов. Итак, заданы утверждения 1- 4 в левом столбце таблица 3. Требуется ответить на вопрос: "Существует ли человек, живущий интересной жизнью?" В виде предикатов эти утверждения записаны во втором столбце таблицы. Предполагается, что . В третьем столбце таблицы записаны дизъюнкты. Отрицание заключения имеет вид (строка 6): Символ NIL означает, что база данных выражений содержит противоречие и поэтому наше предположение, что не существует человек, живущий интересной жизнью, неверно. В методе резолюции порядок комбинации дизъюнктивных выражений не устанавливался. Значит, для больших задач будет наблюдаться экспоненциальный рост числа возможных комбинаций. Поэтому в процедурах резолюции большое значение имеют также эвристики поиска и различные стратегии. Одна из самых простых и понятных стратегий - стратегия предпочтения единичного выражения, которая гарантирует, что резольвента будет меньше, чем наибольшее родительское выражение. Ведь в итоге мы должны получить выражение, не содержащее литералов вообще. Исследования, связанные с доказательством теорем и разработкой алгоритмов опровержения резолюции, привели к развитию языка логического программирования PROLOG (Programming in Logic). PROLOG основан на теории предикатов первого порядка. Логическая программа - это набор спецификаций в рамках формальной логики. Основные недостатки модели исчисления предикатов Доказательство на языке логики предикатов происходит монотонно и аддитивно, то есть рассуждения с помощью описания их предикатами не соответствует мыслительной деятельности эксперта. В языке логики предикатов монотонность определяет последовательное применение всех правил в надежде, что какое-то из правил приведет к результату. Однако, это может привести к комбинаторному взрыву, кроме того в применении логики отсутствует операционное варьирование правилами, то есть какое правило должно использоваться в данный момент не фиксируется. Основные формализмы (инструментальные средства) представления знаний Язык обработки списков LISP В языке LISP осуществляется обработка списка аргументами, которыми могут быть объекты, свойства объектов и функции. В свою очередь каждая функция может быть представлена списком, среди аргументов которого может быть другая функция. Списками в языке LISP определяются все предикаты. Пример: (руководит, X,Y(отчитывается,X,Y)) Работа формализма ориентирована на обработку функций. Управляющая структура языка LISP находит среди аргументов списка описание состояния объекта или ситуации и выполняет процедуру, включенную в этот список. Если процедура содержит список, то он сопоставляется с текущей ситуацией. Управляющая структура языка LISP ориентирована на сопоставление с образцом, а модель на исчисление предикатов. Управляющая структура - это механизм применения правил в заданной модели с целью получения решений. Язык логического программирования PROLOG Prolog реализует управляющую структуру в виде обратной цепочки логического вывода, то есть используется доказательство от противного. Этим частично исключается монотонность. Язык FORLOG. Язык предназначен для обработки математических системных областей, которые можно описать с помощью математических формул.
Одна из областей используемых для данной модели является так называемая система сопоставления образцов. Данная модель используется при разработке системы искусственного интеллекта, по обработке изображений, лингвистической обработки текста, распознавания речи. Основным элементом модели является функция. Функция - это элементарное предложение, простое для обработки и понимания его экспертом. Функции связаны между собой в сеть. Значения данных объединены в структуре данных. Описание структуры определяют значения данных для формирования информационного ядра. Элементы информационного ядра являются аргументами функции. Та функция, которой соответствует информационное ядро при сопоставлении, загружается. Сеть функций дополняет доказательство для получения решений. |