Формальные основы экспертных систем

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

Система продукций Поста задается своим алфавитом С= {с,...,с}

и системой базисных продукций

x_iW→Wy_i (i =1,...,1),

где x_i, y_i - слова в алфавите С.

Пусть некоторое слово Y начинается словом x_i. Применить к Y продукцию x_iW →Wy_i - это значит вычеркнуть из Y начальный отрезок x_i и затем к оставшемуся слову приписать слово y_i. Например, применив к слову aba продукцию ab W → W c, получим слово ас.

Каждая система продукций понимается как формальная система с правилами вывода p_i (i = 1,..., 1), где p_i (F,Y) считается истинным (применимым), если слово Y получается из F при помощи продукции x_iW → Wy_i.

Наложив на набор упорядоченных продукций неявную управляющую структуру, перейдем к понятию нормального алгоритма Маркова [2]. В алгоритме Маркова упорядоченные продукции (формулы подстановок) применяются к некоторому заданному слову.

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

Психологические исследования процессов принятия решений человеком [13] показали, что, рассуждая, человек использует правила, аналогичные продукциям, т.е. правила вида "условие → действие". А.Ньюэлл [12] предложил использовать продукционные системы для моделирования на ЭВМ процесса принятия решений. Формализуя предложения Ньюэлла, определим продукционную систему (PS) следующим образом:

PS = <R, В, I>,

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

В - база знаний, содержащая множество продукций (правил вида: "условие → действие");

I - интерпретатор (решатель), реализующий процесс вывода, который в цикле выполняет следующие действия: определяет множество означиваний, т.е. множество пар: {правило (р_i), набор текущих данных (a_j), на котором это правило удовлетворяется}; выполняет определенные означивания, производя изменения в рабочей памяти.

Интерпретатор формально может быть представлен четверкой:

I = (V, S, K, W),

где V - процесс выбора из В и из R подмножества активных продукций B_v и подмножества активных данных R_v соответственно, которые будут использованы в очередном цикле работы интерпретатора. Механизм выбора может быть тривиальным (на каждом цикле выбираются все правила и все данные) или более сложным [4] для того, чтобы устранить из рассмотрения те правила, условия которых заведомо не удовлетворяются данными рабочей памяти или малополезны. В усложненных системах механизм выбора может использовать иерархию правил, метаправила или сложные схемы управления, подобные сетям Петри [1];

S - процесс сопоставления, определяющий множество означиваний, т.е. множество пар: правило (р_i) - данные (d_i), где p_i P_v, {d_i} R_v, причем каждое p_i применимо к элементам множества {d_i} (будем также говорить, что "p_i удовлетворяется на элементах множества {d_i}"). Операция сопоставления может требовать много времени, так как в общем случае влечет за собой означивание многих переменных;

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

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

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

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

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

3. Учитывая неформализованность решаемых задач и эвристический, личностный характер используемых знаний, пользователь (эксперт) должен иметь возможность непосредственного взаимодействия с экспертной системой в виде диалога.

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

Третий принцип предъявляет к системе следующие требования:

• способность вести диалог о решаемой задаче на языке, удобном пользователю (эксперту), и, в частности, приобретать в ходе диалога новые знания;

• способность при решении задачи следовать линии рассуждения, понятной пользователю (эксперту);

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

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

7. Архитектура статических и динамических экспертных систем. 8. Составные части экспертной системы: база знаний, механизм вывода, механизмы приобретения и объяснения знаний, интеллектуальный интерфейс. (Попов)

Типичная статическая ЭС состоит из следующих основных компонентов (рис. 1.1):

• решателя (интерпретатора);

• рабочей памяти (РП), называемой также базой данных (БД);

• базы знаний (БЗ);

• компонентов приобретения знаний;

• объяснительного компонента;

• диалогового компонента.

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

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

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

Компонент приобретения знаний автоматизирует процесс наполнения ЭС знаниями, осуществляемый пользователем-экспертом.

Объяснительный компонент объясняет, как система получила решение задачи (или почему она не получила решение) и какие знания она при этом использовала, что облегчает эксперту тестирование системы и повышает доверие пользователя к полученному результату.

Рис. 1.1. Структура статической ЭС

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

В разработке ЭС участвуют представители следующих специальностей:

- эксперт в проблемной области, задачи которой будет решать ЭС;

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

- программист по разработке инструментальных средств (ИС), предназначенных для ускорения разработки ЭС.

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

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

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

Программист разрабатывает ИС (если ИС разрабатывается заново), содержащее в пределе все основные компоненты ЭС, и осуществляет его сопряжение с той средой, в которой оно будет использовано.

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

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

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

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

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

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

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

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

Рис. 1.2. Архитектура статических и динамических ЭС (компоненты, подвергающиеся изменениям, заштрихованы)

Рис. 1.3. Структура современных ИС для ЭС

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

Дата добавления: 2014-12-27