Редактирование: МОТП, Задачи на экзамене
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 3: | Строка 3: | ||
''За нерешение данных задач оценка снижается на балл.'' — Д. П. Ветров | ''За нерешение данных задач оценка снижается на балл.'' — Д. П. Ветров | ||
- | == | + | ==Вывод формул для векторного дифференцирования== |
Вывести (считаем все матрицы вещественными): | Вывести (считаем все матрицы вещественными): | ||
Строка 20: | Строка 20: | ||
<math>\|A\bar{u}-\bar{f}\|^2 = (A\bar{u}-\bar{f})^T(A\bar{u}-\bar{f})=(A\bar{u})^TA\bar{u}-2\bar{f}^TA\bar{u}+\bar{f}^T\bar{f}</math> | <math>\|A\bar{u}-\bar{f}\|^2 = (A\bar{u}-\bar{f})^T(A\bar{u}-\bar{f})=(A\bar{u})^TA\bar{u}-2\bar{f}^TA\bar{u}+\bar{f}^T\bar{f}</math> | ||
- | <math>\bar{f}^TA\bar{u}=\bar{f}^T(\bar{a}_1u_1+\dots+\bar{a}_nu_n) \Rightarrow \frac{\partial \bar{f}^TA\bar{u}}{\partial u_i} = \bar{f}^T\bar{a}_i | + | <math>\bar{f}^TA\bar{u}=\bar{f}^T(\bar{a}_1u_1+\dots+\bar{a}_nu_n) \Rightarrow \frac{\partial \bar{f}^TA\bar{u}}{\partial u_i} = \bar{f}^T\bar{a}_i \Rightarrow \frac{\partial \bar{f}^TA\bar{u}}{\partial \bar{u}} = \bar{f}^TA</math> |
<math>(A\bar{u})^TA\bar{u}=(\bar{a}_1u_1+\dots+\bar{a}_nu_n)^T(\bar{a}_1u_1+\dots+\bar{a}_nu_n)=\sum_{i=1}^n\sum_{j=1}^nu_iu_j\bar{a}_i^T\bar{a}_j \Rightarrow \frac{\partial (A\bar{u})^TA\bar{u}}{\partial u_i} = 2\sum_{j=1}^nu_j\bar{a}_i^T\bar{a}_j \Rightarrow \frac{\partial (A\bar{u})^TA\bar{u}}{\partial \bar{u}}=2A^TA\bar{u}</math> | <math>(A\bar{u})^TA\bar{u}=(\bar{a}_1u_1+\dots+\bar{a}_nu_n)^T(\bar{a}_1u_1+\dots+\bar{a}_nu_n)=\sum_{i=1}^n\sum_{j=1}^nu_iu_j\bar{a}_i^T\bar{a}_j \Rightarrow \frac{\partial (A\bar{u})^TA\bar{u}}{\partial u_i} = 2\sum_{j=1}^nu_j\bar{a}_i^T\bar{a}_j \Rightarrow \frac{\partial (A\bar{u})^TA\bar{u}}{\partial \bar{u}}=2A^TA\bar{u}</math> | ||
Строка 33: | Строка 33: | ||
<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> | ||
- | == | + | ==Метод главных компонент (PCA)== |
- | + | Даны р точек в двухмерном пространстве (буду прямо их ручкой у вас на листочке задавать). Найти методом главных компонент первую главную компоненту. Так что вспоминайте как матрицу 2х2 к главным осям приводить и ковариации считать. | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | Даны | + | |
===Решение=== | ===Решение=== | ||
Строка 61: | Строка 40: | ||
Рассмотрим следующую задачу: <math>p=5</math>, <math>x_1=(1,1)</math>, <math>x_2=(1,2)</math>, <math>x_3=(3,2)</math>, <math>x_4=(4,1)</math>, <math>x_5=(6,4)</math>. | Рассмотрим следующую задачу: <math>p=5</math>, <math>x_1=(1,1)</math>, <math>x_2=(1,2)</math>, <math>x_3=(3,2)</math>, <math>x_4=(4,1)</math>, <math>x_5=(6,4)</math>. | ||
- | Находим <math>\bar{x}=\frac{1}{p}\sum_{i=1}^px_i=(3,2)</math>. | + | Находим<math> \bar{x}=\frac{1}{p}\sum_{i=1}^px_i=(3,2)</math>. |
Находим <math> | Находим <math> | ||
Строка 68: | Строка 47: | ||
</math> | </math> | ||
- | Решаем <math>|S-\lambda I| = 0 \Rightarrow \lambda=2.4\pm \sqrt{3.4}</math> | + | Решаем <math>|S-\lambda I| = 0 \Rightarrow \lambda=2.4\pm \sqrt{3.4}</math> |
- | Находим собственный вектор, соответствующий <math>\lambda_1=2.4+\sqrt{3.4}</math>, решая <math>(S-\lambda_1I)\hat{d}=0</math>. Получаем <math>\hat{d}=(0.9085, 0.4179)</math> | + | Находим собственный вектор, соответствующий <math>\lambda_1=2.4+\sqrt{3.4}</math>, решая <math>(S-\lambda_1I)\hat{d}=0</math>. Получаем <math>\hat{d}=(0.9085, 0.4179)</math> - собственный вектор, соответствующий максимальному собственному значению матрицы ковариации. Он и будет являться первой главной компонентой. |
- | == | + | Подробные вычисления не приведены. Можете сами повторить и сверить результаты. Однако сильно не надейтесь найти ошибку, решение проверено в MATLAB. |
+ | |||
+ | ==Метод максимального правдоподобия (ММП)== | ||
Как метко заметил Оверрайдер, будут задачки на поиск оценки максимального правдоподобия. Не сложные, но чтобы было интереснее, не с нормальным распределением. Что-нибудь типа найти оценку МП на параметр распределения Лапласа. | Как метко заметил Оверрайдер, будут задачки на поиск оценки максимального правдоподобия. Не сложные, но чтобы было интереснее, не с нормальным распределением. Что-нибудь типа найти оценку МП на параметр распределения Лапласа. | ||
Строка 102: | Строка 83: | ||
<math>\frac{\partial \log p(X|\lambda)}{\partial \lambda}=\frac{n}{\lambda}-\sum_{i=1}^n|x_i|=0 \Rightarrow \frac{1}{\lambda}=\frac{1}{n}\sum_{i=1}^n|x_i|</math> | <math>\frac{\partial \log p(X|\lambda)}{\partial \lambda}=\frac{n}{\lambda}-\sum_{i=1}^n|x_i|=0 \Rightarrow \frac{1}{\lambda}=\frac{1}{n}\sum_{i=1}^n|x_i|</math> | ||
- | == | + | ==Правило множителей Лангранжа== |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
Обязательно кому-то дам задачку на условную максимизацию квадратичной функции с линейным ограничением в виде равенства. Писанины там немного, но вот без правила множителей Лагранжа обойтись вряд ли удастся. | Обязательно кому-то дам задачку на условную максимизацию квадратичной функции с линейным ограничением в виде равенства. Писанины там немного, но вот без правила множителей Лагранжа обойтись вряд ли удастся. | ||
Строка 145: | Строка 107: | ||
<math>\Rightarrow x=y-1 \Rightarrow 2(y-1)-6y=-4y-2=\lambda \Rightarrow -10(y-1)+2y-4y-2=8-12y=0 \Rightarrow y=\frac{2}{3} \Rightarrow x=-\frac{1}{3}</math>. | <math>\Rightarrow x=y-1 \Rightarrow 2(y-1)-6y=-4y-2=\lambda \Rightarrow -10(y-1)+2y-4y-2=8-12y=0 \Rightarrow y=\frac{2}{3} \Rightarrow x=-\frac{1}{3}</math>. | ||
- | + | ==Линейная регрессия== | |
+ | Даны 3-4 точки в двухмерном пространстве - одна координата, это х, другая - t. Задача построить по ним линейную регрессию вида <math>\hat{t}=kx+b</math>, т.е. найти коэффициенты <math>k</math> и <math>b</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|Черновик]] | ||
- | == | + | <math>E(T,X,k,b)=\sum_{i=1}^n(t_i-kx_i-b)^2</math> |
- | + | ||
- | + | ||
- | + | ||
- | 1 | + | <math>\frac{\partial E(T,X,k,b)}{\partial k}=2\sum_{i=1}^n(t_i-kx_i-b)(-x_i)=0 \Rightarrow \sum_{i=1}^n(t_i-kx_i-b)x_i=0</math> |
- | + | <math>\frac{\partial E(T,X,k,b)}{\partial b}=2\sum_{i=1}^n(t_i-kx_i-b)(-1)=0 \Rightarrow \frac{1}{n}\sum_{i=1}^n(t_i-kx_i)=b</math> | |
- | + | <math>k \left(\sum_{i=1}^nx_i^2-\frac{1}{n}\left(\sum_{i=1}^nx_i\right)^2\right)=\sum_{i=1}^nt_ix_i-\frac{1}{n}\left(\sum_{i=1}^nx_i\right)\left(\sum_{i=1}^nt_i\right)</math> | |
- | + | Подставляем значения для <math>x_i</math> и <math>t_i</math>, получаем <math>k</math>, затем <math>b</math>. Решение проверено на нескольких наборах данных в MATLAB. | |
- | + | Еще один вариант - посчитать напрямую <math>(k,b)=(X^TX)^{-1}X^TY</math>, где <math>X</math> - матрица, первый столбец которой составлен из <math>x_i</math>, второй - из единиц, а <math>Y</math> - столбец из <math>t_i</math>. | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | <math> | + | |
- | + | ||
- | </math> | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | <math> | + | |
- | + | ||
- | </math> | + | |
- | + | ||
- | <math> | + | |
- | + | ||
- | </math> | + | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | Для t1: 0 с вероятностью ~0.922 | ||
{{Курс МОТП}} | {{Курс МОТП}} |