Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 196
Текст из файла (страница 196)
в) Запишите распределение условных вероятностей Р)М, ~ М) для случая, где Ме 11, 2, 3 ) и М,е 10, 1, 2, 3, 4) . Каждая запись в распределении условных вероятностей должна быть представлена как функция от параметров е и/или Е. г) Примите предположение, что М,=1 и м;-3. Каково возможное количество звезд, если предполагается, что на значения и не налагаются априорные ограничения? д) Каково наиболее вероятное количество звезд, если даны эти наблюдения? Объясните, как рассчитать эту вероятность, или, если ее невозможно рассчитать, объясните, какая требуется дополнительная информация и как она повлияет на результат.
14.4. Рассмотрите сеть, показанную на рис. 14.13, б; примите предположение, что два телескопа лают идентичные результаты, )ье ( 1, 2, 3 ) и м„, М,е ( О, 1, 2, 3, 4 ), а также, что применяются такие символические таблицы СРТ, как описано в упр. 14.3. Используя алгоритм перебора, рассчитайте распределение вероятностей Р(М~Мд — — 2, Ма=2) . в) а) Рис. 74. 73. Три возможные сети для задачи с телескопом 14.5.
Рассмотрите семейство линейных гауссовых сетей, которое показано на с. 672. а) Допустим, что в сети с двумя переменными переменная Х, является родительской по отношению к переменной Х„переменная х, имеет гауссово распределение априорных вероятностей, а Р (Х, ~ Х„) — линейное гауссово распределение.
Покажите, что совместное распределение Р(х,,х,) представляет собой многомерное гауссово распределение, и рассчитайте его матрицу ковариации. б) Докажите по индукции, что совместное распределение для линейной гауссовой сети общего вида по переменным х,, ..., х„также является многомерным гауссовым распределением. 14.6. Пробит-распределение, описанное на с. 674, позволяет представить распределение вероятностей для булевой дочерней переменной, если задана одна непрерывная родительская переменная. Глава 14. Вероятностные рассуждения 715 а) Как можно расширить это определение, чтобы оно охватывало несколько непрерывных родительских переменных? б) Как оно может быть расширено с учетом многозначной дочерней переменной? Рассмотрите и те случаи, в которых значения дочерней переменной упорядочены (как при выборе во время вождения автомобиля передачи в зависимости от скорости, крутизны подъема, требуемого ускорения и т.д.), и те случаи, в которых они не упорядочены (как при выборе для проезда на работу или автобуса, или электропоезда, или автомобиля).
(Подсказка. Рассмотрите способы распределения возможных значений по двум множествам для имитации булевой переменной.) 14.7. В этом упражнении речь идет об алгоритме устранения переменной, приведенном в листинге 14.2. а) В разделе !4.4 алгоритм устранения переменной применялся к следующему запросу: Р(яигязагу1,голлса11з=егие,маеуса11з=егие) Проведите указанные вычисления и проверьте правильность ответа. б) Подсчитайте количество выполненных арифметических операций и сравните его с количеством операций, выполняемых в алгоритме перебора. в) Предположим, что сеть имеет форму цепи — последовательности булевых переменных Х,, ..., Х„, где Рахепея(Х,) =(Х,,) для 4=2, ..., п. Какова сложность вычисления выражения я (х, (х„= сг зе! с использованием алгоритма перебора? С использованием алгоритма устранения переменной? г) Докажите, что сложность применения алгоритма устранения переменной в сети, имеющей форму полидерева, линейно зависит от размера дерева при любом упорядочении переменных, согласованном со структурой сети.
14.8. Проведите исследование сложности точного вывода в байесовских сетях общего вида. а) Докажите, что любую задачу 3-ЯАТ можно свести к задаче точного вывода в байесовской сети, сформированной для представления данной конкретной задачи, и поэтому такой точный вывод является (чР-трудным. (Подсказка. Рассмотрите сеть с одной переменной для каждого пропозиционального символа, с одной для каждого выражения и с одной для конъюнкции выражений.) б) Проблема подсчета количества выполняющих присваиваний для задачи 3-ЯАТ является Л Р-полной (шарп-, или диез-Р-полной). Покажите, что задача точного вывода является, по меныпей мере, такой же трудной, как эта.
14.9. Рассмотрите задачу формирования случайной выборки из заданного распределения по одной переменной. Вы можете принять предположение, что в вашем распоряжении имеется генератор случайных чисел, который возвращает случайное число с равномерным распределением в интервале от О до 1. а) Допустим, что х — дискретная переменная с Р(х=х,) =р, для уя (1, ..., й). ск Кумулятивиое распределение (спшп1аг(хе сйзгпЬпг(оп) х задает вероятность того, что хя (х,, ..., х,) для каждого возможного т'. Объясните, как рассчитать это кумулятивное распределение за время 716 Часть Ч.
Неопределенные знания и рассуждения в условиях неопределенности О( й) и как получить из него одну выборку х. Может ли последняя операция быть выполнена за время меньше 0 ((с)? б) Теперь предположим, что необходимо сформировать ((( выборок к, где дь>(с Объясните, как выполнить эту операцию с ожидаемым временем прогона в расчете на выборку, которое является постоянным (т.е. независимым от й). в) После этого рассмотрим непрерывную переменную с параметризованным (например, с гауссовым) распределением. Как можно формировать выборки с помошью такого распределения? г) Предположим, что необходимо сформулировать запрос, касающийся непрерывной переменной, и что лля вероятностного вывода используется такой алгоритм, как Ы(се?1(зооЖеуд(зсупд.
Как вы модифицировали бы процесс поиска ответов на такие запросы? 14.10. Марковское покрытие переменной определено на с. 669. а) Докажите, что переменная является независимой от всех других переменных в сети, если дано ее марковское покрытие. б) Выведите уравнение 14.11. 14.11. Рассмотрите запрос и (паул ~ Брюхо(с1ек= ские, гуесдказв= ские) к байе- совской сети, приведенной на рис. 14.9, а, и покажите, как можно получить на него ответ с помощью алгоритма МСМС. а) Какое количество состояний имеет эта цепь Маркова? б) Рассчитайте матрицу переходов О, содержащую значение д(у — ~у') для всех у, у'. в) Что представляет собой 0', квадрат матрицы переходов? г) А что можно сказать о выражении 0", где и — э ? д) Объясните, как следует выполнять вероятностный вывод в байесовских сетях, при условии, что доступно выражение (7".
Является ли такой способ вероятностного вывода практически применимым? 14.12. ЙЬ Три футбольные команды, л, и и с, играют друг с другом по одному разу. Каждый матч проводится между двумя командами и может закончиться для команды выигрышем, ничьей или проигрышем. Каждой команде присвоена постоянная, неизвестная оценка ее класса (целое число в лиапазоне от О до 3), и результат матча оценивается вероятностной зависимостью от разницы в классе между двумя участвуюшими командами.
а) Сформируйте реляционную вероятностную модель для описания этой проблемной области и предложите реальные числовые значения для всех необходимых распределений вероятностей. б) Сформируйте эквивалентную байесовскую сеть. в) Примите предположение, что в первых двух матчах команда л побеждает в и играет вничью с С. Используя выбранный вами алгоритм точного вывода, вычислите распределение апостериорных вероятностей для результатов третьего матча.
Глава 14. Вероятностные рассуждения 717 г) Предположим, что в этой футбольной лиге и команд и известны результа- ты всех матчей, кроме последнего. Как сложность предсказания результа- тов последней игры зависит от п? Рассмотрите возможность применения алгоритма МСМС для решения этой задачи. Насколько быстро этот алгоритм сходится на практике и на- сколько хорошо он масштабируется? В данной главе предпринимается попытка истолковать настоя- щее, понять прошлое, а также, возможно, предсказать будущее, даже если пока лишь немногое полностью ясно. Агенты, действующие в неопределенных вариантах среды, должны быть способны следить за текущим состоянием среды; это требование аналогично тому, которое предъявляется к логическим агентам.
Указанная задача в значительной степени усложняется из-за наличия частичных и зашумленных результатов восприятия, а также из-за неопределенности в отношении того, как среда изменяется во времени. В лучшем случае агент будет способен получить только вероятностную оценку текушей ситуации. В этой главе описаны способы представления и алгоритмы вероятностного вывода, благодаря которым такая оценка становится возможной, на основе идей, представленных в главе 14.
Базовый подход описан в разделе 15.1: изменяющийся мир моделируется с использованием случайных переменных, обозначающих каждый аспект состояния мира в каждый момент времени. Отношения между этими переменными описывают, как развивается данное состояние. В разделе 15.2 определены основные задачи вероятностного вывода и описана обшая структура алгоритмов вероятностного вывода для временных моделей. Затем рассматриваются три конкретных типа моделей: скрытые марковские модели, фильтры Калмана и динамические байесовские сети (которые включают скрытые марковские модели и фильтры Калмана в качестве частных случаев). Наконец, в разделе 15.6 показано, благодаря чему временные вероятностные модели образуют ядро современных систем распознавания речи. Центральную роль в создании всех этих моделей играет обучение, но подробное исследование алгоритмов обучения будет отложено до части Ч1.
719 Глава ! 5. Вероятностные рассуждения во времени 15.1. ВРЕМЯ И НЕОПРЕДЕЛЕННОСТЬ В предыдугдих главах методы вероятностных рассуждений рассматривались в контексте статических миров, в которых каждая случайная переменная имеет одно фиксированное значение. Например, в ходе ремонта автомобиля предполагается, что неисправный узел остается неисправным на протяжении всего процесса диагностики; наша задача состоит в вероятностном выводе информации о состоянии автомобиля из наблюдаемых свидетельств, которые также остаются фиксированными. Теперь обратимся к несколько другой задаче — лечение больного диабетом. Как и в случае ремонта автомобиля, в нашем распоряжении имеются факты, такие как последние дозы приема инсулина, рацион питания, результаты измерения количества сахара в крови и другие физические симптомы.
Задача состоит в том, чтобы оценить текуШее состояние пациента, включая фактический уровень сахара в крови и уровень инсулина. При наличии такой информации врач (или больной) принимает решение о рационе питания больного и дозе инсулина. Но в отличие от случая с ремонтом автомобиля теперь становятся сушественными динамические аспекты задачи. Значения уровня сахара в крови и результаты их измерения могут резко изменяться во времени, в зависимости от последнего приема пиши больным и доз инсулина, от интенсивности обмена вешеств в организме, времени суток и т.д.
Чтобы оценить текушее состояние больного по хронологии накопленных фактов и предсказать результаты терапевтических действий, необходимо моделировать эти изменения. Точно такие же соображения возникают во многих других контекстах, начиная от слежения за экономической активностью определенного государства по приблизительным и частичным статистическим паиным и заканчивая пониманием последовательности слов устной речи по зашумленным и неоднозначным результатам акустических измерений. Возникает вопрос: как можно промоделировать подобные динамические ситуации? Состояния и наблюдения Основной подход, который булет принят в этой главе, основан на идеях, аналогичных идеям ситуационного исчисления, как описано в главе!О: процесс изменения может рассматриваться как ряд снимков, каждый из которых описывает состояние мира в данный конкретный момент времени. Каждый снимок, или 'в. временной срез, содержит множество случайных переменных, причем одна часть из них является наблюдаемой, а другая — нет, Для упрощения будем предполагать, что в каждом временном срезе является наблюдаемым одно и то же подмножество переменных (хотя такое требование не является строго необходимым во всем последуюшем изложении).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
