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

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

Версия 14:38, 19 января 2009

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

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

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

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

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

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

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

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

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

Скачать: 1.1. Основные понятия и примеры прикладных задач (PDF, 929 КБ). 1.2–1.4. Статистические (байесовские) методы классификации (PDF, 776 КБ). 1.5. Метрические методы классификации (PDF, 382 КБ). 1.6, 1.7, 1.9, 1.10. Линейные методы классификации (PDF, 1,56 МБ). 1.8. Нейронные сети (PDF, 346 КБ). 1.11–1.13. Регрессия (PDF, 421 КБ). Замечание. В этих лекциях есть материал, который не входит в программу курса. Он включён «для общего развития» и на экзамене спрашиваться не будет.

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

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

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

• Оптимальный байесовский классификатор.
• Функционал среднего риска. Ошибки 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, его недостатки и пути усовершенствования.