дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
 Скачать 3.73 Mb.
|
|
Глава 1. Введение в экспертные системы 94 Непроцедурные подходы Суть непроцедурных подходов состоит в том, что они не требуют от программиста описания точных подробностей того, как должна быть решена задача. В этом непроцедурные подходы коренным образом отличаются от процедурных подходов, которые требуют указания того, как должна вычисляться последовательность функций или операторов. При использовании непроцедурных подходов основной объем работы заключается в том, чтобы указать, что должно быть сделано, и позволить системе определить, как это сделать. Декларативное программирование В декларативном подходе путь достижения цели рассматривается отдельно от методов, используемых для достижения этой цели. Пользователь задает цель, а основополагающий механизм реализации предпринимает попытку достичь данной цели или, как принято говорить, выполнить эту цель. Для реализации такой декларативной модели было создано множество подходов и связанных сними языков программирования. Обьектно- ориентированное программирование Еще одним подходом, который может отчасти рассматриваться как императивный и отчасти как декларативный, является обьектно- ориентированный подход. В настоящее время термин обьектно- ориентированный используется для обозна- лучше всего разрабатывать с помощью обычных языков, а не инструментальных средств экспертных систем. Именно поэтому в языке CLIPS предусмотрена возможность легко создавать собственные функции на базовом языке. С дополнительными сведениями по этими другим сложным темам можно ознакомиться в оперативном режиме с помощью справочного руководства CLIPS Reference Мапиа1 (http: //www. ghgcorp. corn/clips/CLIPS. html). Обычно экспертные системы, написанные на языке LISP, сложно внедрить в программы на языках, отличных от LISP, если для этого не предусмотрены специальные конструкции. Поэтому основным требованием при выборе языка искусственного интеллекта является анализ возможности применения того языка, на котором написано само инструментальное средство. В настоящее время исходя из соображений переносимости, эффективности и быстродействия код многих инструментальных средств экспертных систем разрабатывается на языке С или преобразуется в код на языке С. Благодаря этому устраняется также проблема, связанная стем, что для приложений, основанных на языке LISP, требуются дорогостоящие специальные аппаратные средства 1.12. Непроцедурные подходы 95 чения таких языков программирования, как Си СФ. Основная идея этого подхода состоит в том, что программа разрабатывается по принципу представления данных, используемых в программе, в виде объектов, с последующей реализацией операций над этими объектами. Такой способ разработки программы является противоположным по отношению к способу, применяемому при нисходящем проектировании, который осуществляется путем поэтапного уточнения управляющей структуры программы. Один из широко применяемых способов объектноориентированного проектирования основан на языке UML (Unified Modeling Language — универсальный язык моделирования. В качестве примера объектно-ориентированного проекта рассмотрим задачу написания программы для управления расчетным счетом с помощью интерактивного меню. Наиболее важными объектами данных являются текущий остаток, суммы списания и зачисления. После определения соответствующих классов могут быть также определены различные методы, предназначенные для осуществления операций с объектами данных. В состав таких операций могут входить зачисление, списание, а также начисление месячных процентов. После определения всех объектов данных, операций и интерфейса меню можно приступать к составлению программы. Такая методология объектно-ориентированного проектирования хорошо приспособлена для создания программ, имеющих слабую управляющую структуру. С другой стороны, подобная методология может оказаться неприменимой при создании программ, имеющих сильную управляющую структуру, таких как приложения для учета заработной платы. Нов настоящее время объектно-ориентированное программирование применяется весьма широко, поскольку позволяет снизить затраты на сопровождение и обеспечить повторное использование кода объектов. Термин объектно-ориентированное программирование первоначально использовался применительно к таким языкам, как Smalltalk, которые были специально предназначены для работы с объектами. В настоящее время этот термин иногда применяется для обозначения способа разработки объектно-ориентированного проекта даже на языке, не имеющем подлинной объектной поддержки. Такие современные объектно-ориентированные языки, как Си С, обладают средствами поддержки объектов, встроенными непосредственно в сам язык. Язык происходит от языка ЯМШ.А 67, разработанного для моделирования (simulation, отсюда название языка. В языке ЯМШ.А 67 реализовано понятие класса, которое легло в основу понятия сокрытия информации реализация этого понятия позволяет достичь такой ситуации, в которой программисту требуется знать лишь то, как используется объект, и не учитывать подробности внутреннего устройства объекта и того, как он запрограммирован. Класс — это не тип. Экземпляром класса является объект данных, с которым могут проводиться необходимые манипуляции. Термин экземпляр был перенесен на экспертные системы, в которых он означает факт, согласующийся с шаблоном. Аналогичным Глава 1. Введение в экспертные системы Логическое программирование Одним из первых приложений искусственного интеллекта, в которых использовались компьютеры, было доказательство логических теорем с помощью программы Logic Theorist (Логик-теоретик) Ньюэлла (Newell) и Саймона (Simon). Впервые отчет о создании этой программы был опубликован на Дартмутской конференции по искусственному интеллекту в 1956 году. Данный отчет вызвал сенсацию, поскольку до этого компьютеры применялись только для числовых расчетов. А в данном случае компьютер механически проводил рассуждения, необходимые для доказательства математических теорем, тогда как до сих пор считалось, что эту задачу способны выполнять только математики. Термин механический означает автоматический; впервые этот термин был применен для обозначения механического вычислительного устройства, предложенного Бэббиджем (Babbage) в XIX столетии. образом в проблематике экспертных систем принято применять формулировку, что использован экземпляр правила, в тех случаях, когда выполняется левая часть этого правила. В системах, основанных на правилах, термины активизированный и используемый в качестве экземпляра рассматриваются как синонимы. Еще одним важным понятием, заимствованным из языка А 67, является наследование. С помощью наследования может быть определен подкласс, который наследует свойства одного или нескольких классов. Например, может быть определен один класс, состоящий из объектов, которые используются в стеке, и другой класс, предназначенный для применения в качестве класса комплексных чисел. После этого может быть легко определен подкласс, состоящий из объектов, которые представляют собой комплексные числа, используемые в стеке. Таким образом, эти объекты имеют свойства, унаследованные от вышестоящих классов, называемых суперклассами. Понятие наследования может быть расширено для организации объектов в виде иерархии, в которой объекты могут наследовать свойства от своих классов, а эти классы, в свою очередь, могут наследовать свойства от вышестоящих классов, и т.д. Принцип наследования является очень полезным, поскольку позволяет создавать объекты, которые наследуют свойства от своих классов при этом программист не обязан повторно задавать каждое свойство, наследуемое объектом. Но задача обеспечения множественного наследования является более сложной, поэтому такая возможность в языках Java и СФ не предусмотрена. Но язык создан на основе языка Си в связи с этим позволяет воспользоваться преимуществами множественного наследования. В язык CLIPS встроен полноценный объектно- ориентированный язык, называемый COOL. Внутреннее функционирование языка COOL осуществляется незаметно для пользователя, поэтому пользователю достаточно лишь понимать суть объектно-ориентированного программирования 97 1.12. Непроцедурные подходы При разработке программы Theorist и ее преемника, программы GPS (General Problem Solver — универсальный решатель задач, Ньюэлл и Саймон сосредоточились на осуществлении попытки реализовать мощные алгоритмы, позволяющие решать любые задачи. Программа Logic Theorist была предназначена только для доказательства математических теорема программа разрабатывалась для решения логических задач любого типа, включая игры и головоломки, такие как шахматы, задача с ханойской башней, задача с миссионерами и каннибалами и криптоарифметические задачи. Кроме того, ниже приведен пример известной криптоарифметической головоломки (числового ребуса, которая рассматривалась Ньюэллом и Саймоном. По условию этой головоломки известно, чтоП=5. DONALD + GERALD ROBERT Задача состоит в том, чтобы подобрать вместо букв разные цифры от 0 дои преобразовать этот ребус в правильный пример сложения чисел. Программа оказалась первой программой решения задач, в которой знания в области решения задач были явно отделены от знаний в проблемной области. Теперь такой подход, предусматривающий явное отделение знаний в области решения задач от знаний в проблемной области, используется в качестве основы экспертных систем. В современных экспертных системах решения о том, какие знания должны использоваться и каких следует применить, принимает машина логического вывода. Усилия в направлении усовершенствования автоматического доказательства теорем продолжались ив дальнейшем. К началу х годов было обнаружено, что вычисление представляет собой частный случай механической, логической дедукции. После того как к высказываниям в форме "заключение i f условия" был применен обратный логический вывод, обнаружилось, что он является достаточно мощным для доказательства весьма сложных теорем. В этой форме условия могут рассматриваться как представляющие шаблоны, с которыми должно быть найдено соответствие по такому же принципу, как в продукционных правилах, рассматривавшихся ранее. Высказывания, представленные в такой форме, принято называть хорновскими выражениями в честь Альфреда Хорна (Alfred Horn), который впервые исследовал их. В 1972 году Ковальский (Kowalski), Колмероэ (Colmerauer) и Руссел (Roussell) создали язык PROLOG для реализации принципа логического программирования на основе обратного логического вывода с использованием хорновских выражений. Обратный логический вывод может применяться не только для выражения знаний с помощью декларативного представления, но и для управления процессом формирования рассуждений. Как правило, обратный логический вывод Глава 1. Введение в экспертные системы осуществляется путем определения меньших подцелей, которые должны быть удовлетворены для того, чтобы могла быть удовлетворена первоначальная цель. Затем эти подцели могут дальше подвергаться разбиению на меньшие подцели и т.д. В качестве примера декларативных знаний можно привести следующий классический пример Все люди смертны Сократ — человек Это высказывание может быть представлено с помощью хорновских выражений таким образом некто смертен IF некто — человек Сократ — человек IF (во всех случаях) В данном высказывании, касающемся Сократа, условие IF является истинным во всех случаях. Иными словами, для использования знаний о Сократе не требуется согласования фактов с какими-либо шаблонами. Сравните это с таким случаем, где речь идет о смертных, и некто должен быть человеком, для того чтобы был удовлетворен шаблон условия IF. Обратите внимание на то, что хорновское выражение может интерпретироваться как процедура, которая указывает, как должна быть удовлетворена цель. Таким образом, для определения того, что некто является смертным, необходимо определить, является ли хоть кто-либо человеком. Ниже приведен немного более сложный пример. Условиями нормальной эксплуатации автомобиля является наличие бензина, масла и надутых шин Этот пример может быть представлен с помощью хорновского выражения следующим образом х является исправным автомобилем и может нормально эксплуатироваться IF х снабжен бензином их снабжен маслом и IF x имеет надутые шины Здесь заслуживает внимания то, что проблема определения, пригоден ли автомобиль к нормальной эксплуатации, сведена к трем более простым подпроблемам, или подцелям. А теперь предположим, что имеются некоторые дополнительные декларативные знания наподобие следующих Бензиномер показывает ненулевое значение IF автомобиль снабжен бензином Указатель уровня масла показывает ненулевое значение. Непроцедурные подходы 99 IF автомобиль снабжен маслом Воздушный манометр показывает по меньшей мере 20 IF автомобиль имеет надутые шины Бензиномер показывает ненулевое значение Указатель уровня масла показывает нулевое значение Воздушный манометр показывает 15 Эти знания могут быть представлены с помощью таких хорновских выражений х снабжен бензином IF бензиномер показывает ненулевое значение х снабжен маслом IF указатель уровня масла показывает ненулевое значение х имеет надутые шины воздушный манометр показывает по меньшей мере 20 Бензиномер показывает ненулевое значение IF (во всех случаях) Указатель уровня масла показывает нулевое значение Воздушный манометр показывает 15 IF (во всех случаях) На основании этих выражений программа автоматического доказательства теорем может доказать, что автомобиль непригоден к нормальной эксплуатации, поскольку в нем нет масла, а давление воздуха является недостаточным. Одним из преимуществ систем обратного логического вывода является то, что выполнение заложенных в них программ может осуществляться параллельно. Это означает, что при наличии многочисленных процессоров они могли бы одновременно работать над выполнением подцелей. В языке предусмотрена машина обратного логического вывода, поэтому он представляет собой больше чем просто язык. Как минимум PROLOG можно рассматривать как командный интерпретатор, поскольку он требует применения следующих компонентов интерпретатор или машина логического вывода ° база данных (факты и правила ° определенная форма сопоставления с шаблонами, называемая унификацией ° механизм перебора с возвратами, позволяющий переходить к исследованию альтернативных подцелей, если текущая попытка поиска, предпринятая для выполнения некоторой цели, оказалась неудачной. В качестве примера обратного логического вывода предположим, что вы можете купить масло для того, чтобы обеспечить нормальную эксплуатацию своего автомобиля, если у вас есть наличные или кредитная карточка. В данном случае Глава 1. Введение в экспертные системы 100 Экспертные системы Экспертные системы могут рассматриваться как направление декларативного программирования, поскольку программист не указывает на уровне алгоритма, как программа должна достичь заданной цели. Например, в экспертной системе, основанной на правилах, любое из правил может стать активизированными быть помещено в рабочий список правил, если левая часть этого правила согласуется с фактами. Порядок, в котором были введены правила, не влияет на то, какие правила должны быть активизированы. Таким образом, порядок операторов в программе не задает жесткий порядок управления ходом выполнения. Экспертные системы других типов основаны на фреймах, как описано в главе 2, и сетях логического вывода, которые рассматриваются в главе 4. одной из подцелей становится проверка того, есть ли у вас наличные. Если тот факт, что у вас есть наличные, не обнаруживается, то механизм перебора с возвратами может затем перейти к исследованию другой подцели для определения того, если ли у вас кредитная карточка. Если кредитная карточка имеется, то цель покупки масла может быть достигнута. Следует отметить, что отсутствие некоторого факта, требуемого для доказательства целевого утверждения, приводит к такому же действенному дальнейшему развитию логического вывода (хотя, возможно, менее эффективному, чем наличие отрицательного факта, такого как "Указатель уровня масла показывает нулевое значение. К недостижению цели могут приводить и отрицательные, и отсутствующие факты (очевидно, что в политике часто наблюдается другая логика. Если по условиям задачи механизмы перебора с возвратами и сопоставления с шаблонами не требуются, то программист должен исключить возможность их использования или разработать код на другом языке. Одним из преимуществ логического программирования является возможность применения исполняемых спецификаций. Это означает, что для создания исполняемой программы достаточно представить требования к решению задачи в виде хорновских выражений. В этом состоит весьма существенное отличие от обычного программирования, в котором документ с описанием требований отнюдь не напоминает окончательный исполняемый код. В отличие от систем, основанных на применении продукционных правил, в языке PROLOG порядок, в котором заданы подцели, факты и правила, существенно влияет на работу этой программы. С другой стороны, способ поиска данных в базе данных, применяемый в программе влияет на эффективность программы и поэтому на ее быстродействие. Более того, в некоторых случаях программы выполняются правильно, если подцели, факты и правила введены водном порядке, но входят в бесконечный цикл или вырабатывают ошибки этапа прогона, если этот порядок становится другим 1.12. Непроцедурные подходы Между экспертными системами и обычными программами имеется целый ряд различий. Некоторые из этих различий перечислены в табл. Таблица 1.12. Некоторые различия между обычными программами и экспертными системами Обычная программа Экспертная система Характеристика Способ управления ходом выполнения Средства и данные управления Слабая Сильная На основе правили логического вывода С помощью алгоритма Отсутствует или применяется в небольших масштабах Применяется в крупных масштабах Поиск решения С применением правил Решение задач Возможно применение неполных или неправильных данных Входные данные Обработка непредвиденных входных данных Связана с возникновением значительных сложностей Всегда правильные Выходные данные Обычно предусмотрено Объяснение причин полу- Отсутствует чения конкретных результатов Символические рассуждения Приложения Под влиянием правил Выполнение Структурированный проект Проект программы Связана с затруднениями Осуществляется в виде крупных этапов Происходит постепенно Детерминированность управления Способ принятия решений Возможность модификации приложения Расширение возможностей приложения С |