Редактирование: МОТП, Задачи на экзамене

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

Версия от 22:58, 16 ноября 2009; 92.243.167.93 (Обсуждение)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

ПРЕДУПРЕЖДЕНИЕ: Вы редактируете устаревшую версию данной страницы. После сохранения страницы будут потеряны изменения, сделанные в последующих версиях.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

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

==Вывод формул для векторного дифференцирования==
Вывести (считаем все матрицы вещественными):

# <math>\frac{\partial \bar{c}^T\bar{u}}{\partial \bar{u}}=\bar{c}</math>
# <math>\frac{\partial\|A\bar{u}-\bar{f}\|^2}{\partial \bar{u}}=2A^TA\bar{u} - 2A^T\bar{f}</math>
# <math>\frac{\partial^2\|A\bar{u}-\bar{f}\|^2}{\partial \bar{u}^2}=2A^TA</math>

===Решение===

====Формула 1====
<math>\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}</math>

====Формула 2====
Далее через <math>\bar{a}_i</math> всюду обозначен столбец матрицы <math>A</math> с номером <math>i</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 = (\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}</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>\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}</math>

====Формула 3====
Далее через <math>\bar{b}_i</math> всюду обозначен столбец матрицы <math>B</math> с номером <math>i</math>.

<math>\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}}</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)==
Даны ''р'' точек в двухмерном пространстве. Найти методом главных компонент первую главную компоненту.

===Решение===

Рассмотрим следующую задачу: <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>
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}
</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>p(x|b,\mu)=\frac{1}{2b}e^{-\frac{|x-\mu|}{b}}</math>, <math>\mu</math> - сдвиг, <math>b</math> - масштаб (подробнее в [http://en.wikipedia.org/wiki/Laplace_distribution википедии]).

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

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

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

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

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

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

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

<math>p(x|b)=\frac{1}{2b}e^{-\frac{|x|}{b}}=\frac{\lambda}{2}e^{-\lambda|x|}=p(x|\lambda)</math>

<math>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|}</math>

<math>\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}</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>

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

===Решение===

[http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B8%D1%82%D0%B5%D0%BB%D0%B5%D0%B9_%D0%9B%D0%B0%D0%B3%D1%80%D0%B0%D0%BD%D0%B6%D0%B0 множители Лагранжа на вики]

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

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

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

<math>
\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
</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>.

(По-моему, гораздо проще без функции Лагранжа: <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>\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:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице: