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

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

Версия 12:38, 29 августа 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-алгоритма для её настройки.

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

• Естественный нейрон, модель МакКаллока-Питтса, функции активации.
• Линейный классификатор, непрерывные аппроксимации пороговых функций потерь.
• Квадратичная функция потерь, метод наименьших квадратов, связь с линейным дискриминантом Фишера.
• Метод стохастического градиента и частные случаи: адаптивный линейный элемент ADALINE, перцептрон Розенблатта, правило Хэбба.
• Теорема Новикова о сходимости.

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

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

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

• Проблема исключающего или. Проблема полноты. Полнота двухслойных сетей в пространстве булевских функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства).
• Алгоритм обратного распространения ошибок. Недостатки алгоритма, способы их устранения.
• Проблема переобучения.
• Проблема «паралича» сети.
• Редукция весов (weight decay).
• Подбор структуры сети: методы постепенного усложнения сети, метод оптимального прореживания сети (optimal brain damage).

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

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

Методы оптимизации SVM

• Обучение SVM методом последовательной минимизации. Псевдокод: алгоритм SMO.
• Обучение SVM методом активных ограничений. Псевдокод: алгоритм INCAS.
• SVM-регрессия.

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

• Метод ближайших соседей (kNN) и его обобщения.
• Подбор числа k по критерию скользящего контроля.
• Обобщённый метрический классификатор.
• Метод потенциальных функций, градиентный алгоритм.
• Настройка весов объектов. Отбор эталонных объектов. Псевдокод: алгоритм СТОЛП.
• Проклятие размерности. Настройка весов признаков.
• Вывод на основе прецедентов (CBR).

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

• Сглаживание. Локально взвешенный метод наименьших квадратов и оценка Надарая-Ватсона.
• Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна.
• Проблема выбросов и робастная непараметрическая регрессия. Псевдокод: алгоритм 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, его недостатки и пути усовершенствования.