193
правки
Изменения
Нет описания правки
|definition=
<tex>L_{2}</tex>-регуляризация, или регуляризация Тихонова (англ. ''ridge regularization'' или ''Tikhonov regularization''):
:<tex>Q(\beta, X^l)=\sum\limits_{i=1}^l\mathcal{L}(y_{i}, g(x_{i}, \beta))+\lambda \sum\limits_{j=1}^n{\beta_{j}}^{2}</tex>.
}}
Минимизация регуляризованного cоответствующим образом эмпирического риска приводит в данном случае к выбору такого вектора параметров <tex>\beta</tex>, которое не слишком сильно отклоняется от нуля. В линейных классификаторах это позволяет избежать проблем мультиколлинеарности и переобучения.
|definition=
<tex>L_{1}</tex>-регуляризация(англ. ''lasso regularization''), или регуляризация через манхэттенское расстояние:
:<tex>Q(\beta, X^l)=\sum _\limits_{i=1}^l\mathcal{L}(y_{i}, g(x_{i}, \beta))+\lambda \sum _\limits_{j=1}^n{|\beta_{j}|}</tex>.
}}
Данный вид регуляризации также позволяет ограничить значения вектора <tex>\beta</tex>. Однако, он также обладает интересным и полезным на практике свойством {{---}} обнуляет значения некоторых параметров, что в случае с линейными моделями приводит к отбору признаков.
Запишем задачу настройки вектора параметров <tex>\beta</tex>:
:<tex>Q(\beta) = \sum_sum\limits_{i=1}^l\mathcal{L}_{i}(\beta) + \lambda \sum _\limits_{j=1}^n{|\beta_{j}|}</tex>,
где <tex>\mathcal{L}_{i}(\beta) = \mathcal{L}(y_{i}, g(x_{i}, \beta))</tex> {{---}} некоторая ограниченная гладкая функция потерь. Сделаем замену переменных, чтобы функционал стал гладким. Каждой переменной <tex>\beta_{j}</tex> поставим в соответствие две новые неотрицательные переменные:
:<tex>\begin{cases} u_{j}=\frac{1}{2}(|\beta_{j}| + \beta_{j}) \\ v_{j}=\frac{1}{2}(|\beta_{j}| - \beta_{j}) \end{cases} </tex>
:<tex>\begin{cases} \beta_{j} = u_{j} - v_{j} \\ |\beta_{j}| = u_{j} + v_{j} \end{cases}</tex>
В новых переменных функционал становится гладким, но добавляется ограничения-неравенства:
:<tex>\begin{cases} Q(u, v) = \sum_sum\limits_{i=1}^l\mathcal{L}_{i}(u - v) + \lambda \sum_sum\limits_{j=1}^n(u_{j} + v_{j}) \rightarrow min_{u,v} \\ u_{j} \geq 0, v_{j} \geq 0, \: j=1,...,n\end{cases} </tex>
Для любого <tex>j</tex> хотя бы одно из ограничений <tex>u_{j} \geq 0</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>w_{j} = 0</tex>. Как говорилось ранее, в линейных моделях это означает, что значения <tex>j</tex>-го признака игнорируются, и его можно исключить из модели.
|definition=
Эластичная сеть (англ. ''elastic net regularization''):
:<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}{\beta_{j}}^{2}</tex>.
}}
Приведенная регуляризация использует как <tex>L_{1}</tex>, так и <tex>L_{2}</tex> регуляризации, учитывая эффективность обоих методов. Ее полезной особенностью является то, что она создает условия для группового эффекта при высокой корреляции переменных, а не обнуляет некоторые из них, как в случае с <tex>L_{1}</tex>-регуляризацией.
===Эквивалентная вероятностная задача===
Перед нами стоит задача {{---}} минимизировать эмпирический риск:
:<tex>Q(\beta, X^l)=\sum \limits _{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>.
:<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_sum\limits_{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>L_{\gamma}(\beta, X^l)=\ln p(X^l, \beta;\gamma)=\sum_sum\limits_{i}^l \ln p(x_{i}, y_{i}|\beta) + \ln p(\beta; \gamma) \rightarrow max_{\beta}</tex>
Функционал <tex>L_{\gamma}</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_sum\limits_{j}|\beta_{j}|</tex>
Распределение Лапласа имеет более острый пик и более тяжёлые «хвосты», по сравнению с нормальным распределением. Его дисперсия равна <tex>2C^2</tex>.
==Регуляризация в линейной регрессии==
В [[Линейная регрессия | линейной регрессии]] моделируется линейная зависимость между зависимой и независимой переменной. Таким образом, модель алгоритмов для нее состоит из функций вида:
:$g(x, \beta) = \sum_sum\limits_{j}^n \beta_{j} f_{j}(x)$
В итоге оптимизируемый функционал эмпирического риска выглядит следующим образом:
:$Q(a) = \|F\beta - y\|^2$,
:$\beta^* = (F^TF)^{-1}F^Ty$
В итоге, использовав [[Сингулярное разложение | сингулярное разложение]] для представления $F$ и проведя МНК-аппроксимизацию целевого вектора $y$, имеем выражение для нормы вектора \beta:
:$\|\beta^*\|^2 = \sum_sum\limits_{j=1}^n \frac{1}{\lambda_{j}}(v_{j}^Ty)^2$
К сожалению, могут возникнуть проблемы мультиколлинеарности и переобучения в случае, если ковариационная матрица $\sum = F^T F$ плохо обусловлена. Одним из способов борьбы с этими проблемами является регуляризация.
Рассмотрим, какой эффект оказывает добавление гребня. Выразим регуляризованное МНК-решение через сингулярное разложение:
:$\beta_{t}^* = (UD^2U^T + \tau I_{n})^{-1}UDV^{T}y=U(D^2+\tau I_{n})^{-1}DV^Ty=\sum_sum\limits_{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_sum\limits_{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_sum\limits_{j=1}^n \frac{1}{\lambda_{j} + \tau}(v_{j}^Ty)^2 < \sum_sum\limits_{j=1}^n \frac{1}{\lambda_{j}}(v_{j}^Ty)^2 = \|\beta^*\|^2$
Поэтому данный метод называют также ''сжатие'' или ''сокращение весов''.
В случае с гребнем:
:$n_{effective} = tr\:F(F^TF + \tau I_{n})^{-1}F^T = tr\:diag(\frac{\lambda_{j}}{\lambda_{j} + \tau}) = \sum_sum\limits_{j=1}^n \frac{1}{\lambda_{j}} < n$
===Лассо регрессия===
Запишем систему для этой регрессии в виде минимизации неизменного функционала $Q$ при неравенстве-ограничении:
:$\begin{cases} Q(\beta) = \| F\beta - y \|^2 \rightarrow min_{\beta} \\ \sum_sum\limits_{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 = n$ и матрица объекты-признаки является единичной $F = I$. Тогда МНК-решение дает вектор коэффициентов $\beta$:
:$\beta^* = argmin(\sum_sum\limits_{i=1}^l(\beta_{i} - y_{i})^2)$
:$\beta_{j}^* = y_{j}$
В случае с гребниевой регрессией:
===Градиентный спуск===
Алгоритм [[Стохастический градиентный спуск | градиентного спуска]] используют для нахождения аппроксимирующей зависимости, определяя вектор весов <tex>w \in R^n</tex>, при котором достигается минимум эмпирического риска:
:<tex>Q(w, X^l)=\sum_sum\limits_{i=1}^l\mathcal{L}(y_{i}, \langle w, x_{i} \rangle) \rightarrow min_{w}</tex>
В этом методевыбирается некоторое начальное приближение для вектора весов <tex>w</tex>, затем запускается итерационный процесс, на каждом шаге которого вектор w изменяется в направлении наиболее быстрого убывания функционала Q {{---}} противоположно вектору градиента
Также существуют разновидности SVM с другими регуляризаторами.
* Метод релевантных векторов (англ. ''RVM, Relevance vector Machine''):
:$\frac{1}{2}\sum_sum\limits_{i=1}^l(\ln w_{i} + \frac{\lambda_{i}^2}{w_{i}})$
* Метод опорных векторов с лассо (англ. ''LASSO SVM''):
:$\mu \sum_sum\limits_{i=1}^n|w_{i}|$
* Метод опорных признаков (англ. ''Support feature machine''):
:$\sum_sum\limits_{i=1}^nR_{\mu}(w_{i}), \begin{cases} 2 \mu |w_{i}|, |w_{i}|<\mu \\ \mu^2 + w_{i}^2, |w_{i}| \geq \mu \end{cases}$
==Другие использования регуляризации==
Для настройки вектора коэффициентов $\beta$ по обучающей выборке $X^l$ максимизируют логарифм правдоподобия:
:$L(\beta, X^l) = log_{2}\prod_{i=1}^lp(x_{i}, y_{i}) \rightarrow max_{\beta}$
:$L(\beta, X^l) = \sum_sum\limits_{i=1}^{l}log_{2}\sigma(\langle \beta, x_{i} \rangle y_{i}) + const(\beta) \rightarrow max_{\beta}$
$L_{2}$-регуляризация:
:$L(\beta, X^l) = \sum_sum\limits_{i=1}^{l}log_{2}\sigma(\langle \beta, x_{i} \rangle y_{i}) - \lambda \| \beta \|^2 + const(\beta) \rightarrow max_{\beta}$
$L_{1}$-регуляризация:
:$L(\beta, X^l) = \sum_sum\limits_{i=1}^{l}log_{2}\sigma(\langle \beta, x_{i} \rangle y_{i}) - \lambda \|\beta \|_{1} + const(\beta) \rightarrow max_{\beta}$
Аналогично можно использовать и другие регуляризаторы.
