Машинное обучение (курс лекций, К.В.Воронцов)

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

(Различия между версиями)
Перейти к: навигация, поиск
(Байесовская теория классификации)
Строка 105: Строка 105:
* Вероятностная интерпретация регуляризации, совместное правдоподобие данных и модели. Принцип максимума апостериорной вероятности.
* Вероятностная интерпретация регуляризации, совместное правдоподобие данных и модели. Принцип максимума апостериорной вероятности.
* Гауссовский и лапласовский регуляризаторы.
* Гауссовский и лапласовский регуляризаторы.
-
* [[Логистическая регрессия]]: для двух классов, для многих классов. Регуляризованная логистическая регрессия. [[Калибровка Платта]].
+
* [[Логистическая регрессия]]. Принцип максимума правдоподобия и логарифмическая функция потерь. [[Метод стохастического градиента]] для логарифмической функции потерь. Сглаженное правило Хэбба. Многоклассовая логистическая регрессия. Регуляризованная логистическая регрессия. [[Калибровка Платта]].
<!--
<!--
* Функции потерь, зависящие от цены ошибок. [[Кривая ошибок]] (ROC curve). Алгоритм эффективного построения ROC-кривой.
* Функции потерь, зависящие от цены ошибок. [[Кривая ошибок]] (ROC curve). Алгоритм эффективного построения ROC-кривой.
Строка 147: Строка 147:
* [[Метод Ньютона-Рафсона]], [[метод Ньютона-Гаусса]].
* [[Метод Ньютона-Рафсона]], [[метод Ньютона-Гаусса]].
* Обобщённая аддитивная модель (GAM): [[метод настройки с возвращениями]] (backfitting) Хасти-Тибширани.
* Обобщённая аддитивная модель (GAM): [[метод настройки с возвращениями]] (backfitting) Хасти-Тибширани.
-
* [[Логистическая регрессия]]. Метод наименьших квадратов с итерационным взвешиванием (IRLS).
+
* [[Логистическая регрессия]]. [[Метод наименьших квадратов с итеративным пересчётом весов]] (IRLS). Пример прикладной задачи: кредитный скоринг. Бинаризация признаков. Скоринговые карты и оценивание вероятности дефолта. ''Риск кредитного портфеля банка.''
* [[Обобщённая линейная модель]] (GLM). Экспоненциальное семейство распределений.
* [[Обобщённая линейная модель]] (GLM). Экспоненциальное семейство распределений.
* Неквадратичные функции потерь. Метод наименьших модулей. Квантильная регрессия. Пример прикладной задачи: прогнозирование потребительского спроса.
* Неквадратичные функции потерь. Метод наименьших модулей. Квантильная регрессия. Пример прикладной задачи: прогнозирование потребительского спроса.
* Робастная регрессия, функции потерь с горизонтальными асимптотами.
* Робастная регрессия, функции потерь с горизонтальными асимптотами.
 +
<!---
 +
* [[Логистическая регрессия]]. Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
 +
--->
== Критерии выбора моделей и методы отбора признаков ==
== Критерии выбора моделей и методы отбора признаков ==
Строка 204: Строка 207:
* ''Робастное оценивание. Цензурирование выборки (отсев объектов-выбросов).''
* ''Робастное оценивание. Цензурирование выборки (отсев объектов-выбросов).''
-
== Логистическая регрессия. Разделение смеси распределений ==
+
== Разделение смеси распределений ==
-
Презентация: [[Media:Voron-ML-Bayes2-slides.pdf|(PDF,&nbsp;0,8&nbsp;МБ)]] {{важно|— обновление 20.04.2015}}.
+
Презентация: [[Media:Voron-ML-Bayes2-slides.pdf|(PDF,&nbsp;1,7&nbsp;МБ)]] {{важно|— обновление 26.04.2016}}.
-
* Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
 
-
* [[Логистическая регрессия]]. Принцип максимума правдоподобия и логарифмическая функция потерь.
 
-
* [[Метод стохастического градиента]] для логарифмической функции потерь. Сглаженное правило Хэбба.
 
-
* [[Метод наименьших квадратов с итеративным пересчётом весов]] (IRLS).
 
-
* Пример прикладной задачи: кредитный скоринг. Бинаризация признаков. Скоринговые карты и оценивание вероятности дефолта. ''Риск кредитного портфеля банка.''
 
* [[Смесь распределений]].
* [[Смесь распределений]].
* [[EM-алгоритм]]: основная идея, понятие скрытых переменных. Теорема об эквивалентной системе уравнений. ЕМ алгоритм как метод простых итераций.
* [[EM-алгоритм]]: основная идея, понятие скрытых переменных. Теорема об эквивалентной системе уравнений. ЕМ алгоритм как метод простых итераций.
Строка 218: Строка 216:
* Смесь многомерных нормальных распределений. [[Сеть радиальных базисных функций]] (RBF) и применение EM-алгоритма для её настройки.
* Смесь многомерных нормальных распределений. [[Сеть радиальных базисных функций]] (RBF) и применение EM-алгоритма для её настройки.
* Сопоставление RBF-сети и SVM с гауссовским ядром.
* Сопоставление RBF-сети и SVM с гауссовским ядром.
-
 
-
== Кластеризация ==
 
-
Презентация: [[Media:Voron-ML-Clustering-slides.pdf|(PDF,&nbsp;1,7&nbsp;МБ)]] {{важно|— обновление 27.04.2015}}.
 
-
* Постановка задачи [[кластеризация|кластеризации]]. Примеры прикладных задач. Типы кластерных структур.
 
* Статистические алгоритмы: [[EM-алгоритм]] и [[Алгоритм k средних]] (k-means).
* Статистические алгоритмы: [[EM-алгоритм]] и [[Алгоритм k средних]] (k-means).
-
* [[Нейронная сеть Кохонена]]. [[Конкурентное обучение]], стратегии WTA и WTM.
 
-
* [[Самоорганизующаяся карта Кохонена]]. Применение для визуального анализа данных. Искусство интерпретации карт Кохонена.
 
-
* [[Агломеративная кластеризация]], [[Алгоритм Ланса-Вильямса]] и его частные случаи.
 
-
* Алгоритм построения [[дендрограмма|дендрограммы]]. Определение числа кластеров.
 
-
* Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
 
-
<!--* ''Потоковые (субквадратичные) алгоритмы кластеризации.''
 
-
* [[Графовые алгоритмы кластеризации]]. Выделение связных компонент. [[Кратчайший незамкнутый путь]].
 
-
* [[Алгоритм ФОРЭЛ]].
 
-
* Функционалы качества кластеризации.
 
-
* [[Многомерное шкалирование]], примеры прикладных задач.
 
-
* Субквадратичный алгоритм, псевдокод. Минимизация функционала стресса методом Ньютона-Рафсона.
 
-
* Визуализация: [[карта сходства]], [[диаграмма Шепарда]].
 
-
* Совмещение многомерного шкалирования и иерархической кластеризации.
 
-
-->
 
= Второй семестр =
= Второй семестр =
Строка 318: Строка 298:
* [[Алгоритм FP-growth]]. Понятия FP-дерева и условного FP-дерева. Два этапа поиска частых наборов в FP-growth: построение FP-дерева и рекурсивное порождение частых наборов.
* [[Алгоритм FP-growth]]. Понятия FP-дерева и условного FP-дерева. Два этапа поиска частых наборов в FP-growth: построение FP-дерева и рекурсивное порождение частых наборов.
* Общее представление о динамических и иерархических методах поиска ассоциативных правил.
* Общее представление о динамических и иерархических методах поиска ассоциативных правил.
 +
 +
== Кластеризация ==
 +
Презентация: [[Media:Voron-ML-Clustering-slides.pdf|(PDF,&nbsp;1,7&nbsp;МБ)]] {{важно|— обновление 27.04.2015}}.
 +
* Постановка задачи [[кластеризация|кластеризации]]. Примеры прикладных задач. Типы кластерных структур.
 +
* Статистические алгоритмы: [[EM-алгоритм]] и [[Алгоритм k средних]] (k-means).
 +
* [[Нейронная сеть Кохонена]]. [[Конкурентное обучение]], стратегии WTA и WTM.
 +
* [[Самоорганизующаяся карта Кохонена]]. Применение для визуального анализа данных. Искусство интерпретации карт Кохонена.
 +
* [[Агломеративная кластеризация]], [[Алгоритм Ланса-Вильямса]] и его частные случаи.
 +
* Алгоритм построения [[дендрограмма|дендрограммы]]. Определение числа кластеров.
 +
* Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
 +
<!--* ''Потоковые (субквадратичные) алгоритмы кластеризации.''
 +
* [[Графовые алгоритмы кластеризации]]. Выделение связных компонент. [[Кратчайший незамкнутый путь]].
 +
* [[Алгоритм ФОРЭЛ]].
 +
* Функционалы качества кластеризации.
 +
* [[Многомерное шкалирование]], примеры прикладных задач.
 +
* Субквадратичный алгоритм, псевдокод. Минимизация функционала стресса методом Ньютона-Рафсона.
 +
* Визуализация: [[карта сходства]], [[диаграмма Шепарда]].
 +
* Совмещение многомерного шкалирования и иерархической кластеризации.
 +
-->
== Задачи с частичным обучением ==
== Задачи с частичным обучением ==

Версия 21:04, 26 апреля 2016

Содержание

Теория обучения машин (machine learning, машинное обучение) находится на стыке прикладной статистики, численных методов оптимизации, дискретного анализа, и за последние 50 лет оформилась в самостоятельную математическую дисциплину. Методы машинного обучения составляют основу ещё более молодой дисциплины — интеллектуального анализа данных (data mining).

В курсе рассматриваются основные задачи обучения по прецедентам: классификация, кластеризация, регрессия, понижение размерности. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами.

Все методы излагаются по единой схеме:

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

Данный курс расширяет и углубляет набор тем, рекомендованный международным стандартом ACM/IEEE Computing Curricula 2001 по дисциплине «Машинное обучение и нейронные сети» (machine learning and neural networks) в разделе «Интеллектуальные системы» (intelligent systems).

Курс читается

На материал данного курса опираются последующие кафедральные курсы. На кафедре ММП ВМиК МГУ параллельно с данным курсом и в дополнение к нему читается спецкурс Теория надёжности обучения по прецедентам, посвящённый проблемам переобучения и оценивания обобщающей способности.

От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание математической статистики, методов оптимизации и какого-либо языка программирования желательно, но не обязательно.

Ниже представлена расширенная программа — в полном объёме она занимает больше, чем могут вместить в себя два семестра. Каждый параграф приблизительно соответствует одной лекции. Курсивом выделен дополнительный материал, который может разбираться на семинарах.

Замечания для студентов

  • Видеолекции ШАД Яндекс.
  • На подстранице имеется перечень вопросов к устному экзамену. Очень помогает при подготовке к устному экзамену!
  • О найденных ошибках и опечатках сообщайте мне. — К.В.Воронцов 18:24, 19 января 2009 (MSK)
  • Материал, который есть в pdf-тексте, но не рассказывался на лекциях, обычно не входит в программу экзамена.

Первый семестр

Текст лекций: (PDF, 3 МБ) — обновление 4.10.2011.

Основные понятия и примеры прикладных задач

Презентация: (PDF, 1,4 МБ) — обновление 09.02.2016.

Метрические методы классификации и регрессии

Презентация: (PDF, 3,0 МБ) — обновление 18.02.2016.

Логические методы классификации

Текст лекций: (PDF, 625 КБ).
Презентация: (PDF, 1.8 МБ) — обновление 25.02.2016.

Факультатив

  • Статистический критерий информативности, точный тест Фишера. Сравнение областей эвристических и статистических закономерностей. Асимптотическая эквивалентность статистического и энтропийного критерия информативности. Разнообразие критериев информативности в (p,n)-пространстве.
  • Решающий пень. Бинаризация признаков. Алгоритм разбиения области значений признака на информативные зоны.
  • Решающий список. Жадный алгоритм синтеза списка.
  • Преобразование решающего дерева в решающий список.

Градиентные методы обучения

Презентация: (PDF, 1,3 МБ) — обновление 03.03.2016.

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

Презентация: (PDF, 1,2 МБ) — обновление 10.03.2016.

  • Оптимальная разделяющая гиперплоскость. Понятие зазора между классами (margin).
  • Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией регуляризованного эмпирического риска. Кусочно-линейная функция потерь.
  • Задача квадратичного программирования и двойственная задача. Понятие опорных векторов.
  • Рекомендации по выбору константы C.
  • Функция ядра (kernel functions), спрямляющее пространство, теорема Мерсера.
  • Способы конструктивного построения ядер. Примеры ядер.
  • SVM-регрессия.
  • Регуляризации для отбора признаков: LASSO SVM, Elastic Net SVM, SFM, RFM.
  • Метод релевантных векторов RVM

Многомерная линейная регрессия

Презентация: (PDF, 0,6 MБ) — обновление 22.03.2016.

Нелинейная регрессия

Презентация: (PDF, 0,7 MБ) — обновление 29.03.2016.

Критерии выбора моделей и методы отбора признаков

Текст лекций: (PDF, 330 КБ).
Презентация: (PDF, 1,0 МБ) — обновление 05.03.2015.
Презентация: (PDF, 1,3 МБ) — обновление 05.04.2016.

Прогнозирование временных рядов

Презентация: (PDF, 0,9 MБ) — обновление 12.04.2016.

Байесовская теория классификации

Презентация: (PDF, 1,1 МБ) — обновление 14.04.2016.

Разделение смеси распределений

Презентация: (PDF, 1,7 МБ) — обновление 26.04.2016.

  • Смесь распределений.
  • EM-алгоритм: основная идея, понятие скрытых переменных. Теорема об эквивалентной системе уравнений. ЕМ алгоритм как метод простых итераций.
  • Детали реализации EM-алгоритма. Критерий останова. Выбор начального приближения. Выбор числа компонентов смеси.
  • Стохастический EM-алгоритм.
  • Смесь многомерных нормальных распределений. Сеть радиальных базисных функций (RBF) и применение EM-алгоритма для её настройки.
  • Сопоставление RBF-сети и SVM с гауссовским ядром.
  • Статистические алгоритмы: EM-алгоритм и Алгоритм k средних (k-means).

Второй семестр

Нейронные сети

Презентация: (PDF, 1,4 МБ) — обновление 13.10.2015.

Линейные композиции, бустинг

Текст лекций: (PDF, 1 MБ).
Презентация: (PDF, 0.9 МБ) — обновление 08.09.2015.

Эвристические, стохастические, нелинейные композиции

Презентация: (PDF, 0.9 МБ) — обновление 08.09.2015.

  • Стохастические методы: бэггинг и метод случайных подпространств.
  • Случайный лес. Анализ смещения и вариации для простого голосования.
  • Смесь алгоритмов (квазилинейная композиция), область компетентности, примеры функций компетентности.
  • Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
  • Построение смеси алгоритмов с помощью EM-подобного алгоритма.
  • Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии. Задача монотонизации выборки, изотонная регрессия.

Ранжирование

Презентация: (PDF, 0,5 МБ) — обновление 14.10.2014.

  • Постановка задачи обучения ранжированию. Примеры.
  • Признаки в задаче ранжирования поисковой выдачи: текстовые, ссылочные, кликовые. TF-IDF. PageRank.
  • Критерии качества ранжирования: Precision, MAP, AUC, DCG, NDCG, pFound.
  • Ранговая классификация, OC-SVM.
  • Попарный подход: RankingSVM, RankNet, LambdaRank.

Поиск ассоциативных правил

Презентация: (PDF, 1.1 МБ) — обновление 20.10.2015.

  • Понятие ассоциативного правила и его связь с понятием логической закономерности.
  • Примеры прикладных задач: анализ рыночных корзин, выделение терминов и тематики текстов.
  • Алгоритм APriori. Два этапа: поиск частых наборов и рекурсивное порождение ассоциативных правил. Недостатки и пути усовершенствования алгоритма APriori.
  • Алгоритм FP-growth. Понятия FP-дерева и условного FP-дерева. Два этапа поиска частых наборов в FP-growth: построение FP-дерева и рекурсивное порождение частых наборов.
  • Общее представление о динамических и иерархических методах поиска ассоциативных правил.

Кластеризация

Презентация: (PDF, 1,7 МБ) — обновление 27.04.2015.

Задачи с частичным обучением

Презентация: (PDF, 1.0 МБ) — обновление 28.10.2015.

  • Постановка задачи Semisupervised Learning, примеры приложений.
  • Простые эвристические методы: self-training, co-training, co-learning.
  • Адаптация алгоритмов кластеризации для решения задач с частичным обучением. Кратчайшиё незамкнутый путь. Алгоритм Ланса-Уильямса. Алгоритм k-средних.
  • Трансдуктивный метод опорных векторов TSVM.
  • Алгоритм Expectation-Regularization на основе многоклассовой регуляризированной логистической регрессии.

Коллаборативная фильтрация

Презентация: (PDF, 1.5 МБ) — обновление 13.04.2014.

Тематическое моделирование

Текст лекций: (PDF, 830 КБ).
Презентация 1: (PDF, 2.8 МБ) — обновление 16.11.2015. Презентация 2: (PDF, 6.1 МБ) — обновление 16.11.2015.

Обучение с подкреплением

Презентация: (PDF, 0.9 МБ) — обновление 16.11.2015.

  • Задача о многоруком бандите. Жадные и эпсилон-жадные стратегии. Метод UCB (upper confidence bound). Стратегия Softmax.
  • Среда для экспериментов.
  • Адаптивные стратегии на основе скользящих средних. Метод сравнения с подкреплением. Метод преследования.
  • Постановка задачи при наличии информации о среде в случае выбора действия. Контекстный многорукий бандит.
  • Линейная регрессионная модель с верхней доверительной оценкой LinUCB.
  • Оценивание новой стратегии по большим историческим данным.
  • Постановка задачи в случае, когда агент влияет на среду. Ценность состояния среды. Ценность действия.
  • Жадные стратегии максимизации ценности. Уравнения оптимальности Беллмана.
  • Метод временных разностей TD(0). Метод SARSA. Метод Q-обучения.
  • Многошаговое TD-прогнозирование. Обобщения методов временных разностей, SARSA, Q-обучения.

См. также

Список подстраниц

Машинное обучение (курс лекций, К.В.Воронцов)/2009Машинное обучение (курс лекций, К.В.Воронцов)/ToDoМашинное обучение (курс лекций, К.В.Воронцов)/Вопросы
Машинное обучение (курс лекций, К.В.Воронцов)/Семестровый курсМашинное обучение (курс лекций, К.В.Воронцов)/Форма отчета
Личные инструменты