Изменения

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

На Рис . 1. представлена зависимость, которая хорошо подходит для описания данных, а на Рис. 2 {{---}} модель, слишком сильно заточенная под обучающую выборку.

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

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

В представленных ниже формулах для эмпирического риска <tex>Q</tex>: <tex>\mathcal{L}</tex> является функцией потерь, а <tex>\beta</tex> {{---}} вектором параметров элемента <tex>g(x, \beta)</tex> из [[Модель алгоритма и ее выбор | модели алгоритмовалгоритма]], а <tex>\lambda</tex> {{---}} неотрицательный гиперпараметр, являющийся коэффициентом регуляризации.

<tex>L_{1}</tex>-регуляризация(англ. ''lasso regularization''), или регуляризация через [[Метрический классификатор и метод ближайших соседей#Использование различных метрик расстояния | манхэттенское расстояние]]:

:<tex>\begin{cases} u_{j}=\fracdfrac{1}{2}(|\beta_{j}| + \beta_{j}) \\ v_{j}=\fracdfrac{1}{2}(|\beta_{j}| - \beta_{j}) \end{cases} </tex>

:<tex>\begin{cases} Q(u, v) = \sum\limits_{i=1}^l\mathcal{L}_{i}(u - v) + \lambda \sum\limits_{j=1}^n(u_{j} + v_{j}) \rightarrow min_\min\limits_{u,v} \\ u_{j} \geq 0, v_{j} \geq 0, \: j=1,...\ldots,n\end{cases} </tex>Для любого <tex>j</tex> хотя бы одно из ограничений <tex>u_{j} \geq 􏰧00</tex> и <tex>v_{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_{j} = v_{j} = 0</tex>, откуда следует, что <tex>\beta_{j} = 0</tex>. Как говорилось ранее, в линейных моделях это означает, что значения <tex>j</tex>-го признака игнорируются, и его можно исключить из модели.

:<tex>Q(\beta, X^l)=\sum\limits_{Ii=1}^l\mathcal{L}(y_{i}, g(x_{i}, \beta))+\lambda_{1} \sum\limits_{j=1}^n{|\beta_{j}|}+\lambda_{2} \sum\limits_{j=1}^n{\beta_{j}}^{2}</tex>.

:<tex>Q(\beta, X^l)=\sum\limits _{i=1}^l\mathcal{L}(y_{i}, g(x_{i}, \beta)) \rightarrow min_\min\limits_{\beta}</tex>

:<tex>p(X^l|\beta)=\prod\limits_{i=1}^lp(x_{i},y_{i}|\beta) \rightarrow max_\max\limits_{\beta}</tex>

:<tex>L(\beta, X^l)=\ln p(X^l|\beta)=\sum\limits_{i=1}^l \ln p(x_{i}, y_{i}|\beta) \rightarrow max_\max\limits_{\beta}</tex>

:<tex>L_{\gamma}(\beta, X^l)=\ln p(X^l, \beta;\gamma)=\sum\limits_{i=1}^l \ln p(x_{i}, y_{i}|\beta) + \ln p(\beta; \gamma) \rightarrow max_\max\limits_{\beta}</tex>

:<tex>\ln p(\beta; \sigma) = \ln \left(\fracdfrac{1}{(2 \pi \sigma)^{n/2}} \exp\left(- \fracdfrac{\| \beta \| ^ 2}{2 \sigma}\right)\right) = - \fracdfrac{1}{2 \sigma}\| \beta \| ^ 2 + const(\beta),</tex>

:<tex>\ln p(\beta; C) = \ln \left(\fracdfrac{1}{(2C)^n} \exp\left(- \fracdfrac{\| \beta \|_{1}}{C}\right)\right) = - \fracdfrac{1}{C}\| \beta \|_{1} + const(\beta), \| \beta \|_{1} = \sum\limits_{j}|\beta_{j}|</tex>Аналогично случаю с нормальным регуляризатором, <tex>const(\beta)</tex> можно опустить и, таким образом, получаем <tex>L_{1}</tex> -регуляризатор. Распределение Лапласа имеет более острый пик и более тяжёлые «хвосты», по сравнению с нормальным распределением, как можно видеть на Рис. 4. Его дисперсия Дисперсия Лапласовского распределения равна <tex>2C^2</tex>.

Аналогично случаю с нормальным регуляризатором, <tex>const(\beta)</tex> можно опустить и, таким образом, получаем <tex>L_{1}</tex> |align="center" |-регуляризаторvalign="top" |[[Файл:laplace_and_normal.png|400px|thumb|Рис. 4. Сравнение нормального и Лапласовского распределений при одинаковых математических ожиданиях и дисперсиях.]] |}

В [[Линейная регрессия | линейной регрессии]] моделируется линейная зависимость между зависимой и независимой переменной. Таким образомКаждому объекту $x \in X^l$ соответствует признаковое описание $(f_{1}(x), модель \dots,f_{n}(x))$, где $f_{j}:X \rightarrow \mathbb{R}$ {{---}} числовые признаки. Модель алгоритмов для нее линейной регрессии состоит из функций вида::$g(x, \beta) = \sum\limits_{j}^n \beta_{j} \,f_{j}(x)$

где $F = (f_{j}(x_{i}))_{l \times n}$ {{---}} матрица объекты-признаки, $y = (y_{i})_{l \times 1}$ {{---}} целевой вектор, $\beta = (\beta_{j})_{n \times 1}$ {{---}} вектор параметров.

:$\|\beta^*\|^2 = \sum\limits_{j=1}^n \fracdfrac{1}{\lambda_{j}}(v_{j}^Ty)^2$

В статье о [[Виды Вариации регрессии | видах вариациях регрессии]] представлены модификации линейной регресиии с различными регуляризаторами ($L_{1}$ и $L_{2}$) и их отличие. Описание в данном разделе будет похожим, однако здесь будет рассмотрен эффект от добавления регуляризаторов немного подробнее.

К В [[Вариации регрессии#Гребневая регрессия (ридж-регрессия) | гребневой регрессии]] к функционалу $Q$ добавляется $L_{2}$-регуляризатор.

:$\beta_{t}^* = (UD^2U^T + \tau I_{n})^{-1}UDV^{T}y=U(D^2+\tau I_{n})^{-1}DV^Ty=\sum\limits_{j=1}^n \fracdfrac{\sqrt{\lambda_{j}}}{\lambda_{j} + \tau}u_{j}(v_{j}^Ty)$

:$F \beta_{\tau}^* = VDU^T \beta_{\tau}^* = V diag\left(\fracdfrac{\lambda_{j}}{\lambda_{j} + \tau}\right)V^Ty = \sum\limits_{j=1}^n \fracdfrac{\lambda_{j}}{\lambda_{j} + \tau}v_{j}(v_{j}^Ty)$Как можно видеть, проекции на собственные векторы сокращаются, умножаясь $\fracdfrac{\lambda_{j}}{\lambda_{j} + \tau} \in (0, 1)$.

:$\|\beta_{\tau}^*\|^2 = \| D^2(D^2 + \tau I_{n})^{-1}D^{-1}V^{T}y)\|^2 = \sum\limits_{j=1}^n \fracdfrac{1}{\lambda_{j} + \tau}(v_{j}^Ty)^2 < \sum\limits_{j=1}^n \fracdfrac{1}{\lambda_{j}}(v_{j}^Ty)^2 = \|\beta^*\|^2$

:$n_{effective} = tr\:F(F^TF + \tau I_{n})^{-1}F^T = tr\:diag\left(\fracdfrac{\lambda_{j}}{\lambda_{j} + \tau}\right) = \sum\limits_{j=1}^n \fracdfrac{1}{\lambda_{j}} < n$

К В [[Вариации регрессии#Лассо-регрессия | лассо регрессии]] к функционалу $Q$ добавляется $L_{1}$-регуляризатор.

:$\begin{cases} Q(\beta) = \| F\beta - y \|^2 \rightarrow min_\min\limits_{\beta} \\ \sum\limits_{j=1}^n|\beta_{j}| \leq \chi \\ \end{cases}$

Продублируем наглядный пример из статьи о [[Вариации регрессии | вариациях регрессии]]. Рассмотрим для простоты двумерное пространство независимых переменных. В случае лассо регрессии органичение на коэффициенты представляет собой ромб (<tex>|\beta_1| + |\beta_2| \leq t</tex>), в случае гребневой регрессии {{---}} круг (<tex>\beta_1^2 + \beta_2^2 \leq t^2</tex>). Необходимо минимизировать функцию ошибки, но при этом соблюсти ограничения на коэффициенты. С геометрической точки зрения задача состоит в том, чтобы найти точку касания линии, отражающей функцию ошибки с фигурой, отражающей ограничения на <tex>\beta</tex>. Из Рис. 3 5 интуитивно понятно, что в случае лассо регрессии эта точка с большой вероятностью будет находиться на углах ромба, то есть лежать на оси, тогда как в случае гребневой регрессии такое происходит очень редко. Если точка пересечения лежит на оси, один из коэффициентов будет равен нулю, а значит, значение соответствующей независимой переменной не будет учитываться.

|[[Файл: Ridge_and_Lasso_RegressionRidge_and_Lasso.png|400px|thumb|Рис.35. Сравнение лассо (слева) и гребневой и лассо (справа) регрессий, пример для двумерного пространства независимых переменных.<br/>Бирюзовые области изображают ограничения на коэффициенты <tex>\beta</tex>, эллипсы {{---}} некоторые значения функции наименьшей квадратичной ошибки.]]

:$\beta^* = argmin\left(\sum\limits_{i=1}^l(\beta_{i} - y_{i})^2\right)$

:$\beta_{j}^* = \fracdfrac{y_{j}}{1 + \lambda}$

В итоге на Рис. 4 6 на графиках с зависимостями $\beta_{j}^*$ от $y_{j}$ можно увидеть описанные ранее особенности данных регуляризованных линейных регрессий.

|[[Файл: regularization_comparing.png|400px|thumb|Рис.46. Сравнение лассо и гребневой и лассо регрессий, пример для с простой модельной задачи.]]

Алгоритм [[Стохастический градиентный спуск | градиентного спуска]] используют для нахождения аппроксимирующей зависимости, определяя вектор весов <tex>w \in \mathbb{R}^n</tex>, при котором достигается минимум эмпирического риска::<tex>Q(w, X^l)=\sum\limits_{i=1}^l\mathcal{L}(y_{i}, \langle w, x_{i} \rangle) \rightarrow min_\min\limits_{w}</tex>

<tex>Q'(w)=(\fracdfrac{\partial Q^(w)}{\partial w_{j}})_{j=1}^n</tex>:

:<tex>Q_{\tau}(w) = Q(w) + \fracdfrac{\tau}{2}\|w\|^2</tex>

:<tex>Q′τ Q_{\tau}'(w) = Q′(w) + \tauw</tex>

\fracdfrac{1}{2} \lVert w \rVert^2 + C \sum\limits_{i=1}^l \xi_i \to \min\limits_{w, b, \xi} \\

$Q(w, b) = \fracdfrac{1}{2C} \lVert w \rVert^2 + \sum\limits_{i=1}^l \left(1 - M_i(w, b)\right)_+ \to \min\limits_{w, b}$

В силу неравенства $[M_{i} < 0] \leq (1 - M_{i})_{+}$, функционал $Q(w, b)$ можно рассматривать как верхнюю оценку эмпирического риска, к которому добавлен регуляризатор $\fracdfrac{1}{2C} \|w\|^2$.

:$\fracdfrac{1}{2}\sum\limits_{i=1}^l\left(\ln w_{i} + \fracdfrac{\lambda_{i}^2}{w_{i}}\right)$

:$L(\beta, X^l) = log_{2}\prod\limits_{i=1}^lp(x_{i}, y_{i}) \rightarrow max_\max\limits_{\beta}$:$L(\beta, X^l) = \sum\limits_{i=1}^{l}log_{2}\sigma(\langle \beta, x_{i} \rangle y_{i}) + const(\beta) \rightarrow max_\max\limits_{\beta}$

:$L(\beta, X^l) = \sum\limits_{i=1}^{l}log_{2}\sigma(\langle \beta, x_{i} \rangle y_{i}) - \lambda \| \beta \|^2 + const(\beta) \rightarrow max_\max\limits_{\beta}$

:$L(\beta, X^l) = \sum\limits_{i=1}^{l}log_{2}\sigma(\langle \beta, x_{i} \rangle y_{i}) - \lambda \|\beta \|_{1} + const(\beta) \rightarrow max_\max\limits_{\beta}$

Регуляризация также используется и в [[Нейронные сети, перцептрон | нейронных сетях]] для борьбы со слишком большими весами сети и переобучением. Однако, в этом случае зануление коэффициентов при использовании $L_{1}$-регуляризатора не несет в себе смысл "отбора признаков", как в случае с линейными моделями. Регуляризация К сожалению, регуляризация не снижает число параметров и не упрощает структуру сети.

Для нейронной сети помимо добавления штрафного слагаемого к эмпирическому риску активно используют и другой метод регуляризации борьбы с переобучением {{---}} ''прореживание сети'' (англ. ''dropout''), в ходе которого упрощают сеть, руководствуясь правилом {{---}} если функция ошибки не изменяется, то сеть можно упрощать и дальше. Подробнее об этом можно почитать в статье, рассказывающей о [[Практики реализации нейронных сетей | практике реализации нейронных сетей]].