Формализация базы знаний

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

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

Степень структурированности знания

Степень

Определенности степень операционности

(формальности)

				Семантическая модель

Степень динамичности

	Нечеткая логика		Условные вероятности

Степень динамичности

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

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

· Логическая модель реализует и объекты, и правила с помощью предикатов первого порядка, является строго формализованной моделью с универсальным дедуктивным и монотонным методом логического вывода «от цели к данным»;

· Продукционная модель позволяет осуществлять эвристические методы вывода на правилах и может обрабатывать неопределенности в виде условных вероятностей или коэффициентов уверенности, а также выполнять монотонный или немонотонный вывод;

· Семантическая сеть отображает разнообразные отношения объектов;

· Фреймовая модель, как частный случай семантической сети, использует для реализации операционного знания присоединенные процедуры;

· Объектно-ориентированная модель, как развитие фреймовой модели, реализуя обмен сообщениями между объектами, в большей степени ориентирована на решение динамических задач и отражение поведенческой модели.

Логическая модель предполагает унифицированное описание объектов и действий в виде предикатов первого порядка. Под предикатом понимается логическая функция на N – аргументах признаках, которая принимает истинное или ложное значение в зависимости от значений аргументов. Отличие заключается в том, что для объектов соответствующие реляционные отношения задаются явно в виде фактов, а действия описываются как правила, определяющие логическую формулу вывода фактов из других фактов. Пример фрагмента базы знаний подбора претендентов на вакансии в записи логического программирования ПРОЛОГ представлен на рис. (Обозначения “:” – “если”, “”– “и”, “.” – “конец утверждения”).

Vibor (Fio, Dolgnost):-

Pretendent (Fio, Obrasov, Stag),

Vacancy (Dolgnost, Obrasov, Opyt),

Stag>=Opyt.

Pretendent («Иванов», «среднее»10).

Pretendent («Петров», «высшее»12).

Vacancy («менеджер», «высшее», 10).

Vacancy («директор», «высшее», 15).

Рис. Пример фрагмента базы знаний на языке ПРОЛОГ

Механизм вывода осуществляет дедуктивный перебор фактов, относящихся к правилу по принципу «сверху - вниз», «слева - направо» или обратный вывод методом поиска в глубину. Так, в ответ на запрос Vibor (X, Y) получим: Х= «Петров», Y= «менеджер».

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

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

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

В продуктивной модели основной единицей знаний служит правило в виде: “если” <посылка>, то <заключение>, с помощью которого могут быть выражены пространственно-временные, причинно-следственные, функционально-поведенческие (ситуация, действие) отношения объектов. Правилами могут быть описаны сами объекты: «объект - свойство» или «набор свойств - объект», то чаще описания объектов фигурируют только в качестве переменных («атрибут - значение») внутри правил. В основном продукционная модель предназначена для описания последовательности различий ситуаций или действий и в меньшей степени для структурированного описания объектов.

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

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

<A,B,C->D,E>, где

импликация C->D определяет собой собственно правило;

А – предусловие выбора класса правил;

В – предусловие выбора правила в классе;

Е – постусловие правила, определяющее переход на следующее правило.

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

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

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

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

P(H/E) = P(E/H)*P(H)/P(E) и

P(^H/E) = P(E/^H)*P(^H)/P(E),

Где P(H) – априорная вероятность гипотезы Н;

P(^H) – 1-Р(Н) – априорная вероятность отрицания гипотезы Н;

Р(Е) – априорная вероятность свидетельства Е;

Р(Н/Е) – апостериорная (условная) вероятность гипотезы Н при условии, что имеет место свидетельство Е;

P(^H,E) – апостериорная (условная) вероятность отрицания гипотезы Н при условии, что имеет место свидетельство Е;

Р(Е,Н) – вероятность свидетельства гипотезы Е при отрицании гипотезы Н;

Р(Е/^Н) – вероятность свидетельства гипотезы Е при отрицании гипотезы Н.

Найдем отношения левых и правых частей представленных уравнений:

Р(Н/Е) Р(Е/Н) Р(Н)

--------- = ---------- * ------- или

P(^P/E) P(E/^H) P(^H)

O(H/E) = Ls * O(H), где

О(Н) – априорные шансы гипотезы Н, отражающей отношение числа позитивных проявлений гипотезы к числу негативных;

О(Н/Е) – апостериорные шансы гипотезы Н при условии наличия свидетельства Е;

Ls – фактор достаточности, отражающий степень воздействия на шансы гипотезы при наличии свидетельства Е. Аналогично выводится зависимость:

О(Н/^E) = Ln * O(H), где

О(Н/Е) - апостериорные шансы гипотезы Н при условии отсутствия свидетельства Е;

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

Шансы и вероятности связаны уравнениями:

Р О

О = ----- и Р = ------

1-Р О+1

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

Рассмотрим использование байесовского подхода на пример оценки надежности поставщика. Фрагмент подмножества правил представляется следующим образом:

Если Задолженность = «есть», То Финансовое _ состояние = «удовл.»

Ls = 0.01, Ln = 10

Если Рентабельность = «есть», То Финансовое _ состояние = «удовл.»

Ls = 100, Ln = 0.001

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

О(Н/Е1,Е2) = 1* 10 * 100 = 1000;

P(H/E1,E2) = 1000/1001 = 0.99.

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