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

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

(Различия между версиями)
Перейти к: навигация, поиск
(дополнение, уточнение)
м (Отбор эталонов и оптимизация метрики: уточнение)
Строка 101: Строка 101:
* Отбор эталонных объектов. Псевдокод: [[алгоритм СТОЛП]].
* Отбор эталонных объектов. Псевдокод: [[алгоритм СТОЛП]].
* [[Функция конкурентного сходства]], [[алгоритм FRiS-СТОЛП]].
* [[Функция конкурентного сходства]], [[алгоритм FRiS-СТОЛП]].
-
* ''[[Функционал полного скользящего контроля]], формула быстрого вычисления для метода 1NN. [[Профиль компактности]]. Функция вклада объекта. Отбор эталонных объектов на основе минимизации функционала полного скользящего контроля. Эффективные структуры данных для быстрого поиска ближайших объектов в прямых и обратных окрестностях — [[метрические деревья]].''
+
* [[Функционал полного скользящего контроля]], формула быстрого вычисления для метода 1NN. [[Профиль компактности]]. ''Функция вклада объекта. Отбор эталонных объектов на основе минимизации функционала полного скользящего контроля. Эффективные структуры данных для быстрого поиска ближайших объектов в прямых и обратных окрестностях — [[метрические деревья]].''
* ''[[Проклятие размерности]]. Задача настройки весов признаков.''
* ''[[Проклятие размерности]]. Задача настройки весов признаков.''
* ''Концепция вывода на основе прецедентов ([[CBR]]).''
* ''Концепция вывода на основе прецедентов ([[CBR]]).''

Версия 23:05, 6 июня 2011

Содержание

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

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

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

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

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

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

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

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

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

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

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

Замечание 2. На подстранице имеется перечень вопросов к устному экзамену. Очень помогает при подготовке к устному экзамену!

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

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

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

Текст лекции: (PDF, 287 КБ).

Статистичесие (байесовские) методы классификации

Текст лекций: (PDF, 610 КБ).
Презентация: (PDF, 1,37 МБ)

Оптимальный байесовский классификатор

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

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

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

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

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

Текст лекций: (PDF, 191 КБ).
Презентация: (PDF, 1.57 МБ).

Метод ближайших соседей и его обобщения

Отбор эталонов и оптимизация метрики

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

Текст лекций: (PDF, 1,56 МБ) (ожидается обновление...).
Презентация: (PDF, 1,04 МБ).

Градиентные методы

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

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

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

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

Методы регрессионного анализа

Текст лекций: (PDF, 421 КБ).
Презентация: (PDF, 781 КБ).

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

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

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

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

Текст лекций: (PDF, 346 КБ).
Презентация: (PDF, 577 КБ).

Многослойные нейронные сети

Методы кластеризации

Текст лекций: (PDF, 252 КБ).
Презентация: (PDF, 1,43 МБ).

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

Таксономия

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

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

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

Текст лекций: (PDF, 330 КБ).
Презентация: (PDF, 750 КБ).

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

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

Композиционные методы классификации и регрессии

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

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

Эвристические и стохастические методы

Бустинг алгоритмов ранжирования

  • Задача ранжирования. Примеры: ранжирование результатов текстового поиска, задача Netflix.
  • Функционал качества — число дефектных пар.
  • Бустинг алгоритмов ранжирования — аналоги AdaBoost и AnyBoost.
  • Двудольная задача. Сведение попарного функционала качества к поточечному.

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

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

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

Текст лекций: (PDF, 625 КБ).
Презентация: (PDF, 875 КБ).

Понятия закономерности и информативности

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

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

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

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

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

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

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


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

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