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

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

(Различия между версиями)

Версия 18:04, 27 апреля 2015

Содержание

1 Замечания для студентов
2 Первый семестр
3 Второй семестр

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

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

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

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

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

Курс читается

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

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

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

Ниже представлена расширенная программа — в полном объёме она занимает больше, чем могут вместить в себя два семестра. Каждый параграф приблизительно соответствует одной лекции. Курсивом выделен дополнительный материал, который может разбираться на семинарах.

Замечания для студентов

Видеолекции ШАД Яндекс.
На подстранице имеется перечень вопросов к устному экзамену. Очень помогает при подготовке к устному экзамену!
О найденных ошибках и опечатках сообщайте мне. — К.В.Воронцов 18:24, 19 января 2009 (MSK)
Материал, который есть в pdf-тексте, но не рассказывался на лекциях, обычно не входит в программу экзамена.

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

Текст лекций: (PDF, 3 МБ) — обновление 4.10.2011.

Основные понятия и примеры прикладных задач

Презентация: (PDF, 1,4 МБ) — обновление 09.02.2015.

Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.
Типы задач: классификация, регрессия, прогнозирование, ранжирование.
Основные понятия: модель алгоритмов, метод обучения, функция потерь и функционал качества, принцип минимизации эмпирического риска, обобщающая способность, скользящий контроль.
Линейные модели регрессии и классификации. Метод наименьших квадратов. Полиномиальная регрессия.
Примеры прикладных задач.
Методика экспериментального исследования и сравнения алгоритмов на модельных и реальных данных.
Конкурсы по анализу данных kaggle.com. Полигон алгоритмов классификации.
CRISP-DM — межотраслевой стандарт ведения проектов интеллектуального анализа данных.

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

Презентация: (PDF, 3,5 МБ) — обновление 18.02.2015.

Гипотезы компактности и непрерывности.
Обобщённый метрический классификатор.
Метод ближайших соседей kNN и его обобщения. Подбор числа k по критерию скользящего контроля.
Метод окна Парзена с постоянной и переменной шириной окна.
Метод потенциальных функций и его связь с линейной моделью классификации.
Непараметрическая регрессия. Локально взвешенный метод наименьших квадратов. Ядерное сглаживание.
Оценка Надарая-Ватсона с постоянной и переменной шириной окна. Выбор функции ядра.
Задача отсева выбросов. Робастная непараметрическая регрессия. Алгоритм LOWESS.
Задача отбора эталонов. Понятие отступа. Алгоритм СТОЛП.
Задача отбора признаков. Жадный алгоритм построения метрики.

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

Текст лекций: (PDF, 625 КБ).
Презентация: (PDF, 1.8 МБ) — обновление 26.02.2015.

Понятие логической закономерности. Эвристическое, статистическое, энтропийное определение информативности. Индекс Джини. Сравнение областей эвристических и статистических закономерностей. Асимптотическая эквивалентность статистического и энтропийного определения.
Разновидности закономерностей: конъюнкции пороговых предикатов (гиперпараллелепипеды), синдромные правила, шары, гиперплоскости.
Жадные алгоритмы синтеза конъюнкций: стохастический локальный поиск, стабилизация, редукция.
Решающий пень. Бинаризация признаков. Алгоритм разбиения области значений признака на информативные зоны.
Решающий список. Жадный алгоритм синтеза списка.
Решающее дерево. Жадный алгоритм ID3. Недостатки алгоритма и способы их устранения. Проблема переобучения.
Редукция решающих деревьев: предредукция и постредукция.
Преобразование решающего дерева в решающий список.
Небрежные решающие деревья (oblivious decision tree).
Решающий лес. Случайный лес (Random Forest).

Критерии выбора моделей и методы отбора признаков

Текст лекций: (PDF, 330 КБ).
Презентация: (PDF, 1,0 МБ) — обновление 05.03.2015.

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

Градиентные методы обучения

Презентация: (PDF, 1,6 МБ) — обновление 09.03.2015.

Линейный классификатор, модель МакКаллока-Питтса, непрерывные аппроксимации пороговой функции потерь.
Метод стохастического градиента SG.
Метод стохастического среднего градиента SAG.
Частные случаи: адаптивный линейный элемент ADALINE, перcептрон Розенблатта, правило Хэбба.
Теорема Новикова о сходимости. Доказательство теоремы Новикова
Эвристики: инициализация весов, порядок предъявления объектов, выбор величины градиентного шага, «выбивание» из локальных минимумов.
Проблема мультиколлинеарности и переобучения, редукция весов (weight decay).
Функции потерь, зависящие от цены ошибок. Кривая ошибок (ROC curve). Алгоритм эффективного построения ROC-кривой.
Градиентный метод максимизации AUC.

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

Презентация: (PDF, 1,2 МБ) — обновление 16.03.2015.

Оптимальная разделяющая гиперплоскость. Понятие зазора между классами (margin).
Случаи линейной разделимости и отсутствия линейной разделимости. Связь с минимизацией регуляризованного эмпирического риска. Кусочно-линейная функция потерь.
Задача квадратичного программирования и двойственная задача. Понятие опорных векторов.
Рекомендации по выбору константы C.
Функция ядра (kernel functions), спрямляющее пространство, теорема Мерсера.
Способы конструктивного построения ядер. Примеры ядер.
SVM-регрессия.
Регуляризации для отбора признаков: LASSO SVM, Elastic Net SVM, SFM, RFM.
Вероятностная интерпретация регуляризации. Принцип максимума совместного правдоподобия данных и модели. Гауссовский и лапласовский регуляризаторы.
Метод релевантных векторов RVM
Обучение SVM методом активных ограничений. Алгоритм INCAS. Алгоритм SMO.
ню-SVM.

Многомерная линейная регрессия

Презентация: (PDF, 0,7 MБ) — обновление 24.03.2015.

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

Нелинейная регрессия

Презентация: (PDF, 0,7 MБ) — обновление 02.04.2015.

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

Прогнозирование временных рядов

Презентация: (PDF, 0,9 MБ) — обновление 06.04.2015.

Задача прогнозирования временных рядов. Примеры приложений.
Экспоненциальное скользящее среднее. Модель Хольта. Модель Тейла-Вейджа. Модель Хольта-Уинтерса.
Адаптивная авторегрессионная модель.
Следящий контрольный сигнал. Модель Тригга-Лича.
Адаптивная селективная модель. Адаптивная композиция моделей. Адаптация весов с регуляризацией.

Байесовская теория классификации

Презентация: (PDF, 1,1 МБ) — обновление 13.04.2015.

Принцип максимума апостериорной вероятности. Теорема об оптимальности байесовского классификатора.
Оценивание плотности распределения: три основных подхода.
Наивный байесовский классификатор.
Непараметрическое оценивание плотности. Ядерная оценка плотности Парзена-Розенблатта. Одномерный и многомерный случаи.
Метод парзеновского окна. Выбор функции ядра. Выбор ширины окна, переменная ширина окна.
Параметрическое оценивание плотности. Нормальный дискриминантный анализ.
Многомерное нормальное распределение, геометрическая интерпретация. Выборочные оценки параметров многомерного нормального распределения.
Матричное дифференцирование. Вывод оценок параметров многомерного нормального распределения.
Квадратичный дискриминант. Вид разделяющей поверхности. Подстановочный алгоритм, его недостатки и способы их устранения.
Линейный дискриминант Фишера. Связь с методом наименьших квадратов.
Проблемы мультиколлинеарности и переобучения. Регуляризация ковариационной матрицы.
Параметрический наивный байесовский классификатор.
Жадное добавление признаков в линейном дискриминанте, метод редукции размерности Шурыгина.
Робастное оценивание. Цензурирование выборки (отсев объектов-выбросов).

Логистическая регрессия. Разделение смеси распределений

Презентация: (PDF, 0,8 МБ) — обновление 20.04.2015.

Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
Логистическая регрессия. Принцип максимума правдоподобия и логарифмическая функция потерь.
Метод стохастического градиента для логарифмической функции потерь. Сглаженное правило Хэбба.
Метод наименьших квадратов с итеративным пересчётом весов (IRLS).
Пример прикладной задачи: кредитный скоринг. Бинаризация признаков. Скоринговые карты и оценивание вероятности дефолта. Риск кредитного портфеля банка.
Смесь распределений.
EM-алгоритм: основная идея, понятие скрытых переменных. Теорема об эквивалентной системе уравнений. ЕМ алгоритм как метод простых итераций.
Детали реализации EM-алгоритма. Критерий останова. Выбор начального приближения. Выбор числа компонентов смеси.
Стохастический EM-алгоритм.
Смесь многомерных нормальных распределений. Сеть радиальных базисных функций (RBF) и применение EM-алгоритма для её настройки.
Сопоставление RBF-сети и SVM с гауссовским ядром.

Кластеризация

Презентация: (PDF, 1,7 МБ) — обновление 27.04.2015.

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

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

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

Презентация: (PDF, 1,8 МБ) — обновление 16.04.2012.

Многослойные нейронные сети

Биологический нейрон, модель МакКаллока-Питтса как линейный классификатор. Функции активации.
Проблема полноты. Задача исключающего или. Полнота двухслойных сетей в пространстве булевых функций. Теоремы Колмогорова, Стоуна, Горбаня (без доказательства).
Алгоритм обратного распространения ошибок.
Эвристики: формирование начального приближения, ускорение сходимости, диагональный метод Левенберга-Марквардта. Проблема «паралича» сети.
Метод послойной настройки сети.
Подбор структуры сети: методы постепенного усложнения сети, оптимальное прореживание нейронных сетей (optimal brain damage).

Композиционные методы классификации и регрессии

Текст лекций: (PDF, 1 MБ).
Презентация: (PDF, 1.1 МБ) — обновление 04.03.2014.

Линейные композиции, бустинг

Основные понятия: базовый алгоритм (алгоритмический оператор), корректирующая операция.
Взвешенное голосование.
Алгоритм AdaBoost. Экспоненциальная аппроксимация пороговой функции потерь. Процесс последовательного обучения базовых алгоритмов. Теорема о сходимости бустинга.
Базовые алгоритмы в бустинге. Решающие пни.
Варианты бустинга: GentleBoost, LogitBoost, BrownBoost, и другие.
Алгоритм AnyBoost.
Градиентный бустинг.

Эвристические и стохастические методы

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

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

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

Ранжирование

Презентация: (PDF, 0,5 МБ) — обновление 27.11.2013.

Постановка задачи обучения ранжированию. Примеры.
Признаки в задаче ранжирования поисковой выдачи: текстовые, ссылочные, кликовые. TF-IDF. PageRank.
Критерии качества ранжирования: Precision, MAP, AUC, DCG, NDCG, pFound.
Ранговая классификация, OC-SVM.
Попарный подход: RankingSVM, RankNet, LambdaRank.

Обучение без учителя

Поиск ассоциативных правил

Презентация: (PDF, 1.1 МБ) — обновление 21.06.2014.

Понятие ассоциативного правила и его связь с понятием логической закономерности.
Примеры прикладных задач: анализ рыночных корзин, выделение терминов и тематики текстов.
Алгоритм APriori. Два этапа: поиск частых наборов и рекурсивное порождение ассоциативных правил. Недостатки и пути усовершенствования алгоритма APriori.
Алгоритм FP-growth. Понятия FP-дерева и условного FP-дерева. Два этапа поиска частых наборов в FP-growth: построение FP-дерева и рекурсивное порождение частых наборов.
Общее представление о динамических и иерархических методах поиска ассоциативных правил.

Задачи с частичным обучением

Презентация: (PDF, 0.9 МБ) — обновление 21.06.2014.

Постановка задачи Semisupervised Learning, примеры приложений.
Простые эвристические методы: self-training, co-training, co-learning.
Адаптация алгоритмов кластеризации для решения задач с частичным обучением. Кратчайшиё незамкнутый путь. Алгоритм Ланса-Уильямса. Алгоритм k-средних.
Трансдуктивный метод опорных векторов TSVM.
Алгоритм Expectation-Regularization на основе многоклассовой регуляризированной логистической регрессии.

Коллаборативная фильтрация

Презентация: (PDF, 1.5 МБ) — обновление 13.04.2014.

Задачи коллаборативной фильтрации, транзакционные данные и матрица субъекты—объекты.
Корреляционные методы user-based, item-based.
Латентные методы на основе би-кластеризации. Алгоритм Брегмана.
Латентные методы на основе матричных разложений. Метод главных компонент для разреженных данных. Метод стохастического градиента.
Неотрицательные матричные разложения. Разреженный SVD. Метод чередующихся наименьших квадратов ALS.

Тематическое моделирование

Текст лекций: (PDF, 830 КБ).
Презентация: (PDF, 2.5 МБ) — обновление 12.11.2014.

Задача тематического моделирования коллекции текстовых документов.
Метод максимума правдоподобия. Униграммная модель документа. Применение метода множителей Лагранжа.
Вероятностный латентный семантический анализ PLSA. ЕМ-алгоритм.
Латентное размещение Дирихле LDA. Сглаженная частотная оценка условной вероятности.
Аддитивная регуляризация тематических моделей. Регуляризованный EM-алгоритм, теорема о стационарной точке.
Регуляризаторы разреживания, сглаживания, декоррелирования и отбора тем.

Обучение с подкреплением