Графические модели (курс лекций)
Материал из MachineLearning.
| Курс посвящен математическим методам обработки информации, основанных на использовании внутренних взаимосвязей в данных и их последующем анализе. Эти методы широко используются при решении задач из разных прикладных областей, включая обработку изображений и видео, анализ социальных сетей, распознавание речи, машинное обучение. До 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 «Алгоритмы на основе разрезов графов, | Презентация (PDF, 618 Кб) |
| 28 марта 2012 | Лекция 7 «Приближенные методы вывода в циклических графических моделях. Алгоритм Tree-ReWeighted Message Passing (TRW)» | Конспект лекции (PDF, 86Кб) |
| 4 апреля 2012 | Семинар 2 | |
| 11 апреля 2012 | Лекция 8 «Структурный метод опорных векторов» | Конспект (PDF, 103Кб) |
| 18 апреля 2012 | Лекция 9 «Методы Монте Карло по схеме марковских цепей» | Конспект (PDF, 121Кб) |
| 25 апреля 2012 | Лекция 10 «Вариационный вывод» | Конспект1 (JPG, 930Кб), Конспект2 (JPG, 900Кб) |
| 2 мая 2012 | Семинар 3 | |
| 16 мая 2012 | Лекция 11 «Использование графических моделей для решения различных прикладных задач анализа данных» | Презентация (PDF, 963Кб) |
Экзамен
На экзамене при подготовке ответа на билет разрешается пользоваться любыми материалами. При непосредственном ответе ничем пользоваться нельзя.
Вопросы к экзамену + теоретический минимум (PDF, 102Кб)
Практические задания
Задание 1. «Алгоритмы передачи сообщений».
Задание 2. «Динамические системы и фильтр Калмана».
Задание 3. «TRW и α-расширение».
Задание 4. «Разрезы графов и двойственное разложение».
Задание 5. «Структурное обучение».
Задание 6. «Модель Изинга».
Оценки
| № п/п | Студент | Задание 1 (3 балла) | Задание 2 (4 балла) | Задание 3 (4 балла) | Задание 4 (3 балла) | Задание 5 (3+3 балла) | Задание 6 (5 баллов) | Сумма | Конверт. | Устный | Итоговая |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | Александров Я. | 2 | 2.5 | 3 | 2 | 4 | 5 | *18.5 | 4 | 5 | 5 |
| 2 | Артюхин С. | 3 | 3 | 4 | 2 | 5.5 | 4.5 | *22 | 5 | 5 | 5 |
| 3 | Бобрик К. | 3 | 2.5 | -10 | 3 | 3.5 | 0.5 | 2.5 | |||
| 4 | Гаврилюк К. | 3 | 3 | 4 | 2 | 6 | 4.5 | *22.5 | 5 | 5 | 5 |
| 5 | Елшин Д. | 3 | 3 | 4 | 2 | 6 | 4.5 | *22.5 | 5 | 5 | 5 |
| 6 | Ермушева А. | 2 | 2.5 | 2.5 | 2 | 5 | 4.5 | *18.5 | 4 | 5 | 5 |
| 7 | Зимовнов А. | 3 | 4 | 4 | 2 | 7 | 4.5 | *24.5 | 5+ | 5 | 5 |
| 8 | Игнатьев О. | 3 | 3 | 2.5 | 0 | 4.5 | 3.5 | *16.5 | 4 | 5 | 5 |
| 9 | Кириллов А. | 3 | 3 | 4 | 2 | 6 | 5 | *23 | 5 | 5 | 5 |
| 10 | Марченко Е. | 3 | 3 | 2.5 | 2 | -10 | -10 | -9.5 | 5 | ||
| 11 | Матвеева Д. | 3 | 3 | 4 | 2 | 6 | 5 | *23 | 5 | 5 | 5 |
| 12 | Меркулова Т. | 3 | 2.5 | 3 | -10 | -10 | 5 | -6.5 | 4 | ||
| 13 | Некрасов К. | 3 | 3.5 | 3 | 2 | 3.5 | 2.5 | *17.5 | 4 | 5 | 5 |
| 14 | Новиков П. | 3 | 3 | 3.5 | 1.5 | 3 | 4 | *18 | 4 | 5 | 5 |
| 15 | Панов А. | 3 | 3 | 3.5 | 1.5 | 7 | 3.5 | *21.5 | 5 | 4 | 5 |
| 16 | Плященко Е. | 2 | 4 | 1.5 | 1.5 | 5 | 4.5 | *18.5 | 4 | ||
| 17 | Полежаев В. | 3 | 2.5 | 4 | 2 | 6 | 4 | *21.5 | 5 | 5 | 5 |
| 18 | Сабурова М. | 3 | 3 | 0 | 1.5 | 4 | 4.5 | *16 | 4 | 4 | 4 |
| 19 | Соколов Е. | 3 | 4 | 4 | 2 | 6 | 5 | *24 | 5+ | 5 | 5 |
| 20 | Фигурнов М. | 3 | 3 | 4 | 2 | 6.5 | 4.5 | *23 | 5 | 5 | 5 |
| 21 | Цупков С. | 3 | 3.5 | 3.5 | 3 | 5 | 2.5 | *20.5 | 5 | 5 | 5 |
| 22 | Шанин И. | -10 | 1.5 | -10 | 0 | -10 | -10 | -38.5 | +15 | -23.5 | |
| 24 | Ульянов Д. (212) | 3 | 4 | 3.25 | 1.5 | 11.75 |
Система выставления оценок по курсу
- При наличии несданных заданий максимальная возможная оценка за курс — это «удовлетворительно».
- Итоговая оценка вычисляется по формуле
, где Oral — оценка из пяти баллов за устный экзамен, HomeWork — баллы, набранные за практические задания (см. таблицу выше), Mark — итоговая оценка по 5-балльной шкале. Нецелые значения округляются в сторону ближайшего целого, превосходящего дробное значение.
- Студент может отказаться от оценки и пойти на пересдачу, на которой может заново получить Oral.
- За каждое несданное задание выставляется минус 10 баллов в HomeWork (допускаются отрицательные значения).
- Если на экзамене итоговая оценка оказывается ниже трех, студент отправляется на пересдачу. При этом оценка Oral, полученная на пересдаче, добавляется к положительной (три и выше) оценке Oral, полученной на основном экзамене и т.д. до тех пор, пока студент не наберет на итоговую оценку «удовлетворительно» (для итоговых оценок выше «удовлетворительно» оценки Oral не суммируются).
- Студент может досдать недостающие практические задания в любое время. При этом проверка задания гарантируется только в том случае, если задание сдано не позднее, чем за неделю до основного экзамена или пересдачи.
- Штраф за просрочку сдачи заданий начисляется из расчета 0.5 балла за неделю, но не более 5 баллов.
- В случае успешной сдачи всех практических заданий студент получает возможность претендовать на итоговую оценку «хорошо» и «отлично». При этом экзамен на оценку Oral может сдаваться до сдачи всех заданий (оценки Oral в этом случае не суммируются).
- Экзамен на оценку Oral сдается либо в срок основного экзамена, либо в срок официальных пересдач.
Программа курса
Введение в курс и понятие графических моделей. Байесовские и марковские сети.
Обзор курса. Задачи анализа структурированных данных. Представление зависимостей между объектами в виде графов. Байесовские сети. Элементарные способы работы с байесовскими сетями. Марковские сети. Потенциалы на кликах. Примеры использования марковских сетей для анализа изображений.
Ликбез: независимость случайных событий. Условная вероятность. Условная независимость.
Статья в Википедии по графическим моделям
Презентация лекции (PDF, 1.01 Мб)
Точные методы вывода в ациклических графических моделях: Алгоритм Belief Propagation.
Поиск наиболее вероятной конфигурации ацикличной марковской сети с помощью алгоритма Belief Propagation (динамическое программирование). Интерфейс передачи сообщений. Подсчет мин-маргиналов. Поиск маргинальных распределений для графических моделей в форме дерева. Использование произвольных полукольцевых операций в графических моделях.
Конспект лекции (PDF, 64 Кб)
Статья в Википедии про алгоритм Belief Propagation
Скрытые марковские модели (СММ). Алгоритм сегментации сигнала
Примеры задач сегментации сигналов. Обучение СММ с учителем. Поиск наиболее вероятной последовательности состояний (алгоритм Витерби).
Линейные динамические системы. Фильтр Калмана
Свойства многомерного нормального распределения. Задача сопровождения объекта. Линейные динамические системы, фильтр Калмана. Обучение параметров линейной динамической системы с учителем. Расширенный фильтр Калмана, пример использования.
Обучение СММ без учителя
ЕМ-алгоритм и его использование в анализе графических моделей. Алгоритм Баума-Уэлша для подсчета условного распределения скрытой переменной в отдельной точке. ЕМ-алгоритм для обучения СММ без учителя. Особенности численной реализации на ЭВМ. Модификации СММ (СММ высших порядков, факториальные СММ, многопоточные СММ, СММ ввода-вывода). Примеры использования СММ.
Алгоритмы на основе разрезов графов
Энергетическая формулировка задач компьютерного зрения. Разрезы графов, алгоритмы нахождения максимального потока. Интерактивная сегментация изображений. Энергия, которую можно минимизировать с помощью разрезов графов. Приближенная минимизация энергии с помощью алгоритма альфа-расширения.
Приближенные методы вывода в графических моделях: Tree-ReWeighted Message Passing (TRW).
ЛП-релаксация задачи байесовского вывода. Двойственное разложение. Независимость алгоритма TRW от способа разбиений на деревья. Свойства алгоритма TRW для субмодулярной энергии.
Методы настройки марковских случайных полей. Структурный метод опорных векторов.
Задача структурного обучения. Метод опорных векторов для случая многих классов. Структурный метод опорных векторов. Обучение с помощью метода отсекающей плоскости. Обучение с помощью двойственной задачи. Примеры.
Методы Монте Карло по схеме марковских цепей
Генерация выборки из одномерных распределений. Теоретические свойства марковских цепей: однородность, эргодичность и инвариантные распределения. Схема Метрополиса-Хастингса. Схема Гиббса. Примеры применения для дискретных марковских сетей. Фильтр частиц.
Вариационный вывод
Литература
- Памятка по теории вероятностей
- Bishop C.M. Pattern Recognition and Machine Learning. Springer, 2006.
- Mackay D.J.C. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003.
- Jordan M.I. (Ed.) Learning in graphical models. Cambridge MA: MIT Press, 1999
- Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J. Probabilistic networks and expert systems. Berlin: Springer, 1999.
Страницы курса прошлых лет
См. также
Курс «Байесовские методы машинного обучения»
Спецсеминар «Байесовские методы машинного обучения»
Математические методы прогнозирования (кафедра ВМиК МГУ)
Онлайн-курс Стэнфордского университета по вероятностным графическим моделям
