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

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

Версия от 12:36, 26 мая 2010; Juan sin tierra (Обсуждение | вклад)

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

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

Материалы по курсу
Билеты (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 Решение
6 Задача 10.
- 6.1 Решение
7 Задача 11.
- 7.1 Решение
8 Задача 13.
- 8.1 Решение
9 Задача 14. Алгоритм Витерби
10 Задача 14. Алгоритм вперед-назад
- 10.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$ )

Задача 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

Учитывая данные в задаче числа, показывающие количество единиц, двоек и троек, получаем, что нужно максимизировать следующую функцию:

$30 * l o g (g * a) + 60 * l o g (b * (1 - g)) + 20 * (0.5 * l o g (g * (1 - a)) + 0.5 * l o g ((1 - g) * (1 - b)))$

Для поиска максимума нужно взять производные по a, b, g приравнять их к нулю. После первой итерации получаем новые значения:

a=3/4

b=6/7

g=4/11

Задача 11.

Решение

P(a=0) = 0.6 ; P(b=0) = 0.592 ; P(a=0 & b=0) = 0.336

Вероятности получены сложение значений вероятностей всех комбинаций, где выполняется условие. Если бы a и b были независимы, то по определению, третья вероятность была бы произведением первых двух, но это не так, поэтому a и b не независимы.

Однако a и b независимы при с=0:

P(a=0 | c=0) = P(a=0 & c=0)/P(c=0) = 0.5 (определение условной вероятности)
P(b=0 | c=0) = 0.8
P(a=0 & b=0 | c=0) = P(a=0 & b=0 & c=0)/P(c=0) = 0.4 = P(a=0 | c=0) * P(b=0 | c=0)

Все остальные соотношения проверяются аналогично.

Задача 13.

Решение

all.pdf, страницы 168-169.

Оценка МП $% p i$ - значение первой скрытой переменной, оно нам дано, поэтому вероятность $P (t 11 = 1) = 1, P (t 12 = 1) = 0$ .

Оценка МП для матрицы A записана на странице 169. Содержательно эта формула означает следующее. Элемент A[i,j] - вероятность прехода из состояния i в состояние j. Оценка МП - отношение количества известных нам переходов из i в j к количеству раз, которые наблюдали систему в состоянии i. В данной задаче мы наблюдали состояние 1 100 раз, состояние 2 - 99 раз (последний раз не считается). Переход 1->2 наблюдали 25 раз, переход 1->1 - 75 раз, переход 2->1 - 24 раза, переход 2->2 - 75 раз.

Итого матрица A:

$75/100 ~ 25/100$

$24/99 ~75/99$

Задача 14. Алгоритм Витерби

Программа на python, решающая задачу (алгоритм взят из [1])

# 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()

Вывод программы:

           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'])

То есть наиболее вероятная последовательность состояний: 1-1-1-1-1-2-2

Задача 14. Алгоритм вперед-назад

Решение

Описание алгоритма с простыми обозначениями можно прочитать здесь: [2]

Значения "альфы" (первой и второй) на каждом шаге:

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

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

Получено с 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

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

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

Содержание

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

Решение

Формула 1

Формула 2

Формула 3

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

Решение

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

Решение

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

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

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

Решение

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

Решение

Задача 10.

Решение

Задача 11.

Решение

Задача 13.

Решение

Задача 14. Алгоритм Витерби

Задача 14. Алгоритм вперед-назад

Решение

Просмотры

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

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты