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

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

Версия 12:50, 30 апреля 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-алгоритм. Сети радиальных базисных функций (RBF) и их настройка с помощью EM-алгоритма.

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

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

Кластеризация и многомерное шкалирование

Методы кластеризации. Примеры прикладных задач. Графовые алгоритмы: связные компоненты, кратчайший незамкнутый путь, Форель. Функционалы качества кластеризации. Статистические алгоритмы: EM и k-means. Агломеративные (иерархические) алгоритмы. Формула Ланса-Вильямса. Алгоритм построения дендрограммы. Свойства сжатия/растяжения, монотонности и редуктивности. Определение числа кластеров. Потоковые (субквадратичные) алгоритмы кластеризации.

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

Алгоритмы восстановления регрессии

Непараметрическая регрессия. Локально взвешенный метод наименьших квадратов и оценка Надарая-Ватсона. Выбор функции ядра. Выбор ширины окна сглаживания. Сглаживание с переменной шириной окна. Проблема «выбросов» и робастная непараметрическая регрессия. Проблема «проклятия размерности» и проблема выбора метрики.

Многомерная линейная регрессия. Принцип наименьших квадратов. Сингулярное разложение. Проблемы мультиколлинеарности и переобучения. Гребневая регрессия. Лассо Тибширани. Линейная монотонная регрессия (симплекс-метод). Линейные преобразования признакового пространства. Метод главных компонент и декоррелирующее преобразование Карунена-Лоэва. Робастная регрессия.

Шаговая регрессия. Алгоритм модифицированной ортогонализации Грама-Шмидта, достоинства и недостатки. Отбор признаков в процессе ортогонализации, критерии выбора и останова. Метод наименьших углов, его связь с лассо и шаговой регрессией.

Нелинейная параметрическая регрессия. Методы Ньютона-Рафсона и Ньютона-Гаусса. Одномерные нелинейные преобразования признаков: метод обратной настройки (backfitting) Хасти-Тибширани. Обобщённые линейные модели. Неквадратичные функции потерь, примеры прикладных задач.

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

Элементы теории обобщающей способности

Функционалы скользящего контроля. Теорема Вапника-Червоненкиса. Функция роста и ёмкость. Емкость некоторых семейств алгоритмов. Метод структурной минимизации риска. Принцип минимума длины описания. Достаточная длина обучающей выборки. Причины завышенности оценок Вапника-Червоненкиса. Эффект локализации семейства алгоритмов. Оценки, зависящие от данных. Принцип самоограничения сложности. Декомпозиция ошибки на шум, смещение и вариацию. Понятие стабильности обучения. Методы эмпирического оценивания обобщающей способности.

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

Критерии качества модели. Внутренние и внешние критерии. Скользящий контроль, критерии непротиворечивости и регуляризации. Критерии, основанные на оценках обобщающей способности: Вапника-Червоненкиса, Акаике (AIC), байесовский (BIC). Статистические критерии: коэффициент детерминации, критерий Фишера, анализ остатков.

Методы отбора признаков. Полный перебор, методы добавлений и удалений (шаговая регрессия), поиск в глубину (метод ветвей и границ), усечённый поиск в ширину (многорядный итерационный алгоритм МГУА), генетический алгоритм, случайный поиск с адаптацией.

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

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

Персептроны. Естественный нейрон и его математическая модель. Персептрон Розенблатта. Метод стохастического градиента. Теорема сходимости (Новикова). Связь однослойного персептрона с логистической регрессией и обоснование сигмоидной функции потерь. Проблема «исключающего или». Проблема полноты. Полнота двухслойных сетей в пространстве булевских функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства).

Многослойные нейронные сети. Алгоритм обратного распространения ошибок. Недостатки алгоритма, способы их устранения. Проблема переобучения. Проблема «паралича» сети. Редукция весов. Подбор структуры сети. Метод оптимальной редукции сети (optimal brain damage).

Обучающееся векторное квантование (сети Кохонена). Структура сети Кохонена. Конкурентное обучение, стратегии WTA и WTM. Самоорганизующиеся карты Кохонена. Применение для визуального анализа данных. Сети встречного распространения, их применение для кусочно-постоянной и гладкой аппроксимации функций.

Машины опорных векторов

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

Алгоритмические композиции

Линейные алгоритмические композиции. Понятия базового алгоритма и корректирующей операции. Процесс последовательного обучения базовых алгоритмов. Простое голосование (комитет большинства). Решающий список (комитет старшинства). Взвешенное голосование. Бустинг: алгоритм AdaBoost, теорема сходимости. Стохастические методы: бэггинг и метод случайных подпространств.

Метод комитетов. Комитеты большинства, простое и взвешенное голосование. Сопоставление с нейронной сетью. Понятия максимальной совместной подсистемы и минимального комитета. Алгоритм построения комитета большинства. Верхняя оценка числа членов комитета.

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

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

Понятие логической закономерности. Энтропийное и комбинаторное определения информативности, их асимптотическая эквивалентность. Разновидности закономерностей: шары, гиперплоскости, гиперпараллелепипеды (конъюнкции). Бинаризация признаков, алгоритм выделения информативных зон. «Градиентный» алгоритм синтеза конъюнкций, частные случаи: жадный алгоритм, стохастический локальный поиск, стабилизация, редукция.

Решающие списки. Жадный алгоритм синтеза списка. Разновидности решающих правил в списках: шары, гиперплоскости, гиперпараллелепипеды (конъюнкции).

Решающие деревья. Алгоритм синтеза дерева ID3. Недостатки алгоритма и способы их устранения. Проблема переобучения. Редукция решающих деревьев: предредукция и постредукция. Преобразование решающего дерева в решающий список. Решающий лес и бустинг над решающими деревьями.

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

Алгоритмы вычисления оценок. Принцип частичной прецедентности. Структура АВО. Тупиковые тесты и тупиковые представительные наборы. Проблема оптимизации АВО. АВО как композиция метрических закономерностей. Применение бустинга для оптимизации АВО.

Поиск ассоциативных правил. Пример прикладной задачи: анализ рыночных корзин. Понятие ассоциативного правила и его связь с понятием логической закономерности. Алгоритм APriori, его недостатки и пути усовершенствования.

Файлы

Программа курса

Экзаменационные билеты

Практикум