дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
 Скачать 3.73 Mb.
|
как абстрактное представление действительно применяемых компьютеров, архитектура которых, в свою очередь, основана на машине Тьюринга и фон-неймановской машине с регистрами и хранилищем данных (памятью. В основе архитектуры этих машин лежит понятие модифицируемого хранилища данных. В языке программи- 1.11. Процедурные подходы 87 рования аналогом модифицируемого хранилища данных являются переменные и результаты присваивания значений переменным, а хранилище данных представляет собой объект, которым управляет программа. В языках императивного программирования предусмотрен богатый набор команд, которые позволяют задавать структуру кода и управлять хранилищем данных. В каждом языке императивного программирования определено конкретное представление об аппаратных средствах. Эти представления настолько отличаются друг от друга, что принято вести речь, например, о виртуальной машине Pascal или виртуальной машине Java, которая выполняет байт-коды с учетом конкретной аппаратной платформы. Благодаря такой особенности виртуальных машин обеспечивается возможность переноса байт-кода без изменений с одной компьютерной платформы на другую. Успешное распространение языка Pascal в 1970 — х годах достигнуто в основном за счет переносимости байт-кода. В дальнейшем та же система была применена в языке Java. В действительности в языке программирования, поддерживаемом фактически применяемыми аппаратными средствами и операционной системой, виртуальную машину реализует компилятор, который определяется языком программирования. В императивном программировании значение может быть обозначено именем, а в дальнейшем это имя может быть присвоено другому значению. Коллекция имени связанных сними значений, а также местонахождение в программе оператора, которому передано управление, представляет собой состояние. Состояние этологическая модель памяти, представляющая собой ассоциацию между местонахождениями в памяти и значениями. Программу входе ее выполнения можно рассматривать как осуществляющую переход изначального состояния в конечнсе и при этом проходящую через последовательность промежуточных состояний. Переход от одного состояния в другое определяется операциями присваивания, командами ввода и командами определения хода выполнения. Императивные языки были разработаны в целях освобождения программиста от необходимости составления кода на языке ассемблера в фон- неймановской архитектуре. Поэтому в императивных языках обеспечивается большая поддержка переменных, операций присваивания и операций повторного выполнения. Все эти операции представляют собой операции низкого уровня, поэтому в современных языках предпринимается попытка их сокрытия путем предоставления таких средств, как рекурсия, процедуры, модули, пакеты и т.д. Императивные языки характеризуются также тем, что в них широко используется жесткая структура управления ив связи с этим реализуются нисходящие проекты программ. Серьезная проблема, связанная с использованием всех языков, заключается в том, что задача доказательства правильности программы является очень сложной. Под понятием правильной программы подразумевается непротиворечивая программа (эта тема обсуждается более подробно в главе 2). Сточки зрения искусственного интеллекта еще одной серьезной проблемой при использовании Глава 1. Введение в экспертные системы императивных языков является то, что они не обеспечивают достаточно эффективного манипулирования символами. Дело в том, что архитектура императивных языков была модифицирована таким образом, чтобы они соответствовали фон-неймановской компьютерной архитектуре, поэтому по указанному принципу были созданы языки, которые позволяют очень хорошо осуществлять сложные математические расчеты, ноне обеспечивают манипулирование символами. Однако для написания командных интерпретаторов экспертных систем в качестве базовых языков использовались императивные языки, такие как Си объектноориентированные языки, подобные С++ или Java. Эти языки и созданные на их основе командные интерпретаторы работают более эффективно и быстро на компьютерах общего назначения по сравнению с первыми версиями командных интерпретаторов, созданных с использованием языка LISP, для которого требуется специальное аппаратное обеспечение, предназначенное исключительно для LISP. Итак, императивные языки характеризуются тем, что создаваемые сих помощью программы являются последовательными, поэтому указанные языки не позволяют непосредственно реализовывать достаточно эффективные экспертные системы, особенно основанные на правилах. В качестве иллюстрации этой проблемы рассмотрим способ представления в виде кода информации о реальной задаче с сотнями или тысячами правил. Например, в базе знаний классической системы XCON, применяемой для определения конфигурации компьютерных систем, содержатся приблизительно 7000 правил. Вначале были предприняты безуспешные попытки написать такую программу на языке или ВАЯС, и только после этого был принят более подходящий подход, основанный на использовании экспертной системы. Такое инструментальное средство экспертной системы, как CLIPS, позволяет создать подобную крупную базу правил намного проще, чем при использовании программирования на языке третьего поколения или объектно- ориентированном языке, таком как Java, С+ или СФ. Чтобы полностью оценить преимущества языка экспертной системы, необходимо прежде всего попытаться составить на нем программу. Программирование на языке CLIPS рассматривается далее в этой книге. Непосредственный способ представления этих знаний на императивном языке мог бы предусматривать использование 7000 операторов IF — THEN или очень и очень большого оператора САЯЕ. Такой стиль программирования приводит к появлению весьма серьезных проблем сточки зрения производительности, поскольку в каждом цикле "распознавание — действие" приходится выполнять поиск шаблонов, сопоставляемых с фактами, во всех 7000 правил. Следует отметить, что программное обеспечение машины логического вывода и применяемого в ней цикла "распознавание действие" также приходится создавать на императивном языке. Но при этом ситуация становится намного сложнее, чем при оформлении в виде кода 7000 правил, поскольку многие правила активизируются в результате активизации других правил. Например, если речь идет о том, нужно ли останав- 89 1.11. Процедурные подходы Функциональное программирование По своему характеру функциональное программирование, которое иллюстрируется на примере таких языков, как LISP, значительно отличается от программирования на основе операторных языков, поскольку в последних в основном применяются сложные управляющие структуры и нисходящее проектирование. ливаться, увидев красный свет на светофоре, то необходимо учитывать, что это правило действует, только если вы приближаетесь к светофору, а не после того, как вы его миновали. В системе, основанной на правилах, могут также возникать многие другие варианты взаимодействия. Некоторые правила могут предусматривать добавление фактов в базу знаний, другие — извлечение фактов, а третьи модификацию фактов. А в случае машинного обучения могут применяться более сложные правила для создания новых правил или удаления существующих. Эффективность программы можно было бы повысить, если бы существовала возможность упорядочить правила таким образом, чтобы правила, которые должны быть выполнены с наибольшей вероятностью, были перенесены в самое начало списка. Однако для осуществления такого подхода потребовался бы значительный объем работы по настройке системы, причем после добавления новых правила также удаления и модификации существующих правил снова требовалась бы настройка. Лучший метод повышения эффективности состоит в создании в памяти динамической сети шаблонов правил, позволяющей уменьшить время поиска для определения того, какие правила должны быть активизированы. К тому же было бы лучше не вынуждать программиста создавать такую древовидную сеть вручную, а формировать ее автоматически с помощью программы, учитывающей синтаксис шаблонов и действий в правилах IF — THEN. Было бы также удобно иметь синтаксис правил IF — THEN, который в большей степени способствовал бы успешному представлению знаний и допускал применение мощных средств сопоставления с шаблонами. Для этого необходимо разработать синтаксический анализатор, который бы анализировал структуру входных данных, а также интерпретатор или компилятор, позволяющий обрабатывать новые синтаксические конструкции правил IF — THEN. Результатом применения всех указанных методов повышения эффективности становится специализированная экспертная система. На основе одной экспертной системы можно создавать другие экспертные системы, отделив от нее машину логического вывода, синтаксический анализатор и интерпретатор, те. компоненты, которые в целом принято называть командным интерпретатором экспертной системы. Нов наши дни, безусловно, гораздо проще воспользоваться такими существующими инструментальными средствами, как которые имеют качественную документацию и прошли серьезную проверку, а не выполнять всю указанную разработку с нуля. Глава 1. Введение в экспертные системы 90 cube(x) =х*х*к, где х вещественное число, а cube — функция с вещественными значениями Определение функции возведения в куб, состоит из следующих трех частей 1. отображение — х * х * х область определения — вещественные числа 3. область значений — вещественные числа. Символ = означает "является эквивалентным, или "определен как. Следующее обозначение представляет собой сокращенный способ записи утверждения, что функция возведения в куб (cube) представляет собой отображение из области определения, состоящей из вещественных чисел и обозначенной как Я, в область значений, также состоящей из вещественных чисел cube:ß - Я Общим обозначением для функции f, которая выполняет отображение из области определения S в область значений Т, служит f S ТА проекцией функции f называется множество всех образов элементов з, где 8 — элемент множества S. В случае функции возведения в куб образом элемента 8 является элемента проекция представляет собой множество всех вещественных чисел. Применительно к функции возведения в куб проекция и область значений совпадают. Но это условие может не соблюдаться применительно к другим функциям, таким как функция возведения в квадрат х w х, областью определения и областью значений которой являются вещественные числа. Дело в том, Решение задач при их разбиении на подзадачи намного упрощается. Но обычные языки программирования не позволяют применять достаточно сложные принципы такого разбиения. С другой стороны, в функциональных языках подобные ограничения во многом устранены. Разбивка программ на модули, соответствующие подзадачам, значительно облегчается в основном благодаря использованию таких двух средств функциональных языков, как функции высокого порядка и отложенное вычисление. В основе функционального программирования лежит фундаментальная идея объединения простых функций для создания более мощных функций. При этом по сути применяется метод восходящего проектирования, в отличие от обычных методов нисходящего проектирования, применяемых в императивных языках. Функциональное программирование сосредоточено вокруг понятия функции. Сточки зрения математики функция представляет собой отображение, или правило, по которому устанавливается соответствие между элементами одного множества (области определения) и другого множества (области значений. Пример определения функции приведен ниже 1 11. Процедурные подходы что проекцией по отношению к функции возведения в квадрат являются только неотрицательные вещественные числа, поэтому проекция и область значений не совпадают. С использованием обозначения, применяемого для описания множества, проекции функции можно определить таким образом Фигурные скобки (()) обозначают множество, а вертикальная черта (I) читается "где". Приведенное выше выражение можно интерпретировать так, что проекция В эквивалентна множеству значений f (s), где каждый элемент s принадлежит к множеству S. Отображение — это множество упорядоченных пар (s, t), где s 6 S, t Е Т и t = f (Каждому элементу в множестве S должен соответствовать один и только один элемент множества Т. Но одному элементу s может соответствовать несколько значений t. В качестве простого примера можно указать, что каждое положительное число и имеет два квадратных корня,:Еф. Функции могут быть также определены рекурсивно, как в следующем примере) = их Если параметр х передается по ссылке и его значение изменяется в вызове функции х, то какое значение будет использоваться для второго вхождения переменной х в это выражение В зависимости оттого, как написан компилятор, х может иметь первоначальное значение, если этот элемент выражения сохраняется где и — целое число и factorial — целочисленная функция Рекурсивные функции очень широко применяются в таких функциональных языках, как LISP. Математические понятия и выражения являются ссылочно прозрачными, поскольку значение всего выражения полностью определяется его частями, а между частями отсутствует какое-либо скрытое взаимодействие. Например, рассмотрим функциональное выражение х + (2 * х. Очевидно, что его результатом является З*х. Это означает, что оба выражениях+ (хи З*х, дают одинаковый результат, независимо оттого, какие значения будут подставлены вместо х. В качестве х можно даже подставить другие функции, и результат сравнения двух выражений останется неизменным. Допустим, что д) — некоторая произвольная функция. Ив таком случае выражение д) + (2 * 6(y)) будет по-прежнему эквивалентно выражению 3 * 6(д). Теперь рассмотрим следующий оператор присваивания в таком императивном языке программирования, как С 92 Глава 1. Введение в экспертные системы в стеке, или новое значение, если хне сохраняется. Еще один источник путаницы возникает, если один компилятор вычисляет выражения справа налево, а другой слева направо. В таком случае при использовании разных компиляторов результат вычисления выражениях не будет равен результату вычисления выражениях+ х, даже если применяется один и тот же язык. Вследствие применения глобальных переменных могут возникать и другие побочные эффекты. Поэтому программные функции, в отличие от математических функций, не являются ссылочно прозрачными. Функциональные языки программирования создавались с учетом обеспечения требования к ссылочной прозрачности. Функциональный язык состоит из следующих пяти частей ° обьекты данных, с которыми должны оперировать языковые функции примитивные функции, которые должны применяться к объектам данных ° функциональные формы, предназначенные для создания новых функций на основе существующих функций прикладные операции на функциях, которые возвращают значения ° процедуры именования, предназначенные для присваивания имен новым функциям. Функциональные языки, как правило, реализуются с помощью интерпретаторов для обеспечения простоты конструирования и быстрого отклика на ввод команд пользователем. В языке LISP (сокращение от LIST Processing — обработка списков) объекты данных представляют собой символические выражения (выражения, которые являются либо списками, либо атомами. Ниже приведены примеры списков, которые демонстрируются в связи стем, что стиль их представления аналогичен тому стилю, с помощью которого в языке CLIPS программируются шаблоны. (milk eggs cheese) (shopping (groceries (milk eggs cheese) clothes (pants))) (Шаблоны, подобные этим, могут задаваться в программе в условном выражении либо в левой части (Left-Hand-Side — правила и представлять факты или вложенные списки, как в примере списка "shopping". Если условное выражение имеет истинное значение, то выполняется правая часть (RightHand- Side — RHS) правила и создаются новые списки. В программе может быть предусмотрено выполнение в правой части правила других действий, таких как извлечение фактов. Списки всегда заключены в парные круглые скобки, а элементы списков разделены пробелами. Элементами списков могут быть атомы, такие как milk, eggs и cheese, или вложенные списки, такие как eggs cheese) и (pants) . Списки можно разбивать на элементы, а атомы не под. Процедурные подходы 93 лежат разбиению. Пустой список, не содержит элементов и обозначается как Первоначальная версия языка LISP именовалась чистым языком LISP, поскольку была чисто функциональной. Но эта версия не была достаточно эффективным средством написания программ. Поэтому в LISP были введены нефункциональные дополнения в целях повышения эффективности написания программ. В качестве примера можно назвать оператор который действует как оператор присваивания, а операторы и PROG могут использоваться для создания локальных переменных и выполнения последовательности S-выражений. Безусловно, эти операторы действуют аналогично функциям, ноне являются функциональными в строго математическом смысле. По истечении определенного времени после его создания LISP стал ведущим языком искусственного интеллекта в Соединенных Штатах. На языке LISP было написано много оригинальных командных интерпретаторов экспертных систем, поскольку с помощью LISP можно очень легко проводить эксперименты по созданию программ. Но обычные компьютеры недостаточно эффективно выполняют программы LISP, а эксплуатация командных интерпретаторов, созданных с помощью LISP, осуществляется еще менее эффективно. Безусловно, по мере усовершенствования процессоров и повышения их тактовой частоты возрастает и производительность программ LISP. Таким образом, с внедрением программ LISP связана проблема значительных издержек, которая оказала свое влияние на разработку таких программ и стала причиной возникновения так называемой проблемы доставки. Дело в том, что недостаточно лишь разработать великолепную программу, если ее невозможно доставить пользователю для последующей эксплуатации из-за слишком больших издержек. Даже если разработка ведется с помощью превосходной рабочей станции, компьютер с аналогичными характеристиками не всегда становится приемлемым средством доставки программы пользователю в связи с наличием ограничений по быстродействию, мощности, размерам, весу, стойкости к воздействию окружающей среды или стоимости. Для некоторых приложений может даже потребоваться, чтобы окончательный вариант кода был помещен в ПЗУ в целях уменьшения стоимости и обеспечения энергонезависимости. Но при использовании определенных инструментальных средств искусственного интеллекта и экспертных систем, для эксплуатации которых требуются специальные аппаратные средства, возможность помещения кода в ПЗУ может стать проблематичной. Поэтому лучше обеспечить такую возможность заранее, чем в дальнейшем сталкиваться с необходимостью повторной разработки кода программы. Еще одна проблема состоит в том, как обеспечить при создании интеллектуальных систем сопряжение языков искусственного интеллекта с такими обычными языками программирования, как С, С, Си. Приложения, в которых должен осуществляться большой объем сложных математических расчетов, |