дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
 Скачать 3.73 Mb.
|
Ожидаемый выигрыш в узле А 350 000 долларов = (673 долларов) (0.52) — (О долларов) (0.48) В узле действия Е необходимо сделать выбор между ожидаемым выигрышем для того случая, когда поиск нефти прекращается ( — долларов, и ожидаемым выигрышем, достигаемым в случае проведения бурения (846153 доллара. Поскольку значение 846 153 долларов больше чем — 50 000 долларов, можно прийти к логическому выводу, что это — лучший способ действий, и записать полученный выигрыш рядом с узлом Е. Путь, ведущий к узлу, в котором происходит прекращение дальнейших действий, отсекается, или исключается. Для этого поперек этого пути проставляется символ =, указывающий, что дальнейшее его изучение проводиться не будет (рис. 4.12). Аналогичным образом, в узле действия D выбор наилучшего способа действий сводится к сравнению значений ожидаемого выигрыша, равных — 50000 долларов и — 500000 долларов, что влечет за собой выбор значения — 50 000 долларов, и это значение записывается рядом с узлом D. 334 Глава 4. Рассуждения в условиях неопределенности Ни один из путей, ведущих из узла Ане отсекается, поскольку уже было решено выполнить сейсмическое исследование. Чтобы принять решение по проведению сейсмического исследования, потребовалось бы развернуть дерево решений в обратном направлении перед узлом А. Следует учитывать, что при проведении обратной индукции рассуждения проводятся против хода времени, для того чтобы действия, намеченные на будущее, были оптимальными. В таблице выигрышей (см. табл) данным конкретным вариантам соответствует тривиальное решение, которое должна была бы принять геологоразведывательная компания в отношении узла действия, поскольку ожидаемый выигрыш составляет 0 долларов. Нона этом этапе в игру вступают отвага, удача и опыт. Специалисты геологоразведывательной компании должны просто доверять своему чутью и принять в узле D решение о разведывательном бурении, несмотря на отрицательные результаты сейсмических исследований и на значительный шанс отсутствия нефти. Иногда в подобных случаях компания выигрывает, а иногда проигрывает. Нов таких ситуациях важно помнить одну мудрую рекомендацию — всегда ставьте на кон не свои деньги, а чужие По мере повышения шансов на получение ожидаемого выигрыша в результате успешного бурения нефтяной скважины возрастают и значения выигрышей в узлах В и D. Например, если перспективная нефтяная скважина принесет выигрыш в долларов вместо 1000000 долларов, ожидаемый выигрыш в узлах В и D составит 62500 долларов, а это все еще меньше стоимости осуществления решения пробурить скважину, равной 200000 долларов, но гораздо лучше по сравнению с предыдущим ожидаемым выигрышем, который составлял долларов. Тем самым подтверждается правило, основанное на здравом смысле, согласно которому, чем больше приходится за что-то платить, тем больше выигрыш, который может быть получен в обмен на эти расходы. Но следует отметить, что даже если бы цена на нефть достигла миллиардов долларов, риски, связанные с существующими вероятностями, оставались бы теми же. (Изменяется только выигрыш, но, как знают многие "великие комбинаторы, кто не рискует, тот не пьет шампанское.) Рассматриваемое дерево решений представляет собой пример гипотетических рассуждений, или ситуаций, в которых важную роль играют вопросы "что, если. Исследуя альтернативные способы действий, мы можем отсекать путине ведущие к оптимальным выигрышам. В инструментальных средствах экспертных систем ив байесовском программном обеспечении некоторых типов предусмотрены развитые механизмы проведения гипотетических рассуждений и исключения бесперспективных путей. Дополнительные сведения приведены в разделе "Программные ресурсы" приложения Ж. В частности, в настоящее время можно легко найти бесплатные или коммерческие байесовские инструментальные средства, позволяющие без особого труда строить в графической форме байесовские и вероятностные деревья и проводить сними эксперименты в различных сценариях поиска ответов на вопросы "что, если. Очень развитые способы, обеспечиваю 4.10. Временные рассуждения и марковские цепи 335 щие проведение расчетов в условиях неопределенности, предусмотрены в таких электронных таблицах, как Microsoft Excel, а проведение поискав позволяет найти много макрокоманд, еще более превосходящих возможности встроенных функций для работы с классическими вероятностями и статистическими показателями, которые входят в состав Excel. Кроме того, удобные графические средства электронных таблиц позволяют легко представлять визуально сложные данные. Дерево решений, приведенное на рис. показывает оптимальную стратегию для геологоразведывательной компании. Если результаты сейсмических исследований являются положительными, тов рассматриваемом районе должно быть проведено бурение, а если результаты сейсмических исследований отрицательны, то район необходимо покинуть. Безусловно, этот пример байесовского принятия решений является очень простым, но он показывает, какого типа рассуждения применяются в условиях неопределенности. В более сложных случаях, например, касающихся принятия решения о проведении сейсмических исследований, деревья решений могут намного увеличиваться Временные рассуждения и марковские цепи Рассуждения о событиях, зависящих от времени, называются временными рассуждениями. Люди проводят такие рассуждения довольно легко. Но временные события трудно формализовать так, чтобы временные логические выводы мог выполнять компьютер. Вместе стем экспертные системы, способные рассуждать о таких временных событиях, которые, например, связаны с управлением воздушным движением, могли бы принести большую пользу. Экспертные системы, проводящие свои рассуждения во времени, были разработаны в медицине. К ним относится система VM, предназначенная для управления вентиляторами, устанавливаемыми в масках пациентов, чтобы им было легче дышать. К числу других систем относится система CASNET, предназначенная для лечения глаукомы, и система, предоставляющая консультации по применению терапевтических средств на основе наперстянки при лечении больных с сердечными заболеваниями. Все медицинские системы, кроме VM, перечисленные выше, предназначены для решения гораздо более легкой задачи проведения временных рассуждений по сравнению с системой управления воздушным движением, которая должна действовать в реальном времени. Большинство экспертных систем не могут функционировать в реальном времени, поскольку этого не позволяет проект машины логического вывода, к тому же требуется большой объем обрабатывающих мощностей. Задача создания экспертной системы, выполняющей значительное количество этапов временных логических рассуждений для исследования много 336 Глава 4. Рассуждения в условиях неопределенности Будущее 1 2 S1 Р Р Настоящее S2 Р Р Например, предположим, что только Ы из тех, кто в настоящее время использует жесткие диски модели Х, купят еще один жесткий диск модели Х, когда это потребуется. Кроме того, Ы из тех, кто в настоящее время не использует модели Х, купят жесткий диск модели Х, когда им потребуется новый жесткий диск (единственным достоинством модели Х является хорошая реклама. Какое количество людей купят жесткий диск модели Х в течение продолжительного периода времени Ниже показана матрица переходов, Т, в которой сумма чисел в каждой строке должна быть равна 1. Х Х' Х 0.1 0.9 Т Х' 0.6 0.4 численных гипотез в реальном времени, является слишком сложной. Тем не менее на основе различных множеств аксиом разработано много вариантов временных логик. Различия между разными теориями определяются тем, какой способ применяется для поиска ответов на определенные вопросы. Имеет ли время начало и конец Протекает ли время непрерывно или дискретно Можно ли считать, что прошлое только одно, а возможных вариантов будущего много Формулировка различных ответов на эти вопросы приводит к разработке различных видов логики. Временная логика применяется также в обычных программах, например, для порождения и синхронизации параллельных процессов в программах. Еще один подход к организации рассуждений во времени состоит в использовании вероятностей. Система, переходящая из одного состояния в другое, может рассматриваться как развивающаяся во времени. Такая система может представлять любые вероятностные явления, такие как изменение ценна акции, распределение голосов избирателей, погодные явления, процессы, происходящие в деловом мире, развитие заболеваний, функционирование оборудования, генетические изменения и т.д. Если процесс перехода системы через последовательность состояний является вероятностным, то он рассматривается как стохастический процесс. Стохастический процесс удобно представлять в форме матрицы переходов. В простом случае с двумя состояниями, S1 и S2, матрица переходов может быть представлена в следующей форме, где Р„— вероятность перехода из состояния т в состояние и 337 4.10. Временные рассуждения и марковские цепи Вектор, компоненты которого не являются отрицательными ив сумме составляют 1, называется вектором вероятностей. Определению вектора вероятностей соответствует каждая строка матрицы Т. Один из способов интерпретации матрицы переходов состоит в использовании диаграммы состояний, как показано на рис. Обратите внимание на то, что вероятность системы остаться в состоянии Х равна 0.1, вероятность остаться в состоянии Х' равна 0.4, вероятность перейти из состояния Х в состояние Х' равна 0.9, а вероятность перейти из состояния Х' в состояние Х равна 0.6. Рис. 4.13. Интерпретация матрицы переходов с помощью диаграммы состояний Вначале примем предположение, что жесткий диск модели Х установлен в компьютерах Ъ пользователей. На риса показано дерево вероятностей для нескольких переходов между состояниями, в котором состояния обозначены номером состояния и приведена используемая модель жесткого диска Обратите внимание на то, как быстро начинает расти дерево. А если бы количество переходов достигло 10, то количество ветвей в дереве увеличилось бы до О = Альтернативный способ изображения этого дерева состоит в том, что оно может быть представлено в виде решетки, как показано на рис. 4.14, б. Преимущество представления в виде решетки состоит в том, что в нем не требуется так много связей, соединяющих состояния. Вероятность пребывания системы в определенном состоянии может быть выражена с помощью следующей однострочной матрицы, называемой матрицей состоянии, в которои Р + Р + + Р = 1: 1 Р ь] Первоначально, когда жесткие диски модели Х установлены в компьютерах Ъ пользователей, матрица состояний имеет такой вид 0.8 0.2 Ас течением времени числа в этой матрице изменяются в зависимости оттого, какие модели жестких дисков покупают пользователи Глава 4. Рассуждения в условиях неопределенности 338 Для того чтобы рассчитать в состоянии 2 количество пользователей, имеющих жесткий диск модели Хине имеющих жесткий диск модели Х, достаточно умножить матрицу состояний на матрицу переходов с использованием обычных правил умножения матриц, следующим образом , =1 Выполнение этой операции приводит к получению таких результатов 0.8 0.2 = [(0.8)(0.1) + (0.2)(0.6) (0.8)(0.9) + (0.2)(0.4)] = 0.2 0.8 Умножение матрицы, соответствующей второму состоянию, на матрицу переходов позволяет получить следующие результаты з = Ж 0.8 з = 0 5 0.5 S4 = з 0.57 0.5 S4 = 0.35 0.65 Матрицы, соответствующие следующим состояниям, приведены ниже 0.575 Sg = 0.3875 0.6125 Sy = 0.40625 0.59375 0.396875 0.602125 А умножение полученной матрицы, соответствующей третьему состоянию, на матрицу переходов дает такие результаты 339 4.10. Временные рассуждения и марковские цепи Рис. Диаграммы переходов между состояниями во времени, имеющие вид дерева и решетки Следует отметить, что эти матрицы состояний сходятся к следующей матрице, называемой матрицей установившихся состояний 0.4 0.6 Систему, находящуюся в установившемся состоянии, принято называть находящейся в равновесии, поскольку система не изменяется. Любопытно отметить, что значения в матрице установившихся состояний не зависят от начального состояния. Даже если бы использовался какой-то другой начальный вектор вероятностей, значения в установившемся состоянии были бы теми же самыми. Глава 4. Рассуждения в условиях неопределенности 340 Вектор вероятностей S представляет собой матрицу установившихся состояний для матрицы переходов Т, если справедливо следующее соотношение (1) S =ST Если Т — обычная матрица переходов (таковой называется матрица, имеющая определенную степень и содержащая только положительные элементы, то существует единственное установившееся состояние S. Тот факт, что элементы матрицы переходов являются положительными, означает, что в какой-то момент времени возможен переход системы в определенное состояние, независимо оттого, каковым является начальное состояние. Таким образом, потенциально достижимо любое состояние. Процесс в марковской цепи определен как имеющий перечисленные ниже характеристики. 1. Процесс имеет конечное количество возможных состояний. 2. Процесс может одновременно находиться водном и только одном состоянии. Процесс со временем последовательно переходит, или трансформируется из одного состояния в другое. 4. Вероятность перехода в некоторое состояние зависит только от непосредственно предшествующего состояния. Например, предположим, что дано конечное множество состояний (А, В, С, E, F, С, Н, I). В таком случае, если следующим состоянием, в которое переходит процесс из состояния Н, является I, то условная вероятность определяется таким выражением P(I Н HnGnFnEnDnCnBnA) Х УХУ Выполнение операции умножения в левой части и приравнивание полученных элементов соответствующим элементам в правой части приводит к получению Обратите внимание на то, насколько диаграмма в виде решетки, представленная на рис. 4.14, б, напоминает цепь. Рассматриваемый случай с покупкой жестких дисков представляет собой процесс в марковской цепи, поэтому матрица установившихся состояний может быть определена путем применения уравнения (1). Примем за основу некоторый произвольный вектор S с компонентами Хи У и применим к нему уравнение (1) следующим образом. Анализ вероятностных систем на основе понятий шансов следующей зависимой системы уравнений Х+ УХ Х + У = У Решение этой системы уравнений для Х в зависимости от У приводит к получению таких результатов Х= У= — У 0.6 2 0.9 3 Чтобы полностью найти решение для Хи У, воспользуемся тем фактом, что сумма вероятностей равна Таким образом, Х+У =1 Это означает, что 2 Х — У — У 3 и поэтому 2 3 Х — У 5 5 Таким образом, матрица установившихся состояний принимает следующий вид, т.е. действительно совпадает с матрицей, полученной в конечном итоге в результате сходящихся вычислений с использованием значений, принятых в качестве гипотетических 0.4 0.6 Анализ вероятностных систем на основе понятий шансов и убеждений До сих пор вероятности рассматривались как показатели, применяемые для анализа повторяющихся событий в идеальных системах. Но люди проявляют необычайные способности при вычислении вероятностей многих неповторяющихся событий, например, происходящих при медицинской диагностике и разведке полезных ископаемых, когда любой пациент и любое месторождение являются уникальными. Для того чтобы обеспечить возможность использования экспертных систем в подобных областях, необходимо расширить понятие события и распространить его на высказывания (таковыми являются утверждения, которые могут быть истинными или ложными. Например, в качестве события может рассматриваться следующее высказывание Глава 4. Рассуждения в условиях неопределенности "Кожа пациента покрыта красныыи пятнаыи" а также такое высказывание Р(А В) Вместо этого выражение Р(А В) может интерпретироваться как степень доверия к тому, что А истинно, если дано В. Если Р(А В) = 1, мы уверены в том, что выражение А действительно истинно, если же Р(А ВО, то мы уверены в том, что А действительно ложно, а все другие значения, ОРАВ, означают, что мы не совсем уверены в истинности или ложности А. Для обозначения некоторых высказываний, истинность или ложность которых невозможно установить с полной уверенностью на основании некоторого свидетельства, применяется термин гипотеза, взятый из статистики. В таком случае условная вероятность рассматривается как правдоподобие. Например, значение Р(Н Е) выражает правдоподобие некоторой гипотезы, Н, определяемое на основании некоторого свидетельства, Е. Безусловно, выражение Р(Н Е) имеет такую же форму, как и выражение для условной вероятности, но фактически обозначает нечто иное — правдоподобие, или степень доверия. Понятие вероятности распространяется на повторяющиеся события, а понятие правдоподобия выражает степень доверия к тому, что произойдут неповторяющиеся события. Экспертные системы моделируют работу экспертов-людей, поэтому выражение Р(Н Е, вообще говоря, представляет степень доверия эксперта, согласно которой некоторая гипотеза, Н, является истинной, если дано некоторое свидетельство, Е. Безусловно, если бы события были повторяемыми, то выражение Р(Н Е) представляло бы просто вероятность. Если мы согласимся стем, что выражение Р(Н Е) обозначает правдоподобие, или степень доверия, то что показывает некоторое значение этого выражения, такое как 5010 или 95 Например, предположим, вы на 95 уверены в том, что двигатель вашего автомобиля в следующий раз запустится. Один из способов интерпретации этого правдоподобия состоит в использовании понятия шансов выигрыша ставки. Шансы odds выигрыша А против В, если дано некоторое событие С, определяются следующим образом РАС) Р(В I СУ пациента — корь" Предположим, что А — высказывание. В таком случае приведенное ниже выражение для условной вероятности может необязательно соответствовать определению вероятности в классическом смысле, если события и высказывания не могут повторяться или иметь математическое обоснование 4.11. Анализ вероятностных систем на основе понятий шансов. Если В = А, то выражение РАС) РАС) РАС РАС) определяет следующее Р=Р(А |