1632
правки
Изменения
м
#*[http://www.machinelearning.ru/wiki/images/5/53/Voron-ML-Lin-SG.pdf Метод К.В. Воронцов {{---}} Линейные методы классификации и регрессии: метод стохастического градиента] $-$ презентация Воронцова#*[https://www.youtube.com/watch?v=4BKQ3GZR32w&list=PLJOzdkh8T5kp99tGTEFjH_b9zqEQiiBtC&index=4 Метод Курс "Машинное обучение" {{---}} Линейные методы классификации: метод стохастического градиента{{---}} К.В. Воронцов] $-$ запись лекции Воронцова#*[https://en.wikipedia.org/wiki/Logistic_regression Wikipedia {{---}} Logistic regression] $-$ Wikipedia#*[https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.SGDClassifier.html#sklearn.linear_model.SGDClassifier.decision_function sklearn.linear_model.SGDClassifier] ${{---$ }} описание алгоритма на scikit-learn.org]
rollbackEdits.php mass rollback
== Стохастический градиентный спуск ==
Проблема предыдущего алгоритма заключается в том, что чтобы определить новое приближение вектора весов необходимо вычислить градиент от каждого элемента выборки, что может сильно замедлять алгоритм. Идея ускорения алгоритма заключается в использовании только одного элемента, либо некоторой подвыборки для подсчета нового приближения весов. То есть теперь новое приближение будет вычисляться как ${\bf w}^{(t+1)}={\bf w}^{(t)} $-$ h\nabla \mathscr{L}_i({\bf w}^{(t)})$, где $i$ $-$ случайно выбранный индекс. Так как теперь направление изменения $\bf w$ будет определяться за $O(1)$, подсчет $Q$ на каждом шаге будет слишком дорогостоящим. Для того, чтобы ускорить оценку $Q$, будем использовать приближенную рекуррентную формулу. Можно выбрать одну из следующих формул:
* среднее арифметическое: $\overline{Q}_m = \dfrac{1}{m}\varepsilon_m + \dfrac{1}{m}\varepsilon_{m - 1} + \dfrac{1}{m}\varepsilon_{m - 2} + \dots = \dfrac{1}{m}\varepsilon_m + (1 - \dfrac{1}{m})\overline{Q}_{m-1}$;
* экспоненциальное скользящее среднее: $\overline{Q}_m = \lambda\varepsilon_m + (1 - \lambda)\varepsilon_{m - 1} + (1 - \lambda)^2\varepsilon_{m - 2} + \dots = \lambda\varepsilon_m + (1-\lambda)\overline{Q}_{m - 1},$ где $\lambda$ $-$ темп забывания предыстории ряда.
$i =$ rand() % $l$ <font color=green> # случайно выбрать элемент, по которому будет считаться градиент </font>
$\varepsilon = \mathscr{L}_i({\bf w})$ <font color=green> # вычислить потерю </font>
${\bf w} = {\bf w} - h \nabla \mathscr{L}_i({\bf w})$ <font color=green># обновить вектор весов в направлении градиентаантиградиента</font>
$\overline{Q} = \lambda\varepsilon + (1 - \lambda)\overline{Q}$ <font color=green># оценить функционал</font>
'''return''' w
== Регуляризация ==
Основным способом уменьшить переобучение является [[РегулярищацияРегуляризация|регуляризация]]<sup>[на 28.01.19 не создан]</sup>, т.е. сокращение весов. Будем штрафовать за увеличение нормы вектора весов, для этого перепишем функцию потерь $\tilde{\mathscr{L}}_i({\bf w}) = \mathscr{L}_i({\bf w}) + \dfrac{\tau}{2}||w||^2 = \mathscr{L}_i({\bf w}) + \dfrac{\tau}{2} \sum\limits_{j=1}^nw_j^2 \rightarrow \min\limits_w$, где $\tau$ $-$ коэффициент регуляризации.
Тогда градиент будет следующим: $\nabla \tilde{\mathscr{L}}_i({\bf w}) = \nabla \mathscr{L}_i({\bf w}) + \tau {\bf w}$, а градиентный шаг будет выглядеть так: ${\bf w} = {\bf w}(1 - h\tau) - h\nabla \mathscr{L}_i({\bf w})$.
== Источники информации ==
[[Категория: Машинное обучение]]
