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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Алгоритмы вычисления оценок: уточнение ссылки)
(два уровня разделов, ссылки на тексты лекций и презентации)
Строка 29: Строка 29:
''Курсивом'' выделен дополнительный материал, который может разбираться на семинарах.
''Курсивом'' выделен дополнительный материал, который может разбираться на семинарах.
-
== Первый семестр ==
+
=== Замечания для студентов ===
-
 
+
-
{{well|'''Скачать:'''
+
-
 
+
-
1.1. Основные понятия и примеры прикладных задач [[Media:Voron-ML-Intro.pdf|(PDF, 929 КБ)]].
+
-
 
+
-
1.2–1.4. Статистические (байесовские) методы классификации [[Media:Voron-ML-Bayes.pdf|(PDF, 776 КБ)]].
+
-
 
+
-
1.5. Метрические методы классификации [[Media:Voron-ML-Metric.pdf|(PDF, 382 КБ)]].
+
-
 
+
-
1.6–1.9. Линейные методы классификации [[Media:Voron-ML-Lin.pdf|(PDF, 1,56 МБ)]].
+
-
 
+
-
1.10–1.12. Регрессия [[Media:Voron-ML-Regression.pdf|(PDF, 421 КБ)]].
+
-
 
+
-
1.13. Нейронные сети [[Media:Voron-ML-NeuralNets.pdf|(PDF, 346 КБ)]].
+
'''Замечание 1.'''
'''Замечание 1.'''
Строка 50: Строка 36:
'''Замечание 2.'''
'''Замечание 2.'''
 +
На подстанице имеется перечень
 +
[[Машинное обучение (курс лекций, К.В.Воронцов)/Вопросы|вопросов к устному экзамену]].
 +
Очень помогает при подготовке к устному экзамену!
 +
 +
'''Замечание 3.'''
О найденных ошибках и опечатках [[Служебная:EmailUser/Vokov|сообщайте мне]]. — ''[[Участник:Vokov|К.В.Воронцов]] 18:24, 19 января 2009 (MSK)''
О найденных ошибках и опечатках [[Служебная:EmailUser/Vokov|сообщайте мне]]. — ''[[Участник:Vokov|К.В.Воронцов]] 18:24, 19 января 2009 (MSK)''
-
'''[[Машинное обучение (курс лекций, К.В.Воронцов)/Вопросы|Вопросы к устному экзамену]]'''
+
= Первый семестр =
-
}}
+
=== Основные понятия и примеры прикладных задач ===
=== Основные понятия и примеры прикладных задач ===
 +
Текст лекций: [[Media:Voron-ML-Intro.pdf|(PDF, 929 КБ)]].
 +
* Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.
* Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.
* Типы задач: [[классификация]], [[регрессия]], [[прогнозирование]], [[кластеризация]]. Примеры прикладных задач.
* Типы задач: [[классификация]], [[регрессия]], [[прогнозирование]], [[кластеризация]]. Примеры прикладных задач.
Строка 62: Строка 54:
* ''Вероятностная постановка задачи обучения по прецедентам, [[принцип максимума правдоподобия]] и его связь с принципом минимизации эмпирического риска. Разновидности функций потерь и их вероятностная интерпретация.''
* ''Вероятностная постановка задачи обучения по прецедентам, [[принцип максимума правдоподобия]] и его связь с принципом минимизации эмпирического риска. Разновидности функций потерь и их вероятностная интерпретация.''
-
=== Байесовские алгоритмы классификации ===
+
== Статистичесие (байесовские) методы классификации ==
 +
Текст лекций: [[Media:Voron-ML-Bayes.pdf|(PDF,&nbsp;776&nbsp;КБ)]].<br/>
 +
Презентация: [[Media:Voron-ML-Bayes-slides.pdf|(PDF,&nbsp;???&nbsp;КБ)]]
 +
 
 +
=== Байесовский классификатор. Непараметрическое оценивание плотности ===
* Оптимальный [[байесовский классификатор]].
* Оптимальный [[байесовский классификатор]].
* Функционал среднего риска. Ошибки I и II рода.
* Функционал среднего риска. Ошибки I и II рода.
Строка 87: Строка 83:
* Смесь многомерных нормальных распределений. [[Сеть радиальных базисных функций]] (RBF) и применение EM-алгоритма для её настройки.
* Смесь многомерных нормальных распределений. [[Сеть радиальных базисных функций]] (RBF) и применение EM-алгоритма для её настройки.
-
=== Метрические алгоритмы классификации ===
+
== Метрические методы классификации ==
 +
Текст лекций: [[Media:Voron-ML-Metric.pdf|(PDF,&nbsp;382&nbsp;КБ)]].<br/>
 +
Презентация: [[Media:Voron-ML-Metric-slides.pdf|(PDF,&nbsp;???&nbsp;КБ)]].
 +
 
 +
=== Метод ближайших соседей и его обобщения ===
* [[Метод ближайших соседей]] (''k''NN) и его обобщения.
* [[Метод ближайших соседей]] (''k''NN) и его обобщения.
* Подбор числа ''k'' по критерию скользящего контроля.
* Подбор числа ''k'' по критерию скользящего контроля.
* Обобщённый [[метрический классификатор]], понятие [[отступ]]а.
* Обобщённый [[метрический классификатор]], понятие [[отступ]]а.
* [[Метод потенциальных функций]], градиентный алгоритм.
* [[Метод потенциальных функций]], градиентный алгоритм.
 +
 +
=== Отбор эталонов и оптимизация метрики ===
* Отбор эталонных объектов. Псевдокод: [[алгоритм СТОЛП]].
* Отбор эталонных объектов. Псевдокод: [[алгоритм СТОЛП]].
* [[Функция конкурентного сходства]], [[алгоритм FRiS-СТОЛП]].
* [[Функция конкурентного сходства]], [[алгоритм FRiS-СТОЛП]].
Строка 98: Строка 100:
* ''Концепция вывода на основе прецедентов ([[CBR]]).''
* ''Концепция вывода на основе прецедентов ([[CBR]]).''
-
=== Линейные алгоритмы классификации ===
+
== Линейные методы классификации ==
 +
Текст лекций: [[Media:Voron-ML-Lin.pdf|(PDF,&nbsp;1,56&nbsp;МБ)]].<br/>
 +
Презентация: [[Media:Voron-ML-Lin-slides.pdf|(PDF,&nbsp;???&nbsp;КБ)]].
 +
 
 +
=== Градиентные методы ===
* [[Линейный классификатор]], непрерывные аппроксимации пороговой функции потерь.
* [[Линейный классификатор]], непрерывные аппроксимации пороговой функции потерь.
* ''Квадратичная функция потерь, [[метод наименьших квадратов]], связь с линейным дискриминантом Фишера.''
* ''Квадратичная функция потерь, [[метод наименьших квадратов]], связь с линейным дискриминантом Фишера.''
Строка 127: Строка 133:
* Настройка порога решающего правила по критерию числа ошибок I и II рода. [[Кривая ошибок]] (ROC curve).
* Настройка порога решающего правила по критерию числа ошибок I и II рода. [[Кривая ошибок]] (ROC curve).
* Пример прикладной задачи: кредитный скоринг. Скоринговые карты и оценивание вероятности дефолта. ''Риск кредитного портфеля банка.''
* Пример прикладной задачи: кредитный скоринг. Скоринговые карты и оценивание вероятности дефолта. ''Риск кредитного портфеля банка.''
 +
 +
== Методы регрессионного анализа ==
 +
Текст лекций: [[Media:Voron-ML-Regression.pdf|(PDF,&nbsp;421&nbsp;КБ)]].<br/>
 +
Презентация: [[Media:Voron-ML-Regression-slides.pdf|(PDF,&nbsp;???&nbsp;КБ)]].
=== Непараметрическая регрессия ===
=== Непараметрическая регрессия ===
Строка 156: Строка 166:
* Неквадратичные функци потерь. Робастная регрессия, функция Мешалкина. Несимметричные функции потерь, пример прикладной задачи: прогнозирование потребительского спроса.
* Неквадратичные функци потерь. Робастная регрессия, функция Мешалкина. Несимметричные функции потерь, пример прикладной задачи: прогнозирование потребительского спроса.
-
== Второй семестр ==
+
= Второй семестр =
 +
 
 +
== Критерии выбора моделей и методы отбора признаков ==
 +
Текст лекций: [[Media:Voron-ML-Modeling.pdf|(PDF,&nbsp;???&nbsp;КБ)]].<br/>
 +
Презентация: [[Media:Voron-ML-Modeling-slides.pdf|(PDF,&nbsp;???&nbsp;КБ)]].
 +
 
 +
=== Оценивание и выбор моделей ===
 +
* Внутренние и [[внешние критерии]].
 +
* [[Скользящий контроль]], разновидности скользящего контроля.
 +
* [[Критерий непротиворечивости]].
 +
* [[Регуляризация]].
 +
* Критерий, основанные на теории Вапника-Червоненкиса.
 +
* [[Критерий Акаике]] (AIC).
 +
* [[Байесовский информационный критерий]] (BIC).
 +
* ''Статистические критерии: [[коэффициент детерминации]], [[критерий Фишера]], [[анализ регрессионных остатков]].''
 +
* Агрегированные и многоступенчатые критерии.
 +
 
 +
=== Методы отбора признаков ===
 +
* Сложность задачи [[отбор признаков|отбора признаков]]. [[Полный перебор]].
 +
* [[Метод добавления и удаления]], шаговая регрессия.
 +
* [[Поиск в глубину]], метод ветвей и границ.
 +
* Усечённый [[поиск в ширину]], [[многорядный итерационный алгоритм МГУА]].
 +
* [[Генетический алгоритм]], его сходство с МГУА.
 +
* [[Случайный поиск]] и [[Случайный поиск с адаптацией]] (СПА).
 +
 
 +
== Нейросетевые методы классификации и регрессии ==
 +
Текст лекций: [[Media:Voron-ML-NeuralNets.pdf|(PDF,&nbsp;346&nbsp;КБ)]].<br/>
 +
Презентация: [[Media:Voron-ML-NeuralNets-slides.pdf|(PDF,&nbsp;???&nbsp;КБ)]].
=== Нейронные сети ===
=== Нейронные сети ===
Строка 165: Строка 202:
* Подбор структуры сети: методы постепенного усложнения сети, [[оптимальное прореживание нейронных сетей]] (optimal brain damage).
* Подбор структуры сети: методы постепенного усложнения сети, [[оптимальное прореживание нейронных сетей]] (optimal brain damage).
-
=== Алгоритмические композиции ===
+
== Композиционные методы классификации и регрессии ==
 +
Текст лекций: [[Media:Voron-ML-Compositions.pdf|(PDF,&nbsp;???&nbsp;КБ)]].<br/>
 +
Презентация: [[Media:Voron-ML-Compositions-slides.pdf|(PDF,&nbsp;???&nbsp;КБ)]].
 +
 
 +
=== Линейные композиции, бустинг ===
* Основные понятия: [[базовый алгоритм]] ([[алгоритмический оператор]]), [[корректирующая операция]].
* Основные понятия: [[базовый алгоритм]] ([[алгоритмический оператор]]), [[корректирующая операция]].
* [[Взвешенное голосование]].
* [[Взвешенное голосование]].
Строка 190: Строка 231:
* ''Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии.''
* ''Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии.''
-
=== Оценивание и выбор моделей ===
+
== Логические методы классификации ==
-
* Внутренние и [[внешние критерии]].
+
Текст лекций: [[Media:Voron-ML-Logic.pdf|(PDF,&nbsp;???&nbsp;КБ)]].<br/>
-
* [[Скользящий контроль]], разновидности скользящего контроля.
+
Презентация: [[Media:Voron-ML-Logic-slides.pdf|(PDF,&nbsp;???&nbsp;КБ)]].
-
* [[Критерий непротиворечивости]].
+
-
* [[Регуляризация]].
+
-
* Критерий, основанные на теории Вапника-Червоненкиса.
+
-
* [[Критерий Акаике]] (AIC).
+
-
* [[Байесовский информационный критерий]] (BIC).
+
-
* ''Статистические критерии: [[коэффициент детерминации]], [[критерий Фишера]], [[анализ регрессионных остатков]].''
+
-
* Агрегированные и многоступенчатые критерии.
+
-
 
+
-
=== Методы отбора признаков ===
+
-
* Сложность задачи [[отбор признаков|отбора признаков]]. [[Полный перебор]].
+
-
* [[Метод добавления и удаления]], шаговая регрессия.
+
-
* [[Поиск в глубину]], метод ветвей и границ.
+
-
* Усечённый [[поиск в ширину]], [[многорядный итерационный алгоритм МГУА]].
+
-
* [[Генетический алгоритм]], его сходство с МГУА.
+
-
* [[Случайный поиск]] и [[Случайный поиск с адаптацией]] (СПА).
+
-
=== Логические алгоритмы классификации ===
+
=== Понятия закономерности и информативности ===
* Понятие [[логическая закономерность|логической закономерности]]. Эвристическое, статистическое, энтропийное определение [[информативность|информативности]]. Асимптотическая эквивалентность статистического и энтропийного определения. Сравнение областей эвристических и статистических закономерностей.
* Понятие [[логическая закономерность|логической закономерности]]. Эвристическое, статистическое, энтропийное определение [[информативность|информативности]]. Асимптотическая эквивалентность статистического и энтропийного определения. Сравнение областей эвристических и статистических закономерностей.
* Разновидности закономерностей: шары, гиперплоскости, гиперпараллелепипеды (конъюнкции).
* Разновидности закономерностей: шары, гиперплоскости, гиперпараллелепипеды (конъюнкции).
Строка 236: Строка 262:
* Проблема оптимизации АВО. АВО как композиция метрических закономерностей.
* Проблема оптимизации АВО. АВО как композиция метрических закономерностей.
* Применение бустинга, ТЭМП и СПА для оптимизации АВО.
* Применение бустинга, ТЭМП и СПА для оптимизации АВО.
 +
 +
== Методы обучения без учителя ==
 +
Текст лекций: [[Media:Voron-ML-Unsupervised.pdf|(PDF,&nbsp;???&nbsp;КБ)]].<br/>
 +
Презентация: [[Media:Voron-ML-Unsupervised-slides.pdf|(PDF,&nbsp;???&nbsp;КБ)]].
=== Поиск ассоциативных правил ===
=== Поиск ассоциативных правил ===

Версия 16:25, 23 февраля 2010

Содержание

Машинное обучение возникло на стыке прикладной статистики, оптимизации, дискретного анализа, и за последние 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, 929 КБ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Методы обучения без учителя

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

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

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

Таксономия

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

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

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

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