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

Большинство экспертных систем базируется на понятии "формальная продукционная система". Продукционные системы берут свое начало с работ Е.Поста, который в 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 продукцию abW →Wc, получим слово ас.

Каждая система продукций понимается как формальная система с правилами вывода 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. Учитывая неформализованность решаемых задач и эвристический, личностный характер используемых знаний, пользователь (эксперт) должен иметь возможность непосредственного взаимодействия с экспертной системой в виде диалога.

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

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

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

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

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

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