На YouTube опубликован цикл из 22 лекций курса «Машинное обучение» К.В.Воронцова, прочитанных в 2019 году в Школе анализа данных (Яндекс).
Воронцов Константин Вячеславович — профессор кафедры интеллектуальных систем факультета управления и прикладной математики МФТИ, доктор физико-математических наук, доцент кафедры математических методов прогнозирования факультета ВМиК МГУ, преподаватель Школы анализа данных Яндекса, профессор ВШЭ.
Школа анализа данных (ШАД) — это бесплатная двухгодичная программа для тех, кто хочет стать продвинутым датасаентистом или архитектором систем хранения и обработки больших данных. Лекции и семинары в ШАДе проводят сотрудники Яндекса, преподаватели ведущих университетов.
Вводная лекция
В первой половине лекции вводятся обозначения и понятия, которые будут использоваться на протяжении всего курса: объекты, признаки, функция потерь, предсказательная модель, минимизация эмпирического риска, обучающая выборка, тестовая выборка, переобучение, скользящий контроль. Во второй половине лекции приводятся примеры прикладных задач классификации, регрессии, ранжирования. В конце кратко обсуждаются некоторые вопросы методологии машинного обучения: особенности реальных данных, межотраслевой стандарт CRISP-DM, организация вычислительных экспериментов.
Линейная модель играет фундаментальную роль в теории машинного обучения. Это простейшая модель нейрона и основной строительный блок для нейронных сетей. Обучать её можно с помощью метода стохастического градиента. На практике он нуждается в различных эвристических усовершенствованиях. Одно из важнейших – регуляризация. Она делает решение устойчивым в случае мультиколлинеарных признаков и уменьшает переобучение. Постановка задачи построения разделяющей поверхности в терминах теории вероятности приводит к пониманию регуляризатора через априорное распределение параметров модели. В конце рассматривается логистическая регрессия – метод классификации, способный не только классифицировать объекты, но и давать оценки вероятностей классов.
Метод ближайшего соседа является, пожалуй, самым простым методом классификации. Разбирая один за другим его недостатки, мы приходим к методам взвешенных ближайших соседей, парзеновского окна, потенциальных функций… и осознаём, что снова пришли к линейному классификатору. Отбор эталонных объектов в ленивом обучении в некоторых задачах позволяет радикально уменьшить объём хранимых данных, а, если повезёт, то и улучшить качество классификации. Идея, что схожим объектам должны соответствовать схожие ответы, в регрессии приводит к непараметрическим методам типа ядерного сглаживания. Выводы на удивление те же, что и для классификации: подбор ширины окна принципиально важен для оптимизации качества модели, а выбор ядра сглаживания отвечает лишь за её гладкость. В конце рассматривается проблема обнаружения и отсева выбросов.
Снова линейный классификатор. Принцип максимума ширины зазора между классами приводит к выпуклой задаче квадратичного программирования, которая имеет массу замечательных свойств. Во-первых, её решение единственно. Во-вторых, оно зависит не от всей выборки, а только от горстки объектов на границе между классами, которые и называются опорными векторами. В-третьих, заменяя скалярное произведение между объектами (не совсем) произвольной функцией от пары объектов, можно из линейной модели классификации получить нелинейную. Это один из самых красивых математических трюков во всём машинном обучении. Наконец, заменяя общепринятую L2 регуляризацию более экзотическими регуляризаторами, можно наделить SVM свойством отбора признаков. Интересный общий вывод: в линейных моделях негладкость функции потерь приводит к отбору объектов.
5. Многомерная линейная регрессия (А.Ю.Фонарев)
Классический способ обучения линейной модели регрессии – это метод наименьших квадратов. Сингулярное разложение матрицы признаковых описаний объектов позволяет изящно записать классическое решение МНК. Мультиколлинеарность или скрытые линейные зависимости между признаками приводит к неустойчивости решения и переобучению. Гребневая регрессия с помощью L2-регуляризации делает решение немного смещённым, но намного более устойчивым. Сингулярное разложение и в этом случае позволяет записать решение. Более того, оно позволяет эффективно оптимизировать параметр регуляризации. Метод LASSO или L1-регуляризация решает проблему мультиколлинеарности по-другому – отбрасывая лишние признаки. Третье решение – линейный переход от большого числа исходных признаков к малому числу новых признаков, но так, чтобы исходные по новым можно было восстановить как можно точнее. Это приводит к методу главных компонент, который оказывается обобщением всё того же сингулярного разложения.
Что делать, если модель регрессии не линейная или функция потерь не квадратичная? Общий рецепт такой: применение метода Ньютона-Рафсона приводит к итерационному процессу, на каждом шаге которого решается задача линейной регрессии. Смысл её сводится к тому, чтобы поточнее настроиться на тех объектах, на которых модель в текущем её приближении работает недостаточно хорошо. В этот общий сценарий неплохо вписывается серия важных частных случаев. Нелинейная регрессия с квадратичной функцией потерь. Логистическая регрессия. Обобщённая линейная модель (GLM), в которой прогнозируемая величина описывается экспоненциальным семейством распределений. Логистическая регрессия является частным случаем GLM, и, благодаря этому факту, мы теперь понимаем, почему вероятность классов выражается через сигмоиду от дискриминантной функции. В конце немного про неквадратичные функции потерь: метод наименьших модулей, квантильная регрессия, робастная регрессия и SVM-регрессия.
7. Прогнозирование временных рядов
Прогнозирование временных рядов – это специальный случай задачи регрессии, в которой объекты выборки линейно упорядочены по времени. Обучающая выборка находится в прошлом, тестовая – в будущем. В простых задачах из области эконометрики поведение временного ряда складывается из медленно меняющегося тренда, сезонной квазипериодичности и различных календарных эффектов. В этих случаях неплохо работают адаптивные методы краткосрочного прогнозирования. Они основаны на рекуррентных формулах, которые выводятся методом наименьших квадратов. Если модель временного ряда не известна, а временных рядов много, используются методы адаптивной селекции и адаптивного комбинирования моделей. Их точности вполне хватает для решения многих практических задач, а неоспоримым преимуществом является вычислительная эффективность.
Лекция состоит из двух слабо связанных частей. В первой части рассматриваются критерии качества классификации, от простейшего «числа ошибок» до правдоподобия, AUC и PR-AUC. Каждый из них имеет свои границы применимости и противопоказания. От них мы переходим к критериям, характеризующим обобщающую способность моделей. От скользящего контроля до разного рода штрафов за сложность модели: AIC, BIC, VC-bound и прочие. Во второй части рассматривается задача отбора признаков, имеющая экспоненциальную вычислительную сложность, и эвристические методы сокращения полного перебора. Жадные алгоритмы. Поиск в глубину и в ширину. Эволюционные алгоритмы. Случайный поиск с адаптацией.
9. Логические методы классификации
Логическая закономерность в задаче классификации – это предикат с простой интерпретируемой формулой, выделяющий много объектов одного класса и мало объектов всех остальных классов. Самый распространённый вид предикатов – конъюнкции небольшого числа пороговых условий на признаки. Алгоритмы поиска информативных конъюнкций очень похожи на алгоритмы отбора признаков из предыдущей лекции. Специальный вариант – методы индукции решающих деревьев. Недостаток деревьев в том, что они не устойчивы к составу обучающей выборки и ошибкам в данных. Справиться с переобучением деревьев помогает процедура усечения (pruning) либо ансамблирование – разного рода решающие леса, в том числе очень известный метод случайного леса.
10. Поиск ассоциативных правил
Специальный случай поиска логических закономерностей в форме правил «если выполняется конъюнкция признаков X, то выполняется также конъюнкция признаков Y». Это обучение без учителя, поскольку целевой признак-класс изначально не задан для объектов. Задача пришла из анализа рыночных корзин в конце 90х годов, но быстро нашла массу применений в других областях. Есть простой классический алгоритм APriori, но на больших данных он не эффективен. Большая часть лекции посвящена алгоритму FP-growth, основанному на построении очень эффективной структуры данных – префиксного дерева, позволяющего сохранить в оперативной памяти полную информацию о всех часто встречающихся наборах признаков за один линейный проход по всем объектам выборки.
Восстановление плотности распределения по выборке – важный класс задач машинного обучения. В частности, к ним сводится построение байесовского классификатора. Рассматриваются три подхода к восстановлению плотности. Самый простой – непараметрический, это оценка плотности Парзена-Розенблатта. Классическим считается параметрический подход, и мы рассматриваем его подробно на примере восстановления плотности многомерного нормального распределения. Третий подход – восстановление смеси вероятностных распределений. Познакомимся с ЕМ-алгоритмом в общем виде и в одном частном случае, когда компонентами смеси являются сферические гауссианы. В байесовском классификаторе это приводит к конструкции, одновременно похожей на метод потенциальных функций, SVM с гауссовским ядром и двухслойную нейронную сеть с радиальными базисными функциями.
12. Кластеризация и частичное обучение
Задача кластеризации – это обучение без учителя. Требуется разбить конечное множество объектов на кластеры по их взаимной близости. Если для части объектов, обычно очень небольшой, классификации всё же известны, то это задача с частичным обучением. Самый известный метод кластеризации – k-средних, если внимательно присмотреться, является сильно упрощённым вариантом ЕМ-алгоритма для разделения смеси сферических гауссиан. Метод DBSCAN более удобен в тех задачах, где нельзя делать предположение о сферичности кластеров. Если требуется иерархически объединять мелкие кластеры в более крупные, используется алгоритм Ланса-Уильямса. Все методы кластеризации очень легко приспосабливаются для частичного обучения. Есть и противоположный подход – приспосабливать методы классификации с учителем. Кроме простых эвристических методов, существует трансдуктивный SVM и различные подходы на основе регуляризаторов.
13. Нейронные сети и градиентные методы
Любую непрерывную функцию можно приблизить многослойной нейронной сетью с любой заданной точностью. Теоретически, двух слоёв для этого достаточно. На практике для обучения искусственных нейронных сетей чаще всего используется метод BackPropagation – обратное распространение ошибок. Он позволяет эффективно вычислять градиент функции потерь по вектору параметров сети. Чтобы этот метод действительно работал, приходится использовать совокупность эвристик для ускорения сходимости, выбора начального приближения, градиентного шага и регуляризации. Методы разреживания сети позволяют радикально сокращать число нейронов и связей.
14. Нейронные сети глубокого обучения
Современный бум искусственных нейронных сетей обязан своим появлением конкурсу по классификации изображений ImageNet. Свёрточные нейронные сети осуществили прорыв в компьютерном зрении, впервые обеспечив высокое качество распознавания при обучении по большим данным. Свёрточные слои осуществляют обучаемое преобразование сырого представления объекта в векторное представление фиксированной размерности, с которым далее работает полносвязная сеть, как правило, из небольшого числа слоёв. Для обработки сигналов и текстов используются рекуррентные нейронные сети, для которых есть свой вариант метода BackPropagation. Одна из самых известных рекуррентных сетей – LSTM, а также её упрощённый вариант GRU. Вкратце рассматриваются важнейшие нейросетевые техники – автокодировщики, перенос обучения, самостоятельное обучение, генеративные состязательные сети.
15. Линейные композиции, бустинг
Композиционные методы машинного обучения дают положительный конструктивный ответ на вопрос, возможно ли из большого числа ненадёжных алгоритмов построить один надёжный. Алгоритм AdaBoost строит последовательность алгоритмов так, чтобы каждый следующий стремился исправлять ошибки предыдущих. В AdaBoost используется экспоненциальная аппроксимация пороговой функции потерь и дискретно-значные базовые классификаторы. Градиентный бустинг обобщает эту идею и позволяет использовать произвольную функцию потерь и вещественно-значные базовые алгоритмы. С помощью градиентного бустинга можно решать задачи регрессии и ранжирования. Алгоритмы MatrixNet и CatBoost, разработанные в Яндексе, представляют собой градиентный бустинг над решающими деревьями специального вида.
16. Композиции классификаторов, часть 2
Бэггинг похож на бустинг, но использует простое голосование вместо взвешенного, бутстрепинг объектов обучающей выборки вместо их перевзвешивания, независимое параллельное построение базовых алгоритмов вместо строго последовательного. По критерию качества бустинг, бэггинг и случайные леса, как правило, сопоставимы. Во многих приложениях базовые алгоритмы проще обучать на отдельных частях признакового пространства, называемых областями компетенции. Такие методы похожи на восстановление смеси распределений и используют ЕМ-подобные алгоритмы для поочерёдной оптимизации базовых алгоритмов и их областей компетенции.
Задача ранжирования отличается от классификации и регрессии тем, что вместо правильных ответов на объектах обучающей выборке задаётся отношение частичного порядка. Модель ранжирования – это функция от объекта (как и в задаче регрессии), с помощью которой можно отранжировать произвольное множество объектов. Задачи ранжирования решаются в информационно-поисковых, рекламных и рекомендательных системах. Критерии качества ранжирования весьма разнообразны, наиболее важные из них рассматриваются в лекции. Методы обучения ранжированию делятся на три большие группы: поточеченые, попарные и списочные. Поточечные являются незначительными модификациями методов классификации или регрессии. Попарные оптимизируют критерии, представляющие собой сумму по парам объектов, а не по отдельным объектам. Для оптимизации часто используется метод стохастического градиента. Списочные методы приближённо оптимизируют качество ранжирования в списках поисковой выдачи.
Имеются транзакционные данные о предпочтениях объектов клиентами. Требуется для заданного клиента спрогнозировать, какие объекты для него наиболее предпочтительны. Простые и уже устаревшие методы коллаборативной фильтрации основаны на поиске схожих клиентов, которые предпочитают схожие множества объектов. Более современные методы основаны на поиске латентных векторов интересов клиентов и объектов. Для этого используются методы матричных разложений. Качество рекомендаций измеряется многими критериями: это не только точность предсказания известных предпочтений, но и разнообразие, новизна, покрытие, догадливость. Кроме того, рекомендательная система должна обеспечивать адекватность рекомендаций даже в условиях «холодного старта», когда по объекту или по клиенту не хватает информации о предпочтениях.
19. Тематическое моделирование
Имеется коллекция текстовых документов. Требуется выявить тематическую кластерную структуру коллекции и оценить, к каким темам относится каждый документ, и какими словами описывается каждая тема. Как и в рекомендательных системах, задача сводится к построению низкорангового неотрицательного матричного разложения. Данная задача является многокритериальной и некорректно поставленной, поскольку имеет бесконечное множество решений. Для нахождения устойчивого решения вводятся дополнительные критерии-регуляризаторы и используется регуляризованный ЕМ-алгоритм. В лекции рассматриваются регуляризаторы для учёта дополнительной информации, ограничений и требований к тематической модели.
Процесс обучения представляется в виде игры агента со средой, в которой агент совершает действия, среда в ответ даёт премии, и агент должен корректировать свою стратегию принятия решений таким образом, чтобы максимизировать суммарную будущую премию. Задача имеет черты классификации и прогнозирования. В простейшем случае это задача выбора действия по накопленной статистике премий, называемая задачей о многоруком бандите. В более сложном случае на каждом шаге известно, в каком из состояний находится среда. Если состояние среды описывается вектором признаков, то для принятия решений возможно приспособить инкрементные методы классификации, а для оптимизации стратегии агента применять градиентные методы. Во всех случаях основным вопросом обучения с подкреплением остаётся компромисс «exploration-exploitation» между изучающими действиями и действиями, непосредственно нацеленными на получение премий.
Активное обучение используется в тех случаях, когда получение ответа от учителя стоит дорого, но есть возможность выбирать, какой объект предъявить учителю следующим. Активное обучение позволяет сокращать объём обучающей выборки по сравнению с пассивным случайным выбором. Для сэмплирования объектов используются различные стратегии: по неуверенности, по ожидаемому изменению модели, по ожидаемому сокращению ошибки, по уменьшению дисперсии параметров модели. Как и в обучении с подкреплением, здесь также имеется компромисс «exploration-exploitation» и методы для введения изучающих действий.
В заключительной лекции даётся беглый обзор курса, выделяются многочисленные сходства и взаимосвязи между различными методами машинного обучения, обсуждаются идеи разнообразных гибридных подходов.