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

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

(Различия между версиями)
Перейти к: навигация, поиск
(ММП)
Строка 1: Строка 1:
-
Д.П.Ветров: За нерешение данных задач оценка снижается на балл.
+
''За нерешение данных задач оценка снижается на балл.'' — Д. П. Ветров
==Метод главных компонент (PCA)==
==Метод главных компонент (PCA)==

Версия 08:19, 26 мая 2009

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

Содержание

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

1. Даны р точек в двухмерном пространстве (буду прямо их ручкой у вас на листочке задавать). Найти методом главных компонент первую главную компоненту. Так что вспоминайте как матрицу 2х2 к главным осям приводить и ковариации считать.

Решение:

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

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

Находим S=\frac{1}{p}\sum_{i=1}^p(x_i-\hat{x})^T(x_i-\hat{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) - собственный вектор, соответствующий максимальному собственному значению матрицы ковариации. Он и будет являться первой главной компонентой.

Подробные вычисления не приведены. Можете сами повторить и сверить результаты. Однако сильно не надейтесь найти ошибку, решение проверено в MATLAB.

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

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

Решение:

Кому, как ни мне, привести пример. :) Overrider 07:48, 26 мая 2009 (UTC)

Пусть есть распределение Лапласа Laplace(μ,0) с неизвестным матожиданием и единичным параметром масштаба (о нём можно узнать из википедии). Дана выборка, взятая из этого распределения: (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. Там и достигается максимум правдоподобия. Короче, нужно нарисовать график, и всё будет понятно: максимум правдоподобия достигается в точке, равной медиане выборки.

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

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

Решение:

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

4. Даны 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)

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

Еще один вариант - посчитать напрямую (k,b) = (XTX) − 1XTY, где X - матрица, первый столбец которой составлен из xi, второй - из единиц, а Y - столбец из ti.

Получено с 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
Личные инструменты
Разделы