Машинное обучение (курс лекций, К.В.Воронцов)
Материал из 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''. | ||
* [[Функция ядра]] (kernel functions), [[спрямляющее пространство]], [[теорема Мерсера]]. | * [[Функция ядра]] (kernel functions), [[спрямляющее пространство]], [[теорема Мерсера]]. | ||
* Способы построения ядер. Примеры ядер. | * Способы построения ядер. Примеры ядер. | ||
Строка 75: | Строка 92: | ||
* Обучение SVM методом активных ограничений. Псевдокод: [[алгоритм INCAS]]. | * Обучение SVM методом активных ограничений. Псевдокод: [[алгоритм INCAS]]. | ||
* SVM-регрессия. | * SVM-регрессия. | ||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
=== Непараметрическая регрессия === | === Непараметрическая регрессия === | ||
* [[Сглаживание]]. Локально взвешенный [[метод наименьших квадратов]] и [[оценка Надарая-Ватсона]]. | * [[Сглаживание]]. Локально взвешенный [[метод наименьших квадратов]] и [[оценка Надарая-Ватсона]]. | ||
* Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна. | * Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна. | ||
+ | * Доверительный интервал значения регрессии в точке. | ||
* Проблема выбросов и робастная непараметрическая регрессия. Псевдокод: [[алгоритм 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 года. На материал данного курса существенно опираются последующие кафедральные курсы. На кафедре ММП ВМиК МГУ параллельно с данным курсом и в дополнение к нему читается спецкурс Теория надёжности обучения по прецедентам, посвящённый проблемам переобучения и оценивания обобщающей способности.
От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание математической статистики, методов оптимизации и какого-либо языка программирования желательно, но не обязательно.
Первый семестр
Вводная лекция
- Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.
- Типы задач: классификация, регрессия, прогнозирование, кластеризация. Примеры прикладных задач.
- Основные понятия: модель алгоритмов, метод обучения, функция потерь и функционал качества, принцип минимизации эмпирического риска, обобщающая способность, скользящий контроль.
- Вероятностная постановка задачи, принцип максимума правдоподобия и его связь с принципом минимизации эмпирического риска.
Байесовские алгоритмы классификации
- Оптимальный байесовский классификатор.
- Функционал среднего риска. Ошибки I и II рода.
- Теорема об оптимальности байесовского решающего правила.
- Оценивание плотности распределения: три основных подхода.
- Наивный байесовский классификатор.
- Непараметрическое оценивание плотности распределения по Парзену-Розенблатту. Выбор функции ядра. Выбор ширины окна, переменная ширина окна. Робастное оценивание плотности. Метод парзеновского окна.
Параметрическое оценивание плотности
- Нормальный дискриминантный анализ. Многомерное нормальное распределение, геометрическая интерпретация. Выборочные оценки параметров многомерного нормального распределения.
- Квадратичный дискриминант. Вид разделяющей поверхности. Подстановочный алгоритм, его недостатки и способы их устранения.
- Линейный дискриминант Фишера.
- Проблемы мультиколлинеарности и переобучения. Регуляризация ковариационной матрицы. Метод редукции размерности Шурыгина. Робастное оценивание.
- Факультатив или семинар: матричное дифференцирование.
Разделение смеси распределений
- Смесь распределений.
- EM-алгоритм: основная идея, понятие скрытых переменных. «Вывод» алгоритма без обоснования сходимости. Псевдокод EM-алгоритма. Критерий останова. Выбор начального приближения. Выбор числа компонентов смеси.
- Стохастический EM-алгоритм.
- Смесь многомерных нормальных распределений. Сеть радиальных базисных функций (RBF) и применение EM-алгоритма для её настройки.
Метрические алгоритмы классификации
- Метод ближайших соседей (kNN) и его обобщения.
- Подбор числа k по критерию скользящего контроля.
- Обобщённый метрический классификатор, понятие отступа.
- Метод потенциальных функций, градиентный алгоритм.
- Отбор эталонных объектов. Псевдокод: алгоритм СТОЛП.
- Настройка весов объектов.
- Проклятие размерности. Настройка весов признаков.
- Вывод на основе прецедентов (CBR).
Линейные алгоритмы классификации
- Естественный нейрон, модель МакКаллока-Питтса, функции активации.
- Линейный классификатор, непрерывные аппроксимации пороговых функций потерь.
- Квадратичная функция потерь, метод наименьших квадратов, связь с линейным дискриминантом Фишера.
- Метод стохастического градиента и частные случаи: адаптивный линейный элемент ADALINE, перцептрон Розенблатта, правило Хэбба.
- Теорема Новикова о сходимости.
- Недостатки метода стохастического градиента и способы их устранения. Проблема «паралича» сети. Ускорение сходимости, «выбивание» из локальных минимумов. Проблема переобучения, редукция весов (weight decay).
Логистическая регрессия
- Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
- Логистическая регрессия. Принцип максимума правдоподобия и логарифмическая функция потерь. Снова метод стохастического градиента, аналогия с правилом Хэбба.
- Настройка порога решающего правила по критерию числа ошибок I и II рода, кривая ошибок (lift curve), отказы от классификации.
- Пример прикладной задачи: кредитный скоринг и скоринговые карты.
Нейронные сети
- Проблема полноты. Задача исключающего или. Полнота двухслойных сетей в пространстве булевских функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства).
- Алгоритм обратного распространения ошибок. Недостатки алгоритма, способы их устранения.
- Подбор структуры сети: методы постепенного усложнения сети, оптимальное прореживание сети (optimal brain damage).
Метод опорных векторов
- Оптимальная разделяющая гиперплоскость. Понятие зазора между классами (margin).
- Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией эмпирического риска, кусочно-линейная функция потерь.
- Задача квадратичного программирования и двойственная задача. Понятие опорных векторов.
- Рекомендации по выбору константы C.
- Функция ядра (kernel functions), спрямляющее пространство, теорема Мерсера.
- Способы построения ядер. Примеры ядер.
- Сопоставление SVM и RBF-сети.
Методы оптимизации SVM
- Обучение SVM методом последовательной минимизации. Псевдокод: алгоритм SMO.
- Обучение SVM методом активных ограничений. Псевдокод: алгоритм INCAS.
- SVM-регрессия.
Непараметрическая регрессия
- Сглаживание. Локально взвешенный метод наименьших квадратов и оценка Надарая-Ватсона.
- Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна.
- Доверительный интервал значения регрессии в точке.
- Проблема выбросов и робастная непараметрическая регрессия. Псевдокод: алгоритм LOWESS.
- Проблема «проклятия размерности» и выбор метрики.
Многомерная линейная регрессия
- Задача регрессии, многомерная линейная регрессия.
- Метод наименьших квадратов. Сингулярное разложение.
- Проблемы мультиколлинеарности и переобучения.
- Регуляризация. Гребневая регрессия. Лассо Тибширани. Линейная монотонная регрессия (симплекс-метод).
- Линейные преобразования признакового пространства, задача сокращения размерности. Метод главных компонент и декоррелирующее преобразование Карунена-Лоэва.
- Робастная регрессия.
Шаговая регрессия
- Модифицированная ортогонализация Грама-Шмидта, достоинства и недостатки.
- Отбор признаков в процессе ортогонализации, критерии выбора и останова.
- Метод наименьших углов (LARS), его связь с лассо и шаговой регрессией.
Нелинейная параметрическая регрессия
- Метод Ньютона-Рафсона, метод Ньютона-Гаусса.
- Одномерные нелинейные преобразования признаков: метод обратной настройки (backfitting) Хасти-Тибширани.
- Обобщённая линейная модель (GLM).
- Логистическая регрессия как частный случай GLM, метод наименьших квадратов с итеративным пересчётом весов (IRLS).
Прогнозирование временных рядов
- Аддитивная модель временного ряда: тренд, сезонность, цикличность. Модель Бокса-Дженкинса. Модель ARIMA — авторегрессии и интегрированного скользящего среднего.
- Адаптивные модели. Примеры экономических приложений.
- Неквадратичные функции потерь, примеры прикладных задач.
Второй семестр
Кластеризация
- Постановка задачи кластеризации. Примеры прикладных задач.
- Графовые алгоритмы кластеризации. Алгоритм связных компонент.
- Псевдокод алгоритма: кратчайший незамкнутый путь.
- Псевдокод алгоритма: ФОРЭЛ.
- Функционалы качества кластеризации.
- Статистические алгоритмы: EM-алгоритм и k-means, псевдокод.
Таксономия и многомерное шкалирование
- Агломеративная кластеризация: псевдокод алгоритма, формула Ланса-Вильямса и её частные случаи.
- Алгоритм построения дендрограммы. Определение числа кластеров.
- Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
- Потоковые (субквадратичные) алгоритмы кластеризации.
- Многомерное шкалирование, примеры прикладных задач.
- Субквадратичный алгоритм, псевдокод. Размещение одной точки методом Ньютона-Рафсона.
- Визуализация: карта сходства, диаграмма Шепарда.
- Совмещение многомерного шкалирования и иерархической кластеризации.
Сети Кохонена
- Сеть Кохонена. Конкурентное обучение, стратегии WTA и WTM, обучающееся векторное квантование.
- Самоорганизующаяся карта Кохонена. Применение для визуального анализа данных.
- Сети встречного распространения, их применение для кусочно-постоянной и гладкой аппроксимации функций.
Алгоритмические композиции
- Основные понятия: базовый алгоритм (алгоритмический оператор), корректирующая операция.
- Линейные (выпуклые) алгоритмические композиции.
- Процесс последовательного обучения базовых алгоритмов.
- Простое голосование (комитет большинства). Эвристический алгоритм.
- Решающий список (комитет старшинства). Эвристический алгоритм.
Бустинг, бэггинг и аналоги
- Взвешенное голосование.
- Экспоненциальная аппроксимация пороговой функции потерь. Теорема о сходимости бустинга.
- Псевдокод: алгоритм AdaBoost.
- Варианты бустинга: GentleBoost, LogitBoost, BrownBoost, и другие.
- Стохастические методы: бэггинг и метод случайных подпространств.
Метод комитетов
- Общее понятие: комитет системы ограничений. Комитеты большинства, простое и взвешенное голосование (z,p-комитеты).
- Теоремы о существовании комитетного решения.
- Сопоставление комитета линейных неравенств с нейронной сетью.
- Максимальная совместная подсистема, минимальный комитет. Теоремы об NP-полноте задачи поиска минимального комитета.
- Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.
Нелинейные алгоритмические композиции
- Смесь экспертов, область компетентности алгоритма.
- Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
- Построение смесей экспертов с помощью EM-алгоритма.
- Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии.
Оценивание и выбор моделей
- Внутренние и внешние критерии.
- Скользящий контроль.
- Критерий непротиворечивости.
- Регуляризация.
- Критерии, основанные на оценках обобщающей способности: Вапника-Червоненкиса, критерий Акаике (AIC), байесовский информационный критерий (BIC).
- Статистические критерии: коэффициент детерминации, критерий Фишера, анализ остатков.
Методы отбора признаков
- Сложность задачи отбора признаков. Полный перебор.
- Метод добавления и удаления (шаговая регрессия).
- Поиск в глубину (метод ветвей и границ).
- Усечённый поиск в ширину (многорядный итерационный алгоритм МГУА).
- Генетический алгоритм, его сходство с МГУА.
- Случайный поиск с адаптацией (СПА).
Логические алгоритмы классификации
- Понятие логической закономерности. Эвристическое, статистическое, энтропийное определение информативности. Асимптотическая эквивалентность статистического и энтропийного определения. Принципиальные отличия эвристического и статистического определения.
- Разновидности закономерностей: шары, гиперплоскости, гиперпараллелепипеды (конъюнкции).
- Бинаризация признаков, алгоритм выделения информативных зон.
- «Градиентный» алгоритм синтеза конъюнкций, частные случаи: жадный алгоритм, стохастический локальный поиск, стабилизация, редукция.
Решающие списки и деревья
- Решающий список. Жадный алгоритм синтеза списка.
- Решающее дерево. Псевдокод: жадный алгоритм ID3. Недостатки алгоритма и способы их устранения. Проблема переобучения.
- Редукция решающих деревьев: предредукция и постредукция.
- Преобразование решающего дерева в решающий список.
- Решающий лес и бустинг над решающими деревьями.
- Переключающиеся решающие деревья (alternating decision tree).
Взвешенное голосование закономерностей
- Принцип голосования. Проблема различности (диверсификации) закономерностей.
- Методы синтеза конъюнктивных закономерностей. Псевдокод: алгоритм КОРА, алгоритм ТЭМП.
- Алгоритм бустинга. Теорема сходимости.
- Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.
Алгоритмы вычисления оценок
- Принцип частичной прецедентности. Структура АВО.
- Тупиковые тесты.
- Тупиковые представительные наборы.
- Проблема оптимизации АВО. АВО как композиция метрических закономерностей.
- Применение бустинга, ТЭМП и СПА для оптимизации АВО.
Поиск ассоциативных правил
- Пример прикладной задачи: анализ рыночных корзин.
- Понятие ассоциативного правила и его связь с понятием логической закономерности.
- Псевдокод: алгоритм APriori, его недостатки и пути усовершенствования.