Графические модели (курс лекций)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
м
(оценки за задание 3)
Строка 61: Строка 61:
== Оценки ==
== Оценки ==
{|class = "standard sortable"
{|class = "standard sortable"
-
! class="unsortable"|№ п/п !! Студент !! Задание 1 (3 балла) !! Задание 2 (4 балла) !! Задание 3 !! Задание 4 !! Задание 5 !!Сумма
+
! class="unsortable"|№ п/п !! Студент !! Задание 1 (3 балла) !! Задание 2 (4 балла) !! Задание 3 (4 балла) !! Задание 4 !! Задание 5 !!Сумма
|-
|-
-
| align="center"|1 || Александров Я. || 2 || 2.5 || на проверке || на проверке || ||
+
| align="center"|1 || Александров Я. || 2 || 2.5 || 3 || на проверке || ||
|-
|-
-
| align="center"|2 || Артюхин С. || 3 || 3 || на проверке || на проверке || ||
+
| align="center"|2 || Артюхин С. || 3 || 3 || 4 || на проверке || ||
|-
|-
| align="center"|3 || Бобрик К. || 3 || 2.5 || || на проверке || ||
| align="center"|3 || Бобрик К. || 3 || 2.5 || || на проверке || ||
|-
|-
-
| align="center"|4 || Гаврилюк К. || 3 || 3 || на проверке || на проверке || ||
+
| align="center"|4 || Гаврилюк К. || 3 || 3 || 4 || на проверке || ||
|-
|-
-
| align="center"|5 || Елшин Д. || 3 || 3 || на проверке || на проверке || ||
+
| align="center"|5 || Елшин Д. || 3 || 3 || 4 || на проверке || ||
|-
|-
-
| align="center"|6 || Ермушева А. || 2 || 2.5 || на проверке || на проверке || ||
+
| align="center"|6 || Ермушева А. || 2 || 2.5 || 2.5 || на проверке || ||
|-
|-
-
| align="center"|7 || Зимовнов А.|| 3 || 4 || на проверке || на проверке || ||
+
| align="center"|7 || Зимовнов А.|| 3 || 4 || 4 || на проверке || ||
|-
|-
| align="center"|8 || Игнатьев О. || 3 || 3 || || || ||
| align="center"|8 || Игнатьев О. || 3 || 3 || || || ||
|-
|-
-
| align="center"|9 || Кириллов А. || 3 || 3 || на проверке || на проверке || ||
+
| align="center"|9 || Кириллов А. || 3 || 3 || 4 || на проверке || ||
|-
|-
| align="center"|10 || Марченко Е.|| 3 || 3 || || на проверке || ||
| align="center"|10 || Марченко Е.|| 3 || 3 || || на проверке || ||
|-
|-
-
| align="center"|11 || Матвеева Д. || 3 || 3 || на проверке || на проверке || ||
+
| align="center"|11 || Матвеева Д. || 3 || 3 || 4 || на проверке || ||
|-
|-
-
| align="center"|12 || Меркулова Т. || 2.9 || 2.5 || на проверке || || ||
+
| align="center"|12 || Меркулова Т. || 2.9 || 2.5 || 3 || || ||
|-
|-
-
| align="center"|13 || Некрасов К. || 3 || 3.5 || на проверке || на проверке || ||
+
| align="center"|13 || Некрасов К. || 3 || 3.5 || 3 || на проверке || ||
|-
|-
-
| align="center"|14 || Новиков П. || 3 || 3 || на проверке || || ||
+
| align="center"|14 || Новиков П. || 3 || 3 || 3.5 || || ||
|-
|-
-
| align="center"|15 || Панов А. || 3 || 3 || на проверке || на проверке || ||
+
| align="center"|15 || Панов А. || 3 || 3 || 3.5 || на проверке || ||
|-
|-
-
| align="center"|16 || Плященко Е. || 2 || 4 || на проверке || на проверке || ||
+
| align="center"|16 || Плященко Е. || 2 || 4 || 3.5 || на проверке || ||
|-
|-
-
| align="center"|17 || Полежаев В. || 3 || 2.5 || на проверке || на проверке || ||
+
| align="center"|17 || Полежаев В. || 3 || 2.5 || 4 || на проверке || ||
|-
|-
| align="center"|18 || Сабурова М. || 3 || 3 || || на проверке || ||
| align="center"|18 || Сабурова М. || 3 || 3 || || на проверке || ||
|-
|-
-
| align="center"|19 || Соколов Е.|| 3 || 4 || на проверке || на проверке || ||
+
| align="center"|19 || Соколов Е.|| 3 || 4 || 4 || на проверке || ||
|-
|-
-
| align="center"|20 || Фигурнов М. || 3 || 3 || на проверке || на проверке || ||
+
| align="center"|20 || Фигурнов М. || 3 || 3 || 4 || на проверке || ||
|-
|-
-
| align="center"|21 || Цупков С. || 3 || 3.5 || на проверке || || ||
+
| align="center"|21 || Цупков С. || 3 || 3.5 || 3.5 || || ||
|-
|-
| align="center"|22 || Шанин И. || не получено || 1.5 || || || ||
| align="center"|22 || Шанин И. || не получено || 1.5 || || || ||
Строка 109: Строка 109:
| align="center"|23 || Львов С. (212) || 3 || не получено || || || ||
| align="center"|23 || Львов С. (212) || 3 || не получено || || || ||
|-
|-
-
| align="center"|24 || Ульянов Д. (212) || 3 || 4 || на проверке || на проверке || ||
+
| align="center"|24 || Ульянов Д. (212) || 3 || 4 ||2.75 || на проверке || ||
|-
|-
| align="center"|25 || Тихонов А. (517) || 0 || не получено || || || ||
| align="center"|25 || Тихонов А. (517) || 0 || не получено || || || ||

Версия 12:53, 24 апреля 2012


Курс посвящен математическим методам обработки информации, основанных на использовании внутренних взаимосвязей в данных и их последующем анализе. Эти методы широко используются при решении задач из разных прикладных областей, включая обработку изображений и видео, анализ социальных сетей, распознавание речи, машинное обучение. До 2011 года курс читался как спецкурс «Структурные методы анализа изображений и сигналов».

Лекторы: Д.П. Ветров, Д.А. Кропотов.

Семинарист: А.А. Осокин.

Расписание занятий

В 2012 году курс читается в весеннем семестре на факультете ВМиК МГУ по средам в ауд. 524, начало в 16-50.

ДатаЗанятиеМатериалы
8 февраля 2012 Лекция 1 «Графические модели: Байесовские и марковские сети» Презентация (PDF, 1.01 Мб)
15 февраля 2012  Лекция 2 «Точные методы вывода в ациклических графических моделях. Алгоритм Belief Propagation» Конспект (PDF, 64 Кб)
22 февраля 2012 Семинар 1
29 февраля 2012 Лекция 3 «Скрытые марковские модели. Алгоритм сегментации сигнала, обучение с учителем» Презентация (PDF, 700 Кб)
7 марта 2012 Лекция 4 «Задача фильтрации многомерных сигналов. Линейные динамические системы. Фильтр Калмана» Конспект (PDF, 281Кб)
14 марта 2012 Лекция 5 «ЕМ-алгоритм. Обучение скрытых марковских моделей и линейных динамических систем.» Презентация (PDF, 1.14 Мб)
21 марта 2012 Лекция 6 «Алгоритмы на основе разрезов графов, \alpha-расширение.» Презентация (PDF, 618 Кб)
28 марта 2012 Лекция 7 «Приближенные методы вывода в циклических графических моделях. Алгоритм Tree-ReWeighted Message Passing (TRW)» Конспект лекции (PDF, 86Кб)
4 апреля 2012 Семинар 2
11 апреля 2012 Лекция 8 «Структурный метод опорных векторов» Конспект (PDF, 103Кб)
18 апреля 2012 Лекция 9 «Методы Монте Карло по схеме марковских цепей»
25 апреля 2012 Семинар 3
2 мая 2012
16 мая 2012 Лекция 10 «Вариационный вывод»

Практические задания

Задание 1. «Алгоритмы передачи сообщений».

Задание 2. «Динамические системы и фильтр Калмана».

Задание 3. «TRW и α-расширение».

Задание 4. «Разрезы графов и двойственное разложение».

Задание 5. «Структурное обучение».

Оценки

№ п/п Студент Задание 1 (3 балла) Задание 2 (4 балла) Задание 3 (4 балла) Задание 4 Задание 5 Сумма
1 Александров Я. 2 2.5 3 на проверке
2 Артюхин С. 3 3 4 на проверке
3 Бобрик К. 3 2.5 на проверке
4 Гаврилюк К. 3 3 4 на проверке
5 Елшин Д. 3 3 4 на проверке
6 Ермушева А. 2 2.5 2.5 на проверке
7 Зимовнов А. 3 4 4 на проверке
8 Игнатьев О. 3 3
9 Кириллов А. 3 3 4 на проверке
10 Марченко Е. 3 3 на проверке
11 Матвеева Д. 3 3 4 на проверке
12 Меркулова Т. 2.9 2.5 3
13 Некрасов К. 3 3.5 3 на проверке
14 Новиков П. 3 3 3.5
15 Панов А. 3 3 3.5 на проверке
16 Плященко Е. 2 4 3.5 на проверке
17 Полежаев В. 3 2.5 4 на проверке
18 Сабурова М. 3 3 на проверке
19 Соколов Е. 3 4 4 на проверке
20 Фигурнов М. 3 3 4 на проверке
21 Цупков С. 3 3.5 3.5
22 Шанин И. не получено 1.5
23 Львов С. (212) 3 не получено
24 Ульянов Д. (212) 3 4 2.75 на проверке
25 Тихонов А. (517) 0 не получено

Программа курса

Введение в курс и понятие графических моделей. Байесовские и марковские сети.

Обзор курса. Задачи анализа структурированных данных. Представление зависимостей между объектами в виде графов. Байесовские сети. Элементарные способы работы с байесовскими сетями. Марковские сети. Потенциалы на кликах. Примеры использования марковских сетей для анализа изображений.

Ликбез: независимость случайных событий. Условная вероятность. Условная независимость.

Статья в Википедии по графическим моделям

Презентация лекции (PDF, 1.01 Мб)

Точные методы вывода в ациклических графических моделях: Алгоритм Belief Propagation.

Поиск наиболее вероятной конфигурации ацикличной марковской сети с помощью алгоритма Belief Propagation (динамическое программирование). Интерфейс передачи сообщений. Подсчет мин-маргиналов. Поиск маргинальных распределений для графических моделей в форме дерева. Использование произвольных полукольцевых операций в графических моделях.

Конспект лекции (PDF, 64 Кб)
Статья в Википедии про алгоритм Belief Propagation

Скрытые марковские модели (СММ). Алгоритм сегментации сигнала

Примеры задач сегментации сигналов. Обучение СММ с учителем. Поиск наиболее вероятной последовательности состояний (алгоритм Витерби).

Линейные динамические системы. Фильтр Калмана

Свойства многомерного нормального распределения. Задача сопровождения объекта. Линейные динамические системы, фильтр Калмана. Обучение параметров линейной динамической системы с учителем. Расширенный фильтр Калмана, пример использования.

Конспект лекции (PDF, 281Кб)

Обучение СММ без учителя

ЕМ-алгоритм и его использование в анализе графических моделей. Алгоритм Баума-Уэлша для подсчета условного распределения скрытой переменной в отдельной точке. ЕМ-алгоритм для обучения СММ без учителя. Особенности численной реализации на ЭВМ. Модификации СММ (СММ высших порядков, факториальные СММ, многопоточные СММ, СММ ввода-вывода). Примеры использования СММ.

Презентация (PDF, 1.2Мб)

Алгоритмы на основе разрезов графов

Энергетическая формулировка задач компьютерного зрения. Разрезы графов, алгоритмы нахождения максимального потока. Интерактивная сегментация изображений. Энергия, которую можно минимизировать с помощью разрезов графов. Приближенная минимизация энергии с помощью алгоритма альфа-расширения.

Презентация (PDF, 618 Кб)

Приближенные методы вывода в графических моделях: Tree-ReWeighted Message Passing (TRW).

ЛП-релаксация задачи байесовского вывода. Двойственное разложение. Независимость алгоритма TRW от способа разбиений на деревья. Свойства алгоритма TRW для субмодулярной энергии.

Конспект лекции (PDF, 86Кб)

Методы настройки марковских случайных полей. Структурный метод опорных векторов.

Методы Монте Карло по схеме марковских цепей

Теоретические свойства марковских цепей: однородной, эргодичность и инвариантные распределения. Схема Метрополиса-Хастингса. Схема Гиббса. Примеры применения для дискретных марковских сетей. Фильтр частиц.

Вариационный вывод

Литература

  1. Памятка по теории вероятностей
  2. Bishop C.M. Pattern Recognition and Machine Learning. Springer, 2006.
  3. Mackay D.J.C. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003.
  4. Jordan M.I. (Ed.) Learning in graphical models. Cambridge MA: MIT Press, 1999
  5. Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J. Probabilistic networks and expert systems. Berlin: Springer, 1999.

Страницы курса прошлых лет

2009 год

2011 год

См. также

Курс «Байесовские методы машинного обучения»

Спецсеминар «Байесовские методы машинного обучения»

Математические методы прогнозирования (кафедра ВМиК МГУ)

Онлайн-курс Стэнфордского университета по вероятностным графическим моделям

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