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

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

Версия 18:50, 23 июля 2008

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

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

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

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

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

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

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

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

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

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

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

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

Лекция 3. Параметрическое оценивание плотности

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

Лекция 4. Разделение смеси распределений

• Смесь распределений.
• EM-алгоритм: основная идея, понятие скрытых переменных. «Вывод» алгоритма без обоснования сходимости. Псевдокод EM-алгоритма. Критерий останова. Выбор начального приближения. Выбор числа компонентов смеси.
• Стохастический EM-алгоритм.
• Смесь многомерных нормальных распределений. Сеть радиальных базисных функций (RBF) и применение EM-алгоритма для её настройки.

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

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

Лекция 6. Кластеризация

• Постановка задачи кластеризации. Примеры прикладных задач.
• Графовые алгоритмы кластеризации. Алгоритм связных компонент.
• Псевдокод алгоритма: кратчайший незамкнутый путь.
• Псевдокод алгоритма: ФОРЭЛ.
• Функционалы качества кластеризации.
• Статистические алгоритмы: EM-алгоритм. Псевдокод алгоритма k-means.

Лекция 7. Иерерхическая кластеризация и многомерное шкалирование

• Псевдокод алгоритма: агломеративная кластеризация. Формула Ланса-Вильямса.
• Алгоритм построения дендрограммы. Определение числа кластеров.
• Свойства сжатия/растяжения, монотонности и редуктивности. Псевдокод редуктивной версии алгоритма.

Потоковые (субквадратичные) алгоритмы кластеризации.

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

Лекция 8. Непараметрическая регрессия

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

Лекция 9. Многомерная линейная регрессия

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

Лекция 10. Шаговая регрессия

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

Лекция 11. Нелинейная параметрическая регрессия

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

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

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

Лекция 13. Элементы теории обобщающей способности

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

Лекция 14. Оценивание и выбор моделей

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

Лекция 15. Методы отбора признаков

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

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

Лекция 1. Однослойный персептрон

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

Лекция 2. Многослойные нейронные сети

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

Лекция 3. Обучающееся векторное квантование (сети Кохонена)

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

Лекция 4. Метод опорных векторов

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

Лекция 5. Оптимизационные техники решения задачи SVM

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

Лекция 6. Алгоритмические композиции

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

Лекция 7. Бустинг, бэггинг и аналоги

• Взвешенное голосование.
• Экспоненциальная аппроксимация пороговой функции потерь. Теорема о сходимости бустинга.
• Псевдокод: алгоритм AdaBoost.
• Варианты бустинга: GentleBoost, LogitBoost, BrownBoost, и другие.
• Стохастические методы: бэггинг и метод случайных подпространств.

Лекция 8. Метод комитетов

• Общее понятие: комитет системы ограничений. Комитеты большинства, простое и взвешенное голосование (z,p-комитеты).
• Теоремы о существовании комитетного решения.
• Сопоставление комитета линейных неравенств с нейронной сетью.
• Максимальная совместная подсистема, минимальный комитет. Теоремы об NP-полноте задачи поиска минимального комитета.
• Алгоритм построения комитета, близкого к минимальному. Верхняя оценка числа членов комитета.

Лекция 9. Нелинейные алгоритмические композиции

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

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

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

Лекция 11. Решающие списки и деревья

• Решающий список. Жадный алгоритм синтеза списка.
• Решающее дерево. Псевдокод: жадный алгоритм ID3. Недостатки алгоритма и способы их устранения. Проблема переобучения.
• Редукция решающих деревьев: предредукция и постредукция.
• Преобразование решающего дерева в решающий список.
• Решающий лес и бустинг над решающими деревьями.
• Переключающиеся решающие деревья (alternating decision tree).

Лекция 12. Взвешенное голосование логических закономерностей

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

Лекция 13. Алгоритмы вычисления оценок

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

Лекция 14. Поиск ассоциативных правил

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

Файлы

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

Практикум