УПРАЖНЕНИЯ
14.1. Рассмотрите сеть для диагностики автомобиля, показанную на рис. 14.12.
а) Дополните сеть булевыми переменными icyWeather (Морозная погода)
и StarterMotor (Стартер).
б) Приведите приемлемые таблицы условных вероятностей для всех вер-
шин.
в) Сколько независимых значений содержится в совместном распределении
вероятностей для восьми булевых вершин, если исходить из предположе-
ния, что неизвестны какие-либо отношения условной независимости,
которые бы их связывали?
г) Какое количество независимых вероятностных значений содержится в
таблицах вашей сети?
д) Условное распределение для вершины Starts (Запускается) может быть
описано как распределение зашумленного AND. Дайте общее определение
этого семейства распределений и покажите его связь с распределениями
зашумленного OR.
14.2. Допустим, что вы живете рядом с атомной электростанцией, в которой преду-
смотрена тревожная сигнализация, срабатывающая, если показания датчика
температуры превышают некоторое пороговое значение. Датчик измеряет
температуру в реакторе. Рассмотрите булевы переменные А (звучит тревожный
сигнал), FA (тревожная сигнализация неисправна) и FG (неисправен датчик), а
также многозначные вершины G (показания датчика) и т (фактическая темпе-
ратура в реакторе).
а) Нарисуйте байесовскую сеть для этой проблемной области с учетом того,
что вероятность отказа датчика повышается, если температура в реакторе становится слишком высокой.
б) Является ли ваша сеть полидеревом?
в) Примите предположение, что есть только два значения фактической и
измеряемой температур — нормальная и высокая; вероятность того, что
датчик сообщает правильную температуру, равна х, когда он работает,
а если не исправен, равна у. Приведите таблицу условных вероятностей,
связанную с вершиной G.
г) Примите предположение, что тревожная сигнализация действует пра-
вильно, при условии, что она не вышла из строя; в последнем случае тре-
вожный сигнал никогда не звучит. Приведите таблицу условных вероят-
ностей, связанную с вершиной А.
д) Примите предположение, что тревожная сигнализация и датчик исправ-
ны и что тревожный сигнал звучит. Вычислите выражение для вероятно-
сти того, что температура в реакторе слишком высока, в терминах раз-
личных условных вероятностей в данной сети.
14.3. Два астронома в различных частях Земли провели измерения, Мг и М2, количе-
ства звезд, N, в некотором небольшом регионе неба с помощью своих
телескопов. Обычно вероятность ошибки е на одну звезду в большую или
меньшую сторону при подсчете этого количества не очень велика. Каждый телескоп может также оказаться (с гораздо меньшей вероятностью f) сильно
расфокусированным (события Fx и F2), и в этом случае ученый не досчитается
трех или большего количества звезд (или, если N меньше 3, вообще не обнаружит ни одной звезды). Рассмотрите эти три сети, показанные на рис. 14.13.
а) Какая из этих трех байесовских сетей может служить правильным (но не обязательно эффективным) представлением приведенной выше информации?
б) Какая из этих сетей является самой лучшей? Объясните, почему.
в) Запишите распределение условных вероятностей P(M1\N) для случая, где
№{1,2,3} и Mxe {0,1,2,3,4}. Каждая запись в распределении условных вероятностей должна быть представлена как функция от параметров
е и/или f.
г) Примите предположение, что M±=l и м2=3. Каково возможное количество
звезд, если предполагается, что на значения N не налагаются априорные
ограничения?
д) Каково наиболее вероятное количество звезд, если даны эти наблюдения? Объясните, как рассчитать эту вероятность, или, если ее невозможно рассчитать, объясните, какая требуется дополнительная информация и как она повлияет на результат.
14.4. Рассмотрите сеть, показанную на рис. 14.13, б; примите предположение, что два телескопа дают идентичные результаты, №{1,2,3} и м1гМ2е {0,1,2,3,4}, а также, что применяются такие символические таблицы СРТ, как описано в упр. 14.3. Используя алгоритм перебора, рассчитайте распределение вероятностей F(N\M1=2,M2=2).
14.5. Рассмотрите семейство линейных гауссовых сетей, которое показано на с. 672.
а) Допустим, что в сети с двумя переменными переменная хг является роди-
тельской по отношению к переменной х2, переменная хх имеет гауссово
распределение априорных вероятностей, а Р (Х2 \ хг) — линейное гауссо-
во распределение. Покажите, что совместное распределение P(Xltx2)
представляет собой многомерное гауссово распределение, и рассчитайте
его матрицу ковариации.
б) Докажите по индукции, что совместное распределение для линейной га-
уссовой сети общего вида по переменным xlf..., хп также является мно-
гомерным гауссовым распределением.
14.6. Пробит-распределение, описанное на с. 674, позволяет представить распреде-
ление вероятностей для булевой дочерней переменной, если задана одна не-
прерывная родительская переменная.
а) Как можно расширить это определение, чтобы оно охватывало несколько
непрерывных родительских переменных?
б) Как оно может быть расширено с учетом многозначной дочерней пере-
менной? Рассмотрите и те случаи, в которых значения дочерней пере-
менной упорядочены (как при выборе во время вождения автомобиля пе-
редачи в зависимости от скорости, крутизны подъема, требуемого уско-
рения и т.д.), и те случаи, в которых они не упорядочены (как при выборе
для проезда на работу или автобуса, или электропоезда, или автомобиля).
(Подсказка. Рассмотрите способы распределения возможных значений по
двум множествам для имитации булевой переменной.)
14.7. В этом упражнении речь идет об алгоритме устранения переменной, приве-
денном в листинге 14.2.
а) В разделе 14.4 алгоритм устранения переменной применялся к следую-
щему запросу:
Р[Burglary]JohnCalls=true,MaryCalls=true)
Проведите указанные вычисления и проверьте правильность ответа.
б) Подсчитайте количество выполненных арифметических операций и сравни-
те его с количеством операций, выполняемых в алгоритме перебора.
в) Предположим, что сеть имеет форму цепи — последовательности булевых
переменных xlt Хп, где Paren ts (Xi) = {Х} для 1=2,..., п. Какова
сложность вычисления выражения Р (X1\xn=true) с использованием алго-
ритма перебора? С использованием алгоритма устранения переменной?
г) Докажите, что сложность применения алгоритма устранения переменной в
сети, имеющей форму полидерева, линейно зависит от размера дерева при
любом упорядочении переменных, согласованном со структурой сети.
14.8. Проведите исследование сложности точного вывода в байесовских сетях об-
щего вида.
а) Докажите, что любую задачу 3-SAT можно свести к задаче точного вывода
в байесовской сети, сформированной для представления данной кон-
кретной задачи, и поэтому такой точный вывод является NP-трудным.
(Подсказка. Рассмотрите сеть с одной переменной для каждого пропози-
ционального символа, с одной для каждого выражения и с одной для
конъюнкции выражений.)
б) Проблема подсчета количества выполняющих присваиваний для задачи
3-SAT является #Р-полной (шарп-, или диез-Р-полной). Покажите, что зада-
ча точного вывода является, по меньшей мере, такой же трудной, как эта.
14.9. Рассмотрите задачу формирования случайной выборки из заданного распре-
деления по одной переменной. Вы можете принять предположение, что в ва-
шем распоряжении имеется генератор случайных чисел, который возвращает
случайное число с равномерным распределением в интервале от 0 до 1.
а) Допустим, что X— дискретная переменная с P(X=Xi)=Pi для ie {1,..., к]. Кумулятивное распределение (cumulative distribution) X задает вероятность того, что хе {xlf..., Xj} для каждого возможного j. Объясните, как рассчитать это кумулятивное распределение за время
О (к) и как получить из него одну выборку X. Может ли последняя операция быть выполнена за время меньше О {к)?
б) Теперь предположим, что необходимо сформировать N выборок X, где
Ш>к. Объясните, как выполнить эту операцию с ожидаемым временем
прогона в расчете на выборку, которое является постоянным (т.е. независимым от к).
в) После этого рассмотрим непрерывную переменную с параметризован-
ным (например, с гауссовым) распределением. Как можно формировать
выборки с помощью такого распределения?
г) Предположим, что необходимо сформулировать запрос, касающийся не-
прерывной переменной, и что для вероятностного вывода используется
такой алгоритм, как LikelihoodWeighting. Как вы модифицировали
бы процесс поиска ответов на такие запросы?
14.10. Марковское покрытие переменной определено на с. 669.
а) Докажите, что переменная является независимой от всех других пере-
менных в сети, если дано ее марковское покрытие.
б) Выведите уравнение 14.11.
14.11. Рассмотрите запрос Р {Rain | Sprinkler true, WetGrass= true) к байе-
совской сети, приведенной на рис. 14.9, я, и покажите, как можно получить на
него ответ с помощью алгоритма МСМС.
а) Какое количество состояний имеет эта цепь Маркова?
б) Рассчитайте матрицу переходов Q, содержащую значение д(у—>у' ) для
всех у, у.
в) Что представляет собой О2, квадрат матрицы переходов?
г) А что можно сказать о выражении (У1, где л—>°о?
д) Объясните, как следует выполнять вероятностный вывод в байесовских
сетях, при условии, что доступно выражение 0й. Является ли такой спо-
соб вероятностного вывода практически применимым?
14.12. $т Три футбольные команды, А, В и С, играют друг с другом по одному разу.
Каждый матч проводится между двумя командами и может закончиться для
команды выигрышем, ничьей или проигрышем. Каждой команде присвоена
постоянная, неизвестная оценка ее класса (целое число в диапазоне от 0 до 3),
и результат матча оценивается вероятностной зависимостью от разницы в
классе между двумя участвующими командами.
а) Сформируйте реляционную вероятностную модель для описания этой
проблемной области и предложите реальные числовые значения для всех
необходимых распределений вероятностей.
б) Сформируйте эквивалентную байесовскую сеть.
в) Примите предположение, что в первых двух матчах команда А побеждает
в и играет вничью с С. Используя выбранный вами алгоритм точного вы-
вода, вычислите распределение апостериорных вероятностей для резуль-
татов третьего матча.
г) Предположим, что в этой футбольной лиге п команд и известны результаты всех матчей, кроме последнего. Как сложность предсказания результатов последней игры зависит от л?
д) Рассмотрите возможность применения алгоритма МСМС для решения
этой задачи. Насколько быстро этот алгоритм сходится на практике и на-
сколько хорошо он масштабируется?