Rapid advances in Internet technologies have opened new opportunities for enhancing traditional expert systems to distributed expert systems. The earlier success of rule-based expert systems employing more efficient inference engines pushed forward investigations of distributed production systems where multiple rule-based systems solve a common problem together. The basic idea is that a collection of production systems could be a model of group decision making, since single production system can represent logics of an individual human expert. Although researchers have offered a number of particular algorithms for cooperation between production systems, this research direction is still at the stage of formalization. Mostly the offered algorithms exploit such global ideas as data sharing [1], knowledge sharing, learning and quoting from external sources.

Further we use the following restrictive assumptions about monotonic production systems [2]:
F₀ is an enumerated set of facts presented in working memory;
D  is a set of potential goals;
P  is a set of production rules like IF f₁ ... f_n THEN f;
E  is an algorithm which task is to return just one proper rule
   on any step of inference.

Assumption. Rule interpreter is goal-driven; for a given potential goal d it either generates well-grounded inference (in the form of a chain of rules) supporting d or returns reject message informing it is impossible to draw the conclusion d. To search for an appropriate rule, the rule interpreter every time turns to the algorithm E.

Definition. The h-rule is any production rule like IF ... THEN h.

Definition. Given a set of production rules P and the goal d, we say that P_d is a well-grounded inference for d if P_d is minimal set of production rules which satisfy the following conditions:
(1) P_d contains just one d-rule;
(2) if P_d contains the rule IF f₁ ... f₁ THEN f, then for every fact f_i either f_i ∈ F₀ or P_d contains just one f_i-rule.

Notice that the last definition is exhaustive: a given set of productions Q can be matching with the above conditions.

Now let us consider the algorithm E. If the fact h is selected as a hypothesis then rule interpreter turns to the algorithm E which returns either h-rule or reject message. If E(h) is reject message, then rule interpreter starts with another hypothesis. If E(h) is not reject message, then rule interpreter uses E(h) for construction of inference.

In its operation, the algorithm E provides for that the same rules are not selected once again. At the very beginning all the rules are marked as executable; once selected rules are marked as non-executable.

In general, the algorithm E consists of two steps:

Not to concentrate on minor aspects, hereinafter we will assume a certain level of similarity of the cooperating production systems, namely (1) rules of the production systems should be generated on the basis of the same syntax, (2) despite facts of the production systems may differ, the facts identical in meaning should have the same name, (3) the production systems should have at least one common goal.

Let us consider the two production systems: < F₀, P, D, E > and < F₀, Q, D₁, E₁ >. Suppose that for the same problem situation F₀ and for the same hypothesis d the system S returned reject message and the system S₁ generated a well-grounded inference Q_d. Backing to analogy with human collective decision making, imagine that the system S nevertheless tried to generate well-grounded inference P'_d referring to the respected opinion of the system S₁. In this case we say that the production system S "quoted" the system S₁.

Formally, the task of quoting for the production system S is
► to provide the well-grounded inference P_d for the goal d
► taking advantage of some of the rules of the another system S₁,
► with the post factum estimation of originality of the received results.

To solve the task of quoting we offer to upgrade the algorithm E of the production system S to the algorithm E⁺, which explicitly uses the borrowed well-grounded inference:

Note, in the case Q_d = ∅ the algorithm E⁺ turns into E. If Q_d ≠ ∅ the production system < F₀, P, D, E⁺ > guarantees the well-grounded inference P' for the goal d, using the rules P ∪ Q_d, where P'_d contains at least one rule from Q_d \ P.

The simplest formula for estimation of originality of the received result: k = ||P'_d \ Q_d|| / ||P'_d||. In the worst case (full borrowing of knowledge): P'_d = Q_d and k = 0. At best, but unattainable, case (no borrowing of knowledge): k = 1. The more sophisticated estimations can be calculated by using the measure of similarity of set Q_d and set P'_d [4].

We proposed a quoting-based algorithm which allows a production system to enhance its capabilities with the help of borrowing from another production system. In general case, the proposed algorithm does not guarantee the maximum originality for the generated inference P'_d. At the same time, realization of the algorithm requires minor changes the traditional backward chaining engine.

Gennady Ginkul
ZAO Sberbank-Technologii,
Moscow, Russia
Email: ghincul@hotmail.com

Sergey Soloviev
Lomonosov Moscow State University,
Moscow, Russia
Email: soloviev@glossary.ru

Развитие глобальной сети Интернет актуализировало большое количество исследований, посвященных различным аспектам взаимодействия между распределенными программными системами вообще и экспертными системами в частности. Для экспертных систем отличительными видами взаимодействий являются: выработка коллективного мнения [1], обмен знаниями, обучение, а также цитирование из внешних источников знаний. Формализация перечисленных процессов еще не закончена, идет процесс накопления частных решений. Рассмотрим задачу цитирования для хорошо изученных монотонных продукционных систем [2].

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

Будем рассматривать продукционные системы с обратным выводом, различающиеся наборами правил, списками окончательных диагнозов и алгоритмами разрешения конфликтов. Соответственно каждая такая продукционная система определяется тройкой < P, D, E >, где
P – множество продукционных правил (продукций);
D – упорядоченный список потенциально возможных заключительных диагнозов;
E – алгоритм разрешения конфликтов.
Дополнительно будем полагать, что в рабочую память продукционной системы заранее загружено множество фактов F₀, описывающих проблемную ситуацию, для которой необходимо найти диагноз.

Продукционные правила множества P имеют вид IF f₁ & ... & f_n THEN f. Правила, в THEN-частях которых располагается факт f, называются f-правилами.

Упорядоченный список диагнозов D = (d₁, d₂, ..., d_m) используется как очередь гипотез, подлежащих последовательной проверке. Если очередная гипотеза d = d_i подтверждается, то продукционная система формирует так называемое мотивированное заключение и завершает свою работу. Если же гипотеза d_i не подтверждается, то проверяется гипотеза d_i+1 и т.д. Если ни одна гипотеза из списка D не подтверждается, то продукционная система вырабатывает сообщение ОТКАЗ.

Алгоритм E позволяет из заданного множества продукционных правил выбрать одно правило. Обычно алгоритм E реализует некоторую универсальную стратегию разрешения конфликтов [4].

На каждом такте своей работы алгоритм обратного вывода анализирует заданную гипотезу h, формирует множество h-правил, из которого при помощи алгоритма E выбирает для продолжения некоторое правило IF h₁ & ... & h_n THEN h. Гипотеза h считается подтвердившейся, если для каждого факта h_j из IF-части выбранного правила выполняется одно из двух:
либо h_j содержится в рабочей памяти продукционной системы;
либо гипотеза h_j подтверждается тем же самым алгоритмом обратного вывода.
Подтвердившиеся гипотезы заносятся в рабочую память продукционной системы, а подтвердившие их правила рассматриваются как материал для построения мотивированного заключения. Однажды выбранные продукционные правила в дальнейшей работе продукционной системы участия не принимают, они игнорируются алгоритмом разрешения конфликтов E. Если алгоритм E не в состоянии выбрать продукцию для продолжения, то он вырабатывает сообщение ОТКАЗ, и гипотеза h считается опровергнутой.

Для наших целей важно зафиксировать, что алгоритм разрешения конфликтов для заданной гипотезы h вырабатывает либо некоторое продукционное правило, либо сообщение ОТКАЗ: E(h) есть либо h-правило, либо ОТКАЗ.

Под мотивированным заключением диагноза d понимается минимальное по количеству элементов множество продукций P_d ⊆ P, удовлетворяющее следующим свойствам:
1. P_d содержит ровно одно d-правило;
2. если P_d содержит правило IF h₁ & ... & hP_n THEN h,
 то для каждого факта h_i из IF-части этого правила справедливо одно из двух:
   либо h_i ∈ F₀;
   либо P_d содержит ровно одно h_i-правило.

Приведенное определение мотивированного заключения является самодостаточным: любое заданное множество продукций Q можно проверить на соответствие определению, а при положительном ответе можно выявить факт, играющий роль заключительного диагноза d, а также множество невыводимых фактов T(Q). По определению множество T(Q) составляют факты, которые встречаются в IF-частях правил из Q и не встречаются в THEN-частях: если Q ⊆ P, то T(Q) ⊆ F₀.

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

Схематично действие продукционной системы S = < P, D, E > по анализу заданной проблемной ситуации F₀ сводится
       либо к виду S : F₀ → P_d,
       либо к виду S : F₀ → ОТКАЗ.

Рассмотрим две различные, но согласованные продукционные системы
S = < P, D, E >и S₁ = < Q, D₁, E₁ >. Под согласованностью будем понимать выполнение трех условий. Во-первых, одинаковые по смыслу элементы, описывающие проблемные области систем S и S₁, в обеих системах представляются одним и тем же фактом. Во-вторых, в обеих системах продукционные правила построены с использованием одинакового синтаксиса. В-третьих, D ∩ D₁ ≠ ∅. Первые два условия позволяют переносить продукции из системы в систему без технических затруднений, а третье условие позволяет использовать обе системы в консилиумах.

Предположим, что в проблемной ситуации F₀ система S₁ способна построить мотивированное заключение Q_d некоторого диагноза d, а система S сообщает о невозможности построить заключение P_d, хотя d ∈ D. То есть:
       S : F₀ → ОТКАЗ,
       S₁ : F₀ → Q_d, для некоторого d из D ∩ D₁.
На месте системы S настойчивый ученый способен воспользоваться (в порядке цитирования) чужими знаниями и все-таки построить некоторый – гибридный – вывод диагноза d. Между тем современные продукционные системы такими способностями не обладают, а потому разработка и включение в состав продукционных систем алгоритма цитирования представляет определенный научный интерес. Строго говоря, для системы S задача цитирования состоит
в построении мотивированного заключения диагноза d
посредством привлечения некоторых продукций из Q_d
с последующей оценкой оригинальности полученного заключения.

Предлагаемый метод решения задачи цитирования для описанного класса продукционных систем состоит в модификации алгоритма разрешения конфликтов. Фактически предлагается в продукционной системе S = < P, D, E > алгоритм E заменить на E⁺ и перейти к продукционной системе S⁺ = < P, D⁺, E⁺ >, где список D⁺ получается из D перемещением гипотезы d на первое место. Алгоритм E⁺ в качестве дополнительного аргумента использует мотивированное заключение Q_d и реализует следующее вычисление:

E+(h,Qd) :	Если	E(h) = ОТКАЗ,
	но	Qd \ P содержит h-правило q,
	то	результатом является правило q,
	иначе	результатом является E(h).

При Q_d = ∅ алгоритм E⁺ вырождается в E, а при Q_d ≠ ∅ продукционная система S⁺ гарантированно строит мотивированное заключение P'_d диагноза d: S⁺ : (F₀, Q_d) → P'_d, причем P'_d содержит хотя бы одно правило из Q_d \ P.

Простейшая оценка оригинальности полученного заключения определяется величиной
k = k₁ / k₂, где k₁ – количество элементов множества P'_d \ Q_d, а k₂ – количество элементов в P'_d. В худшем случае, соответствующем 100% заимствованию знаний, P'_d = Q_d и k = 0. В наилучшем, но недостижимом случае, когда в заключении P'd не используются сторонние правила, k = 1. Более тонкие оценки оригинальности вычисляются как меры сходства [5] множеств T(Q_d) и T(P'_d).

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

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

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

Рассматриваемая работа относится ко второму направлению исследований – созданию распределенных ЭС. Как известно, экспертные системы призваны принимать решения в плохо формализуемых проблемных областях. В таких областях не существует формальных алгоритмов для решения задач, но существуют специалисты-эксперты, которые умеют в основном правильно действовать в складывающихся проблемных ситуациях. Главной составляющей экспертной системы является база знаний, в которой содержатся знания о проблемной области. Эти знания должны быть получены от эксперта и представлены в базе знаний одним из традиционных способов представления знаний: в виде системы продукций, семантической сети, сети фреймов или логики предикатов 1-го порядка.

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

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

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

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

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

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

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

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