Структурные методы анализа изображений и сигналов (курс лекций)

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

Версия от 16:18, 10 февраля 2011; Kropotov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
ВНИМАНИЕ студентам 3-4 курсов

Учебная часть отказывается засчитывать спецкурс, полученный ранее, чем требуется учебным планом. Во избежание проблем для студентов принято следующее решение: в конце "нужного" семестра вы подходите ко мне с ведомостью и зачеткой и я вам проставляю оценку в зачетку ЕЩЕ РАЗ (это разрешается) уже в нужный семестр. Одновременно оценка ставится в ведомость, которую вы относите в учебную часть. Текущие ведомости для студентов 3-го курса, заполненные в ходе экзамена, я уничтожил. Вся информация о сдавших нами будет хранится, так что все полученные вами оценки останутся в силе. ведомости 5го курса сданы в учебную часть. Vetrov 15:37, 18 декабря 2009 (MSK)



Студентам на заметку: на вкладке «Обсуждение» к данной странице можно задать вопрос по курсу, высказать свои пожелания, предложения и т.п.

Д.А. Кропотов, 20 сентября 2009


Содержание

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

Краткая презентация о курсе (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.

См. также

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

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

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

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

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