Изменения

'''Стохастический градиентный спуск''' - оптимизационный алгоритм, отличающийся от обычного [https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA градиентного спуска] тем, что градиент оптимизируемой функции считается на каждом шаге не как сумма градиентов от каждого элемента выборки, а как градиент от одного, случайно выбранного элемента.

Для начала вспомним, как работает обычный градиентный спуск. Пусть объекты задаются $n$ числовыми признаками $f_j : X \to R, j = 1 ... n$ и пространство признаковых описаний в таком случае $X = R^n$. Пусть $Y$ $-$ конечное множество меток классов и задана обучающая выборка пар «объект-ответ» <tex>\{(x_1,y_1),\dots,(x_l,y_l)\}.</tex> Пусть семейство алгоритмов $a(x, {\bf w})$ зависит от вектора параметров имеет параметр вектор весов $\bf w$. И пускай мы выбрали какую-нибудь функцию потерь, для . Для $i$-го объекта выборки для алгоритма с весами ${\bf w}$ обозначим ее <tex> \mathscr{L}_i({\bf w}) </tex>. Необходимо минимизировать эмпирический риск, т.е. <tex>Q(w) = \sum\limits_{i=1}^l \mathscr{L}_i(w) \,\to\, \min\limits_{\bf w}</tex>. Если функция потерь принадлежит классу $C_1(X)$, то можно применить метод градиентного спуска. Выберем ${\bf w}^{(0)}$ - начальное приближение. Тогда каждый следующий вектор параметров будет вычисляться как ${\bf w}^{(t+1)}={\bf w}^{(t)} - h\sum\limits_{i=1}^{l}\nabla \mathscr{L}_i({\bf w}^{(t)})$, где $h$ - градиентный шаг, смысл которого заключается в том, насколько сильно менять вектор весов в направлении градиента. Остановка алгоритм алгоритма будет определятся определяться сходимостью $Q$ или $\bf w$.

Проблема предыдущего алгоритма заключается в том, что чтобы определить новое приближение вектора весов необходимо вычислить градиент от каждого элемента выборки, что может сильно замедлять алгоритм. Идея ускорения алгоритма заключается в использовании только одного элемента, либо некоторой подвыборки для подсчета нового приближения весов. То есть теперь новое приближение будет вычисляться как ${\bf w}^{(t+1)}={\bf w}^{(t)} - h\nabla \mathscr{L}_i({\bf w}^{(t)})$, где $i$ - случайно выбранный индекс. Так как теперь направление изменения $\bf w$ будет определяться за $O(1)$, подсчет $Q$ на каждом шаге будет слишком дорогостоящим. Для того, чтобы этого не делатьускорить оценку $Q$, будем использовать приближенную рекуррентную формулу. Тогда оценка $Q$ на $m$-ом шаге может выполняться следующими способамиМожно выбрать одну из следующих формул:

Есть Существует несколько способов инициализировать веса:

Так же можно запустить спуск несколько раз с разными начальными приближениями и выбрать лучшее решение.

* Иногда можно выполнять пробные шаги с помощью увеличения , а именно увеличивать h для выбивания процесса из локальных минимумов