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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (уточнение)
(Программа ММРО, весна 2009, кафедра ММП ВМиК МГУ)
Строка 174: Строка 174:
=== Алгоритмические композиции ===
=== Алгоритмические композиции ===
* Основные понятия: [[базовый алгоритм]] ([[алгоритмический оператор]]), [[корректирующая операция]].
* Основные понятия: [[базовый алгоритм]] ([[алгоритмический оператор]]), [[корректирующая операция]].
-
* Линейные (выпуклые) алгоритмические композиции.
+
* [[Простое голосование]] (комитет большинства). Эвристический алгоритм. Идентификация нетипичных объектов (выбросов). Обобщение на большое число классов.
-
* Процесс последовательного обучения базовых алгоритмов.
+
* [[Решающий список]] (комитет старшинства). Эвристический алгоритм. Стратегия выбора классов для базовых алгоритмов.
-
* [[Простое голосование]] (комитет большинства). Эвристический алгоритм.
+
-
* [[Решающий список]] (комитет старшинства). Эвристический алгоритм.
+
=== Бустинг, бэггинг и аналоги ===
=== Бустинг, бэггинг и аналоги ===
* [[Взвешенное голосование]].
* [[Взвешенное голосование]].
-
* Экспоненциальная аппроксимация пороговой функции потерь. Теорема о сходимости [[бустинг]]а.
+
* Экспоненциальная аппроксимация пороговой функции потерь.
 +
* Процесс последовательного обучения базовых алгоритмов.
 +
* Теорема о сходимости [[бустинг]]а.
* Псевдокод: [[алгоритм AdaBoost]].
* Псевдокод: [[алгоритм AdaBoost]].
-
* Варианты бустинга: GentleBoost, LogitBoost, BrownBoost, и другие.
+
<!---* Варианты бустинга: GentleBoost, LogitBoost, BrownBoost, и другие.--->
* Стохастические методы: [[бэггинг]] и [[метод случайных подпространств]].
* Стохастические методы: [[бэггинг]] и [[метод случайных подпространств]].
 +
<!---
=== Метод комитетов ===
=== Метод комитетов ===
* Общее понятие: [[комитет]] системы ограничений. Комитеты большинства, простое и взвешенное голосование (''z,p''-комитеты).
* Общее понятие: [[комитет]] системы ограничений. Комитеты большинства, простое и взвешенное голосование (''z,p''-комитеты).
Строка 192: Строка 193:
* [[Максимальная совместная подсистема]], [[минимальный комитет]]. Теоремы об ''NP''-полноте задачи поиска минимального комитета.
* [[Максимальная совместная подсистема]], [[минимальный комитет]]. Теоремы об ''NP''-полноте задачи поиска минимального комитета.
* Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.
* Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.
 +
--->
=== Нелинейные алгоритмические композиции ===
=== Нелинейные алгоритмические композиции ===
Строка 197: Строка 199:
* Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
* Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
* Построение смесей экспертов с помощью EM-алгоритма.
* Построение смесей экспертов с помощью EM-алгоритма.
-
* Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии.
+
<!---* Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии. --->
=== Оценивание и выбор моделей ===
=== Оценивание и выбор моделей ===
* Внутренние и [[внешние критерии]].
* Внутренние и [[внешние критерии]].
-
* [[Скользящий контроль]].
+
* [[Скользящий контроль]], разновидности скользящего контроля.
* [[Критерий непротиворечивости]].
* [[Критерий непротиворечивости]].
* [[Регуляризация]].
* [[Регуляризация]].
* Критерии, основанные на оценках обобщающей способности: Вапника-Червоненкиса, [[критерий Акаике]] (AIC), [[байесовский информационный критерий]] (BIC).
* Критерии, основанные на оценках обобщающей способности: Вапника-Червоненкиса, [[критерий Акаике]] (AIC), [[байесовский информационный критерий]] (BIC).
-
* Статистические критерии: [[коэффициент детерминации]], [[критерий Фишера]], [[анализ остатков]].
+
<!---* Статистические критерии: [[коэффициент детерминации]], [[критерий Фишера]], [[анализ регрессионных остатков]]. --->
 +
* Агрегированные и многоступенчатые критерии.
=== Методы отбора признаков ===
=== Методы отбора признаков ===
* Сложность задачи [[отбор признаков|отбора признаков]]. [[Полный перебор]].
* Сложность задачи [[отбор признаков|отбора признаков]]. [[Полный перебор]].
-
* [[Метод добавления и удаления]] (шаговая регрессия).
+
* [[Метод добавления и удаления]], шаговая регрессия.
-
* [[Поиск в глубину]] (метод ветвей и границ).
+
* [[Поиск в глубину]], метод ветвей и границ.
-
* Усечённый [[поиск в ширину]] ([[многорядный итерационный алгоритм МГУА]]).
+
* Усечённый [[поиск в ширину]], [[многорядный итерационный алгоритм МГУА]].
* [[Генетический алгоритм]], его сходство с МГУА.
* [[Генетический алгоритм]], его сходство с МГУА.
-
* [[Случайный поиск с адаптацией]] (СПА).
+
* [[Случайный поиск]] и [[Случайный поиск с адаптацией]] (СПА).
=== Логические алгоритмы классификации ===
=== Логические алгоритмы классификации ===
-
* Понятие [[логическая закономерность|логической закономерности]]. Эвристическое, статистическое, энтропийное определение [[информативность|информативности]]. Асимптотическая эквивалентность статистического и энтропийного определения. Принципиальные отличия эвристического и статистического определения.
+
* Понятие [[логическая закономерность|логической закономерности]]. Эвристическое, статистическое, энтропийное определение [[информативность|информативности]]. Асимптотическая эквивалентность статистического и энтропийного определения. Сравнение областей эвристических и статистических закономерностей.
* Разновидности закономерностей: шары, гиперплоскости, гиперпараллелепипеды (конъюнкции).
* Разновидности закономерностей: шары, гиперплоскости, гиперпараллелепипеды (конъюнкции).
* [[Бинаризация признаков]], алгоритм выделения информативных зон.
* [[Бинаризация признаков]], алгоритм выделения информативных зон.
Строка 232: Строка 235:
* Принцип голосования. Проблема различности (диверсификации) закономерностей.
* Принцип голосования. Проблема различности (диверсификации) закономерностей.
* Методы синтеза конъюнктивных закономерностей. Псевдокод: [[алгоритм КОРА]], [[алгоритм ТЭМП]].
* Методы синтеза конъюнктивных закономерностей. Псевдокод: [[алгоритм КОРА]], [[алгоритм ТЭМП]].
-
* Алгоритм бустинга. Теорема сходимости.
+
* Алгоритм бустинга. Теорема сходимости. Критерий информативности в бустинге.
* Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.
* Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.
Строка 248: Строка 251:
=== Кластеризация ===
=== Кластеризация ===
-
* Постановка задачи [[кластеризация|кластеризации]]. Примеры прикладных задач.
+
* Постановка задачи [[кластеризация|кластеризации]]. Примеры прикладных задач. Типы кластерных структур.
-
* [[Графовые алгоритмы кластеризации]]. Алгоритм связных компонент.
+
* [[Графовые алгоритмы кластеризации]]. Выделение связных компонент. [[Кратчайший незамкнутый путь]].
-
* Псевдокод алгоритма: [[кратчайший незамкнутый путь]].
+
* Псевдокод алгоритма: [[ФОРЭЛ]].
* Псевдокод алгоритма: [[ФОРЭЛ]].
* Функционалы качества кластеризации.
* Функционалы качества кластеризации.
Строка 259: Строка 261:
* Алгоритм построения [[дендрограмма|дендрограммы]]. Определение числа кластеров.
* Алгоритм построения [[дендрограмма|дендрограммы]]. Определение числа кластеров.
* Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
* Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
-
* Потоковые (субквадратичные) алгоритмы кластеризации.
+
<!---* Потоковые (субквадратичные) алгоритмы кластеризации.--->
 +
<!---
=== Многомерное шкалирование ===
=== Многомерное шкалирование ===
* [[Многомерное шкалирование]], примеры прикладных задач.
* [[Многомерное шкалирование]], примеры прикладных задач.
Строка 266: Строка 269:
* Визуализация: [[карта сходства]], [[диаграмма Шепарда]].
* Визуализация: [[карта сходства]], [[диаграмма Шепарда]].
* Совмещение многомерного шкалирования и иерархической кластеризации.
* Совмещение многомерного шкалирования и иерархической кластеризации.
 +
--->
=== Сети Кохонена ===
=== Сети Кохонена ===
-
* [[Нейронная сеть Кохонена|Сеть Кохонена]]. [[Конкурентное обучение]], стратегии WTA и WTM, обучающееся векторное квантование.
+
* [[Нейронная сеть Кохонена]]. [[Конкурентное обучение]], стратегии WTA и WTM.
-
* [[Нейронная сеть Кохонена|Самоорганизующаяся карта Кохонена]]. Применение для визуального анализа данных.
+
* [[Самоорганизующаяся карта Кохонена]]. Применение для визуального анализа данных. Искусство интерпретации карт Кохонена.
-
* [[Сети встречного распространения]], их применение для кусочно-постоянной и гладкой аппроксимации функций.
+
<!---* [[Сети встречного распространения]], их применение для кусочно-постоянной и гладкой аппроксимации функций.--->
[[Категория:Учебные курсы]]
[[Категория:Учебные курсы]]

Версия 21:24, 30 мая 2009

Содержание

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

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

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

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

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

Курс читается студентам 3 курса кафедры «Интеллектуальные системы / интеллектуальный анализ данных» ФУПМ МФТИ с 2004 года; студентам 3 курса кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года; студентам Школы анализа данных Яндекса с 2009 года.

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

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

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

Скачать:

1.1. Основные понятия и примеры прикладных задач (PDF, 929 КБ).

1.2–1.4. Статистические (байесовские) методы классификации (PDF, 776 КБ).

1.5. Метрические методы классификации (PDF, 382 КБ).

1.6–1.9. Линейные методы классификации (PDF, 1,56 МБ).

1.10–1.12. Регрессия (PDF, 421 КБ).

1.13. Нейронные сети (PDF, 346 КБ).

Замечание 1. В этих лекциях есть материал, который не входит в программу курса. Он включён «для общего развития» и на экзамене спрашиваться не будет.

Замечание 2. О найденных ошибках и опечатках сообщайте мне. — К.В.Воронцов 18:24, 19 января 2009 (MSK)

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


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

Байесовские алгоритмы классификации

Параметрическое оценивание плотности

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

  • Смесь распределений.
  • EM-алгоритм: основная идея, понятие скрытых переменных. «Вывод» алгоритма без обоснования сходимости. Псевдокод EM-алгоритма. Критерий останова. Выбор начального приближения. Выбор числа компонентов смеси.
  • Стохастический EM-алгоритм.
  • Смесь многомерных нормальных распределений. Сеть радиальных базисных функций (RBF) и применение EM-алгоритма для её настройки.

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

Линейные алгоритмы классификации

Логистическая регрессия

  • Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
  • Логистическая регрессия. Принцип максимума правдоподобия и логарифмическая функция потерь. Снова метод стохастического градиента, аналогия с правилом Хэбба.

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

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

Обобщённый линейный классификатор

  • Задача максимизации совместного правдоподобия данных и модели.
  • Возможные типы априорных предположений о вероятностном распределении в пространстве параметров и их связь с регуляризацией.
  • Некоторые разновидности регуляризаторов, применяемые на практике.
  • Настройка порога решающего правила по критерию числа ошибок I и II рода. Кривая ошибок (ROC curve).

Непараметрическая регрессия

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

Нелинейная параметрическая регрессия

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

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

Алгоритмические композиции

Бустинг, бэггинг и аналоги


Нелинейные алгоритмические композиции

Оценивание и выбор моделей

Методы отбора признаков

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

Решающие списки и деревья

Взвешенное голосование закономерностей

  • Принцип голосования. Проблема различности (диверсификации) закономерностей.
  • Методы синтеза конъюнктивных закономерностей. Псевдокод: алгоритм КОРА, алгоритм ТЭМП.
  • Алгоритм бустинга. Теорема сходимости. Критерий информативности в бустинге.
  • Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.

Алгоритмы вычисления оценок

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

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

Таксономия


Сети Кохонена

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