Новогодние каникулы – хорошее время не только для отдыха, но и для самообразования. Можно отвлечься от повседневных задач и посвятить несколько дней тому, чтобы научиться чему-нибудь новому, что будет помогать вам весь год (а может и не один). Поэтому мы решили в эти выходные опубликовать серию постов с лекциями курсов первого семестра Школы анализа данных.
Сегодня — о самом важном. Современный анализ данных без него представить невозможно. В рамках курса рассматриваются основные задачи обучения по прецедентам: классификация, кластеризация, регрессия, понижение размерности. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами.
Читает курс лекций Константин Вячеславович Воронцов, старший научный сотрудник Вычислительного центра РАН. Заместитель директора по науке ЗАО «Форексис». Заместитель заведующего кафедрой «Интеллектуальные системы» ФУПМ МФТИ. Доцент кафедры «Математические методы прогнозирования» ВМиК МГУ. Эксперт компании «Яндекс». Доктор физико-математических наук.
Лекция 1. Основные понятия и примеры прикладных задач
- Постановка задач обучения по прецедентам. Объекты и признаки. Типы шкал: бинарные, номинальные, порядковые, количественные.
- Типы задач: классификация, регрессия, прогнозирование, кластеризация.
- Основные понятия: модель алгоритмов, метод обучения, функция потерь и функционал качества, принцип минимизации эмпирического риска, обобщающая способность, скользящий контроль.
- Примеры прикладных задач.
Лекция 2. Байесовские алгоритмы классификации, непараметрические методы
- Вероятностная постановка задачи классификации. Основные понятия: априорная вероятность, апостериорная вероятность, функция правдоподобия класса.
- Функционал среднего риска. Ошибки I и II рода.
- Оптимальный байесовский классификатор.
- Оценивание плотности распределения: три основных подхода.
- Наивный байесовский классификатор.
- Непараметрическое оценивание плотности распределения по Парзену-Розенблатту. Выбор функции ядра. Выбор ширины окна, переменная ширина окна. Метод парзеновского окна.
- Непараметрический наивный байесовский классификатор.
- Робастное оценивание плотности. Цензурирование выборки (отсев объектов-выбросов).
Лекция 3. Параметрические методы, нормальный дискриминантный анализ
- Многомерное нормальное распределение: геометрическая интерпретация, выборочные оценки параметров: вектора математического ожидания и ковариационной матрицы.
- Квадратичный дискриминант. Вид разделяющей поверхности. Подстановочный алгоритм, его недостатки и способы их устранения.
- Линейный дискриминант Фишера.
- Проблемы мультиколлинеарности и переобучения. Регуляризация ковариационной матрицы.
- Метод редукции размерности.
- Модель смеси распределений.
- EM-алгоритм: основная идея, понятие скрытых переменных, Е-шаг, М-шаг. Конструктивный вывод формул М-шага (без обоснования сходимости).
Лекция 4. EM-алгоритм и сеть радиальных базисных функций
- Критерий останова, выбор начального приближения, выбор числа компонент.
- Стохастический EM-алгоритм.
- Смесь многомерных нормальных распределений. Сеть радиальных базисных функций (RBF) и применение EM-алгоритма для её настройки.
- Метод ближайших соседей (kNN) и его обобщения.
- Подбор числа k по критерию скользящего контроля.
Лекция 5. Метрические алгоритмы классификации
- Обобщённый метрический классификатор, понятие отступа.
- Метод потенциальных функций, градиентный алгоритм.
- Отбор эталонных объектов. Псевдокод: алгоритм СТОЛП.
- Функция конкурентного сходства, алгоритм FRiS-СТОЛП.
- Биологический нейрон, модель МакКаллока-Питтса.
- Линейный классификатор, понятие отступа, непрерывные аппроксимации пороговой функции потерь.
- Лекция 6. Линейные алгоритмы классификации
- Квадратичная функция потерь, метод наименьших квадратов, связь с линейным дискриминантом Фишера.
- Метод стохастического градиента и частные случаи: адаптивный линейный элемент ADALINE, перcептрон Розенблатта, правило Хэбба.
- Недостатки метода стохастического градиента и способы их устранения. Ускорение сходимости, «выбивание» из локальных минимумов. Проблема переобучения, редукция весов (weight decay).
- Гипотеза экспоненциальности функций правдоподобия классов.
- Теорема о линейности байесовского оптимального классификатора.
- Оценивание апостериорных вероятностей классов с помощью сигмоидной функции активации.
- Логистическая регрессия. Принцип максимума правдоподобия и логарифмическая функция потерь.
- Метод стохастического градиента, аналогия с правилом Хэбба.
Лекция 7. Метод опорных векторов (SVM)
- Оптимальная разделяющая гиперплоскость. Понятие зазора между классами (margin). Случаи линейной разделимости и отсутствия линейной разделимости.
- Связь с минимизацией регуляризованного эмпирического риска. Кусочно-линейная функция потерь.
- Задача квадратичного программирования и двойственная задача. Понятие опорных векторов.
- Рекомендации по выбору константы C.
- Функция ядра (kernel functions), спрямляющее пространство, теорема Мерсера.
- Способы конструктивного построения ядер. Примеры ядер.
- Сопоставление SVM с гауссовским ядром и RBF-сети.
Лекция 8. Линейные методы классификации: обобщения и обзор
- Теоретические обоснования различных непрерывных функций потерь и различных регуляризаторов.
- Байесовский подход. Принцип максимума совместного правдоподобия данных и модели.
- Некоторые разновидности регуляризаторов, применяемые на практике. Квадратичный (L2) регуляризатор. L1- и L0- регуляризаторы и их связь с отбором признаков.
- Метод релевантных векторов.
- Сложностный подход. Радемахеровская сложность и некоторые её свойства. Верхняя оценка вероятности ошибки для линейных классификаторов.
Лекция 9. Методы восстановления регрессии
- Задача восстановления регрессии, метод наименьших квадратов.
- Одномерная непараметрическая регрессия (сглаживание): оценка Надарая-Ватсона, выбор ядра и ширины окна сглаживания.
- Многомерная линейная регрессия. Сингулярное разложение.
- Регуляризация: гребневая регрессия и лассо Тибширани.
- Метод главных компонент и декоррелирующее преобразование Карунена-Лоэва.
- Робастная регрессия: простой алгоритм отсева выбросов LOWESS.
Лекция 10. Прогнозирование временных рядов
- Аддитивная и мультипликативная модели временного ряда. Тренд, сезонность, календарные эффекты.
- Адаптивные модели: экспоненциальное сглаживание, модели Хольта-Уинтерса и Тейла-Вейджа.
- Скользящий контрольный сигнал и модель Тригга-Лича.
- Адаптивная селекция и композиция моделей прогнозирования.
- Примеры прикладных задач: прогнозирование трафика, числа посещений, объёмов продаж.
Лекция 11. Нейронные сети
- Структура многослойной нейронной сети. Функции активации.
- Проблема полноты. Задача исключающего или. Полнота двухслойных сетей в пространстве булевских функций.
- Алгоритм обратного распространения ошибок. Формирование начального приближения. Проблема паралича сети.
- Методы оптимизации структуры сети. Выбор числа слоёв и числа нейронов в скрытом слое. Постепенное усложнение сети. Оптимальное прореживание сети (optimal brain damage).
Лекция 12. Алгоритмы кластеризации
- Постановка задачи кластеризации. Типы кластерных структур.
- Графовые методы кластеризации: алгоритм выделения связных компонент, алгоритм ФОРЭЛ, функционалы качества кластеризации.
- Иерархическая кластеризация (таксономия): агломеративная иерархическая кластеризация, дендрограмма и свойство монотонности, свойства сжатия, растяжения и редуктивности.
- Статистические методы кластеризации: EM-алгоритм, метод k-средних.
Лекция 13. Методы частичного обучения
- Простые эвристические методы: особенности задачи SSL, метод self-training, композиции алгоритмов классификации.
- Модификация методов кластеризации: оптимизационный подход, кластеризация с ограничениями.
- Модификация методов классификации: трансдуктивный SVM, логистическая регрессия, Expectation Regularization.
Лекции 14-15. Композиции классификаторов. Бустинг (часть 1, часть 2)
- Композиция классификаторов: задачи обучения композиций, классический алгоритм AdaBoost, градиентный бустинг.
- Бэггинг и комитетные методы: бэггинг и метод случайных подпространств, простое и взвешенное голосование, голосование по старшинству.
- Смеси алгоритмов: идея областей компетентности, итерационный метод обучения смеси, последовательное наращивание смеси.
Лекция 16. Оценки обобщающей способности
- Задачи и критерии выбора метода обучения: задачи выбора модели или метода обучения, эмпирические оценки скользящего контроля, аналитические оценки и критерии регуляризации.
- Теория обобщающей способности: вероятность переобучения и VC-теория, бритва Оккама, комбинаторная теория переобучения.
- Методы отбора признаков: полный перебор и жадные алгоритмы, поиск в глубину и в ширину, стохастический поиск.
Лекция 17. Методы отбора признаков. Отбор признаков
- Сложность задачи отбора признаков. Полный перебор.
- Метод добавления и удаления, шаговая регрессия.
- Поиск в глубину, метод ветвей и границ.
- Усечённый поиск в ширину, многорядный итерационный алгоритм МГУА.
- Генетический алгоритм, его сходство с МГУА.
- Случайный поиск и Случайный поиск с адаптацией (СПА).
Лекция 18. Логические алгоритмы классификации
- Понятие закономерности и информативности: определения и обозначения, интерпретируемость, информативность.
- Методы поиска информативных закономерностей: жадный алгоритм, алгоритм на основе отбора признаков, бинаризация данных.
- Композиции закономерностей: решающий список, решающие деревья, голосование закономерносей, решающие леса.
Лекция 19. Логические алгоритмы классификации. Решающие деревья
- Решающий список. Жадный алгоритм синтеза списка.
- Решающее дерево. Псевдокод: жадный алгоритм ID3. Недостатки алгоритма и способы их устранения. Проблема переобучения.
- Редукция решающих деревьев: предредукция и постредукция.
- Преобразование решающего дерева в решающий список.
- Алгоритм LISTBB.
- Чередующиеся решающие деревья (alternating decision tree).
- Невнимательные решающие деревья (oblivious decision tree).
- Решающий лес и бустинг над решающими деревьями. Алгоритм TreeNet.
Лекция 20. Логические алгоритмы классификации. Взвешенное голосование
- Методы синтеза конъюнктивных закономерностей. Псевдокод: алгоритм КОРА, алгоритм ТЭМП.
- Эвристики, обеспечивающие различность и полезность закономерностей. Построение Парето-оптимальных закономерностей. Выравнивание распределения отступов.
- Применение алгоритма бустинга AdaBoost к закономерностям. Критерий информативности в бустинге.
- Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.
Лекция 21. Поиск ассоциативных правил
- Методы синтеза конъюнктивных закономерностей. Псевдокод: алгоритм КОРА, алгоритм ТЭМП.
- Эвристики, обеспечивающие различность и полезность закономерностей. Построение Парето-оптимальных закономерностей. Выравнивание распределения отступов.
- Применение алгоритма бустинга AdaBoost к закономерностям. Критерий информативности в бустинге.
- Примеры прикладных задач: кредитный скоринг, прогнозирование ухода клиентов.
Лекция 22. Коллаборативные итерации
- Постановка задачи и приложения.
- Корреляционные модели, основанные на хранении данных, задача восстановления пропущенных значений функция близости.
- Латентные модели: бикластеризация и матричные разложения, вероятностные латентные модели, эксперименты из данных Яндекса.
Лекции 23-24. Тематическое моделирование (часть 1, часть 2)
- Задача тематического моделирования: вероятностная тематическая модель, униграммная модель.
- Тематические модели PLSA и LDA: вероятностная латентная семантическая модель, латентное размещения Дирихле, эмпирические оценки качества тематических моделей.
- Робастная вероятностная тематическая модель: модель с фоновой и шумовой компонентами, EM-алгоритм для робастной модели, разреженность робастной модели.
Лекция 25. Обучение с подкреплением
- Многорукий бандит: простая постановка задачи, жадные и полужадные стратегии, адаптивные стратегии.
- Динамическое программирование: полная постановка задачи, уравнение Беллмана.
- Метод временных разностей.
Автор: anton
