Лекция 9

представить знания в виде множества предложений типа: Если (условие), то

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

(действие)
В продукционных системах в качестве условия (часто –

множество условий) выступает образец для поиска, а заключением будет вывод о подтверждении некоей гипотезы, факта.
Пример такого продукционного правила:
если Сигнал_датчика_давления = «красный» то ситуация = ТРЕВОГА.
В экспертных системах часто используются правила, в которых посылкой является описание ситуации, а заключением – действия, которые необходимо предпринять в данной ситуации.

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

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

вводимые факты как истинные, отыскивая правила, в состав которых входят

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

новые факты, начиная с уже известных.
Однако отсутствие связи между

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

(факта, который требуется установить) к посылкам. В обратном механизме логического

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

Z отсутствует.
Ищем правило, которое может привести к Z. Это р1:F&BZ
Условия

правила – В и F. В известно.
2. Пытаемся установить факт F.
Ищем правило, которое может привести к F. Это р2: C&DF
Условия правила С и D. С известно.
3. Пытаемся установить факт D.
Ищем правило, которое может привести к D. Это р3:AD
Условие правила А – известно.
Выполняем правила р3, р2, р1. Z доказано

распространение, заключаются в следующем:
продукционные правила легки для восприятия человеком;
достоинством

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

= a1&a2& … &an – конъюнкция условий,
В – заключение,

kpi – коэффициент достоверности продукции pi .
Здесь В – конъюнктивная вершина.
Поставим цель – найти коэффициент достоверности заключения kB. , если известны коэффициенты достоверности посылок a1, a2, … ,an . Обозначим k1, k2, … , kn эти коэффициенты. Их возможные значения лежат в диапазоне от 1 (абсолютно достоверно) до 0 (абсолютно ложно).
Примем, что при kpi =1 степень достоверности заключения не может превосходить степень достоверности самой слабой посылки:
kB =min(k1, k2, … , kn ).
Если kpi <1 , kB =min(k1, k2, … , kn )* kpi.

несколько наборов условий:
pi(kpi): a1&a2& … &an  B (обозначим кратко

AiB ) и
pj(kpj): b1&b2& … &bm  B (обозначим кратко AjB).
Здесь В – дизъюнктивная вершина.
Поставим цель – найти kB.
1.Пусть обе продукции достоверны полностью (kpi =1, kpj =1). Для вершины ИЛИ считаем, что посылки подкрепляют друг друга при получении заключения. Тогда kB = k Ai + k Aj (1 - k Ai)
При условии kpi ≠1, kpj ≠1 получим
kB = kpi k Ai + kpj k Aj (1 - kpi k Ai)

экспертной системе коэффициент достоверности заключения сравнивается с некоторым пороговым значением,

определяемым эмпирически. Цель – исключить наименее достоверные выводы.
Так, в экспертной системе MYCIN это значение равно 0.2).

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

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

«красный» то ситуация = ТРЕВОГА
На объекте расположены 25 различных датчиков,

контролирующих давление, тогда нужно включить в БЗ 25 различных правил, имеющих одинаковую структуру
р1:если Сигнал_датчика_давления_1 = «красный» то ситуация = ТРЕВОГА
р2:если Сигнал_датчика_давления_2 = «красный» то ситуация = ТРЕВОГА…
р25: если Сигнал_датчика_давления_25 = «красный» то ситуация = ТРЕВОГА
Можно построить одно обобщенное правило, например
рgen: если Сигнал_датчика_давления_х[1, 25] = «красный» то ситуация = ТРЕВОГА

продукций. В состав продукций могут входить продукции, содержащие переменные, предикаты.

Включает управление активными фактами и правилами.
Рабочая область (или база фактов). Хранит факты, текущие гипотезы, данные (символьные, числовые, логические). В начале работы рабочее пространство содержит формулировку поставленной задачи; затем добавляются факты, которые программа-интерпретатор установила к текущему моменту.
Программа – интерпретатор решает ряд важных задач: определяет правила, а также относящиеся к ним факты путём унификации; выбирает те правила, которые нужно выполнить (либо все пригодные, либо по оценкам важности); выполняет правило (продукцию) и пополняет базу фактов.

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

на выполнение;
текущий план;
список подзадач.

следующие преимущества:
- модульность;
-наглядность;

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

Такая система предназначена для хранения совокупности знаний о предметной области

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

обычной БД в виде таблиц, задающих отношения между объектами. БД,

в которой хранятся факты, называется экстенсиональной.
Базу данных для хранения общих законов (аксиом) назовём интенсиональной.
Рассмотрим два способа представить отношение «предшествует» (≤).
В интенсиональном представлении определяем:
Если x ≤y и y ≤z, то x ≤z.
Не существует таких x1, x2, … , xm, что
x1 ≤ x2, x2 ≤x3, … , xm-1 ≤ xm, xm ≤x1.
В экстенсиональном представлении мы перечисляем все пары объектов, для которых это отношение истинно. Например, пусть x, y – бинарные векторы длины 3. Тогда экстенсионал отношения включает пары: <0, 0, 0> ≤ <0, 0, 1>
<0, 0, 1> ≤ <1, 0, 1> , …, <1, 1, 0> ≤ <1, 1, 1>

в таком представлении сложно задавать интерпретации.
Экстенсиональное представление обеспечит быстрый поиск

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

экстенсиональной, содержащей факты, и интенсиональной, содержащей правила для логического вывода

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

дизъюнктами Хорна.
Дизъюнкт Хорна – это дизъюнкт, имеющий не более чем

одну положительную литеру. Его вид: A1 A2 …  An  B,
что соответствует формуле
A1 &A2& … &An  B в обычной записи.
Дизъюнкты Хорна без условий – это факты (используются в экстенсиональном представлении).
Дизъюнкты Хорна, имеющие как условие, так и заключение, это аксиомы (общие законы), соответствующие интенсиональному представлению знаний.
Дизъюнкты Хорна без заключения – это отрицания фактов, или цели, которые нужно доказать.

Назовём данные, принимающие значение «ложь», негативной информацией.
Негативная информация может быть

выражена различными способами.
Явно, с помощью негативной фундаментальной литеры (например, Q(a, b, c) ).
Неявно. Путём вывода при использовании некоторых законов.
Например, закон однозначности позволяет вывести факт:
Год рождения(Иванов, 1981) из конкретного факта
Год рождения(Иванов, 1979) и аксиомы «Каждый человек имеет единственный год рождения».
Негативная информация создаёт трудности при её обработке.

замкнутом мирах.
В предположении о замкнутом мире мы считаем, что

располагаем полным знанием о предметной области.
В предположении об открытом мире как позитивная, так и негативная информация должна быть представлена явно, таким образом допускаются «бреши» в знании о ПО.
Рассмотрим пример. Пусть имеется множество
{Амосов, Дубинский, Григорьев, Перескоков} – лекторы;
{Смирнов, Петров, Парамонов, Галкин} – студенты.
Представлено отношение «Обучает»:

замкнутом мире мы получим ответ «Лекторы, не обучающие студента Петрова,

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

число негативных фактов огромно, и перечислять их бессмысленно. Поэтому явно

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