дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
 Скачать 3.73 Mb.
|
обозначаемые термином правила подстановки, используются также в лингвистике как способ определения грамматики языка. Компьютерные языки обычно определяются с помощью формы продукционных правил, известной как нормальная форма Бэкуса — Наура (BackusNaur Form — BNF); в качестве примера такого определения можно ознакомиться. Продукционные системы с грамматикой языка приведенной в приложении Г. Основная идея Поста заключалась в том, что любая математическая или логическая система представляет собой набор правил, который указывает, как преобразовать одну строку символов в другой последовательный набор символов. Это означает, что продукционное правило после получения входной строки (антецедента) способно выработать новую строку (консеквент). Такая идея является также действительной по отношению к программами экспертным системам, в которых начальная строка символов представляет собой входные данные, а выходная строка становится результатом определенных преобразований, которым были подвергнуты входные данные. В качестве очень простого случая можно представить себе, что если входной строкой является "у пациента имеется высокая температура, то выходной строкой может быть "пациент должен принять аспирин. Обратите внимание на то, что за этими строками не закреплен какой-либо смысл. Иными словами, манипуляции со строками основаны на синтаксисе, а не на семантике, те. не на понимании того, что скрывается за словами "высокая температура, "аспирин" и "пациент. Люди знают, что означают эти строки в реальном мире, а продукционная система Поста применяется лишь в качестве способа преобразования одной строки в другую. Для данного примера может быть предусмотрено следующее продукционное правило антецедент -+ консеквент у пациента имеется высокая температура пациент должен принять аспирин В этом правиле стрелка означает, что одна строка должна быть преобразована в другую. Указанное правило можно интерпретировать с помощью более знакомой системы обозначений IF — THEN следующим образом IF у пациента имеется высокая температура THEN пациент должен принять аспирин Продукционные правила также могут иметь несколько антецедентов, как в следующем примере у пациента имеется высокая температура AND температура выше градуса -+ обратиться к врачу Обратите внимание на то, что специальная связка AND не входит в состав ни одной строки. Связка AND указывает, что данное правило имеет несколько антецедентов. Продукционная система Поста состоит из группы продукционных правил, подобных приведенным ниже (числа, заданные в этих правилах в круглых скобках, упоминаются в дальнейшем обсуждении. (1) двигатель автомобиля не запускается -+ проверить аккумулятор Глава 1. Введение в экспертные системы (2) двигатель автомобиля не запускается - проверить наличие бензина (проверить аккуыулятор AND аккумулятор неисправен -заменить аккуыулятор (4) проверить наличие бензина бензин отсутствует — + заполнить бак бензином Если обнаруживается строка "двигатель автомобиля не запускается", то могут использоваться правила (1) или (2) для выработки строк "неисправен аккумулятор" и "проверить аккумулятор. Но механизм управления не предусматривает применения к строке одновременно обоих правил. Может быть применено только одно правило, оба правила последовательно или ни одного правила. Если есть еще одна строка "проверить аккумулятора также строка "аккумулятор неисправен, то может быть применено правило (3) для выработки строки "заменить аккумулятор. В отличие от обычного языка программирования, такого как С или С, порядок, в котором записаны правила, не имеет никакого значения. Правила в рассматриваемом примере могут быть записаны в указанном ниже порядке, а система при этом остается неизменной. (4) проверить наличие бензина бензин отсутствует — заполнить бак бензином (2) двигатель автомобиля не запускается — проверить наличие бензина (двигатель автомобиля не запускается - проверить аккуыулятор (3) проверить аккумулятор AND аккумулятор неисправен - заыенить аккуыулятор Безусловно, продукционные правила Поста были необходимы для формирования определенной части фундамента экспертных систем, но они небыли достаточными для написания практически применимых программ. Основным ограничением продукционных правил Поста сточки зрения программирования является отсутствие стратегии управления, которая позволяла бы регламентировать применение правил. Система Поста позволяет применять правила к строкам в любой форме, поскольку отсутствует какая- либо спецификация, определяющая то, как должны применяться те или иные правила. В качестве аналогии предположим, что вы отправились в библиотеку, чтобы найти определенную книгу по экспертным системам. В библиотеке вы начинаете бессистемно просматривать книги на полках, пытаясь найти требуемую. Если библиотека довольно большая, тона поиск необходимой книги может потребоваться много времени. Даже если вы найдете отделение с книгами по экспертным системам, то следующая случайная попытка поиска может привести вас в совершенно 1.10. Продукционные системы другое отделение, например, посвященное французской кулинарии. Ситуация становится еще хуже, если вам требуется материал из первой книги, чтобы вы могли определить, какую вторую книгу необходимо найти. Случайный поиск второй книги также отнимет много времени. Марковские алгоритмы АВ НГЛ после ее применения к входной строке GABKAB вырабатывает новую строку СН13КАВ. Поскольку теперь продукция применяется к новой строке, окончательным результатом становится строка СНГЛКН13. Специальный символ Л обозначает пустую строку, не содержащую символов. Например, следующая продукция удаляет все вхождения символа А в строке А л Другие специальные символы могут представлять любой отдельный символ и обозначаются строчными буквами а, ос, х, y, z. Эти символы представляют собой односимвольные переменные и являются важной частью современных языков экспертных систем. Например, следующее правило меняет местами символы Аи В в строке, где х — любой единственный символ: АхВ ВхА Греческие буквы а,,З и т.д. используются в строках в качестве специальных знаков пунктуации. Греческие буквы применяются потому, что их можно легко отличить от обычных букв алфавита. Ниже приведен пример марковского алгоритма, который переводит первую букву входной строки вконец выходной строки. Правила упорядочены с учетом того, что правило (1) имеет высший приоритет, правило (2) — приоритет, который Следующий крупный шаг в разработке методов применения продукционных правил был сделан на основании открытия, сделанного Марковым, которое позволило определить структуру управления для продукционных систем. Марковский алгоритм — это упорядоченная группа продукций, которые применяются в порядке приоритета к входной строке. Если правило с наивысшим приоритетом является неприменимым, то используется следующее правило в порядке приоритета, и т.д. Марковский алгоритм завершает свою работу после обнаружения одного из следующих условий во-первых, последняя продукция неприменима к строке или, во-вторых, применена продукция, которая заканчивается точкой. Марковские алгоритмы могут также применяться к подстрокам строк, начиная слева. Например, продукционная система, состоящая из следующего единственного правила: Глава 1. Введение в экспертные системы 82 следует за высшим приоритетом, и т.д. Приоритет правил задан в соответствии с порядком ввода правил, как показано ниже. (1) (2) (з) обад — дох о — Л Л — о В табл. 1.11 показана трассировка выполнения алгоритма применительно к входной строке АВС. Таблица 1.11. Трассировка выполнения марковского алгоритма Правило Успех (S) или неудача (F) Строка АВС АВС аАВС ВаАС ВСаА ВСАа ВСА S S S S S алгоритм Обратите внимание на то, что марковские алгоритмы предусматривают применение вполне определенной стратегии управления, поскольку высокоприоритетные правила расположены по порядку на первых местах. При условии, что применимо правило с самым высоким приоритетом, используется это правило. В противном случаев марковском алгоритме предпринимаются попытки использовать правила с более низкими приоритетами. Безусловно, марковский алгоритм может применяться в качестве основы экспертной системы, но он является весьма неэффективным способом создания систем со многими правилами. Если требуется создать экспертную систему для решения реальных задач, содержащую сотни или тысячи правил, то проблема эффективности приобретает наибольшую Обратите внимание на то, что символ о действует аналогично временной переменной в обычном языке программирования. Но символ о не хранит значение, а используется как метка- заполнитель для обозначения места внесения изменений во входной строке. После выполнения задачи символ о удаляется с помощью правила 2. Скрытые марковские модели (Hidden Markov Model — НММ) широко используются в приложениях распознавания образов. К числу наиболее известных приложений такого типа относятся программы распознавания речи. Продукционные системы 83 важность. Независимо от того, насколько приемлемыми являются все прочие характеристики системы, если пользователю придется долго ожидать ответа, то он не станет работать с такой системой. Поэтому фактически требуется алгоритм, который имеет полную информацию обо всех правилах и может применить любое нужное правило, не предпринимая попытки последовательно проверять каждое правило. Решением этой проблемы является rete-алгоритм, разработанный Чарльзом Л. Форги (Charles L. Forgy) в университете Карнеги — Меллона в 1979 году в рамках диссертации по командному интерпретатору экспертной системы OPS (Ofhcial Production System — стандартная продукционная система) на получение степени доктора философии. Термин алгоритм происходит от латинского слова rete (по-английски читается "рити", а по-русски — "рете"), которое означает сеть. алгоритм функционирует как сеть, предназначенная для хранения большого объема информации и обеспечивающая значительное сокращение времени отклика и повышение быстродействия при запуске правил по сравнению с большими группами правил IF — THEN, которые должны проверяться один за другим в обычной системе, основанной на правилах. алгоритм основан на использовании динамической структуры данных, подобной стандартному дереву В, которая автоматически реорганизуется в целях оптимизации поиска. алгоритм представляет собой очень быстрое средство сопоставления с шаблонами, высокое быстродействие которого достигается благодаря хранению в оперативной памяти информации о правилах, находящихся в сети. Этот алгоритм предназначен для повышения быстродействия систем с прямым логическим выводом, основанных на правилах, благодаря ограничению объема работы, требуемой для повторного вычисления конфликтного множества после запуска одного из правил. Недостатком этого алгоритма является его высокие потребности в памяти, нов наши дни, когда микросхемы памяти стали такими дешевыми, этот недостаток не имеет большого значения. В алгоритме воплощены два описанных ниже эмпирических наблюдения, на основании которых была предложена структура данных, лежащая в его основе. ° Временная избыточность. Изменения, возникающие в результате запуска одного из правил, обычно затрагивают лишь несколько фактов, а каждое из этих изменений влияет только на несколько правил. ° Структурное подобие. Один и тот же шаблон часто обнаруживается в левой части больше чем одного правила. Если в системе заданы сотни или тысячи правил, то подход к организации работы, в котором компьютер последовательно проверяет вероятность того, должен ли быть выполнен запуск каждого правила, становится очень неэффективным. Благодаря разработке алгоритма появилась практическая возможность создания инструментальных средств экспертных систем даже на тех медленных Глава 1. Введение в экспертные системы Экспертные системы, основанные на правилах Машина логического вывода Факты Правила Эффективные средства сопоставления с шаблонами Средства выполнения правой части правил Продукционные правила Поста Разрешение конфликтов Rete- алгоритм Марковский алгоритм Рис. 1.7. Технологии, образующие фундамент современных экспертных систем, основанных на правилах компьютерах, которые применялись в 1970- х годах. В наши дни алгоритм продолжает оставаться важным средством повышения быстродействия в тех случаях, когда экспертная система содержит много правил. В rete- алгоритме в каждом цикле контролируются только изменения в согласованиях, поэтому в каждом цикле "распознавание действие" не приходится согласовывать факты с каждым правилом. Благодаря этому существенно повышается скорость согласования фактов с антецедентами, поскольку статические данные, которые не изменяются от цикла к циклу, могут быть проигнорированы. Эта тема будет обсуждаться более подробно в главах, посвященных языку CLIPS. В результате создания быстрых алгоритмов согласования с шаблонами, таких как rete- алгоритм, был полностью подготовлен фундамент для развертывания практических приложений экспертных систем. На рис. 1.7 приведены общие сведения о технологиях, которые образуют фундамент современных экспертных систем, основанных на правилах 85 1 11. Процедурные подходы 1.11 Процедурные подходы Принципы программирования можно классифицировать как процедурные и непроцедурные. На рис. 1.8 показана таксономия, или классификация процедурных подходов, на примере различных языков, а на рис. 1.9 показана таксономия непроцедурных подходов. Эти рисунки иллюстрируют общую связь между экспертными системами и другими подходами к программированию, поэтому должны рассматриваться как общее руководство, а не как строгие определения. В частности, язык CLIPS обозначен как основанный на правилах, нона этом языке можно написать полностью объектно-ориентированную экспертную систему или гибридную систему, в которой используются и правила, и объекты. Некоторые подходы к программированию и языки имеют такие особенности, которые позволяют отнести их больше чем к одной категории. Например, одни ученые рассматривают функциональное программирование как пример процедурного подхода, а другие считают его декларативным. Рис. 1.8. Процедурные языки Алгоритм представляет собой метод решения задачи за конечное количество шагов. Реализация алгоритма в виде программы называется процедурной программой. Термины алгоритмическое программирование, процедурное программирование и обычное программирование часто используются как синонимы для обозначения программ, не относящихся к искусственному интеллекту. В основе процедурной программы лежит такой общий принцип, что выполнение ее осуществляется последовательно, оператор за оператором, если не встречается команда перехода. Для обозначения процедурной программы часто используется еще один синоним — последовательная программа. Однако термин последовательное программирование подразумевает наличие слишком больших ограничений. Дело в том, что все современные языки программирования поддерживают рекурсию, поэтому программы могут оказаться нестрого последовательными. Отличительной особенностью процедурного подхода является то, что программист обязан точно указывать, как должно быть реализовано в программе 86 Глава 1. Введение в экспертные системы Рис. Непроцедурные языки решение задачи. Процедурный код приходится вырабатывать даже при использовании генераторов кода. Нов определенном смысле программирование с помощью генераторов кода можно считать непроцедурным программированием, поскольку генератор кода удаляет основную часть или даже весь процедурный код, написанный программистом. Цель непроцедурного программирования состоит в том, чтобы предоставить программисту возможность указывать, что должно быть сделано, и позволить системе решать, как это сделать. Императивное программирование Термины императивный и операторный используются как синонимы. Наиболее заметной отличительной особенностью такого языка, как С, является применение в нем операторов, которые представляют собой указания или команды компьютеру, сообщающие, что нужно сделать. Но следует отметить, что в объектно-ориентированной версии языка С, те. в языке С++, также могут использоваться объекты, а общий принцип работы программы состоит в том, что объекты передают сообщения друг другу и тем самым управляют ходом выполнения программы. Таким образом, выполнение объектно- ориентированной программы в большей степени напоминает работу системы, управляемой событиями, а не императивной системы, в основе которой лежит принцип, что операторы программы выполняются последовательно от начала до конца. |