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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: {{notice| '''ВНИМАНИЕ студентам 3-4 курсов'''<br/> Учебная часть отказывается засчитывать спецкурс, полученный...)
(→Литература)
 
(36 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
{{notice|
+
{{TOCright|300px}}
-
'''ВНИМАНИЕ студентам 3-4 курсов'''<br/>
+
-
Учебная часть отказывается засчитывать спецкурс, полученный ранее, чем требуется учебным планом. Во избежание проблем для студентов принято следующее решение: в конце "нужного" семестра вы подходите ко мне с ведомостью и зачеткой и я вам проставляю оценку в зачетку ЕЩЕ РАЗ (это разрешается) уже в нужный семестр. Одновременно оценка ставится в ведомость, которую вы относите в учебную часть. Текущие ведомости для студентов 3-го курса, заполненные в ходе экзамена, я уничтожил. Вся информация о сдавших нами будет хранится, так что все полученные вами оценки останутся в силе. ведомости 5го курса сданы в учебную часть.
+
-
[[Участник:Dmitry Vetrov|Vetrov]] 15:37, 18 декабря 2009 (MSK)
+
-
}}
+
 +
Спецкурс посвящен математическим методам обработки информации, основанных на использовании внутренних взаимосвязей в данных и их последующем анализе. Эти методы широко используются при решении задач из разных прикладных областей, включая обработку изображений и видео, анализ социальных сетей, распознавание речи, машинное обучение.
-
{{tip|
+
Лекторы: [[Участник:Dmitry Vetrov|Д.П. Ветров]], [[Участник:Kropotov| Д.А. Кропотов]], [[Участник:Anton|А.А. Осокин]].
-
Студентам на заметку: на вкладке «Обсуждение» к данной странице можно задать вопрос по курсу, высказать свои пожелания, предложения и т.п.
+
-
[[Участник:Kropotov|Д.А. Кропотов]], 20 сентября 2009
+
-
}}
+
-
{{TOCright}}
+
[[Изображение:SMAIS_intro_fig.gif|400px]]
-
Курс посвящен математическим методам обработки информации, основанных на выделении структуры в исходных данных и ее последующем анализе. Эти методы широко используются при решении задач из разных прикладных областей, включая обработку изображений и видео, анализ поведения, распознавание речи, машинное обучение.
+
&nbsp;
-
[[Медиа:SMAIS2009_intro.pdf| Краткая презентация о курсе (PDF, 532 Кб)]]
+
&nbsp;
-
[[Изображение:StructuralVision2009-intro.jpg|400px]]
+
&nbsp;
-
== Программа курса ==
+
== Расписание занятий ==
-
<u>Часть 1. Графические модели для анализа изображений.</u>
+
В 2011 году курс читается в весеннем семестре по пятницам на факультете ВМиК МГУ, в ауд. 612, начало в 16-20.
-
=== Введение в курс и понятие графических моделей. ===
+
{| class="standard"
 +
!Дата||Занятие
 +
|-
 +
|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*(оценка за экзамен).
-
[[Медиа:SMAIS-2009-1.pdf| Презентация (PDF, 535 КБ)]]
+
{| class="standard"
 +
!Участник||Группа||Задание 1||Задание 2||Экзамен||Итоговая оценка
 +
|-
 +
|Ромов П.|| align="center"|202 || align="center"|5.0 || align="center"|5.0 || align="center"|5.0 || align="center"|5.0
 +
|-
 +
|Гитман Ю.|| align="center"|205 || align="center"|5.0 || || ||
 +
|-
 +
|Лобачева Е.|| align="center"|209 || align="center"|5.0 || align="center"|5.0 || ||
 +
|-
 +
|Елшин Д.|| align="center"|317 || align="center"|5.0 || align="center"|5.0 || align="center"|4.5 || align="center"|5.0
 +
|-
 +
|Новиков П.|| align="center"|317 || align="center"|4.5 || align="center"|4.5 || align="center"|5.0 || align="center"|5.0
 +
|-
 +
|Некрасов К.|| align="center"|317 || align="center"|4.5 || align="center"|4.0 || align="center"|3.0 || align="center"|4.0
 +
|-
 +
|Меркулова Т.|| align="center"|317 || align="center"|4.5 || align="center"|4.5 || align="center"|5.0 || align="center"|5.0
 +
|-
 +
|Костин Г.|| align="center"|320 || align="center"|4.0 || align="center"|4.5 || align="center"|5.0 || align="center"|5.0
 +
|-
 +
|Шальнов Е.|| align="center"|321 || align="center"|4.5 || align="center"|5.0 || align="center"|5.0 || align="center"|5.0
 +
|-
 +
|Конев А.|| align="center"|321 || align="center"|4.0 || align="center"|4.5 || align="center"|5.0 || align="center"|5.0
 +
|-
 +
|Птенцов С.|| align="center"|321 || align="center"|3.0 || align="center"|3.0 || align="center"|5.0 || align="center"|4.0
 +
|-
 +
|Новикова Т.|| align="center"|321 || align="center"|3.0 ||align="center"|4.0 || align="center"|4.0 || align="center"|4.0
 +
|-
 +
|Сапатов А.|| align="center"|321 || align="center"|3.5 || align="center"|4.0 || align="center"|3.5 || align="center"|4.0
 +
|-
 +
|Батанов П.|| align="center"|321 || || align="center"|3.5 || ||
 +
|-
 +
|Парамонов С.|| align="center"|324 || align="center"|4.0 || align="center"|3.0 || align="center"|4.0 || align="center"|4.0
 +
|-
 +
|Колев Д.|| align="center"|417 || align="center"|5.0 || align="center"|4.5 || align="center"|5.0 || align="center"|5.0
 +
|-
 +
|Тихонов А.|| align="center"|417 || align="center"|3.5 || || ||
 +
|-
 +
|Ермишин Ф.|| align="center"|421 || align="center"|4.5 || align="center"|4.0 || align="center"|5.0 || align="center"|5.0
 +
|-
 +
|Беликов В.|| align="center"|422 || align="center"|4.5 || align="center"|3.5 || ||
 +
|-
 +
|Субботин Н.|| align="center"|422 || align="center"|4.0 || align="center"|3.0 || ||
 +
|-
 +
|Бартунов С.|| align="center"|428 || align="center"|3.5 || || ||
 +
|-
 +
|Казаков И.|| align="center"|432 || align="center"|4.0 || || ||
 +
|-
 +
|Заякина О.|| align="center"|ВВО || align="center"|5.0 || || ||
 +
|-
 +
|}
-
=== Основные графические модели ===
+
== Практические задания ==
-
Байесовские сети. Элементарные способы работы с байесовскими сетями. Марковские сети. Потенциалы на кликах. Примеры использования марковских сетей для анализа изображений. Ликбез: независимость случайных событий. Условная вероятность. Условная независимость.
+
Задание 1. [[Структурные методы анализа изображений и сигналов (курс лекций)/2011/Задание 1|Скрытые марковские модели и линейные динамические системы]].
-
[[Медиа:SMAIS-2009-2a.pdf| Презентация (PDF, 548 КБ)]]
+
Задание 2. [[Структурные методы анализа изображений и сигналов (курс лекций)/2011/Задание 2|TRW и α-расширение]].
-
{|
+
== Экзамен ==
-
|<videoflash type="vimeo">7348738</videoflash>
+
-
|<videoflash type="vimeo">7517616</videoflash>
+
-
|}
+
-
=== Марковские сети и дискретная оптимизация ===
+
К экзамену допускаются только те студенты, которые успешно выполнили оба практических задания. Для студентов 4-ого и 5-ого курса экзамен состоится 13 мая, начало в 13-00, ауд. П-8а. Для остальных студентов экзамен состоится 20 мая, начало в 13-00, ауд. П-8а. При подготовке билета разрешается пользоваться любыми материалами. При ответе ничем пользоваться нельзя. Убедительная просьба при себе иметь экзаменационную ведомость по спецкурсу (достаточно одной для каждой академической группы).
-
Энергетическая формулировка задач компьютерного зрения. Разрезы графов, алгоритмы нахождения максимального потока. Интерактивная сегментация изображений. Энергия, которую можно минимизировать с помощью разрезов графов. Многоуровневые разрезы графов. Приближенная минимизация энергии с помощью разрезов графов. Алгоритм, основанный на замене. Примеры минимизируемых энергий. Сегментация видео. Сшивка изображений. Трехмерная реконструкция.
+
-
[[Медиа:SMISA2009_03.pdf| Презентация (PDF, 2.44 МБ)]]
+
[[Media:SMAIS11_exam_questions.pdf|Вопросы к экзамену (PDF)]]
-
Презентация с тьюториала на Графиконе 2009 по разрезам графов
+
== Программа курса ==
-
[[Медиа:MRFtutorial2.pdf| Презентация (PDF, 742 КБ)]]
+
=== Введение в курс и понятие графических моделей. ===
-
=== Методы настройки марковских случайных полей ===
+
Обзор курса. Задачи анализа структурированных данных. Представление зависимостей между объектами в виде графов. Основные задачи, для решения которых используются графические модели. Демонстрация современных работ, опирающихся на данные в курсе методы.
-
Методы обучения в марковских случайных полях. Применение для семантической сегментации изображений, распознавания объектов с учетом контекста и трехмерной реконструкции.
+
Напоминание основных понятий, которые будут активно использоваться в следующих лекциях. Основные операции с вероятностями (правило суммы, произведения, формула Байеса). Понятия мат. ожидание и матрицы ковариаций. Нормальное распределение. Независимость событий. Маргинализация (исключение переменной). Метод максимального правдоподобия, МАР-оценивание на примере нормального распределения. Матричная нотация (скалярное произведение, следы матриц, квадратичные формы, дифференцирование по вектору). Правило множителей Лагранжа с ограничениями в виде равенств и неравенств.
-
Алгоритмы обмена сообщениями. Belief propagation и Loopy belief propagation.
+
=== Основные графические модели ===
-
[[Медиа:SMAIS-2009-4.pdf| Презентация (PDF, 1.7 Мб)]]
+
Байесовские сети. Элементарные способы работы с байесовскими сетями. Марковские сети. Потенциалы на кликах. Примеры использования марковских сетей для анализа изображений. ''Ликбез: независимость случайных событий. Условная вероятность. Условная независимость.''
-
=== Приближенные методы вывода в графических моделях ===
+
[[Медиа:SMAIS-2009-2a.pdf| Презентация (PDF, 548 КБ)]]<br>
 +
[http://en.wikipedia.org/wiki/Graphical_models Статья в Википедии по графическим моделям]
-
Алгоритмы обмена сообщениями на графах. Алгоритмы Belief Propagation и Tree-ReWeighted Belief Propagation.
+
{|
 +
|<videoflash type="vimeo">7348738</videoflash>
 +
|<videoflash type="vimeo">7517616</videoflash>
 +
|}
-
[[Медиа:SMAIS-Kolmogorov.pdf| Презентация лекции Владимира Колмогорова (PDF, 209 Кб)]]
+
=== Точные методы вывода в ациклических графических моделях: Алгоритм Belief Propagation. ===
-
=== Расширения разрезов графов для сегментации изображений ===
+
Поиск наиболее вероятной конфигурации ацикличной марковской сети с помощью алгоритма Belief Propagation (динамическое программирование). Интерфейс передачи сообщений. Подсчет мин-маргиналов. Поиск маргинальных распределений для графических моделей в форме дерева. Использование произвольных полукольцевых операций в графических моделях.
-
Расширения разрезов графов для сегментации изображений. Branch-and-Mincut. Bounding box prior for interactive segmentation.
+
[[Media:SMAIS-2011-BP.pdf| Конспект лекции (PDF, 64 Кб)]]<br>
 +
[http://en.wikipedia.org/wiki/Belief_propagation Статья в Википедии про алгоритм Belief Propagation]
-
[[Медиа:SMAIS_2009_lempicky.pdf| Презентация лекции Виктора Лемпицкого (PDF, 5.58 Мб)]] [http://courses.graphicon.ru/files/courses/smisa/2009/lectures/lecture06.pptx (PPTX, 13 Мб)]
+
=== Скрытые марковские модели (СММ). Алгоритм сегментации сигнала. ===
-
+
-
<u>Часть 2. Графические модели для анализа и распознавания сигналов.</u>
+
-
=== Скрытые марковские модели. Алгоритм сегментации сигнала ===
+
Примеры задач сегментации сигналов. Обучение СММ с учителем. Поиск наиболее вероятной последовательности состояний. ЕМ-алгоритм и его использование в анализе графических моделей.
-
Примеры задач сегментации сигналов. Обучение НММ с учителем. Поиск наиболее вероятной последовательности состояний. ЕМ-алгоритм и его использование в анализе графических моделей.
+
[[Media:SMAIS_2009_lecture6.pdf|Презентация лекции (PDF, 779 Кб)]]
-
 
+
-
[[Media:SMAIS_2009_lecture6.pdf | Презентация (PDF, 779 Кб)]]
+
=== Обучение СММ без учителя ===
=== Обучение СММ без учителя ===
-
Алгоритм Баума-Уэлша для подсчета условного распределения скрытой переменной в отдельной точке. ЕМ-алгоритм для обучения НММ без учителя. Особенности численной реализации на ЭВМ. Модификации НММ (НММ высших порядков, факториальные НММ, многопоточные НММ, НММ ввода-вывода). Примеры использования НММ.
+
Алгоритм Баума-Уэлша для подсчета условного распределения скрытой переменной в отдельной точке. ЕМ-алгоритм для обучения СММ без учителя. Особенности численной реализации на ЭВМ. Модификации СММ (СММ высших порядков, факториальные СММ, многопоточные СММ, СММ ввода-вывода). Примеры использования СММ.
-
 
+
-
[[Media:SMAIS-2009-8.pdf| Презентация (PDF, 1.01 Мб)]]
+
-
[http://courses.graphicon.ru/main/smisa/lectures/video08_1 Видео-лекция (часть 1)]&nbsp;
+
[[Media:SMAIS-2009-8.pdf|Презентация лекции (PDF, 1.01 Мб)]]
-
[http://courses.graphicon.ru/main/smisa/lectures/video08_2 Видео-лекция (часть 2)]
+
=== Методы фильтрации данных ===
=== Методы фильтрации данных ===
Строка 92: Строка 160:
Линейные динамические системы, фильтр Калмана. Настройка параметров фильтра Калмана. Уравнения Рауса-Тунга-Штрибеля. Расширенный фильтр Калмана, пример использования.
Линейные динамические системы, фильтр Калмана. Настройка параметров фильтра Калмана. Уравнения Рауса-Тунга-Штрибеля. Расширенный фильтр Калмана, пример использования.
-
[[Media:SMAIS2009-10.pdf|Презентация (PDF, 471 Кб)]]
+
[[Media:SMAIS11_LDS.pdf|Конспект лекции (PDF, 135 Кб)]]
-
=== Методы Монте Карло с марковскими цепями===
+
=== Приближенные методы вывода в графических моделях: Tree-ReWeighted Message Passing (TRW). ===
-
Взятие интегралов методами Монте-Карло, голосование по апостериорному распределению вместо точечного решающего правила. Схема Гиббса. Гибридные методы Монте-Карло. Использование методов Монте Карло на примере фильтра частиц.
+
-
[[Media:SMAIS2009-11.pdf| Презентация (PDF, 454 Кб)]]
+
ЛП-релаксация задачи байесовского вывода. Двойственное разложение. Независимость алгоритма TRW от способа разбиений на деревья. Свойства алгоритма TRW для субмодулярной энергии.
-
=== Использование методов обработки сигналов в задачах анализа поведения ===
+
[[Media:SMAIS11_TRW.pdf|Конспект лекции (PDF, 78 Кб)]]
-
Задачи одиночного/множественного трекинга лабораторных животных. Определение числа особей в блобе. Алгоритм разделения особей. Идентификация животных и определение ключевых точек. Сегментация на поведенческие акты.
+
-
[[Media:SMAIS2009-12.pdf|Презентация (PDF, 5.39Мб)]] (Для просмотра необходим [http://get.adobe.com/reader/ Acrobat Reader 9] и выше).
+
=== Алгоритмы на основе разрезов графов ===
-
<u>Часть 3. Методы понижения размерности.</u>
+
Энергетическая формулировка задач компьютерного зрения. Разрезы графов, алгоритмы нахождения максимального потока. Интерактивная сегментация изображений. Энергия, которую можно минимизировать с помощью разрезов графов. Приближенная минимизация энергии с помощью алгоритма альфа-расширения.
-
=== Методы понижения размерности ===
+
[[Media:SMAIS11_GraphCut.pdf|Презентация (PDF, 634 Кб)]]
-
Метод главных компонент. Вероятностный РСА. Анализ независимых компонент. Нелинейное уменьшение размерности.
+
=== Примеры практического применения алгоритмов, обсуждаемых в курсе ===
 +
Восстановление изображений. Сегментация изображений. Стерео. Панорамы. Поиск составных объектов на изображении.
-
[[Media:SMAIS2009-13.pdf|Презентация (PDF, 1.11Мб)]]
+
[[Media:SMAIS11_Practice.pdf|Презентация (PDF, 519 Кб)]]
-
=== Модель активных контуров ===
+
=== [[Метод опорных векторов]] ===
 +
[[Линейный классификатор]]. Оптимальная разделяющая гиперплоскость. Понятие о двойственной задаче условной оптимизации. Получение двойственной задачи для метода опорных векторов, ее свойства. Ядровой переход. Настройка параметров алгоритма.
-
Модель активных контуров и примеры ее применения в задачах компьютерного зрения.
+
[[Media:SMAIS11_SVM.pdf|Конспект лекции (PDF, 204 Кб)]]
-
[[Media:SMAIS2009-9.pdf| Презентация (PDF, 2.11Мб)]]
+
=== Методы настройки марковских случайных полей. Структурный метод опорных векторов. ===
-
== Расписание занятий ==
+
[[Media:SMAIS11_structSVM.pdf|Презентация (PDF, 993 Кб)]]
-
В 2009 году курс читается по четвергам на факультете ВМиК МГУ, в ауд. 671, начало в 18-05.
+
-
{| class="standard"
+
=== Методы Монте Карло по схеме марковских цепей ===
-
!Дата||Занятие
+
Теоретические свойства марковских цепей: однородной, эргодичность и инвариантные распределения. Схема Метрополиса-Хастингса. Схема Гиббса. Примеры применения для дискретных марковских сетей. Фильтр частиц.
-
|-
+
-
|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||Экзамен
+
-
|}
+
-
== Практические задания по курсу ==
+
[[Media:SMAIS11_MCMC.pdf|Конспект лекции (PDF, 90Кб)]]
-
Для успешной сдачи спецкурса необходимо выполнить все практические задания, а также сдать экзамен. Выполненные практические задания следует загружать [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
+
-
|-
+
-
|}
+
-
== Литература ==
+
# [http://matthias.vallentin.net/probability-and-statistics-cookbook/ Памятка по теории вероятностей]
# ''Bishop C.M.'' [http://research.microsoft.com/en-us/um/people/cmbishop/prml/ Pattern Recognition and Machine Learning.] Springer, 2006.
# ''Bishop C.M.'' [http://research.microsoft.com/en-us/um/people/cmbishop/prml/ Pattern Recognition and Machine Learning.] Springer, 2006.
# ''Mackay D.J.C.'' [http://www.inference.phy.cam.ac.uk/mackay/itila/book.html Information Theory, Inference, and Learning Algorithms.] Cambridge University Press, 2003.
# ''Mackay D.J.C.'' [http://www.inference.phy.cam.ac.uk/mackay/itila/book.html Information Theory, Inference, and Learning Algorithms.] Cambridge University Press, 2003.
# ''Jordan M.I. (Ed.)'' Learning in graphical models. Cambridge MA: MIT Press, 1999
# ''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.
# ''Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J.'' Probabilistic networks and expert systems. Berlin: Springer, 1999.
 +
 +
== Страницы курса прошлых лет ==
 +
 +
[[Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)|2009 год]]
== См. также ==
== См. также ==
-
[http://courses.graphicon.ru/main/smisa2009 Страница курса на сайте лаборатории компьютерной графики и мультимедиа ВМиК МГУ]
 
-
[[Байесовские методы машинного обучения (курс лекций, Д.П. Ветров, Д.А. Кропотов, 2009)|Курс «Байесовские методы машинного обучения»]]
+
[[Бммо|Курс «Байесовские методы машинного обучения»]]
[[Спецсеминар "Байесовские методы машинного обучения"|Спецсеминар «Байесовские методы машинного обучения»]]
[[Спецсеминар "Байесовские методы машинного обучения"|Спецсеминар «Байесовские методы машинного обучения»]]

Текущая версия

Содержание

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

Лекторы: Д.П. Ветров, Д.А. Кропотов, А.А. Осокин.

 

 

 

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

В 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)

Программа курса

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

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

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

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

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

Презентация (PDF, 548 КБ)
Статья в Википедии по графическим моделям

Точные методы вывода в ациклических графических моделях: Алгоритм Belief Propagation.

Поиск наиболее вероятной конфигурации ацикличной марковской сети с помощью алгоритма Belief Propagation (динамическое программирование). Интерфейс передачи сообщений. Подсчет мин-маргиналов. Поиск маргинальных распределений для графических моделей в форме дерева. Использование произвольных полукольцевых операций в графических моделях.

Конспект лекции (PDF, 64 Кб)
Статья в Википедии про алгоритм Belief Propagation

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

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

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

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

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

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

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

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

Конспект лекции (PDF, 135 Кб)

Приближенные методы вывода в графических моделях: Tree-ReWeighted Message Passing (TRW).

ЛП-релаксация задачи байесовского вывода. Двойственное разложение. Независимость алгоритма TRW от способа разбиений на деревья. Свойства алгоритма TRW для субмодулярной энергии.

Конспект лекции (PDF, 78 Кб)

Алгоритмы на основе разрезов графов

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

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

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

Восстановление изображений. Сегментация изображений. Стерео. Панорамы. Поиск составных объектов на изображении.

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

Метод опорных векторов

Линейный классификатор. Оптимальная разделяющая гиперплоскость. Понятие о двойственной задаче условной оптимизации. Получение двойственной задачи для метода опорных векторов, ее свойства. Ядровой переход. Настройка параметров алгоритма.

Конспект лекции (PDF, 204 Кб)

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

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

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

Теоретические свойства марковских цепей: однородной, эргодичность и инвариантные распределения. Схема Метрополиса-Хастингса. Схема Гиббса. Примеры применения для дискретных марковских сетей. Фильтр частиц.

Конспект лекции (PDF, 90Кб)

Литература

  1. Памятка по теории вероятностей
  2. Bishop C.M. Pattern Recognition and Machine Learning. Springer, 2006.
  3. Mackay D.J.C. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003.
  4. Jordan M.I. (Ed.) Learning in graphical models. Cambridge MA: MIT Press, 1999
  5. Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J. Probabilistic networks and expert systems. Berlin: Springer, 1999.

Страницы курса прошлых лет

2009 год

См. также

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

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

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

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%BD%D1%8B%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0_%D0%B8%D0%B7%D0%BE%D0%B1%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D0%B9_%D0%B8_%D1%81%D0%B8%D0%B3%D0%BD%D0%B0%D0%BB%D0%BE%D0%B2_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%29»
Личные инструменты