Машинное обучение (курс лекций, К.В.Воронцов)
Материал из MachineLearning.
Машинное обучение возникло на стыке прикладной статистики, оптимизации, дискретного анализа, и за последние 30 лет оформилось в самостоятельную математическую дисциплину. Методы машинного обучения составляют основу ещё более молодой дисциплины — интеллектуального анализа данных (data mining).
В курсе рассматриваются основные задачи обучения по прецедентам: классификация, кластеризация, регрессия, понижение размерности. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами.
Все методы излагаются по единой схеме:
- исходные идеи и эвристики;
- их формализация и математическая теория;
- описание алгоритма в виде слабо формализованного псевдокода;
- анализ достоинств, недостатков и границ применимости;
- пути устранения недостатков;
- сравнение с другими методами;
- примеры прикладных задач.
Данный курс существенно расширяет и углубляет набор тем, рекомендованный международным стандартом ACM/IEEE Computing Curricula 2001 по дисциплине «Машинное обучение и нейронные сети» (machine learning and neural networks) в разделе «Интеллектуальные системы» (intelligent systems).
Курс читается студентам 3 курса кафедры «Интеллектуальные системы / интеллектуальный анализ данных» ФУПМ МФТИ с 2004 года; студентам 3 курса кафедры «Математические методы прогнозирования» ВМиК МГУ с 2007 года; студентам Школы анализа данных Яндекс с 2009 года.
На материал данного курса существенно опираются последующие кафедральные курсы. На кафедре ММП ВМиК МГУ параллельно с данным курсом и в дополнение к нему читается спецкурс Теория надёжности обучения по прецедентам, посвящённый проблемам переобучения и оценивания обобщающей способности.
От студентов требуются знания курсов линейной алгебры, математического анализа, теории вероятностей. Знание математической статистики, методов оптимизации и какого-либо языка программирования желательно, но не обязательно.
Первый семестр
Вводная лекция
- Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.
- Типы задач: классификация, регрессия, прогнозирование, кластеризация. Примеры прикладных задач.
- Основные понятия: модель алгоритмов, метод обучения, функция потерь и функционал качества, принцип минимизации эмпирического риска, обобщающая способность, скользящий контроль.
- Вероятностная постановка задачи, принцип максимума правдоподобия и его связь с принципом минимизации эмпирического риска.
Байесовские алгоритмы классификации
- Оптимальный байесовский классификатор.
- Функционал среднего риска. Ошибки I и II рода.
- Теорема об оптимальности байесовского решающего правила.
- Оценивание плотности распределения: три основных подхода.
- Наивный байесовский классификатор.
- Непараметрическое оценивание плотности распределения по Парзену-Розенблатту. Выбор функции ядра. Выбор ширины окна, переменная ширина окна. Робастное оценивание плотности. Метод парзеновского окна.
Параметрическое оценивание плотности
- Нормальный дискриминантный анализ. Многомерное нормальное распределение, геометрическая интерпретация. Выборочные оценки параметров многомерного нормального распределения.
- Квадратичный дискриминант. Вид разделяющей поверхности. Подстановочный алгоритм, его недостатки и способы их устранения.
- Линейный дискриминант Фишера.
- Проблемы мультиколлинеарности и переобучения. Регуляризация ковариационной матрицы.
- Робастное оценивание. Цензурирование выборки (отсев объектов-выбросов).
Разделение смеси распределений
- Смесь распределений.
- EM-алгоритм: основная идея, понятие скрытых переменных. «Вывод» алгоритма без обоснования сходимости. Псевдокод EM-алгоритма. Критерий останова. Выбор начального приближения. Выбор числа компонентов смеси.
- Стохастический EM-алгоритм.
- Смесь многомерных нормальных распределений. Сеть радиальных базисных функций (RBF) и применение EM-алгоритма для её настройки.
Метрические алгоритмы классификации
- Метод ближайших соседей (kNN) и его обобщения.
- Подбор числа k по критерию скользящего контроля.
- Обобщённый метрический классификатор, понятие отступа.
- Метод потенциальных функций, градиентный алгоритм.
- Отбор эталонных объектов. Псевдокод: алгоритм СТОЛП.
Линейные алгоритмы классификации
- Биологический нейрон, модель МакКаллока-Питтса.
- Линейный классификатор, функции активации, непрерывные аппроксимации пороговой функции потерь.
- Квадратичная функция потерь, метод наименьших квадратов, связь с линейным дискриминантом Фишера.
- Метод стохастического градиента и частные случаи: адаптивный линейный элемент ADALINE, перцептрон Розенблатта, правило Хэбба.
- Теорема Новикова о сходимости.
- Недостатки метода стохастического градиента и способы их устранения. Проблема «паралича» сети. Ускорение сходимости, «выбивание» из локальных минимумов. Проблема переобучения, редукция весов (weight decay).
Логистическая регрессия
- Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
- Логистическая регрессия. Принцип максимума правдоподобия и логарифмическая функция потерь. Снова метод стохастического градиента, аналогия с правилом Хэбба.
Нейронные сети
- Проблема полноты. Задача исключающего или. Полнота двухслойных сетей в пространстве булевских функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства).
- Алгоритм обратного распространения ошибок. Способы формирования начального приближения. Недостатки алгоритма, способы их устранения.
- Подбор структуры сети: методы постепенного усложнения сети, оптимальное прореживание нейронных сетей (optimal brain damage).
Метод опорных векторов
- Оптимальная разделяющая гиперплоскость. Понятие зазора между классами (margin).
- Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией регуляризованного эмпирического риска. Кусочно-линейная функция потерь.
- Задача квадратичного программирования и двойственная задача. Понятие опорных векторов.
- Рекомендации по выбору константы C.
- Функция ядра (kernel functions), спрямляющее пространство, теорема Мерсера.
- Способы конструктивного построения ядер. Примеры ядер.
- Сопоставление SVM с гауссовским ядром и RBF-сети.
- Обучение SVM методом активных ограничений. Псевдокод: алгоритм INCAS.
Обобщённый линейный классификатор
- Задача максимизации совместного правдоподобия данных и модели.
- Возможные типы априорных предположений о вероятностном распределении в пространстве параметров и их связь с регуляризацией.
- Некоторые разновидности регуляризаторов, применяемые на практике.
- Настройка порога решающего правила по критерию числа ошибок I и II рода. Кривая ошибок (ROC curve).
Непараметрическая регрессия
- Сглаживание. Локально взвешенный метод наименьших квадратов и оценка Надарая-Ватсона.
- Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна.
- Проблема выбросов и робастная непараметрическая регрессия. Псевдокод: алгоритм LOWESS.
Многомерная линейная регрессия
- Задача регрессии, многомерная линейная регрессия.
- Метод наименьших квадратов. Сингулярное разложение.
- Проблемы мультиколлинеарности и переобучения.
- Регуляризация. Гребневая регрессия. Лассо Тибширани.
- Линейные преобразования признакового пространства, задача сокращения размерности. Метод главных компонент и декоррелирующее преобразование Карунена-Лоэва.
Нелинейная параметрическая регрессия
- Метод Ньютона-Рафсона, метод Ньютона-Гаусса.
- Одномерные нелинейные преобразования признаков: метод обратной настройки (backfitting) Хасти-Тибширани.
- Обобщённая линейная модель (GLM).
- Логистическая регрессия как частный случай GLM, метод наименьших квадратов с итеративным пересчётом весов (IRLS).
Второй семестр
Кластеризация
- Постановка задачи кластеризации. Примеры прикладных задач.
- Графовые алгоритмы кластеризации. Алгоритм связных компонент.
- Псевдокод алгоритма: кратчайший незамкнутый путь.
- Псевдокод алгоритма: ФОРЭЛ.
- Функционалы качества кластеризации.
- Статистические алгоритмы: EM-алгоритм и k-means, псевдокод.
Таксономия и многомерное шкалирование
- Агломеративная кластеризация: псевдокод алгоритма, формула Ланса-Вильямса и её частные случаи.
- Алгоритм построения дендрограммы. Определение числа кластеров.
- Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.
- Потоковые (субквадратичные) алгоритмы кластеризации.
- Многомерное шкалирование, примеры прикладных задач.
- Субквадратичный алгоритм, псевдокод. Размещение одной точки методом Ньютона-Рафсона.
- Визуализация: карта сходства, диаграмма Шепарда.
- Совмещение многомерного шкалирования и иерархической кластеризации.
Сети Кохонена
- Сеть Кохонена. Конкурентное обучение, стратегии WTA и WTM, обучающееся векторное квантование.
- Самоорганизующаяся карта Кохонена. Применение для визуального анализа данных.
- Сети встречного распространения, их применение для кусочно-постоянной и гладкой аппроксимации функций.
Алгоритмические композиции
- Основные понятия: базовый алгоритм (алгоритмический оператор), корректирующая операция.
- Линейные (выпуклые) алгоритмические композиции.
- Процесс последовательного обучения базовых алгоритмов.
- Простое голосование (комитет большинства). Эвристический алгоритм.
- Решающий список (комитет старшинства). Эвристический алгоритм.
Бустинг, бэггинг и аналоги
- Взвешенное голосование.
- Экспоненциальная аппроксимация пороговой функции потерь. Теорема о сходимости бустинга.
- Псевдокод: алгоритм AdaBoost.
- Варианты бустинга: GentleBoost, LogitBoost, BrownBoost, и другие.
- Стохастические методы: бэггинг и метод случайных подпространств.
Метод комитетов
- Общее понятие: комитет системы ограничений. Комитеты большинства, простое и взвешенное голосование (z,p-комитеты).
- Теоремы о существовании комитетного решения.
- Сопоставление комитета линейных неравенств с нейронной сетью.
- Максимальная совместная подсистема, минимальный комитет. Теоремы об NP-полноте задачи поиска минимального комитета.
- Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.
Нелинейные алгоритмические композиции
- Смесь экспертов, область компетентности алгоритма.
- Выпуклые функции потерь. Методы построения смесей: последовательный и иерархический.
- Построение смесей экспертов с помощью EM-алгоритма.
- Нелинейная монотонная корректирующая операция. Случай классификации. Случай регрессии.
Оценивание и выбор моделей
- Внутренние и внешние критерии.
- Скользящий контроль.
- Критерий непротиворечивости.
- Регуляризация.
- Критерии, основанные на оценках обобщающей способности: Вапника-Червоненкиса, критерий Акаике (AIC), байесовский информационный критерий (BIC).
- Статистические критерии: коэффициент детерминации, критерий Фишера, анализ остатков.
Методы отбора признаков
- Сложность задачи отбора признаков. Полный перебор.
- Метод добавления и удаления (шаговая регрессия).
- Поиск в глубину (метод ветвей и границ).
- Усечённый поиск в ширину (многорядный итерационный алгоритм МГУА).
- Генетический алгоритм, его сходство с МГУА.
- Случайный поиск с адаптацией (СПА).
Логические алгоритмы классификации
- Понятие логической закономерности. Эвристическое, статистическое, энтропийное определение информативности. Асимптотическая эквивалентность статистического и энтропийного определения. Принципиальные отличия эвристического и статистического определения.
- Разновидности закономерностей: шары, гиперплоскости, гиперпараллелепипеды (конъюнкции).
- Бинаризация признаков, алгоритм выделения информативных зон.
- «Градиентный» алгоритм синтеза конъюнкций, частные случаи: жадный алгоритм, стохастический локальный поиск, стабилизация, редукция.
Решающие списки и деревья
- Решающий список. Жадный алгоритм синтеза списка.
- Решающее дерево. Псевдокод: жадный алгоритм ID3. Недостатки алгоритма и способы их устранения. Проблема переобучения.
- Редукция решающих деревьев: предредукция и постредукция.
- Преобразование решающего дерева в решающий список.
- Решающий лес и бустинг над решающими деревьями.
- Переключающиеся решающие деревья (alternating decision tree).
Взвешенное голосование закономерностей
- Принцип голосования. Проблема различности (диверсификации) закономерностей.
- Методы синтеза конъюнктивных закономерностей. Псевдокод: алгоритм КОРА, алгоритм ТЭМП.
- Алгоритм бустинга. Теорема сходимости.
- Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.
Алгоритмы вычисления оценок
- Принцип частичной прецедентности. Структура АВО.
- Тупиковые тесты.
- Тупиковые представительные наборы.
- Проблема оптимизации АВО. АВО как композиция метрических закономерностей.
- Применение бустинга, ТЭМП и СПА для оптимизации АВО.
Поиск ассоциативных правил
- Пример прикладной задачи: анализ рыночных корзин.
- Понятие ассоциативного правила и его связь с понятием логической закономерности.
- Псевдокод: алгоритм APriori, его недостатки и пути усовершенствования.