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

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

(Различия между версиями)
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
-
__NOTOC__
+
#REDIRECT [[Графические модели (курс лекций)/2014]]
-
 
+
-
{|border = "0"
+
-
| valign="top"|[[Изображение:Mrf.jpg|300px]]
+
-
| valign="top"|Курс посвящен математическим методам обработки информации, основанных на использовании внутренних взаимосвязей в данных и их последующем анализе. Эти методы широко используются при решении задач из разных прикладных областей, включая обработку изображений и видео, анализ социальных сетей, распознавание речи, машинное обучение. До 2011 года курс читался как спецкурс [[Структурные методы анализа изображений и сигналов (курс лекций)/2011|«Структурные методы анализа изображений и сигналов»]].
+
-
 
+
-
Целью курса является освоение математического аппарата для работы с графическими моделями. Предполагается, что в результате прохождения курса студенты обретут навыки самостоятельного построения графических моделей для решения задач из различных прикладных областей; будут способны решать задачи настройки параметров графических моделей по данным, определять подходящую структуру графической модели, выбирать методы, наиболее эффективные для работы с построенной моделью; получат опыт применения графических моделей для различных задач анализа изображений, сигналов, сетей.
+
-
|}
+
-
 
+
-
Лектор: [[Участник:Dmitry Vetrov|Д.П. Ветров]],
+
-
 
+
-
Семинарист: [[Участник:Anton|А.А. Осокин]],
+
-
 
+
-
Ассистент: [[Участник:Kropotov|Д.А. Кропотов]].
+
-
 
+
-
Вопросы и комментарии по курсу можно оставлять на вкладке «Обсуждение» к этой странице или направлять письмом по адресу ''bayesml@gmail.com''. При этом в название письма просьба добавлять [ГМ14].
+
-
 
+
-
== Расписание занятий ==
+
-
 
+
-
В 2014 году курс читается на факультете [[ВМиК]] МГУ по вторникам в ауд. 510, начало в 14-35 (лекция) и 16-20 (семинар).
+
-
 
+
-
{| class="standard"
+
-
!Дата !! № занятия !! Занятие !! Материалы
+
-
|-
+
-
| rowspan=2|11 февраля 2014 || rowspan=2 align="center"|1 || Лекция «Введение в курс. Байесовские рассуждения.» || rowspan=3|[[Media:GM13_1.pdf|Презентация (pdf)]] по байесовским рассуждениям и графическим моделям
+
-
|-
+
-
|Семинар «Правила работы с вероятностями, байесовские рассуждения»
+
-
|-
+
-
| rowspan=2|18 февраля 2014 || rowspan=2 align="center"|2 || Лекция «Графические модели: байесовские и марковские сети»
+
-
|-
+
-
|Семинар «Фактор-графы, задачи вывода в ГМ, решение практических задач с помощью ГМ» || [[Media:GM_applied_tasks.pdf|Презентация по практическим задачам (pdf)]]
+
-
|-
+
-
| rowspan=2|25 февраля 2014 || rowspan=2 align="center"|3 || Лекция «Алгоритм Belief Propagation (BP) для вывода в ациклических графических моделях. Алгоритм Loopy BP» || [[Media:SMAIS-2011-BP.pdf|Конспект по алгоритмам передачи сообщений (pdf)]]
+
-
|-
+
-
|Семинар «Алгоритмы передачи сообщений» ||
+
-
|-
+
-
| rowspan=2|4 марта 2014 || rowspan=2 align="center"|4 || Лекция «Помехоустойчивое кодирование, теорема Шеннона, линейные коды, коды с малой плотностью проверок на чётность» || [http://ru.wikipedia.org/wiki/LDPC LDPC-коды] в Википедии
+
-
|-
+
-
|Семинар «Вывод формул для алгоритма декодирования в LDPC-кодах, выдача задания по кодированию» ||
+
-
|-
+
-
| rowspan=2|11 марта 2014 || rowspan=2 align="center"|5 || Лекция «Скрытые марковские модели. Алгоритм сегментации сигнала, обучение с учителем» || [[Media:GM12_3.pdf|Презентация (pdf)]]
+
-
|-
+
-
|Семинар «Скрытые марковские модели» ||
+
-
|-
+
-
| rowspan=2|18 марта 2014 || rowspan=2 align="center"|6 || Лекция «ЕМ-алгоритм. Обучение скрытых марковских моделей без учителя.» || [[Media:GM13_em_hmm_unsupervised.pdf|Презентация (pdf)]]
+
-
|-
+
-
|Семинар «Матричные вычисления» || [[Media:Matrix-Gauss.pdf|Конспект по матричным вычислениям и нормальному распределению (pdf)]]
+
-
|-
+
-
| rowspan=2|25 марта 2014 || rowspan=2 align="center"|7 || Лекция «Линейные динамические системы. Фильтр Калмана. Расширенный фильтр Калмана.» || [[Media:LDS.pdf|Конспект по ЛДС (pdf)]]
+
-
|-
+
-
|Семинар «Контрольная по матричным вычислениям. ЕМ-алгоритм» ||
+
-
|-
+
-
| rowspan=2|1&nbsp;апреля&nbsp;2014 || rowspan=2 align="center"|8 || Лекция «Алгоритмы на основе разрезов графов, <tex>\alpha</tex>-расширение.»
+
-
|| [[Media:Lecture6.pdf| Презентация (pdf)]], [[Media:GM_graphCuts.pdf‎|Конспект по разрезам графов (pdf)]]
+
-
|-
+
-
| Семинар «Алгоритмы разрезов графов» ||
+
-
|-
+
-
| rowspan=2|8&nbsp;апреля&nbsp;2014 || rowspan=2 align="center"|9 || Лекция «Алгоритм Tree-ReWeighted Message Passing (TRW) для вывода в циклических графических моделях» || [[Media:TRW.pdf| Конспект по TRW (pdf)]]
+
-
|-
+
-
|Семинар «Двойственное разложение» ||
+
-
|-
+
-
|rowspan=2|15&nbsp;апреля&nbsp;2014 || rowspan=2 align="center"|10 || Лекция «Структурный метод опорных векторов (SSVM)» || [[Media:SMAIS11_SSVM.pdf|Конспект по SSVM (pdf)]]
+
-
|-
+
-
|Семинар «Структурный метод опорных векторов» ||
+
-
|-
+
-
|rowspan=2|22&nbsp;апреля&nbsp;2014 || rowspan=2 align="center"|11 || Лекция «Методы Монте Карло по схеме марковских цепей (MCMC)» || [[Media:MCMC.pdf|Конспект по MCMC (pdf)]]
+
-
|-
+
-
|Семинар «Методы MCMC» ||
+
-
|-
+
-
|rowspan=2|29&nbsp;апреля&nbsp;2014 || rowspan=2 align="center"|12 || Лекция «Вариационный вывод» || [[Media:Variational_inference.pdf|Конспект по вариационному выводу (pdf)]]
+
-
|-
+
-
|Семинар «Вариационный вывод» ||
+
-
|-
+
-
|rowspan=2|6&nbsp;мая&nbsp;2014 || rowspan=2 align="center"|13 || Лекция «Вероятностные методы обучения графических моделей, экспоненциальное семейство распределений» ||
+
-
|-
+
-
|Семинар «Экспоненциальное семейство распределений» ||
+
-
|-
+
-
|rowspan=2|13&nbsp;мая&nbsp;2014 || rowspan=2 align="center"|14 || Лекция «Байесовский подход для выбора графической модели» ||
+
-
|-
+
-
|Семинар «Контрольная по вариационному выводу» ||
+
-
|-
+
-
|}
+
-
 
+
-
== Практические задания ==
+
-
 
+
-
Задание 1. «Байесовские рассуждения».
+
-
 
+
-
Задание 2. «Алгоритм Loopy Belief Propagation для LDPC-кодов».
+
-
 
+
-
Задание 3. «Алгоритмы минимизации энергии для задачи стерео».
+
-
 
+
-
Задание 4. «Модель Изинга».
+
-
 
+
-
== Оценки по курсу ==
+
-
 
+
-
{|class = "standard"
+
-
! rowspan=2|№ п/п !! rowspan=2|Студент !! colspan=4|Практические задания !! rowspan=2|Сумма !! rowspan=2|Экзамен !! rowspan=2|Оценка
+
-
|-
+
-
! №1 !! №2 !! №3 !! №4
+
-
|-
+
-
| align="center"|1 || Алешин Илья || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|2 || Антипов Алексей || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|3 || Арбузова Дарья || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|4 || [[Участник:Algor|Горелов Алексей]] || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|5 || Зиннурова Эльвира (C) || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|6 || Ломов Никита || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|7 || Львов Сергей || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|8 || Найдин Олег || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|9 || Никифоров Андрей || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|10 || Новиков Александр || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|11 || Петров Григорий || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|12 || Подоприхин Дмитрий || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|13 || [[Участник:Alex.Ryzhkov|Рыжков Александр]] || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|14 || Сокурский Юрий || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|15 || Ульянов Дмитрий || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|16 || Харациди Олег || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|17 || Шабашев Федор || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
| align="center"|18 || [[Участник:SdvAnd|Шадриков Андрей]] || <!--З1--> align="center"| || <!--З2--> align="center"| || <!--З3--> align="center"| || <!--З4--> align="center"| || <!--S--> align="center"| || <!--E--> align="center"| || <!--M--> align="center"|
+
-
|-
+
-
|}
+
-
 
+
-
== Система выставления оценок по курсу ==
+
-
 
+
-
# При наличии несданных заданий максимальная возможная оценка за курс — это «удовлетворительно».
+
-
# Необходимым условием получения положительной оценки за курс является сдача не менее двух практических заданий и сдача устного экзамена не менее чем на оценку «удовлетворительно».
+
-
# Итоговая оценка вычисляется по формуле <tex>Mark = \frac{Oral*4+HomeWork}{8}</tex>, где Oral — оценка за устный экзамен (0, 3, 4, 5), HomeWork — баллы, набранные за практические задания (см. таблицу выше), Mark — итоговая оценка по 5-балльной шкале. Нецелые значения округляются в сторону ближайшего целого, <b>превосходящего</b> дробное значение. Максимальный балл за HomeWork равен 20.
+
-
# На экзамене студент может отказаться от оценки и пойти на пересдачу, на которой может заново получить Oral.
+
-
# За каждое несданное задание выставляется минус 10 баллов в баллы по заданиям (допускаются отрицательные значения).
+
-
# Если на экзамене итоговая оценка оказывается ниже трех, то студент отправляется на пересдачу. При этом оценка Oral, полученная на пересдаче, <b>добавляется</b> к положительной (три и выше) оценке Oral, полученной на основном экзамене и т.д. до тех пор, пока студент не наберет на итоговую оценку «удовлетворительно» (для итоговых оценок выше «удовлетворительно» оценки Oral не суммируются).
+
-
# Студент может досдать недостающие практические задания в любое время. При этом проверка задания гарантируется только в том случае, если задание сдано не позднее, чем за неделю до основного экзамена или пересдачи.
+
-
# Штраф за просрочку сдачи заданий начисляется из расчета 0.1 балла в день, но не более 5 баллов.
+
-
# В случае успешной сдачи всех практических заданий студент получает возможность претендовать на итоговую оценку «хорошо» и «отлично». При этом экзамен на оценку Oral может сдаваться до сдачи всех заданий (оценки Oral в этом случае <b>не суммируются</b>).
+
-
# Экзамен на оценку Oral сдается либо в срок основного экзамена, либо в срок официальных пересдач.
+
-
 
+
-
<!--
+
-
== Программа курса ==
+
-
 
+
-
=== Введение в курс и понятие графических моделей. Байесовские и марковские сети. ===
+
-
 
+
-
Обзор курса. Задачи анализа структурированных данных. Представление зависимостей между объектами в виде графов. Байесовские сети. Элементарные способы работы с байесовскими сетями. Марковские сети. Потенциалы на кликах. Примеры использования марковских сетей для анализа изображений.
+
-
 
+
-
''Ликбез: независимость случайных событий. Условная вероятность. Условная независимость.''
+
-
 
+
-
[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Кб)]]
+
-
 
+
-
=== Вариационный вывод ===
+
-
-->
+
-
 
+
-
== Литература ==
+
-
 
+
-
# ''Barber D.'' [http://web4.cs.ucl.ac.uk/staff/D.Barber/textbook/290313.pdf Bayesian Reasoning and Machine Learning.] Cambridge University Press, 2012.
+
-
# ''Murphy K.P.'' Machine Learning: A Probabilistic Perspective. The MIT Press, 2012.
+
-
# ''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.
+
-
# ''Wainwright M.J., Jordan M.I.'' [http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJor08_FTML.pdf Graphical Models, Exponential Families, and Variational Inference.] Foundations and Trends in Machine Learning, NOWPress, 2008.
+
-
# ''Koller D., Friedman N.'' [http://www.twirpx.com/file/804418/ Probabilistic Graphical Models: Principles and Techniques.] The MIT Press, 2009.
+
-
# ''Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J.'' Probabilistic networks and expert systems. Berlin: Springer, 1999.
+
-
# [http://matthias.vallentin.net/probability-and-statistics-cookbook/ Памятка по теории вероятностей]
+
-
 
+
-
== Страницы курса прошлых лет ==
+
-
 
+
-
[[Графические модели (курс лекций)/2013|2013 год]]
+
-
 
+
-
[[Графические модели (курс лекций)/2012|2012 год]]
+
-
 
+
-
[[Структурные методы анализа изображений и сигналов (курс лекций)/2011|2011 год]]
+
-
 
+
-
[[Структурные методы анализа изображений и сигналов (курс лекций, А.С. Конушин, Д.П. Ветров, Д.А. Кропотов, О.В. Баринова, В.С. Конушин, 2009)|2009 год]]
+
-
 
+
-
== См. также ==
+
-
 
+
-
[[Бммо|Курс «Байесовские методы машинного обучения»]]
+
-
 
+
-
[[Спецсеминар "Байесовские методы машинного обучения"|Спецсеминар «Байесовские методы машинного обучения»]]
+
-
 
+
-
[[Математические методы прогнозирования (кафедра ВМиК МГУ)]]
+
-
 
+
-
[https://www.coursera.org/course/pgm Онлайн-курс Стэнфордского университета по вероятностным графическим моделям]
+
-
 
+
-
[[Категория:Учебные курсы]]
+
-
[[Категория:Байесовские методы]]
+

Версия 12:32, 3 февраля 2014

  1. REDIRECT Графические модели (курс лекций)/2014
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%93%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8_%28%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%29»
Личные инструменты