2010 Задачи к экзамену по курсу МОТП. Решение v1, страница 2

А значит, не поменяются и значения параметров на Mшаге.M-шагДействительно в формулах для "взвешенного" правдоподобия ничего не изменилось:30 g11 log ( p1 ( x = 1)) + 20 g 21 log ( p1 ( x = 2)) → max ,α60 g 32 log( p2 ( x = 3)) + 20 g 22 log( p2 ( x = 2)) → maxβСледовательно:34α = ,β =Аналогично и для γ :67γ=30 g11 + 20 g 21 4=60 + 30 + 20 11Как видим, значения параметров на второй итерации не изменились.Задача 11Пусть имеется три бинарных переменных a, b, c ∈ 0,1 , совместное распределение которыхзадаётся следующей таблицей:a b cp ( a , b, c )0 0 00.1920 0 10 1 00.1440.0480 1 10.2161 0 00.1921 0 11 1 00.0640.0481 1 10.096Требуется показать, что переменные a и b не являются независимыми, но при этом являютсяусловно независимыми как при c = 0 , так и при c = 1 .Решение:Вначалепокажемзависимость этихp ( a = 0, b = 0) ≠ p ( a = 0) p (b = 0) : Имеем:переменных.Покажем,например,чтоp (a = 0) = ∑ p (a, b, c) = 0.192 + 0.144 + 0.048 + 0.216 = 0.6,a =0p (b = 0) = ∑ p (a, b, c) = 0.192 + 0.144 + 0.192 + 0.064 = 0.592,b=0p ( a = 0, b = 0) =∑p ( a, b, c ) = 0.192 + 0.144 = 0.336a = 0,b = 0Очевидно:0.336 ≠ 0.592 * 0.6 = 0.3552Значит, переменные зависимые.Далее покажем условную независимость.

Для этого составим таблички, в которые занесёмнеобходимые вероятности: p ( a, c ), p (b, c ), p (c ) :a c0 0p ( a, c)0.240 10.361 01 10.240.16b c0 0p (b, c)0.3840 10.2081 01 10.0960.312c p(c)0 0.481 0.52Теперь проверим условную независимость переменных a и b при условии c , воспользовавшисьследующей формулой, вытекающей из определения условной независимости двух величин:p (a, b, c) p (a, c) p (b, c)=*.p (c )p (c )p (c )• При c = 0.При a = 0, b = 0 :0.192 0.24 0.384=*- верно.0.48 0.48 0.480.048 0.24 0.096=*- верно.При a = 0, b = 1 :0.480.480.480.192 0.24 0.384=*При a = 1, b = 0 :- верно.0.480.480.480.048 0.24 0.096=*- верно.При a = 1, b = 1 :0.480.480.48• При c = 1.При a = 0, b = 0 :0.144 0.36 0.208=*- верно.0.52 0.52 0.52При a = 0, b = 1 :0.216 0.36 0.312=*- верно.0.52 0.52 0.52При a = 1, b = 0 :0.064 0.16 0.208=*- верно.0.52 0.52 0.52При a = 1, b = 1 :0.096 0.16 0.312=*- верно.0.52 0.52 0.52Отсюда следует, что данное равенство: p ( a, b | c ) = p ( a | c ) p (b | c ) и переменные условнонезависимы.Задача 12Пусть имеется байесовская сеть с графом следующего вида:bacdТребуется показать, что переменные и являются независимыми, но при этом не являютсяусловно независимыми от .Решение:Покажем, что a и b – независимы:, , , , | |, |, | |, .

Значит случайные величиныa и b независимы по определению.Докажем отсутствие условной независимости случайных величин a и b от d.| | В то время как, | , | |, | |, , | |Следовательно , | |, |, что означает отсутствие условной независимости по d.Задача 13Имеется скрытая марковская модель с двумя скрытыми состояниями и бинарныминаблюдаемыми переменными.

Пусть наблюдаемая последовательность имеет вид 1011001110001 … , т.е. идет группа из единиц, потом группа из нулей, потом группа из 1 единиц, 1 нулей и так далее. При этом наблюдаемая последовательность состояний 1111222211112222 … . С помощью метода максимального правдоподобия требуетсяоценить вектор априорных вероятностей и матрицу перехода , если длина последовательностиравна 200.Решение:Воспользуемся формулами, полученными для оценки параметров методом максимальногоправдоподобия: , 1, … ∑ , ,∑ ,, 1, … Где 2, 200. Тогда 1,0, так как 1,0, так как в первый момент модельнаходится в первом состоянии. Для матрицы перехода получим: ∑25 3 , 0.75∑ ,25 4Числитель дроби соответсвует количеству переходов из первого состояния во второе, азнаменатель обозначает общее количество переходов из первого состояния.

Аналогично: Таким образом матрица равна:Ответ: 1,0, %∑25 1 , 0.2525 4∑ ,∑24 , 0. 24∑ ,4 24 3∑24 3 3 , 0. 75∑ ,4 24 3%0.750.25&.0. 24 0. 750.750.25&0. 24 0. 75Задача 14Имеется скрытая марковская модель с двумя скрытыми состояниями. Вектор априорных0.9 0.1вероятностей 0.5,0.5, матрица перехода '*. Наблюдаемая переменная0.2 0.8является бинарной, в первом состоянии значение 0 выпадает с вероятностью 0.8, а во второмсостоянии – с вероятностью 0.2. Требуется с помощью алгоритма Витерби найти наиболееправдоподобную последовательность скрытых состояний для наблюдаемой последовательности +0,0,1,0,0,1,1,.Решение:Воспользуемся формулами для функции Беллмана:- ./0- max-, ./0 ./04 |5 6 70 max-, ./0 ./04 |5 .Тогда:- ./0 ./00.5- ./0 ./00.5- maxlog 0.5 log 0.9 log 0.8, log 0.5 log 0.2 log 0.8 maxlog 0.36, log0.08- maxlog 0.5 log 0.1 log 0.2, log 0.5 log 0.8 log 0.2 maxlog 0.01, log0.08- maxlog 0.36 log 0.9 log 0.2, log 0.08 log 0.2 log 0.2 maxlog 0.0648, log0.0032- maxlog 0.36 log 0.1 log 0.8, log 0.08 log 0.8 log 0.8 maxlog 0.0288, log0.0512И так далее до 7й итерации:- maxlog 0.01 log 0.9 log 0.2, log 0.008 log 0.2 log 0.2 maxlog 0.0018, log0.0003- maxlog 0.01 log 0.1 log 0.8, log 0.008 log 0.8 log 0.8 maxlog 0.0008, log0.0051Таким образом 7 70max- , - 2.

Используя формулу для вычисления 6 , получаемпоследовательность скрытых состояний равных 2.Задача 15Имеется скрытая марковская модель с двумя скрытыми состояниями. Вектор априорных0.9 0.1вероятностей 0.5,0.5, матрица перехода '*. Наблюдаемая переменная0.2 0.8является бинарной, в первом состоянии значение 0 выпадает с вероятностью 0.8, а во второмсостоянии – с вероятностью 0.2. Требуется с помощью алгоритма «вперед-назад» вычислить всемаргинальные распределения вида | для наблюдаемой последовательности 0,0,1.Решение:Пользуясь свойствами условной независимости в для скрытых марковских сетей, запишем | < · > , где B < .ಿВычислим < , пользуясь формулами:< C 4 |5 భೕ< 4 | B < | .೙షభТогда< < '0.8 00.9 0.10.40.80.5*·'* · ' * < ' * ' *,0 0.20.2 0.80.10.20.50.9 0.10.5* – матрица перехода, ' * - априорные вероятности, < - нормировочная0.2 0.80.5константа.

АналогичноГде '< < '< < '0.8 00.9 0.10.80.90.592*·'*·' * <'*' *0 0.20.2 0.80.20.10.0640.2 00.9 0.10.90.1640.44*·'*·' * <'*'*.0 0.80.2 0.80.10.2080.56Рассчитываем > по формулам:> B > 4 | | ೙శభТогда в нашей задаче:> > '> > '> 1.0.9 0.10.2 010.1880.22*·'*·' * >'*'*0.2 0.80 0.810.680.780.9 0.10.8 00.220.1740.52*·'*·'* >'*'*0.2 0.80 0.20.780.160.48> > '0.9 0.10.8 00.3840.70.52*·'*·'* >'* ' *,0.2 0.80 0.20.160.30.48Где >- нормировочная константа.Тогда итоговые маргинальные распределения:D | D | D | 0.7 · 0.44 0.3730.3 · 0.56 0.7 · 0.440.52 · 0.9 0.9060.1 · 0.48 0.52 · 0.90.22 · 0.8 0.8310.78 · 0.2 0.22 · 0.8Рассматривается игра «Морской бой».

В квадрате размера 3 E 3возможны 2 ситуации: одиндвухпалубный корабль и два двухпалубных корабля. С помощью построения тупикового тестанайти минимальное число ходов, необходимое для гарантированного определения того, какая издвух ситуаций имеет место.Задача 16Решение:Для начала запишем таблицы всех возможных положений кораблей каждого из классов К1 (1двухпалубный) и К2 (2 двухпалубных).

Поле 9*9 будем представлять как вектор длины 9, соответствующийследующей нумерации клеток:1 2 34 5 67 8 9Найдём таблицу попарных различий строк из таблиц первого и второго классов.Далее применяем стандартный метод. Для каждой строки вида [z1 z2 … z9] записываем соответствующуюдизъюнкт: ݇ 4 - 4 - … -4ೖ , в которую включается переменная 4 F G 1 . Рассматриваемфункцию H I J , в которой получаем 96 дизъюнктов. Упрощение с использованиемпреобразований J J - J’ J производилось с использованием компьютера.В итоге получилось H 4 - 4 4 - 4 4 -4 4 -4 4 -4 4 -4 4 -4 4 -4 4 - 4 4 4 - 4 4 4 - 4 4 4 - 4 4 4 4 4 4 - 4 4 4 4 - H’, где F’ очевидносодержит только конъюнкты длины > 4. Значит кратчайшими тупиковыми тестами будут 2-4-6-8 и1-3-7-9, что соответствует: .

Очевидно, в первом случае при 2-х ипопаданиях получаем 2 корабля, при одном – один. Во втором – 1 корабль при 0 и 1 попадании, 2корабля – при 2.Код на Матлабе для исключения лишних дизъюнктов прилагается:a = [110100000000100001000000010000000010001000110000001100001100000100000011000010010000000011000100000001000001];b = [111101011010000000111010000011110000000000001111100100111111000001100101];na = size(a, 1);nb = size(b, 1);m = size(a, 2);c = zeros(na*nb, m, 'uint8');for i = 1 : size(a, 1)for j = 1 : size(b, 1)c((i-1)*nb + j, :) = (a(i,:) ~= b(j, :));endendfinish = false;while ~finishfinish = true;n = size(c, 1);for i = 1 : nfor j = 1 : i-1if (c(i, :) <= c(j, :))c(j, :) = [];finish = false;break;elseif (c(j, :) <= c(i, :))c(i, :) = [];finish = false;break;endendif finish == falsebreak;endendendЗадача 17Найти результирующую ДНФ для системы тестовых уравнений4 Q4 1P N 4 Q4 14 Q4 1 SORNM4 Q4 1Рассмотрим д.

н. ф. Q 4 4 … 4ೖ , где индексы  , … , ೖ _ всевозможные комбинации,удовлетворяющие условиям:Решение:1) 0 k  k R k ೖ k 2) Среди  нет трёх подряд идущих чисел (считая, что индексы  и ೖ присутствуютвсегда).3)  _  l 2, 0, 1, … , 1,  0, ೖ 1 .Очевидно, если д.н.ф. = 1, то все уравнения системы будут выполняться. Действительно, в д.н.ф.найдётся конъюнкт К = 4 4 … 4ೖ 1, у которого индексы  , … , ೖ удовлетворяют условиям 1)3).

Из условия 3) сразу же следует выполнимость каждого уравнения системы.Осталось показать, что д.н.ф. - тупиковая. Поскольку правило склейки неприменимо (нетотрицаний переменных), все конъюнкты различны и правило поглощения не применимо, то потеореме Блейка-Квайна д.н.ф.

является максимальной. Невозможность применить правилапоглощения (K V K*K’ => K) следует из того, что характеристические вектора наборов индексовразличных конъюнктов несравнимы между собой. Под характеристическим вектором конъюнктапонимается булев вектор, где 1 стоят на тех (и только тех) местах, которые соответствуют номераминдексов переменных, входящих в этот конъюнкт. А несравнимы они потому, что при добавлениихотя бы одной новой единицы в характеристический вектор какого-либо конъюнкта приведёт кнарушению свойства 2).Значит построенная таким образом д.н.ф. является тупиковой д.н.ф.,ч.т.дЗадача 18В обучающей таблице класс K1 состоит из всех векторов, принадлежащих шару радиуса 3 сцентром в (0, 0, …, 0), а класс K2 состоит из всех векторов, принадлежащих шару радиуса 4с центром в (1, 1, …, 1).

К какому классу будет отнесен объект (0, 1, 0, …, 1) алгоритмом«Кора», если n – четное?Решение:Утверждение: Для любого набора из 3 столбцов (i1, i2, i3) и любой тройки чисел (k1, k2, k3)можно найти такой вектор U из K1 и V из K2, что Ui1 = Vi1 = k1, Ui2 = Vi2 = k2, Ui3 = Vi3 = k3.Доказательство:1)Для класса K1: берём вектор U : Ui = kj для i = ij и Ui = 0 для остальных i. В нем не большетрёх единиц (по построению), следовательно, U отстоит от (0, 0, …, 0) не более, чем на 3 ипринадлежит K1.2)Для класса К2: берём вектор V : Vi = kj для i = ij и Ui = 1 для остальных i.