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

Версия 15:04, 4 ноября 2011 (править) Vokov (Обсуждение | вклад) (Поиск ассоциативных правил) ← К предыдущему изменению		Версия 15:06, 4 ноября 2011 (править) (отменить) Vokov (Обсуждение | вклад) (→Решающие списки и деревья) К следующему изменению →
Строка 276:		Строка 276:
	* ''[[Алгоритм LISTBB]].''		* ''[[Алгоритм LISTBB]].''
	* [[Чередующиеся решающие деревья]] (alternating decision tree).		* [[Чередующиеся решающие деревья]] (alternating decision tree).
		+	* [[Невнимательные решающие деревья]] (oblivious decision tree).
	* [[Решающий лес]] и бустинг над решающими деревьями. ''[[Алгоритм TreeNet]].''		* [[Решающий лес]] и бустинг над решающими деревьями. ''[[Алгоритм TreeNet]].''

---

Версия 15:06, 4 ноября 2011

Содержание 1 Замечания для студентов 2 Первый семестр 2.1 Основные понятия и примеры прикладных задач 2.2 Статистичесие (байесовские) методы классификации 2.2.1 Оптимальный байесовский классификатор 2.2.2 Непараметрическое оценивание плотности 2.2.3 Параметрическое оценивание плотности 2.2.4 Разделение смеси распределений 2.3 Метрические методы классификации 2.3.1 Метод ближайших соседей и его обобщения 2.3.2 Отбор эталонов и оптимизация метрики 2.4 Линейные методы классификации 2.4.1 Градиентные методы 2.4.2 Логистическая регрессия 2.4.3 Метод опорных векторов 2.5 Методы регрессионного анализа 2.5.1 Непараметрическая регрессия 2.5.2 Многомерная линейная регрессия 2.5.3 Нелинейная параметрическая регрессия 2.6 Нейросетевые методы классификации и регрессии 2.6.1 Многослойные нейронные сети 2.7 Методы кластеризации 2.7.1 Кластеризация 2.7.2 Таксономия 2.7.3 Сети Кохонена 2.7.4 Многомерное шкалирование 3 Второй семестр 3.1 Критерии выбора моделей и методы отбора признаков 3.1.1 Задачи оценивания и выбора моделей 3.1.2 Теория обобщающей способности 3.1.3 Методы отбора признаков 3.2 Композиционные методы классификации и регрессии 3.2.1 Линейные композиции, бустинг 3.2.2 Эвристические и стохастические методы 3.2.3 Бустинг алгоритмов ранжирования 3.2.4 Нелинейные алгоритмические композиции 3.3 Логические методы классификации 3.3.1 Понятия закономерности и информативности 3.3.2 Решающие списки и деревья 3.3.3 Взвешенное голосование закономерностей 3.3.4 Алгоритмы вычисления оценок 3.4 Поиск ассоциативных правил 3.5 Задачи с частичным обучением 3.6 Список подстраниц

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Статистичесие (байесовские) методы классификации

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

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

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

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

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

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

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

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

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

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

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

Метод ближайших соседей и его обобщения

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

Отбор эталонов и оптимизация метрики

• Отбор эталонных объектов. Псевдокод: алгоритм СТОЛП.
• Функция конкурентного сходства, алгоритм FRiS-СТОЛП.
• Функционал полного скользящего контроля, формула быстрого вычисления для метода 1NN. Профиль компактности. Функция вклада объекта. Отбор эталонных объектов на основе минимизации функционала полного скользящего контроля. Эффективные структуры данных для быстрого поиска ближайших объектов в прямых и обратных окрестностях — метрические деревья.
• Проклятие размерности. Задача настройки весов признаков.
• Концепция вывода на основе прецедентов (CBR).

Линейные методы классификации

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

Градиентные методы

• Линейный классификатор, непрерывные аппроксимации пороговой функции потерь. Связь с методом максимума правдоподобия.
• Квадратичная функция потерь, метод наименьших квадратов, связь с линейным дискриминантом Фишера.
• Метод стохастического градиента и частные случаи: адаптивный линейный элемент ADALINE, перcептрон Розенблатта, правило Хэбба.
• Теорема Новикова о сходимости. Доказательство теоремы Новикова
• Эвристики: инициализация весов, порядок предъявления объектов, выбор величины градиентного шага, «выбивание» из локальных минимумов.
• Проблема переобучения, редукция весов (weight decay).
• Байесовская регуляризация. Принцип максимума совместного правдоподобия данных и модели. Квадратичный (гауссовский) и лапласовский регуляризаторы.

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

• Гипотеза экспоненциальности функций правдоподобия классов. Теорема о линейности байесовского оптимального классификатора. Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
• Логистическая регрессия. Принцип максимума правдоподобия и логарифмическая функция потерь. Снова метод стохастического градиента, сглаженное правило Хэбба.
• Пример прикладной задачи: кредитный скоринг. Бинаризация признаков. Скоринговые карты и оценивание вероятности дефолта. Риск кредитного портфеля банка.
• Настройка порога решающего правила по критерию числа ошибок I и II рода. Кривая ошибок (ROC curve). Алгоритм эффективного построения ROC-кривой.

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

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

Методы регрессионного анализа

Презентация: (PDF, 781 КБ).

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

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

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

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

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

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

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

Презентация: (PDF, 577 КБ).

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

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

Методы кластеризации

Презентация: (PDF, 1,43 МБ).

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

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

Таксономия

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

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

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

Многомерное шкалирование

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

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

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

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

Задачи оценивания и выбора моделей

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

Теория обобщающей способности

• Теория Вапника-Червоненкиса. Функционал равномерного отклоненеия частот ошибок. Функция роста, ёмкость семейства алгоритмов. Структурная минимизация риска.
• Оценка «бритвы Оккама».
• Радемахеровская сложность семейства алгоритмов.
• Комбинаторная теория переобучения. Функционал вероятности переобучения. Граф расслоения-связности. Оценки расслоения-связности.

Методы отбора признаков

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

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

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

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

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

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

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

Бустинг алгоритмов ранжирования

• Задача ранжирования. Примеры: ранжирование результатов текстового поиска, задача Netflix.
• Функционал качества — число дефектных пар.
• Бустинг алгоритмов ранжирования — аналоги AdaBoost и AnyBoost.
• Двудольная задача. Сведение попарного функционала качества к поточечному.

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

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

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

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

Понятия закономерности и информативности

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

Решающие списки и деревья

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

Взвешенное голосование закономерностей

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

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

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

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

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

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

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

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

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

Машинное обучение (курс лекций, К.В.Воронцов)/2009	Машинное обучение (курс лекций, К.В.Воронцов)/ToDo	Машинное обучение (курс лекций, К.В.Воронцов)/Вопросы
Машинное обучение (курс лекций, К.В.Воронцов)/Семестровый курс	Машинное обучение (курс лекций, К.В.Воронцов)/Форма отчета