Введение

В этом параграфе мы разберёмся, какие модели называются линейными, почему они работают и в каких случаях их стоит использовать.

Так как это первый класс моделей, с которым вы столкнётесь, мы постараемся подробно проговорить все важные моменты. Заодно объясним на сравнительно простых примерах, как работает машинное обучение.

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

Представьте другую ситуацию: у вас есть данные геологоразведки, по которым вы хотели бы оценить перспективы разных месторождений. В этом случае по набору геологических данных ваша модель будет, к примеру, оценивать потенциальную годовую доходность шахты. Это пример задачи регрессии.

Числа, которым мы хотим соотнести объекты из нашего множества, иногда называют таргетами (англ. target). Таким образом, задачи классификации и регрессии можно сформулировать как поиск отображения из множества объектов в множество возможных таргетов.

Математическое описание

Математически задачи можно описать так:

• классификация: , где — номера классов;

• регрессия: .

Очевидно, что просто соотносить какие-то объекты с какими-то числами — дело довольно бессмысленное. Мы же хотим быстро обнаруживать мошенников или принимать решение, где строить шахту. Значит, нам нужен какой-то критерий качества.

Мы бы хотели найти такое отображение, которое лучше всего приближает истинное соответствие между объектами и таргетами. Что значит «лучше всего» — вопрос сложный. Мы к нему будем много раз возвращаться.

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

Весь этот параграф будет посвящён самому простому такому семейству — линейным функциям вида:

где:

• — целевая переменная (таргет);
• — вектор, соответствующий объекту выборки (вектор признаков);
• — параметры модели.

Признаки ещё называют фичами (англ. features). Вектор часто называют вектором весов, так как на предсказание модели можно смотреть как на взвешенную сумму признаков объекта, а число — свободным коэффициентом, или сдвигом (англ. bias).

Более компактно линейную модель можно записать в виде:

Теперь, когда мы выбрали семейство функций, в котором будем искать решение, задача стала существенно проще. Мы теперь ищем не какое-то абстрактное отображение, а конкретный вектор .

Замечание. Чтобы применять линейную модель, нужно, чтобы каждый объект уже был представлен вектором численных признаков . Конечно, просто текст или граф в линейную модель не положить, придётся сначала придумать для него численные фичи. Модель называют линейной, если она является линейной по этим численным признакам.

Разберёмся, как будет работать такая модель в случае, если . То есть у наших объектов есть ровно один численный признак, по которому они отличаются. Теперь наша линейная модель будет выглядеть совсем просто: . Для задачи регрессии мы теперь пытаемся приблизить значение какой-то линейной функцией от переменной .

А что будет значить линейность для задачи классификации? Давайте вспомним про пример с поиском мошеннических транзакций по картам.

Допустим, нам известна ровно одна численная переменная — объём транзакции. Для бинарной классификации транзакций на законные и потенциально мошеннические мы будем искать так называемое разделяющее правило: там, где значение функции положительно, мы будем предсказывать один класс, где отрицательно — другой. В нашем примере простейшим правилом будет какое-то пороговое значение объёма транзакций, после которого есть смысл пометить транзакцию как подозрительную.

В случае более высоких размерностей вместо прямой будет гиперплоскость с аналогичным смыслом.

Вопрос на подумать. Если вы посмотрите содержание хендбука, то не найдёте в нём ни полиномиальных моделей, ни каких-нибудь логарифмических, хотя, казалось бы, зависимости бывают довольно сложными. Почему так?

Вопрос на подумать. А как быть, если одна из фич категориальная, то есть принимает значения из (обычно конечного числа) значений, не являющихся числами? Например, это может быть время года, уровень образования, марка машины и так далее. Как правило, с такими значениями невозможно производить арифметические операции или же результаты их применения не имеют смысла.

Помимо простоты, у линейных моделей есть несколько других достоинств.

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

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

То есть если вы построили линейную модель, вы неплохо можете объяснить заказчику те или иные её результаты. Это качество моделей называют интерпретируемостью. Оно особенно ценится в индустриальных задачах, цена ошибки в которых высока.

Если от работы вашей модели может зависеть жизнь человека, то очень важно понимать, как модель принимает те или иные решения и какими принципами руководствуется. При этом не все методы машинного обучения хорошо интерпретируемы.

К примеру, поведение искусственных нейронных сетей или градиентного бустинга интерпретировать довольно сложно.

В то же время слепо доверять весам линейных моделей тоже не стоит по целому ряду причин.

Во-первых, линейные модели — всё-таки довольно узкий класс функций. Они неплохо работают для небольших датасетов и простых задач.

Однако если вы решаете линейной моделью более сложную задачу, то вам, скорее всего, придётся выдумывать дополнительные признаки, которые будут сложными функциями от исходных. Поиск дополнительных признаков называется feature engineering. Технически он устроен примерно так, как мы описали в вопросе про сложные модели. Вот только поиском таких искусственных фич можно сильно увлечься, так что осмысленность интерпретации будет сильно зависеть от здравого смысла эксперта, строившего модель.

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

В-третьих, особенно осторожно стоит верить в утверждения вида «Этот коэффициент маленький, значит, этот признак не важен».

• Всё зависит от масштаба признака: вдруг коэффициент мал, чтобы скомпенсировать его.
• Зависимость действительно может быть слабой, но кто знает, в какой ситуации она окажется важна.

Такие решения принимаются на основе данных, например путём проверки статистического критерия, — об этом мы коротко упомянем в разделе про вероятностные модели.

В-четвёртых, конкретные значения весов могут меняться в зависимости от обучающей выборки, хотя с ростом её размера они будут потихоньку сходиться к весам «наилучшей» линейной модели, которую можно было бы построить по всем-всем-всем данным на свете.

Обсудив немного общие свойства линейных моделей, перейдём к тому, как их всё-таки обучать. Сначала разберёмся с регрессией, а затем настанет черёд классификации.

Линейная регрессия и метод наименьших квадратов (МНК)

Мы начнём с использования линейных моделей для решения задачи регрессии. Простейший пример постановки задачи линейной регрессии — метод наименьших квадратов (англ. ordinary least squares).

Пусть у нас задан датасет ,

где:

• — вектор значений целевой переменной;
• — матрица «объекты — признаки», в которой -я строка представляет вектор признаков -го объекта выборки.

Мы хотим моделировать зависимость от как линейную функцию со свободным членом.

Общий вид такой функции из в выглядит следующим образом:

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

Поскольку это сильно упрощает запись, в дальнейшем будем считать, что это уже сделано и зависимость имеет вид .

Сведение к задаче оптимизации

Мы хотим, чтобы на нашем датасете — то есть на парах из обучающей выборки — функция как можно лучше приближала нашу зависимость.

Для того, чтобы чётко сформулировать задачу, нам осталось только одно: на математическом языке выразить желание приблизить к .

Говоря простым языком, мы должны научиться измерять качество модели и минимизировать её ошибку, как-то меняя обучаемые параметры. В нашем примере обучаемые параметры — это веса .

Функция, оценивающая то, как часто модель ошибается, традиционно называется функцией потерь, функционалом качества или просто лоссом (англ. loss function). Важно, чтобы её было легко оптимизировать: скажем, гладкая функция потерь — это хорошо, а кусочно постоянная — просто ужасно.

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

Интуитивно понятно, что для нашей текущей задачи нам нужно взять вектор и вектор предсказаний модели и как-то сравнить, насколько они похожи. Так как эти векторы «живут» в одном векторном пространстве, расстояние между ними вполне может быть функцией потерь. Более того, положительная непрерывная функция от этого расстояния тоже подойдёт в качестве функции потерь. При этом способов задать расстояние между векторами тоже довольно много.

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

Во-первых, как мы увидим дальше, так задачу будет нетрудно решить, а во-вторых, у этого лосса есть ещё несколько дополнительных свойств:

• -норма разницы — это евклидово расстояние между вектором таргетов и вектором ответов модели, то есть мы их приближаем в смысле самого простого и понятного «расстояния».

• Как мы увидим в разделе про вероятностные модели, с точки зрения статистики это соответствует гипотезе о том, что наши данные состоят из линейного «сигнала» и нормально распределённого «шума».

Так вот, наша функция потерь выглядит так:

Такой функционал ошибки не очень хорош для сравнения поведения моделей на выборках разного размера.

Представьте, что вы хотите понять, насколько качество модели на тестовой выборке из объектов хуже, чем на обучающей из объектов. Вы измерили -норму ошибки и получили в одном случае , а в другом — . Эти числа не очень интерпретируемы. Гораздо лучше посмотреть на среднеквадратичное отклонение: по этой метрике на тестовой выборке получим , а на обучающей — .

Функция потерь называется среднеквадратическим отклонением (англ. Mean Squared Error, MSE). Разница с -нормой чисто косметическая, на алгоритм решения задачи не влияет:

В самом широком смысле функции работают с объектами множеств: берут какой-то входящий объект из одного множества и выдают на выходе соответствующий ему объект из другого.

Если мы имеем дело с линейным отображением из векторного пространства в поле , то такое отображение называют (линейным) функционалом.

Если вы посмотрите на нашу функцию потерь, то увидите, что это именно функционал. Для каждой конкретной линейной функции, которую задают веса , мы получаем число, которое оценивает, насколько точно эта функция приближает наши значения . Чем меньше это число, тем точнее наше решение, а значит, для того, чтобы найти лучшую модель, этот функционал нам надо минимизировать по :

Эту задачу можно решать разными способами. В этом параграфе мы сначала решим её аналитически, а потом приближенно. Сравнение двух этих решений позволит нам проиллюстрировать преимущества того подхода, которому посвящена эта книга. На наш взгляд, это самый простой способ на пальцах показать суть машинного обучения.

МНК: точный аналитический метод

Точку минимума можно найти разными способами. Если вам интересно аналитическое решение, вы можете найти его в параграфе про матричные дифференцирования. Здесь же мы воспользуемся геометрическим подходом.

Пусть — столбцы матрицы , то есть столбцы признаков. Тогда

и задачу регрессии можно сформулировать следующим образом: найти линейную комбинацию столбцов , которая наилучшим способом приближает столбец по евклидовой норме, — то есть найти проекцию вектора на подпространство, образованное векторами .

Разложим , где — та самая проекция, а — ортогональная составляющая, то есть .

Как это можно выразить в матричном виде? Оказывается, очень просто:

В самом деле, каждый элемент столбца — это скалярное произведение строки (столбца = одного из ) на . Из уравнения уже очень легко выразить :

Вопрос на подумать. Для вычисления нам приходится обращать (квадратную) матрицу , что возможно, только если она невырождена. Что это значит с точки зрения анализа данных? Почему мы верим, что это выполняется во всех разумных ситуациях?

Вычислительная сложность аналитического решения — , где — длина выборки, — число признаков у одного объекта. Слагаемое отвечает за сложность перемножения матриц и , а слагаемое — за сложность обращения их произведения.

Перемножать матрицы и не стоит. Гораздо лучше сначала умножить на и затем полученный вектор на . Так будет быстрее, и, кроме того, не нужно будет хранить матрицу .

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

Проблемы «точного» решения

Заметим, что для получения ответа нам нужно обратить матрицу . Это создаёт множество проблем:

1. Основная проблема в обращении матрицы — это то, что вычислительно обращать большие матрицы — дело сложное, а мы бы хотели работать с датасетами, в которых могут быть миллионы точек.

2. Матрица хоть почти всегда и обратима в разумных задачах машинного обучения, зачастую плохо обусловлена. Между признаками, особенно если их много, может появляться приближённая линейная зависимость, которую мы можем упустить на этапе формулирования задачи. В подобных случаях погрешность нахождения будет зависеть от квадрата числа обусловленности матрицы , что очень плохо. Это делает полученное таким образом решение численно неустойчивым: малые возмущения могут приводить к катастрофическим изменениям .

Полностью вылечить проблемы мы не сможем, но никто и не обязывает нас останавливаться на «точном» решении (которое всё равно никогда не будет вполне точным). Поэтому ниже мы познакомим вас с совершенно другим методом.

МНК: приближенный численный метод

Минимизируемый функционал является гладким и выпуклым, а это значит, что можно эффективно искать точку его минимума с помощью итеративных градиентных методов. Более подробно вы можете прочитать о них в разделе про методы оптимизации, а здесь мы лишь коротко расскажем об одном самом базовом подходе.

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

где — это параметр алгоритма («темп обучения»), который контролирует величину шага в направлении антиградиента. Описанный алгоритм называется градиентным спуском.

Градиентный спуск для функции потерь будет вычисляться как:

Следовательно, стартовав из какого-то начального приближения, мы можем итеративно уменьшать значение функции, пока не сойдёмся (по крайней мере, в теории) к минимуму.

Для произвольных функций это может быть локальный минимум, однако в ML мы стараемся строить именно выпуклые функции потерь (MSE также является выпуклой), а в таком случае теория гарантирует нам сходимость к глобальному минимуму.

Алгоритм градиентного спуска

1w = random_normal()             # можно пробовать и другие виды инициализации
2repeat S times:                 # другой вариант: while abs(err) > tolerance
3   f = X.dot(w)                 # посчитать предсказание
4   err = f - y                  # посчитать ошибку
5   grad = 2 * X.T.dot(err) / N  # посчитать градиент
6   w -= alpha * grad            # обновить веса

С теоретическими результатами о скорости и гарантиях сходимости градиентного спуска вы можете познакомиться в параграфе про методы оптимизации. Мы позволим себе лишь несколько общих замечаний:

• Поскольку задача выпуклая, выбор начальной точки влияет на скорость сходимости, но не настолько сильно, чтобы на практике нельзя было стартовать всегда из нуля или из любой другой приятной вам точки.

• Число обусловленности матрицы существенно влияет на скорость сходимости градиентного спуска: чем более вытянуты эллипсоиды уровня функции потерь, тем хуже.

• Темп обучения тоже сильно влияет на поведение градиентного спуска. Вообще, он является гиперпараметром алгоритма, и его, возможно, придётся подбирать отдельно. Другими гиперпараметрами являются максимальное число итераций и/или порог .

  Вычислительная сложность градиентного спуска — , где, как и выше, — длина выборки, — число признаков у одного объекта. Сравните с оценкой для «наивного» вычисления аналитического решения.

  Сложность по памяти — на хранение выборки. В памяти мы держим и выборку, и градиент, но в большинстве реалистичных сценариев доминирует выборка.

Подробнее о влиянии темпа обучения

Рассмотрим три задачи регрессии, для которых матрица имеет соответственно маленькое, среднее и большое числа обусловленности. Будем строить для них модели вида .

Раскрасим плоскость в соответствии со значениями . Тёмная область содержит минимум этой функции — оптимальное значение .

Запустим из двух точек градиентный спуск с разными значениями темпа обучения и посмотрим, что получится.

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

Итог: при неудачном выборе алгоритм не сходится или идёт вразнос, а для плохо обусловленной задачи он сходится абы куда.

Стохастический градиентный спуск

На каждом шаге градиентного спуска нам требуется выполнить потенциально дорогую операцию вычисления градиента по всей выборке (сложность ). Возникает идея заменить градиент его оценкой на подвыборке. Такую подвыборку обычно именуют батч (англ. batch) или мини-батч (англ. mini-batch).

Если функция потерь имеет вид суммы по отдельным парам «объект — таргет»:

а градиент, соответственно, записывается в виде

то предлагается брать оценку

для некоторого подмножества этих пар .

Обратите внимание на множители перед суммами. Почему они нужны? Полный градиент можно воспринимать как среднее градиентов по всем объектам, то есть как оценку матожидания . Тогда оценка матожидания по меньшей подвыборке тоже будет иметь вид среднего градиентов по объектам этой подвыборки.

Как делить выборку на батчи? Ясно, что можно было бы случайным образом семплировать их из полного датасета, но даже если использовать быстрый алгоритм вроде резервуарного семплирования, сложность этой операции может получиться излишне высокой. Поэтому используют линейный проход по выборке, которую перед этим лучше всё-таки случайным образом перемешать.

Давайте введём ещё один параметр нашего алгоритма: размер батча . Теперь на очередном батче размера вычислим градиент и обновим веса модели. При этом вместо количества шагов алгоритма обычно задают количество эпох . Это ещё один гиперпараметр. Одна эпоха — это один полный проход нашего семплера по выборке. Заметим, что если выборка очень большая, а модель компактная, то даже первый проход бывает можно не заканчивать.

Алгоритм

1w = normal(0, 1)
2repeat E times:
3  for i = B, i <= n, i += B
4     X_batch = X[i-B : i]
5     y_batch = y[i-B : i]
6     f = X_batch.dot(w)                 # посчитать предсказание
7     err = f - y_batch                  # посчитать ошибку
8     grad = 2 * X_batch.T.dot(err) / B  # посчитать градиент
9     w -= alpha * grad

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

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

Заметим, впрочем, что при этом лучше бы взять побольше: чтение с диска — более затратная по времени операция, чем чтение из оперативной памяти.

В целом разницу между алгоритмами можно представлять как-то так:

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

По крайней мере, сходимость можно получить при хорошо подобранных коэффициентах темпа обучения в случае выпуклого функционала качества. Подробнее об этом мы поговорим в параграфе про оптимизацию.

Для сложных моделей и лоссов стохастический градиентный спуск может сходиться плохо или застревать в локальных минимумах, поэтому придумано множество его улучшений. О некоторых из них мы рассказали в параграфе про оптимизацию.

Существует определённая терминологическая путаница: иногда стохастическим градиентным спуском называют версию алгоритма, в которой размер батча равен единице (то есть максимально шумную и быструю версию алгоритма), а версии с бо́льшим размером батча называют batch gradient descent. В книгах, которые, возможно, старше вас, такая процедура иногда ещё называется инкрементальным градиентным спуском. Это не очень принципиально, но вы будьте готовы, если что.

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

Неградиентные методы

После прочтения этой главы у вас может сложиться ощущение, что приближённые способы решения ML-задач и градиентные методы — это одно и то же, но вы будете правы в этом только на 98%.

В принципе, существуют и другие способы численно решать эти задачи, но в общем случае они работают гораздо хуже, чем градиентный спуск, и не обладают таким хорошим теоретическим обоснованием.

Мы не будем рассказывать про них подробно, но можете на досуге почитать, скажем, про пошаговую регрессию (англ. Stepwise regression), Orthogonal matching pursuit или метод наименьших углов (англ. least angle regression, LARS). У LARS, кстати, есть довольно интересное свойство: он может эффективно работать на выборках, в которых число признаков больше числа примеров.

Регуляризация

Всегда ли решение задачи регрессии единственно? Вообще говоря, нет. Так, если в выборке два признака будут линейно зависимы (и, следовательно, ранг матрицы будет меньше ), то гарантированно найдётся такой вектор весов , что .

В этом случае если какой-то является решением оптимизационной задачи, то и тоже является решением для любого . То есть решение не только не обязано быть уникальным, так ещё и может быть сколь угодно большим по модулю.

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

Конечно, в жизни редко бывает так, что признаки строго линейно зависимы, а вот приближённо линейно зависимыми они вполне могут быть. Такая ситуация называется мультиколлинеарностью. В этом случае у нас также возникают проблемы, близкие к описанным выше.

Дело в том, что для вектора , состоящего из коэффициентов приближённой линейной зависимости, и, соответственно, , то есть матрица снова будет близка к вырожденной. Как и любая симметричная матрица, она диагонализуется в некотором ортонормированном базисе, и некоторые из собственных значений близки к нулю.

Если вектор в выражении будет близким к соответствующему собственному вектору, то он будет умножаться на , что опять же приведёт к появлению у очень больших по модулю компонент (при этом ещё и будет вычислен с большой погрешностью из-за деления на маленькое число).

И, конечно же, все ошибки и весь шум, которые имелись в матрице , при вычислении будут умножаться на эти большие и неточные числа и возрастать во много-много раз, что приведёт к проблемам, от которых нас не спасёт никакое сингулярное разложение.

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

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

Вместо исходной задачи теперь предлагается решить такую:

Здесь — это один из двух вариантов:

или

Добавка называется регуляризационным членом или регуляризатором, а число — коэффициентом регуляризации.

Коэффициент является гиперпараметром модели и достаточно сильно влияет на качество итогового решения. Его подбирают по логарифмической шкале (скажем, от до ), используя для сравнения моделей с разными значениями дополнительную валидационную выборку. При этом качество модели с подобранным коэффициентом регуляризации уже проверяют на тестовой выборке, чтобы исключить переобучение. Более подробно о том, как нужно подбирать гиперпараметры, вы можете почитать в соответствующем параграфе.

Договоримся, что вес , соответствующий отступу от начала координат (то есть признаку из всех единичек), мы регуляризовать не будем, потому что это не имеет смысла: если даже все значения равномерно велики, это не должно портить качество обучения. Обычно это не отображают в формулах, но если придираться к деталям, то стоило бы написать сумму по всем весам, кроме :

В случае -регуляризации решение задачи изменяется не очень сильно. Продифференцировав новый лосс по , легко получить, что «точное» решение имеет вид

За этой формулой стоит и понятная численная интуиция: раз матрица близка к вырожденной, то обращать её — сродни самоубийству.

Мы лучше слегка исказим её добавкой , которая увеличит все собственные значения на , отодвинув их от нуля. Да, аналитическое решение перестаёт быть «точным», но за счёт снижения численных проблем мы получим более качественное решение, чем при использовании «точной» формулы.

В свою очередь, градиент функции потерь

по весам теперь выглядит так:

Подставив этот градиент в алгоритм стохастического градиентного спуска, мы получаем обновлённую версию приближенного алгоритма, отличающуюся от старой только наличием дополнительного слагаемого.

Вопрос на подумать. Рассмотрим стохастический градиентный спуск для -регуляризованной линейной регрессии с батчами размера . Выберите правильный вариант шага SGD:

(а) ;

(б) ;

(в) .

Вопрос на подумать. Распишите процедуру стохастического градиентного спуска для -регуляризованной линейной регрессии. Как вам кажется, почему никого не волнует, что функция потерь, строго говоря, не дифференцируема?

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

или

Разреживание весов в -регуляризации

-регуляризация работает прекрасно и используется в большинстве случаев, но есть одна полезная особенность регуляризации : её применение приводит к тому, что у признаков, которые не оказывают большого влияния на ответ, вес в результате оптимизации получается равным .

Это позволяет удобным образом удалять признаки, слабо влияющие на таргет. Кроме того, это даёт возможность автоматически избавляться от признаков, которые участвуют в соотношениях приближённой линейной зависимости, и, соответственно, спасает от проблем, связанных с мультиколлинеарностью, о которых мы писали выше.

Не очень строгим, но довольно интуитивным образом это можно объяснить так.

В точке оптимума линии уровня регуляризационного члена касаются линий уровня основного лосса, потому что, во-первых, и те, и другие выпуклые, а во-вторых, если они пересекаются трансверсально, то существует более оптимальная точка:

Линии уровня -нормы — это -мерные октаэдры. Точки их касания с линиями уровня лосса, скорее всего, лежат на грани размерности, меньшей , то есть как раз в области, где часть координат равна нулю:

Заметим, что данное построение говорит о том, как выглядит оптимальное решение задачи, но ничего не говорит о способе, которым это решение можно найти. На самом деле найти такой оптимум непросто: у -меры довольно плохая производная. Однако способы есть. Можете на досуге прочитать, например, статью о том, как работало предсказание CTR в Google в 2012 году. Кроме того, рекомендуем посмотреть про проксимальные методы в главе хендбука про оптимизацию в ML.

Заметим также, что вообще-то оптимизация любой нормы , приведёт к появлению разреженных векторов весов. Просто если с ещё хоть как-то можно работать, то с остальными всё будет ещё сложнее. Хотя говорить о том, что с параметром является нормой, не верно. В данном случае это квазинорма (не выполняется неравенство треугольника), и в пространствах с квазинормой формулировать и решать задачи выпуклой оптимизации не корректно.

Другие лоссы

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

MAE

Средняя абсолютная ошибка (англ. mean absolute error, MAE) появляется при замене -нормы в MSE на :

Можно заметить, что в MAE, по сравнению с MSE, существенно меньший вклад в ошибку будут вносить примеры, сильно удалённые от ответов модели. Так как в MAE мы считаем модуль расстояния, а не квадрат, вклад больших ошибок в MSE получается существенно больше. Поэтому такая функция потерь уместна в случаях, когда вы пытаетесь обучить регрессию на данных с большим количеством выбросов в таргете.

Иначе на эту разницу можно посмотреть так: MSE приближает матожидание условного распределения , а MAE — медиану.

MAPE

Средняя абсолютная процентная ошибка (англ. mean absolute percentage error, MAPE):

Часто используется в задачах прогнозирования (например, погоды, загруженности дорог, кассовых сборов фильмов, цен), когда ответы могут быть различными по порядку величины и при этом мы бы хотели верно угадать порядок, то есть мы не хотим штрафовать модель за предсказание вместо в разы сильней, чем за предсказание вместо .

Вопрос на подумать. Кроме описанных выше, в задаче линейной регрессии можно использовать и другие функции потерь, например функцию потерь Хубера (англ. Huber loss):

Число является гиперпараметром. Сложная формула при нужна, чтобы функция была непрерывной. Попробуйте объяснить, зачем может быть нужна такая функция потерь.

Линейная классификация

Теперь давайте поговорим про задачу классификации. Для начала будем говорить про бинарную классификацию на два класса. Обобщить эту задачу до задачи классификации на классов не составит большого труда.

Пусть теперь наши таргеты кодируют принадлежность к положительному или отрицательному классу, то есть принадлежность множеству , а — по-прежнему векторы из .

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

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

В идеальной ситуации найдётся плоскость, которая разделит классы: положительный окажется с одной стороны от неё, а отрицательный — с другой. Выборка, для которой это возможно, называется линейно разделимой. Увы, в реальной жизни такое встречается крайне редко.

Как обучить линейную модель классификации, нам ещё предстоит понять, но уже ясно, что итоговое предсказание можно будет вычислить по формуле:

Почему бы не решать задачу классификации как задачу регрессии?

Мы можем попробовать предсказывать числа и , минимизируя для этого, например, MSE с последующим взятием знака, но ничего хорошего не получится.

• Во-первых, регрессия почти не штрафует за ошибки на объектах, которые лежат близко к разделяющей плоскости, но не с той стороны.
• Во вторых, ошибкой будет считаться предсказание, например, вместо , хотя нам-то на самом деле не важно, какой у числа модуль, лишь бы знак был правильным.

Если визуализировать такое решение, то проблемы тоже вполне заметны:

Нам нужна прямая, которая разделяет эти точки, а не проходит через них!

Сконструируем теперь функционал ошибки так, чтобы он вышеперечисленными проблемами не обладал. Мы хотим минимизировать число ошибок классификатора, то есть:

Домножим обе части на и немного упростим:

Величина называется отступом (англ. margin) классификатора. Такая функция потерь показывает долю неверно классифицированных объектов и называется misclassification loss. Легко видеть, что:

• отступ положителен, когда , то есть класс угадан верно; при этом чем больше отступ, тем больше расстояние от до разделяющей гиперплоскости, то есть «уверенность классификатора»;

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

От каждого из отступов мы вычисляем функцию:

Она кусочно-постоянная, и из-за этого всю сумму невозможно оптимизировать градиентными методами: ведь её производная равна нулю во всех точках, где она существует.

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

Вопрос на подумать. Допустим, мы как-то обучили классификатор, и подавляющее большинство отступов оказались отрицательными. Действительно ли нас постигла катастрофа?

Вопрос на подумать. Предположим, что у нас есть два классификатора с примерно одинаковыми и достаточно приемлемыми значениями интересующей нас метрики. При этом одна почти всегда выдаёт предсказания с большими по модулю отступами, а вторая — с относительно маленькими. Верно ли, что первая модель лучше, чем вторая?

Ошибка перцептрона

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

Давайте запишем такой лосс с -регуляризацией:

Найдём градиент:

Имея аналитическую формулу для градиента, мы теперь можем так же, как и раньше, применить стохастический градиентный спуск, и задача будет решена.

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

Она решает задачу линейной классификации, но у неё есть одна особенность: её решение не единственно и сильно зависит от начальных параметров. Например, все изображённые ниже классификаторы имеют одинаковый нулевой лосс:

Hinge loss, SVM

Для таких случаев, как на картинке выше, возникает логичное желание не только найти разделяющую прямую, но и постараться провести её на одинаковом удалении от обоих классов, то есть максимизировать минимальный отступ:

Это можно сделать, слегка поменяв функцию ошибки, а именно — положив её равной .

Почему же добавленная единица приводит к желаемому результату?

Интуитивно это можно объяснить так: объекты, которые проклассифицированы правильно, но не очень уверенно (то есть ), продолжают вносить свой вклад в градиент и пытаются «отодвинуть» от себя разделяющую плоскость как можно дальше.

К такому выводу можно прийти и чуть более строго. Для этого надо совершенно по-другому взглянуть на выражение, которое мы минимизируем. Поможет вот эта картинка:

Если мы максимизируем минимальный отступ, то надо максимизировать , то есть ширину полосы при условии того, что большинство объектов лежат с правильной стороны, что эквивалентно решению нашей исходной задачи:

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

Второе слагаемое — это штраф за то, что некоторые объекты неправильно расположены относительно разделительной полосы. В конце концов, никто нам не обещал, что наши классы линейно разделимы и можно провести оптимальную плоскость вообще без ошибок.

Итоговое положение плоскости задаётся всего несколькими обучающими примерами. Это ближайшие к плоскости правильно классифицированные объекты, которые называют опорными векторами (англ. support vectors).

Весь метод, соответственно, зовётся методом опорных векторов (англ. support vector machine, SVM). Начиная с шестидесятых годов это был сильнейший из известных методов машинного обучения. В девяностые его сменили методы, основанные на деревьях решений, которые, в свою очередь, недавно передали пальму первенства нейросетям.

Почему же SVM был столь популярен? Из-за небольшого количества параметров и доказуемой оптимальности.

Сейчас для нас нормально выбирать специальный алгоритм под задачу и подбирать оптимальные гиперпараметры для этого алгоритма перебором.

Но когда-то трава была зеленее, а компьютеры медленнее, и такой роскоши у людей не было. Поэтому им нужны были модели, которые гарантированно неплохо работали бы в любой ситуации. Такой моделью и был SVM.

Другие замечательные свойства SVM: существование уникального решения и доказуемо минимальная склонность к переобучению среди всех популярных классов линейных классификаторов. Кроме того, несложная модификация алгоритма, ядровый SVM, позволяет проводить нелинейные разделяющие поверхности.

Строгий вывод постановки задачи SVM можно прочитать тут или в лекции К.В. Воронцова.

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

В этом параграфе мы будем обозначать классы нулём и единицей.

Ещё один интересный метод появляется из желания посмотреть на классификацию как на задачу предсказания вероятностей.

Хороший пример — предсказание кликов в интернете (например, в рекламе и поиске). Наличие клика в обучающем логе не означает, что, если повторить полностью условия эксперимента, пользователь обязательно кликнет по объекту опять. Скорее, у объектов есть какая-то «кликабельность», то есть истинная вероятность клика по данному объекту.

Клик на каждом обучающем примере является реализацией этой случайной величины, и мы считаем, что в пределе в каждой точке отношение положительных и отрицательных примеров должно сходиться к этой вероятности.

Проблема состоит в том, что вероятность, по определению, — величина от до , а простого способа обучить линейную модель так, чтобы это ограничение соблюдалось, нет.

Из этой ситуации можно выйти так: научить линейную модель правильно предсказывать какой-то объект, связанный с вероятностью, но с диапазоном значений , и преобразовать ответы модели в вероятность. Таким объектом является logit или log odds — логарифм отношения вероятности положительного события к отрицательному .

Если ответом нашей модели является , то искомую вероятность посчитать не трудно:

Функция в правой части называется сигмоидой и обозначается

Таким образом, .

Как теперь научиться оптимизировать так, чтобы модель как можно лучше предсказывала логиты? Нужно применить метод максимума правдоподобия для распределения Бернулли.

Это самое простое распределение, возникающее, к примеру, при бросках монетки, которая орлом выпадает с вероятностью . Только у нас событием будет не орёл, а то, что пользователь кликнул на объект с такой вероятностью. Подробнее про распределение Бернулли можно прочитать в теоретическом минимуме.

Понять, насколько вероятно получить данные значения таргета при данных и весах , позволяет правдоподобие

Для распределения Бернулли его можно выписать следующим образом:

где — это вероятность, посчитанная из ответов модели.

Оптимизировать произведение неудобно, хочется иметь дело с суммой, так что мы перейдём к логарифмическому правдоподобию и подставим формулу для вероятности, которую мы получили выше:

Если заметить, что

то выражение можно переписать проще:

Нас интересует , для которого правдоподобие максимально. Чтобы получить функцию потерь, которую мы будем минимизировать, умножим его на минус один:

В отличие от линейной регрессии, для логистической нет явной формулы решения. Деваться некуда, будем использовать градиентный спуск. К счастью, градиент устроен очень просто:

Предсказание модели будет вычисляться, как мы договаривались, следующим образом:

Это вероятность положительного класса, а как от неё перейти к предсказанию самого класса? В других методах нам достаточно было посчитать знак предсказания, но теперь все наши предсказания положительные и находятся в диапазоне от до . Что же делать?

Интуитивным, но не правильным будет ответ «Взять порог ». Более корректным будет подобрать этот порог отдельно, для уже построенной регрессии, минимизируя нужную вам метрику на отложенной тестовой выборке. Например, сделать так, чтобы доля положительных и отрицательных классов примерно совпадала с реальной.

Отдельно заметим, что метод называется логистической регрессией, а не логистической классификацией именно потому, что предсказываем мы не классы, а вещественные числа — логиты.

Остановитесь и подумайте. Проверьте, что если метки классов — это , а не и , то функцию потерь для логистической регрессии можно записать в более компактном виде:

Вопрос на подумать. Правда ли, что разделяющая поверхность модели логистической регрессии является гиперплоскостью?

Вопрос на подумать. Допустим, что матрица «объекты — признаки» имеет полный ранг по столбцам, то есть все её столбцы линейно независимы. Верно ли, что решение задачи восстановления логистической регрессии единственно?

Вопрос на подумать. На картинке ниже представлены результаты работы на одном и том же датасете трёх моделей логистической регрессии с разными коэффициентами -регуляризации:

Наверху показаны предсказанные вероятности положительного класса, внизу — вид разделяющей поверхности.

Как вам кажется, какие картинки соответствуют самому большому коэффициенту регуляризации, а какие — самому маленькому? Почему?

Многоклассовая классификация

В этом разделе мы будем следовать изложению из лекций Евгения Соколова.

Пусть каждый объект нашей выборки относится к одному из классов: . Чтобы предсказывать эти классы с помощью линейных моделей, нам придётся свести задачу многоклассовой классификации к набору бинарных, которые мы уже хорошо умеем решать.

Мы разберём два самых популярных способа это сделать — «один против всех» (англ. one-vs-all) и «все против всех» (англ. all-vs-all), а проиллюстрировать их нам поможет вот такой игрушечный датасет:

Один против всех

Обучим линейных классификаторов , выдающих оценки принадлежности классам соответственно. В случае с линейными моделями эти классификаторы будут иметь вид

Классификатор с номером будем обучать по выборке . Иными словами, мы учим классификатор отличать -й класс от всех остальных.

Логично, чтобы итоговый классификатор выдавал класс, соответствующий самому уверенному из бинарных алгоритмов. Уверенность можно в каком-то смысле измерить с помощью значений линейных функций:

Давайте посмотрим, что даст этот подход применительно к нашему датасету. Обучим три линейных модели, отличающих один класс от остальных:

Теперь сравним значения линейных функций:

Для каждой точки выберем тот класс, которому соответствует большее значение, то есть самый «уверенный» классификатор:

Хочется сказать, что самый маленький класс «обидели».

Проблема данного подхода заключается в том, что каждый из классификаторов обучается на своей выборке и значения линейных функций , или, проще говоря, «выходы» классификаторов, могут иметь разные масштабы. Из-за этого сравнивать их будет неправильно.

Нормировать вектора весов, чтобы они выдавали ответы в одной и той же шкале, не всегда может быть разумным решением: так, в случае с SVM веса перестанут являться решением задачи, поскольку нормировка изменит норму весов.

Все против всех

Обучим классификаторов .

В случае с линейными моделями эти модели будут иметь вид

Классификатор будем настраивать по подвыборке , содержащей только объекты классов и . Соответственно, классификатор будет выдавать для любого объекта либо класс , либо класс .

Проиллюстрируем это для нашей выборки:

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

Для нашего датасета получается следующая картинка:

Обратите внимание на серый треугольник на стыке областей. Это точки, для которых голоса разделились, — в данном случае каждый классификатор выдал какой-то свой класс, то есть у каждого класса было по одному голосу. Для этих точек нет явного способа выдать обоснованное предсказание.

Многоклассовая логистическая регрессия

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

В логистической регрессии для двух классов мы строили линейную модель

а затем переводили её прогноз в вероятность с помощью сигмоидной функции

Допустим, что мы теперь решаем многоклассовую задачу и построили линейных моделей

каждая из которых даёт оценку принадлежности объекта одному из классов.

Как преобразовать вектор оценок в вероятности? Для этого можно воспользоваться оператором , который производит «нормировку» вектора:

В этом случае вероятность -го класса будет выражаться как

Обучать эти веса предлагается с помощью метода максимального правдоподобия: так же, как и в случае с двухклассовой логистической регрессией:

Масштабируемость линейных моделей

Мы уже обсуждали, что SGD позволяет обучению хорошо масштабироваться по числу объектов, так как мы можем не загружать их целиком в оперативную память.

А что делать, если признаков очень много или мы не знаем заранее, сколько их будет? Такое может быть актуально, например, в следующих ситуациях:

• Классификация текстов: мы можем представить текст в формате «мешка слов», то есть неупорядоченного набора слов, встретившихся в данном тексте, и обучить на нём, например, определение тональности отзыва в интернете. Наличие каждого слова из языка в тексте у нас будет кодироваться отдельной фичей. Тогда размерность каждого элемента обучающей выборки будет порядка нескольких сотен тысяч.

• В задаче предсказания кликов по рекламе можно получить выборку любой размерности, например так: в качестве фичи закодируем индикатор того, что пользователь X побывал на веб-странице Y. Суммарная размерность тогда будет порядка . Кроме того, всё время появляются новые пользователи и веб-страницы, так что на этапе применения нас ждут сюрпризы.

Есть несколько хаков, которые позволяют бороться с такими проблемами:

• Несмотря на то, что полная размерность объекта в выборке огромна, количество ненулевых элементов в нём невелико. Значит, можно использовать разреженное кодирование, то есть вместо плотного вектора хранить словарь, в котором будут перечислены индексы и значения ненулевых элементов вектора.

• Даже хранить все веса не обязательно! Можно хранить их в хеш-таблице и вычислять индекс по формуле hash(feature) % tablesize. Хеш может вычисляться прямо от слова или ID пользователя. Таким образом, несколько фич будут иметь общий вес, который, тем не менее, обучится оптимальным образом. Такой подход называется хешированием признаков (англ. hashing trick). Ясно, что сжатие вектора весов приводит к потерям в качестве, но, как правило, ценой совсем небольших потерь можно сжать этот вектор на много порядков.

Пример открытой библиотеки, в которой реализованы эти возможности, — vowpal wabbit.

Если при решении задачи ставки столь высоки, что мы не можем разменивать качество на сжатие вектора весов, а признаков всё-таки очень много, то задачу можно решать распределённо, храня все признаки в шардированной хеш-таблице:

Кружки здесь означают отдельные серверы. Жёлтые загружают данные, а серые хранят части модели. Для обучения жёлтый кружок запрашивает у серого нужные ему для предсказания веса, считает градиент и отправляет его обратно, где тот потом применяется. Схема обладает бесконечной масштабируемостью, но задач, где это оправдано, не очень много.

Заключение

На линейную модель можно смотреть как на однослойную нейросеть, поэтому многие методы, которые были изначально разработаны для них, сейчас переиспользуются в задачах глубокого обучения, а базовые подходы к регрессии, классификации и оптимизации вообще выглядят абсолютно так же. Поэтому, несмотря на то, что в целом линейные модели на сегодня применяются редко, их компоненты и принципы построения знать очень и очень полезно.

И как видите — решение любой ML-задачи состоит из выбора функции потерь, параметризованного класса моделей и способа оптимизации. Если вы смогли увидеть это, значит, сделали главный вывод после прочтения этого параграфа.

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

Теперь предлагаем вам закрепить изученный материал на практике.

Скачайте ноутбук с лабораторной работой. В нём вы найдёте описания заданий и дополнительные материалы. Задания из лабораторной прикреплены к этому параграфу в виде задач в системе Яндекс Контест. Чтобы проверить себя, отправляйте решения по соответствующим задачам в систему. Успехов в практике!