|
|
| (240 промежуточных версий не показаны.) |
| Строка 1: |
Строка 1: |
| - | {{TOCright|300px}}
| + | #REDIRECT [[Графические модели (курс лекций)/2015]] |
| - | | + | |
| - | Спецкурс посвящен математическим методам обработки информации, основанных на использовании внутренних взаимосвязей в данных и их последующем анализе. Эти методы широко используются при решении задач из разных прикладных областей, включая обработку изображений и видео, анализ социальных сетей, распознавание речи, машинное обучение.
| + | |
| - | | + | |
| - | Лекторы: [[Участник:Dmitry Vetrov|Д.П. Ветров]], [[Участник:Kropotov| Д.А. Кропотов]], [[Участник:Anton|А.А. Осокин]].
| + | |
| - | | + | |
| - | [[Изображение:SMAIS_intro_fig.gif|400px]]
| + | |
| - | | + | |
| - |
| + | |
| - | | + | |
| - |
| + | |
| - | | + | |
| - |
| + | |
| - | | + | |
| - | == Расписание занятий ==
| + | |
| - | | + | |
| - | В 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*(оценка за экзамен).
| + | |
| - | | + | |
| - | {| 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|Скрытые марковские модели и линейные динамические системы]].
| + | |
| - | | + | |
| - | Задание 2. [[Структурные методы анализа изображений и сигналов (курс лекций)/2011/Задание 2|TRW и α-расширение]].
| + | |
| - | | + | |
| - | == Экзамен ==
| + | |
| - | | + | |
| - | К экзамену допускаются только те студенты, которые успешно выполнили оба практических задания. Для студентов 4-ого и 5-ого курса экзамен состоится 13 мая, начало в 13-00, ауд. П-8а. Для остальных студентов экзамен состоится 20 мая, начало в 13-00, ауд. П-8а. При подготовке билета разрешается пользоваться любыми материалами. При ответе ничем пользоваться нельзя. Убедительная просьба при себе иметь экзаменационную ведомость по спецкурсу (достаточно одной для каждой академической группы).
| + | |
| - | | + | |
| - | [[Media:SMAIS11_exam_questions.pdf|Вопросы к экзамену (PDF)]]
| + | |
| - | | + | |
| - | == Программа курса ==
| + | |
| - | | + | |
| - | === Введение в курс и понятие графических моделей. ===
| + | |
| - | | + | |
| - | Обзор курса. Задачи анализа структурированных данных. Представление зависимостей между объектами в виде графов. Основные задачи, для решения которых используются графические модели. Демонстрация современных работ, опирающихся на данные в курсе методы.
| + | |
| - | | + | |
| - | Напоминание основных понятий, которые будут активно использоваться в следующих лекциях. Основные операции с вероятностями (правило суммы, произведения, формула Байеса). Понятия мат. ожидание и матрицы ковариаций. Нормальное распределение. Независимость событий. Маргинализация (исключение переменной). Метод максимального правдоподобия, МАР-оценивание на примере нормального распределения. Матричная нотация (скалярное произведение, следы матриц, квадратичные формы, дифференцирование по вектору). Правило множителей Лагранжа с ограничениями в виде равенств и неравенств.
| + | |
| - | | + | |
| - | === Основные графические модели ===
| + | |
| - | | + | |
| - | Байесовские сети. Элементарные способы работы с байесовскими сетями. Марковские сети. Потенциалы на кликах. Примеры использования марковских сетей для анализа изображений. ''Ликбез: независимость случайных событий. Условная вероятность. Условная независимость.''
| + | |
| - | | + | |
| - | [[Медиа:SMAIS-2009-2a.pdf| Презентация (PDF, 548 КБ)]]<br>
| + | |
| - | [http://en.wikipedia.org/wiki/Graphical_models Статья в Википедии по графическим моделям]
| + | |
| - | | + | |
| - | {|
| + | |
| - | |<videoflash type="vimeo">7348738</videoflash>
| + | |
| - | |<videoflash type="vimeo">7517616</videoflash>
| + | |
| - | |}
| + | |
| - | | + | |
| - | === Точные методы вывода в ациклических графических моделях: Алгоритм Belief Propagation. ===
| + | |
| - | | + | |
| - | Поиск наиболее вероятной конфигурации ацикличной марковской сети с помощью алгоритма Belief Propagation (динамическое программирование). Интерфейс передачи сообщений. Подсчет мин-маргиналов. Поиск маргинальных распределений для графических моделей в форме дерева. Использование произвольных полукольцевых операций в графических моделях.
| + | |
| - | | + | |
| - | [[Media:SMAIS-2011-BP.pdf| Конспект лекции (PDF, 64 Кб)]]<br>
| + | |
| - | [http://en.wikipedia.org/wiki/Belief_propagation Статья в Википедии про алгоритм Belief Propagation]
| + | |
| - | | + | |
| - | === Скрытые марковские модели (СММ). Алгоритм сегментации сигнала. ===
| + | |
| - | | + | |
| - | Примеры задач сегментации сигналов. Обучение СММ с учителем. Поиск наиболее вероятной последовательности состояний. ЕМ-алгоритм и его использование в анализе графических моделей.
| + | |
| - | | + | |
| - | [[Media:SMAIS_2009_lecture6.pdf|Презентация лекции (PDF, 779 Кб)]]
| + | |
| - | | + | |
| - | === Обучение СММ без учителя ===
| + | |
| - | | + | |
| - | Алгоритм Баума-Уэлша для подсчета условного распределения скрытой переменной в отдельной точке. ЕМ-алгоритм для обучения СММ без учителя. Особенности численной реализации на ЭВМ. Модификации СММ (СММ высших порядков, факториальные СММ, многопоточные СММ, СММ ввода-вывода). Примеры использования СММ.
| + | |
| - | | + | |
| - | [[Media:SMAIS-2009-8.pdf|Презентация лекции (PDF, 1.01 Мб)]]
| + | |
| - | | + | |
| - | === Методы фильтрации данных ===
| + | |
| - | | + | |
| - | Линейные динамические системы, фильтр Калмана. Настройка параметров фильтра Калмана. Уравнения Рауса-Тунга-Штрибеля. Расширенный фильтр Калмана, пример использования.
| + | |
| - | | + | |
| - | [[Media:SMAIS11_LDS.pdf|Конспект лекции (PDF, 135 Кб)]]
| + | |
| - | | + | |
| - | === Приближенные методы вывода в графических моделях: Tree-ReWeighted Message Passing (TRW). ===
| + | |
| - | | + | |
| - | ЛП-релаксация задачи байесовского вывода. Двойственное разложение. Независимость алгоритма TRW от способа разбиений на деревья. Свойства алгоритма TRW для субмодулярной энергии.
| + | |
| - | | + | |
| - | [[Media:SMAIS11_TRW.pdf|Конспект лекции (PDF, 78 Кб)]]
| + | |
| - | | + | |
| - | === Алгоритмы на основе разрезов графов ===
| + | |
| - | | + | |
| - | Энергетическая формулировка задач компьютерного зрения. Разрезы графов, алгоритмы нахождения максимального потока. Интерактивная сегментация изображений. Энергия, которую можно минимизировать с помощью разрезов графов. Приближенная минимизация энергии с помощью алгоритма альфа-расширения.
| + | |
| - | | + | |
| - | [[Media:SMAIS11_GraphCut.pdf|Презентация (PDF, 634 Кб)]]
| + | |
| - | | + | |
| - | === Примеры практического применения алгоритмов, обсуждаемых в курсе ===
| + | |
| - | Восстановление изображений. Сегментация изображений. Стерео. Панорамы. Поиск составных объектов на изображении.
| + | |
| - | | + | |
| - | [[Media:SMAIS11_Practice.pdf|Презентация (PDF, 519 Кб)]]
| + | |
| - | | + | |
| - | === [[Метод опорных векторов]] ===
| + | |
| - | [[Линейный классификатор]]. Оптимальная разделяющая гиперплоскость. Понятие о двойственной задаче условной оптимизации. Получение двойственной задачи для метода опорных векторов, ее свойства. Ядровой переход. Настройка параметров алгоритма.
| + | |
| - | | + | |
| - | [[Media:SMAIS11_SVM.pdf|Конспект лекции (PDF, 204 Кб)]]
| + | |
| - | | + | |
| - | === Методы настройки марковских случайных полей. Структурный метод опорных векторов. ===
| + | |
| - | | + | |
| - | [[Media:SMAIS11_structSVM.pdf|Презентация (PDF, 993 Кб)]]
| + | |
| - | | + | |
| - | === Методы Монте Карло по схеме марковских цепей ===
| + | |
| - | Теоретические свойства марковских цепей: однородной, эргодичность и инвариантные распределения. Схема Метрополиса-Хастингса. Схема Гиббса. Примеры применения для дискретных марковских сетей. Фильтр частиц.
| + | |
| - | | + | |
| - | [[Media:SMAIS11_MCMC.pdf|Конспект лекции (PDF, 90Кб)]]
| + | |
| - | | + | |
| - | == Литература ==
| + | |
| - | | + | |
| - | # [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.
| + | |
| - | # ''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
| + | |
| - | # ''Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J.'' Probabilistic networks and expert systems. Berlin: Springer, 1999.
| + | |
| - | | + | |
| - | == Страницы курса прошлых лет ==
| + | |
| - | | + | |
| - | [[Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)|2009 год]]
| + | |
| - | | + | |
| - | == См. также ==
| + | |
| - | | + | |
| - | [[Бммо|Курс «Байесовские методы машинного обучения»]]
| + | |
| - | | + | |
| - | [[Спецсеминар "Байесовские методы машинного обучения"|Спецсеминар «Байесовские методы машинного обучения»]]
| + | |
| - | | + | |
| - | [[Математические методы прогнозирования (кафедра ВМиК МГУ)]]
| + | |
| - | | + | |
| - | [[Категория:Учебные курсы]]
| + | |
| - | [[Категория:Байесовские методы]]
| + | |
