Регуляризация — различия между версиями
(→Нейронные сети) |
(→Градиентный спуск) |
||
(не показано 48 промежуточных версий этого же участника) | |||
Строка 9: | Строка 9: | ||
===На примере [[Линейная регрессия | линейной регрессии]]=== | ===На примере [[Линейная регрессия | линейной регрессии]]=== | ||
− | В качестве наглядного примера | + | В качестве наглядного примера рассмотрим линейные регрессионные модели. |
− | Восстановить зависимость для нескольких точек можно пытаться полиномами разной степени M. | + | Восстановить зависимость для нескольких точек можно пытаться полиномами разной степени $M$. |
{|align="center" | {|align="center" | ||
Строка 18: | Строка 18: | ||
|} | |} | ||
− | + | На Рис 1. представлена зависимость, которая хорошо подходит для описания данных, а на Рис. 2 {{---}} модель, слишком сильно заточенная под обучающую выборку. | |
− | + | Однин из способов бороться с негативным эффектом излишнего подстраивания под данные {{---}} использование регуляризации, т. е. добавление некоторого штрафа за большие значения коэффициентов у линейной модели. Тем самым запрещаются слишком "резкие" изгибы и предотвращается переобучение. | |
===На примере [[Логистическая регрессия | логистической регрессии]]=== | ===На примере [[Логистическая регрессия | логистической регрессии]]=== | ||
− | Необходимость регуляризации можно увидеть и на другом примере. Представьте, что ваша обучающая выборка была линейно разделима. В таком случае в процессе оптимизации значения весов уйдут в бесконечность и вместо сигмойды получится "ступенька", | + | Необходимость регуляризации можно увидеть и на другом примере {{---}} при использовании логистической регресии. Представьте, что ваша обучающая выборка была линейно разделима. В таком случае в процессе оптимизации значения весов модели уйдут в бесконечность, и вместо сигмойды получится "ступенька", представленная на Рис. 3. |
{|align="center" | {|align="center" | ||
Строка 31: | Строка 31: | ||
|} | |} | ||
− | Это плохо, ибо | + | Это плохо, ибо произошло затачивание под обучающую выборку. Как и в предыдущем примере, побороться с этим можно путем добавлением регуляризатора, не дающего весам принимать слишком большие значения. |
==Основные виды регуляризации== | ==Основные виды регуляризации== | ||
Строка 42: | Строка 42: | ||
|definition= | |definition= | ||
<tex>L_{2}</tex>-регуляризация, или регуляризация Тихонова (англ. ''ridge regularization'' или ''Tikhonov regularization''): | <tex>L_{2}</tex>-регуляризация, или регуляризация Тихонова (англ. ''ridge regularization'' или ''Tikhonov regularization''): | ||
− | :<tex>Q(\beta, X^l)=\sum | + | :<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оответствующим образом эмпирического риска приводит | + | Минимизация регуляризованного cоответствующим образом эмпирического риска приводит к выбору такого вектора параметров <tex>\beta</tex>, которое не слишком сильно отклоняется от нуля. В линейных классификаторах это позволяет избежать проблем мультиколлинеарности и переобучения. |
===<tex>L_{1}</tex>-регуляризация=== | ===<tex>L_{1}</tex>-регуляризация=== | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | <tex>L_{1}</tex>-регуляризация(англ. ''lasso regularization''), или регуляризация через манхэттенское расстояние: | + | <tex>L_{1}</tex>-регуляризация (англ. ''lasso regularization''), или регуляризация через манхэттенское расстояние: |
− | :<tex>Q(\beta, X^l)=\sum | + | :<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>\beta</tex>: | Запишем задачу настройки вектора параметров <tex>\beta</tex>: | ||
− | :<tex>Q(\beta) = \ | + | :<tex>Q(\beta) = \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>\mathcal{L}_{i}(\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>\begin{cases} u_{j}=\frac{1}{2}(|\beta_{j}| + \beta_{j}) \\ v_{j}=\frac{1}{2}(|\beta_{j}| - \beta_{j}) \end{cases} </tex> |
− | |||
Тогда: | Тогда: | ||
− | :<tex>\beta_{j} = u_{j} | + | :<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\limits_{i=1}^l\mathcal{L}_{i}(u - v) + \lambda \sum\limits_{j=1}^n(u_{j} + v_{j}) \rightarrow \min\limits_{u,v} \\ u_{j} \geq 0, v_{j} \geq 0, \: j=1,...,n\end{cases} </tex> |
− | :<tex>Q(u, v) = \ | + | Для любого <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>\beta_{j} = 0</tex>. Как говорилось ранее, в линейных моделях это означает, что значения <tex>j</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> | ||
===Эластичная сеть=== | ===Эластичная сеть=== | ||
Строка 71: | Строка 68: | ||
|definition= | |definition= | ||
Эластичная сеть (англ. ''elastic net regularization''): | Эластичная сеть (англ. ''elastic net regularization''): | ||
− | :<tex>Q(\beta, X^l)=\sum | + | :<tex>Q(\beta, X^l)=\sum\limits_{I=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>L_{1}</tex>, так и <tex>L_{2}</tex> регуляризации, учитывая эффективность обоих методов. Ее полезной особенностью является то, что она создает условия для группового эффекта при высокой корреляции переменных, а не обнуляет некоторые из них, как в случае с <tex>L_{1}</tex>-регуляризацией. | ||
Строка 78: | Строка 75: | ||
===Эквивалентная вероятностная задача=== | ===Эквивалентная вероятностная задача=== | ||
Перед нами стоит задача {{---}} минимизировать эмпирический риск: | Перед нами стоит задача {{---}} минимизировать эмпирический риск: | ||
− | :<tex>Q(\beta, X^l)=\sum _{i}^l\mathcal{L}(y_{i}, g(x_{i}, \beta)) \rightarrow | + | :<tex>Q(\beta, X^l)=\sum\limits _{i=1}^l\mathcal{L}(y_{i}, g(x_{i}, \beta)) \rightarrow \min\limits_{\beta}</tex> |
[[Байесовская классификация | Вероятностная модель данных]] дает возможность по-другому взглянуть на задачу. Пусть <tex>X \times Y</tex> {{---}} является вероятностным пространством. Тогда вместо <tex>g(x_{i}, \beta)</tex> задана совместная плотность распределение объектов и классов <tex>p(x, y|\beta)</tex>. | [[Байесовская классификация | Вероятностная модель данных]] дает возможность по-другому взглянуть на задачу. Пусть <tex>X \times Y</tex> {{---}} является вероятностным пространством. Тогда вместо <tex>g(x_{i}, \beta)</tex> задана совместная плотность распределение объектов и классов <tex>p(x, y|\beta)</tex>. | ||
− | Для настройки вектора параметров \beta воспользуемся ''принципом максимума правдоподобия'': | + | Для настройки вектора параметров $\beta$ воспользуемся ''принципом максимума правдоподобия'': |
− | :<tex>p(X^l|\beta)=\ | + | :<tex>p(X^l|\beta)=\prod\limits_{i=1}^lp(x_{i},y_{i}|\beta) \rightarrow \max\limits_{\beta}</tex> |
Удобнее рассматривать логарифм правдоподобия: | Удобнее рассматривать логарифм правдоподобия: | ||
− | :<tex>L(\beta, X^l)=\ln p(X^l|\beta)=\ | + | :<tex>L(\beta, X^l)=\ln p(X^l|\beta)=\sum\limits_{i=1}^l \ln p(x_{i}, y_{i}|\beta) \rightarrow \max\limits_{\beta}</tex> |
Можно заключить, что задачи в исходном и вероятностном представлении эквивалентны, если положить: | Можно заключить, что задачи в исходном и вероятностном представлении эквивалентны, если положить: | ||
:<tex>-\ln p(x_{i}, y_{i}|\beta)=\mathcal{L}(y_{i}, g(x_{i}, \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( | + | Допустим, что наряду с параметрической моделью плотности распределения <tex>p(x, y|\beta)</tex> имеется еще и ''априорное распределение в пространстве параметров модели'' <tex>p(\beta)</tex>. Чтобы ослабить априорные ограничения, вместо фиксированной функции <tex>p(\beta)</tex> вводится ''параметрическое семейство априорных распределений'' <tex>p(\beta; \gamma)</tex>, где <tex>\gamma</tex> {{---}} гиперпараметр. |
Принцип максимума правдоподобия теперь будет записываться по-другому, так как не только появление выборки <tex>X^l</tex>, но и появление модели <tex>\beta</tex> также является случайным. Их совместное появление описывается, согласно формуле условной вероятности, плотностью распределения: | Принцип максимума правдоподобия теперь будет записываться по-другому, так как не только появление выборки <tex>X^l</tex>, но и появление модели <tex>\beta</tex> также является случайным. Их совместное появление описывается, согласно формуле условной вероятности, плотностью распределения: | ||
Строка 95: | Строка 92: | ||
Таким образом, приходим к ''принципу максимума совместного правдоподобия данных и модели'': | Таким образом, приходим к ''принципу максимума совместного правдоподобия данных и модели'': | ||
− | :<tex>L_{\gamma}(\beta, X^l)=\ln p(X^l, \beta;\gamma)=\ | + | :<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\limits_{\beta}</tex> |
Функционал <tex>L_{\gamma}</tex> распадается на два слагаемых: логарифм правдоподобия и ''регуляризатор'', не зависящий от данных. Второе слагаемое ограничивает вектор параметров модели, не позволяя ему быть каким угодно. | Функционал <tex>L_{\gamma}</tex> распадается на два слагаемых: логарифм правдоподобия и ''регуляризатор'', не зависящий от данных. Второе слагаемое ограничивает вектор параметров модели, не позволяя ему быть каким угодно. | ||
Строка 107: | Строка 104: | ||
Логарифмируя, получаем ''квадратичный регуляризатор'': | Логарифмируя, получаем ''квадратичный регуляризатор'': | ||
:<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>\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>const(\beta)</tex> {{---}} слагаемое, не зависящее от <tex>\beta</tex>, которым можно пренебречь, поскольку оно не влияет на решение оптимизационной задачи. В итоге имеем <tex>L_{2}</tex>-регуляризатор. |
===Лапласовский регуляризатор=== | ===Лапласовский регуляризатор=== | ||
Строка 113: | Строка 110: | ||
:<tex>\beta \sim Laplace(0, C)</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} = \ | + | :<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\limits_{j}|\beta_{j}|</tex> |
Распределение Лапласа имеет более острый пик и более тяжёлые «хвосты», по сравнению с нормальным распределением. Его дисперсия равна <tex>2C^2</tex>. | Распределение Лапласа имеет более острый пик и более тяжёлые «хвосты», по сравнению с нормальным распределением. Его дисперсия равна <tex>2C^2</tex>. | ||
− | Аналогично случаю с нормальным регуляризатором, <tex>const(\beta)</tex> можно опустить и, таким образом, получаем <tex>L_{1}</tex> | + | Аналогично случаю с нормальным регуляризатором, <tex>const(\beta)</tex> можно опустить и, таким образом, получаем <tex>L_{1}</tex> -регуляризатор. |
==Регуляризация в линейной регрессии== | ==Регуляризация в линейной регрессии== | ||
В [[Линейная регрессия | линейной регрессии]] моделируется линейная зависимость между зависимой и независимой переменной. Таким образом, модель алгоритмов для нее состоит из функций вида: | В [[Линейная регрессия | линейной регрессии]] моделируется линейная зависимость между зависимой и независимой переменной. Таким образом, модель алгоритмов для нее состоит из функций вида: | ||
− | :$g(x, \beta) = \ | + | :$g(x, \beta) = \sum\limits_{j}^n \beta_{j} f_{j}(x)$ |
В итоге оптимизируемый функционал эмпирического риска выглядит следующим образом: | В итоге оптимизируемый функционал эмпирического риска выглядит следующим образом: | ||
:$Q(a) = \|F\beta - y\|^2$, | :$Q(a) = \|F\beta - y\|^2$, | ||
− | где $F = (f_ | + | где $F = (f_(x_{i}))_{l \times n}$ {{---}} матрица объекты-признаки, $y = (y_{i})_{l \times 1}$ {{---}} целевой вектор, $\beta = (\beta_{j})_{n \times 1}$ {{---}} вектор параметров. |
Приравняв нулю производную $Q(\beta)$ по параметру $\beta$, получаем: | Приравняв нулю производную $Q(\beta)$ по параметру $\beta$, получаем: | ||
:$\beta^* = (F^TF)^{-1}F^Ty$ | :$\beta^* = (F^TF)^{-1}F^Ty$ | ||
− | В итоге, | + | В итоге, используя [[Сингулярное разложение | сингулярное разложение]] для представления $F$ и проведя МНК-аппроксимизацию целевого вектора $y$, имеем выражение для нормы вектора $\beta$: |
− | :$\|\beta^*\|^2 = \ | + | :$\|\beta^*\|^2 = \sum\limits_{j=1}^n \frac{1}{\lambda_{j}}(v_{j}^Ty)^2$ |
− | К сожалению, могут возникнуть проблемы мультиколлинеарности и переобучения в случае, если ковариационная матрица $\sum = F^T F$ плохо обусловлена. Одним из способов борьбы с этими проблемами является регуляризация. | + | К сожалению, могут возникнуть проблемы мультиколлинеарности и переобучения в случае, если ковариационная матрица $\sum = F^T F$ плохо обусловлена. Одним из способов борьбы с этими проблемами, как говорилось ранее, является регуляризация. |
− | В статье о [[Виды регрессии | видах регрессии]] представлены модификации линейной регресиии с различными регуляризаторами ($L_{1}$ и $L_{2}$) и их отличие. Описание в данном разделе будет похожим, однако здесь будет рассмотрен эффект от добавления регуляризаторов немного | + | В статье о [[Виды регрессии | видах регрессии]] представлены модификации линейной регресиии с различными регуляризаторами ($L_{1}$ и $L_{2}$) и их отличие. Описание в данном разделе будет похожим, однако здесь будет рассмотрен эффект от добавления регуляризаторов немного подробнее. |
===Гребневая регрессия=== | ===Гребневая регрессия=== | ||
Строка 137: | Строка 134: | ||
Итоговый минимизируемый функционал с поправкой: | Итоговый минимизируемый функционал с поправкой: | ||
− | :<tex>Q_{\lambda}(\beta) = ||F \beta - y||^2 + \ | + | :<tex>Q_{\lambda}(\beta) = ||F \beta - y||^2 + \tau ||\beta||^2</tex> |
− | Итоговое выражение для параметра \beta: | + | Итоговое выражение для параметра $\beta$: |
:<tex>\beta_{\tau}^* = (F^TF + \tau I_{n})^{-1}F^Ty</tex> | :<tex>\beta_{\tau}^* = (F^TF + \tau I_{n})^{-1}F^Ty</tex> | ||
Таким образом, перед обращением матрицы к ней добавляется "гребень" {{---}} диагональная матрица $\tau I_{n}$. При этом все её собственные значения увеличиваются на $\tau$, а собственные векторы не изменяются. В результате матрица становится хорошо обусловленной, оставаясь в то же время «похожей» на исходную. | Таким образом, перед обращением матрицы к ней добавляется "гребень" {{---}} диагональная матрица $\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=\ | + | :$\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 \frac{\sqrt{\lambda_{j}}}{\lambda_{j} + \tau}u_{j}(v_{j}^Ty)$ |
Теперь найдём регуляризованную МНК-аппроксимацию целевого вектора y: | Теперь найдём регуляризованную МНК-аппроксимацию целевого вектора y: | ||
− | :$F \beta_{\tau}^* = VDU^T \beta_{\tau}^* = V diag(\frac{\lambda_{j}}{\lambda_{j} + \tau})V^Ty = \ | + | :$F \beta_{\tau}^* = VDU^T \beta_{\tau}^* = V diag(\frac{\lambda_{j}}{\lambda_{j} + \tau})V^Ty = \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)$. | Как можно видеть, проекции на собственные векторы сокращаются, умножаясь $\frac{\lambda_{j}}{\lambda_{j} + \tau} \in (0, 1)$. | ||
В сравнении с нерегуляризованным случаем, уменьшается и норма вектора $\beta$: | В сравнении с нерегуляризованным случаем, уменьшается и норма вектора $\beta$: | ||
− | :$\|\beta_{\tau}^*\|^2 = \| D^2(D^2 + \tau I_{n})^{-1}D^{-1}V^{T}y)\|^2 = \ | + | :$\|\beta_{\tau}^*\|^2 = \| D^2(D^2 + \tau I_{n})^{-1}D^{-1}V^{T}y)\|^2 = \sum\limits_{j=1}^n \frac{1}{\lambda_{j} + \tau}(v_{j}^Ty)^2 < \sum\limits_{j=1}^n \frac{1}{\lambda_{j}}(v_{j}^Ty)^2 = \|\beta^*\|^2$ |
Поэтому данный метод называют также ''сжатие'' или ''сокращение весов''. | Поэтому данный метод называют также ''сжатие'' или ''сокращение весов''. | ||
Строка 157: | Строка 154: | ||
В нерегуляризованном случае: | В нерегуляризованном случае: | ||
− | :$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)^{-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}) = \ | + | :$n_{effective} = tr\:F(F^TF + \tau I_{n})^{-1}F^T = tr\:diag(\frac{\lambda_{j}}{\lambda_{j} + \tau}) = \sum\limits_{j=1}^n \frac{1}{\lambda_{j}} < n$ |
===Лассо регрессия=== | ===Лассо регрессия=== | ||
Строка 170: | Строка 167: | ||
Запишем систему для этой регрессии в виде минимизации неизменного функционала $Q$ при неравенстве-ограничении: | Запишем систему для этой регрессии в виде минимизации неизменного функционала $Q$ при неравенстве-ограничении: | ||
− | :$\begin{cases} Q(\beta) = \| F\beta - y \|^2 \rightarrow | + | :$\begin{cases} Q(\beta) = \| F\beta - y \|^2 \rightarrow \min\limits_{\beta} \\ \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_{1}$-регуляризатор, коэффициенты $\beta_{j}$ постепенно обнуляются с уменьшением $\chi$. Происходит отбор признаков, поэтому параметр $\chi$ называют еще ''селективностью''. Параметр $\chi$ "зажимает" вектор коэффициентов $\beta$, отсюда и название метода {{---}} лассо (англ. ''LASSO, least absolute shrinkage and selection operator''). | ||
− | ===Сравнение | + | ===Сравнение гребневой и лассо регрессий=== |
− | Основное различие | + | Основное различие лассо и гребневой регрессий заключается в том, что первая может приводить к обращению некоторых независимых переменных в ноль (используется $L_{1}$-регуляризатор), тогда как вторая уменьшает их до значений, близких к нулю (используется $L_{2}$-регуляризатор). |
Продублируем наглядный пример из статьи о [[Вариации регрессии | вариациях регрессии]]. Рассмотрим для простоты двумерное пространство независимых переменных. В случае лассо регрессии органичение на коэффициенты представляет собой ромб (<tex>|\beta_1| + |\beta_2| \leq t</tex>), в случае гребневой регрессии {{---}} круг (<tex>\beta_1^2 + \beta_2^2 \leq t^2</tex>). Необходимо минимизировать функцию ошибки, но при этом соблюсти ограничения на коэффициенты. С геометрической точки зрения задача состоит в том, чтобы найти точку касания линии, отражающей функцию ошибки с фигурой, отражающей ограничения на <tex>\beta</tex>. Из Рис. 3 интуитивно понятно, что в случае лассо регрессии эта точка с большой вероятностью будет находиться на углах ромба, то есть лежать на оси, тогда как в случае гребневой регрессии такое происходит очень редко. Если точка пересечения лежит на оси, один из коэффициентов будет равен нулю, а значит, значение соответствующей независимой переменной не будет учитываться. | Продублируем наглядный пример из статьи о [[Вариации регрессии | вариациях регрессии]]. Рассмотрим для простоты двумерное пространство независимых переменных. В случае лассо регрессии органичение на коэффициенты представляет собой ромб (<tex>|\beta_1| + |\beta_2| \leq t</tex>), в случае гребневой регрессии {{---}} круг (<tex>\beta_1^2 + \beta_2^2 \leq t^2</tex>). Необходимо минимизировать функцию ошибки, но при этом соблюсти ограничения на коэффициенты. С геометрической точки зрения задача состоит в том, чтобы найти точку касания линии, отражающей функцию ошибки с фигурой, отражающей ограничения на <tex>\beta</tex>. Из Рис. 3 интуитивно понятно, что в случае лассо регрессии эта точка с большой вероятностью будет находиться на углах ромба, то есть лежать на оси, тогда как в случае гребневой регрессии такое происходит очень редко. Если точка пересечения лежит на оси, один из коэффициентов будет равен нулю, а значит, значение соответствующей независимой переменной не будет учитываться. | ||
Строка 181: | Строка 178: | ||
{|align="center" | {|align="center" | ||
|-valign="top" | |-valign="top" | ||
− | |[[Файл: | + | |[[Файл: Ridge_and_Lasso.png|400px|thumb|Рис.3. Сравнение лассо (слева) и гребневой (справа) регрессий, пример для двумерного пространства независимых переменных.<br/>Бирюзовые области изображают ограничения на коэффициенты <tex>\beta</tex>, эллипсы {{---}} некоторые значения функции наименьшей квадратичной ошибки.]] |
|} | |} | ||
Также полезно будет рассмотреть простую модельную задачу. Пусть $l = n$ и матрица объекты-признаки является единичной $F = I$. Тогда МНК-решение дает вектор коэффициентов $\beta$: | Также полезно будет рассмотреть простую модельную задачу. Пусть $l = n$ и матрица объекты-признаки является единичной $F = I$. Тогда МНК-решение дает вектор коэффициентов $\beta$: | ||
− | :$\beta^* = argmin(\ | + | :$\beta^* = argmin(\sum\limits_{i=1}^l(\beta_{i} - y_{i})^2)$ |
:$\beta_{j}^* = y_{j}$ | :$\beta_{j}^* = y_{j}$ | ||
− | В случае с | + | В случае с гребневой регрессией: |
:$\beta_{j}^* = \frac{y_{j}}{1 + \lambda}$ | :$\beta_{j}^* = \frac{y_{j}}{1 + \lambda}$ | ||
В случае с лассо регрессией: | В случае с лассо регрессией: | ||
Строка 195: | Строка 192: | ||
{|align="center" | {|align="center" | ||
|-valign="top" | |-valign="top" | ||
− | |[[Файл: regularization_comparing.png|400px|thumb|Рис.4. Сравнение гребневой | + | |[[Файл: regularization_comparing.png|400px|thumb|Рис.4. Сравнение лассо и гребневой регрессий, пример с простой модельной задачи.]] |
|} | |} | ||
Строка 201: | Строка 198: | ||
===Градиентный спуск=== | ===Градиентный спуск=== | ||
Алгоритм [[Стохастический градиентный спуск | градиентного спуска]] используют для нахождения аппроксимирующей зависимости, определяя вектор весов <tex>w \in R^n</tex>, при котором достигается минимум эмпирического риска: | Алгоритм [[Стохастический градиентный спуск | градиентного спуска]] используют для нахождения аппроксимирующей зависимости, определяя вектор весов <tex>w \in R^n</tex>, при котором достигается минимум эмпирического риска: | ||
− | :<tex>Q(w, X^l)=\ | + | :<tex>Q(w, X^l)=\sum\limits_{i=1}^l\mathcal{L}(y_{i}, \langle w, x_{i} \rangle) \rightarrow \min\limits_{w}</tex> |
− | В этом | + | В этом методе выбирается некоторое начальное приближение для вектора весов <tex>w</tex>, затем запускается итерационный процесс, на каждом шаге которого вектор $w$ изменяется в направлении наиболее быстрого убывания функционала $Q$ {{---}} противоположно вектору градиента |
<tex>Q'(w)=(\frac{\partial Q^(w)}{\partial w_{j}})_{j=1}^n</tex>: | <tex>Q'(w)=(\frac{\partial Q^(w)}{\partial w_{j}})_{j=1}^n</tex>: | ||
:<tex>w := w - \eta Q'(w)</tex>, | :<tex>w := w - \eta Q'(w)</tex>, | ||
Строка 211: | Строка 208: | ||
:<tex>Q_{\tau}(w) = Q(w) + \frac{\tau}{2}\|w\|^2</tex> | :<tex>Q_{\tau}(w) = Q(w) + \frac{\tau}{2}\|w\|^2</tex> | ||
Это приводит к появлению аддитивной поправки в градиенте: | Это приводит к появлению аддитивной поправки в градиенте: | ||
− | :<tex> | + | :<tex>Q_{\tau}'(w) = Q′(w) + \tau</tex> |
В результате правило обновления весов принимает вид: | В результате правило обновления весов принимает вид: | ||
:<tex>w := w(1 - \eta \tau) - \eta Q'(w)</tex> | :<tex>w := w(1 - \eta \tau) - \eta Q'(w)</tex> | ||
Строка 223: | Строка 220: | ||
К сожалению, зачастую выборка является линейно неразделимой. В таком случае приходится "ослаблять ограничения", позволяя некоторым объектам попадать на территорию другого класса. Для каждого объекта от отступа отнимается некоторая положительная величина $\xi_i$, но требуется, чтобы введенные поправки были минимальны. В итоге постановка задачи ''SVM с мягким отступом'' (англ. ''soft-margin SVM'') выглядит следующим образом: | К сожалению, зачастую выборка является линейно неразделимой. В таком случае приходится "ослаблять ограничения", позволяя некоторым объектам попадать на территорию другого класса. Для каждого объекта от отступа отнимается некоторая положительная величина $\xi_i$, но требуется, чтобы введенные поправки были минимальны. В итоге постановка задачи ''SVM с мягким отступом'' (англ. ''soft-margin SVM'') выглядит следующим образом: | ||
$\begin{cases} | $\begin{cases} | ||
− | \frac{1}{2} \lVert w \rVert^2 + C \sum\limits_{i=1}^ | + | \frac{1}{2} \lVert w \rVert^2 + C \sum\limits_{i=1}^l \xi_i \to \min\limits_{w, b, \xi} \\ |
− | M_i(w, b) \geq 1 - \xi_i, \quad i = 1, \ldots, | + | M_i(w, b) \geq 1 - \xi_i, \quad i = 1, \ldots, l \\ |
− | \xi_i \geq 0, \quad i = 1, \ldots, | + | \xi_i \geq 0, \quad i = 1, \ldots, l \\ |
\end{cases}$ | \end{cases}$ | ||
− | Как показано в соответствующем данному | + | Как показано в соответствующем данному методу разделе, эквивалентной задачей безусловной минимизации является: |
− | $Q(w, b) = \frac{1}{2C} \lVert w \rVert^2 + \sum\limits_{i=1}^ | + | $Q(w, b) = \frac{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)$ можно рассматривать как верхнюю оценку эмпирического риска, к которому добавлен регуляризатор $\frac{1}{2C} \|w\|^2$. | В силу неравенства $[M_{i} < 0] \leq (1 - M_{i})_{+}$, функционал $Q(w, b)$ можно рассматривать как верхнюю оценку эмпирического риска, к которому добавлен регуляризатор $\frac{1}{2C} \|w\|^2$. | ||
Строка 239: | Строка 236: | ||
Также существуют разновидности SVM с другими регуляризаторами. | Также существуют разновидности SVM с другими регуляризаторами. | ||
* Метод релевантных векторов (англ. ''RVM, Relevance vector Machine''): | * Метод релевантных векторов (англ. ''RVM, Relevance vector Machine''): | ||
− | :$\frac{1}{2}\ | + | :$\frac{1}{2}\sum\limits_{i=1}^l(\ln w_{i} + \frac{\lambda_{i}^2}{w_{i}})$ |
* Метод опорных векторов с лассо (англ. ''LASSO SVM''): | * Метод опорных векторов с лассо (англ. ''LASSO SVM''): | ||
− | :$\mu \ | + | :$\mu \sum\limits_{i=1}^n|w_{i}|$ |
* Метод опорных признаков (англ. ''Support feature machine''): | * Метод опорных признаков (англ. ''Support feature machine''): | ||
− | :$\ | + | :$\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$ максимизируют логарифм правдоподобия: | Для настройки вектора коэффициентов $\beta$ по обучающей выборке $X^l$ максимизируют логарифм правдоподобия: | ||
− | :$L(\beta, X^l) = log_{2}\ | + | :$L(\beta, X^l) = log_{2}\prod\limits_{i=1}^lp(x_{i}, y_{i}) \rightarrow \max\limits_{\beta}$ |
− | :$L(\beta, X^l) = \ | + | :$L(\beta, X^l) = \sum\limits_{i=1}^{l}log_{2}\sigma(\langle \beta, x_{i} \rangle y_{i}) + const(\beta) \rightarrow \max\limits_{\beta}$ |
$L_{2}$-регуляризация: | $L_{2}$-регуляризация: | ||
− | :$L(\beta, X^l) = \ | + | :$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\limits_{\beta}$ |
$L_{1}$-регуляризация: | $L_{1}$-регуляризация: | ||
− | :$L(\beta, X^l) = \ | + | :$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\limits_{\beta}$ |
Аналогично можно использовать и другие регуляризаторы. | Аналогично можно использовать и другие регуляризаторы. | ||
Строка 264: | Строка 261: | ||
Регуляризация также используется и в [[Нейронные сети, перцептрон | нейронных сетях]] для борьбы со слишком большими весами сети и переобучением. Однако, в этом случае зануление коэффициентов при использовании $L_{1}$-регуляризатора не несет в себе смысл "отбора признаков", как в случае с линейными моделями. Регуляризация не снижает число параметров и не упрощает структуру сети. | Регуляризация также используется и в [[Нейронные сети, перцептрон | нейронных сетях]] для борьбы со слишком большими весами сети и переобучением. Однако, в этом случае зануление коэффициентов при использовании $L_{1}$-регуляризатора не несет в себе смысл "отбора признаков", как в случае с линейными моделями. Регуляризация не снижает число параметров и не упрощает структуру сети. | ||
− | Для нейронной сети помимо добавления | + | Для нейронной сети помимо добавления штрафного слагаемого к эмпирическому риску используют и другой метод регуляризации {{---}} ''прореживание сети'' (англ. ''dropout''), в ходе которого упрощают сеть, руководствуясь правилом {{---}} если функция ошибки не изменяется, то сеть можно упрощать и дальше. Подробнее об этом можно почитать в статье, рассказывающей о [[Практики реализации нейронных сетей | практике реализации нейронных сетей]]. |
==См. также== | ==См. также== |
Версия 13:52, 21 января 2020
Определение: |
Регуляризация (англ. regularization) в статистике, машинном обучении, теории обратных задач — метод добавления некоторых дополнительных ограничений к условию с целью решить неккоректно поставленную задачу или предотвратить переобучение. Чаще всего эта информация имеет вид штрафа за сложность модели. |
Содержание
Мотивация
Как говорилось ранее, регуляризация полезна для борьбы с переобучением. Если вы выбрали сложную модель, и при этом у вас недостаточно данных, то легко можно получить итоговую модель, которая хорошо описывает обучающую выборку, но не обобщается на тестовую.
На примере линейной регрессии
В качестве наглядного примера рассмотрим линейные регрессионные модели. Восстановить зависимость для нескольких точек можно пытаться полиномами разной степени $M$.
На Рис 1. представлена зависимость, которая хорошо подходит для описания данных, а на Рис. 2 — модель, слишком сильно заточенная под обучающую выборку.
Однин из способов бороться с негативным эффектом излишнего подстраивания под данные — использование регуляризации, т. е. добавление некоторого штрафа за большие значения коэффициентов у линейной модели. Тем самым запрещаются слишком "резкие" изгибы и предотвращается переобучение.
На примере логистической регрессии
Необходимость регуляризации можно увидеть и на другом примере — при использовании логистической регресии. Представьте, что ваша обучающая выборка была линейно разделима. В таком случае в процессе оптимизации значения весов модели уйдут в бесконечность, и вместо сигмойды получится "ступенька", представленная на Рис. 3.
Это плохо, ибо произошло затачивание под обучающую выборку. Как и в предыдущем примере, побороться с этим можно путем добавлением регуляризатора, не дающего весам принимать слишком большие значения.
Основные виды регуляризации
Переобучение в большинстве случаев проявляется в том, что итоговые модели имеют слишком большие значения параметров. Соответственно, необходимо добавить в целевую функцию штраф за это. Наиболее часто используемые виды регуляризации —
и , а также их линейная комбинация — эластичная сеть.В представленных ниже формулах для эмпирического риска модели алгоритмов.
: является функцией потерь, а — вектором параметров элемента-регуляризация
Определение: |
| -регуляризация, или регуляризация Тихонова (англ. ridge regularization или Tikhonov regularization):
Минимизация регуляризованного cоответствующим образом эмпирического риска приводит к выбору такого вектора параметров
, которое не слишком сильно отклоняется от нуля. В линейных классификаторах это позволяет избежать проблем мультиколлинеарности и переобучения.-регуляризация
Определение: |
| -регуляризация (англ. lasso regularization), или регуляризация через манхэттенское расстояние:
Данный вид регуляризации также позволяет ограничить значения вектора
. Однако, к тому же он обладает интересным и полезным на практике свойством — обнуляет значения некоторых параметров, что в случае с линейными моделями приводит к отбору признаков.Запишем задачу настройки вектора параметров
:- ,
где
— некоторая ограниченная гладкая функция потерь. Сделаем замену переменных, чтобы функционал стал гладким. Каждой переменной поставим в соответствие две новые неотрицательные переменные:Тогда:
В новых переменных функционал становится гладким, но добавляются ограничения-неравенства:
Для любого
хотя бы одно из ограничений и обращается в равенство, иначе второе слагаемое в можно было бы уменьшить, не изменив первое. Если гиперпараметр устремить к , в какой-то момент все ограничений обратятся в равенство. Постепенное увеличение гиперпараметра приводит к увеличению числа таких , для которых , откуда следует, что . Как говорилось ранее, в линейных моделях это означает, что значения -го признака игнорируются, и его можно исключить из модели.Эластичная сеть
Определение: |
Эластичная сеть (англ. elastic net regularization):
|
Приведенная регуляризация использует как
, так и регуляризации, учитывая эффективность обоих методов. Ее полезной особенностью является то, что она создает условия для группового эффекта при высокой корреляции переменных, а не обнуляет некоторые из них, как в случае с -регуляризацией.Вероятностная интерпретация регуляризации
Эквивалентная вероятностная задача
Перед нами стоит задача — минимизировать эмпирический риск:
Вероятностная модель данных дает возможность по-другому взглянуть на задачу. Пусть — является вероятностным пространством. Тогда вместо задана совместная плотность распределение объектов и классов .
Для настройки вектора параметров $\beta$ воспользуемся принципом максимума правдоподобия:
Удобнее рассматривать логарифм правдоподобия:
Можно заключить, что задачи в исходном и вероятностном представлении эквивалентны, если положить:
Принцип максимума совместного правдоподобия данных и модели
Допустим, что наряду с параметрической моделью плотности распределения
имеется еще и априорное распределение в пространстве параметров модели . Чтобы ослабить априорные ограничения, вместо фиксированной функции вводится параметрическое семейство априорных распределений , где — гиперпараметр.Принцип максимума правдоподобия теперь будет записываться по-другому, так как не только появление выборки
, но и появление модели также является случайным. Их совместное появление описывается, согласно формуле условной вероятности, плотностью распределения:Таким образом, приходим к принципу максимума совместного правдоподобия данных и модели:
Функционал
распадается на два слагаемых: логарифм правдоподобия и регуляризатор, не зависящий от данных. Второе слагаемое ограничивает вектор параметров модели, не позволяя ему быть каким угодно.В итоге мы получили, что с байесовской точки зрения многие методы регуляризации соответствуют добавлению некоторых априорных распределений на параметры модели. При этом можно определить распределения, которые соответствуют представленным ранее
и регуляризаторам.Нормальный регуляризатор
Пусть вектор [1], все его компоненты независимы и имеют равные дисперсии:
имеет нормальное распределениеЛогарифмируя, получаем квадратичный регуляризатор:
где
— слагаемое, не зависящее от , которым можно пренебречь, поскольку оно не влияет на решение оптимизационной задачи. В итоге имеем -регуляризатор.Лапласовский регуляризатор
Пусть вектор [2], все его компоненты независимы и имеют равные дисперсии:
имеет распределение ЛапласаТогда:
Распределение Лапласа имеет более острый пик и более тяжёлые «хвосты», по сравнению с нормальным распределением. Его дисперсия равна
.Аналогично случаю с нормальным регуляризатором,
можно опустить и, таким образом, получаем -регуляризатор.Регуляризация в линейной регрессии
В линейной регрессии моделируется линейная зависимость между зависимой и независимой переменной. Таким образом, модель алгоритмов для нее состоит из функций вида:
- $g(x, \beta) = \sum\limits_{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\limits_{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\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\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\limits_{j=1}^n \frac{1}{\lambda_{j} + \tau}(v_{j}^Ty)^2 < \sum\limits_{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\limits_{j=1}^n \frac{1}{\lambda_{j}} < n$
Лассо регрессия
К функционалу $Q$ добавляется $L_{1}$-регуляризатор.
Итоговый минимизируемый функционал с поправкой:
Запишем систему для этой регрессии в виде минимизации неизменного функционала $Q$ при неравенстве-ограничении:
- $\begin{cases} Q(\beta) = \| F\beta - y \|^2 \rightarrow \min\limits_{\beta} \\ \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_{1}$-регуляризатор), тогда как вторая уменьшает их до значений, близких к нулю (используется $L_{2}$-регуляризатор).
Продублируем наглядный пример из статьи о вариациях регрессии. Рассмотрим для простоты двумерное пространство независимых переменных. В случае лассо регрессии органичение на коэффициенты представляет собой ромб ( ), в случае гребневой регрессии — круг ( ). Необходимо минимизировать функцию ошибки, но при этом соблюсти ограничения на коэффициенты. С геометрической точки зрения задача состоит в том, чтобы найти точку касания линии, отражающей функцию ошибки с фигурой, отражающей ограничения на . Из Рис. 3 интуитивно понятно, что в случае лассо регрессии эта точка с большой вероятностью будет находиться на углах ромба, то есть лежать на оси, тогда как в случае гребневой регрессии такое происходит очень редко. Если точка пересечения лежит на оси, один из коэффициентов будет равен нулю, а значит, значение соответствующей независимой переменной не будет учитываться.
Также полезно будет рассмотреть простую модельную задачу. Пусть $l = n$ и матрица объекты-признаки является единичной $F = I$. Тогда МНК-решение дает вектор коэффициентов $\beta$:
- $\beta^* = argmin(\sum\limits_{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$ — противоположно вектору градиента :- ,
где
— величина шага в направлении антиградиента.Регуляризация — одна из эвристик улучшения градиентных методов обучения. Основным способом уменьшить переобучение является квадратичная регуляризация, называемая также сокращением весов. Чтобы ограничить рост абсолютных значений весов, к минимизируемому функционалу
добавляется штрафное слагаемое:Это приводит к появлению аддитивной поправки в градиенте:
В результате правило обновления весов принимает вид:
Таким образом, вся модификация сводится к появлению неотрицательного множителя
, приводящего к постоянному уменьшению весов.Регуляризация предовтращает паралич, повышает устойчивость весов в случае мультиколлинеарности, повышает обобщающую способность алгоритма и снижает риск переобучения. Однако есть и недостатки — параметр кросс-валидации, что связано с большими вычислительными затратами.
необходимо выбирать с помощьюМетод опорных векторов
Метод опорных векторов (SVM) используется для задач классификации и регрессии. В нем строится гиперплоскость, разделяющая объекты выборки оптимальным образом.
К сожалению, зачастую выборка является линейно неразделимой. В таком случае приходится "ослаблять ограничения", позволяя некоторым объектам попадать на территорию другого класса. Для каждого объекта от отступа отнимается некоторая положительная величина $\xi_i$, но требуется, чтобы введенные поправки были минимальны. В итоге постановка задачи SVM с мягким отступом (англ. soft-margin SVM) выглядит следующим образом: $\begin{cases} \frac{1}{2} \lVert w \rVert^2 + C \sum\limits_{i=1}^l \xi_i \to \min\limits_{w, b, \xi} \\ M_i(w, b) \geq 1 - \xi_i, \quad i = 1, \ldots, l \\ \xi_i \geq 0, \quad i = 1, \ldots, l \\ \end{cases}$
Как показано в соответствующем данному методу разделе, эквивалентной задачей безусловной минимизации является: $Q(w, b) = \frac{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)$ можно рассматривать как верхнюю оценку эмпирического риска, к которому добавлен регуляризатор $\frac{1}{2C} \|w\|^2$.
С введением регуляризатора устраняется проблема мультиколлинеарности, повышается устойчивость алгоритма, улучшается его обобщающая способность.
В результате получаем, что принцип оптимальной разделяющей гиперплоскости или максимизации ширины разделяющей полосы в случае неразделимой выборки тесно связан с $L_{2}$-регуляризацией, которая возникает естественным образом из постановки задачи.
Также существуют разновидности SVM с другими регуляризаторами.
- Метод релевантных векторов (англ. RVM, Relevance vector Machine):
- $\frac{1}{2}\sum\limits_{i=1}^l(\ln w_{i} + \frac{\lambda_{i}^2}{w_{i}})$
- Метод опорных векторов с лассо (англ. LASSO SVM):
- $\mu \sum\limits_{i=1}^n|w_{i}|$
- Метод опорных признаков (англ. Support feature machine):
- $\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\limits_{i=1}^lp(x_{i}, y_{i}) \rightarrow \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\limits_{\beta}$
$L_{2}$-регуляризация:
- $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\limits_{\beta}$
$L_{1}$-регуляризация:
- $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\limits_{\beta}$
Аналогично можно использовать и другие регуляризаторы.
Нейронные сети
Регуляризация также используется и в нейронных сетях для борьбы со слишком большими весами сети и переобучением. Однако, в этом случае зануление коэффициентов при использовании $L_{1}$-регуляризатора не несет в себе смысл "отбора признаков", как в случае с линейными моделями. Регуляризация не снижает число параметров и не упрощает структуру сети.
Для нейронной сети помимо добавления штрафного слагаемого к эмпирическому риску используют и другой метод регуляризации — прореживание сети (англ. dropout), в ходе которого упрощают сеть, руководствуясь правилом — если функция ошибки не изменяется, то сеть можно упрощать и дальше. Подробнее об этом можно почитать в статье, рассказывающей о практике реализации нейронных сетей.
См. также
- Переобучение
- Модель алгоритма и её выбор
- Байесовская классификация
- Вариации регрессии
- Линейная регрессия
- Логистическая регрессия
- Стохастический градиентный спуск
- Метод опорных векторов (SVM)
- Нейронные сети, перцептрон
- Практики реализации нейронных сетей
Примечания
Источники информации
- Воронцов К.В. — Математические методы обучения по прецедентам
- Википедия — Регуляризация (математика)
- coursea.org — Регуляризация
- machinelearning.ru — L1-регуляризация линейной регрессии
- medium.com — 5 видов регрессии и их свойства
- Wikipedia — Elastic net regularization
- Keng B. — A Probabilistic Interpretation of Regularization