Структурные методы анализа изображений и сигналов (курс лекций)
Материал из MachineLearning.
Спецкурс посвящен математическим методам обработки информации, основанных на использовании внутренних взаимосвязей в данных и их последующем анализе. Эти методы широко используются при решении задач из разных прикладных областей, включая обработку изображений и видео, анализ социальных сетей, распознавание речи, машинное обучение.
Лекторы: Д.П. Ветров, Д.А. Кропотов, А.А. Осокин.
Расписание занятий
В 2011 году курс читается в весеннем семестре по пятницам на факультете ВМиК МГУ, в ауд. 612, начало в 16-20.
| Дата | Занятие |
|---|---|
| 18 февраля 2011 | Лекция 1 «Введение в курс. Напоминание известных математических фактов для последующих лекций» |
| 25 февраля 2011 | Лекция 2 «Графические модели» |
| 4 марта 2011 | Лекция 3 «Точные методы вывода в ациклических графических моделях. Алгоритм Belief Propagation» |
| 11 марта 2011 | Лекция 4 «Скрытые марковские модели. Алгоритм сегментации сигнала» |
| 18 марта 2011 | Лекция 5 «Обучение скрытых марковских моделей» |
| 25 марта 2011 | Лекция 6 «Задача фильтрации многомерных сигналов. Линейные динамические системы. Фильтр Калмана» |
| 1 апреля 2011 | Лекция 7 «Приближенные методы вывода в циклических графических моделях. Алгоритм Tree-ReWeighted Message Passing (TRW)» |
| 8 апреля 2011 | Лекция 8 «Алгоритмы на основе разрезов графов» |
| 15 апреля 2011 | Лекция 9 «Примеры практического применения алгоритмов, обсуждаемых в курсе. Комментарии ко второму заданию.» |
| 22 апреля 2011 | Лекция 10 «Метод опорных векторов» |
| 29 апреля 2011 | Лекция 11 «Структурный метод опорных векторов» |
| 6 мая 2011 | Лекция 12 «Методы Монте Карло по схеме марковских цепей» |
| 13 мая 2011 | Экзамен по спецкурсу для студентов 4-ого и 5-ого курсов |
| 20 мая 2011 | Экзамен по спецкурсу для студентов 2-ого и 3-ого курса |
Оценка за курс
Для успешной сдачи спецкурса необходимо в течение семестра выполнить два практических задания, а также сдать экзамен. Оценка за курс вычисляется по формуле 0.25*(оценка за первое задание) + 0.25*(оценка за второе задание) + 0.5*(оценка за экзамен).
| Участник | Группа | Задание 1 | Задание 2 | Экзамен | Итоговая оценка |
|---|---|---|---|---|---|
| Ромов П. | 202 | 5.0 | 5.0 | 5.0 | 5.0 |
| Гитман Ю. | 205 | 5.0 | |||
| Лобачева Е. | 209 | 5.0 | 5.0 | ||
| Елшин Д. | 317 | 5.0 | 5.0 | 4.5 | 5.0 |
| Новиков П. | 317 | 4.5 | 4.5 | 5.0 | 5.0 |
| Некрасов К. | 317 | 4.5 | 4.0 | 3.0 | 4.0 |
| Меркулова Т. | 317 | 4.5 | 4.5 | 5.0 | 5.0 |
| Костин Г. | 320 | 4.0 | 4.5 | 5.0 | 5.0 |
| Шальнов Е. | 321 | 4.5 | 5.0 | 5.0 | 5.0 |
| Конев А. | 321 | 4.0 | 4.5 | 5.0 | 5.0 |
| Птенцов С. | 321 | 3.0 | 3.0 | 5.0 | 4.0 |
| Новикова Т. | 321 | 3.0 | 4.0 | 4.0 | 4.0 |
| Сапатов А. | 321 | 3.5 | 4.0 | 3.5 | 4.0 |
| Батанов П. | 321 | 3.5 | |||
| Парамонов С. | 324 | 4.0 | 3.0 | 4.0 | 4.0 |
| Колев Д. | 417 | 5.0 | 4.5 | 5.0 | 5.0 |
| Тихонов А. | 417 | 3.5 | |||
| Ермишин Ф. | 421 | 4.5 | 4.0 | 5.0 | 5.0 |
| Беликов В. | 422 | 4.5 | 3.5 | ||
| Субботин Н. | 422 | 4.0 | 3.0 | ||
| Бартунов С. | 428 | 3.5 | |||
| Казаков И. | 432 | 4.0 | |||
| Заякина О. | ВВО | 5.0 |
Практические задания
Задание 1. Скрытые марковские модели и линейные динамические системы.
Задание 2. TRW и α-расширение.
Экзамен
К экзамену допускаются только те студенты, которые успешно выполнили оба практических задания. Для студентов 4-ого и 5-ого курса экзамен состоится 13 мая, начало в 13-00, ауд. П-8а. Для остальных студентов экзамен состоится 20 мая, начало в 13-00, ауд. П-8а. При подготовке билета разрешается пользоваться любыми материалами. При ответе ничем пользоваться нельзя. Убедительная просьба при себе иметь экзаменационную ведомость по спецкурсу (достаточно одной для каждой академической группы).
Программа курса
Введение в курс и понятие графических моделей.
Обзор курса. Задачи анализа структурированных данных. Представление зависимостей между объектами в виде графов. Основные задачи, для решения которых используются графические модели. Демонстрация современных работ, опирающихся на данные в курсе методы.
Напоминание основных понятий, которые будут активно использоваться в следующих лекциях. Основные операции с вероятностями (правило суммы, произведения, формула Байеса). Понятия мат. ожидание и матрицы ковариаций. Нормальное распределение. Независимость событий. Маргинализация (исключение переменной). Метод максимального правдоподобия, МАР-оценивание на примере нормального распределения. Матричная нотация (скалярное произведение, следы матриц, квадратичные формы, дифференцирование по вектору). Правило множителей Лагранжа с ограничениями в виде равенств и неравенств.
Основные графические модели
Байесовские сети. Элементарные способы работы с байесовскими сетями. Марковские сети. Потенциалы на кликах. Примеры использования марковских сетей для анализа изображений. Ликбез: независимость случайных событий. Условная вероятность. Условная независимость.
Презентация (PDF, 548 КБ)
Статья в Википедии по графическим моделям
Точные методы вывода в ациклических графических моделях: Алгоритм Belief Propagation.
Поиск наиболее вероятной конфигурации ацикличной марковской сети с помощью алгоритма Belief Propagation (динамическое программирование). Интерфейс передачи сообщений. Подсчет мин-маргиналов. Поиск маргинальных распределений для графических моделей в форме дерева. Использование произвольных полукольцевых операций в графических моделях.
Конспект лекции (PDF, 64 Кб)
Статья в Википедии про алгоритм Belief Propagation
Скрытые марковские модели (СММ). Алгоритм сегментации сигнала.
Примеры задач сегментации сигналов. Обучение СММ с учителем. Поиск наиболее вероятной последовательности состояний. ЕМ-алгоритм и его использование в анализе графических моделей.
Презентация лекции (PDF, 779 Кб)
Обучение СММ без учителя
Алгоритм Баума-Уэлша для подсчета условного распределения скрытой переменной в отдельной точке. ЕМ-алгоритм для обучения СММ без учителя. Особенности численной реализации на ЭВМ. Модификации СММ (СММ высших порядков, факториальные СММ, многопоточные СММ, СММ ввода-вывода). Примеры использования СММ.
Презентация лекции (PDF, 1.01 Мб)
Методы фильтрации данных
Линейные динамические системы, фильтр Калмана. Настройка параметров фильтра Калмана. Уравнения Рауса-Тунга-Штрибеля. Расширенный фильтр Калмана, пример использования.
Приближенные методы вывода в графических моделях: 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.
Страницы курса прошлых лет
См. также
Курс «Байесовские методы машинного обучения»
