193
правки
Изменения
Нет описания правки
:<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>\begin{cases} u_{j}=\dfrac{1}{2}(|\beta_{j}| + \beta_{j}) \\ v_{j}=\fdracdfrac{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>\beta \sim N(0, \sigma^2)</tex>
Логарифмируя, получаем ''квадратичный регуляризатор'':
:<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 \sim Laplace(0, C)</tex>
Тогда:
:<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\limits_{j}|\beta_{j}|</tex>
Распределение Лапласа имеет более острый пик и более тяжёлые «хвосты», по сравнению с нормальным распределением. Его дисперсия равна <tex>2C^2</tex>.
:$\beta^* = (F^TF)^{-1}F^Ty$
В итоге, используя [[Сингулярное разложение | сингулярное разложение]] для представления $F$ и проведя МНК-аппроксимизацию целевого вектора $y$, имеем выражение для нормы вектора $\beta$:
:$\|\beta^*\|^2 = \sum\limits_{j=1}^n \fracdfrac{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\limits_{j=1}^n \fracdfrac{\sqrt{\lambda_{j}}}{\lambda_{j} + \tau}u_{j}(v_{j}^Ty)$
Теперь найдём регуляризованную МНК-аппроксимацию целевого вектора y:
:$F \beta_{\tau}^* = VDU^T \beta_{\tau}^* = V diag(\fracdfrac{\lambda_{j}}{\lambda_{j} + \tau})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$:
:$\|\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(\fracdfrac{\lambda_{j}}{\lambda_{j} + \tau}) = \sum\limits_{j=1}^n \fracdfrac{1}{\lambda_{j}} < n$
===Лассо регрессия===
:$\beta_{j}^* = y_{j}$
В случае с гребневой регрессией:
:$\beta_{j}^* = \fracdfrac{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}$
В этом методе выбирается некоторое начальное приближение для вектора весов <tex>w</tex>, затем запускается итерационный процесс, на каждом шаге которого вектор $w$ изменяется в направлении наиболее быстрого убывания функционала $Q$ {{---}} противоположно вектору градиента
<tex>Q'(w)=(\fracdfrac{\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) + \fracdfrac{\tau}{2}\|w\|^2</tex>
Это приводит к появлению аддитивной поправки в градиенте:
:<tex>Q_{\tau}'(w) = Q′(w) + \tau</tex>
К сожалению, зачастую выборка является линейно неразделимой. В таком случае приходится "ослаблять ограничения", позволяя некоторым объектам попадать на территорию другого класса. Для каждого объекта от отступа отнимается некоторая положительная величина $\xi_i$, но требуется, чтобы введенные поправки были минимальны. В итоге постановка задачи ''SVM с мягким отступом'' (англ. ''soft-margin SVM'') выглядит следующим образом:
$\begin{cases}
\fracdfrac{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 \\
Как показано в соответствующем данному методу разделе, эквивалентной задачей безусловной минимизации является:
$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$.
С введением регуляризатора устраняется проблема мультиколлинеарности, повышается устойчивость алгоритма, улучшается его обобщающая способность.
Также существуют разновидности SVM с другими регуляризаторами.
* Метод релевантных векторов (англ. ''RVM, Relevance vector Machine''):
:$\fracdfrac{1}{2}\sum\limits_{i=1}^l(\ln w_{i} + \fracdfrac{\lambda_{i}^2}{w_{i}})$
* Метод опорных векторов с лассо (англ. ''LASSO SVM''):
:$\mu \sum\limits_{i=1}^n|w_{i}|$
