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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Задачи МОТП 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 не поменялись.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов ответов (шпаргалок)