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

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

(Различия между версиями)
Перейти к: навигация, поиск
м (дополнение, уточнение)
(Таксономия и многомерное шкалирование)
Строка 155: Строка 155:
* Статистические алгоритмы: [[EM-алгоритм]] и [[k-means]], псевдокод.
* Статистические алгоритмы: [[EM-алгоритм]] и [[k-means]], псевдокод.
-
=== Таксономия и многомерное шкалирование ===
+
=== Таксономия ===
* [[Агломеративная кластеризация]]: псевдокод алгоритма, [[формула Ланса-Вильямса]] и её частные случаи.
* [[Агломеративная кластеризация]]: псевдокод алгоритма, [[формула Ланса-Вильямса]] и её частные случаи.
* Алгоритм построения [[дендрограмма|дендрограммы]]. Определение числа кластеров.
* Алгоритм построения [[дендрограмма|дендрограммы]]. Определение числа кластеров.
* Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
* Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
-
* Потоковые (субквадратичные) алгоритмы кластеризации.
+
* Потоковые (субквадратичные) алгоритмы кластеризации.
 +
 
 +
=== Многомерное шкалирование ===
* [[Многомерное шкалирование]], примеры прикладных задач.
* [[Многомерное шкалирование]], примеры прикладных задач.
* Субквадратичный алгоритм, псевдокод. Размещение одной точки методом Ньютона-Рафсона.
* Субквадратичный алгоритм, псевдокод. Размещение одной точки методом Ньютона-Рафсона.
* Визуализация: [[карта сходства]], [[диаграмма Шепарда]].
* Визуализация: [[карта сходства]], [[диаграмма Шепарда]].
-
* Совмещение многомерного шкалирования и иерархической кластеризации.
+
* Совмещение многомерного шкалирования и иерархической кластеризации.
=== Сети Кохонена ===
=== Сети Кохонена ===

Версия 01:18, 14 января 2009

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таксономия

Многомерное шкалирование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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