Графические модели (курс лекций)/2017

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

(Различия между версиями)
Перейти к: навигация, поиск
(Расписание занятий)
(Система выставления оценок по курсу)
 
(6 промежуточных версий не показаны.)
Строка 3: Строка 3:
{|border = "0"
{|border = "0"
| valign="top"|[[Изображение:Mrf.jpg|300px]]
| valign="top"|[[Изображение:Mrf.jpg|300px]]
-
| valign="top"|Курс посвящен математическим методам обработки информации, основанных на использовании внутренних взаимосвязей в данных и их последующем анализе. Эти методы широко используются при решении задач из разных прикладных областей, включая обработку изображений и видео, анализ социальных сетей, распознавание речи, машинное обучение.
+
| valign="top"|Курс посвящен математическим методам обработки информации, основанных на использовании внутренних взаимосвязей в данных и их последующем анализе. Эти методы широко используются при решении задач из разных прикладных областей, включая обработку изображений и видео, анализ социальных сетей, помехоустойчивое кодирование, распознавание речи, машинное обучение.
Целью курса является освоение математического аппарата для работы с графическими моделями. Предполагается, что в результате прохождения курса студенты обретут навыки самостоятельного построения графических моделей для решения задач из различных прикладных областей; будут способны решать задачи настройки параметров графических моделей по данным, определять подходящую структуру графической модели, выбирать методы, наиболее эффективные для работы с построенной моделью; получат опыт применения графических моделей для различных задач анализа изображений, сигналов, сетей.
Целью курса является освоение математического аппарата для работы с графическими моделями. Предполагается, что в результате прохождения курса студенты обретут навыки самостоятельного построения графических моделей для решения задач из различных прикладных областей; будут способны решать задачи настройки параметров графических моделей по данным, определять подходящую структуру графической модели, выбирать методы, наиболее эффективные для работы с построенной моделью; получат опыт применения графических моделей для различных задач анализа изображений, сигналов, сетей.
Строка 13: Строка 13:
По всем вопросам, связанным с курсом, просьба писать на ''bayesml@gmail.com'', в название письма обязательно добавлять [ВМК ГМ17].
По всем вопросам, связанным с курсом, просьба писать на ''bayesml@gmail.com'', в название письма обязательно добавлять [ВМК ГМ17].
 +
 +
== Новости ==
 +
 +
'''20.03.17''' Выложено первое практическое задание по низкоплотностным кодам. Срок сдачи — '''2 апреля (воскресенье), 23:59'''
 +
 +
'''31.03.17''' Выложено второе практическое задание по разрезам графов и коллажам. Срок сдачи — '''16 апреля (воскресенье), 23:59'''
 +
 +
'''28.04.17''' Добавлен список вопросов к экзамену
 +
 +
== Экзамен ==
 +
Экзамен по курсу состоится 3 мая в ауд. 582, начало в 12-00. На экзамене при подготовке билета разрешается пользоваться любыми материалами. При непосредственном ответе ничем пользоваться нельзя. В билете два вопроса.
 +
 +
[[Media:GM17_exam_questions.pdf|Вопросы к экзамену]]
== Практические задания ==
== Практические задания ==
Строка 27: Строка 40:
| rowspan=2|10 февраля 2017 || rowspan=2 align="center"|1 || Лекция «Графические модели: байесовские и марковские сети, примеры применения» || [[Media:GM13_1.pdf|Презентация]] по байесовским рассуждениям и графическим моделям
| rowspan=2|10 февраля 2017 || rowspan=2 align="center"|1 || Лекция «Графические модели: байесовские и марковские сети, примеры применения» || [[Media:GM13_1.pdf|Презентация]] по байесовским рассуждениям и графическим моделям
|-
|-
-
|Семинар «Фактор-графы, задачи вывода в ГМ, решение практических задач с помощью ГМ» || [[Media:GM_applied_tasks.pdf|Презентация]] по практическим задачам
+
|Семинар «Условная независимость в байесовских и марковских сетях, фактор-графы, решение практических задач с помощью ГМ» || [[Media:GM_applied_tasks.pdf|Презентация]] по практическим задачам
|-
|-
| rowspan=2|17 февраля 2017 || rowspan=2 align="center"|2 || Лекция «Алгоритм Belief Propagation (BP) для вывода в ациклических графических моделях» || [[Media:SMAIS-2011-BP.pdf|Конспект]] по алгоритмам передачи сообщений
| rowspan=2|17 февраля 2017 || rowspan=2 align="center"|2 || Лекция «Алгоритм Belief Propagation (BP) для вывода в ациклических графических моделях» || [[Media:SMAIS-2011-BP.pdf|Конспект]] по алгоритмам передачи сообщений
Строка 64: Строка 77:
== Система выставления оценок по курсу ==
== Система выставления оценок по курсу ==
-
В рамках курса предполагается два практических задания и два домашних задания. Каждое практическое задание оценивается из 5-ти баллов, домашнее задание – из 2-х баллов.
+
В рамках курса предполагается два практических задания. Каждое задание оценивается из 5-ти баллов.
# При наличии несданных заданий максимальная возможная оценка за курс — это «удовлетворительно».
# При наличии несданных заданий максимальная возможная оценка за курс — это «удовлетворительно».
-
# Необходимым условием получения положительной оценки за курс является сдача не менее одного практического задания, не менее одного домашнего задания и сдача устного экзамена не менее чем на оценку «удовлетворительно».
+
# Необходимым условием получения положительной оценки за курс является сдача не менее одного практического задания и сдача устного экзамена не менее чем на оценку «удовлетворительно».
-
# Итоговый балл за курс вычисляется по формуле <tex>\frac{5}{14}*Homework+Oral</tex>, где HomeWork — баллы, набранные за задания, а Oral — оценка за устный экзамен (0, 3, 4, 5). Для получения итоговой оценки 5 необходимо набрать 8 итоговых баллов, для оценки 4 — 6 баллов, для оценки 3 — 4 балла.
+
# Итоговый балл за курс вычисляется по формуле 0.25*<Оценка_за_задание_1> + 0.25*<Оценка_за_задание_2> + 0.5*<Оценка_за_экзамен> с округлением в большую сторону.
# Штраф за просрочку сдачи заданий начисляется из расчета 0.1 балла в день, но не более 3 баллов.
# Штраф за просрочку сдачи заданий начисляется из расчета 0.1 балла в день, но не более 3 баллов.
-
 
-
<!--
 
-
== Программа курса ==
 
-
 
-
=== Введение в курс и понятие графических моделей. Байесовские и марковские сети. ===
 
-
 
-
Обзор курса. Задачи анализа структурированных данных. Представление зависимостей между объектами в виде графов. Байесовские сети. Элементарные способы работы с байесовскими сетями. Марковские сети. Потенциалы на кликах. Примеры использования марковских сетей для анализа изображений.
 
-
 
-
''Ликбез: независимость случайных событий. Условная вероятность. Условная независимость.''
 
-
 
-
[http://en.wikipedia.org/wiki/Graphical_models Статья в Википедии по графическим моделям]
 
-
 
-
{|
 
-
|<videoflash type="vimeo">7348738</videoflash>
 
-
|<videoflash type="vimeo">7517616</videoflash>
 
-
|}
 
-
 
-
[[Media:Lecture1 GM.pdf|Презентация лекции (PDF, 1.01 Мб)]]
 
-
 
-
=== Точные методы вывода в ациклических графических моделях: Алгоритм Belief Propagation. ===
 
-
 
-
Поиск наиболее вероятной конфигурации ацикличной марковской сети с помощью алгоритма Belief Propagation (динамическое программирование). Интерфейс передачи сообщений. Подсчет мин-маргиналов. Поиск маргинальных распределений для графических моделей в форме дерева. Использование произвольных полукольцевых операций в графических моделях.
 
-
 
-
[[Media:SMAIS-2011-BP.pdf| Конспект лекции (PDF, 64 Кб)]]<br>
 
-
[http://en.wikipedia.org/wiki/Belief_propagation Статья в Википедии про алгоритм Belief Propagation]
 
-
 
-
=== Скрытые марковские модели (СММ). Алгоритм сегментации сигнала ===
 
-
 
-
Примеры задач сегментации сигналов. Обучение СММ с учителем. Поиск наиболее вероятной последовательности состояний (алгоритм Витерби).
 
-
 
-
=== Линейные динамические системы. Фильтр Калмана ===
 
-
 
-
Свойства многомерного нормального распределения. Задача сопровождения объекта. Линейные динамические системы, фильтр Калмана. Обучение параметров линейной динамической системы с учителем. Расширенный фильтр Калмана, пример использования.
 
-
 
-
[[Media:GM12_4.pdf|Конспект лекции (PDF, 281Кб)]]
 
-
 
-
=== Обучение СММ без учителя ===
 
-
 
-
ЕМ-алгоритм и его использование в анализе графических моделей. Алгоритм Баума-Уэлша для подсчета условного распределения скрытой переменной в отдельной точке. ЕМ-алгоритм для обучения СММ без учителя. Особенности численной реализации на ЭВМ. Модификации СММ (СММ высших порядков, факториальные СММ, многопоточные СММ, СММ ввода-вывода). Примеры использования СММ.
 
-
 
-
[[Media:lecture5.pdf|Презентация (PDF, 1.2Мб)]]
 
-
 
-
=== Алгоритмы на основе разрезов графов ===
 
-
 
-
Энергетическая формулировка задач компьютерного зрения. Разрезы графов, алгоритмы нахождения максимального потока. Интерактивная сегментация изображений. Энергия, которую можно минимизировать с помощью разрезов графов. Приближенная минимизация энергии с помощью алгоритма альфа-расширения.
 
-
 
-
[[Media:Lecture6.pdf| Презентация (PDF, 618 Кб)]]
 
-
 
-
=== Приближенные методы вывода в графических моделях: Tree-ReWeighted Message Passing (TRW). ===
 
-
 
-
ЛП-релаксация задачи байесовского вывода. Двойственное разложение. Независимость алгоритма TRW от способа разбиений на деревья. Свойства алгоритма TRW для субмодулярной энергии.
 
-
 
-
[[Media:TRW.pdf|Конспект лекции (PDF, 86Кб)]]
 
-
 
-
=== Методы настройки марковских случайных полей. Структурный метод опорных векторов. ===
 
-
Задача структурного обучения. Метод опорных векторов для случая многих классов. Структурный метод опорных векторов. Обучение с помощью метода отсекающей плоскости. Обучение с помощью двойственной задачи. Примеры.
 
-
 
-
[[Media:SMAIS11_SSVM.pdf|Конспект лекции (PDF, 103Кб)]]
 
-
 
-
=== Методы Монте Карло по схеме марковских цепей ===
 
-
Генерация выборки из одномерных распределений. Теоретические свойства марковских цепей: однородность, эргодичность и инвариантные распределения. Схема Метрополиса-Хастингса. Схема Гиббса. Примеры применения для дискретных марковских сетей. Фильтр частиц.
 
-
 
-
[[Media:GM12_9.pdf|Конспект лекции (PDF, 121Кб)]]
 
-
 
-
=== Вариационный вывод ===
 
-
-->
 
== Литература ==
== Литература ==

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


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

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

Лектор: Д.П. Ветров,

Семинаристы: Д.А. Кропотов, Кирилл Струминский.

По всем вопросам, связанным с курсом, просьба писать на bayesml@gmail.com, в название письма обязательно добавлять [ВМК ГМ17].

Новости

20.03.17 Выложено первое практическое задание по низкоплотностным кодам. Срок сдачи — 2 апреля (воскресенье), 23:59

31.03.17 Выложено второе практическое задание по разрезам графов и коллажам. Срок сдачи — 16 апреля (воскресенье), 23:59

28.04.17 Добавлен список вопросов к экзамену

Экзамен

Экзамен по курсу состоится 3 мая в ауд. 582, начало в 12-00. На экзамене при подготовке билета разрешается пользоваться любыми материалами. При непосредственном ответе ничем пользоваться нельзя. В билете два вопроса.

Вопросы к экзамену

Практические задания

Приём заданий по курсу осуществляется в системе anytask.org. Для получения инвайта по курсу просьба писать на почту курса.

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

В 2017 году курс читается на факультете ВМиК МГУ по пятницам в ауд. 526б, начало в 14-35 (лекция) и 16-20 (семинар).

Дата № занятия Занятие Материалы
10 февраля 2017 1 Лекция «Графические модели: байесовские и марковские сети, примеры применения» Презентация по байесовским рассуждениям и графическим моделям
Семинар «Условная независимость в байесовских и марковских сетях, фактор-графы, решение практических задач с помощью ГМ» Презентация по практическим задачам
17 февраля 2017 2 Лекция «Алгоритм Belief Propagation (BP) для вывода в ациклических графических моделях» Конспект по алгоритмам передачи сообщений
Семинар «Алгоритмы передачи сообщений»
3 марта 2017 3 Лекция «Помехоустойчивое кодирование, теорема Шеннона, линейные коды, коды с малой плотностью проверок на чётность» LDPC-коды в Википедии
Семинар «Вывод формул для алгоритма декодирования в LDPC-кодах, выдача задания по кодированию»
10 марта 2017 4 Лекция «Скрытые марковские модели. Алгоритм сегментации сигнала, обучение с учителем и без учителя» Презентация 1, Презентация 2
Семинар «Расширения скрытых марковских моделей»
17 марта 2017 5 Лекция «Линейные динамические системы. Фильтр Калмана. Расширенный фильтр Калмана.» Конспект по ЛДС
Семинар «Вывод формул фильтра Калмана»
24 марта 2017 6 Лекция «Алгоритмы на основе разрезов графов, \alpha-расширение.» Презентация, конспект по разрезам графов
Семинар «Алгоритмы разрезов графов»
31 марта 2017 7 Лекция «Алгоритм Tree-ReWeighted Message Passing (TRW) для вывода в циклических графических моделях» Конспект по TRW
Семинар «Двойственное разложение»
7 апреля 2017 8 Лекция «Вариационная передача сообщений» Методы вывода как алгоритмы передачи сообщений
Семинар «Фильтр частиц»
14 апреля 2017 9 Лекция «Подход Expectation Propagation для приближённого вывода в графических моделях»
Семинар «Модель TrueSkill» Презентация по TrueSkill

Система выставления оценок по курсу

В рамках курса предполагается два практических задания. Каждое задание оценивается из 5-ти баллов.

  1. При наличии несданных заданий максимальная возможная оценка за курс — это «удовлетворительно».
  2. Необходимым условием получения положительной оценки за курс является сдача не менее одного практического задания и сдача устного экзамена не менее чем на оценку «удовлетворительно».
  3. Итоговый балл за курс вычисляется по формуле 0.25*<Оценка_за_задание_1> + 0.25*<Оценка_за_задание_2> + 0.5*<Оценка_за_экзамен> с округлением в большую сторону.
  4. Штраф за просрочку сдачи заданий начисляется из расчета 0.1 балла в день, но не более 3 баллов.

Литература

  1. Barber D. Bayesian Reasoning and Machine Learning. Cambridge University Press, 2012.
  2. Murphy K.P. Machine Learning: A Probabilistic Perspective. The MIT Press, 2012.
  3. Bishop C.M. Pattern Recognition and Machine Learning. Springer, 2006.
  4. Mackay D.J.C. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003.
  5. Wainwright M.J., Jordan M.I. Graphical Models, Exponential Families, and Variational Inference. Foundations and Trends in Machine Learning, NOWPress, 2008.
  6. Koller D., Friedman N. Probabilistic Graphical Models: Principles and Techniques. The MIT Press, 2009.

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

2016 год

2015 год

2014 год

2013 год

2012 год

2011 год

2009 год

См. также

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

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

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

Онлайн-курс Стэнфордского университета по вероятностным графическим моделям

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