Редактирование: МОТП, Задачи на экзамене
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 32: | Строка 32: | ||
<math>B\bar{u}=\bar{b}_1u_1+\dots+\bar{b}_nu_n \Rightarrow \frac{\partial B\bar{u}}{\partial u_i}=b_i \Rightarrow \frac{\partial B\bar{u}}{\partial \bar{u}}=B=2A^TA</math> | <math>B\bar{u}=\bar{b}_1u_1+\dots+\bar{b}_nu_n \Rightarrow \frac{\partial B\bar{u}}{\partial u_i}=b_i \Rightarrow \frac{\partial B\bar{u}}{\partial \bar{u}}=B=2A^TA</math> | ||
- | |||
- | ==Задача 2. Поиск нормального псевдорешения== | ||
- | Найти нормальное псевдорешение для системы линейных уравнений. | ||
- | ===Решение=== | ||
- | |||
- | '''В чём суть''': Мы хотим решить несовместную систему линейных уравнений <math>Ax \approx b</math>. Для этого мы будем минимизировать квадрат нормы невязки, т.е найдём <math>x</math> такой, что при нём квадрат нормы невязки будет наименьшим: <math>{\|Ax-b\|}^2\to min_{x}</math>. Теперь по шагам: | ||
- | |||
- | 1. Представим норму в матричном виде и раскроем скалярное произведение: | ||
- | |||
- | <math>{\|Ax-b\|}^2=\langle Ax-b,Ax-b \rangle = {(Ax-b)}^{T}(Ax-b) = </math> | ||
- | |||
- | <math> = {(Ax)}^{T}Ax-b^{T}Ax-{(Ax)}^{T}b+b^{T}b = x^{T}A^{T}Ax-2x^{T}A^{T}b+b^{T}b</math> | ||
- | |||
- | 2. Теперь возьмём производную и приравняем её к нулю: | ||
- | |||
- | <math>\frac{\partial}{\partial x}(x^{T}A^{T}Ax-2x^{T}A^{T}b+b^{T}b) = 2{A}^{T}Ax - 2{A}^{T}b = 0</math> | ||
- | |||
- | 3. Из этого получаем <math>x</math>: | ||
- | |||
- | <math>x={({A}^{T}A)}^{-1}{A}^{T}b</math> | ||
- | |||
==Задача 3. Метод главных компонент (PCA)== | ==Задача 3. Метод главных компонент (PCA)== | ||
Строка 118: | Строка 97: | ||
Еще один вариант - посчитать напрямую <math>(k,b)=(X^TX)^{-1}X^TY</math>, где <math>X</math> - матрица, первый столбец которой составлен из <math>x_i</math>, второй - из единиц, а <math>Y</math> - столбец из <math>t_i</math>. | Еще один вариант - посчитать напрямую <math>(k,b)=(X^TX)^{-1}X^TY</math>, где <math>X</math> - матрица, первый столбец которой составлен из <math>x_i</math>, второй - из единиц, а <math>Y</math> - столбец из <math>t_i</math>. | ||
- | |||
- | Либо еще другой вариант: <math>k = \frac{cov(X,T)}{DX}</math>, <math>b = \overline{T} - k\overline{X}</math> | ||
== Задача 6. Правило множителей Лангранжа== | == Задача 6. Правило множителей Лангранжа== | ||
Строка 146: | Строка 123: | ||
(По-моему, гораздо проще без функции Лагранжа: <math>y=x+1; f(x)=-6x^2-4x-3; x=-b/2a=-4/12=-1/3</math>) | (По-моему, гораздо проще без функции Лагранжа: <math>y=x+1; f(x)=-6x^2-4x-3; x=-b/2a=-4/12=-1/3</math>) | ||
- | |||
- | |||
- | ==Задача 8. Марковская сеть== | ||
- | Дана марковская сеть с бинарными переменными вида решетка: | ||
- | |||
- | ---рисунок--- | ||
- | |||
- | Пусть все унарные энергии совпадают для всех вершин | ||
- | <math> \Theta(x_i)=\Theta(x)</math> | ||
- | и равны | ||
- | <math>\Theta(0)=a, \Theta(1)=b</math>. Аналогично все бинарные энергии совпадают между собой | ||
- | <math> | ||
- | \Theta_{ij}(x_i; x_j) = | ||
- | \Theta(x; y) | ||
- | </math> | ||
- | и равны | ||
- | <math> | ||
- | \Theta(0; 0) = c; | ||
- | \Theta(0; 1) = d; | ||
- | \Theta(1; 0) = e; | ||
- | \Theta(1; 1) = f. | ||
- | </math> | ||
- | Требуется выполнить репараметризацию в этом графе так, чтобы все энергии | ||
- | <math> | ||
- | \Theta_{ij}(0; 0) = \Theta_{ij}(1; 1) = 0 | ||
- | </math>. | ||
- | ===Решение=== | ||
- | [[Изображение:Репараметризация.jpg|600px|Черновик]] | ||
- | |||
- | == Задача 10. == | ||
- | === Решение === | ||
- | g - гамма, a - альфа, b - бета. | ||
- | Очевидно, выборка из наблюдений дискретной случайно величины со следующим распределением: | ||
- | |||
- | 1 с вероятностью ga | ||
- | |||
- | 2 с вероятностью g(1-a)+(1-g)(1-b) | ||
- | |||
- | 3 с вероятностью b(1-g) | ||
- | |||
- | Первый шаг. С учетом начального приближения, вероятности 1, 2 и 3 - 0.25, 0.5 и 0.25 соответственно. | ||
- | |||
- | Распределения скрытой компоненты очевидны: | ||
- | |||
- | Если текущий элемент выборки 1, то Z=0 с вероятностью 1 | ||
- | |||
- | Если текущий элемент выборки 3, то Z=1 с вероятностью 1 | ||
- | |||
- | Если текущий элемент выборки 2, то Z=0 и 1 с вероятностями по 0.5 | ||
- | |||
- | Учитывая данные в задаче числа, показывающие количество единиц, двоек и троек, получаем, что нужно максимизировать следующую функцию: | ||
- | |||
- | <math> | ||
- | 30*log(g*a)+60*log(b*(1-g))+20*(0.5*log(g*(1-a)) + 0.5*log((1-g)*(1-b))) | ||
- | </math> | ||
- | |||
- | Для поиска максимума нужно взять производные по a, b, g приравнять их к нулю. После первой итерации получаем новые значения: | ||
- | |||
- | a=3/4 | ||
- | |||
- | b=6/7 | ||
- | |||
- | g=4/11 | ||
- | |||
- | Второй шаг. С учетом нового начального приближения, вероятности 1, 2 и 3 - 3/11, 2/11 и 6/11 соответственно. | ||
- | |||
- | Распределения скрытой компоненты рассчитываются аналогично, для X=1 и 3 отличий нет, для X=2 формула новая, но значения вероятностей тоже совпадают с первым шагом: | ||
- | |||
- | P(Z=0)=g*(1-a) / (g*(1-a)+(1-g)*(1-b )) = (4/11 * 1/4) / (2/11) = 1/2 | ||
- | |||
- | Таким образом, функция для оптимизации будет такая же, как на предыдущем шаге. Алгоритм сошелся за два шага. | ||
- | |||
- | Ответ: | ||
- | |||
- | a=3/4 | ||
- | |||
- | b=6/7 | ||
- | |||
- | g=4/11 | ||
== Задача 11. == | == Задача 11. == | ||
Строка 334: | Строка 232: | ||
То есть наиболее вероятная последовательность состояний: 1-1-1-1-1-2-2 | То есть наиболее вероятная последовательность состояний: 1-1-1-1-1-2-2 | ||
- | == Задача | + | == Задача 14. Алгоритм вперед-назад == |
=== Решение === | === Решение === | ||
Описание алгоритма с простыми обозначениями можно прочитать здесь: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%B0%D1%83%D0%BC%D0%B0-%D0%92%D0%B5%D0%BB%D1%88%D0%B0] | Описание алгоритма с простыми обозначениями можно прочитать здесь: [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%B0%D1%83%D0%BC%D0%B0-%D0%92%D0%B5%D0%BB%D1%88%D0%B0] | ||
Строка 354: | Строка 252: | ||
1: 0.4664 и 0.1576 | 1: 0.4664 и 0.1576 | ||
- | Нормировочные константы: | ||
- | |||
- | 3: 0.09536 | ||
- | |||
- | 2: 0.20176 | ||
- | |||
- | 1: 0.20232 | ||
- | |||
- | И наконец, маргинальные распределения (гамма нулевое - вероятность того, что система была в состоянии 0): | ||
- | |||
- | Для t3: 0 с вероятностью ~0.58 | ||
- | |||
- | Для t2: 0 с вероятностью ~0.919 | ||
- | |||
- | Для t1: 0 с вероятностью ~0.922 | ||
{{Курс МОТП}} | {{Курс МОТП}} |