Экспертная система

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

1. Введение.

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

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

В экспертных системах для  решения задач на уровне эксперта-человека широко

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

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

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

Рис. 1. Основные принципы функционирования экспертной системы.  

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

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

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

Рис. 2. Связь между  предметной областью и областью знаний.  

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

2. Преимущества  экспертных систем.

Как описано ниже, экспертные системы обладают многими  привлекательными особенностями.

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

· Уменьшенные издержки. Стоимость предоставления экспертных знаний в расчете на отдельного пользователя существенно снижается.

· Уменьшенная опасность. Экспертные системы могут использоваться в таких вариантах среды, которые могут оказаться опасными для человека.

· Постоянство. Экспертные знания никуда не исчезают. В отличие от экспертов-людей, которые могут уйти на пенсию, уволиться с работы или умереть, знания экспертной системы сохраняются в течение неопределенно долгого времени.

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

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

· Объяснение. Экспертная система способна подробно объяснить свои рассуждения, которые привели к определенному заключению. А человек может оказаться слишком усталым, не склонным к объяснениям или неспособным делать это постоянно. Возможность получить объяснение способствует повышению доверия к тому, что было принято правильное решение.

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

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

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

· Возможность применения в качестве интеллектуальной базы данных.

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

3. Общие понятия  экспертных систем.

Знания могут  быть представлены в экспертной системе  многими способами. Одним из широко применяемых методов представления  знаний являются правила в форме IF-THEN, как показано ниже.

IF горит  красный свет THEN стоять.

Если обнаруживается факт, что на светофоре горит красный  свет, то этот факт согласуется с шаблоном "на светофоре горит красный свет". Условие правила удовлетворяется и выполняется обусловленное в нем действие "стоять".

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

Рис. 3. Процесс  разработки экспертной системы

Основные этапы  разработки экспертной системы показаны на рис. 3. Вначале инженер по знаниям  устанавливает диалог с экспертом-человеком, чтобы выявить знания эксперта. Этот этап аналогичен этапу работы, выполняемому системным проектировщиком при обычном программировании в ходе обсуждения требований к системе с клиентом, для которого создается программа. Затем инженер по знаниям представляет знания в явном виде для внесения в базу знаний. После этого эксперт проводит оценку экспертной системы и передает критические замечания инженеру по знаниям. Такой процесс повторяется снова и снова, до тех пор, пока эксперт не оценит результаты работы системы как удовлетворительные.

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

4. Элементы экспертной  системы.

Элементы типичной экспертной системы показаны на рис. 4. В cистеме, основанной на правилах, знания в проблемной области, необходимые для решения задач, закодированы в форме правил и содержатся в базе знаний. Безусловно, для представления знаний наиболее широко применяются правила.

Рис. 4. Структура  экспертной системы, основанной на правилах.

Экспертная система состоит  из описанных ниже компонентов.

Пользовательский  интерфейс. Механизм, с помощью которого происходит общение пользователя и экспертной системы.

• Средство объяснения. Компонент, позволяющий объяснить пользователю ход рассуждений системы.

• Рабочая память. Глобальная база фактов, используемых в правилах.

• Машина логического вывода. Программный компонент, который обеспечивает формирование логического вывода (принимая решение о том, каким правилам удовлетворяют факты или объекты), располагает выполняемыеправила по приоритетам и выполняет правило с наивысшим приоритетом.

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

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

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

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

горит красный свет —> стоять

горит зеленый свет —> двигаться

Продукционные правила  могут быть выражены в эквивалентном  формате псевдокода IF-THEN следующим образом:

Правило: red__light

IF горит красный свет THEN стоять 

Правило: green_light

IF горит зеленый свет THEN двигаться 

Каждое правило  обозначается именем. Вслед за именем находится часть IF правила. Участок правила между частями IF и THEN правила упоминается под разными именами, такими как антецедент, условная часть, часть шаблона или левая часть (left-hand-side — LHS). Такое отдельно взятое условие, как

“горит красный свет” называется условным элементом, или шаблоном.

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

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

Обратный логический вывод предусматривает формирование рассуждений в обратном направлении - от гипотезы (потенциального заключения, которое должно быть доказано) к фактам, которые подтверждают гипотезу. Например, если вы не выглядываете наружу, но кто-то вошел в дом с влажными ботинками и зонтиком, то можно принять гипотезу, что идет дождь. Чтобы подтвердить эту гипотезу, достаточно спросить данного человека, идет ли дождь. В случае положительного ответа будет доказано, что гипотеза истинна, поэтому она становится фактом. Как уже было сказано выше, гипотеза может рассматриваться как факт, истинность которого вызывает сомнение и должна быть установлена. В таком случае гипотеза может интерпретироваться как цель, которая должна бытьдоказана.

В зависимости от проекта  экспертной системы в машине логического  вывода осуществляется либо прямой, либо обратный логический вывод, либо обе эти формы логического вывода. Например, язык CLIPS спроектирован в расчете на применение прямого логического вывода, в языке PROLOG осуществляется обратный логический вывод, а в версии CLIPS, называемой Eclipse, разработанной Полом Хэйли (Paul Haley), осуществляется и прямой, и обратный логический выводы. Выбор машины логического вывода зависит от типа задачи. Диагностические задачи лучше всего решать с помощью обратного логического вывода, в то время как задачи прогнозирования, текущего контроля и управления проще всего поддаются решению с помощью прямого логического вывода.

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

Если в рабочей  памяти имеется факт "горит зеленый  свет", машина логического вывода обнаруживает, что этот факт удовлетворяет условной части правила green_light и помещает это правило в рабочий список правил. А если правило имеет несколько шаблонов, то все эти шаблоны должны быть удовлетворены одновременно для того, чтобы правило можно было поместить в рабочий список правил. В качестве условия удовлетворения некоторых шаблонов можно даже указать отсутствие определенных фактов в рабочей памяти.

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

Вслед за частью THEN правила находится список действий, которые должны быть выполнены после запуска правила. Эта часть правила называется консеквентом, или правой частью (Right-Hand Side — RHS). Если происходит запуск правила red_light, выполняется его действие “стоять”. Аналогичным образом после запуска правила green_lightего действием становится “двигаться”. В состав конкретных действий обычно входит добавление или удаление фактов из рабочей памяти либо вывод результатов. Формат описания этих действий зависит от синтаксиса языка экспертной системы. Например, в языке CLIPS действие по добавлению в рабочую память нового факта, называемого “stop” (стоять), принимает вид (assert stop).

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

WHILE работа не закончена

Разрешение  конфликтов. Если имеются активизированные

правила, то выбрать  правило с наивысшим приоритетом;

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

Действие. Последовательно осуществить действия,

указанные в правой части выбранного активизированного

правила. В данном цикле проявляется непосредственное

влияние тех действий, которые изменяют содержимое

рабочей памяти. Удалить из рабочего список правил

только что  запущенное правило.

Согласование. Обновить рабочий список правил путем

проверки того, выполняется ли левая часть каких-либо

правил. В случае положительного ответа активизировать

соответствующие правила. Удалить активизированные

правила, если левая  часть соответствующих правил больше

не выполняется.

Проверка  условий останова. Если осуществлено

действие halt или дана команда break, то работа закончена.

END-WHILE

Принять новую команду  пользователя. 

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

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

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

После завершения выполнения всех правил управление возвращается к интерпретатору команд верхнего уровня, чтобы пользователь мог выдать командному интерпретатору экспертной системы дополнительные инструкции. Работа в режиме верхнего уровня соответствует применяемому по умолчанию режиму, в котором пользователь взаимодействует с экспертной системой, и обозначается как задача "Accept a new user command" (Принять новую команду пользователя). Прием новых команд происходит именно на верхнем уровне.

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

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

5. Продукционные  системы.

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

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

Широкое применение систем, основанных на правилах, обусловлено  описанными ниже причинами.

• Модульная организация. Благодаря такой организации упрощается представление знаний и расширение экспертной системы по методу инкрементной разработки.

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

• Наличие аналогии с познавательным процессом человека. Согласно результатам, полученным Ньюэллом иСаймоном, правила, по-видимому, представляют собой естественный способ моделирования процесса решения задач человеком. А при осуществлении попытки выявить знания, которыми обладают эксперты, проще объяснить экспертам структуру представления знаний, поскольку применяется простое представление правил IF-THEN.

Продукционные системы Поста

Продукционные системы  были впервые использованы в символической  логике Постом (Post), поэтому имя этого ученого вошло в название указанных систем. Пост доказал такой важный и неожиданный результат, что любая система математики или логики может быть оформлена в виде системы продукционных правил определенного типа. Этот результат показал огромные возможности применения продукционных правил для представления важных классов знаний, а это означает, что продукционные правила не сводятся к нескольким ограниченным типам. Кроме того, продукционные правила, обозначаемые термином правила подстановки, используются также в лингвистике как способ определения грамматики языка. Компьютерные языки обычно определяются с помощью формы продукционных правил, известной как нормальная форма Бэкуса-Наура (Backus-Naur Form — BNF. Основная идея Поста заключалась в том, что любая математическая или логическая система представляет собой набор правил, который указывает, как преобразовать одну строку символов в другой последовательный набор символов. Это означает, что продукционное правило после получения входной строки (антецедента) способно выработать новую строку (консеквент). Такая идея является также действительной по отношению к программам и экспертным системам, в которых начальная строка символов представляет собой входные данные, а выходная строка становитсярезультатом определенных преобразований, которым были подвергнуты входные данные.

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

антецедент —> консеквент

у пациента имеется  высокая температура —> пациент должен принять аспирин

В этом правиле стрелка  означает, что одна строка должна быть преобразована в другую. Указанное правило можно интерпретировать с помощью более знакомой системы обозначений IF-THEN следующим образом:

IF у пациента имеется высокая температура THEN пациент должен принять аспирин.

Rete-алгоритм

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

Решением этой проблемы является rete-алгоритм, разработанный Чарльзом Л. Форги (Charles L. Forgy) в университете Карнеги-Меллона в 1979 году в рамках диссертации по командному интерпретатору экспертной системы OPS (Official Production System — стандартная продукционная система) на получение степени доктора философии. Термин rete-алгоритм происходит от латинского слова rete (по-английски читается "рити", а по-русски — "рете"), которое означает сеть. Rete-алгоритм функционирует как сеть, предназначенная для хранения большого объема информации и обеспечивающая значительное сокращение времени отклика и повышение быстродействия при запуске правил по сравнению с большими группами правил IF-THEN, которые должны проверяться один за другим в обычной системе, основанной на правилах. Rete-алгоритм основан на использовании динамической структуры данных, подобной стандартному дереву В+, которая автоматически реорганизуется в целях оптимизации поиска.

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

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

• Структурное подобие. Один и тот же шаблон часто обнаруживается в левой части больше чем одного правила.

Если в системе заданы сотни или тысячи правил, то подход к организации работы, в котором компьютер последовательно проверяет вероятность того, должен ли быть выполнен запуск каждого правила, становится очень неэффективным. Благодаря разработке rete-алгоритма появилась практическая возможность создания инструментальных средств экспертных систем даже на тех медленных компьютерах, которые применялись в 1970-х годах. В наши дни rete-алгоритм продолжает оставаться важным средством повышения быстродействия в тех случаях,когда экспертная система содержит много правил.

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

На рис. 5 показаны технологиях, которые образуют фундамент современных экспертных систем, основанных на правилах. 

Рис. 5. Технологии, образующие фундамент современных  экспертных систем, основанных на правилах.