50
правок
Изменения
Init
'''Стохастический градиентный спуск''' - оптимизационный алгоритм, отличающийся от обычного [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$ на $m$-ом шаге может выполняться следующими способами:
* Среднее арифметическое: $\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$ - темп забывания предыстории ряда.
== Псевдокод ==
'''def''' SG(x, h, l)''':'''
${\bf w} =$ initialize_weights() # инициализировать веса
$\overline{Q} = \frac{1}{l} \sum_{i=1}^{l}\mathscr{L}_i({\bf w})$ # инициализировать оценку функционала
'''while''' $Q$ not converges '''or''' ${\bf w}$ not converges''':'''
$i =$ rand() % $l$ # случайно выбрать элемент, по которому будет считаться градиент
$\varepsilon = \mathscr{L}_i({\bf w})$ # вычислить потерю
${\bf w} = {\bf w} - h \nabla \mathscr{L}_i({\bf w})$ # обновить вектор весов в направлении градиента
$\overline{Q} = \lambda\varepsilon + (1 - \lambda)\overline{Q}$ # оценить функционал
== Эвристики ==
Есть несколько способов инициализировать веса:
* ${\bf w} = {\bf 0}$
* $w_j = random(-\dfrac{1}{2n}, \dfrac{1}{2n})$. Стоит брать небольшие случайные веса, так как если выбрать их слишком большими, в некоторых случаях (к примеру в случае нейрона с функцией активациии равной арктангенсу) большие начальные значения веса могут привести в область с малыми по модулю производными, в связи с чем из такой области будет трудно выбраться.
* $w_j = \dfrac{\langle y, f_j \rangle}{\langle f_j, f_j \rangle}$, где $f_j = (f_j(x_i))_{i=1}^l$. Оценка оптимальная в случае, если функция потерь квадратична и признаки нескоррелированы, то есть $\langle f_j, f_k \rangle = 0, j \neq k$
Так же можно запустить спуск несколько раз и выбрать лучшее решение.
При выборе случайного элемента можно использовать следующие эвристики:
* брать объекты из разных классов
* брать объекты, на которых ошибка больше, то есть чем меньше отступ $M_i$, тем больше вероятность взять объект
* брать объекты, на которых уверенность меньше, то есть чем меньше $|M_i|$, тем больше вероятность взять объект
* не брать объекты, на которых уже высокая уверенность ($M_i > \mu_+$) либо не брать объекты-выбросы ($M_i<\mu_i$)
Выбирать величину градиентного шага можно следующими способами:
* $h_t = \dfrac{1}{t}$
* метод скорейшего градиентного спуска: $\mathscr{L}_i({\bf w} - h\nabla \mathscr{L}_i({\bf w})) \rightarrow \min\limits_h$.
* При квадратичной функции потерь можно использовать $h = ||x_i||^2$
* Иногда можно выполнять пробные шаги с помощью увеличения h для выбивания процесса из локальных минимумов
* [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D0%B1%D0%B5%D1%80%D0%B3%D0%B0_%E2%80%94_%D0%9C%D0%B0%D1%80%D0%BA%D0%B2%D0%B0%D1%80%D0%B4%D1%82%D0%B0 Метод Левенберга-Марквардта]
== Регуляризация ==
Основным способом уменьшить переобучение является регуляризация, т.е. сокращение весов. Будем штрафовать за увеличение нормы вектора весов, для этого перепишем функцию потерь $\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})$.
== Достоинства и недостатки ==
'''Достониства:'''
* Легко реализуется
* Функция потерь и семейство алгоритмов могут быть любыми (если функция потерь не дифференцируема, ее можно аппроксимировать дифференцируемой)
* Легко добавить регуляризацию
* Возможно потоковое обучение
* Подходит для задач с большими данными, иногда можно получить решение даже не обработав всю выборку
'''Недостатки'''
* Нет универсального набора эвристик, их нужно выбирать для конкретной задачи отдельно
== Пример кода scikit-learn ==
Классификатор [https://scikit-learn.org/stable/modules/sgd.html sklearn.linear_model.'''SGDClassifier'''] имеет несколько параметров, например:
'''loss''' - функция потерь. По умолчанию используется "hinge", дающая алгоритм линейного SVM
'''penalty''' - метод регуляризации. По умолчанию "l2"
'''alpha''' - $\tau$, коэффициент регуляризации
'''learning_rate''' - алгоритм изменения градиентного шага
'''eta0''' - начальный градиентный шаг
'''shuffle''' перемешивать тренировочную выборку после каждой итерации
* Импортируем нужные библиотеки
'''from''' sklearn.linear_model '''import''' SGDClassifier
'''from''' sklearn '''import''' datasets
'''from''' sklearn.model_selection '''import''' train_test_split
* Выберем тренировочное и тестовое множества
iris = datasets.'''load_iris()'''
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size='''0.3''')
* Обучение
clf = SGDClassifier(shuffle = True)
model = clf.'''fit'''(X_train, y_train)
* Предсказание
y_pred = model.'''predict'''(X_test)
model.'''score'''(X_test, y_test)
== Обычный градиентный спуск ==
Для начала вспомним, как работает обычный градиентный спуск. Пусть объекты задаются $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$ на $m$-ом шаге может выполняться следующими способами:
* Среднее арифметическое: $\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$ - темп забывания предыстории ряда.
== Псевдокод ==
'''def''' SG(x, h, l)''':'''
${\bf w} =$ initialize_weights() # инициализировать веса
$\overline{Q} = \frac{1}{l} \sum_{i=1}^{l}\mathscr{L}_i({\bf w})$ # инициализировать оценку функционала
'''while''' $Q$ not converges '''or''' ${\bf w}$ not converges''':'''
$i =$ rand() % $l$ # случайно выбрать элемент, по которому будет считаться градиент
$\varepsilon = \mathscr{L}_i({\bf w})$ # вычислить потерю
${\bf w} = {\bf w} - h \nabla \mathscr{L}_i({\bf w})$ # обновить вектор весов в направлении градиента
$\overline{Q} = \lambda\varepsilon + (1 - \lambda)\overline{Q}$ # оценить функционал
== Эвристики ==
Есть несколько способов инициализировать веса:
* ${\bf w} = {\bf 0}$
* $w_j = random(-\dfrac{1}{2n}, \dfrac{1}{2n})$. Стоит брать небольшие случайные веса, так как если выбрать их слишком большими, в некоторых случаях (к примеру в случае нейрона с функцией активациии равной арктангенсу) большие начальные значения веса могут привести в область с малыми по модулю производными, в связи с чем из такой области будет трудно выбраться.
* $w_j = \dfrac{\langle y, f_j \rangle}{\langle f_j, f_j \rangle}$, где $f_j = (f_j(x_i))_{i=1}^l$. Оценка оптимальная в случае, если функция потерь квадратична и признаки нескоррелированы, то есть $\langle f_j, f_k \rangle = 0, j \neq k$
Так же можно запустить спуск несколько раз и выбрать лучшее решение.
При выборе случайного элемента можно использовать следующие эвристики:
* брать объекты из разных классов
* брать объекты, на которых ошибка больше, то есть чем меньше отступ $M_i$, тем больше вероятность взять объект
* брать объекты, на которых уверенность меньше, то есть чем меньше $|M_i|$, тем больше вероятность взять объект
* не брать объекты, на которых уже высокая уверенность ($M_i > \mu_+$) либо не брать объекты-выбросы ($M_i<\mu_i$)
Выбирать величину градиентного шага можно следующими способами:
* $h_t = \dfrac{1}{t}$
* метод скорейшего градиентного спуска: $\mathscr{L}_i({\bf w} - h\nabla \mathscr{L}_i({\bf w})) \rightarrow \min\limits_h$.
* При квадратичной функции потерь можно использовать $h = ||x_i||^2$
* Иногда можно выполнять пробные шаги с помощью увеличения h для выбивания процесса из локальных минимумов
* [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D0%B1%D0%B5%D1%80%D0%B3%D0%B0_%E2%80%94_%D0%9C%D0%B0%D1%80%D0%BA%D0%B2%D0%B0%D1%80%D0%B4%D1%82%D0%B0 Метод Левенберга-Марквардта]
== Регуляризация ==
Основным способом уменьшить переобучение является регуляризация, т.е. сокращение весов. Будем штрафовать за увеличение нормы вектора весов, для этого перепишем функцию потерь $\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})$.
== Достоинства и недостатки ==
'''Достониства:'''
* Легко реализуется
* Функция потерь и семейство алгоритмов могут быть любыми (если функция потерь не дифференцируема, ее можно аппроксимировать дифференцируемой)
* Легко добавить регуляризацию
* Возможно потоковое обучение
* Подходит для задач с большими данными, иногда можно получить решение даже не обработав всю выборку
'''Недостатки'''
* Нет универсального набора эвристик, их нужно выбирать для конкретной задачи отдельно
== Пример кода scikit-learn ==
Классификатор [https://scikit-learn.org/stable/modules/sgd.html sklearn.linear_model.'''SGDClassifier'''] имеет несколько параметров, например:
'''loss''' - функция потерь. По умолчанию используется "hinge", дающая алгоритм линейного SVM
'''penalty''' - метод регуляризации. По умолчанию "l2"
'''alpha''' - $\tau$, коэффициент регуляризации
'''learning_rate''' - алгоритм изменения градиентного шага
'''eta0''' - начальный градиентный шаг
'''shuffle''' перемешивать тренировочную выборку после каждой итерации
* Импортируем нужные библиотеки
'''from''' sklearn.linear_model '''import''' SGDClassifier
'''from''' sklearn '''import''' datasets
'''from''' sklearn.model_selection '''import''' train_test_split
* Выберем тренировочное и тестовое множества
iris = datasets.'''load_iris()'''
X = iris.data
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size='''0.3''')
* Обучение
clf = SGDClassifier(shuffle = True)
model = clf.'''fit'''(X_train, y_train)
* Предсказание
y_pred = model.'''predict'''(X_test)
model.'''score'''(X_test, y_test)
