дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
 Скачать 3.73 Mb.
|
|
3.3. Пространства состояний и пространства задач 205 После этого безуспешно проводится поиск с использованием пути итак до тех пор, пока не обнаруживается первый правильный путь ABDCA. Пространства слабо структурированных задач Полезным приложением пространств состояний является представление слабо структурированных задач. В главе 1 слабо структурированная задача определена как задача, с которой ассоциируются какие-либо неопределенности. Эти неопределенности могут быть описаны более точно с помощью пространства задач. В качестве примера слабо структурированной задачи еще раз рассмотрим случай, в котором некоторое лицо собирается отправиться в путешествие и, не сумев найти ничего подходящего с помощью поискав оперативном режиме, обращается в бюро путешествий (см. главу 1). В табл. 3.1 перечислены некоторые характеристики этой слабо структурированной задачи как пространства задач с указанием ответов рассматриваемого лица на вопросы агента бюро путешествий. Таблица 3.1. Пример слабо структурированной задачи выбора путешествия Характерная особенность Ответ Я собираюсь куда-нибудь поехать Цель неясна Неограниченное пространство состояний Я еще не решил, в какое место отправиться Я просто люблю путешествовать; место назначения не имеет значения Не дискретное пространство задач Промежуточные состояния трудно достижимы Яне имею достаточного количества денег, чтобы отправиться куда угодно Набор возможных операций в пространстве состояний неизвестен Яне знаю, как получить деньги Временное ограничение Я должен поскорее уехать в путешествие Сравнение табл. 3.1 с табл. 1.10, приведенной в главе 1, показывает, что концепция пространства задач позволяет более точно задавать характеристики слабо структурированной задачи. Очень важно точно охарактеризовать такие параметры, чтобы определить, осуществимо ли решение, а в случае положительного ответа узнать, что требуется для получения решения. Задачу не следует обязательно считать слабо структурированной лишь потому, что в ней имеются одна, несколько или даже все подобные характеристики, поскольку многое зависит оттого, насколько строгим является подход к постановке задачи. Например, все задачи доказательства теорем имеют бесконечное количество потенциальных решений, но из-за этого задача доказательства теорем не становится слабо структурированной Глава 3. Методы логического вывода 206 3.4 Деревья AND — OR и цели Применение обратного логического вывода для поиска решения задач предусмотрено в экспертных системах многих типов. Наглядным примером системы обратного логического вывода является система PROLOG, в которой предпринимаются попытки решать любые задачи путем разбиения их на меньшие подзадачи и последующего решения подзадач. В х годах система РВ.OLOG получила широкое распространение при создании коммерческих приложений в бизнесе и промышленности (http: //www. ddj . corn/documents/ s=9064/ddj 0212ai004/0212aie004. htm). Оптимисты рассматривают процесс решения задачи как процесс достижения цели, но для достижения достаточно значимой цели иногда приходится рассматривать много подцелей. Как показывает табл. 3.1, при решении задачи выбора путешествия возникает много неопределенностей, тем не менее, агенты бюро путешествий повседневно справляются с подобными задачами. Безусловно, не все ситуации могут быть такими же безвыходными, как указанная, носам характер задачи показывает, почему поиск алгоритмического решения был бы очень трудным. Правильно сформулированной задачей является такая задача, в отношении которой известна явная постановка задачи, цель решения и операции, которые могут применяться для перехода из одного состояния (этапа) решения в другое. Правильно сформулированная задача является детерминированной, поскольку после применения некоторой операции к некоторому состоянию можно суверенностью сказать, каким будет следующее состояние. Пространство задач является ограниченным, а состояния — дискретными. Это означает, что имеется конечное количество состояний и все состояния определены полностью. В описанной выше задаче выбора путешествия пространство состояний является неограниченным, поскольку имеется бесконечно большое количество возможных пунктов назначения, в которые может отправиться путешественник. Аналогичная ситуация возникает при использовании аналогового измерительного прибора, который может показывать бесконечное количество возможных результатов измерения. Если каждый результат измерения, полученный от такого измерительного прибора, рассматривается как состояние, то количество возможных состояний бесконечно велико, асами состояния не могут быть полностью определены, поскольку положения стрелки измерительного прибора соответствуют вещественным числам. Между любыми двумя вещественными числами имеется бесконечное количество вещественных чисел, поэтому состояния не являются дискретными, и одно состояние может отличаться от другого лишь на бесконечно малую величину. В отличие от этого показания цифрового измерительного прибора являются дискретными и относятся к ограниченному пространству состояний 3.4. Деревья AND — OR и цели 207 Рис. 3.9. Решетка AND — OR, показывающая, как получить документ об окончании колледжа К одному из типов деревьев (или решеток, которые являются удобным средством представления задач обратного логического вывода, относятся деревья (или решетки) AND — OR. На рис. 3.9 показан простой пример решетки AND — предназначенной для достижения цели получения документа об окончании колледжа. Для достижения этой цели необходимо либо лично посещать колледж, либо поступить на заочные курсы. При прохождении заочных курсов работу можно выполнять либо по заданиям, полученным по почте, либо в оперативном режиме с использованием домашнего компьютера и модема Глава 3. Методы логического вывода Чтобы выполнить требования, необходимые для получения документа об образовании, необходимо достичь трех подцелей: во-первых, подать заявление, вовторых, пройти обучение и, в-третьих, сдать экзамены. Обратите внимание на то, что ребра, ведущие от цели "Выполнить требования" к этим трем подцелям, соединены отрезком кривой. Этот отрезок кривой, проведенный через ребра, показывает, что узел "Выполнить требования" это узел AND, поэтому заданная в нем цель может быть выполнена, только если будут выполнены все три его подцели. А такие целине обозначенные отрезками кривых, как "Почта", "Компьютер и модем" и "Личное посещение, заданы узлами в которых выполнение любой из указанных подцелей позволяет достичь родительской цели — "Получение документа об образовании. Структура, показанная на этой диаграмме, представляет собой решетку, поскольку подцель "Выполнить требования" имеет три родительских узла "Почта, "Компьютер и модем" и "Личное посещение. Обратите внимание на то, что было бы возможно изобразить эту диаграмму в виде дерева, просто продублировав подцель "Выполнить требования" и его поддерево целей, относящееся к целям "Почта, "Компьютер и модем" и "Личное посещение. Тем не менее цель "Выполнить требования" остается одинаковой для каждой из ее родительских целей, поэтому построение такого дерева не дает никаких реальных преимуществ и приводит к созданию более громоздкой диаграммы. В качестве еще одного простого примера на рис. 3.10 показано дерево ANDOR для решения задачи прибытия на работу с помощью различных возможных способов. Для полноты изложения следует отметить, что это дерево может быть также преобразовано в решетку. Для этого, например, можно добавить ребро от узла "Приехать на вокзал" к узлу "На автомобиле" и от узла "Пройти на вокзал" к узлу "Пешком. А на рис. 3.11 показана решетка типа AND-exclusive OR (И исключительное ИЛИ. Еще один способ описания решений задач состоит в использовании решетки AND — OR NOT, в которой применяются символические обозначения логических вентилей, а не такая система обозначений, как в деревьях AND — OR. Обозначения логических вентилей, используемых для выполнения операций AND, OR и показаны на рис. 3.12. Эти логические элементы реализуют истинностные таблицы для операций AND, OR и NOT, которые рассматривались в главе 2. А на рис. 3.13 показан вариант диаграммы, приведенной на рис. 3.9, в котором применяются логические элементы AND и OR. Деревья AND — OR и деревья решений имеют одни и те же основные преимущества и недостатки. Основным преимуществом решеток AND — OR является то, что они допускают возможность реализации в виде аппаратных средств, что позволяет добиваться высоких скоростей обработки. Такие решетки могут быть специально спроектированы в целях дальнейшего изготовления в виде интегральных микросхем. На практике для экономии производственных затрат используется 3.4. Деревья AND — OR и цели 209 цяль Добраться до работы На автомобиле Пешком Автомобиль в хорошем состоянии Достаточно бензина для поездки Ноги здоровы Поручить отремонтировать автомобиль другим Подъехать на автомобиле к заправочной станции Самостоятельно отремонтировать автомобиль Рис. 3.10. Простое дерево AND — показывающие, как добраться до места работы с помощью различных способов только один тип логических вентилей, такой как NOT AND (или NAND), а не отдельно взятые логические вентили AND, OR и NOT. На основании принципов логики можно доказать, что с помощью логического элемента NAND может быть реализована любая логическая функция. А производство интегральных микросхем, состоящих из устройств одного итого же типа, дешевле, чем производство микросхем, состоящих из логических вентилей нескольких типов. Микросхема, в которой используется прямой логический вывод, способна вычислять ответ как функцию от полученных входных данных очень быстро, поскольку обработка данных происходит в ней параллельно. Микросхемы подобного типа могут использоваться для текущего контроля данных, полученных от датчи- 210 Глава 3. Методы логического вывода Рис. 3.11. Решетка — OR для принятия решения о том, следует ли продать или отремонтировать свой автомобиль Рис. Символические обозначения логических вентилей AND, OR и ка, в реальном времени и выработки соответствующих результатов в зависимости от входных данных. Основным недостатком рассматриваемого подхода является то, что микросхемы, предназначенные для выполнения логических операций, как и другие структуры принятия решений, не могут справляться с ситуациями, на которые они не рассчитаны. С другой стороны, искусственная нейронная система, реализованная в виде микросхемы, способна успешно обрабатывать непредвиденные входные данные 211 3.5. Дедуктивная логика и силлогизмы Рис. 3.13. Вариант диаграммы, представленной на рис. 3.9, в котором используются логические вентили AND и OR 3.5 Дедуктивная логика и силлогизмы Рис. 3.14. Типы логического вывода ° Дедукция. Логическое рассуждение, в котором заключения должны следовать из соответствующих им посылок. ° Индукция. Логический вывод от частного случая к общему. Индукцияэто один из основных методов машинного обучения, в котором компьютеры обучаются без вмешательства человека. Три широко применяемых метода машинного обучения основаны на использовании коннекционистской сети Хопфилда, символических алгоритмов ID3/ID5R и эволюционных генетиче- В главе 2 рассматривались способы представления знаний, основанные на логике, а в данном разделе речь идет о том, как осуществляются логические выводы для получения новых знаний или информации. В оставшейся части этой главы рассматриваются различные методы логического вывода. Общий обзор методов логического вывода показан на рис. Краткие сведения по этой теме приведены ниже 212 Глава 3. Методы логического вывода ских алгоритмов (http: //ai bpa. arizona. edu/papers/mlir93/ mlir93 html). ° Интуиция. Метод, не основанный на проверенной теории. Ответ представляет собой всего лишь предположение, возможно, сформулированное путем подсознательно распознавания какого-то основополагающего образа. Логический вывод такого типа еще не реализован в экспертных системах. Но искусственные нейронные системы когда-либо смогут оправдать прогнозы, касающиеся их использования для осуществления логического вывода такого типа, поскольку эти системы способны выходить за рамки того, что было усвоено ими в результате обучения, а непросто предоставлять обусловленный ситуацией ответили выполнять интерполяцию. Это означает, что нейронная сеть всегда вырабатывает свое наилучшее возможное предположение, касающееся искомого решения. Эвристика. Эмпирические правила, основанные на опыте. Метод выработки и проверки — метод проб и ошибок. Часто используется в сочетании с планированием для достижения максимальной эффективности. ° Абдукция. Метод формирования рассуждений в обратном направлении, от истинного заключения к посылкам, которые могли привести к получению этого заключения. ° Рассуждения, применяемые по умолчанию. Рассуждения, которые допускают возможность в отсутствие конкретных знаний принимать по умолчанию общепринятые или общеизвестные знания. ° Аутоэпистемические рассуждения. Самопознание, или рассуждения человека о том, каким ему, например, кажется цвет неба. ° Немонотонные рассуждения. Рассуждения, применяемые в тех условиях, когда ранее полученные знания могут оказаться неправильными после получения нового свидетельства. ° Рассуждения по аналогии. Логический вывод заключения исходя из наличия признаков, подобных признакам другой ситуации. В нейронных сетях рассуждения по аналогии выполняются путем распознавания образов в данных и последующего распространения полученных результатов на новую ситуацию. На рис. 3.14 явно не показан еще один метод рассуждений, в котором используются знания, полученные на основе здравого смысла этот метод представляет собой сочетание всех прочих методов логического вывода и основан на собственном опыте человека. Люди используют рассуждения на основе здравого смысла во многих обычных ситуациях, но задача реализации такого метода формирования рассуждений в компьютерах является очень сложной. Весьма важная попытка. Дедуктивная логика и силлогизмы 213 создать огромную базу данных, содержащую знания, полученные на основе здравого смысла и пригодные для применения в компьютерах, осуществляется Дугом Ленатом (Doug Lenat), начиная с х годов, а к настоящему времени уже созданы практические приложения (http: //www. OpenCyc. org). Эта база данных состоит из многих утверждений и правил, которые могут использоваться для более успешного создания самых разных приложений, начиная с лучшего понимания речи и заканчивая более эффективным построением онтологий. Любопытная особенность этой базы данных состоит в том, что не всегда оправдывается старая поговорка "Чем больше, тем лучше. В следующем сообщении (полученном входе личной переписки по электронной почте) Дуг Ленат объяснил, с чем это связано. Вручную были введены 3 миллиона правил благодаря обобщению и факторизации к настоящему времени мы смогли уменьшить это количество до 1,5 миллиона. Мы пытаемся добиться не максимального увеличения, а максимального уменьшения количества правил. Вином случае мы могли бы легко увеличить это количество так, чтобы правил было, например, больше миллиарда. Рассмотрим 2 типа животных— крысу и верблюда. К крысе относится также правило, что она не является верблюдом. А поскольку нам известно 10 тысяч животных, то мы могли бы написать 100 миллионов правил такого рода. Вместо этого в системе Сус имеется 10 тысячи одно правило линнеевские таксономические отношения плюс одно правило, в котором сказано, что два таксона, применительно к которым неизвестно, что они состоят в отношении genVspec (род/вид), являются непересекающимися. Говоря о "десятках тысяч дополнительных правил, вы фактически ведете речь об одном правиле весьма специального типа, а именно о правиле с определенным уровнем сложности, согласно которому НИ ОДНО из упомянутых выше утверждений (например, что крыса — не верблюд) вообще не может рассматриваться как правило. Количество утверждений в нашей базе знаний составляет всего лишь пару миллионов благодаря тому, что мы пользуемся возможностью избавиться от остальных правил с помощью самого информационного наполнения. Мы НЕ СТРЕМИМСЯ увеличивать количество правил, поскольку из-за этого уменьшилась бы производительность, но если бы мы ХОТЕЛИ, чтобы база знаний стала больше, то могли бы взять за основу 10 тысячи одно из этих (двух миллионов) утверждений в текущей базе знаний и эквивалентно заменить их 100 миллионами правил, которые только внешне кажутся немного менее общими. Это было бы неправильно Глава 3. Методы логического вывода В доказательстве посылки используются в качестве свидетельств, позволяющих доказать истинность заключений. Посылки называют также антецедентами, а заключение — консеквентом. Наиболее важной характерной особенностью дедуктивной логики является то, что из истинных посылок должно следовать истинное заключение. Как показано выше, посылки принято отделять от заключения чертой, поэтому нет необходимости явно указывать, что является посылками и что заключением. Приведенное выше доказательство можно записать более кратко следующим образом Любой, кто умеет составлять программы, интеллектуально развит Джон умеет составлять программы Джон интеллектуально развит В этом доказательстве троеточие (.'.) означает "следовательно. Перейдем к более подробному описанию силлогистической логики. Основное преимущество изучения силлогизмов состоит в том, что это — простая, хорошо изученная область логики, которая может быть полностью доказана. Кроме того, силлогизмы часто бывают полезными потому, что их можно выразить в терминах правил IF- Например, предыдущий силлогизм может быть перефразирован таким образом IF Jlm6oA, кто умеет составлять программы, интеллектуально развит и Джон умеет составлять программы Джон интеллектуально развит Вообще говоря, силлогизмом считается любое действительное дедуктивное доказательство, имеющее две посылки и одно заключение. Классическим счита- Способы применения нечеткой логики для формирования рассуждений на основе здравого смысла рассматриваются в главе 5. Одним из наиболее часто применяемых методов формирования логических выводов является дедуктивная логика, которая с древних времен использовалась для определения обоснованности доказательств. В английском языке аналог слова доказательство) применяется также для описания ожесточенного "обмена мнениями, нов логике это слово имеет совершенно другой смысл. Логическое доказательство — это группа утверждений, в которой последнее рассматривается как обоснованное с использованием предыдущих вцепи рассуждений. Одним из типов логического доказательства является силлогизм, который рассматривался в главе 2. Пример силлогизма приведен ниже. Посылка. Любой, кто умеет составлять программы, интеллектуально развит Посылка. Джон умеет составлять программы Заключение. Следовательно, Джон интеллектуально развит. Дедуктивная логика и силлогизмы 215 ется силлогизм специального типа, называемый категорическим силлогизмом. В |