2010 Задачи к экзамену по курсу МОТП. Решение v2 (1185264), страница 2
Текст из файла (страница 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 00 1p (a, c)0.240.361 01 10.240.16b c0 00 1p (b, c)0.3840.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 max;<= >. ?@, log0.08- maxlog 0.5 log 0.1 log 0.2, log 0.5 log 0.8 log 0.2 maxlog 0.01, ;<=>. >A- maxlog 0.36 log 0.9 log 0.2, log 0.08 log 0.2 log 0.2 max;<= >. >@CA, log0.0032- maxlog 0.36 log 0.1 log 0.8, log 0.08 log 0.8 log 0.8 maxlog 0.0288, ;<=>.
>DEF- maxlog 0.0648 log 0.9 log 0.8, log 0.0512 log 0.2 log 0.8 max;<= >. >C@@, log0.0082- maxlog 0.0648 log 0.1 log 0.2, log 0.0512 log 0.8 log 0.2 maxlog 0.0013, ;<=>. >>AF- maxlog 0.00466 log 0.9 log 0.8, log 0.0082 log 0.2 log 0.8 max;<= >. >??D, log0.0013- maxlog 0.0466 log 0.1 log 0.2, log 0.0082 log 0.8 log 0.2 maxlog 0.001, ;<=>. >>E?- maxlog 0.0335 log 0.9 log 0.2, log 0.0013 log 0.2 log 0.2 max;<= >. >>@, log0.000. . - maxlog 0.0335 log 0.1 log 0.8, log 0.0013 log 0.8 log 0.8 max;<= >. >>FG log0.000832- maxlog 0.006 log 0.9 log 0.2, log 0.0027 log 0.2 log 0.2 max;<= >.
>>E, log0.0001- maxlog 0.006 log 0.1 log 0.8, log 0.0027 log 0.8 log 0.8 maxlog 0.00048, ;<=>. >>EGF.Таким образом, max - , - 2. Рассматривая получившиеся значения 6 , получим 6 2 6 E 6 1 6 1 6 1 6 1.Значит, последовательность крытых состояний имеет вид: (1,1,1,1,1,2,2).Ответ: (1,1,1,1,1,2,2).Задача 15Имеется скрытая марковская модель с двумя скрытыми состояниями. Вектор априорных0.9 0.1вероятностей 0.5,0.5, матрица перехода '*. Наблюдаемая переменная0.2 0.8является бинарной, в первом состоянии значение 0 выпадает с вероятностью 0.8, а во второмсостоянии – с вероятностью 0.2. Требуется с помощью алгоритма «вперед-назад» вычислить всемаргинальные распределения вида | для наблюдаемой последовательности 0,0,1.Решение:Пользуясь свойствами условной независимости в для скрытых марковских сетей, запишем | H · J , где N H .ಿВычислим H , пользуясь формулами:H O 4 |5 భೕH 4 | N H | .షభТогдаH H '0.8 00.9 0.10.40.80.5*·'* · ' * H ' * ' *,0 0.20.2 0.80.10.20.50.9 0.10.5* – матрица перехода, ' * - априорные вероятности, H - нормировочная0.2 0.80.5константа.
АналогичноГде 'H H 'H H '0.8 00.9 0.10.80.90.592*·'*·' * H'*' *0 0.20.2 0.80.20.10.0640.2 00.9 0.10.90.1640.44*·'*·' * H'*'*.0 0.80.2 0.80.10.2080.56Рассчитываем J по формулам:J N J 4 | | శభТогда в нашей задаче:J J 'J J 'J 1.0.9 0.10.2 010.1880.22*·'*·' * J'*'*0.2 0.80 0.810.680.780.9 0.10.8 00.220.1740.52*·'*·'* J'*'*0.2 0.80 0.20.780.160.48J J '0.9 0.10.8 00.3840.70.52*·'*·'* J'* ' *,0.2 0.80 0.20.160.30.48Где J- нормировочная константа.Тогда итоговые маргинальные распределения:P | P | P | 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 Q 3возможны 2 ситуации: одиндвухпалубный корабль и два двухпалубных корабля.
С помощью построения тупикового тестанайти минимальное число ходов, необходимое для гарантированного определения того, какая издвух ситуаций имеет место.Задача 16Решение:Для начала запишем таблицы всех возможных положений кораблей каждого из классов К1 (1двухпалубный) и К2 (2 двухпалубных). Поле 9*9 будем представлять как вектор длины 9, соответствующийследующей нумерации клеток:1 2 34 5 67 8 9Найдём таблицу попарных различий строк из таблиц первого и второго классов.Далее применяем стандартный метод. Для каждой строки вида [z1 z2 … z9] записываем соответствующуюдизъюнкт: ݇ 4 - 4 - … -4ೖ , в которую включается переменная 4 R S 1 . Рассматриваемфункцию T U V , в которой получаем 96 дизъюнктов. Упрощение с использованиемпреобразований V V - V’ V производилось с использованием компьютера.В итоге получилось T 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 - T’, где 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 ]4 1\ Z 4 ]4 14 ]4 1 _[^ZY4 ]4 1Рассмотрим д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
