МОТП, Задачи на экзамене

Материал из eSyr's wiki.

(Различия между версиями)

Версия 07:07, 26 мая 2010

Математические основы теории прогнозирования

Материалы по курсу
Билеты (2009) | Примеры задач (2009) | Примеры задач контрольной работы (2013) | Определения из теории вероятностей

За нерешение данных задач оценка снижается на балл. — Д. П. Ветров

Содержание

1 1. Вывод формул для векторного дифференцирования
- 1.1 Решение
2 3. Метод главных компонент (PCA)
- 2.1 Решение
3 4. Метод максимального правдоподобия (ММП)
- 3.1 Решение
  - 3.1.1 Вариант 1: неизвестный сдвиг, единичный масштаб
  - 3.1.2 Вариант 2: нулевой сдвиг, неизвестный масштаб
4 5. Линейная регрессия
- 4.1 Решение
5 6. Правило множителей Лангранжа
- 5.1 Решение

1. Вывод формул для векторного дифференцирования

Вывести (считаем все матрицы вещественными):

$\frac{\partial \bar{c}^T\bar{u}}{\partial \bar{u}}=\bar{c}$
$\frac{\partial\|A\bar{u}-\bar{f}\|^2}{\partial \bar{u}}=2A^TA\bar{u} - 2A^T\bar{f}$
$\frac{\partial^2\|A\bar{u}-\bar{f}\|^2}{\partial \bar{u}^2}=2A^TA$

Решение

Формула 1

$\bar{c}^T\bar{u}=\sum_{i=1}^nc_iu_i \Rightarrow \frac{\partial \bar{c}^T\bar{u}}{\partial u_i}=c_i \Rightarrow \frac{\partial \bar{c}^T{u}}{\partial \bar{u}} = \bar{c}$

Формула 2

Далее через $\bar{a}_i$ всюду обозначен столбец матрицы $A$ с номером $i$ .

$\|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}$

$\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 = (\bar{f},\bar{a}_i) = \bar{a}_i^T\bar{f} \Rightarrow \frac{\partial \bar{f}^TA\bar{u}}{\partial \bar{u}} = A^T\bar{f}$

$(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}$

$\frac{\partial\|A\bar{u}-\bar{f}\|^2}{\partial \bar{u}} = \frac{\partial (A\bar{u})^TA\bar{u}}{\partial \bar{u}} - 2 \frac{\partial \bar{f}^TA\bar{u}}{\partial \bar{u}} = 2A^TA\bar{u} - 2A^T\bar{f}$

Формула 3

Далее через $\bar{b}_i$ всюду обозначен столбец матрицы $B$ с номером $i$ .

$\frac{\partial^2\|A\bar{u}-\bar{f}\|^2}{\partial \bar{u}^2}=\frac{\partial 2A^TA\bar{u}}{\partial \bar{u}}=\frac{\partial B\bar{u}}{\partial \bar{u}}$

$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$

3. Метод главных компонент (PCA)

Даны р точек в двухмерном пространстве. Найти методом главных компонент первую главную компоненту.

Решение

Рассмотрим следующую задачу: $p = 5$ , $x 1 = (1,1)$ , $x 2 = (1,2)$ , $x 3 = (3,2)$ , $x 4 = (4,1)$ , $x 5 = (6,4)$ .

Находим $\bar{x}=\frac{1}{p}\sum_{i=1}^px_i=(3,2)$ .

Находим $S=\frac{1}{p}\sum_{i=1}^p(x_i-\bar{x})^T(x_i-\bar{x})= \frac{1}{5}\begin{pmatrix}18 && 7 \\ 7 && 6 \end{pmatrix}$

Решаем $|S-\lambda I| = 0 \Rightarrow \lambda=2.4\pm \sqrt{3.4}$ .

Находим собственный вектор, соответствующий $\lambda_1=2.4+\sqrt{3.4}$ , решая $(S-\lambda_1I)\hat{d}=0$ . Получаем $\hat{d}=(0.9085, 0.4179)$ — собственный вектор, соответствующий максимальному собственному значению матрицы ковариации. Он и будет являться первой главной компонентой.

4. Метод максимального правдоподобия (ММП)

Как метко заметил Оверрайдер, будут задачки на поиск оценки максимального правдоподобия. Не сложные, но чтобы было интереснее, не с нормальным распределением. Что-нибудь типа найти оценку МП на параметр распределения Лапласа.

Решение

Плотность распределения Лапласа: $p(x|b,\mu)=\frac{1}{2b}e^{-\frac{|x-\mu|}{b}}$ , $μ$ - сдвиг, $b$ - масштаб (подробнее в википедии).

Вариант 1: неизвестный сдвиг, единичный масштаб

Пусть есть распределение Лапласа с неизвестным матожиданием и единичным параметром масштаба. Дана выборка, взятая из этого распределения: $(x_1, x_2, \dots, x_n )$ . Оценим параметр μ.

Функция распределения запишется так: $p(x | \mu) = \frac{1}{2} e^{-|x - \mu|}$

Функция правдоподобия: $L(\mu) = p(\mu | x_1, x_2, \dots, x_n ) = \prod_{i = 1}^{n} \frac{1}{2} e^{-|x_i - \mu|}$

$\log L(\mu) = \sum_{i = 1}^{n}(-|x_i - \mu|) + const$

Покажем, что эта функция достигает максимума в точке $\mu = \mbox{med}(x_1, x_2, \dots, x_n )$ -- когда параметр равен медиане выборки.

Упорядочим выборку по возрастанию. Пусть теперь она выглядит так: $(x_1', x_2', \dots, x_n' )$ . Рассмотрим последнюю функцию на интервалах вида $(-\infty, x_1'), (x_1', x_2'), \dots, (x_{n-1}', x_n'), (x_n', +\infty),$ . На первом из них все функции под знаком суммы возрастают, итоговая производная равна n, на втором -- одна убывает, остальные возрастают, производная равна (n-2), и т.д. Переломный момент наступает в середине -- в одной точке перегиба (если n нечётно), или на центральном интервале производная равна 0 (если n чётно). После этого функция только убывает. Там и достигается максимум правдоподобия. Короче, нужно нарисовать график, и всё будет понятно: максимум правдоподобия достигается в точке, равной медиане выборки.

Вариант 2: нулевой сдвиг, неизвестный масштаб

$p(x|b)=\frac{1}{2b}e^{-\frac{|x|}{b}}=\frac{\lambda}{2}e^{-\lambda|x|}=p(x|\lambda)$

$p(X|\lambda)=\prod_{i=1}^n\frac{\lambda}{2}e^{-\lambda|x_i|}=\left(\frac{\lambda}{2}\right)^n\prod_{i=1}^ne^{-\lambda|x_i|}$

$\log p(X|\lambda)=n\log(\frac{\lambda}{2}) - \lambda\sum_{i=1}^n|x_i|=n\log\lambda-\lambda\sum_{i=1}^n|x_i| - n \log 2 \rightarrow \max_{\lambda}$

$\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|$

5. Линейная регрессия

Даны 3-4 точки в двухмерном пространстве - одна координата, это х, другая - t. Задача построить по ним линейную регрессию вида $\hat{t}=kx+b$ , т.е. найти коэффициенты $k$ и $b$ .

Решение

$E(T,X,k,b)=\sum_{i=1}^n(t_i-kx_i-b)^2$

$\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$

$\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$

$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)$

Подставляем значения для $x i$ и $t i$ , получаем $k$ , затем $b$ . Решение проверено на нескольких наборах данных в MATLAB.

Еще один вариант - посчитать напрямую $(k, b) = (X T X) - 1 X T Y$ , где $X$ - матрица, первый столбец которой составлен из $x i$ , второй - из единиц, а $Y$ - столбец из $t i$ .

6. Правило множителей Лангранжа

Обязательно кому-то дам задачку на условную максимизацию квадратичной функции с линейным ограничением в виде равенства. Писанины там немного, но вот без правила множителей Лагранжа обойтись вряд ли удастся.

Решение

множители Лагранжа на вики

Пусть нам необходимо максимизировать функцию $f (x, y) = - 5 x 2 + 2 x y - 3 y 2$ при условии $x - y + 1 = 0$ .

Запишем функцию Лагранжа $F(x,y,\lambda)=-5x^2+2xy-3y^2+\lambda(x-y+1) \rightarrow \max_{x,y,\lambda}$ .

Приравняем частные производные к нулю:

$\begin{cases} \frac{\partial F}{\partial x}=-10x+2y+\lambda=0 \\ \frac{\partial F}{\partial y}=2x-6y-\lambda=0 \\ \frac{\partial F}{\partial \lambda}=x-y+1=0 \end{cases} \Rightarrow$

$\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}$ .

(По-моему, гораздо проще без функции Лагранжа: $y = x + 1; f (x) = - 6 x 2 - 4 x - 3; x = - b / 2 a = - 4 / 12 = - 1 / 3$ )

Математические основы теории прогнозирования

Получено с http://esyr.org/wiki/%D0%9C%D0%9E%D0%A2%D0%9F%2C_%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BD%D0%B0_%D1%8D%D0%BA%D0%B7%D0%B0%D0%BC%D0%B5%D0%BD%D0%B5

@@ Строка 3: / Строка 3: @@
 ''За нерешение данных задач оценка снижается на балл.'' — Д.&nbsp;П.&nbsp;Ветров
-==Вывод формул для векторного дифференцирования==
+==1. Вывод формул для векторного дифференцирования==
 Вывести (считаем все матрицы вещественными):
@@ Строка 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>
-==Метод главных компонент (PCA)==
+==3. Метод главных компонент (PCA)==
 Даны ''р'' точек в двухмерном пространстве. Найти методом главных компонент первую главную компоненту.
@@ Строка 51: / Строка 51: @@
 Находим собственный вектор, соответствующий <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> — собственный вектор, соответствующий максимальному собственному значению матрицы ковариации. Он и будет являться первой главной компонентой.
-==Метод максимального правдоподобия (ММП)==
+== 4. Метод максимального правдоподобия (ММП)==
 Как метко заметил Оверрайдер, будут задачки на поиск оценки максимального правдоподобия. Не сложные, но чтобы было интереснее, не с нормальным распределением. Что-нибудь типа найти оценку МП на параметр распределения Лапласа.
@@ Строка 81: / Строка 81: @@
 <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>
-==Правило множителей Лангранжа==
+==5. Линейная регрессия==
+Даны 3-4 точки в двухмерном пространстве - одна координата, это х, другая - t. Задача построить по ним линейную регрессию вида <math>\hat{t}=kx+b</math>, т.е. найти коэффициенты <math>k</math> и <math>b</math>.
+===Решение===
+<math>E(T,X,k,b)=\sum_{i=1}^n(t_i-kx_i-b)^2</math>
+<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>.
+==6. Правило множителей Лангранжа==
 Обязательно кому-то дам задачку на условную максимизацию квадратичной функции с линейным ограничением в виде равенства. Писанины там немного, но вот без правила множителей Лагранжа обойтись вряд ли удастся.
@@ Строка 106: / Строка 123: @@
 (По-моему, гораздо проще без функции Лагранжа: <math>y=x+1; f(x)=-6x^2-4x-3; x=-b/2a=-4/12=-1/3</math>)
-==Линейная регрессия==
-Даны 3-4 точки в двухмерном пространстве - одна координата, это х, другая - t. Задача построить по ним линейную регрессию вида <math>\hat{t}=kx+b</math>, т.е. найти коэффициенты <math>k</math> и <math>b</math>.
-===Решение===
-<math>E(T,X,k,b)=\sum_{i=1}^n(t_i-kx_i-b)^2</math>
-<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>.
 {{Курс МОТП}}

МОТП, Задачи на экзамене

Материал из eSyr's wiki.

Версия 07:07, 26 мая 2010

Содержание

1. Вывод формул для векторного дифференцирования

Решение

Формула 1

Формула 2

Формула 3

3. Метод главных компонент (PCA)

Решение

4. Метод максимального правдоподобия (ММП)

Решение

Вариант 1: неизвестный сдвиг, единичный масштаб

Вариант 2: нулевой сдвиг, неизвестный масштаб

5. Линейная регрессия

Решение

6. Правило множителей Лангранжа

Решение

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты