Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)
Материал из MachineLearning.
(→Расписание занятий) |
м (ссылки) |
||
(41 промежуточная версия не показана) | |||
Строка 1: | Строка 1: | ||
- | {{ | + | {{Main|Графические модели (курс лекций)}} |
- | + | ||
- | + | ||
- | }} | + | |
{{TOCright}} | {{TOCright}} | ||
Строка 29: | Строка 26: | ||
[[Медиа:SMAIS-2009-2a.pdf| Презентация (PDF, 548 КБ)]] | [[Медиа:SMAIS-2009-2a.pdf| Презентация (PDF, 548 КБ)]] | ||
+ | |||
+ | {| | ||
+ | |<videoflash type="vimeo">7348738</videoflash> | ||
+ | |<videoflash type="vimeo">7517616</videoflash> | ||
+ | |} | ||
=== Марковские сети и дискретная оптимизация === | === Марковские сети и дискретная оптимизация === | ||
Строка 57: | Строка 59: | ||
Расширения разрезов графов для сегментации изображений. Branch-and-Mincut. Bounding box prior for interactive segmentation. | Расширения разрезов графов для сегментации изображений. Branch-and-Mincut. Bounding box prior for interactive segmentation. | ||
- | [[Медиа:SMAIS_2009_lempicky.pdf| Презентация лекции Виктора Лемпицкого (PDF, 5.58 Мб)]] | + | [[Медиа:SMAIS_2009_lempicky.pdf| Презентация лекции Виктора Лемпицкого (PDF, 5.58 Мб)]] [http://courses.graphicon.ru/files/courses/smisa/2009/lectures/lecture06.pptx (PPTX, 13 Мб)] |
<u>Часть 2. Графические модели для анализа и распознавания сигналов.</u> | <u>Часть 2. Графические модели для анализа и распознавания сигналов.</u> | ||
Строка 70: | Строка 72: | ||
Алгоритм Баума-Уэлша для подсчета условного распределения скрытой переменной в отдельной точке. ЕМ-алгоритм для обучения НММ без учителя. Особенности численной реализации на ЭВМ. Модификации НММ (НММ высших порядков, факториальные НММ, многопоточные НММ, НММ ввода-вывода). Примеры использования НММ. | Алгоритм Баума-Уэлша для подсчета условного распределения скрытой переменной в отдельной точке. ЕМ-алгоритм для обучения НММ без учителя. Особенности численной реализации на ЭВМ. Модификации НММ (НММ высших порядков, факториальные НММ, многопоточные НММ, НММ ввода-вывода). Примеры использования НММ. | ||
+ | |||
+ | [[Media:SMAIS-2009-8.pdf| Презентация (PDF, 1.01 Мб)]] | ||
+ | |||
+ | [http://courses.graphicon.ru/main/smisa/lectures/video08_1 Видео-лекция (часть 1)] | ||
+ | [http://courses.graphicon.ru/main/smisa/lectures/video08_2 Видео-лекция (часть 2)] | ||
=== Методы фильтрации данных === | === Методы фильтрации данных === | ||
- | Линейные динамические системы, фильтр Калмана. Настройка параметров фильтра Калмана. Уравнения Рауса-Тунга-Штрибеля. | + | Линейные динамические системы, фильтр Калмана. Настройка параметров фильтра Калмана. Уравнения Рауса-Тунга-Штрибеля. Расширенный фильтр Калмана, пример использования. |
+ | |||
+ | [[Media:SMAIS2009-10.pdf|Презентация (PDF, 471 Кб)]] | ||
=== Методы Монте Карло с марковскими цепями=== | === Методы Монте Карло с марковскими цепями=== | ||
Взятие интегралов методами Монте-Карло, голосование по апостериорному распределению вместо точечного решающего правила. Схема Гиббса. Гибридные методы Монте-Карло. Использование методов Монте Карло на примере фильтра частиц. | Взятие интегралов методами Монте-Карло, голосование по апостериорному распределению вместо точечного решающего правила. Схема Гиббса. Гибридные методы Монте-Карло. Использование методов Монте Карло на примере фильтра частиц. | ||
- | === Использование методов обработки сигналов в | + | [[Media:SMAIS2009-11.pdf| Презентация (PDF, 454 Кб)]] |
- | + | ||
+ | === Использование методов обработки сигналов в задачах анализа поведения === | ||
+ | Задачи одиночного/множественного трекинга лабораторных животных. Определение числа особей в блобе. Алгоритм разделения особей. Идентификация животных и определение ключевых точек. Сегментация на поведенческие акты. | ||
+ | |||
+ | [[Media:SMAIS2009-12.pdf|Презентация (PDF, 5.39Мб)]] (Для просмотра необходим [http://get.adobe.com/reader/ Acrobat Reader 9] и выше). | ||
<u>Часть 3. Методы понижения размерности.</u> | <u>Часть 3. Методы понижения размерности.</u> | ||
Строка 85: | Строка 98: | ||
=== Методы понижения размерности === | === Методы понижения размерности === | ||
- | Метод главных компонент. Вероятностный | + | Метод главных компонент. Вероятностный РСА. Анализ независимых компонент. Нелинейное уменьшение размерности. |
- | + | ||
- | + | [[Media:SMAIS2009-13.pdf|Презентация (PDF, 1.11Мб)]] | |
=== Модель активных контуров === | === Модель активных контуров === | ||
Модель активных контуров и примеры ее применения в задачах компьютерного зрения. | Модель активных контуров и примеры ее применения в задачах компьютерного зрения. | ||
+ | |||
+ | [[Media:SMAIS2009-9.pdf| Презентация (PDF, 2.11Мб)]] | ||
== Расписание занятий == | == Расписание занятий == | ||
Строка 116: | Строка 130: | ||
|29 октября 2009||Лекция 8 «Скрытые марковские модели. Обучение без учителя.» | |29 октября 2009||Лекция 8 «Скрытые марковские модели. Обучение без учителя.» | ||
|- | |- | ||
- | |5 ноября 2009||Лекция 9 | + | |5 ноября 2009||Лекция 9 «Модель активных контуров и примеры ее применения в задачах компьютерного зрения.» |
|- | |- | ||
- | |12 ноября 2009||Лекция 10 | + | |12 ноября 2009||Лекция 10 «Линейные динамические системы. Фильтр Калмана.» |
|- | |- | ||
- | |19 ноября 2009||Лекция 11 | + | |19 ноября 2009||Лекция 11 «Методы Монте-Карло с марковскими цепями. Фильтр частиц.» |
|- | |- | ||
- | |26 ноября 2009||Лекция 12 | + | |26 ноября 2009||Лекция 12 «Практические примеры задач. Анализ поведения животных.» |
|- | |- | ||
- | |3 декабря 2009||Лекция 13 | + | |3 декабря 2009||Лекция 13 «Методы понижения размерности» |
|- | |- | ||
- | |10 декабря 2009|| | + | |10 декабря 2009||Обзор курса. Консультация перед экзаменом. |
|- | |- | ||
+ | |17 декабря 2009||Экзамен | ||
|} | |} | ||
Строка 134: | Строка 149: | ||
Задание 1. '''Минимизация энергии с помощью разрезов графа'''. Описание задания доступно [http://courses.graphicon.ru/main/smisa2009 здесь]. | Задание 1. '''Минимизация энергии с помощью разрезов графа'''. Описание задания доступно [http://courses.graphicon.ru/main/smisa2009 здесь]. | ||
+ | |||
+ | Задание 2. [[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2|'''Скрытые марковские модели'''.]] | ||
+ | [[Media:SMAIS2009-task2-comments.pdf|Комментарии к заданию 2 (PDF, 327Кб)]] | ||
+ | |||
+ | == Экзамен == | ||
+ | Экзамен состоится в четверг, 17 декабря, в ауд. 510, начало в 16-20. К экзамену допускаются только те студенты, которые успешно справились с обоими практическими заданиями (см. таблицу ниже). При себе необходимо иметь экзаменационную ведомость по спецкурсу (одна ведомость на каждую академическую группу). На экзамене при подготовке разрешается пользоваться любыми материалами. | ||
+ | |||
+ | [[Media:SMAIS2009-questions.pdf|Вопросы к экзамену (PDF, 87 Кб)]] | ||
+ | |||
+ | == Оценка за курс == | ||
+ | В этом году оценка за курс будет вычисляться по формуле 0.25*(оценка за первое | ||
+ | задание)+0.25*(оценка за второе задание)+0.5*(оценка за экзамен). При этом оценка за курс будет выставляться только тем, кто успешно справился с обоими практическими заданиями + сдал экзамен. | ||
+ | |||
+ | {| class="standard" | ||
+ | !rowspan="2" |Участник||rowspan="2" |Группа||rowspan="2" |Задание 1||colspan = "2" |[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2|Задание 2]]||rowspan="2" |Экзамен||rowspan="2" |Итоговая оценка | ||
+ | |- | ||
+ | !Вариант||Оценка | ||
+ | |- | ||
+ | |Новиков Павел Александрович|| align="center"|203 || align="center"|5.0 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 3|3]] || Задание не получено || Не допущен || | ||
+ | |- | ||
+ | |Дударенко Марина Алексеевна|| align="center"|317 || align="center"|5.0 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 1|1]] || align="center"|4.0 || align="center"|5.0 || align="center"|5.0 | ||
+ | |- | ||
+ | |Тихонов Андрей Александрович|| align="center"|317 || align="center"|5.0 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 2|2]] || align="center"|3.0 || align="center"|4.0 || align="center"|4.0 | ||
+ | |- | ||
+ | |Ермишин Федор Дмитриевич|| align="center"|321 || align="center"|4.5 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 2|2]] || align="center"|4.0 || Не допущен || | ||
+ | |- | ||
+ | |Кухаренко Артем Игоревич|| align="center"|321 || align="center"|5.5 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 3|3]] || align="center"|4.0 || align="center"|5.0 || align="center"|5.0 | ||
+ | |- | ||
+ | |Воронов Александр Александрович|| align="center"|421 || align="center"|5.0 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 1|1]] || Задание не получено || Не допущен || | ||
+ | |- | ||
+ | |Лукина Татьяна Михайловна|| align="center"|421 || align="center"|4.5 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 2|2]] || align="center"|4.5 || Неявка || | ||
+ | |- | ||
+ | |Потапов Дмитрий Борисович|| align="center"|421 || align="center"|4.5 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 3|3]] || align="center"|4.0 || Неявка || | ||
+ | |- | ||
+ | |Третьяк Елена Викторовна|| align="center"|421 || align="center"|4.5 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 1|1]] || align="center"|4.0 || align="center"|5.0 || align="center"|5.0 | ||
+ | |- | ||
+ | |Блажевич Ксения Игоревна|| align="center"|422 || align="center"|5.0 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 2|2]] || align="center"|4.0 || Неявка || | ||
+ | |- | ||
+ | |Ломакин Василий Дмитриевич|| align="center"|517 || align="center"|5.5 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 3|3]] || align="center"|5.0 || align="center"|5.0 || align="center"|5.0 | ||
+ | |- | ||
+ | |Одинокова Евгения Андреевна|| align="center"|517 || align="center"|5.0 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 2|2]] || align="center"|4.0 || align="center"|5.0 || align="center"|5.0 | ||
+ | |- | ||
+ | |Ломакина-Румянцева Екатерина Ильинична|| align="center"|517 || align="center"|4.5 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 2|2]] || align="center"|4.0 || ? || | ||
+ | |- | ||
+ | |Юданов Анатолий Александрович|| align="center"|525 || align="center"|5.0 || align="center"|[[Структурные методы анализа изображений и сигналов (курс лекций) / Задание 2#Вариант 1|1]] || align="center"|4.0 || align="center"|5.0 || align="center"|5.0 | ||
+ | |- | ||
+ | |} | ||
== Литература == | == Литература == | ||
Строка 151: | Строка 213: | ||
[[Категория:Учебные курсы]] | [[Категория:Учебные курсы]] | ||
+ | [[Категория:Байесовские методы]] |
Текущая версия
Курс посвящен математическим методам обработки информации, основанных на выделении структуры в исходных данных и ее последующем анализе. Эти методы широко используются при решении задач из разных прикладных областей, включая обработку изображений и видео, анализ поведения, распознавание речи, машинное обучение.
Краткая презентация о курсе (PDF, 532 Кб)
Программа курса
Часть 1. Графические модели для анализа изображений.
Введение в курс и понятие графических моделей.
Обзор курса. Задачи анализа структурированных данных. Представление зависимостей между объектами в виде графов. Основные задачи, для решения которых используются графические модели. Демонстрация современных работ, опирающихся на данные в курсе методы.
Напоминание основных понятий, которые будут активно использоваться в следующих лекциях. Основные операции с вероятностями (правило суммы, произведения, формула Байеса). Понятия мат. ожидание и матрицы ковариаций. Нормальное распределение. Независимость событий. Маргинализация (исключение переменной). Метод максимального правдоподобия, МАР-оценивание на примере нормального распределения. Матричная нотация (скалярное произведение, следы матриц, квадратичные формы, дифференцирование по вектору). Правило множителей Лагранжа с ограничениями в виде равенств и неравенств.
Основные графические модели
Байесовские сети. Элементарные способы работы с байесовскими сетями. Марковские сети. Потенциалы на кликах. Примеры использования марковских сетей для анализа изображений. Ликбез: независимость случайных событий. Условная вероятность. Условная независимость.
Марковские сети и дискретная оптимизация
Энергетическая формулировка задач компьютерного зрения. Разрезы графов, алгоритмы нахождения максимального потока. Интерактивная сегментация изображений. Энергия, которую можно минимизировать с помощью разрезов графов. Многоуровневые разрезы графов. Приближенная минимизация энергии с помощью разрезов графов. Алгоритм, основанный на замене. Примеры минимизируемых энергий. Сегментация видео. Сшивка изображений. Трехмерная реконструкция.
Презентация с тьюториала на Графиконе 2009 по разрезам графов
Методы настройки марковских случайных полей
Методы обучения в марковских случайных полях. Применение для семантической сегментации изображений, распознавания объектов с учетом контекста и трехмерной реконструкции.
Алгоритмы обмена сообщениями. Belief propagation и Loopy belief propagation.
Приближенные методы вывода в графических моделях
Алгоритмы обмена сообщениями на графах. Алгоритмы Belief Propagation и Tree-ReWeighted Belief Propagation.
Презентация лекции Владимира Колмогорова (PDF, 209 Кб)
Расширения разрезов графов для сегментации изображений
Расширения разрезов графов для сегментации изображений. Branch-and-Mincut. Bounding box prior for interactive segmentation.
Презентация лекции Виктора Лемпицкого (PDF, 5.58 Мб) (PPTX, 13 Мб)
Часть 2. Графические модели для анализа и распознавания сигналов.
Скрытые марковские модели. Алгоритм сегментации сигнала
Примеры задач сегментации сигналов. Обучение НММ с учителем. Поиск наиболее вероятной последовательности состояний. ЕМ-алгоритм и его использование в анализе графических моделей.
Обучение СММ без учителя
Алгоритм Баума-Уэлша для подсчета условного распределения скрытой переменной в отдельной точке. ЕМ-алгоритм для обучения НММ без учителя. Особенности численной реализации на ЭВМ. Модификации НММ (НММ высших порядков, факториальные НММ, многопоточные НММ, НММ ввода-вывода). Примеры использования НММ.
Видео-лекция (часть 1) Видео-лекция (часть 2)
Методы фильтрации данных
Линейные динамические системы, фильтр Калмана. Настройка параметров фильтра Калмана. Уравнения Рауса-Тунга-Штрибеля. Расширенный фильтр Калмана, пример использования.
Методы Монте Карло с марковскими цепями
Взятие интегралов методами Монте-Карло, голосование по апостериорному распределению вместо точечного решающего правила. Схема Гиббса. Гибридные методы Монте-Карло. Использование методов Монте Карло на примере фильтра частиц.
Использование методов обработки сигналов в задачах анализа поведения
Задачи одиночного/множественного трекинга лабораторных животных. Определение числа особей в блобе. Алгоритм разделения особей. Идентификация животных и определение ключевых точек. Сегментация на поведенческие акты.
Презентация (PDF, 5.39Мб) (Для просмотра необходим Acrobat Reader 9 и выше).
Часть 3. Методы понижения размерности.
Методы понижения размерности
Метод главных компонент. Вероятностный РСА. Анализ независимых компонент. Нелинейное уменьшение размерности.
Модель активных контуров
Модель активных контуров и примеры ее применения в задачах компьютерного зрения.
Расписание занятий
В 2009 году курс читается по четвергам на факультете ВМиК МГУ, в ауд. 671, начало в 18-05.
Дата | Занятие |
---|---|
10 сентября 2009 | Лекция 1 «Введение в курс. Напоминание известных математических фактов для последующих лекций» |
17 сентября 2009 | Лекция 2 «Графические модели. Общее представление» |
24 сентября 2009 | Лекция 3 «Минимизация энергии с помощью разрезов графов» |
1 октября 2009 | Лекция 4 «Алгоритмы обмена сообщениями. Методы настройки потенциалов случайных полей» |
8 октября 2009 | Лекция 5 «Алгоритмы обмена сообщениями в циклических графах. Tree-reweighted message passing» |
15 октября 2009 | Лекция 6 «Расширения разрезов графов для сегментации изображений. Branch-and-Mincut. Bounding box prior for interactive segmentation» |
22 октября 2009 | Лекция 7 «Скрытые марковские модели. Обучение с учителем. ЕМ-алгоритм.» |
29 октября 2009 | Лекция 8 «Скрытые марковские модели. Обучение без учителя.» |
5 ноября 2009 | Лекция 9 «Модель активных контуров и примеры ее применения в задачах компьютерного зрения.» |
12 ноября 2009 | Лекция 10 «Линейные динамические системы. Фильтр Калмана.» |
19 ноября 2009 | Лекция 11 «Методы Монте-Карло с марковскими цепями. Фильтр частиц.» |
26 ноября 2009 | Лекция 12 «Практические примеры задач. Анализ поведения животных.» |
3 декабря 2009 | Лекция 13 «Методы понижения размерности» |
10 декабря 2009 | Обзор курса. Консультация перед экзаменом. |
17 декабря 2009 | Экзамен |
Практические задания по курсу
Для успешной сдачи спецкурса необходимо выполнить все практические задания, а также сдать экзамен. Выполненные практические задания следует загружать сюда. Там же будут доступны результаты проверки заданий.
Задание 1. Минимизация энергии с помощью разрезов графа. Описание задания доступно здесь.
Задание 2. Скрытые марковские модели. Комментарии к заданию 2 (PDF, 327Кб)
Экзамен
Экзамен состоится в четверг, 17 декабря, в ауд. 510, начало в 16-20. К экзамену допускаются только те студенты, которые успешно справились с обоими практическими заданиями (см. таблицу ниже). При себе необходимо иметь экзаменационную ведомость по спецкурсу (одна ведомость на каждую академическую группу). На экзамене при подготовке разрешается пользоваться любыми материалами.
Вопросы к экзамену (PDF, 87 Кб)
Оценка за курс
В этом году оценка за курс будет вычисляться по формуле 0.25*(оценка за первое задание)+0.25*(оценка за второе задание)+0.5*(оценка за экзамен). При этом оценка за курс будет выставляться только тем, кто успешно справился с обоими практическими заданиями + сдал экзамен.
Участник | Группа | Задание 1 | Задание 2 | Экзамен | Итоговая оценка | |
---|---|---|---|---|---|---|
Вариант | Оценка | |||||
Новиков Павел Александрович | 203 | 5.0 | 3 | Задание не получено | Не допущен | |
Дударенко Марина Алексеевна | 317 | 5.0 | 1 | 4.0 | 5.0 | 5.0 |
Тихонов Андрей Александрович | 317 | 5.0 | 2 | 3.0 | 4.0 | 4.0 |
Ермишин Федор Дмитриевич | 321 | 4.5 | 2 | 4.0 | Не допущен | |
Кухаренко Артем Игоревич | 321 | 5.5 | 3 | 4.0 | 5.0 | 5.0 |
Воронов Александр Александрович | 421 | 5.0 | 1 | Задание не получено | Не допущен | |
Лукина Татьяна Михайловна | 421 | 4.5 | 2 | 4.5 | Неявка | |
Потапов Дмитрий Борисович | 421 | 4.5 | 3 | 4.0 | Неявка | |
Третьяк Елена Викторовна | 421 | 4.5 | 1 | 4.0 | 5.0 | 5.0 |
Блажевич Ксения Игоревна | 422 | 5.0 | 2 | 4.0 | Неявка | |
Ломакин Василий Дмитриевич | 517 | 5.5 | 3 | 5.0 | 5.0 | 5.0 |
Одинокова Евгения Андреевна | 517 | 5.0 | 2 | 4.0 | 5.0 | 5.0 |
Ломакина-Румянцева Екатерина Ильинична | 517 | 4.5 | 2 | 4.0 | ? | |
Юданов Анатолий Александрович | 525 | 5.0 | 1 | 4.0 | 5.0 | 5.0 |
Литература
- 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.
См. также
Страница курса на сайте лаборатории компьютерной графики и мультимедиа ВМиК МГУ
Курс «Байесовские методы машинного обучения»