Машинное обучение (курс лекций, К.В.Воронцов)
Материал из MachineLearning.
(→Кластеризация) |
(→Обучение без учителя) |
||
Строка 285: | Строка 285: | ||
== Обучение без учителя == | == Обучение без учителя == | ||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
<!--- | <!--- |
Версия 18:04, 27 апреля 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Б) — обновление 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-алгоритм, теорема о стационарной точке.
- Регуляризаторы разреживания, сглаживания, декоррелирования и отбора тем.
Обучение с подкреплением
Презентация: (PDF, 0.9 МБ) — обновление 21.06.2014.
- Задача о многоруком бандите. Жадные и эпсилон-жадные стратегии. Метод UCB (upper confidence bound). Стратегия Softmax.
- Среда для экспериментов.
- Адаптивные стратегии на основе скользящих средних. Метод сравнения с подкреплением. Метод преследования.
- Общая постановка задачи обучения с подкреплением. Ценность состояния среды. Ценность действия.
- Метод временных разностей. Метод SARSA. Метод Q-обучения.
- Многошаговое TD-прогнозирование. Обобщения методов временных разностей, SARSA, Q-обучения.
- Адаптивный полужадный метод VDBE.
Ссылки
Список подстраниц
Машинное обучение (курс лекций, К.В.Воронцов)/2009 | Машинное обучение (курс лекций, К.В.Воронцов)/ToDo | Машинное обучение (курс лекций, К.В.Воронцов)/Вопросы |
Машинное обучение (курс лекций, К.В.Воронцов)/Семестровый курс | Машинное обучение (курс лекций, К.В.Воронцов)/Форма отчета |