Урок 1 Знакомство с машинным обучением
 Скачать 1.57 Mb.
|
|
3.1.3. Недообучение и переобучение Таким образом, недообучение — ситуация, когда алгоритм плохо описывает и обучающую выборку, и новые данные. В этом случае алгоритм необходимо усложнять. В случае переобучения, данные из обучающей выборки будут описываться хорошо, а новые данные плохо. Выявить переобучение, используя только обучающую выборку, невозможно, поскольку и хорошо обученный, и переобученный алгоритмы будут хорошо ее описывать. Необходимо использовать дополнительные данные. Существуют несколько подходов к выявлению переобучения: • Отложенная выборка. Часть данных из обучающей выборки не участвуют в обучении, чтобы позже проверять на ней обученный алгоритм. • Кросс-валидация, несколько усложненный метод отложенной выборки. (Об этом способе речь пойдет позже.) 3 • Использовать меры сложности модели. Об этом пойдет речь далее. 3.2. Регуляризация В этом разделе речь пойдет о регуляризации — способе борьбы с переобучением в линейных моделях. 3.2.1. «Симптомы» переобучения. Мультиколлинеарность. Мерой сложности, то есть «симптомом» переобученности модели, являются большие веса при признаках. Например, в предыдущем разделе при обучении модели a(x) = w 0 + w 1 x + w 2 x 2 + ... + w 9 x 9 веса оказывались огромными: a(x) = 0.5 + 12458922x + 43983740x 2 + ... + 2740x 9 Другая ситуация, в которой можно встретиться с переобучением — мультиколлинеарность. Так называется проблема, при которой признаки в выборке являются линейно зависимыми. Другими словами, существуют коэффициенты α 1 , ..., α d такие, что для любого объекта x i из выборки выполняется: α 1 x 1 i + ... + α d x d i = 0. Более компактно последнее выражение можно переписать в виде: hα, x i i = 0. Допустим, было найдено решение задачи оптимизации: w ∗ = argmin w 1 ` ` X i=1 hw, x i i − y i 2 Другой вектор весов, полученный сдвигом в направлении вектора α: w 1 = w ∗ + tα, так как для элементов x выборки выполняется: hw ∗ + tα, xi = hw ∗ , xi + thα, xi = hw ∗ , xi, также будет являться решением задачи оптимизации. Другими словами, он будет также хорошо описывать данные в выборке, как и исходный алгоритм. Фактически, решениями задачи оптимизации являются бес- конечное множество алгоритмов, но многие из них имеют большие веса, и далеко не все обладают хорошей обобщающей способностью. Поэтому здесь тоже легко столкнуться с переобучением. 3.2.2. Регуляризация Выше было продемонстрировано, что если веса в линейной модели большие, существует высокий риск пере- обучения. Чтобы бороться с этим, минимизируется уже не выражение для функционала ошибки Q(a, X), а новый функционал, получаемый прибавлением регуляризатора. Самый простой регуляризатор — квадратич- ный регуляризатор: kwk 2 = d X j=1 w 2 j В этом случае имеет место следующая задача оптимизации: Q(w, X) + λkwk 2 → min w Таким образом, при обучении будет учитываться также то, что не следует слишком сильно увеличивать веса признаков. 4 3.2.3. Коэффициент регуляризации Введенный выше коэффициент λ, который стоит перед регуляризатором, называется коэффициентом регуля- ризации. Чем больше λ, тем ниже сложность модели. Например, при очень больших его значениях оптимально просто занулить все веса. В то же время при слишком низких значениях λ высок риск переобучения, то есть модель становится слишком сложной. Поэтому нужно найти некоторое оптимальное значение λ, достаточно большое, чтобы не допустить пе- реобучения, и не очень большое, чтобы уловить закономерности в данных. Обычно λ подбирается на кросс- валидации, о которой пойдет речь в следующем разделе. 3.2.4. Смысл регуляризации Чтобы понять смысл регуляризации, вместо задачи оптимизации с квадратичным оптимизатором нагляднее рассмотреть задачу условной оптимизации: ( Q(w, X) → min w kwk 2 ≤ C Добавление регуляризатора вводит требование, чтобы решение задачи минимизации искалось в некоторой круглой области с центром в нуле. W 1 W 2 W ∗ Рис. 3.6: Геометрический смысл условной регуляризации. Красная точка — настоящий оптимум функции, красные линии — линии уровня функции, черная точка — оптимум функции при введенном ограничении. Таким образом, решение задачи с регуляризатором не будет характеризоваться слишком большими зна- чениями весовых коэффициентов. 3.2.5. Виды регуляризаторов Рассмотренный выше квадратичный регуляризатор (L 2 -регуляризатор) является гладким и выпуклым, что позволяет использовать градиентный спуск. Также существует L 1 -регуляризатор: kwk 1 = d X j=1 |w j |, который представляет собой L 1 -норму вектора весов. Он уже не является гладким, а также обладает интерес- ным свойством. Если применять такой регуляризатор, некоторые веса оказываются равными нулю. Другими словами, такой регуляризатор производит отбор признаков и позволяет использовать в модели не все при- знаки, а только самые важные из них. 5 3.3. Оценка качества алгоритмов. Кросс-валидация В этом разделе речь пойдет об оценке качества алгоритмов и о том, как понять, как поведет себя алгоритм на новых данных. 3.3.1. Выявление переобучения Уже было сказано, что переобучение сложно выявить, используя только обучающую выборку: и хороший, и переобученный алгоритмы будут показывать хорошее качество на объектах обучающей выборки. Рассмотрен- ные в предыдущем разделе меры переобученности (значения регуляризаторов), безусловно, можно применять, но они не дают ответа на вопрос, насколько хорошо алгоритм поведет себя на новых данных, то есть какая у него будет доля ошибок на новых данных. 3.3.2. Отложенная выборка Самый простой способ оценить качество алгоритма — использование отложенной выборки. В этом случае следует разбить выборку на две части: первая из двух частей будет использоваться для обучения алгоритма, а вторая, тестовая выборка, — для оценки его качества, в том числе для нахождения доли ошибок в задаче классификации, MSE (среднеквадратичной ошибки) в задаче регрессии и других мер качества в зависимости от специфики задачи. Естественный вопрос — о том, в какой пропорции производить разбиение. Если взять тестовую выборку слишком маленькой, оценка качества будет ненадежной, хотя обучающая выборка будет почти совпадать с полной выборкой. В противоположенном случае, если отложенная часть будет большой, оценка качества будет надежной, но низкое качество алгоритма может свидетельствовать о недостаточном объёме первой, обучающей, части выборки. Обычно выборку разбивают в соотношениях 70/30, 80/20 или 0.632/0.368. Преимуществом отложенной выборки является то, что обучать алгоритм приходится всего лишь один раз, но при этом результат сильно зависит от того, как было произведено разбиение. Например, оценивается стоимость жилья по некоторым признакам. И есть особая категория жилья, на- пример двухэтажные квартиры. И если окажется, что все двухэтажные квартиры, которых немного, попали в отложенную выборку, то после обучения алгоритм будет давать на них очень плохое качество, поскольку в обучающей выборке таких объектов не было. Чтобы решить эту проблему, можно использовать следующий подход: построить n различных разбиений выборки на 2 части, для каждого разбиения найти оценку качества, а в качестве итоговой оценки качества работы алгоритма использовать усредненное по всем разбиениям значение. Но и в данном случае, поскольку разбиения строятся случайно, нет никаких гарантий, что особый объект хотя бы раз попадет на обучение. 3.3.3. Кросс-валидация Более системный подход — кросс валидация. В этом случае выборка делится на k блоков примерно одинако- вого размера. Далее по очереди каждый из этих блоков используется в качестве тестового, а все остальные — в качестве обучающей выборки. После того, как каждый блок побывает в качестве тестового, будут получены k показателей качества. В результате усреднения получается оценка качества по кросс-валидации. При этом встает вопрос, какое число блоков использовать. Если блоков мало, получаются надежные, но смещенные оценки. В случае большого числа блоков оценки, наоборот, получаются ненадежными (большой разброс оценок), но несмещенными. Нет конкретных рекомендаций относительно выбора k. Обычно выбирают k = 3, 5, 10. Чем больше k, тем больше раз приходится обучать алгоритм. Поэтому на больших выборках следует выбирать небольшие значения k, так как даже при удалении 1/3 выборки (а она большая) оставшихся данных будет достаточно для обучения. 3.3.4. Совет: перемешивайте данные в выборке Часто данные в файле записаны в отсортированном виде по какого-нибудь признаку. Поэтому всегда следует перемешивать выборку прежде, чем производить кросс-валидацию. В ином случае алгоритм будет показывать плохое качество и причина этого будет не так очевидна. 6 При этом есть задачи, в которых выборку нельзя перемешивать. Это задачи предсказания будущего, например предсказание погоды на следующий день. В этом случае нужно особо следить за тем, как происходит деление выборки. 3.4. Выбор гиперпараметров и сравнение алгоритмов В этом разделе речь пойдет о выборе гиперпараметров и сравнении различных алгоритмов с помощью изу- ченных ранее схем. 3.4.1. Гиперпараметры Гиперпараметрами называются такие параметры алгоритмов, которые не могут быть получены из обучающей выборки при обучении, поэтому их надо подбирать путем многократного обучения алгоритма. Примерами гиперпараметров являются: • Параметр регуляризации λ (при использовании регуляризатора) • Степень полинома в задаче регрессии с семейством алгоритмов, заданным множеством полиномов опре- деленной степени. 3.4.2. Сравнение разных алгоритмов Более общая задача — сравнение разных алгоритмов: • обученных с разными значениями гиперпараметров; • использующих различный способ регуляризации; • настроенных с использованием разного функционала ошибки, например среднеквадратичной ошибки и средней абсолютной ошибки; • которые принадлежат разным классам алгоритмов. При сравнении алгоритмов можно использовать как отложенную выборку, так и кросс-валидацию, но при этом следует соблюдать осторожность. Действительно, пусть 1000 алгоритмов сравниваются по качеству на отложенной выборке. Каждый из 1000 алгоритмов, обученных на обучающей выборке, тестируется на отложенной, и в результате выбирается лучший. Фактически на этом шаге отложенная выборка также становится своего рода обучающей, и возникает проблема переобучения: из большого числа алгоритмов выбирается тот, который лучше всего ведет себя на отложенной выборке, лучше подогнан под нее. 3.4.3. Улучшенная схема сравнения алгоритмов Чтобы бороться с этим, следует использовать несколько усовершенствованную схему оценивания качества алгоритмов, а именно все данные нужно будет делить на 3 части (в случае использования отложенной выбор- ки): обучение, валидация и контроль. Каждый из тысячи алгоритмов будет обучен на обучающей выборке, а его качество будет измерено на валидационной. Алгоритм с наилучшим качеством будет проверен на тестовой выборке, чтобы исключить переобучение и проверить алгоритм на адекватность. По сути именно тестовая выборка будет играть роль новых данных. Если предпочтительно использовать кросс-валидацию, то данные следует разбить на 2 части. Первая из них будет использоваться для обучения алгоритмов и оценки качества с помощью кросс-валидации, после чего лучший алгоритм будет проверен на адекватность на контрольной выборке. 7 Урок 2 Линейные модели 2.1. Линейные модели в задачах регрессии Данный урок будет посвящен линейным моделям. Речь пойдет о задачах классификации и регрессии, как их обучать, и с какими проблемами можно столкнуться при использовании этих моделей. В этом блоке мы обсудим, как выглядят линейные модели в задачах регрессии. 2.1.1. Повторение обозначений из прошлого урока Для начала необходимо напомнить некоторые обозначения, которые были введены на прошлом уроке. • X — пространство объектов • Y — пространство ответов • x = (x 1 , ..., x d ) — признаковое описание объекта • X = (x i , y i ) ` i=1 — обучающая выборка • a(x) — алгоритм, модель • Q(a, X) — функционал ошибки алгоритма a на выборке X • Обучение: a(x) = argmin a∈A Q(a, X) Напомним, что в задаче регрессии пространство ответов Y = R. Чтобы научиться решать задачу регрессии, необходимо задать: • Функционал ошибки Q: способ измерения того, хорошо или плохо работает алгоритм на конкретной выборке. • Семейство алгоритмов A: как выглядит множество алгоритмов, из которых выбирается лучший. • Метод обучения: как именно выбирается лучший алгоритм из семейства алгоритмов. 2.1.2. Пример задачи регрессии: предсказание прибыли магазина Пусть известен один признак — прибыль магазина в прошлом месяце, а предсказать необходимо прибыль магазина в следующем. Поскольку прибыль — вещественная переменная, здесь идет речь о задаче регрессии. Прибыль в прошлом месяце Прибыль в текущем мес яце Рис. 2.1: Точки обучающей выборки. 1 По этому графику можно сделать вывод о существовании зависимости между прибылью в следующем и прошлом месяцах. Если предположить, что зависимость приблизительно линейная, ее можно представить в виде прямой на этом графике. По этой прямой и можно будет предсказывать прибыль в следующем месяце, если известна прибыль в прошлом. В целом такая модель угадывает тенденцию, то есть описывает зависимость между ответом и признаком. При этом, разумеется, она делает это не идеально, с некоторой ошибкой. Истинный ответ на каждом объекте несколько отклоняется от прогноза. Один признак — это не очень серьезно. Гораздо сложнее и интереснее работать с многомерными выбор- ками, которые описываются большим количеством признаков. В этом случае нарисовать выборку и понять, подходит или нет линейная модель, нельзя. Можно лишь оценить ее качество и по нему уже понять, подходит ли эта модель. Следует отметить, что вообще нельзя придумать модель, которая идеально описывает ваши данные, то есть идеально описывает, как порождается ответ по признакам. 2.1.3. Описание линейной модели Далее обсудим, как выглядит семейство алгоритмов в случае с линейными моделями. Линейный алгоритм в задачах регрессии выглядит следующим образом: a(x) = w 0 + d X j=1 w j x j , где w 0 — свободный коэффициент, x j — признаки, а w j — их веса. Если добавить (d + 1)-й признак, который на каждом объекте принимает значение 1, линейный алгоритм можно будет записать в более компактной форме a(x) = d+1 X j=1 w j x j = hw, xi, где используется обозначение hw, xi для скалярного произведения двух векторов. В качестве меры ошибки не может быть выбрано отклонение от прогноза Q(a, y) = a(x) − y, так как в этом случае минимум функционала не будет достигаться при правильном ответе a(x) = y. Самый простой способ — считать модуль отклонения: |a(x) − y|. Но функция модуля не является гладкой функцией, и для оптимизации такого функционала неудобно ис- пользовать градиентные методы. Поэтому в качестве меры ошибки часто выбирается квадрат отклонения: (a(x) − y) 2 Функционал ошибки, именуемый среднеквадратичной ошибкой алгоритма, задается следующим образом: Q(a, x) = 1 ` ` X i=1 (a(x i ) − y i ) 2 В случае линейной модели его можно переписать в виде функции (поскольку теперь Q зависит от вектора, а не от функции) ошибок: Q(w, x) = 1 ` ` X i=1 (hw, x i i − y i ) 2 2.2. Обучение модели линейной регрессии В этом блоке речь пойдет о том, как обучать модель линейной регрессии, то есть как настраивать ее пара- метры. В прошлый раз было введено следующее выражение для качества линейной модели на обучающей выборке: Q(w, x) = 1 ` ` X i=1 (hw, x i i − y i ) 2 → min w Следует напомнить, что в число признаков входит также постоянный признак, равный 1 для всех объектов, что позволяет исключить постоянную составляющую в последнем соотношении. 2 2.2.1. Переход к матричной форме записи Прежде, чем будет рассмотрена задача оптимизации этой функции, имеет смысл переписать используемые соотношения в матричной форме. Матрица «объекты–признаки» X составлена из признаковых описаний всех объектов из обучающей выборки: X = x 11 x 1d x `1 x `d Таким образом, в ij элементе матрицы X записано значение j-го признака на i объекте обучающей выборки. Также понадобится вектор ответов y, который составлен из истинных ответов для всех объектов: y = y 1 y ` В этом случае среднеквадратичная ошибка может быть переписана в матричном виде: Q(w, X) = 1 ` kXw − yk 2 → min w Эта формула пригодится, в частности, при реализации линейной регрессии на компьютере. 2.2.2. Аналитический метод решения Можно найти аналитическое решение задачи минимизации: w ∗ = (X T X) −1 X T y. Основные сложности при нахождении решения таким способом: • Для нахождения решения необходимо вычислять обратную матрицу. Операция обращения матрицы требует, в случае d признаков, выполнение порядка d 3 операции, и является вычислительно сложной уже в задачах с десятком признаков. • Численный способ нахождения обратной матрицы не может быть применен в некоторых случаях (когда матрица плохо обусловлена). 2.2.3. Оптимизационный подход к решению Другой, несколько более удобный, способ найти решение — использовать численные методы оптимизации. Несложно показать, что среднеквадратическая ошибка — это выпуклая и гладкая функция. Выпуклость гарантирует существование лишь одного минимума, а гладкость — существование вектора градиента в каждой точке. Это позволяет использовать метод градиентного спуска. При использовании метода градиентного спуска необходимо указать начальное приближение. Есть много подходов к тому, как это сделать, в том числе инициализировать случайными числами (не очень большими). Самый простой способ это сделать — инициализировать значения всех весов равными нулю: w 0 = 0. На каждой следующей итерации, t = 1, 2, 3, ..., из приближения, полученного в предыдущей итерации w t−1 , вычитается вектор градиента в соответствующей точке w t−1 , умноженный на некоторый коэффициент η t , называемый шагом: w t = w t−1 − η t ∇Q(w t−1 , X). Остановить итерации следует, когда наступает сходимость. Сходимость можно определять по-разному. В дан- ном случае разумно определить сходимость следующим образом: итерации следует завершить, если разница двух последовательных приближений не слишком велика: kw t − w t−1 k < ε. Подробно метод градиентного спуска обсуждался в прошлом курсе этой специализации. 3 |