Редактирование: МОТП, Задачи на экзамене
Материал из 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. == | == Задача 10. == | ||
Строка 214: | Строка 163: | ||
Распределения скрытой компоненты рассчитываются аналогично, для X=1 и 3 отличий нет, для X=2 формула новая, но значения вероятностей тоже совпадают с первым шагом: | Распределения скрытой компоненты рассчитываются аналогично, для X=1 и 3 отличий нет, для X=2 формула новая, но значения вероятностей тоже совпадают с первым шагом: | ||
- | P(Z=0)=g*(1-a) / ( | + | P(Z=0)=g*(1-a) / (2/11) = (4/11 * 1/4) / (2/11) = 1/2 |
Таким образом, функция для оптимизации будет такая же, как на предыдущем шаге. Алгоритм сошелся за два шага. | Таким образом, функция для оптимизации будет такая же, как на предыдущем шаге. Алгоритм сошелся за два шага. | ||
Строка 334: | Строка 283: | ||
То есть наиболее вероятная последовательность состояний: 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] |