Регуляризация — различия между версиями
(→Лапласовский регуляризатор) |
(→Лапласовский регуляризатор) |
||
Строка 110: | Строка 110: | ||
===Лапласовский регуляризатор=== | ===Лапласовский регуляризатор=== | ||
− | Пусть вектор <tex>\beta</tex> имеет распределение Лапласа<ref>[https://ru.wikipedia.org/wiki/Распределение_Лапласа Распределение Лапласа]</ref>, все его компоненты независимы и имеют равные дисперсии: | + | Пусть вектор <tex>\beta</tex> имеет ''распределение Лапласа''<ref>[https://ru.wikipedia.org/wiki/Распределение_Лапласа Распределение Лапласа]</ref>, все его компоненты независимы и имеют равные дисперсии: |
:<tex>\beta \sim Laplace(0, C)</tex> | :<tex>\beta \sim Laplace(0, C)</tex> | ||
Тогда: | Тогда: |
Версия 10:32, 21 января 2020
Определение: |
Регуляризация (англ. regularization) в статистике, машинном обучении, теории обратных задач — метод добавления некоторых дополнительных ограничений к условию с целью решить неккоректно поставленную задачу или предотвратить переобучение. Чаще всего эта информация имеет вид штрафа за сложность модели. |
Содержание
Мотивация
Как говорилось ранее, регуляризация полезна для борьбы с переобучением. Если вы выбрали сложную модель, и при этом у вас недостаточно данных, то легко можно получить итоговую модель, которая хорошо описывает обучающую выборку, но не обобщается на тестовую.
На примере линейной регрессии
В качестве наглядного примера можно рассмотреть линейные регрессионные модели. Восстановить зависимость для нескольких точек можно пытаться полиномами разной степени M.
Как можно видеть на Рис 1. представлена зависимость, которая хорошо подходит для описания данных, а на Рис. 2 - модель слишком сильно заточилась под обучающую выборку.
Одним из способов бороться с этим эффектом - использовать регуляризацию, т. е. добавлять некоторый штраф за большие значения коэффициентов у линейной модели. Тем самым мы запретим слишком "резкие" изгибы и ограничим возможность подстраивания модели под данные.
На примере логистической регрессии
Необходимость регуляризации можно увидеть и на другом примере. Представьте, что ваша обучающая выборка была линейно разделима. В таком случае в процессе оптимизации значения весов уйдут в бесконечность и вместо сигмойды получится "ступенька", как представлено на Рис. 3.
Это плохо, ибо мы переобучились на нашу обучающую выборку. Как и в предыдущем примере, побороться с этим можно путем добавлением регуляризации, не дающей весам принимать слишком большие значения.
Основные виды регуляризации
Переобучение в большинстве случаев проявляется в том, что итоговые модели имеют слишком большие значения параметров. Соответственно, необходимо добавить в целевую функцию штраф за это. Наиболее часто используемые виды регуляризации -
и , а также их линейная комбинация - эластичная сеть.В представленных ниже формулах для эмпирического риска модели алгоритмов.
: является функцией потерь, а - вектором параметров элемента-регуляризация
Определение: |
| -регуляризация, или регуляризация Тихонова (англ. ridge regularization или Tikhonov regularization):
Минимизация регуляризованного cоответствующим образом эмпирического риска приводит в данном случае к выбору такого вектора параметров
, которое не слишком сильно отклоняется от нуля. В линейных классификаторах это позволяет избежать проблем мультиколлинеарности и переобучения.-регуляризация
Определение: |
| -регуляризация(англ. lasso regularization), или регуляризация через манхэттенское расстояние:
Данный вид регуляризации также позволяет ограничить значения вектора
. Однако, он также обладает интересным и полезным на практике свойством - обнуляет значения некоторых параметров, что в случае с линейными моделями приводит к отбору признаков.Запишем задачу настройки вектора параметров
:- ,
где
- некоторая ограниченная гладкая функция потерь. Сделаем замену переменных, чтобы функционал стал гладким. Каждой переменной поставим в соответствие две новые неотрицательные переменные:Тогда:
В новых переменных функционал становится гладким, но добавляется ограничения-неравенства:
Для любого
хотя бы одно из ограничений и обращается в равенство, иначе второе слагаемое в можно было бы уменьшить, не изменив первое. Если гиперпараметр устремить к , в какой-то момент ограничений обратятся в равенство. Постепенное увеличение гиперпараметра приводит к увеличению числа таких , для которых , откуда следует, что . Как говорилось ранее, в линейных моделях это означает, что значения -го признака игнорируются, и его можно исключить из модели.Эластичная сеть
Определение: |
Эластичная сеть (англ. elastic net regularization):
|
Приведенная регуляризация использует как
, так и регуляризации, учитывая эффективность обоих методов. Ее полезной особенностью является то, что она создает условия для группового эффекта при высокой корреляции переменных, а не обнуляет некоторые из них, как в случае с -регуляризацией.Вероятностная интерпретация регуляризации
Эквивалентная вероятностная задача
Перед нами стоит задача - минимизировать эмпирический риск:
Вероятностная модель данных дает возможность по-другому взглянуть на задачу. Пусть - является вероятностным пространством. Тогда вместо задана совместная плотность распределение объектов и классов .
Для настройки вектора параметров \beta воспользуемся принципом максимума правдоподобия:
Удобнее рассматривать логарифм правдоподобия:
Можно заключить, что задачи в исходном и вероятностном представлении эквивалентны, если положить:
Принцип максимума совместного правдоподобия данных и модели
Допустим, что наряду с параметрической моделью плотности распределения
имеется еще и априорное распределение в пространстве параметров модели . Чтобы ослабить априорные ограничения, вместо фиксированной функции вводится параметрическое семейство априорных распределений , где - гиперпараметр.Принцип максимума правдоподобия теперь будет записываться по-другому, так как не только появление выборки
, но и появление модели также является случайным. Их совместное появление описывается, согласно формуле условной вероятности, плотностью распределения:Таким образом, приходим к принципу максимума совместного правдоподобия данных и модели:
Функционал
распадается на два слагаемых: логарифм правдоподобия и регуляризатор, не зависящий от данных. Второе слагаемое ограничивает вектор параметров модели, не позволяя ему быть каким угодно.В итоге мы получили, что с байесовской точки зрения многие методы регуляризации соответствуют добавлению некоторых априорных распределений на параметры модели. При этом можно определить распределения, которые соответствуют представленным ранее
и регуляризаторам.Нормальный регуляризатор
Пусть вектор [1], все его компоненты независимы и имеют равные дисперсии:
имеет нормальное распределениеЛогарифмируя, получаем квадратичный регуляризатор:
где
- слагаемое, не зависящее от , которым можно пренебречь, поскольку оно не влияет на решение оптимизационной задачи. В итоге имеем - регуляризатор.Лапласовский регуляризатор
Пусть вектор [2], все его компоненты независимы и имеют равные дисперсии:
имеет распределение ЛапласаТогда:
Распределение Лапласа имеет более острый пик и более тяжёлые «хвосты», по сравнению с нормальным распределением. Его дисперсия равна
.Аналогично случаю с нормальным регуляризатором,
можно опустить и, таким образом, получаем - регуляризатор.Регуляризация в линейной регрессии
В линейной регрессии моделируется линейная зависимость между зависимой и независимой переменной. Таким образом, модель алгоритмов для нее состоит из функций вида:
- $g(x, \beta) = \sum_{j}^n \beta_{j} f_{j}(x)$
В итоге оптимизируемый функционал эмпирического риска выглядит следующим образом:
- $Q(a) = \|F\beta - y\|^2$,
где $F = (f_{x_{i}})_{l \times n}$ - матрица объекты-признаки, $y = (y_{i})_{l \times 1}$ - целевой вектор, $\beta = (\beta_{j})_{n \times 1}$ - вектор параметров. Приравняв нулю производную $Q(\beta)$ по параметру $\beta$, получаем:
- $\beta^* = (F^TF)^{-1}F^Ty$
В итоге, использовав сингулярное разложение для представления F и проведя МНК-аппроксимизацию целевого вектора $y$, имеем выражение для нормы вектора \beta:
- $\|\beta^*\|^2 = \sum_{j=1}^n \frac{1}{\lambda_{j}}(v_{j}^Ty)^2$
К сожалению, могут возникнуть проблемы мультиколлинеарности и переобучения в случае, если ковариационная матрица $\sum = F^T F$ плохо обусловлена. Одним из способов борьбы с этими проблемами является регуляризация.
В статье о [Виды регрессии | видах регрессии]] представлены модификации линейной регресиии с различными регуляризаторами ($L_{1}$ и $L_{2}$) и их отличие. Описание в данном разделе будет похожим, однако здесь будет рассмотрен эффект от добавления регуляризаторов немного детальнее.
Гребневая регрессия
К функционалу $Q$ добавляется $L_{2}$-регуляризатор.
Итоговый минимизируемый функционал с поправкой:
Итоговое выражение для параметра \beta:
Таким образом, перед обращением матрицы к ней добавляется "гребень" - диагональная матрица $\tau I_{n}$. При этом все её собственные значения увеличиваются на $\tau$, а собственные векторы не изменяются. В результате матрица становится хорошо обусловленной, оставаясь в то же время «похожей» на исходную.
Рассмотрим, какой эффект оказывает добавление гребня. Выразим регуляризованное МНК-решение через сингулярное разложение:
- $\beta_{t}^* = (UD^2U^T + \tau I_{n})^{-1}UDV^{T}y=U(D^2+\tau I_{n})^{-1}DV^Ty=\sum_{j=1}^n \frac{\sqrt{\lambda_{j}}}{\lambda_{j} + \tau}u_{j}(v_{j}^Ty)$
Теперь найдём регуляризованную МНК-аппроксимацию целевого вектора y:
- $F \beta_{\tau}^* = VDU^T \beta_{\tau}^* = V diag(\frac{\lambda_{j}}{\lambda_{j} + \tau})V^Ty = \sum_{j=1}^n \frac{\lambda_{j}}{\lambda_{j} + \tau}v_{j}(v_{j}^Ty)$
Как можно видеть, проекции на собственные векторы сокращаются, умножаясь $\frac{\lambda_{j}}{\lambda_{j} + \tau} \in (0, 1)$.
В сравнении с нерегуляризованным случаем, уменьшается и норма вектора $\beta$:
- $\|\beta_{\tau}^*\|^2 = \| D^2(D^2 + \tau I_{n})^{-1}D^{-1}V^{T}y)\|^2 = \sum_{j=1}^n \frac{1}{\lambda_{j} + \tau}(v_{j}^Ty)^2 < \sum_{j=1}^n \frac{1}{\lambda_{j}}(v_{j}^Ty)^2 = \|\beta^*\|^2$
Поэтому данный метод называют также сжатие или сокращение весов.
Из формул видно, что по мере увеличения параметра $\tau$ вектор коэффициентов $\beta_{\tau}^*$ становится всё более устойчивым и жёстко определённым. Фактически, происходит понижение эффективной размерности решения — это второй смысл термина сжатие. Роль размерности играет след проекционной матрицы.
В нерегуляризованном случае:
- $n_{effective} = tr\:F(F^TF)^{-1}F^T = tr(F^TF)^{-1}F^TF = tr\:I_{n} = n$
В случае с гребнем:
- $n_{effective} = tr\:F(F^TF + \tau I_{n})^{-1}F^T = tr\:diag(\frac{\lambda_{j}}{\lambda_{j} + \tau}) = \sum_{j=1}^n \frac{1}{\lambda_{j}} < n$
Лассо регрессия
К функционалу $Q$ добавляется $L_{1}$-регуляризатор.
Итоговый минимизируемый функционал с поправкой:
Запишем систему для этой регрессии в виде минимизации неизменного функционала $Q$ при неравенстве-ограничении:
- $\begin{cases} Q(\beta) = \| F\beta - y \|^2 \rightarrow min_{\beta} \\ \sum_{j=1}^n|\beta_{j}| \leq \chi \\ \end{cases}$
Так как используется $L_{1}$-регуляризатор, коэффициенты $\beta_{j}$ постепенно обнуляются с уменьшением \chi. Происходит отбор признаков, поэтому параметр \chi называют еще селективностью. Параметр \chi "зажимает" вектор коэффициентов \beta, отсюда и название метода - лассо (англ. LASSO, least absolute shrinkage and selection operator).
Сравнение гребниевой и лассо регрессий
Основное различие гребниевой и лассо регрессий заключается в том, что первая может приводить к обращению некоторых независимых переменных в ноль (используется $L_{1}$-регуляризатор), тогда как вторая уменьшает их до значений, близких к нулю (используется $L_{2}$-регуляризатор).
Продублируем наглядный пример из статьи о вариациях регрессии. Рассмотрим для простоты двумерное пространство независимых переменных. В случае лассо-регрессии органичение на коэффициенты представляет собой ромб ( ), в случае ридж-регрессии — круг ( ). Необходимо минимизировать функцию ошибки, но при этом соблюсти ограничения на коэффициенты. С геометрической точки зрения задача состоит в том, чтобы найти точку касания линии, отражающей функцию ошибки с фигурой, отражающей ограничения на . Из Рис. 3 интуитивно понятно, что в случае лассо-регрессии эта точка с большой вероятностью будет находиться на углах ромба, то есть лежать на оси, тогда как в случае ридж-регрессии такое происходит очень редко. Если точка пересечения лежит на оси, один из коэффициентов будет равен нулю, а значит, значение соответствующей независимой переменной не будет учитываться.
Также полезно будет рассмотреть простую модельную задачу. Пусть $l = n$ и матрица объекты-признаки является единичной $F = I$. Тогда МНК-решение дает вектор коэффициентов $\beta$:
- $\beta^* = argmin(\sum_{i=1}^l(\beta_{i} - y_{i})^2)$
- $\beta_{j}^* = y_{j}$
В случае с гребниевой регрессией:
- $\beta_{j}^* = \frac{y_{j}}{1 + \lambda}$
В случае с лассо регрессией:
- $\beta_{j}^* = \begin{cases} y_{j} - \lambda / 2, y_{j} > \lambda / 2 \\ y_{j} + \lambda / 2, y_{j} < -\lambda / 2 \\ 0, |y_{j}| \leq \lambda / 2 \end{cases}$
В итоге на Рис. 4 на графиках с зависимостями $\beta_{j}^*$ от $y_{j}$ можно увидеть описанные ранее особенности данных регуляризованных линейных регрессий.
Регуляризация в алгоритмах
Градиентный спуск
Алгоритм градиентного спуска используют для нахождения аппроксимирующей зависимости, определяя вектор весов , при котором достигается минимум эмпирического риска:
В этом методевыбирается некоторое начальное приближение для вектора весов
, затем запускается итерационный процесс, на каждом шаге которого вектор w изменяется в направлении наиболее быстрого убывания функционала Q - противоположно вектору градиента :- ,
где
- величина шага в направлении антиградиента.Регуляризация - одна из эвристик улучшения градиентных методов обучения. Основным способом уменьшить переобучение является квадратичная регуляризация, называемая также сокращением весов. Чтобы ограничить рост абсолютных значений весов, к минимизируемому функционалу
добавляется штрафное слагаемое:Это приводит к появлению аддитивной поправки в градиенте:
В результате правило обновления весов принимает вид:
Таким образом, вся модификация сводится к появлению неотрицательного множителя
, приводящего к постоянному уменьшению весов.Регуляризация предовтращает паралич, повышает устойчивость весов в случае мультиколлинеарности, повышает обобщающую способность алгоритма и снижает риск переобучения. Однако есть и недостатки - параметр кросс-валидации, что связано с большими вычислительными затратами.
необходимо выбирать с помощьюМетод опорных векторов
Метод опорных векторов используется для задачи бинарной классификации. В нем строится гиперплоскость, разделяющая множества разных классов.
К сожалению, зачастую выборка является линейно неразделимой. В таком случае приходится "ослаблять ограничения", позволяя некоторым объектам попадать на территорию другого класса. Для каждого объекта от отступа отнимается некоторая положительная величина $\xi_i$, но требуется, чтобы введенные поправки были минимальны. В итоге постановка задачи SVM с мягким отступом (англ. soft-margin SVM) выглядит следующим образом: $\begin{cases} \frac{1}{2} \lVert w \rVert^2 + C \sum\limits_{i=1}^\ell \xi_i \to \min\limits_{w, b, \xi} \\ M_i(w, b) \geq 1 - \xi_i, \quad i = 1, \ldots, \ell \\ \xi_i \geq 0, \quad i = 1, \ldots, \ell \\ \end{cases}$
Как показано в соответствующем данному алгоритму разделе, эквивалентной задачей безусловной минимизации является: $Q(w, b) = \frac{1}{2C} \lVert w \rVert^2 + \sum\limits_{i=1}^\ell \left(1 - M_i(w, b)\right)_+ \to \min\limits_{w, b}$
В силу неравенства $[M_{i} < 0] \leq (1 - M_{i})_{+}$, функционал $Q(w, b)$ можно рассматривать как верхнюю оценку эмпирического риска, к которому добавлен регуляризатор $\frac{1}{2C} \|w\|^2$.
С введением регуляризатора устраняется проблема мультиколлинеарности, повышается устойчивость алгоритма, улучшается его обобщающая способность.
В результате получаем, что принцип оптимальной разделяющей гиперплоскости или максимизации ширины разделяющей полосы в случае неразделимой выборки тесно связан с $L_{2}$-регуляризацией, которая возникает естественным образом из постановки задачи.
Другие использования регуляризации
Логистическая регрессия
Как было показано в мотивационном примере, для логистической регрессии полезно использовать регуляризацию.
Для настройки вектора коэффициентов $\beta$ по обучающей выборке $X^l$ максимизируют логарифм правдоподобия:
- $L(\beta, X^l) = log_{2}\prod_{i=1}^lp(x_{i}, y_{i}) \rightarrow max_{w}$
- $L(\beta, X^l) = \sum_{i=1}^{l}log_{2}\sigma(\langle \beta, x_{i} \rangle y_{i}) + const(w) \rightarrow max_{w}$
$L_{2}$-регуляризация:
- $L(\beta, X^l) = \sum_{i=1}^{l}log_{2}\sigma(\langle \beta, x_{i} \rangle y_{i}) - \lambda \| \beta \|^2 + const(w) \rightarrow max_{w}$
$L_{1}$-регуляризация:
- $L(\beta, X^l) = \sum_{i=1}^{l}log_{2}\sigma(\langle \beta, x_{i} \rangle y_{i}) - \lambda \|\beta \|_{1} + const(w) \rightarrow max_{w}$
Аналогично можно использовать и другие регуляризаторы.
Нейронные сети
Регуляризация также используется и в нейронных сетях для борьбы со слишком большими весами сети и переобучением. Однако, в этом случае зануление коэффициентов при использовании $L_{1}$-регуляризатора не несет в себе смысл "отбора признаков", как в случае с линейными моделями. Регуляризация не снижает число параметров и не упрощает структуру сети.
Для нейронной сети помимо добавления "штрафного" слагаемого к эмпирическому риску используют и другой метод регуляризации - прореживание сети, в ходе которого упрощают сеть, руководствуясь правилом - если функция ошибки не изменяется, то сеть можно упрощать и дальше. Подробнее об этом можно почитать в статье, рассказывающей о практике реализации нейронных сетей.
См. также
- Переобучение
- Модель алгоритма и её выбор
- Байесовская классификация
- Вариации регрессии
- Линейная регрессия
- Логистическая регрессия
- Стохастический градиентный спуск
- Метод опорных векторов (SVM)
- Нейронные сети, перцептрон
- Практики реализации нейронных сетей
Примечания
Источники информации
- Воронцов К.В. — Математические методы обучения по прецедентам
- Википедия — Регуляризация (математика)
- coursea.org — Регуляризация
- machinelearning.ru — L1-регуляризация линейной регрессии
- medium.com — 5 видов регрессии и их свойства
- Wikipedia — Elastic net regularization
- Keng B. — A Probabilistic Interpretation of Regularization