Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)

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

(Различия между версиями)
Перейти к: навигация, поиск
(Добавил лекцию про HMM, часть 1)
м (ссылки)
 
(42 промежуточные версии не показаны)
Строка 1: Строка 1:
-
{{tip|
+
{{Main|Графические модели (курс лекций)}}
-
Студентам на заметку: на вкладке «Обсуждение» к данной странице можно задать вопрос по курсу, высказать свои пожелания, предложения и т.п.
+
-
[[Участник:Kropotov|Кропотов Д.А.]], 20 сентября 2009
+
-
}}
+
{{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)]&nbsp;
 +
[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:
=== Методы понижения размерности ===
=== Методы понижения размерности ===
-
Метод главных компонент. Вероятностный РСА. Ядровая версия РСА. Анализ независимых компонент. Нелинейное уменьшение размерности.
+
Метод главных компонент. Вероятностный РСА. Анализ независимых компонент. Нелинейное уменьшение размерности.
-
Методы на базе MDL – минимальной длины описания. Активные контура и их применение для сегментации движущихся объектов в видеопотоке. Алгоритмы распознавания лиц на базе методов понижения размерности.
+
-
''Ликбез'': свойства симметричных матриц, положительно определенные матрицы.
+
[[Media:SMAIS2009-13.pdf|Презентация (PDF, 1.11Мб)]]
=== Модель активных контуров ===
=== Модель активных контуров ===
Модель активных контуров и примеры ее применения в задачах компьютерного зрения.
Модель активных контуров и примеры ее применения в задачах компьютерного зрения.
 +
 +
[[Media:SMAIS2009-9.pdf| Презентация (PDF, 2.11Мб)]]
== Расписание занятий ==
== Расписание занятий ==
Строка 112: Строка 126:
|15 октября 2009||Лекция 6 «Расширения разрезов графов для сегментации изображений. Branch-and-Mincut. Bounding box prior for interactive segmentation»
|15 октября 2009||Лекция 6 «Расширения разрезов графов для сегментации изображений. Branch-and-Mincut. Bounding box prior for interactive segmentation»
|-
|-
-
|22 октября 2009||Лекция 7
+
|22 октября 2009||Лекция 7 «Скрытые марковские модели. Обучение с учителем. ЕМ-алгоритм.»
|-
|-
-
|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. Графические модели для анализа изображений.

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

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

Напоминание основных понятий, которые будут активно использоваться в следующих лекциях. Основные операции с вероятностями (правило суммы, произведения, формула Байеса). Понятия мат. ожидание и матрицы ковариаций. Нормальное распределение. Независимость событий. Маргинализация (исключение переменной). Метод максимального правдоподобия, МАР-оценивание на примере нормального распределения. Матричная нотация (скалярное произведение, следы матриц, квадратичные формы, дифференцирование по вектору). Правило множителей Лагранжа с ограничениями в виде равенств и неравенств.

Презентация (PDF, 535 КБ)

Основные графические модели

Байесовские сети. Элементарные способы работы с байесовскими сетями. Марковские сети. Потенциалы на кликах. Примеры использования марковских сетей для анализа изображений. Ликбез: независимость случайных событий. Условная вероятность. Условная независимость.

Презентация (PDF, 548 КБ)

Марковские сети и дискретная оптимизация

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

Презентация (PDF, 2.44 МБ)

Презентация с тьюториала на Графиконе 2009 по разрезам графов

Презентация (PDF, 742 КБ)

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

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

Алгоритмы обмена сообщениями. Belief propagation и Loopy belief propagation.

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

Приближенные методы вывода в графических моделях

Алгоритмы обмена сообщениями на графах. Алгоритмы Belief Propagation и Tree-ReWeighted Belief Propagation.

Презентация лекции Владимира Колмогорова (PDF, 209 Кб)

Расширения разрезов графов для сегментации изображений

Расширения разрезов графов для сегментации изображений. Branch-and-Mincut. Bounding box prior for interactive segmentation.

Презентация лекции Виктора Лемпицкого (PDF, 5.58 Мб) (PPTX, 13 Мб)

Часть 2. Графические модели для анализа и распознавания сигналов.

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

Примеры задач сегментации сигналов. Обучение НММ с учителем. Поиск наиболее вероятной последовательности состояний. ЕМ-алгоритм и его использование в анализе графических моделей.

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

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

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

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

Видео-лекция (часть 1)  Видео-лекция (часть 2)

Методы фильтрации данных

Линейные динамические системы, фильтр Калмана. Настройка параметров фильтра Калмана. Уравнения Рауса-Тунга-Штрибеля. Расширенный фильтр Калмана, пример использования.

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

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

Взятие интегралов методами Монте-Карло, голосование по апостериорному распределению вместо точечного решающего правила. Схема Гиббса. Гибридные методы Монте-Карло. Использование методов Монте Карло на примере фильтра частиц.

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

Использование методов обработки сигналов в задачах анализа поведения

Задачи одиночного/множественного трекинга лабораторных животных. Определение числа особей в блобе. Алгоритм разделения особей. Идентификация животных и определение ключевых точек. Сегментация на поведенческие акты.

Презентация (PDF, 5.39Мб) (Для просмотра необходим Acrobat Reader 9 и выше).

Часть 3. Методы понижения размерности.

Методы понижения размерности

Метод главных компонент. Вероятностный РСА. Анализ независимых компонент. Нелинейное уменьшение размерности.

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

Модель активных контуров

Модель активных контуров и примеры ее применения в задачах компьютерного зрения.

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

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

В 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

Литература

  1. Bishop C.M. Pattern Recognition and Machine Learning. Springer, 2006.
  2. Mackay D.J.C. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003.
  3. Jordan M.I. (Ed.) Learning in graphical models. Cambridge MA: MIT Press, 1999
  4. Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J. Probabilistic networks and expert systems. Berlin: Springer, 1999.

См. также

Страница курса на сайте лаборатории компьютерной графики и мультимедиа ВМиК МГУ

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

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

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

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