Искусственный интеллект

 

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

При описании знаний в декларативных языках могут  быть использованы:

1. Правила.
2. Фреймы.
3. Логические подходы.
4. Семантические сети.
5. Антологии.
6. Другие структуры.

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

Продукционные системы – подкласс систем, основанных на правилах. Состоят из БД и БП, которые составляют БЗ продукционной системы. БД ориентирована на размещение структур определенных типов, представляющих факты и утверждения об предметной области, а также описание концептуальных объектов, целей и отношений, используемых при решении ПЗ. Правило – структура, состоящая из левой и правой части. Левая (условная часть) описывает конфигурацию данных к которой применимо правило и представляет собой образец по которому в базе осуществляется поиск. Обычно левая часть представляет собой булеву комбинацию предложений некоторого языка, которые специфицируют ограничение, назначение свойств или атрибутов объектов, составляющих ситуацию, в которой применимо данное правило. Правая часть – действие,  в общем случае – список модификаций, которые должны быть произведены над БД когда правило активировано (найдены элементы данных, отвечающие образцам левой части). Кроме того, правая часть может содержать указание на добавление, изменение или удаление элемента БД, кроме того иногда допускаются внешние операции, модификации базы правил, а также используется в качестве действий произвольных процедур. Процесс обработки знаний в продукционных системах описывается независимой от предметных знаний процедурой вывода, представляющей собой цикл – «распознавании действия».

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

Процесс распознавания  включает два этапа:

1. Этап сопоставления образцов.
2. Этап выбора правила из конфликтного множества.

Этап сопоставления. В продукционных системах применяются различные типы сопоставления:

1. Синтаксическое. Предполагает, что образец в левой части правила должен быть посимвольно идентичен элементу БД.
2. Семантическое. Предполагает удовлетворение некоторым условиям элементов БД, при условии, что эти элементы соответствуют определенному образцу.
3. Сопоставление по образцу. В левой части правила используются переменные, во время установления соответствия переменные в условии связываются (замещаются) константой из БД. И это связывание последовательно используется во всем правиле, и в условной части и в части действия.

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

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

1. Упорядочивание продукции. Над продукциями задается полный порядок. Применяется та продукция, которая имеет максимальный приоритет.
2. Упорядочивание данных. Упорядочиваются элементы БД и применяется та продукция их конфликтного множества, образцом для которой служат данные с максимальным приоритетом.
3. Использование атрибутов новизны, доверия и других. Из конфликтного множества выбирается та продукция, образцом для условий которой служат данные с максимальной новизной и/или доверием.
4. Применяется продукция с наиболее жесткими требованиями (самый длинный список условий).
5. Иерархия продукции задается в виде сети предшествования

Процедура разрешения конфликта и информацию о последовательности применения продукции в БД – управляющая  стратегия. Обычно выделяют два класса:

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

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

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

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

Фреймы представляют средство для описания объектов, типов  объектов и понятий предметной области, при этом модель представления знаний строиться в виде сети фреймов, то есть системы определенным образом взаимосвязанных фреймов.

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

Фрейм-прототип — это обобщенное (интенсиональное) описание некоторого множества фрейм-примеров.

Фрейм-пример —  конкретизированное (экстенсиональное) описание соответствующего фрейма-прототипа.

В общем виде фрейм может быть описан следующим  образом:

<фрейм>:=<имя  фрейма> <слот 1>...<слот n>,

<слот>:=<имя  слота>:<заполнитель слота 1>...<заполнитель слота n>,

<заполнитель  слота >:=<значение слота>/<фасет>,

<значение слота>:=<имя  фрейма>/<константа>,

<фасет>:=<имя  фасета>(<значение фасета>,...,<значение  фасета>),

<значение фасета>:=<константа>/<имя  фрейма>

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

Часто помимо слота  надкласса присутствует слот подкласса, перечисляющий подклассы объекта, представленного данным фреймом, связи  принадлежности (от элемента к классу и от класса к элементу) представляют собой две интерпретации отношения «является» (is-a). Слоты обычно могут иметь множество значений и набор свойств, представляющих ограничения, либо описания числа и типа значений слота. Конструкции, отражающие эти ограничения и свойства называют фасетами. Значениями слота могут быть: константы либо имена других фреймов. Фасеты могут описывать возможный интервал, тип, структуру, ограничение на число значений, представлять значения, принимаемые по умолчанию, а также процедурные присоединения, что позволяет включать во фреймы обычные процедуры. В случае, когда фасет описывает процедурное присоеденение вставляемая процедура вызывается заполнителем этого фасета. Например, (Вычислить(стоимость производства(цена))), в таком фасете заполнитель извлекает фрейм с именем стоимость производства, содержащим некую процедуру, а полученное в результате выполнения этой процедуры значение заносится в поле цена. Для представления структуры общих понятий в определенной предметной области фреймы могут формироваться в сети (обычно в иерархии).

Рассмотрим пример иерархической структуры фреймов  и отдельных элементов этой структуры.

Часть сети фреймов  для понятие физический объект:

Фрейм:Физические объекты

…

Слот элемента:Длина:

класс значений (положительное число)

минимальное число значений (1)

максимальное  число значений (1)

размерность (км)

значение (неизв.)

Слот элемента:Масса:

класс значений (положительное число)

минимальное число  значений (1)

максимальное  число значений (1)

размерность (т)

значение (неизв.)

Слот элемента:Одушевленность:

класс значений (одушевленный, неодушевленный)

минимальное число  значений (1)

максимальное  число значений (1)

значение (неизв.)

по умолчанию (неодушевленный)

Слот собственный:Максимальная длина:

класс значений (положительное число)

минимальное число значений (1)

максимальное  число значений (1)

размерность (км)

значение (2)

Слот собственный:Максимальный вес:

класс значений (положительное число)

минимальное число  значений (1)

максимальное  число значений (1)

размерность (т)

значение (100)

Фрейм:Поезда:

Надклассы:

Сухопутный транспорт

(средство передвижения

(Физический  объект))

Подклассы:

Грузовые

Почтовые

Пассажирские

Слот Элемента:Статус:

класс значений (международный, внутренний)

минимальное число  значений (1)

максимальное  число значений (1)

значение (неизв.)

Слот Элемента:Вагоны: