Байесовские методы машинного обучения (курс лекций, Д.П. Ветров, Д.А. Кропотов)/2011

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

Перейти к: навигация, поиск


Курс посвящен т.н. байесовским методам решения различных задач машинного обучения (классификации, прогнозирования, восстановления регрессии), которые в настоящее время активно развиваются в мире. Байесовский подход к теории вероятностей позволяет эффективно учитывать различные предпочтения пользователя при построении решающих правил прогноза. Кроме того, он позволяет решать задачи выбора структурных параметров модели. В частности, здесь удается решать без комбинаторного перебора задачи селекции признаков, выбора числа кластеров в данных, размерности редуцированного пространства при уменьшении размерности, значений коэффициентов регуляризации и проч. В байесовском подходе вероятность интерпретируется как мера незнания, а не как объективная случайность. Простые правила оперирования с вероятностью, такие как формула полной вероятности и формула Байеса, позволяют проводить рассуждения в условиях неопределенности. В этом смысле байесовский подход к теории вероятностей можно рассматривать как обобщение классической булевой логики.

Авторы курса: н.с. каф. ММП Ветров Д.П., м.н.с. ВЦ РАН Кропотов Д.А.. Курс читается студентам ВМиК МГУ, начиная с 2007 года. Курс не требует от студентов дополнительной математической подготовки, выходящей за пределы первых двух курсов университетского образования, все необходимые понятия вводятся в ходе лекций.

Расписание на 2011–2012 учебный год

В осеннем семестре 2011 года спецкурс читается на ВМК по средам в ауд. 523, начало в 16-20.

Дата Название лекции Материалы
7 сентября 2011 Введение в курс. Постановки практических задач, рассматриваемых в курсе. Презентация (PDF, 353Кб)
14 сентября 2011 Лекции не будет
21 сентября 2011 Байесовский подход к теории вероятностей Презентация (PDF, 260Кб)
28 сентября 2011 Применение байесовских методов на примере игры "Акинатор". Выдача первого практического заданияПрезентация (PDF, 304Кб)
5 октября 2011 Задачи выбора моделиПрезентация (PDF, 362Кб)
12 октября 2011 Решение задачи выбора модели по Байесу. Обоснованность моделиПрезентация (PDF, 376Кб)
19 октября 2011 Матричные вычисления и нормальное распределение Текст (PDF, 374Кб)
26 октября 2011 Линейная регрессия и метод релевантных векторов для задачи регрессии Презентация (PDF, 507Кб)
2 ноября 2011 ЕМ-алгоритм и метод релевантных векторов для задачи классификации Текст (PDF, 979Кб)
9 ноября 2011 Приближенные способы байесовского вывода: вариационный подход Текст (PDF, 112Кб)
16 ноября 2011 Приближенные способы байесовского вывода: методы Монте Карло по схеме марковских цепей Текст (PDF, 97Кб)
23 ноября 2011 Байесовский метод главных компонент Текст (PDF, 769Кб)
30 ноября 2011 Байесовская смесь нормальных распределений
7 декабря 2011 Приближенные способы байесовского вывода: подход распространения ожидания Текст (PDF, 203Кб)
14 декабря 2011 Тематические модели для коллекций текстов Текст (PDF, 481Кб)
21 декабря 2011 Экзамен Вопросы к экзамену (PDF, 89Кб)

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

Задание 1. «Посещаемость спецкурса».

Задание 2. «Матричные вычисления».

Задание 3. «Модель Изинга».

Экзамен

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

Вопросы к экзамену (PDF, 89 Кб)

Оценка за курс

В рамках курса студентам предлагается выполнить три практических задания. Выполнение этих заданий является обязательным условием для допуска к экзамену и, соответственно, успешной сдачи курса. Итоговая оценка за курс вычисляется по формуле 0.2*(оценка за первое задание)+0.2*(оценка за второе задание)+0.2*(оценка за третье задание)+0.4*(оценка за экзамен).

ФИО студента Группа Задание 1 Задание 2 Задание 3 Экзамен Итоговая оценка
Вариант Оценка Вариант Оценка Вариант Оценка
Зиннурова Э. 204 1 5.0 1 2
Шадриков А. 204 1 5.0 1 1
Кузьмин А. 206 2 5.0 2 5.0 1 5.0 5.0 5
Гавриков М. 317 2 4.0 2 5.0 1 3.0 4.0 4
Фонарев А. 317 3 4.0 3 5.0 2
Никитин М. 321 3 5.0 3 5.0 1 5.0 5.0 5
Меркулова Т. 417 1 4.5 1 5.0 2 5.0 4.0 4
Гаврилюк К. 417 3 5.0 3 5.0 1 5.0 5.0 5
Кривошеева Т. 419 2 4.0 2 5.0 2 5.0 4.5 5
Лихогруд Н. 520 3 5.0 3 1

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

Введение в курс. Различные постановки задач машинного обучения

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

Ликбез: основные понятия теории вероятностей (математическое ожидание, дисперсия, ковариационная матрица, плотность вероятности, функция правдоподобия), метод максимального правдоподобия.

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

Байесовский подход к теории вероятностей. Примеры байесовских рассуждений.

Частотный и вероятностный подходы к теории вероятностей. Интерпретация вероятности как меры нашего незнания, сравнение байесовских рассуждений с логическими. Байесовские сети и основные задачи в них. Пример жизненной ситуации «Джон и колокольчик для воров». Вывод формул для апостериорных вероятностей.

Ликбез: условная вероятность, формула Байеса и ее применение, формула полной вероятности.

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

Байесовский подход и Акинатор

Пример применения байесовских рассуждений для игры Акинатор. Комментарии к первому практическому заданию.

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

Пример работы программы «Пифия»:

Задача выбора модели на примере выбора коэффициента регуляризации, ядровой функции, настройки структурных параметров алгоритма обучения. Основные методы выбора модели.

Общая постановка проблемы выбора модели, ее философский характер. Конкретные примеры структурных параметров. Кросс-валидация. Теория Вапника-Червоненкиса, емкость алгоритмов обучения. Принцип минимальной длины описания, его эквивалентность максимуму регуляризованного правдоподобия. Информационные критерии Акаике и Байеса-Шварца, область их применения.

Ликбез: теорема Шеннона и оптимальная длина описания.

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

Решение задачи выбора модели по Байесу. Обоснованность модели. Полный байесовский вывод.

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

Ликбез: принцип Оккама, ad hoc гипотезы.

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

Матричные вычисления и нормальное распределение.

Дивергенция Кульбака-Лейблера, ее использование для поиска аппроксимации вероятностных распределений. Векторно-матричные преобразования, дифференцирование по вектору и по матрице. Основные матричные тождества. Одномерное и многомерное нормальное распределение, его основные свойства.

Текст (PDF, 374Кб)
Рекомендуется к прочтению: Заметки по матричным вычислениям и свойствам гауссовских распределений

Линейная регрессия и метод релевантных векторов для задачи регрессии

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

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

EM-алгоритм и метод релевантных векторов для задачи классификации

Метод оптимизации Ньютона. EM-алгоритм в общем виде. EM-алгоритм как покоординатный подъем. ЕМ-алгоритм для задачи разделения смеси нормальных распределений. Логистическая и мультиномиальная регрессия. Метод релевантных векторов для задачи классификации.

Текст (PDF, 979Кб)

Приближенные способы байесовского вывода: вариационный подход.

Приближенные методы байесовского вывода. Минимизация дивергенции Кульбака-Лейблера и факторизованное приближение. Идея вариационного подхода, вывод формул для вариационной линейной регрессии.

Ликбез: дивергенция Кульбака-Лейблера, гамма-распределение.

Текст (PDF, 112Кб)

Приближенные способы байесовского вывода: методы Монте-Карло с марковскими цепями.

Методы Монте Карло для оценки вероятностных интегралов в байесовском подходе. Методы генерации одномерной случайной величины. Идея методов Монте Карло по схеме марковских цепей. Теоретические свойства марковских цепей. Схема Метрополиса-Хастингса. Схема Гиббса. Применение схемы Гиббса для марковских сетей. Оценка нормировочной константы распределения с помощью схемы Гиббса.

Текст (PDF, 97Кб)

Байесовский метод главных компонент.

Задача уменьшения размерности в данных. Метод главных компонент. ЕМ-алгоритм для обучения метода главных компонент. Учет пропусков в данных. Байесовский вариант метода главных компонент для автоматического выбора размерности редуцированного пространства. Модель смеси главных компонент.

Текст (PDF, 769Кб)

Байесовская смесь нормальных распределений.

Автоматический выбор количества компонент в смеси.

Приближенные способы байесовского вывода: подход распространения ожидания (Expectation Propagation).

Экспоненциальное семейство распределений. Минимизация дивергенции Кульбака-Лейблера для экспоненциального семейства распределений. Общая схема Expectation Propagation. Примеры применения.

Ликбез: достаточные статистики.

Текст (PDF, 203Кб)

Тематические модели для коллекций текстов

Тематическая модель Latent Dirichlet Allocation (LDA). Обучение и вывод в модели LDA с помощью вариационного подхода. Вывод в модели LDA с помощью схемы Гиббса. Способы использования LDA.

Ликбез: распределение Дирихле.

Текст (PDF, 481Кб)

Литература

  1. Простые и удобные заметки по матричным вычислениям и свойствам гауссовских распределений
  2. Памятка по теории вероятностей
  3. Ветров Д.П., Кропотов Д.А. Байесовские методы машинного обучения, учебное пособие по спецкурсу, 2007 (Часть 1, PDF 1.22МБ; Часть 2, PDF 1.58МБ)
  4. Bishop C.M. Pattern Recognition and Machine Learning. Springer, 2006.
  5. Mackay D.J.C. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003.
  6. Tipping M. Sparse Bayesian Learning. Journal of Machine Learning Research, 1, 2001, pp. 211-244.
  7. Шумский С.А. Байесова регуляризация обучения. В сб. Лекции по нейроинформатике, часть 2, 2002.
  8. Ветров Д.П., Кропотов Д.А. Алгоритмы выбора моделей и синтеза коллективных решений в задачах классификации, основанные на принципе устойчивости. — М.: УРСС, 2006.

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

2010 год

См. также

Курс «Структурные методы анализа изображений и сигналов»

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

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

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