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

Задачи МОТП v 0.1by Александра Астахова, Юрий Бердников, Николай Леонов, Михаил Нокель, Данила ПотаповЗадача 1Вывести формулы векторного дифференцирования: 2 2 2 Решение:Будем считать все матрицы и векторы вещественнозначными. Тогда:1. ∑ ∑ , … , , … , Заметим также, что , .2. , , , , , , 2 , , , 2 Рассмотрим подробнее член , :, 2 , 2 где - k-й столбец матрицы .Таким образом: , 2 2 2 3. 2 2 2 . Задача 2Найти нормальное псевдорешение для системы линейных уравнений.Решение:Рассмотрим переопределенную нерешаемую систему линейных уравнений:1 101 1 61 01Данная система задает в двухмерном пространстве три прямые, не пересекающиеся в однойточке:x1- x2=0x2x1x1+ x2=6x1=1Таким образом она не решаема.

Найдем ее псевдорешение, для этого воспользуемся формулойдля его нахождения: Вычислим соответствующее произведение по порядку: 1 1 11 1 0 3 00 2 101 2 0 316 0 3021  31212 331 13 3102 Заметим, что полученное решение соответствует центру треугольника, образованного прямыми.Задача 3Даны N точек в двухмерном пространстве. Найти с помощью метода главных компонент первуюглавную компоненту и проекцию выборки на одномерное пространство.Рассмотрим 4 точки в двухмерном пространстве (! 4):Решение: 1,2, 2,1, 4,2, 6,3Вычислим выборочное среднее $ :111$ 13,8 &3 , 2'4!4Затем вычислим выборочную матрицу ковариаций ( как:25 5121 11819311+4 0 1 144( $ $ *16 0 16 4 16 0  164/ 4115!40 00 0421144).Найдем собственные вектора матрицы (, решая характеристическое уравнение det( 45 0:594678 1611142 4 6759401632Получаем 4, : ; .

Вектор, соответствующий главной компоненте, отвечает максимальному собственному значению выборочной матрицы ковариации. Получим его, решаяоднородную систему уравнений ( 4 56< 0 и нормируя:6< 0.99,0.018 , >6< > 1Спроецируем точки выборки на полученную прямую:? @A @6<где W-матрица из собственных векторов, @-матрица из точек выборки, центрированныхотносительно выборочного среднего, а ?-матрица проекций:10+ 4012.22*11/0.991.25* 4/30.0180.74*0/2.74* 4/31.) 242Дана выборка @ B , … , C из некоторого распределения D. Требуется оценить по выборкес помощью метода максимального правдоподобия значения параметров этого распределения.Задача 4Например, у распределения Лапласа вида D ℮известном или оценить при известном F.||оценить мат.

ожидание F приРешение:Запишем логарифм функции правдоподобия:G@|, F IJKТогда | F|1,22G LKM F.FТаким образом, F должно удовлетворять уравнению ∑ LKM F 0. Очевидно, что∑ LKM F обращается в 0, когда F O76 , … , , Так как тогда количествоположительных слагаемых будет совпадать с количеством отрицательных.Обозначим 4 и перепишем логарифм функции правдоподобия:1G@|, 4 MIJK4 4 | F| MIJK2.2Требуется найти такое 4, что:Следовательно, ответ:G M 1 | F| 0.4 4 2 11 | F|4 2MF O76 , … , .Дана выборка из ! точек в двухмерном пространстве. Первая координата – это , вторая – 8.

Спомощью метода наименьших квадратов построить линейную регрессию вида 8̂ Q , т.е.найти коэффициенты Q и .Задача 5РешениеМетод наименьших квадратов состоит в нахождении коэффициентов регрессии путемминимизации квадратичной функции потерь (8, 8̂ 8 8̂ . Для выборки из ! точекB , 8 , … , , 8 C и заданного вида регрессии функция потерь будет иметь вид:8 Q R min,Условия минимума на ( будут:( 2 8 Q 0Q( 2 8 Q 0Их можно переписать в виде: 8 Q 8 Q !Таким образом, выражая Q и по заданной выборке, получаем коэффициенты линейнойрегрессии.Задача 6Решить задачу условной оптимизации выпуклой функции при выпуклых ограничениях, например:5 2V 3V R max V1Решение:,Для решения задачи оптимизации воспользуемся правилом множителей Лагранжа. Для этогоприведем ограничение к стандартному виду и запишем функцию Лагранжа G, V, 4: V 1 Y K, V V 1 0G, V, 4 Z, V 4K, V 5 2V 3V 4 V 1Условия экстремума функции Z, V тогда примут вид:G 10 2V 4 0G 2 6V 4 0VG V1 04Для нахождения экстремума функции необходимо решить систему:10 210 26 1 [V\ 0 411 01Решением данной системы будет вектор:1 2 14 , V , ] , , 3 33Значит, максимум искомой функции достигается в точке , .

Задача 7Дана марковская сеть вида:с бинарными переменнымиеменными x1 , x2 , x3 , x4 . Для этой модели заданы все значения унарных функцийθ1 ( x1 ),θ 2 ( x2 ),θ 3 ( x3 ),θ 4 ( x4 ) и бинарных функций θ12 ( x1 , x2 ),θ 23 ( x2 , x3 ),θ 34 ( x3 , x4 ),θ 41 ( x4 , x1 ) . Спомощью репараметризации построить граф, минимальный разрез которого соответствует4минимуму энергии вида∑θ ( x ) + ∑ θii =1i( i , j )∈Eij( xi , x j ) .Решение:Приведём марковскую сеть к стандартному виду:Теперь проведём репараметризацию данной сети, сделав веса горизонтальных рёбер нулевыми,а веса диагональных рёбер - равными. Получим следующую систему уравнений (обозначив(обозначерезai - величину, вычитаемую из рёбер соответствующей вершины xi и прибавляемую к весу этойвершины):θ12 − a1 − a2θ 34 − a3 − a4θ − a − a 41 1 4=0=0= θ 23 − a2 − a3Решая данную систему, придём к следующей:a2a4 a3=== a1 +θ12 − a1θ 34 − a3− θ 41 + θ 34 + θ 23 − θ122a2 a3a4θ12 − a1− θ 41 + θ 34 + θ 23 − θ12= a1 +2θ 34 − θ 23 + θ12 + θ 41=− a12=Отсюда веса диагональных рёбер будутθ 41 − a1 − a4 =θ 41 − θ 34 − θ12 + θ 232Веса горизонтальных же рёбер равны 0 (по определению репараметризации).

Веса же самихвершин определены с точностью до неизвестной. Важно лишь, чтобы эти веса былинеотрицательны.Задача 8Дана марковская сеть с бинарными переменными вида “решетка”:Пусть все унарные энергии совпадают для всех вершин ௜ ௜ и равны 0 , 1 .Аналогично все бинарные энергии совпадают между собой ௜௝ ௜ , ௝ , и равны 0,0 , 0,1 , 1,0 , 1,1 . Требуется выполнить репараметризацию в этом графе так,чтобы все энергии ௜௝ 0,0 ௜௝ 1,1 0.Решение:Рассмотрим две соседние вершины ௜ и ௝ :௜Для них:௝Вычитая одинаковые значения из двух ребер, сходящихся в одну вершину и прибавляя этозначение к весу самой вершины, мы получаем эквивалентный функционал энергии.Таким образом, вычитая из ребер, сходящихся в левой нижней вершине и прибавляя к ее весу ,получим ᇱ 1,1 0. Аналогично с левой верхней вершиной.

Получим:В случае если требуется, чтобы так же были равными диагональные энергии 0,1 ᇱ 1,0,решим систему: ଵ ଶ 0 ଷ ସ 0 ଵ ସ ଶ ଷГде ଵ прибавляем к левой верхней вершине и вычитаем из входящих в нее ребер,аналогичноଶ прибавляем к правой верхней, ଷ соответствует левой нижней, а ସ - правой нижней.В итоге получим:ଵ ଷ .2Положив, например, ଷ 0, получимଵ 2ଶ 2ସ Тогда после репараметризации энергии будут равны: ᇱ 0,1 ଵ ସ 2 ᇱ 1,0 ଶ ଷ 2 ᇱ 0,0 ଵ ଶ 0 ᇱ 1,1 0Таким образом, получили репараметризацию, при которой горизонтальные ребра графа имеютнулевые веса, а веса диагональных ребер совпадают.Задача 9Дана следующая вероятностная модель:NNn =1n =1p ( X , T | µ , a0 , b0 ) = ∏ p ( xn , t n | µ , a0 , b0 ) = ∏ p ( xn | t n , µ ) p (t n | a0 , b0 ),tt n − 2n ( xn − µ ) 2e,2πp ( xn | t n , µ ) = N ( xn | µ , t ) =−1nab 0 a −1 −b tap(t n | a0 , b0 ) = G (t n | a0 , b0 ) = 0 tn 0 e 0 n , Etn = 0 .Γ(a0 )b0Требуется выписать формулы EM-алгоритма для максимизации правдоподобия:p ( X | µ , a0 , b0 ) → maxµпри фиксированных a0 ,b0 .Решение:Выписываем Е-шаг.На Е-шаге необходимо вычислить log( p ( X , T | θ old )) и найти условное математическое ожиданиеET | X ,θoldlog ( p ( X , T | θ old )).

Вычислим их:NNn =1n =1log( p ( X , T | θ old )) = ∑ log( p ( xn | t n , µ )) + ∑ log( p (t n | a0 , b0 )) =aNttb0= ∑(log( n ) − n ( xn − µ ) 2 + log( 0 ) + (a0 − 1) log(tn ) − b0t n )2π2Γ(a0 )n =1Учитывая, что максимизация правдоподобия будет проводиться только лишь по µ , перепишемнайденную величину следующим образом:Ntn( xn − µ ) 2 + f (t n )n =1 2log( p ( X , T | µ old )) = −∑Тогда вычислим условное математическое ожидание, учитывая, что Et n =ET | X ,θoldlog( p( X , T | θ old )) =Na02b0N∑( xna0:b0− µ ) 2 + Ef (tn )n =1Выписываем M-шаг.На M-шаге максимизируется условное математическое ожидание, найденное на E-шаге:δET | X ,θold log( p( X , T | θ old ))δµ=−Отсюда следует:µ=1NN∑xn =1n2 Na02b0N∑( xn =1n− µ) = 0Задача 10Рассматривается вероятностная смесь двух дискретных распределений вида:p( x) = γp1 ( x) + (1 − γ ) p2 ( x).Величина x может принимать значения (1,2,3).

При этом параметры распределений равны:p1 : 123p2 : 1α 1−α 020 1− β3βВыборка X состоит из 30 единиц, 20 двоек и 60 троек. Требуется провести первые две итерацииEM-алгоритма для восстановления параметров смеси (α , β , γ ) для начального приближенияα 0 = β 0 = γ 0 = 0.5.Решение:Первая итерацияE-шагВычисляем значения g ij =w j * p j ( xi )∑wj* p j ( xi ):j0.5 * 0.5= 1,0.5 * 0.5 + 0 * 0.5g12 =0 * 0.5= 0,0.5 * 0.5 + 0 * 0.50.5 * 0.5= 0.5,0.5 * 0.5 + 0.5 * 0.5g 22 =0.5 * 0.5= 0.5,0.5 * 0.5 + 0.5 * 0.50 * 0.5= 0,0.5 * 0.5 + 0 * 0.5g 32 =0.5 * 0.5= 1.0.5 * 0.5 + 0 * 0.5g11 =g 21 =g 31 =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βОтсюда, подставив значения:30 log(α ) + 10 log(1 − α ) → max ,α60 log( β ) + 10 log(1 − β ) → maxβВзяв логарифм и продифференцировав первое выражение по α , второе - по β , получим:34α = ,β =67Пересчитаем γ :γ=30 g11 + 20 g 21 4=60 + 30 + 20 11Вторая итерацияE-шагВычисляем значения g ij =w j * p j ( xi )∑wj* p j ( xi ):j4 3*114g11 == 1,4 37* + 0*11 4114 1*114g 21 == 0.5,4 1 7 1* + *11 4 11 74*011g 31 == 0,47 6*0 + *1111 77*011g12 == 0,4 37* + 0*11 4117 1*117g 22 == 0.5,4 1 7 1* + *11 4 11 77 6*117g 32 == 1.7 67* + 0*11 711Заметим, что значения g ij не поменялись.