4.4. основы построения и использования механизмов логического вывода

4.4. основы построения и использования механизмов логического вывода

 

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

Как следует из определения, для работы МЛВ необходима как "долговременная" информация, содержащаяся в БЗн в выбранном при разработке ЭС виде, так и "текущая", оперативная информация, поступающая в РП после обработки в лингвистическом процессоре запроса пользователя. Таким образом, БЗн отражает основные (долговременные) закономерности, присущие предметной области. Запрос пользователя, как правило, связан с появлением каких-либо новых фактов и/или с возникновением потребности в их толковании.

Перед рассмотрением конкретных МЛВ подчеркнем несколько важных обстоятельств:

единого МЛВ для произвольных СОЗ (ЭС) не существует;

МЛВ полностью определяется моделью представления знаний, принятой в данной системе;

существующие МЛВ не являются строго фиксированными ("узаконенными") для каждого типа СОЗ (ЭС).

 

4.4.1. Механизм логического вывода в продукционных системах

Из всех известных механизмов вывода данный механизм является наиболее формализованным (предопределенным). Различают два типа логического вывода:

прямой вывод (прямая цепочка рассуждений);

обратный вывод (обратная цепочка рассуждений).

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

В терминах "факты — правила" формирование цепочки вывода заключается в многократном повторении элементарных шагов "сопоставить — выполнить".

Рассмотрим следующий пример [54]. В базе знаний некоторой ЭС содержатся три правила, а в рабочей памяти до начала вывода — пять фактов: В, С, Н, G, Е (см. рис. 4.4.1, а). Пусть на вход системы (в РП) поступил факт А. Механизм вывода "просматривает" левые части правил с целью нахождения таких из них, которые позволяют извлечь новые факты (процедура "сопоставить"). В нашем примере на основе третьего правила выводится факт D. Происходит элементарный шаг "выполнить" — данный факт заносится в РП (рис. 4.4.1, б). Процедура "сопоставить" по фактам С и D выявляет факт F. После шага "выполнить" в РП попадает этот факт (рис. 4.4.1, в). По фактам F и В выводится факт Z, и дальнейший "просмотр" правил БЗн новой информации не дает.

Таким образом, прямая цепочка рассуждений состоит из следующих фактов: А — D — F — Z. Иными словами, из факта А на основе имеющихся в БЗн правил "получен" факт Z.

выполнить

 

Отметим, что, несмотря на очевидную простоту прямого вывода для пользователя ЭС, от которого требуется лишь сообщить системе о вновь поступивших или интересующих его фактах, для БЗн со значительным числом правил могут возникнуть две проблемы:

когда завершить вывод;

как обеспечить непротиворечивость правил.

Последнее обстоятельство требует формирования и хранения в ЭС так называемых метаправил — правил "работы с правилами". Кроме того, прямая цепочка рассуждений иногда требует значительного времени.

Механизм обратного вывода имеет совершенно иной алгоритм. Его идея заключается в проверке справедливости некоторой гипотезы (некоторого суждения, факта), которая выдвигается пользователем и проверяется ЭС. При этом осуществляется проверка истинности не левых, а правых частей продукций, а вопрос формулируется так: "Что нужно, чтобы правая часть данного правила была справедлива, и есть ли необходимые суждения в рабочей памяти?" На рис. 4.4.2 показана работа механизма обратного вывода для того же примера, что для прямой цепочки рассуждений (в предположении, что факт А занесен в РП).

При реализации данного механизма пополнения РП новыми (выведенными) фактами не производится, а лишь проверяется наличие необходимых суждений на очередном шаге алгоритма. Как следует из рис. 4.4.2, а, поскольку непосредственно факта Z в РП нет, производится анализ правых частей правил до поиска такого правила, которое обосновывает справедливость суждения Z. Чтобы факт Z был истинным, необходимы факты FhB. Факт В есть, факта F — нет (рис. 4.4.2, б). Чтобы факт F был истинным, необходимы факты ChD. Факт С есть, факта D — нет (рис. 4.4.2, в). Наконец, чтобы был справедлив факт D, нужно наличие факта А, и так как он в РП имеется, обратный вывод закончен. Окончательный результат — на основании имеющихся в ЭС правил и фактов гипотеза о справедливости факта Z подтверждается.

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

 

Z"ecTb?

"А" есть, обратный вывод закончен

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

На рис. 4.4.3 представлен фрагмент блока "Контроль" ЭС (решающей задачи обучения), позволяющий оценивать ответы студентов на зачетах и экзаменах по следующей схеме: обучаемый получает три основных вопроса и отвечает на них.

ЕСЛИ по одному из вопросов получена оценка 2 ТО итоговая оценка не может быть выше 3.

ЕСЛИ по двум и более вопросам получены оценки 2 ТО итоговая оценка — 2.

ЕСЛИ по итогам ответов на основные вопросы обучаемый набрал 14 баллов

ТО необходимо задать дополнительный вопрос. ЕСЛИ ответ на дополнительный вопрос оценивается 5 ТО итоговая оценка — 5.

ЕСЛИ ответ на дополнительный вопрос оценивается 4 ТО итоговая оценка — 4.

ЕСЛИ ответ на дополнительный вопрос оценивается 3 ТО итоговая оценка — 4.

ЕСЛИ по итогам ответов на основные вопросы обучаемый набрал 8 баллов

ТО необходимо задать дополнительный вопрос. ЕСЛИ ответ на дополнительный вопрос оценивается 5 ТО итоговая оценка — 3.

ЕСЛИ ответ на дополнительный вопрос оценивается 4 ТО итоговая оценка — 3.

ЕСЛИ ответ на дополнительный вопрос оценивается 3 ТО итоговая оценка — 3.

ЕСЛИ по одному из вопросов получена оценка 3 ТО итоговая оценка не может быть выше 4.

ЕСЛИ по итогам ответов на основные вопросы набрано 9—10 баллов

ТО итоговая оценка — 3.

ЕСЛИ по итогам ответов на основные вопросы набрано 11—13 баллов

ТО итоговая оценка — 4.

Рис. 4.4.3. Фрагмент продукционной базы правил блока "Контроль" автоматизированной обучающей системы

Преподаватель оценивает каждый ответ по четырехбалльной шкале.

Экспертная система либо сразу рекомендует выставить итоговую оценку, либо "советует" задать дополнительный вопрос и уже по результату ответа на него рекомендует итоговую оценку. В ЭС хранятся знания о существующих в институте правилах оценивания уровня подготовленности обучаемых. Так, например, если на экзамене некий студент на "отлично" ответит два вопроса билета, а третий будет оценен на "хорошо", рекомендуется задать ему дополнительный вопрос. Если на него дается отличный ответ, общая оценка — "отлично"; хороший или удовлетворительный ответ — "хорошо"; неудовлетворительный ответ — "удовлетворительно".

 

4.4.2. Понятие о механизме логического вывода в сетевых системах

Механизм логического вывода в сетевых системах основан на использовании двух ведущих принципов:

принцип наследования свойств;

принцип сопоставления по совпадению.

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

связь "есть", "является" (англ. IS-A);

связи "имеет часть", "является частью" (англ. HAS-PART, PART-OF).

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

Принцип сопоставления по совпадению основан на представлении вопроса к системе в виде фрагмента семантической сети с использованием тех же названий сущностей (узлов) и связей, что и в основной сети, и реализации процедуры "наложения" вопроса на сеть и поиска такого его положения, которое соответствует ответу на вопрос. На рис. 4.4.4, б, помимо уже известной связи "есть", представлено отношение владения (связь "владеет"). Вопрос "Чем владеет Иван?" формализуется с помощью узла "Иван" и отношения "владеет". Далее в простейшем случае осуществляется перебор узлов сети, имеющих имя "Иван" (если они имеются), и поиск такого из них, который имеет связь "владеет". Далее может быть задействован принцип наследования свойств. Ответами на поставленный в примере вопрос будут суждения "Иван владеет автомобилем" и "Иван владеет (автомобилем) ВАЗ 2105". Понятно, что в практике использования ЭС такого типа приходится реализовывать значительно более сложную процедуру поиска, включающую элементы семантического анализа.

HAS-PART

а)

4.4.3. Понятие о механизме логического вывода во фреймовых системах

Как уже отмечалось в п. 4.2.2, обычно фреймовая модель знаний имеет сложную иерархическую структуру, отражающую реальные объекты (понятия) и отношения (связи) некоторой предметной области. Механизм логического вывода в таких ЭС основан на обмене значениями между одноименными слотами различных фреймов и выполнении присоединенных процедур "если-добавлено", "если-удалено" и "если-нужно". Условная схема таких действий для простейшего варианта представлена на рис. 4.4.5.

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

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

Рассмотрим более конкретный пример, иллюстрирующий работу фреймовой ЭС, используемой в подразделении, организующем научно-исследовательскую работу (НИР) в некотором учреждении. На рис. 4.4.6 представлена иерархия справочной информации об отчете по НИР (о понятии, узле "отчет по НИР").

 

Этапный отчет по НИР

Автор: Руководитель НИР (по умолчанию) "Шифр:

Дата:

Объем: 40 страниц (по умолчанию)

Рис. 4.4.7. Структура понятий "Отчет по НИР" и "Этапный отчет по НИР"

Рис. 4.4.8. Структура понятия "Этапный отчет по НИР "Залив" 382

Фреймовая система функционирует следующим образом. Пусть в ЭС поступил запрос от полномочного пользователя: "Необходима информация о ходе выполнения НИР "Залив" (напомним, что, как правило, язык исходного запроса близок к естественному). Информация проходит через лингвистический процессор, анализируется и в виде значения "Залив" вносится в слот Шифр узла "Этапный отчет по НИР "Залив". Далее начинают работать присоединенные процедуры:

процедура "Если-добавлено", связанная со слотом Шифр, выполняется, поскольку в слот было введено некоторое значение. Эта процедура осуществляет поиск сведений о руководителе НИР "Залив" (в нашем примере — Иванов И. И.) и вписывает это имя в слот Автор узла "Этапный отчет по НИР "Залив";

процедура "Если-добавлено", связанная со слотом Автор, выполняется, так как в слот было вписано значение. Эта процедура начинает составлять сообщение, чтобы отправить его Иванову И. И., но обнаруживает, что отсутствует значение слота Дата;

процедура "Если-добавлено", просматривая слот Дата, и найдя его пустым, активизирует процедуру "Если-нужно", связанную с этим слотом. Процедура найдет текущую дату, используя календарь ЭС, выберет ближайшую к ней (но большую) дату представления отчета (в нашем примере — 31.03.2003) и впишет ее в слот Дата;

процедура "Если-добавлено", связанная со слотом Автор, найдет, что отсутствует еще одно значение, необходимое для формирования выходного сообщения, а именно — значение слота Объем. Данный слот (узла "Этапный отчет по НИР "Залив") не имеет присоединенных процедур, поэтому приходится брать значение по умолчанию из одноименного слота общей концепции "Этапного отчета по НИР" (в нашем примере — 40 страниц).

Теперь ЭС может сформировать выходное сообщение типа: "Этапный отчет по НИР "Залив" должен быть представлен Ивановым И. И. к 31 марта 2003 г. Предполагаемый объем отчета — 40 страниц" и/или "Иванов И. И.! Представьте этапный отчет по НИР "Залив" объемом не более 40 страниц к 31 марта 2003 г.".

Если в какой-либо момент значение слота Автор (в нашем примере — Иванов И. И.) будет удалено, то сработает процедура "если-удалено" и система автоматически отправит Иванову И. И. уведомление о том, что отчет не требуется.

 

4.4.4. Механизм логического вывода в диагностических системах байесовского типа

Диагностические ЭС широко применяются в различных областях человеческой деятельности (медицине, технике, экономике и др.). Как правило, в них используются продукционные модели знаний о предметной области. Однако, если имеется возможность использования в правилах статистических данных о понятиях и связях между ними, весьма целесообразно применить известную теорему Байеса для пересчета апостериорных вероятностей по результатам проверки наличия тех или иных симптомов.

Применительно к техническим диагностическим системам используется следующая схема формализации:

объект имеет множество возможных неисправностей

Sv S2,...Sm,

каждой неисправности приписывается априорная вероятность

т

PiS^PiS,),...,P(Sm); lP(St) = \;

каждая неисправность проявляется через симптомы

С С С

причем каждая неисправность характеризуется "своими" симптомами из "общего" списка;

♦ известны условные вероятности проявления симптомов при каждой неисправности

P(C./S.), і = 1,2,...,™; j = 1,2,...,п.

Тогда можно определить апостериорные вероятности наличия неисправности при данном симптоме I:

pislc)=P{C,IS,)-P(S,) _ PiCtlS^PiS,)

ріс,) xpic/sj-Pis,)

1=1

причем при расчете апостериорной вероятности учитывается, наблюдался при испытании данный симптом или нет.

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

На рис. 4.4.9, а, б, в представлена иллюстрация описанного подхода. На рис. 4.4.9, а показаны исходные априорные вероятности наличия неисправностей. Как правило, задается некоторый уровень вероятности Ртр, превышение которого свидетельствует о необходимости проверки именно тех неисправностей, для которых и наблюдается превышение (в нашем примере — S). Далее проверяется наличие того симптома, для которого вероятность его проявления при г-й неисправности наибольшая (например, симптома С1 на рис. 4.4.9 б).

По результатам проверки пересчитываются все апостериорные вероятности и выявляются те из них, которые превышают заданный уровень. По ним определяется очередной проверяемый симптом (на рис. 4.4.9, в — симптом С2) и т. д. Заметим, что в результате пересчета апостериорная вероятность той или иной неисправности может как увеличиться, так и уменьшиться. После нескольких шагов данный алгоритм приводит к тому, что ЭС некоторые неисправности,

P(S(); P(^/C,) • P(SJC2)

I PVJCJ

■~i 4

P(St)

P(St)

P(52)

 

г p(s2/c2)

if

 

 

5, S2

s. s s.

Рис. 4.4.9. Иллюстрация алгоритма работы диагностической ЭС 386 апостериорные вероятности которых стали очень малыми, отбрасывает (перестает учитывать), а другие предлагает исправить.

Рассмотрим конкретный пример — фрагмент ЭС диагностического типа, предназначенной для поиска неисправности в автомобиле при следующих исходных данных:

автомобиль может иметь четыре неисправности:

5j — неисправна аккумуляторная батарея;

iS2— отсутствует топливо;

S3 — "отсырело" зажигание;

54 — замаслены свечи;

симптомами неисправностей являются:

Cj — фары не горят;

С2 — указатель топлива на нуле;

С3— автомобиль не заводится;

С4 — стартер проворачивается;

С5 — двигатель работает неустойчиво, "чихает";

значения априорных вероятностей:

Р(5,) = 0,4; Р(52) = 0,2; P(S3) = 0,3; P(St) = 0,1.

значения условных вероятностей проявлений симптомов при наличии неисправностей приведены в таблице. Знаком "+" обозначены вероятности P(C./S{), а знаком "—" — вероятности P(Cj/Sj).

Реализация описанного выше алгоритма для последовательности симптомов "фары горят" — "указатель топлива не на нуле" — "стартер проворачивается" — "автомобиль заводится" — "двигатель "чихает" приведет к следующему заключению ЭС: "Просушите зажигание, проверьте свечи". Другая последовательность симптомов "фары не горят" — "автомобиль не заводится" — "стартер не проворачивается" — "указатель топлива не на нуле" — "двигатель не чихает" приведет ЭС к рекомендации "Замените аккумуляторную батарею". Если при проверке симптомов окажется, что "фары горят", "указатель топлива на нуле", "автомобиль не заводится", "стартер проворачивается", "двигатель не чихает", рекомендация ЭС, естественно, такова: "Залейте бензин".

Широкое распространение диагностических ЭС в различных областях деятельности определяется рядом обстоятельств:

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

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

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

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

 

В заключение раздела отметим, что в учебнике рассмотрены лишь методологические основы построения и использования систем искусственного интеллекта. Практика совершенствования информационных технологий представляет все новые направления применения интеллектуальных средств. Так, например, наряду с интеллектуальными пакетами прикладных программ появились так называемые интеллектуальные базы данных [27], в которых используются достижения теории искусственного интеллекта как для организации хранения информации о предметной области, так и для удовлетворения информационных потребностей пользователей. Другим примером может служить разработанная специалистами Института человеческого и машинного познания при университете Западной Флориды (США) технология хранения и представления пользователям информации, получившая название СМар (англ. Concept Map — карта понятий), являющаяся одним из вариантов применения семантических сетей. С помощью этой технологии можно осваивать большие объемы сложно структурированного материала, решая различные задачи (в том числе и задачи обучения специалистов). Еще одним примером является известная концепция "интеллектуального дома (жилища)", призванная рационально использовать средства искусственного интеллекта при всестороннем обеспечении управления бытовыми системами (начиная от регулирования подачи электроэнергии и воды и заканчивая включением/выключением микроволновой печи или телевизора в заданное время). Существует множество подобных примеров, подтверждающих главный вывод: магистральным путем современной автоматизации профессиональной деятельности людей является ее интеллектуализация.