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

Версия 11:19, 16 марта 2015

Теория обучения машин (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Б) — обновление 20.03.2014.

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

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

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

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

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

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

Неквадратичные функции потерь

• Метод наименьших модулей. Квантильная регрессия. Пример прикладной задачи: прогнозирование потребительского спроса.
• Робастная регрессия, функция Мешалкина.
• SVM-регрессия.

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

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

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

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

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

Оптимальный байесовский классификатор

• Принцип максимума апостериорной вероятности.
• Функционал среднего риска. Ошибки I и II рода.
• Теорема об оптимальности байесовского классификатора.
• Оценивание плотности распределения: три основных подхода.
• Наивный байесовский классификатор.

Непараметрическое оценивание плотности

• Ядерная оценка плотности Парзена-Розенблатта. Одномерный и многомерный случаи.
• Метод парзеновского окна.
• Выбор функции ядра. Выбор ширины окна, переменная ширина окна.
• Робастное оценивание плотности.
• Непараметрический наивный байесовский классификатор.

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

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

Разделение смеси распределений

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

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

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

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

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

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

Презентация: (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,0 МБ) — обновление 21.06.2014.

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

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

Сети Кохонена

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

Таксономия

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

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

Презентация: (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-алгоритм, теорема о стационарной точке.
• Регуляризаторы разреживания, сглаживания, декоррелирования и отбора тем.

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

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

• Задача о многоруком бандите. Жадные и эпсилон-жадные стратегии. Метод UCB (upper confidence bound). Стратегия Softmax.
• Среда для экспериментов.
• Адаптивные стратегии на основе скользящих средних. Метод сравнения с подкреплением. Метод преследования.
• Общая постановка задачи обучения с подкреплением. Ценность состояния среды. Ценность действия.
• Метод временных разностей. Метод SARSA. Метод Q-обучения.
• Многошаговое TD-прогнозирование. Обобщения методов временных разностей, SARSA, Q-обучения.
• Адаптивный полужадный метод VDBE.

Ссылки

• Машинное обучение (курс лекций, Н.Ю.Золотых)
• Машинное обучение (курс лекций, СГАУ, С.Лисицын)

Список подстраниц