Экспертные системы

В начале 1970-х гг. пришло понимание, что необходимы глубокие знания в соответствующей области и выделение зна­ний из данных, получаемых от эксперта. Появляются эксперт­ные системы (ЭС), или системы, основанные на знаниях.

В основе базы знаний экспертных систем используется сис­тема представления знаний, называемая «системой про­дукций». Системы продукций — это набор правил, исполь­зуемый как база знаний, поэтому его еще называют базой пра­вил.

В продукционных системах, основанных на правилах, зна­ния о решении задачи представляются в виде правил «Если…то…». Этот подход, являясь одним из старейших ме­тодов представления знаний о предметной области в эксперт­ной системе, широко применяется в коммерческих и экспери­ментальных ИСУ.

Общий вид продукционного правила представлен ниже:

<Идентификатор правила> <приоритет правила>

Если <Условие> то <Действие>,

где:

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

приоритет правила — число, показывающее «важность» правила в рассуждениях. Если два и более правил будут иметь истинные условия в левой части, то продолжит рассуждения правило с большим приоритетом;

условие — это левая часть продукционного правила, сово­купность элементарных фактов, связанных знаками конъюнк­ции (И), дизъюнкции (ИЛИ) и отрицания (НЕ).

В качестве простого примера рассмотрим следующее про­дукционное правило, формат записи которого представлен на языке интегрированной среды для разработки интеллектуаль­ных систем управления КAPPA-РС (компании IntelliCorp):

GoodElecSys:

IF car:SparkPlugCondition #= Ok And

car:Timing #= InSynch And

car:Battery #= Charged;

THEN car:ElectricalSystem = Ok; car:Status = Running.

При записи правила сначала указывается его идентифика­тор (имя) «GodElecSys:», а затем после двоеточия — левая и правая части, соответственно <Условие> и <Действие>. Имеем следующий словарь информационных объектов (фак­тов): car:SparkPlugCondiion — условия искрообразования в автомобиле, car:Timing — регулировка момента зажигания автомобиля, InSynch — синхронизированно, car:Battery — состояние аккумулятора, Charged — заряжено, car:ElectricalSystem — состояние электрической системы ав­томобиля, car:Status — статус автомобиля, Running — готов­ность к запуску, ОК — хорошее, And — операция конъюнк­ции.

Логический смысл данного правила следующий:

Если <условия искрообразования в автомобиле хорошие

И регулировка момента зажигания автомобиля

синхронизирована

И аккумулятор заряжен>

То <состояние электрической системы автомобиля хорошее,

автомобиль готов к запуску>

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

На рисунке 32 изображены основные элементы механизма поиска решений системы КAPPA-РС.

Интерпретатор — программа, имитирующая рассуждения эксперта, решающего задачу, и работающая в одном из двух режимов — в режиме рассуждений в прямом направлении (прямой вывод) или в режиме рассуждений в обратном на­правлении (обратный вывод). Рассуждения в прямом направ­лении — это рассуждения, идущие в направлении «от фактов» в левых частях правил базы знаний к «действиям», указанным в правых частях правил из базы знаний.

База фактов хранит иерархию информационных объектов (пирамиду знаний) в виде «объект: слот».

База знаний хранит иерархию правил обработки фактов.

План решения задачи (Agenda) — очередь пар «объект: слот», которые должны быть обработаны машиной прямого вывода. Слоты, чьи значения изменены в результате примене­ния правила, автоматически добавляются интерпретатором в Agenda.

Список правил (Rule List) — это список всех правил из те­кущего подмножества правил, удовлетворяющего следующе­му условию: все элементарные факты, а значит, и составной факт в левой части правила получили значение ИСТИНА. Правило, размещенное в списке правил, считается возбужден­ным, т. е. «готовым к применению». Прежде чем проверять истинность всех элементарных фактов из левой части правила, интерпретатор проверяет его релевантность («уместность»). Для этого пара «объект: слот» из Agenda сверяется со всеми элементарными фактами из левых частей всех правил базы знаний. Если совпадений нет, правило исключается из рас­смотрения. Если есть хотя бы одно совпадение, то правило продолжает рассматриваться, т. е. продолжается оценка ис­тинности других фактов в его левой части.

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

Если в списке будет несколько правил, то такая ситуация называется «конфликтом правил», они «конфликтуют» за то, чтобы продолжить рассуждения. Для того чтобы разрешить конфликт, интерпретатору нужна дополнительная информа­ция. Такая информация называется стратегией разрешения конфликта.

Система КАPPA-PC, как и большинство аналогичных сис­тем, поддерживает следующие классические стратегии разре­шения конфликтов:

¾ стратегия Выборочная оценка (SELECTIVE Evaluation) — в процессе прямого вывода заново возбужденное правило до­бавляется в список правил в соответствии с его приорите­том. Одно правило из списка получает значение «истина», осталь­ные из конфликтующих правил из списка правил уда­ляются. Список правил очищается перед тем, как новая пара «объект: слот» из Agenda начнет рассматриваться;

¾ стратегия Поиск в глубину (DEPTHFIRST Evaluation) — отличается от выборочной стратегии только тем, что не очи­щает список правил после выбора одного из конфликтующих правил и его использования в рассуждениях. Только что акти­вированное правило (т. е. правило из базы знаний, у которого подтвердилась истинность составного факта в левой части) классифицируется в соответствии с его приоритетом и добав­ляется в начало списка правил. Правило из начала списка применяется интерпретатором в рассуждениях, что добавляет новую пару «объект: слот» в начало Agenda (пара добавляется, если значение слота какого-либо объекта из базы фактов из­менено в результате действия, указанного в правой части пра­вила, использованного в рассуждениях). Если есть пары «объ­ект: слот» в Agenda и список правил не пустой, то приоритет отдается оценке следующей пары «объект: слот» в Agenda.

¾ стратегия Поиск в ширину (BREADTHFIRST Evalua­tion) — в течение прямого вывода в режиме «в ширину» вновь возбужденное правило размещается в соответствии с приори­тетом, а потом добавляется в конец списка правил. Затем пер­вое правило из списка применяется, и оно может сгенериро­вать новую пару «объект: слот» в Agenda. Если есть пары «объект: слот» в Agenda и правила в списке правил, приоритет отдается проверке следующего правила из списка.

Рассмотрим пример, иллюстрирующий работу выше опи­санного механизма поиска решений (см. рис. 32, с. 124) для выборочной стратегии разрешения конфликтов и базы знаний, состоящей из нескольких правил. Имеем следующий словарь информационных объектов базы знаний: SparkPlugCondition — условия искрообразования, Timing — регулировка момента зажигания, OutOfSynch — разсинхронизация, InSynch — син­хронизация, IgnitionKey — ключ зажигания, Charged — заря­жено, GasSystem — топливная система, Status — состояние, LightSwitch — включатель фар, LightsAppearance — наружный свет (свет фар), Bright — яркий, Dim — тусклый, EngineTurno­ver — обороты двигателя, Brisk — хорошие, Sluggish — мед­ленные, Battery — аккумулятор.

База знаний рассматриваемого примера следующая:

BadElecSys:

IF car:SparkPlugCondition #= Bad Or

car:Timing #= OutOfSynch Or

car:Battery #= Low;

THEN car:ElectricalSystem = Bad;

GoodElecSys:

IF car:SparkPlugCondition #= Ok And

car:Timing #= InSynch And

car:Battery #= Charged;

THEN car:ElectricalSystem = Ok;

BadEngineSys:

IF car:IgnitionKey #= Off Or

car:GasSystem #= Bad Or

car:ElectricalSystem #= Bad;

THEN car:Status = Stopped;

GoodEngSys:

IF car:IgnitionKey #= On And

car:GasSystem #= Ok And

car:ElectricalSystem #= Ok;

THEN car:Status = Running;

BrighLights:

IF car:LightSwitch #= On And

car:Battery #= Charged;

THEN car:LightsAppearance = Bright;

DimLights:

IF car:LightSwitch #= On And

car:Battery #= Low;

THEN car:LightsAppearance = Dim;

BriskTurnover:

IF car:IgnitionKey #= On And

car:ElectricalSystem #= Low;

THEN car:EngineTurnover = Brisk;

SluggishTurnover:

IF car:IgnitionKey #= On And

car:ElectricalSystem #= Bad;

THEN car:EngineTurnover = Sluggish;

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

Текущая база фактов:

car:Battery = Charged; car:ElectricalSystem=NULL

car:EngineTurnover=NULL; car:IgnitionKey=On

car:LightsAppearance=NULL; car:LightSwitch=On; car:Gas­System #= Ok;

car:Status=NULL; car:SparkPlugCondition#=Ok; car:Timing #= InSynch.

Assert(сar, Battery); — команда начала поиска решения.

При выполнении этой команды сar:Battery помещается в Agenda и проверяются левые части правил базы знаний.

Проверяется на соответствие с левыми частями правил пара Car:Battery, и добавляются в список правил те из них, у которых совпадение установлено по одному из элементарных фактов:

Проверяется правило BadElecSys. Результат проверки FALSE. Правило удаляется из списка правил.

Проверяется правило GoodElecSys. Результат проверки TRUE. Правило применяется, т. е. выполняются действия из его правой части. Это вносит изменения в базу фактов — слот в паре Car:ElectricalSystem принимает значение Oк. Пара Car:ElectricalSystem добавляется в Agenda. Список правил очищается.

Оцениваются и добавляются в список правил те правила, у которых один из элементарных фактов включает пару Car:ElectricalSystem.

Проверяется правило BadEngineSys. Результат FALSE. Правило удаляется из списка правил.

Поверяется правило GoodEngSys, Результат TRUE. Пра­вило применяется (выполняются действия из его правой части), Car:Status принимает значение Running. Вывод закон­чен.

В результате рассмотренного процесса ИСУ вырабатывает следующую информацию:

Car:ElectricalStatus = Oк;

Car:Status = Running.

«Проблем в электрической системе автомобиля нет,

разрешен запуск автомобиля».

Разработка ЭС имеет существенные отличия от разработки обычного программного продукта. При разработке ЭС, как правило, используется концепция «быстрого прототипа». Суть этой концепции состоит в том, что разработчики не пытаются сразу построить конечный продукт. На начальном этапе они создают прототип (прототипы) ЭС, который должен проде­монстрировать пригодность методов инженерии знаний для данного приложения (или для решения данной задачи). В слу­чае успеха эксперт с помощью инженера по знаниям расширя­ет знания прототипа о проблемной области. При неудаче мо­жет потребоваться разработка нового прототипа или разработ­чики могут прийти к выводу о непригодности методов ЭС для данного приложения. По мере увеличения знаний прототип может достигнуть такого состояния, когда он успешно решает все задачи данного приложения. Преобразование прототипа ЭС в конечный продукт обычно приводит к перепрограммиро­ванию ЭС на языках низкого уровня, обеспечивающих как увеличение быстродействия ЭС, так и уменьшение требуемой памяти. Трудоемкость и время создания ЭС в значительной степени зависят от типа используемого инструментария. В ходе работ по созданию ЭС сложилась определенная техноло­гия их разработки, включающая шесть следующих этапов (рис. 33): идентификацию, концептуализацию, формализацию, выполнение, тестирование, опытную эксплуатацию.

Рис. 33. Технология разработки ЭС

На этапе идентификации определяются задачи, которые подлежат решению, выявляются цели разработки, определя­ются эксперты и типы пользователей.

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

На этапе формализации определяются способы представ­ления всех видов знаний, формализуются основные понятия, определяются способы интерпретации знаний, моделируется работа системы, оценивается адекватность целям системы зафиксированных понятий, методов решений, средств пред­ставления и манипулирования знаниями.

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