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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (орфография)
(уточнение: 1й семестр)
Строка 42: Строка 42:
* [[Линейный дискриминант Фишера]].
* [[Линейный дискриминант Фишера]].
* Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]]. [[Регуляризация]] ковариационной матрицы. [[Метод редукции размерности]] Шурыгина. Робастное оценивание.
* Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]]. [[Регуляризация]] ковариационной матрицы. [[Метод редукции размерности]] Шурыгина. Робастное оценивание.
-
* Факультатив или семинар: матричное дифференцирование.
+
* '''Факультатив или семинар''': матричное дифференцирование.
=== Разделение смеси распределений ===
=== Разделение смеси распределений ===
Строка 49: Строка 49:
* Стохастический EM-алгоритм.
* Стохастический EM-алгоритм.
* Смесь многомерных нормальных распределений. [[Сеть радиальных базисных функций]] (RBF) и применение EM-алгоритма для её настройки.
* Смесь многомерных нормальных распределений. [[Сеть радиальных базисных функций]] (RBF) и применение EM-алгоритма для её настройки.
 +
 +
=== Метрические алгоритмы классификации ===
 +
* [[Метод ближайших соседей]] (''k''NN) и его обобщения.
 +
* Подбор числа ''k'' по критерию скользящего контроля.
 +
* Обобщённый [[метрический классификатор]], понятие [[отступ]]а.
 +
* [[Метод потенциальных функций]], градиентный алгоритм.
 +
* Отбор эталонных объектов. Псевдокод: [[алгоритм СТОЛП]].
 +
* Настройка весов объектов.
 +
* [[Проклятие размерности]]. Настройка весов признаков.
 +
* Вывод на основе прецедентов ([[CBR]]).
=== Линейные алгоритмы классификации ===
=== Линейные алгоритмы классификации ===
Строка 56: Строка 66:
* [[Метод стохастического градиента]] и частные случаи: [[адаптивный линейный элемент]] ADALINE, [[перцептрон Розенблатта]], [[правило Хэбба]].
* [[Метод стохастического градиента]] и частные случаи: [[адаптивный линейный элемент]] ADALINE, [[перцептрон Розенблатта]], [[правило Хэбба]].
* [[Теорема Новикова]] о сходимости.
* [[Теорема Новикова]] о сходимости.
 +
* Недостатки метода стохастического градиента и способы их устранения. Проблема [[паралич сети|«паралича» сети]]. Ускорение сходимости, «выбивание» из локальных минимумов. Проблема переобучения, [[редукция весов]] (weight decay).
=== Логистическая регрессия ===
=== Логистическая регрессия ===
* Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
* Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
-
* [[Логистическая регрессия]]. Принцип максимума правдоподобия и логарифмическая функция потерь.
+
* [[Логистическая регрессия]]. Принцип максимума правдоподобия и логарифмическая функция потерь. Снова метод стохастического градиента, аналогия с правилом Хэбба.
* Настройка порога решающего правила по критерию числа ошибок I и II рода, [[кривая ошибок]] (lift curve), отказы от классификации.
* Настройка порога решающего правила по критерию числа ошибок I и II рода, [[кривая ошибок]] (lift curve), отказы от классификации.
* Пример прикладной задачи: кредитный скоринг и скоринговые карты.
* Пример прикладной задачи: кредитный скоринг и скоринговые карты.
 +
 +
=== Нейронные сети ===
 +
* Проблема полноты. [[Задача исключающего или]]. Полнота двухслойных сетей в пространстве булевских функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства).
 +
* [[Алгоритм обратного распространения ошибок]]. Недостатки алгоритма, способы их устранения.
 +
* Подбор структуры сети: методы постепенного усложнения сети, [[оптимальное прореживание сети]] (optimal brain damage).
=== Метод опорных векторов ===
=== Метод опорных векторов ===
* Оптимальная разделяющая гиперплоскость. Понятие [[зазор]]а между классами (margin).
* Оптимальная разделяющая гиперплоскость. Понятие [[зазор]]а между классами (margin).
-
* Случай линейной разделимости. Задача квадратичного программирования и двойственная задача. Понятие [[Опорный вектор|опорных векторов]].
+
* Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией эмпирического риска, кусочно-линейная функция потерь.
-
* Случай отсутствия линейной разделимости. Связь с минимизацией эмпирического риска, кусочно-линейная функция потерь. Двойственная задача. Отличие от предыдущего случая. Выбор константы ''C''.
+
* Задача квадратичного программирования и двойственная задача. Понятие [[Опорный вектор|опорных векторов]].
 +
* Рекомендации по выбору константы ''C''.
* [[Функция ядра]] (kernel functions), [[спрямляющее пространство]], [[теорема Мерсера]].
* [[Функция ядра]] (kernel functions), [[спрямляющее пространство]], [[теорема Мерсера]].
* Способы построения ядер. Примеры ядер.
* Способы построения ядер. Примеры ядер.
Строка 75: Строка 92:
* Обучение SVM методом активных ограничений. Псевдокод: [[алгоритм INCAS]].
* Обучение SVM методом активных ограничений. Псевдокод: [[алгоритм INCAS]].
* SVM-регрессия.
* SVM-регрессия.
-
 
-
=== Нейронные сети ===
 
-
* [[Проблема исключающего или]]. Проблема полноты. Полнота двухслойных сетей в пространстве булевских функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства).
 
-
* [[Алгоритм обратного распространения ошибок]]. Недостатки алгоритма, способы их устранения.
 
-
* Проблема переобучения.
 
-
* Проблема [[паралич сети|«паралича» сети]].
 
-
* [[Редукция весов]] (weight decay).
 
-
* Подбор структуры сети: методы постепенного усложнения сети, [[метод оптимального прореживания сети]] (optimal brain damage).
 
-
 
-
=== Метрические алгоритмы классификации ===
 
-
* [[Метод ближайших соседей]] (''k''NN) и его обобщения.
 
-
* Подбор числа ''k'' по критерию скользящего контроля.
 
-
* Обобщённый [[метрический классификатор]].
 
-
* [[Метод потенциальных функций]], градиентный алгоритм.
 
-
* Настройка весов объектов. Отбор эталонных объектов. Псевдокод: [[алгоритм СТОЛП]].
 
-
* [[Проклятие размерности]]. Настройка весов признаков.
 
-
* Вывод на основе прецедентов ([[CBR]]).
 
=== Непараметрическая регрессия ===
=== Непараметрическая регрессия ===
* [[Сглаживание]]. Локально взвешенный [[метод наименьших квадратов]] и [[оценка Надарая-Ватсона]].
* [[Сглаживание]]. Локально взвешенный [[метод наименьших квадратов]] и [[оценка Надарая-Ватсона]].
* Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна.
* Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна.
 +
* Доверительный интервал значения регрессии в точке.
* Проблема выбросов и робастная непараметрическая регрессия. Псевдокод: [[алгоритм LOWESS]].
* Проблема выбросов и робастная непараметрическая регрессия. Псевдокод: [[алгоритм LOWESS]].
-
* Проблема «проклятия размерности» и проблема выбора метрики.
+
* Проблема «проклятия размерности» и выбор метрики.
=== Многомерная линейная регрессия ===
=== Многомерная линейная регрессия ===
Строка 104: Строка 105:
* Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]].
* Проблемы [[мультиколлинеарность|мультиколлинеарности]] и [[переобучение|переобучения]].
* [[Регуляризация]]. [[Гребневая регрессия]]. [[Лассо Тибширани]]. Линейная монотонная регрессия (симплекс-метод).
* [[Регуляризация]]. [[Гребневая регрессия]]. [[Лассо Тибширани]]. Линейная монотонная регрессия (симплекс-метод).
-
* Линейные преобразования признакового пространства. [[Метод главных компонент]] и [[декоррелирующее преобразование]] Карунена-Лоэва.
+
* Линейные преобразования признакового пространства, задача сокращения размерности. [[Метод главных компонент]] и [[декоррелирующее преобразование]] Карунена-Лоэва.
* [[Робастная регрессия]].
* [[Робастная регрессия]].

Версия 18:01, 13 ноября 2008

Содержание

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

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

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

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

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

Курс читается студентам 3 курса кафедры «Интеллектуальные системы / интеллектуальный анализ данных» ФУПМ МФТИ с 2004 года и студентам 3 курса кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года. На материал данного курса существенно опираются последующие кафедральные курсы. На кафедре ММП ВМиК МГУ параллельно с данным курсом и в дополнение к нему читается спецкурс Теория надёжности обучения по прецедентам, посвящённый проблемам переобучения и оценивания обобщающей способности.

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

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

Вводная лекция

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

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

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

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

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

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

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

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

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

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

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

Методы оптимизации SVM

  • Обучение SVM методом последовательной минимизации. Псевдокод: алгоритм SMO.
  • Обучение SVM методом активных ограничений. Псевдокод: алгоритм INCAS.
  • SVM-регрессия.

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

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

Шаговая регрессия

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

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

  • Аддитивная модель временного ряда: тренд, сезонность, цикличность. Модель Бокса-Дженкинса. Модель ARIMA — авторегрессии и интегрированного скользящего среднего.
  • Адаптивные модели. Примеры экономических приложений.
  • Неквадратичные функции потерь, примеры прикладных задач.

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

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

Таксономия и многомерное шкалирование

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

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

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

Метод комитетов

  • Общее понятие: комитет системы ограничений. Комитеты большинства, простое и взвешенное голосование (z,p-комитеты).
  • Теоремы о существовании комитетного решения.
  • Сопоставление комитета линейных неравенств с нейронной сетью.
  • Максимальная совместная подсистема, минимальный комитет. Теоремы об NP-полноте задачи поиска минимального комитета.
  • Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.

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

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

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

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

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

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

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

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

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

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

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