Изменения

В качестве наглядного примера можно рассмотреть рассмотрим линейные регрессионные модели. Восстановить зависимость для нескольких точек можно пытаться полиномами разной степени $M$.

|[[Файл:Normal_bias_reg.png|200px|thumb|Рис . 1. Норма. M=2]] |[[Файл:High_variance_reg.png|200px|thumb|Рис . 2. Переобучение. M=4]]

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

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

Необходимость регуляризации можно увидеть и на другом примере{{---}} при использовании логистической регресии. Представьте, что ваша обучающая выборка была линейно разделима. В таком случае в процессе оптимизации значения весов модели уйдут в бесконечность , и вместо сигмойды получится "ступенька", как представлено представленная на Рис. 3.

|[[Файл:Sigmoid_infinity_weights.png|300px|thumb|Рис 3. Сигмойда {{- --}} "ступенька"]]

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

Переобучение в большинстве случаев проявляется в том, что итоговые модели имеют слишком большие значения параметров. Соответственно, необходимо добавить в целевую функцию штраф за это. Наиболее часто используемые виды регуляризации {{--- }} <tex>L_{1}</tex> и <tex >L_{2}</tex>, а также их линейная комбинация {{--- }} эластичная сеть.

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

:<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>, которое не слишком сильно отклоняется от нуля. В линейных классификаторах это позволяет избежать проблем мультиколлинеарности и переобучения.

<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>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}=\fracdfrac{1}{2}(|\beta_{j}| + \beta_{j})</tex>:<tex>\\ v_{j}=\fracdfrac{1}{2}(|\beta_{j}| - \beta_{j})\end{cases} </tex>

:<tex>\begin{cases} \beta_{j} = u_{j} + - v_{j}</tex>:<tex>\\ |\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_\min\limits_{u,v}</tex>:<tex>\\ u_{j} \geq 0, v_{j} \geq 0, \: j=1,\ldots,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_\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}{\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>X \times Y</tex> {{--- }} является вероятностным пространством. Тогда вместо <tex>g(x_{i}, \beta)</tex> задана совместная плотность распределение объектов и классов <tex>p(x, y|\beta)</tex>.

Для настройки вектора параметров $\beta $ воспользуемся ''принципом максимума правдоподобия''::<tex>p(X^l|\beta)=\prod_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_sum\limits_{i=1}^l \ln p(x_{i}, y_{i}|\beta) \rightarrow max_\max\limits_{\beta}</tex>

Допустим, что наряду с параметрической моделью плотности распределения <tex>p(x, y|\beta)</tex> имеется еще и ''априорное распределение в пространстве параметров модели'' <tex>p(\beta)</tex>. Чтобы ослабить априорные ограничения, вместо фиксированной функции <tex>p(w\beta)</tex> вводится ''параметрическое семейство априорных распределений'' <tex>p(\beta; \gamma)</tex>, где <tex>\gamma</tex> {{--- }} гиперпараметр.

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

Пусть вектор <tex>\beta</tex> имеет ''нормальное распределение''<ref>[https://ru.wikipedia.org/wiki/Нормальное_распределение Нормальное распределение]</ref>, все его компоненты независимы и имеют равные дисперсии:

:<tex>\ln p(\beta; \sigma) = \ln (\fracdfrac{1}{(2 \pi \sigma)^{n/2}} \exp(- \fracdfrac{\| \beta \| ^ 2}{2 \sigma})) = - \fracdfrac{1}{2 \sigma}\| \beta \| ^ 2 + const(\beta),</tex>где <tex>const(\beta)</tex> {{--- }} слагаемое, не зависящее от <tex>\beta</tex>, которым можно пренебречь, поскольку оно не влияет на решение оптимизационной задачи. В итоге имеем <tex>L_{2}</tex> - регуляризатор.

Пусть вектор <tex>\beta</tex> имеет ''распределение Лапласа''<ref>[https://ru.wikipedia.org/wiki/Распределение_Лапласа Распределение Лапласа]</ref>, все его компоненты независимы и имеют равные дисперсии:

:<tex>\ln p(\beta; C) = \ln (\fracdfrac{1}{(2C)^n} \exp(- \fracdfrac{\| \beta \|_{1}}{C})) = - \fracdfrac{1}{C}\| \beta \|_{1} + const(\beta), \| \beta \|_{1} = \sum_sum\limits_{j}|\beta_{j}|</tex>

Аналогично случаю с нормальным регуляризатором, <tex>const(\beta)</tex> можно опустить и, таким образом, получаем <tex>L_{1}</tex> - регуляризатор.

 К функционалу $Q$ добавляется $L_{1}$-регуляризатор. Итоговый минимизируемый функционал с поправкой::<tex>Q_{\tau}(\beta) = ||F \beta - y||^2 + \tau ||\beta||</tex> Запишем систему для этой регрессии в виде минимизации неизменного функционала $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}$-регуляризатор). Продублируем наглядный пример из статьи о [[Вариации регрессии | вариациях регрессии]]. Рассмотрим для простоты двумерное пространство независимых переменных. В случае лассо регрессии органичение на коэффициенты представляет собой ромб (<tex>|\beta_1| + |\beta_2| \leq t</tex>), в случае гребневой регрессии {{---}} круг (<tex>\beta_1^2 + \beta_2^2 \leq t^2</tex>). Необходимо минимизировать функцию ошибки, но при этом соблюсти ограничения на коэффициенты. С геометрической точки зрения задача состоит в том, чтобы найти точку касания линии, отражающей функцию ошибки с фигурой, отражающей ограничения на <tex>\beta</tex>. Из Рис. 3 интуитивно понятно, что в случае лассо регрессии эта точка с большой вероятностью будет находиться на углах ромба, то есть лежать на оси, тогда как в случае гребневой регрессии такое происходит очень редко. Если точка пересечения лежит на оси, один из коэффициентов будет равен нулю, а значит, значение соответствующей независимой переменной не будет учитываться. {|align="center" |-valign="top" |[[Файл: Ridge_and_Lasso.png|400px|thumb|Рис.3. Сравнение лассо (слева) и гребневой (справа) регрессий, пример для двумерного пространства независимых переменных.<br/>Бирюзовые области изображают ограничения на коэффициенты <tex>\beta</tex>, эллипсы {{---}} некоторые значения функции наименьшей квадратичной ошибки.]] |} Также полезно будет рассмотреть простую модельную задачу. Пусть $l = n$ и матрица объекты-признаки является единичной $F = I$. Тогда МНК-решение дает вектор коэффициентов $\beta$::$\beta^* = argmin(\sum\limits_{i=1}^l(\beta_{i} - y_{i})^2)$:$\beta_{j}^* = y_{j}$В случае с гребневой регрессией::$\beta_{j}^* = \dfrac{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}$ можно увидеть описанные ранее особенности данных регуляризованных линейных регрессий. {|align="center" |-valign="top" |[[Файл: regularization_comparing.png|400px|thumb|Рис.4. Сравнение лассо и гребневой регрессий, пример с простой модельной задачи.]] |}

Алгоритм [[Стохастический градиентный спуск | градиентного спуска]] используют для нахождения аппроксимирующей зависимости, определяя вектор весов <tex>w \in \mathbb{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_\min\limits_{w}</tex>

В этом методевыбирается методе выбирается некоторое начальное приближение для вектора весов <tex>w</tex>, затем запускается итерационный процесс, на каждом шаге которого вектор $w $ изменяется в направлении наиболее быстрого убывания функционала $Q $ {{- --}} противоположно вектору градиента<tex>Q'(w)=(\fracdfrac{\partial Q^(w)}{\partial w_{j}})_{j=1}^n</tex>:

где <tex>\eta > 0</tex> {{- --}} величина шага в направлении антиградиента.

'''Регуляризация''' {{--- }} одна из эвристик улучшения градиентных методов обучения. Основным способом уменьшить переобучение является квадратичная регуляризация, называемая также ''сокращением весов''. Чтобы ограничить рост абсолютных значений весов, к минимизируемому функционалу <tex>Q(w)</tex> добавляется штрафное слагаемое::<tex>Q_{\tau}(w) = Q(w) + \fracdfrac{\tau}{2}\|w\|^2</tex>

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

Регуляризация предовтращает паралич, повышает устойчивость весов в случае мультиколлинеарности, повышает обобщающую способность алгоритма и снижает риск переобучения. Однако есть и недостатки {{- --}} параметр <tex>\tau</tex> необходимо выбирать с помощью [[Кросс-валидация | кросс-валидации]], что связано с большими вычислительными затратами.

[[Метод опорных векторов(SVM) | Метод опорных векторов (SVM)]] используется для задачи бинарной задач классификациии регрессии. В нем строится гиперплоскость, разделяющая множества разных классовобъекты выборки оптимальным образом.

\fracdfrac{1}{2} \lVert w \rVert^2 + C \sum\limits_{i=1}^\ell l \xi_i \to \min\limits_{w, b, \xi} \\M_i(w, b) \geq 1 - \xi_i, \quad i = 1, \ldots, \ell l \\\xi_i \geq 0, \quad i = 1, \ldots, \ell l \\

Как показано в соответствующем данному алгоритму методу разделе, эквивалентной задачей безусловной минимизации является:$Q(w, b) = \fracdfrac{1}{2C} \lVert w \rVert^2 + \sum\limits_{i=1}^\ell 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$.

==Примечания==<references/>