2010 Задачи к экзамену по курсу МОТП (Журавлёв)

Задачи к экзамену по курсу «Математические основытеории прогнозирования» 20101. Вывести формулы векторного дифференцирования∇x aT x = a,∇x ∥Ax − b∥2 = 2AT Ax − 2AT b,∇2x ∥Ax − b∥2 = 2AT A.2. Найти нормальное псевдорешение для системы линейных уравнений.3. Даны N точек в двухмерном пространстве. Найти с помощью метода главных компонентпервую главную компоненту и проекцию выборки на одномерное пространство.4. Дана выборка X = {x1 , . . . , xN } из некоторого распределения p(x).

Требуется оценитьпо выборке с помощью метода максимального правдоподобия значения параметровэтого()1распределения. Например, у распределения Лапласа вида p(x) = 2bexp − |x−µ|оценить2bмат.ожидание µ при известном b или оценить b при известном µ.5. Дана выборка из N точек в двухмерном пространстве. Первая координата – это x, вторая– t. С помощью метода наименьших квадратов построить линейную регрессию вида t̂ =kx + b, т.е.

найти коэффициенты k и b.6. Решить задачу условной оптимизации выпуклой функции при выпуклых ограничениях,например− 5x2 + 2xy − 3y 2 → max,x,yx = y − 1.7. Дана марковская сеть видаx1x2x4x3с бинарными переменными 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)+θ(xi , xj ).i=1 i i(i,j)∈E ij18.

Дана марковская сеть с бинарными переменными вида решетка:...........................Пусть все унарные энергии совпадают для всех вершин θi (xi ) = θ(x) и равны θ(0) =a, θ(1) = b. Аналогично все бинарные энергии совпадают между собой θij (xi , xj ) =θ(x, y) и равны θ(0, 0) = c, θ(0, 1) = d, θ(1, 0) = e, θ(1, 1) = f . Требуется выполнитьрепараметризацию в этом графе так, чтобы все энергии θij (0, 0) = θij (1, 1) = 0.9. Дана следующая вероятностная модель:p(X, T |µ, a0 , b0 ) =N∏p(xn , tn |µ, a0 , b0 ) =n=1p(xn |tn , µ) =√N (xn |µ, t−1n )=(N∏p(xn |tn , µ)p(tn |a0 , b0 ),n=1)tntn2exp − (xn − µ) ,2π2ba00 a0 −1a0p(tn |a0 , b0 ) = G(tn |a0 , b0 ) =tn exp(−b0 tn ), Etn = .Γ(a0 )b0Требуется выписать формулы ЕМ-алгоритма для максимизации правдоподобияp(X|µ, a0 , b0 ) → maxµпри фиксированных a0 , b0 .10.

Рассматривается вероятностная смесь двух дискретных распределений видаp(x) = γp1 (x) + (1 − γ)p2 (x).Величина x может принимать значения (1,2,3). При этом параметры распределенийравны:p1 :1α21−α30p2 :120 1−β3βВыборка X состоит из 30 единиц, 20 двоек и 60 троек. Требуется провести первые двеитерации ЕМ-алгоритма для восстановления параметров смеси (α, β, γ) для начальногоприближения α0 = β0 = γ0 = 0.5.11. Пусть имеется три бинарных переменных a, b, c ∈ {0, 1}, совместное распределениекоторых задается следующей таблицей:2a00001111b00110011c01010101p(a, b, c)0.1920.1440.0480.2160.1920.0640.0480.096Требуется показать, что переменные a и b не являются независимыми, но при этомявляются условно независимыми как при c = 0, так и при c = 1.12. Пусть имеется байесовская сеть с графом следующего вида:abcdТребуется показать, что переменные a и b являются независимыми, но при этом неявляются условно независимыми от переменной d.13.

Имеется скрытая марковская модель с двумя скрытыми состояниями и бинарныминаблюдаемыми переменными. Пусть наблюдаемая последовательность имеет вид X =(1011001110001 . . . ), т.е. идет группа из n единиц, потом группа из n нулей, потомгруппа из n + 1 единиц, n + 1 нулей и т.д. При этом наблюдаемая последовательностьсостояний T = (11112222111122221 . . . ). С помощью метода максимального правдоподобиятребуется оценить вектор априорных вероятностей π и матрицу перехода A, если длинапоследовательности равна 200.14. Имеется скрытая марковская модель с двумя скрытымисостояниями.Вектор априорных()0.9 0.1. Наблюдаемая переменнаявероятностей π = (0.5, 0.5), матрица перехода A =0.2 0.8является бинарной, в первом состоянии значение ноль выпадает с вероятностью 0.8, вовтором состоянии – с вероятностью 0.2.

Требуется с помощью алгоритма Витерби найтинаиболее правдоподобную последовательность скрытых состояний для наблюдаемойпоследовательности X = (0, 0, 1, 0, 0, 1, 1).15. Имеется скрытая марковская модель с двумя скрытымисостояниями.Вектор априорных()0.9 0.1вероятностей π = (0.5, 0.5), матрица перехода A =. Наблюдаемая переменная0.2 0.8является бинарной, в первом состоянии значение ноль выпадает с вероятностью 0.8,во втором состоянии – с вероятностью 0.2. Требуется с помощью алгоритма «впередназад» вычислить все маргинальные распределения вида p(tn |X) для наблюдаемойпоследовательности X = (0, 0, 1).316. Рассматривается игра «Морской бой». В квадрате размера 3 × 3 возможны две ситуации:один двухпалубный корабль и два двухпалубных корабля. С помощью построениятупикового теста найти минимальное число ходов, необходимое для гарантированногоопределения того, какая из двух ситуаций имеет место.17.

Найти результирующую ДНФ для системы тестовых уравненийx1 ∨ x2 = 1, x2 ∨ x3 = 1,x3 ∨ x4 = 1,........... xn−1 ∨ xn = 1.18. В обучающей таблице класс K1 состоит из всех векторов, принадлежащих шару радиуса3 с центром в (0, 0, . . . , 0), а класс K2 состоит из всех векторов, принадлежащих шарурадиуса 4 с центром в (1, 1, . . .

, 1). К какому классу будет отнесен объект (0, 1, . . . , 0, 1)алгоритмом «Кора», если n – четное?19. В обучающей таблице класс K1 представлен объектами (0, 0, . . . , 0, 0) и (1, 1, . . . , 1, 1),а класс K2 — объектами (1, 0, 1, 0, . . . ) и (0, 1, 0, 1, . . . ). Тестовый объект имеет вид(1, 1, .

. . , 1, 0, 0, . . . , 0). К какому классу будет отнесен этот объект алгоритмом «Кора»| {z }kпри четном и нечетном n?20. Написать формулу для числа голосов в алгоритме вычисления оценок, если функцияблизости определяется параметрами ε1 , . . . , εn , допустимое число невыполняющихсянеравенств q = 3, а совокупность характеристических векторов опорных множествобразует интервал конъюнкции x1 . . . xr x̄r+1 . . .

x̄r+k .21. В алгоритме вычисления оценок x11 = 1, x10 = x01 = x00 = 0. Написать формулу длячисла голосов, если функция близости определяется параметрами ε1 , . . . , εn , допустимоечисло невыполняющихся неравенств равно q, а система опорных множеств состоит из всехподмножеств мощности 2q.4.