Редактирование: МОТП, Билеты (2009)

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

Перейти к: навигация, поиск

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

ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 77 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

Текущая версия Ваш текст
Строка 144: Строка 144:
== Марковские сети. Примеры.==
== Марковские сети. Примеры.==
==Скрытые марковские модели. Обучение СММ с учителем.==
==Скрытые марковские модели. Обучение СММ с учителем.==
 +
==Алгоритм динамического программирования и его применение в скрытых марковских моделях.==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%BA%D1%80%D1%8B%D1%82%D0%B0%D1%8F_%D0%BC%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D1%8C На википедии]
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%BA%D1%80%D1%8B%D1%82%D0%B0%D1%8F_%D0%BC%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D1%8C На википедии]
-
* [http://ru.wikibooks.org/wiki/%D0%A1%D0%BA%D1%80%D1%8B%D1%82%D1%8B%D0%B5_%D0%BC%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8 На викибуки]
+
* [http://ru.wikibooks.org/wiki/%D0%A1%D0%BA%D1%80%D1%8B%D1%82%D1%8B%D0%B5_%D0%BC%D0%B0%D1%80%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8 Викибуки]
 +
* '''Лекция 3, стр. 9-28'''
 +
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%92%D0%B8%D1%82%D0%B5%D1%80%D0%B1%D0%B8 Алгоритм Витерби] - очень хорошо для понимания зачем все это надо
 +
* [http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Динамическое программирование]
 +
 
 +
'''Общие сведения'''<br>
 +
''Динамическое программирование'' в математике и теории вычислительных систем — метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами, который намного эффективнее, чем решение «в лоб». <br>
 +
<br>
-
<br/>
+
''Скрытая Марковская модель'' (первого порядка) — это вероятностная модель последовательности, которая
-
'''Скрытая Марковская модель''' (первого порядка) — это вероятностная модель последовательности, которая:
+
* Состоит из набора наблюдаемых переменных <math> X = {x_1 , \dots , x_N }, n_n \in R_d</math> и латентных (скрытых) переменных <math>T = {t_1, \dots, t_N },\;t_n \in \{0, 1\}^K,\;\sum_{j = 1}^{K}t_{nj}=1</math>.
-
# состоит из набора наблюдаемых переменных <math> X = {x_1 , \dots , x_N }, n_n \in R_d</math> и латентных (скрытых) переменных <math>T = {t_1, \dots, t_N },\;t_n \in \{0, 1\}^K,\;\sum_{j = 1}^{K}t_{nj}=1</math>.
+
* Латентные переменные T являются бинарными и кодируют K состояний, поэтому их иногда называют переменными состояния.
-
# латентные переменные T являются бинарными и кодируют K состояний, поэтому их иногда называют переменными состояния.
+
* Значение наблюдаемого вектора <math>x_n</math> , взятого в момент времени <math>n</math>, зависит только от скрытого состояния <math>t_n</math>, которое в свою очередь зависит только от скрытого состояния в предыдущий момент времени <math>t_{n-1}</math>.
-
# значение наблюдаемого вектора <math>x_n</math> , взятого в момент времени <math>n</math>, зависит только от скрытого состояния <math>t_n</math>, которое в свою очередь зависит только от скрытого состояния в предыдущий момент времени <math>t_{n-1}</math>.
+
* Для полного задания модели достаточно задать все условные распределения вида <math>p(x_n |t_n ),\;p(t_n |t_{n-1})</math> и априорное распределение <math>p(t_1)</math>.
-
# для полного задания модели достаточно задать все условные распределения вида <math>p(x_n |t_n ),\;p(t_n |t_{n-1})</math> и априорное распределение <math>p(t_1)</math>.
+
Пусть имеется <math>K</math> возможных состояний. Закодируем состояние в каждый момент времени <math>n</math> бинарным вектором <math>t_n = (t_{n1},\dots, t_{nK})</math>, где <math>t_{nj} = 1</math>, если в момент <math>n</math> модель находится в состоянии <math>j</math> и <math>t_{nj} = 0</math>, иначе.
Пусть имеется <math>K</math> возможных состояний. Закодируем состояние в каждый момент времени <math>n</math> бинарным вектором <math>t_n = (t_{n1},\dots, t_{nK})</math>, где <math>t_{nj} = 1</math>, если в момент <math>n</math> модель находится в состоянии <math>j</math> и <math>t_{nj} = 0</math>, иначе.
Строка 159: Строка 166:
p(t_n |t_{n-1}) = \prod_{i=1}^K\prod_{j=1}^K A_{ij}^{t_{n-1,i}t_{nj}}
p(t_n |t_{n-1}) = \prod_{i=1}^K\prod_{j=1}^K A_{ij}^{t_{n-1,i}t_{nj}}
</math>
</math>
-
Пусть в первый момент времени <math>p(t_{1j} = 1) = \pi_j</math>. Тогда <math> p(t_1) = \prod_{j=1}^K \pi_j^{t_{1j}}</math>
+
Пусть в первый момент времени <math>p(t_{1j} = 1) = \pi_j</math>. Тогда
 +
<math>
 +
p(t_1) = \prod_{j=1}^K \pi_j^{t_{1j}}
 +
</math>
* Хотя матрица A может быть произвольного вида с учетом ограничений на неотрицательность и сумму элементов строки, с точки зрения СММ представляет интерес диагональное преобладание матрицы перехода.
* Хотя матрица A может быть произвольного вида с учетом ограничений на неотрицательность и сумму элементов строки, с точки зрения СММ представляет интерес диагональное преобладание матрицы перехода.
Строка 167: Строка 177:
* Условное распределение <math>p(x_n |t_n)</math> определяется текущим состоянием <math>t_n</math>
* Условное распределение <math>p(x_n |t_n)</math> определяется текущим состоянием <math>t_n</math>
* Обычно предполагают, что оно нам известно с точностью до параметров <math>\phi_k,\;k \in \{1,\dots, K\}</math>, т.е. если <math>t_{n1} = 1</math>, то <math>x_n</math> взят из распределения <math>p(x_n |\phi_1 )</math>, если <math>t_{n2} = 1</math>, то <math>x_n</math> взят из распределения <math>p(x_n |\phi_2 )</math>, и т.д.
* Обычно предполагают, что оно нам известно с точностью до параметров <math>\phi_k,\;k \in \{1,\dots, K\}</math>, т.е. если <math>t_{n1} = 1</math>, то <math>x_n</math> взят из распределения <math>p(x_n |\phi_1 )</math>, если <math>t_{n2} = 1</math>, то <math>x_n</math> взят из распределения <math>p(x_n |\phi_2 )</math>, и т.д.
-
* Таким образом <math> p(x_n |t_n) = \prod_{j=1}^K(p(x_n |\phi_k ))^{t_{nk}} </math>
+
* Таким образом
 +
<math>
 +
p(x_n |t_n) = \prod_{j=1}^K(p(x_n |\phi_k ))^{t_{nk}}
 +
</math>
Обозначим полный набор параметров <math>\Theta = \{\pi, A, \phi\}</math>.
Обозначим полный набор параметров <math>\Theta = \{\pi, A, \phi\}</math>.
-
'''Обучение с учителем'''. Известна некоторая последовательность <math>X</math>, для которой заданы <math>T</math>. '''Задача состоит''' в оценке по обучающей выборке набора параметров <math>\Theta</math>.
+
'''Собственно, билет'''<br>
-
 
+
-
==Алгоритм динамического программирования и его применение в скрытых марковских моделях.==
+
-
* см. '''Лекция 3, стр. 9-28'''
+
-
<br/>
+
-
'''Динамическое программирование''' в математике и теории вычислительных систем — метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами, который намного эффективнее, чем решение «в лоб». ([http://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 дин. прогр. на вики])
+
-
 
+
-
 
+
-
'''Собственно, билет'''.
+
* Пусть известна некоторая последовательность наблюдений <math>X</math> и набор параметров СММ <math>\Theta</math>. Требуется определить наиболее вероятную последовательность состояний <math>T</math>, т.е. найти <math>arg\;max_T p(T|X, \Theta)</math>.
* Пусть известна некоторая последовательность наблюдений <math>X</math> и набор параметров СММ <math>\Theta</math>. Требуется определить наиболее вероятную последовательность состояний <math>T</math>, т.е. найти <math>arg\;max_T p(T|X, \Theta)</math>.
* Заметим, что <math>p(X|\Theta)</math> не зависит от <math>T</math>, поэтому <math>arg\;max_T p(T|X, \Theta) = arg\;max_T \frac{p(X, T|\Theta)}{p(X|\Theta)} = arg\;max_T p(X, T|\Theta) = arg\;max_T log\,p(X, T|\Theta)</math>.
* Заметим, что <math>p(X|\Theta)</math> не зависит от <math>T</math>, поэтому <math>arg\;max_T p(T|X, \Theta) = arg\;max_T \frac{p(X, T|\Theta)}{p(X|\Theta)} = arg\;max_T p(X, T|\Theta) = arg\;max_T log\,p(X, T|\Theta)</math>.
* Но это же классическая задача динамического программирования!
* Но это же классическая задача динамического программирования!
<br>
<br>
-
''Алгоритм Витерби'' ([http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%92%D0%B8%D1%82%D0%B5%D1%80%D0%B1%D0%B8 Алгоритм Витерби на вики] - очень хорошо для понимания зачем все это надо)
+
''Алгоритм Витерби''<br>
-
 
+
Логарифм совместной плотности по распределению:
Логарифм совместной плотности по распределению:
<math>
<math>
Строка 216: Строка 220:
* Инициализируем <math>\theta</math> некоторыми начальным приближением
* Инициализируем <math>\theta</math> некоторыми начальным приближением
* Е-шаг: оцениваем распределение скрытой компоненты
* Е-шаг: оцениваем распределение скрытой компоненты
-
<math> p(T|X,\theta_{old})=\frac{p(X|T,\theta_{old})}{\sum_T p(X,T|\theta_{old})} </math>
+
<math> p(T|X,\theta_{old})=\frac{p(T|X,\theta_{old})}{\sum_T p(X,T|\theta_{old})} </math>
* M-шаг оптимизируем
* M-шаг оптимизируем
<math>\mathbb E_{T|X,\theta_{old}} log(p(X,T|\theta))=\sum_T p(X|T,\theta_{old})log( p(X,t|\theta)) \to \max_{\theta} </math> <br>
<math>\mathbb E_{T|X,\theta_{old}} log(p(X,T|\theta))=\sum_T p(X|T,\theta_{old})log( p(X,t|\theta)) \to \max_{\theta} </math> <br>

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!


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

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

Получено с http://esyr.us/wiki/%D0%9C%D0%9E%D0%A2%D0%9F%2C_%D0%91%D0%B8%D0%BB%D0%B5%D1%82%D1%8B_%282009%29
Личные инструменты
Разделы