193
правки
Изменения
→Регуляризация в алгоритмах
Как можно видеть на Рис 1. представлена зависимость, которая хорошо подходит для описания данных, а на Рис. 2 - модель слишком сильно заточилась под обучающую выборку.
Одним из способов бороться с этим эффектом - использовать регуляризацию, т. е. добавлять некоторый штраф за большие значения коэффициентов у линейной модели. Тем самым мы запретим слишком "резкие" изгибы и ограничим возможность подстраивания модели под данные.
===На примере [[Логистическая регрессия | логистической регрессии]]===
==Основные виды регуляризации==
Переобучение в большинстве случаев проявляется в том, что в получающихся многочленах итоговые модели имеют слишком большие коэффициентызначения параметров. Соответственно, необходимо добавить в целевую функцию штраф за слишком большие коэффициентыэто. Наиболее часто используемые виды регуляризации - <tex >L_{1}</tex> и <tex >L_{2}</tex>, а также их линейная комбинация - эластичная сеть. В представленных ниже формулах для эмпирического риска <tex>Q</tex>: <tex>\mathcal{L}</tex> является функцией потерь, а <tex>\beta</tex> - вектором параметров элемента <tex>g(x, \beta)</tex> [[Модель алгоритма и ее выбор | модели алгоритмов]]. ===<tex>L_{2}</tex>-регуляризация==={{Определение|definition=<tex>L_{2}</tex>-регуляризация, или регуляризация Тихонова (англ. ''ridge regularization'' или ''Tikhonov regularization''): :<tex>Q(\beta, X^l)=\sum _{i}^l\mathcal{L}(y_{i}, g(x_{i}, \beta))+\lambda \sum _{j}^n{\beta_{j}}^{2}</tex>.}}Минимизация регуляризованного cоответствующим образом эмпирического риска приводит в данном случае к выбору такого вектора параметров <tex>\beta</tex>, которое не слишком сильно отклоняется от нуля. В линейных классификаторах это позволяет избежать проблем мультиколлинеарности и переобучения.
===<tex>L_{1}</tex>-регуляризация===
{{Определение|definition=<tex>L_{1}</tex>-регуляризация (англ. ''lasso regressionregularization''), или регуляризация через манхэттенское расстояние: :<tex>Q(\beta, X^l)=\sum _{i}^l\mathcal{L}(y_{i}-y, g(t_x_{i}, \beta))}^{2}+\lambda \sum _{ij}^n{|a_\beta_{ij}|}</tex>.}}Данный вид регуляризации также позволяет ограничить значения вектора <tex>\beta</tex>. Однако, он также обладает интересным и полезным на практике свойством - обнуляет значения некоторых параметров, что в случае с линейными моделями приводит к отбору признаков.
Запишем задачу настройки вектора параметров <tex>\beta</tex>::<tex>Q(\beta) =\sum_{i=1}^l\mathcal{L}_{i}(\beta) + \lambda \sum _{j=1}^n{|\beta_{j}|}</tex>L_,где <tex>\mathcal{L}_{2i}(\beta) = \mathcal{L}(y_{i}, g(x_{i}, \beta))</tex>-регуляризациянекоторая ограниченная гладкая функция потерь. Сделаем замену переменных, чтобы функционал стал гладким. Каждой переменной <tex>\beta_{j}</tex> поставим в соответствие две новые неотрицательные переменные::<tex>u_{j}=\frac{1}{2}(|\beta_{j}| + \beta_{j})</tex>:<tex>v_{j}=\frac{1}{2}(|\beta_{j}| - \beta_{j})</tex>Тогда::<tex>\beta_{j} =u_{j} + v_{j}</tex>:<tex>L_|\beta_{j}| = u_{2j} + v_{j}</tex>В новых переменных функционал становится гладким, но добавляется ограничения-регуляризация, или регуляризация Тихонова (англ. ''ridge regression'' или ''Tikhonov regularization'')неравенства: :<tex>Q(u, v) =\sum _sum_{i=1}^l\mathcal{(y_L}_{i}(u -yv) + \lambda \sum_{j=1}^n(t_u_{ij} + v_{j}))\rightarrow min_{u,v}^</tex>:<tex>u_{2j}+\lambda geq 0, v_{j} \sum _geq 0</tex>Для любого <tex>j</tex> хотя бы одно из ограничений <tex>u_{ij}\geq 0</tex> и <tex>v_{a_j} \geq 0</tex> обращается в равенство, иначе второе слагаемое в <tex>Q(u, v)</tex> можно было бы уменьшить, не изменив первое. Если гиперпараметр <tex>\lambda</tex> устремить к <tex>\infty</tex>, в какой-то момент <tex>2n</tex> ограничений обратятся в равенство. Постепенное увеличение гиперпараметра <tex>\lambda</tex> приводит к увеличению числа таких <tex>j</tex>, для которых <tex>u_{ij}= v_{j}^= 0</tex>, откуда следует, что <tex>w_{2j}= 0</tex>. Как говорилось ранее, в линейных моделях это означает, что значения <tex>j</tex>-го признака игнорируются, и его можно исключить из модели.
===Эластичная сеть===
{{Определение
|definition=
Эластичная сеть (англ. ''elastic net regularization''):
:<tex>Q(\beta, X^l)=\sum _{i}^l\mathcal{L}(y_{i}-y, g(t_x_{i}, \beta))}^+\lambda_{21}+\lambda \sum _{ij}^n{|a_\beta_{ij}|}+\lambda lambda_{2} \sum _{ij}{a_\beta_{ij}}^{2}</tex>.}}Приведенная регуляризация использует как <tex>L_{1}</tex>, так и <tex>L_{2}</tex> регуляризации, учитывая эффективность обоих методов. Ее полезной особенностью является то, что она создает условия для группового эффекта при высокой корреляции переменных, а не обнуляет некоторые из них, как в случае с <tex>L_{1}</tex>-регуляризацией.
==Вероятностная интерпретация регуляризации==
===Эквивалентная вероятностная задача===
Перед нами стоит задача - минимизировать эмпирический риск:
:<tex>Q(\beta, X^l)=\sum _{i}^l\mathcal{L}(y_{i}, g(x_{i}, \beta)) \rightarrow min_{\beta}</tex>
[[Байесовская классификация | Вероятностная модель данных]] дает возможность по-другому взглянуть на задачу. Пусть <tex>X \times Y</tex> - является вероятностным пространством. Тогда вместо <tex>g(x_{i}, \beta)</tex> задана совместная плотность распределение объектов и классов <tex>p(x, y|\beta)</tex>.
Для настройки вектора параметров \beta воспользуемся ''принципом максимума правдоподобия'':
:<tex>p(X^l|\beta)=\prod_{i}^lp(x_{i},y_{i}|\beta) \rightarrow max_{\beta}</tex>
Удобнее рассматривать логарифм правдоподобия:
:<tex>L(\beta, X^l)=\ln p(X^l|\beta)=\sum_{i}^l \ln p(x_{i}, y_{i}|\beta) \rightarrow max_{\beta}</tex>
Можно заключить, что задачи в исходном и вероятностном представлении эквивалентны, если положить:
:<tex>-\ln p(x_{i}, y_{i}|\beta)=\mathcal{L}(y_{i}, g(x_{i}, \beta))</tex>
===Принцип максимума совместного правдоподобия данных и модели===
Допустим, что наряду с параметрической моделью плотности распределения <tex>p(x, y|\beta)</tex> имеется еще и ''априорное распределение в пространстве параметров модели'' <tex>p(\beta)</tex>. Чтобы ослабить априорные ограничения, вместо фиксированной функции <tex>p(w)</tex> вводится ''параметрическое семейство априорных распределений'' <tex>p(\beta; \gamma)</tex>, где <tex>\gamma</tex> - гиперпараметр.
Принцип максимума правдоподобия теперь будет записываться по-другому, так как не только появление выборки <tex>X^l</tex>, но и появление модели <tex>\beta</tex> также является случайным. Их совместное появление описывается, согласно формуле условной вероятности, плотностью распределения:
:<tex>p(X^l, \beta; \gamma)=p(X^l|\beta)p(\beta;\gamma)</tex>
Таким образом, приходим к ''принципу максимума совместного правдоподобия данных и модели'':
:<tex>L_{\gamma}(\beta, X^l)=\ln p(X^l, \beta;\gamma)=\sum_{i}^l \ln p(x_{i}, y_{i}|\beta) + \ln p(\beta; \gamma) \rightarrow max_{\beta}</tex>
Функционал <tex>L_{\gamma}</tex> распадается на два слагаемых: логарифм правдоподобия и ''регуляризатор'', не зависящий от данных. Второе слагаемое ограничивает вектор параметров модели, не позволяя ему быть каким угодно.
В итоге мы получили, что с байесовской точки зрения многие методы регуляризации соответствуют добавлению некоторых априорных распределений на параметры модели.
При этом можно определить распределения, которые соответствуют представленным ранее <tex>L_{1}</tex> и <tex>L_{2}</tex> регуляризаторам.
===Нормальный регуляризатор===
Пусть вектор <tex>\beta</tex> имеет ''нормальное распределение'', все его компоненты независимы и имеют равные дисперсии:
:<tex>\beta \sim N(0, \sigma^2)</tex>
Логарифмируя, получаем ''квадратичный регуляризатор'':
:<tex>\ln p(\beta; \sigma) = \ln (\frac{1}{(2 \pi \sigma)^{n/2}} \exp(- \frac{\| \beta \| ^ 2}{2 \sigma})) = - \frac{1}{2 \sigma}\| \beta \| ^ 2 + const(\beta),</tex>
где <tex>const(\beta)</tex> - слагаемое, не зависящее от <tex>\beta</tex>, которым можно пренебречь, поскольку оно не влияет на решение оптимизационной задачи. В итоге имеем <tex>L_{2}</tex> - регуляризатор.
===Лапласовский регуляризатор===
Пусть вектор <tex>\beta</tex> имеет ''распределение Лапласа'', все его компоненты независимы и имеют равные дисперсии:
:<tex>\beta \sim Laplace(0, C)</tex>
Тогда:
:<tex>\ln p(\beta; C) = \ln (\frac{1}{(2C)^n} \exp(- \frac{\| \beta \|_{1}}{C})) = - \frac{1}{C}\| \beta \|_{1} + const(\beta), \| \beta \|_{1} = \sum_{j}|\beta_{j}|</tex>
Распределение Лапласа имеет более острый пик и более тяжёлые «хвосты», по сравнению с нормальным распределением. Его дисперсия равна <tex>2C^2</tex>.
Аналогично случаю с нормальным регуляризатором, <tex>const(\beta)</tex> можно опустить и, таким образом, получаем <tex>L_{1}</tex> - регуляризатор.
==Регуляризация в линейной регрессии==
===Гребневая регрессия===
===Лассо регрессия===
===Сравнение гребниевой и лассо регрессий===
==Регуляризация в алгоритмах==
===Градиентный спуск===
Алгоритм [[Стохастический градиентный спуск | градиентного спуска]] используют для нахождения аппроксимирующей зависимости, определяя вектор весов <tex>w \in R^n</tex>, при котором достигается минимум эмпирического риска:
:<tex>Q(w, X^l)=\sum_{i=1}^l\mathcal{L}(y_{i}, \langle w, x_{i} \rangle) \rightarrow min_{w}</tex>
В этом методевыбирается некоторое начальное приближение для вектора весов <tex>w</tex>, затем запускается итерационный процесс, на каждом шаге которого вектор w изменяется в направлении наиболее быстрого убывания функционала Q - противоположно вектору градиента
<tex>Q'(w)=(\frac{\partial Q^(w)}{\partial w_{j}})_{j=1}^n</tex>:
:<tex>w := w - \eta Q'(w)</tex>,
где <tex>\eta > 0</tex> - величина шага в направлении антиградиента.
'''Регуляризация''' - одна из эвристик улучшения градиентных методов обучения. Основным способом уменьшить переобучение является квадратичная регуляризация, называемая также ''сокращением весов''. Чтобы ограничить рост абсолютных значений весов, к минимизируемому функционалу <tex>Q(w)</tex> добавляется штрафное слагаемое:
:<tex>Q_{\tau}(w) = Q(w) + \frac{\tau}{2}\|w\|^2</tex>
Это приводит к появлению аддитивной поправки в градиенте:
:<tex>Q′τ (w) = Q′(w) + \tau</tex>
В результате правило обновления весов принимает вид:
:<tex>w := w(1 - \eta \tau) - \eta Q'(w)</tex>
Таким образом, вся модификация сводится к появлению неотрицательного множителя <tex>(1 − \eta \tau)</tex>, приводящего к постоянному уменьшению весов.
Регуляризация предовтращает паралич, повышает устойчивость весов в случае мультиколлинеарности, повышает обобщающую способность алгоритма и снижает риск переобучения. Однако есть и недостатки - параметр <tex>\tau</tex> необходимо выбирать с помощью [[Кросс-валидация | кросс-валидации]], что связано с большими вычислительными затратами. ===Метод опорных векторов===[[Метод опорных векторов]] используется для задачи бинарной классификации. В нем строится гиперплоскость, разделяющая множества разных классов. К сожалению, зачастую выборка является линейно неразделимой. В таком случае приходится "ослаблять ограничения", позволяя некоторым объектам попадать на территорию другого класса. Для каждого объекта от отступа отнимается некоторая положительная величина $\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}$-регуляризацией, которая возникает естественным образом из постановки задачи. ==Другие использования регуляризации=====Линейные классификаторы======Логистическая регрессия===
===Нейронные сети===
==См. также=Метод опорных вектоов= ==Примечания== =Стохастический градиентный спуск=Источники информации==
