дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
 Скачать 3.73 Mb.
|
обосновывающих текущую гипотезу Поиск в прямом направлении для определения того, какие решения следуют из фактов Обеспечивает поиск в ширину Поиск определяется антецедентами Обеспечивает поиск в глубину Поиск определяется консеквентами Способствует формированию объяснения Не способствует формированию объяснениякакую цель она пытается выполнить. А система прямого логического вывода не позволяет также легко получить объяснение, поскольку подцели не становятся явно известными до тех пор, пока не будут обнаружены 266 Глава 3. Методы логического вывода Рис. 3.23. Прямой логический вывод Процесс прямого логического вывода называется восходящими рассуждениями, поскольку в нем рассуждения осуществляются от свидетельств нижнего уровня, т.е. фактов, к заключениям верхнего уровня, которые основаны на этих фактах. Процесс формирования восходящих рассуждений в экспертной системе аналогичен обычному восходящему программированию, о котором речь шла в главе В подходе, основанном на знаниях, факты рассматриваются как элементарные единицы знаний, поскольку невозможна их декомпозиция на какие- либо меньшие единицы знаний, имеющие смысл. Например, факт "duck" имеет определенный смысл как существительное (утка) и как глагол (нырять. Но результатом его дальнейшей декомпозиции становятся буквы "d", "u", си, которые не имеют какого-либо конкретного смысла. А в обычных программах основными единицами значения являются данные. Обычно применяется соглашение, в соответствии с которым конструкции высокого уровня, состоящие из конструкций низкого уровня, располагаются в верхней части условной схемы. Поэтому рассуждения, проводимые от таких конструкций высокого уровня, как гипотезы, в направлении вниз, к фактам низкого уровня, позволяющим обосновать гипотезы, называются нисходящими рассуждениями, или обратным логическим выводом. Понятие обратного логического вывода иллюстрируется на рис. 3.24. Для того чтобы доказать или опровергнуть гипотезу Х, необходимо доказать по меньшей мере одну из промежуточных гипотез, Х 3.14. Прямой и обратный логический вывод 267 Н или Нз. Обратите внимание на то, что диаграмма представлена в виде дерева AND — OR, поскольку это позволяет показать, что в некоторых случаях, таких как Н, для обоснования Н должны выполняться все гипотезы низкого уровня. А в других случаях, таких как гипотеза верхнего уровня Н, необходимо доказать только одну гипотезу низкого уровня. При использовании обратного логического вывода в системе обычно предусматривается возможность запрашивать у пользователя дополнительные свидетельства, способствующие доказательству или опровержению гипотез. В этом состоит принципиальное отличие таких систем от систем прямого логического вывода, в которых все относящиеся к делу факты обычно известны заранее. Рис. 3.24. Обратный логический вывод Еще развернувшись к рис. 3.4, приведенному в разделе, можно заметить, что представленная на рисунке сеть решений организована так, что очень хорошо подходит для обратного логического вывода. Гипотезы верхнего уровня представляют различные типы кустарников малины, таких как душистая малина, западная малина, японская малина и обыкновенная малина. Свидетельства, позволяющие обосновать эти гипотезы, показаны ниже. Могут быть легко сформулированы правила, позволяющие идентифицировать любой из видов кустарников малины. В качестве примера можно привести следующее правило Глава 3. Методы логического вывода IF листья — простые душистая ыалина Одним из важных аспектов выявления необходимых дополнительных свидетельств является способность задавать правильные вопросы. Правильными называются такие вопросы, которые способствуют повышению эффективности процесса определения правильного ответа. Для решения этой задачи необходимо выполнить одно очевидное требование, согласно которому экспертная система должна задавать вопросы, касающиеся только тех гипотез, которые она пытается доказать. Безусловно, количество вопросов, которые могут быть заданы системой, исчисляются сотнями или тысячами, нона получение свидетельств, позволяющих отвечать на вопросы, все равно приходится затрачивать время и деньги. Кроме того, накопление свидетельств некоторого типа, таких как результаты медицинских анализов, может представлять собой неприятный и даже, возможно, опасный для пациента процесс (и действительно, трудно представить себе, что какой-то пациент будет испытывать удовольствие от проведения медицинских анализов. В идеальном случае экспертная система должна также позволять пользователю добровольно предлагать дополнительные свидетельства, даже если система их не запрашивает. Предоставление пользователю возможности добровольно вводить дополнительные свидетельства способствует ускорению процесса обратного логического вывода и позволяет сделать систему более удобной для пользователя. Добровольно предоставляемое свидетельство может дать системе возможность пропустить некоторые звенья в причинной цепи или выбрать полностью новый подход. А недостаток рассматриваемого варианта состоит в том, что потребуется создание более сложной программы экспертной системы, поскольку в такой системе необходимо будет предусмотреть возможность пропуска отдельных звеньев цепи. Схемы организации приложений, наиболее подходящих для использования в них прямого и обратного логического вывода, показаны на рис. 3.25. Для упрощения соответствующие диаграммы представлены в виде деревьев, а не сетей общего вида. Наиболее подходящим для прямого логического вывода является такое приложение, схема организации которого имеет вид широкого и не очень глубокого дерева. Это связано с тем, что прямой логический вывод способствует применению поискав ширину. Это означает, что прямой логический вывод является удобным, если поиск заключений выполняется путем последовательного перехода с одного уровня на другой. В отличие от этого, обратный логический вывод способствует применению поискав глубину. А дерево, наиболее подходящее для поискав глубину, является узкими глубоким. Обратите внимание на то, что выбор наиболее подходящего способа поиска решения зависит от структуры правил. Это означает, что эффективность процесса активизации правил зависит от того, какие шаблоны будут применяться для согласования в проектируемом правиле. Шаблоны в левой части правила позво- 3.14. Прямой и обратный логический вывод 269 Рис. Прямой и обратный логический вывод IF А THEN В IF В THEN С ляют определить, может ли правило стать активизированным с помощью фактов. А действия, заданные в правой части правила, определяют, какие факты должны быть введены в базу знаний и удалены из нее, и поэтому влияют на другие правила. Аналогичная ситуация имеет место применительно к обратному логическому выводу, не считая того, что вместо правил используются гипотезы. Безусловно, любая промежуточная гипотеза может представлять собой какое-то правило, при согласовании с которым применяется консеквент, а не антецедент. В качестве очень простого примера рассмотрим следующие правила типа П- THEN: 270 Глава 3. Методы логического вывода IF С THEN D Если дан факт Аи машина логического вывода спроектирована с учетом согласования фактов с антецедентами, тов базу знаний будут введены промежуточные факты В и С, а также заключение Этот процесс соответствует прямому логическому выводу. Такая машина логического вывода представляет собой основу экспертной системы. В отличие от этого, если в базу знаний вводится факт D (который в действительности представляет собой гипотезу, а машина логического вывода согласует факты с консеквентами правил, то полученный результат соответствует обратному логическому выводу. В системах, предназначенных для обратного логического вывода, таких как механизм обратного логического вывода включает широкий набор средств, позволяющих упростить построение обратной цепи, таких как автоматический перебор с возвратами. Обратный логический вывод можно осуществить в системе прямого логического вывода (и наоборот) путем перепроектирования правил. Например, приведенные выше правила для прямого логического вывода можно перезаписать следующим образом IF D THEN С IF СВ В THEN А Теперь факты Си В рассматриваются как подцели или промежуточные гипотезы, которые должны быть выполнены для выполнения гипотезы D. С другой стороны, свидетельство А рассматривается как факт, который обозначает конец процесса выработки подцелей. Если факт А существует, то гипотеза имеет основание и рассматривается согласно этой цепи обратного логического вывода как истинная. Если же факт Ане существует, то гипотеза D не имеет основания и рассматривается как ложная. Одним из затруднений, связанных с использованием данного подхода, является обеспечение эффективности. Система обратного логического вывода способствует применению поискав глубину, а система прямого логического вывода поискав ширину. Безусловно, приложение, требующее обратного логического вывода, можно написать в системе прямого логического вывода и наоборот, но эта система не будет показывать такую эффективность при поиске решения, как более подходящая для этого система. А вторая сложность является концептуальной. Она связана с тем, что знания, выявленные с помощью эксперта, нужно будет модифицировать таким образом, чтобы они соответствовали требованиям машины логического вывода. Например, машина прямого логического вывода согласовывает факты с антецедентами правила машина обратного логического вывода согласовывает факты с консеквентами. Это означает, что если знания эксперта естественным образом подходят для построения обратной цепи, то их придется 3.15. Другие методы логического вывода полностью реструктурировать, чтобы привести к форме, подходящей для использования в режиме прямого логического вывода, и наоборот. 3.15 Другие методы логического вывода В экспертных системах иногда используются некоторые другие типы логического вывода, Безусловно, эти методы не являются столь же универсальными, как дедукция, но иногда бывают очень полезными. Аналогия Еще одним мощным методом логического вывода, кроме дедукции и индукции, является аналогия. Основная идея рассуждений по аналогии состоит в том, чтобы попытаться связать ранее встретившиеся ситуации с новой ситуацией для использования ранее достигнутых результатов в качестве руководства. В процессе своего существования все живые создания проявляют весьма хорошие способности к применению рассуждений по аналогии эти способности являются крайне важными, поскольку количество новых ситуаций, с которыми им приходится сталкиваться в реальном мире, является просто поразительным. Но вместо того, чтобы трактовать каждую новую ситуацию как уникальную, часто бывает полезно попытаться найти аналогии между новой ситуацией и какими-либо старыми, в отношении которых известно, как действовать в этих ситуациях. Рассуждения по аналогии тесно связаны с индуктивными рассуждениями. Но индукция предусматривает проведение в определенной ситуации логического вывода от частного к общему, а проведение аналогии в той же ситуации связано с попыткой формирования логических выводов с учетом ситуаций, которые не являются точно такими же, как новая. Рассуждения по аналогии не позволяют получать такие формальные доказательства, которые создаются с помощью дедукции. Вместо этого рассуждения по аналогии представляют собой эвристическое инструментальное средство формирования рассуждений, которое иногда позволяет выполнить необходимую работу. Вообще говоря, такие рассуждения служат основным инструментальным средством формирования рассуждений на основе прецедентов в судебных доказательствах и медицинской диагностике. Одним из примеров рассуждений по аналогии является медицинская диагностика. После того как пациент приходит на прием к врачу обнаружив какие-то проблемы со здоровьем, врач получает от него необходимую информацию и регистрирует симптомы наблюдаемой проблемы. Если эти симптомы идентичны или в значительной степени аналогичны наблюдавшимся у других людей с заболеванием Х, врач может вывести по аналогии, что поступивший к нему пациент имеет заболевание Х. Рассуждения по аналогии — это наименее дорогостоящий способ формирования рассуждений Глава 3. Методы логического вывода 6 1 8 7 5 3 2 9 4 Это типичный магический квадрат, поскольку в нем сумма значений по строкам, столбцами диагоналям является постоянной. Доску для игры в крестики- нолики, заполненную значениями чисел из магического квадрата, можно рассматривать как аналогию для игры в 15. После того как игрок начнет рассматривать игру в 15 в терминах игры в крестики-нолики и применит показанную стратегию выигрыша к игре введение последней становится очень простым. Данный конкретный магический квадрат называется стандартным квадратом третьего порядка. Термин порядок обозначает количество строк или столбцов в квадрате. Существует только один уникальный квадрат третьего порядка. Путем вращения или создания зеркального отображения по отношению к стандартному квадрату могут быть созданы другие магические квадраты. Еще один Обратите внимание на то, что полученный таким путем диагноз не является результатом дедуктивного вывода, поскольку каждый пациент является уникальным. Лишь то, что осмотр какого-то другого пациента с таким же заболеванием позволяет выявить некоторые симптомы, отнюдь не означает, что данный пациент стем же заболеванием покажет наличие у него таких же симптомов. Вместо этого врач принимает предположение, что обнаруженные у текущего пациента симптомы позволяют провести аналогию между ними лицом с подобными симптомами и с известным заболеванием. Этот начальный диагноз представляет собой гипотезу, которая может быть либо доказана, либо опровергнута с помощью медицинских анализов. Но крайне важно иметь начальную рабочую гипотезу, поскольку именно она позволяет свести весь перечень, состоящий из тысяч потенциальных заболеваний, к одному или нескольким заболеваниям. Если бы врач решил начать свое обследование с выписки направлений на всевозможные медицинские анализы, не выдвинув начальной гипотезы, то такое решение было бы просто невыполнимым из-за слишком высоких затрат денег и времени. В качестве примера того, какими полезными могут быть рассуждения по аналогии, предположим, что два человека ведут между собой игру, называемую игрой в 15. Эти игроки по очереди выбирают число от 1 до 9, руководствуясь таким ограничением, что одно и тоже число не может использоваться дважды. Побеждает тот, кто первым сумеет получить сумму выбранных цифр, равную 15. Безусловно, на первый взгляд может показаться, что это — очень сложная игра, для победы в которой необходимо хорошо подумать, но благодаря аналогии ее можно превратить в игру, ведение которой становится очень несложным. Рассмотрим следующую приведенную ниже доску для игры в крестики-нолики, в которой в каждую клетку вписаны числа, как показано схематически на доске. Другие методы логического вывода 273 способ создания магического квадрата на основе других магических квадратов состоит в добавлении одной и той же числовой константы к значению в каждой клетке исходного квадрата. Знание этой информации позволяет также логическим путем определить стратегии выигрыша для игры в 18, в которой числа должны выбираться из следующего множества 2,3,4,5,6, 7,8,9, 10) или для игры в 21, в которой используется такое множество, 10, Ц Теперь мы можем воспользоваться индукцией для вывода логическим путем стратегии выигрыша для игры в 15 + ЗЮ, где N — любое натуральное число 1, 2, рассматривая эту игру как аналогичную игре на доске для игры в крестики-нолики, которая, в свою очередь, связана аналогией с магический квадратом, состоящим из следующих значений (1+ N,2+ З+ N,4+ N,5+ N,6+ N,7+ N,8+ N,9+ N) Используя аналогию, согласно которой квадрат третьего порядка можно применять для ведения игр стремя ходами, по индукции можно прийти к логическому выводу, что для ведения игр, входе которых должно быть сделано больше трех ходов, можно использовать магические квадраты более высокого порядка. Например, приведенный ниже магический квадрат четвертого порядка 4 позволяет найти стратегию выигрыша для четырехходовой игры в 34, рассматривая эту игру в терминах игры в крестики-нолики. 16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1 Нов отличие оттого, что количество стандартных квадратов третьего порядка равно 1, количество стандартных квадратов четвертого порядка равно 880, а это позволяет вести значительно больше непохожих друг на друга игр. Рассуждения по аналогии составляют важную часть рассуждений на основе здравого смысла, а задача проведения таких рассуждений является очень сложной для компьютеров (и детей. Другими приложениями, в которых широко применяются рассуждения по аналогии, стали учебные программы Глава 3. Методы логического вывода Метод формирования и проверки Еще одним методом логического вывода является классическая стратегия формирования и проверки, применяемая в искусственном интеллекте, которую иногда называют выработкой и проверкой. Применение данного метода предусматривает формирование вероятного решения и последующую его проверку для определения того, соответствует ли предложенное решение всем требованиям. Если решение является удовлетворительным, работа прекращается, в противном случае формируется новое решение, которое опять проверяется, и т.д. Этот метод использовался впервой экспертной системе, DENDRAL, проект которой был задуман в году для содействия в определении структур органических молекул. С помощью массового спектрометра подготавливались |