Редактирование: МОТП, Задачи на экзамене
Материал из 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. == | ||
Строка 242: | Строка 140: | ||
== Задача 13. == | == Задача 13. == | ||
- | === Решение === | ||
all.pdf, страницы 168-169. | all.pdf, страницы 168-169. | ||
Строка 258: | Строка 155: | ||
24/99 ~75/99 | 24/99 ~75/99 | ||
</math> | </math> | ||
- | |||
- | == Задача 14. Алгоритм Витерби == | ||
- | Программа на python, решающая задачу (алгоритм взят из [http://en.wikipedia.org/wiki/Viterbi_algorithm]) | ||
- | <pre> | ||
- | # Helps visualize the steps of Viterbi. | ||
- | def print_dptable(V): | ||
- | print " ", | ||
- | for i in range(len(V)): print "%7s" % ("%d" % i), | ||
- | print | ||
- | |||
- | for y in V[0].keys(): | ||
- | print "%.5s: " % y, | ||
- | for t in range(len(V)): | ||
- | print "%.7s" % ("%f" % V[t][y]), | ||
- | print | ||
- | |||
- | def viterbi(obs, states, start_p, trans_p, emit_p): | ||
- | V = [{}] | ||
- | path = {} | ||
- | |||
- | # Initialize base cases (t == 0) | ||
- | for y in states: | ||
- | V[0][y] = start_p[y] * emit_p[y][obs[0]] | ||
- | path[y] = [y] | ||
- | |||
- | # Run Viterbi for t > 0 | ||
- | for t in range(1,len(obs)): | ||
- | V.append({}) | ||
- | newpath = {} | ||
- | |||
- | for y in states: | ||
- | (prob, state) = max([(V[t-1][y0] * trans_p[y0][y] * emit_p[y][obs[t]], y0) for y0 in states]) | ||
- | V[t][y] = prob | ||
- | newpath[y] = path[state] + [y] | ||
- | |||
- | # Don't need to remember the old paths | ||
- | path = newpath | ||
- | |||
- | print_dptable(V) | ||
- | (prob, state) = max([(V[len(obs) - 1][y], y) for y in states]) | ||
- | return (prob, path[state]) | ||
- | |||
- | states = ('first', 'second') | ||
- | |||
- | observations = ('0', '0', '1', '0', '0', '1', '1') | ||
- | |||
- | start_probability = {'first': 0.5, 'second': 0.5} | ||
- | |||
- | transition_probability = { | ||
- | 'first' : {'first': 0.9, 'second': 0.1}, | ||
- | 'second' : {'first': 0.2, 'second': 0.8}, | ||
- | } | ||
- | |||
- | emission_probability = { | ||
- | 'first' : {'0': 0.8, '1': 0.2}, | ||
- | 'second' : {'0': 0.2, '1': 0.8}, | ||
- | } | ||
- | |||
- | def example(): | ||
- | return viterbi(observations, | ||
- | states, | ||
- | start_probability, | ||
- | transition_probability, | ||
- | emission_probability) | ||
- | print example() | ||
- | </pre> | ||
- | Вывод программы: | ||
- | <pre> | ||
- | 0 1 2 3 4 5 6 | ||
- | secon: 0.10000 0.01600 0.02304 0.00368 0.00074 0.00215 0.00137 | ||
- | first: 0.40000 0.28800 0.05184 0.03732 0.02687 0.00483 0.00087 | ||
- | (0.0013759414272000007, ['first', 'first', 'first', 'first', 'first', 'second', 'second']) | ||
- | </pre> | ||
- | |||
- | То есть наиболее вероятная последовательность состояний: 1-1-1-1-1-2-2 | ||
- | |||
- | == Задача 15. Алгоритм вперед-назад == | ||
- | === Решение === | ||
- | Описание алгоритма с простыми обозначениями можно прочитать здесь: [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] | ||
- | |||
- | Значения "альфы" (первой и второй) на каждом шаге: | ||
- | |||
- | 1: 0.4 и 0.1 | ||
- | |||
- | 2: 0.304 и 0.024 | ||
- | |||
- | 3: 0.05568 и 0.03968 | ||
- | |||
- | Значения "беты" на каждом шаге, от третьего к первому: | ||
- | |||
- | 3: 1 и 1 | ||
- | |||
- | 2: 0.61 и 0.68 | ||
- | |||
- | 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 | ||
{{Курс МОТП}} | {{Курс МОТП}} |