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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Решение)
Строка 243: Строка 243:
3: 0.05568 и 0.03968
3: 0.05568 и 0.03968
 +
 +
Значения "беты" на каждом шаге, от третьего к первому:
 +
 +
3: 1 и 1
 +
 +
2: 0.61 и 0.68
 +
 +
1: 0.4664 и 0.1576
 +
{{Курс МОТП}}
{{Курс МОТП}}

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

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

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

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

Содержание

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

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

  1. \frac{\partial \bar{c}^T\bar{u}}{\partial \bar{u}}=\bar{c}
  2. \frac{\partial\|A\bar{u}-\bar{f}\|^2}{\partial \bar{u}}=2A^TA\bar{u} - 2A^T\bar{f}
  3. \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, x1 = (1,1), x2 = (1,2), x3 = (3,2), x4 = (4,1), x5 = (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)

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

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

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

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

Решение

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

Пусть нам необходимо максимизировать функцию f(x,y) = − 5x2 + 2xy − 3y2 при условии 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) = − 6x2 − 4x − 3;x = − b / 2a = − 4 / 12 = − 1 / 3)

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

Оценка МП %pi - значение первой скрытой переменной, оно нам дано, поэтому вероятность P(t11 = 1) = 1,P(t12 = 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

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

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

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