Методика разработки программного продукта для поиска причин в изменениях трендов в данных. Стохастический Градиентный Спуск
Цель - минимизировать функцию F в пространстве все возможных точек. График F представляет собой параболическую поверхность, и у неё должен быть один-единственный минимум. А вопрос о том, как исправлять точки так, чтобы двигаться в сторону этого минимума, давным-давно решён в математическом анализе. Для этого нужно двигаться в направлении, противоположном градиенту - вектору, вдоль которого производная максимальна. Градиент вычисляется следующим образом:
Т.е. для вычисления градиента мы должны использовать производную от заданной функции при соответствующих точках (переменных).
Таким образом, чтобы определить, как правильно исправлять координаты точек, мы должны вычислить градиент и отнять вектор какой-нибудь наперёд заданной длины (в нашем случае этой длинной выступает заданный шаг а) от имеющегося вектора точек:
Чтобы реализовать это программно, нужно научиться дифференцировать функцию F:
Пример 1 - алгоритм градиентного спуска для одной точки.
GradientDescent()
- 1. Инициализировать маленькими случайными значениями.
- 2. Повторить Number_of_Steps раз:
- а) Для всех i от 1 до n
- б) Для всех j
от 1 до m
:
- (i) Для всех i от 1 до n
- 3. выдать значения.
Это значит, что нам нужно подправлять координаты точек после каждого тестового примера так:
Новый, изменённый алгоритм показан в примере 1. Правда, нужно внести и другие изменения. Во-первых, мы больше не можем рассчитывать на то, что в какой-то момент достигнем идеальной гармонии с исходными данными, и нам нужно научиться останавливаться в какой-то момент. В качестве условия для остановки здесь принято то, что алгоритм выполняется пока разности значений функции меньше ранее заданной точности. Другое изменение - в том, что если оставлять а постоянным, то на каком-то этапе точка перестанет приближаться к искомому минимуму, а начнёт его «перепрыгивать» на каждой итерации, то в одну сторону, то в другую. Поэтому a нужно уменьшать со временем. В данной программе мы уменьшаем шаг на два.
Этот алгоритм может находить локальные минимумы (у рассматривавшегося нами параболоида есть один локальный минимум). Его отличие в том, что он не собирает всю информацию со всех тестовых примеров, а модифицирует точки сразу же, после каждого шага итерации.
В этой лекции мы обсудим различные способы реализации , об их достоинствах и недостатках. Я бы хотел поговорить о трёх основных типах градиентного спуска – полном, пакетном и стохастическом.
В большинстве предыдущих курсов мы пользовались полным градиентным спуском.
Почему именно так?
Потому что это приносит больше пользы, если мы хотим максимизировать правдоподобие для всего учебного набора:
Недостатком такого подхода является то, что вычисление градиента занимает много времени, поскольку он зависит от каждого примера (наблюдения).
Полной противоположностью является стохастический градиентный спуск. Он зависит от ошибки лишь для одного конкретного наблюдения:
Метод основывается на том факте, что все наблюдения являются независимыми и равномерно распределёнными, поэтому в долгосрочной перспективе ошибка будет уменьшаться, ведь все наблюдения берутся из одного и того распределения. В таком случае, когда расчёты сократились от N наблюдений до 1, – это замечательное улучшение метода.
В чём же недостаток?
Дело в том, что если при полном градиентном спуске логарифм функции правдоподобия всегда улучшается на каждой итерации, то при стохастическом логарифм функции правдоподобия может даже ухудшиться. На самом деле поведение функции затрат будет хаотично меняться при каждой итерации, но в долгосрочной перспективе она всё же уменьшится.
Удачным компромиссов между этими двумя методами является пакетный градиентный спуск. Если у нас есть, к примеру, 10 000 наблюдений, то мы можем разделить их на 100 пакетов по 100 наблюдений в каждом и вычислять функцию затрат, основываясь на каждом пакете при каждой итерации:
Что в этом случае будет с функцией затрат?
Она тоже может становиться больше, но будет менее хаотична, чем в случае чисто стохастического градиентного спуска.
И пользуясь случаем, хочу отметить, что если вы желаете получить бесплатный материал, связанный с глубоким и машинным обучением, а также обработке данных, посетите мой сайт lazyprogrammer.me. Я постоянно пишу новые материалы по этим темам, так что проверяйте почаще. Там должно появиться предложение подписаться, так что вы можете подписаться на моё бесплатное введение в обработку данных. В нём много замечательных ресурсов для изучения языка Python, алгоритмов и структур данных, а также купонов на курсы на .
Полный, пакетный и стохастический градиентный спуск в коде
Теперь сравним изменение функции затрат в трёх случаях градиентного спуска – полного, пакетного и стохастического. Поскольку в этом примере много кода скопировано из других файлов, мы просто последовательно пройдёмся по тексту программы.
Итак, в начале файла мы импортируем все обычные библиотеки. Из файла util.py мы импортируем функцию get_transformed_data , чтобы преобразовать данные по методу главных компонент, а также функции forward, error_date, cost, gradW, gradb и y2indicator.
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.utils import shuffle
from datetime import datetime
from util import get_transformed_data, forward, error_rate, cost, gradW, gradb, y2indicator
Для ускорения процесса мы вместо полной нейронной сети используем .
Итак, вначале мы используем функцию get_transformed_data , взяв лишь первые 300 столбцов. Далее нормализуем наши X путём вычитания среднего значения и деления на стандартное отклонение. Затем, поскольку функция get_transformed_data уже перемешала наши данные, мы оставляем последние 1 000 примеров в качестве проверочного набора, использую остальные в качестве учебного.
def main():
X, Y, _, _ = get_transformed_data()
X = X[:, :300]
# normalize X first
mu = X.mean(axis =0)
std = X.std(axis =0)
X = (X – mu) / std
print “Performing logistic regression…”
Xtrain = X[:-1000,]
Ytrain = Y[:-1000]
Xtest = X[-1000:,]
N, D = Xtrain.shape
Ytrain_ind = y2indicator(Ytrain)
Ytest_ind = y2indicator(Ytest)
Затем инициируем весовые коэффициенты и свободные члены. Обратите внимание, что инициируемые весовые коэффициенты установлены относительно малыми – пропорциональными квадратному корню из размерности. Ещё до записи этого видео я установил значения коэффициента обучения и штрафа регуляризации – 0,0001 и 0,01 соответственно. Количество итераций установим равным 200, чтобы вычисления шли не слишком долго.
# 1. full
b = np.zeros(10)
LL =
lr = 0.0001
reg = 0.01
t0 = datetime.now()
for i in xrange (200):
p_y = forward(Xtrain, W, b)
Далее обновляем значения и свободных членов при помощи градиентного спуска и . Используем также функцию forward , чтобы вычислить значение функции затрат при прохождении учебного набора. Будем выводить значение коэффициента ошибок через каждые десять итераций. Кроме того, будем выводить на экран потраченное на вычисления время, поскольку один из методов весьма быстро, а другой – весьма медлителен.
W += lr*(gradW(Ytrain_ind, p_y, Xtrain) – reg*W)
b += lr*(gradb(Ytrain_ind, p_y) – reg*b)
LL.append(ll)
if i % 10 == 0:
print “Error rate:”, err
p_y = forward(Xtest, W, b)
print “Elapsted time for full GD:”, datetime.now() – t0
В случае стохастического градиентного спуска мы в большой мере делаем то же самое, разве что мы делаем лишь один проход по данным, поскольку при стохастическом градиентном спуске мы рассматриваем лишь один пример и обновляем весовые коэффициенты и свободные члены отдельно при каждом проходе, после чего заново перемешиваем данные. Поскольку если проходить по всем примерам, то работать программа будет очень медленно, постольку мы ограничимся лишь 500 примеров.
Затем, как обычно, вычисляем градиент, обновляем весовые коэффициенты с применением регуляризации и вычисляем коэффициент ошибок, разве что выводим значение коэффициента лишь каждые N/2 прохода, поскольку в противном случае вычисления будут очень долгими. В остальном – всё то же самое.
# 2. stochastic
W = np.random.randn(D, 10) / 28
b = np.zeros(10)
LL_stochastic =
lr = 0.0001
reg = 0.01
t0 = datetime.now()
for i in xrange (1): # takes very long since we’re computing cost for 41k samples
for n in xrange (min(N, 500)): # shortcut so it won’t take so long…
x = tmpX.reshape(1,D)
y = tmpY.reshape(1,10)
p_y = forward(x, W, b)
p_y_test = forward(Xtest, W, b)
ll = cost(p_y_test, Ytest_ind)
LL_stochastic.append(ll)
if n % (N/2) == 0:
err = error_rate(p_y_test, Ytest)
print “Cost at iteration %d: %.6f” % (i, ll)
print “Error rate:”, err
p_y = forward(Xtest, W, b)
print “Final error rate:”, error_rate(p_y, Ytest)
print “Elapsted time for SGD:”, datetime.now() – t0
При пакетном градиентном спуске, опять-таки, почти всё то же самое. Установим, что в каждом пакете по 500 примеров, так что общее количество пакетов будет равно N, делённое на размер пакета.
# 3. batch
W = np.random.randn(D, 10) / 28
b = np.zeros(10)
LL_batch =
lr = 0.0001
reg = 0.01
batch_sz = 500
n_batches = N / batch_sz
t0 = datetime.now()
for i in xrange (50):
tmpX, tmpY = shuffle(Xtrain, Ytrain_ind)
for j in xrange (n_batches):
x = tmpX
y = tmpY
p_y = forward(x, W, b)
W += lr*(gradW(y, p_y, x) – reg*W)
b += lr*(gradb(y, p_y) – reg*b)
p_y_test = forward(Xtest, W, b)
ll = cost(p_y_test, Ytest_ind)
LL_batch.append(ll)
if j % (n_batches/2) == 0:
err = error_rate(p_y_test, Ytest)
print “Cost at iteration %d: %.6f” % (i, ll)
print “Error rate:”, err
p_y = forward(Xtest, W, b)
print “Final error rate:”, error_rate(p_y, Ytest)
print “Elapsted time for batch GD:”, datetime.now() – t0
И в конце мы выводим все наши данные на экран.
x1 = np.linspace(0, 1, len(LL))
plt.plot(x1, LL, label =”full”)
x2 = np.linspace(0, 1, len(LL_stochastic))
plt.plot(x2, LL_stochastic, label =”stochastic”)
x3 = np.linspace(0, 1, len(LL_batch))
plt.plot(x3, LL_batch, label =”batch”)
plt.legend()
plt.show()
if __name__ == ‘__main__’:
Итак, запустим программу.
Мы можем видеть, что в случае стохастического градиентного спуска ошибка почти не улучшилась. Это значит, что необходимо намного больше итераций, чтобы добиться улучшения при стохастическом градиентном спуске. Полный градиентный спуск, как мы видим, сходится быстрее, чем пакетный, но и работает он медленнее.
Если мы посмотрим на изменение функции затрат в увеличенном масштабе, то увидим, что в случае пакетного градиентного спуска оно является не очень гладким, в отличие от полного градиентного спуска, когда функция затрат изменяется плавно, поскольку в этом случае функция затрат всегда уменьшается. В случае стохастического градиентного спуска изменение функции затрат также не плавно:
Post Views: 588
В рамках моей домашней работы меня попросили реализовать стохастический градиентный спуск, чтобы решить проблему линейной регрессии (хотя у меня всего 200 учебных примеров). Моя проблема в том, что стохастический градиентный спуск сходится слишком гладко, почти так же, как спуск градиента партии, что подводит меня к моему вопросу: почему это выглядит так гладко, учитывая тот факт, что обычно это намного более шумно. Это потому, что я использую его только с 200 примерами?
MSE с весами от стохастического градиентного спуска: 2.78441258841
MSE с весами от градиентного спуска: 2.78412631451 (идентичный MSE с весами из нормального уравнения)
Def mserror(y, y_pred): n = y.size diff = y - y_pred diff_squared = diff ** 2 av_er = float(sum(diff_squared))/n return av_er
Def linear_prediction(X, w): return dot(X,np.transpose(w))
Def gradient_descent_step(X, y, w, eta): n = X.shape grad = (2.0/n) * sum(np.transpose(X) * (linear_prediction(X,w) - y), axis = 1) return w - eta * grad
Def stochastic_gradient_step(X, y, w, train_ind, eta): n = X.shape grad = (2.0/n) * np.transpose(X) * (linear_prediction(X,w) - y) return w - eta * grad
Def gradient_descent(X, y, w_init, eta, max_iter): w = w_init errors = errors.append(mserror(y, linear_prediction(X,w))) for i in range(max_iter): w = gradient_descent_step(X, y, w, eta) errors.append(mserror(y, linear_prediction(X,w))) return w, errors
Def stochastic_gradient_descent(X, y, w_init, eta, max_iter): n = X.shape w = w_init errors = errors.append(mserror(y, linear_prediction(X,w))) for i in range(max_iter): random_ind = np.random.randint(n) w = stochastic_gradient_step(X, y, w, random_ind, eta) errors.append(mserror(y, linear_prediction(X,w))) return w, errors
1 ответ
Нет ничего необычного в вашем графике. Следует также отметить, что ваш пакетный метод требует меньше итераций для схождения.
Вы можете позволить SGD-сюжетам из нейронных сетей обладать вашим взглядом на то, что должно выглядеть SGD. Большинство нейронных сетей - это гораздо более сложные модели (их трудно оптимизировать), работающие над более сложными проблемами. Это способствует "зубчатости", которую вы ожидаете.
Линейная регрессия является простой проблемой и имеет выпуклое решение. Это означает, что любой шаг, который снизит нашу частоту ошибок, гарантированно станет шагом к наилучшему возможному решению. Это намного сложнее, чем нейронные сети, и часть того, почему вы видите плавное снижение ошибок. Вот почему вы видите почти идентичный MSE. И SGD, и пакет будут сходиться к точному решению.
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Министерство образования и науки РФ
Федеральное государственное автономное образовательное учреждение
Высшего образования
«КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
ВЫСШАЯ ШКОЛА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И ИНФОРМАЦИОННЫХ СИСТЕМ
КУРСОВАЯ РАБОТА
Стохастический градиентный спуск. Варианты реализации
Введение
Градиентный спуск -- метод нахождения локального экстремума (минимума или максимума) функции с помощью движения вдоль градиента.
Из всех методов локальной оптимизации является наиболее простым в реализации. Имеет довольно слабые условия сходимости, но при этом скорость сходимости достаточно мала.
Градиентный спуск является популярным алгоритмом для широкого спектра моделей машинного обучения, в том числе нахождение опорных векторов, логистической регрессии и графических моделей. В сочетании с алгоритмом обратного распространения, это стандартный алгоритм для обучения искусственных нейронных сетей. Стохастический градиентный спуск конкурирует с алгоритмом L-BFGS, который также широко используется. Стохастический градиентный спуск был использован, по крайней мере, в 1960 для обучения линейных регрессионных моделей, первоначально под названием Adaline.
Целью данной курсовой работы является рассмотрение реализации нескольких вариантов стохастического градиентного спуска, последующее их сравнение, выяснение преимуществ и недостатков.
1. Стохастический градиентный спуск
Стохастический градиентный спуск относится к оптимизационным алгоритмам и нередко используется для настройки параметров модели машинного обучения.
При стандартном градиентном спуске для изменения параметров модели используется градиент. Градиент обычно вычисляется как сумма градиентов, вызванных каждым элементом обучения. Вектор параметров изменяется в направлении антиградиента с заданным шагом. Поэтому стандартному градиентному спуску требуется один проход по обучающим данным до того, как он сможет менять параметры.
При стохастическом градиентном спуске значение градиента приближенно вычисляется градиентом функции стоимости, вычисленном только на одном элементе обучения. Затем параметры изменяются пропорционально приближенному градиенту. Таким образом параметры модели изменяются после каждого объекта обучения. Для больших массивов данных стохастический градиентный спуск может дать значительное преимущество в скорости по сравнению со стандартным градиентным спуском.
Между этими двумя видами градиентного спуска существует компромисс, называемый иногда «mini-batch». В этом случае градиент аппроксимируется суммой для небольшого количества обучающих образцов.
1.1 Предпосылки
Статистические оценки и машинное обучение рассматривают задачу минимизации функции, которая имеет вид:
где параметр, который сводит к минимуму, должен быть оценен. Каждое слагаемое как правило ассоциируется с i-ым наблюдением в наборе данных (используется для обучения).
В классической статистике, проблема минимизации сумм возникает в методе наименьших квадратов, а также в методе максимального правдоподобия (для независимых наблюдений). Общий класс оценок, который является результатом минимизации сумм, называется M-оценкой. Однако в статистике, уже давно признано, что требование даже локальной минимизации слишком ограничено для некоторых задач оценки максимального правдоподобия. Таким образом, современные статистические теоретики часто рассматривают стационарные точки на функции правдоподобия (нули производной, функция оценки и другие оценочные уравнения).
Проблема минимизации сумм возникает также в минимизации эмпирического риска. В этом случае,это значение функции потерь при i-омнаборе, и эмпирический риск.
При минимизации функции, стандартный (или «batch») градиентный спуск будет выполнять следующие итерации:
где это размер шага (иногда называемый скоростью обучения в машинном обучении).
Во многих случаях функция слагаемого имеет простую модель, которая включает несложные вычисления функции суммы и суммы градиентов. Например, в статистике, экспоненциальные семейства с одним параметром допускают экономичные вычисления функции и градиентов.
Тем не менее, в других случаях, оценки суммарного градиента могут потребовать дорогостоящую оценку градиентов от всех функций слагаемых. Когда обучающий набор огромен и не существует простых формул, оценка суммы градиентов становится очень дорогой, потому что оценка градиента требует оценки всех градиентов функций слагаемым. Для того, чтобы сэкономить на стоимости вычислений на каждой итерации, в стохастическом градиентном спуске выборкой является подмножество функций слагаемых на каждом шагу. Это очень эффективно в случае крупномасштабных задач машинного обучения.
1.2 Итерационный метод
В стохастическом градиентном спуске, истинный градиент приближенно выражается градиентом на данном примере:
Поскольку алгоритм несется через обучающий набор, он выполняет вышеописанные обновления для каждого учебного примера. Несколько проходов могут быть сделаны по обучающему множеству, пока алгоритм не будет сходится. Данные могут быть перемешены для каждого прохода, чтобы предотвратить циклы. Типичные реализации могут использовать адаптивную скорость обучения так, чтобы алгоритм сходился.
В псевдокоде стохастический градиентный спуск может быть представлен следующим образом:
1) Выбрать исходный вектор параметра и скорость обучения.
2) Повторять до тех пор, пока не будетприблизительно получено минимальное:
2.1) Случайно перетасовать примеры в обучающем наборе.
2.2) Для i = 1,2,...,n, делать:
Сходимость стохастического градиентного спуска была проанализирована с помощью теории выпуклой минимизации и стохастической аппроксимации. Когда скорость обучения убывает с подходящей скоростью, и при относительно слабых допущении, стохастический градиентный спуск сходится к глобальному минимуму, когда функция является выпуклой или псевдовыпуклой, а в противном случае сходится к локальному минимуму.
1.3 Варианты реализации
Множество улучшений было предложено и использовано по сравнению с основным методом стохастического градиентного спуска. В частности, в машинном обучении, необходимость установить скорость обучения (размер шага) было признано проблематичным.
Если задать этот параметр слишком большим, то это может привести к тому, что алгоритм будет расходиться. Если наоборот, то алгоритм будет медленно сходиться.
Концептуально простое расширение стохастического градиентного спуска сделать скорость обучения в виде убывающей функции, зависящая от числа итераций m.
Проделав данную операцию, видно, что первые итерации вызывают большие изменения в параметрах, в то время как более поздние делают более только тонкую настройку.
В рамках данной работы будут рассмотрены следующие варианты реализации стохастического градиентного спуска:
1. 4 Momentum
Momentum, так же известный как метод импульса, появился благодаря американскому психологу Дэвиду Рамелхарту, а также на основе работ Джеффри Хинтонаи Роналда J Уильям саприизучении метода обратного распространения. Стохастический градиентный спуск с импульсом запоминает обновления на каждой итерации, и определяет следующее обновление в виде линейной комбинации градиента и предыдущего обновления:
Что приводит к:
где параметр, который сводит к минимуму, должен быть оценен иразмер шага (иногда называемый скоростью обучения в машинном обучении).
Название импульс происходит по аналогии с импульсом в физике: вектор веса. Мысль о том, что перемещение материальной точки через пространство параметров, влечет за собой ускорение благодаря силе, в качестве которой выступает градиент потерь.
В отличие от классического метода стохастического градиентного спуска, он стремится держать движение в одном направлении, предотвращая колебания. Momentum был успешно применен в течение нескольких десятилетий.
1.5 AdaGrad
AdaGrad представляет собой модифицированный стохастический градиентный спуск с предварительным параметром скорости обучения. Впервые опубликован в 2011. Неформально, он увеличивает скорость обучения для более разреженных параметров и уменьшает скорость обучения менее разреженный из них. Эта стратегия часто повышает вероятность сходимости по сравнению со стандартным алгоритмом стохастического градиентного спуска в тех местах, где данные немногочисленны и редкие параметры являются более информативными.
Примеры таких применений включают обработку естественного языка и распознавание образов.
Он по-прежнему имеет базу скорости обучения, но умножается на элементы вектора, который является диагональю тензорного произведения матрицы.
где градиент при итерации m.
Диагональ задается в виде:
Вектор обновляется после каждой итерации. Формула для обновления теперь выглядит так:
или записывается в виде обновления предварительного параметра,
Каждый повышает масштабируемость коэффициента для скорости обучения, который применяется к одному параметру.
Так как знаменатель является евклидовой нормой предыдущих производных, предельные значения параметров обновления сдерживают, в то время как параметры, у которых были небольшие обновления получают более высокий уровень обучения.
В то время как велась работа над проблемами выпуклой оптимизации, AdaGrad был успешно использован к задачам невыпуклой оптимизации.
1.6 RMSProp
RMSProp также является способом, в котором скорость обучения адаптирована для каждого из параметров. Идея заключается в том, чтобы разделить скорость обучения для определенного веса на скользящую среднюю величин последних градиентов для этого веса. Таким образом, первая скользящая средняя рассчитывается в виде квадрата:
где это параметр экспоненциального взвешивания, или параметр «забывания» («forgetting factor»)
Параметры обновляются с помощью формулы ниже:
RMSProp показал отличную адаптацию скорости обучения в различных приложениях. RMSProp можно рассматривать как обобщение Rprop и так же он способен работать с таким вариантом градиентного спуска как mini-batch, который противопоставлен обычному градиентному спуску.
2. Реализация стохастического градиентного спуска
На данном этапе будут выполнены реализации нескольких вариантов стохастического градиентного в виде программного кода на языке программирования Python.
2.1 Реализация стандартного стохастического градиентного спуска
Во-первых, нужен набор данных. В данном случае создаетсянабор данных с помощью библиотеки Scikit-Learn:
градиент стохастический алгоритм обучение
from sklearn.datasets import make_moons
from sklearn.cross_validation import train_test_split
X, y = make_moons(n_samples=5000, random_state=42, noise=0.1)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)
Вот что мы получили:
Рисунок 1 - Графическое представление набора данных
Далее, определяется модель нейронной сети. Это будет три слоя сети (один скрытый слой):
import numpy as np
def make_network(n_hidden=100):
model = dict(W1=np.random.randn(n_feature, n_hidden),
W2=np.random.randn(n_hidden, n_class)
Также определяется две операции: прямое распространение и обратное распространение. Сначала сделаем первый вариант:
return np.exp(x) / np.exp(x).sum()
def forward(x, model):
h = x @ model["W1"]
prob = softmax(h @ model["W2"])
Схема должна сделать ряд точек от входа до скрытого слоя и потом к выходному слою. В скрытом слое, также может примениться нелинейность, так чтобы нейронная сеть могла предсказать нелинейную границу решения. Ярким представителем нелинейной функции на сегодняшний день является ReLU.
ReLU определяется как f(x)=max(0,x), но, вместо того, чтобы делать np.max(0, x), есть ловкий трюк реализации: x = 0.
После того, как был достигнут выходной слой, выходные данные должны быть такими, чтобы распределение вероятностей Бернулли было точным, поэтому выходные данные разжимаются с помощью функции SoftMax, чтобы получить заданное распределение.
Теперь определяется вторая операция. Обратное распространение выглядит следующим образом:
def backward(model, xs, hs, errs):
dW2 = hs.T @ errs
dh = errs @ model["W2"].T
dh = 0
return dict(W1=dW1, W2=dW2)
Создаётся основа алгоритма. Выполняется реализация функцииsgd. Выглядит она так:
def sgd(model, X_train, y_train, batch_size):
for iter in range(n_iter):
print("Iteration {}".format(iter))
X_train, y_train = shuffle(X_train, y_train)
for i in range(0, X_train.shape, batch_size):
X_train_mini = X_train
y_train_mini = y_train
model = sgd_step(model, X_train_mini, y_train_mini)
return model
Выполняется реализация функции sgd_step. Выглядит она так:
def sgd_step(model, X_train, y_train):
grad = get_batch_grad(model, X_train, y_train)
model = model.copy()
for layer in grad:
model += learning_rate * grad
Выполняется реализация функции get_batch_grad. Выглядит она так:
def get_batch_grad(model, X_train, y_train):
xs, hs, errs = , ,
for x, cls_idx in zip(X_train, y_train):
h, y_pred = forward(x, model)
y_true = np.zeros(n_class)
y_true = 1.
err = y_true - y_pred
errs.append(err)
return backward(model, np.array(xs), np.array(hs), np.array(errs))
В этой функции перебирается каждая точка данных в batch, затем отправляется в сеть и сравнивается результат истинной метки стой, что была получена обучающими данными. Ошибка определяется разностью вероятности истинной метки и вероятности нашего прогноза.
2.2 Реализация Momentum
Momentum работает по принципу физического закона движения, он проходит через локальные оптимумы (небольшие холмы). Добавление импульса будет приводить к тому, что сходимость алгоритма будет происходить быстрее, так как происходит накопление скорости и шаг метода может быть больше, чем постоянный шаг в обычном методе.
Учитывая, что заготовок программы уже готов, нужно реализовать лишь основную функцию данного метода. Функция momentum приведена ниже:
def momentum(model, X_train, y_train, batch_size):
velocity = {k: np.zeros_like(v) for k, v in model.items()}
gamma =.9
X_mini, y_mini = batches
for layer in grad:
velocity = gamma * velocity + alpha * grad
model += velocity
Включается новая переменная velocity, которая будет накапливать импульс для каждого параметра. Обновление переменной будет происходить слагаемым alpha*grad на каждом новом шаге градиентного спуска. Так же происходит небольшое уменьшение с помощью коэффициента gamma значения переменной velocity, которая была вычислена на предыдущем шаге.
2.3 Реализация AdaGrad
До сих пор была игнорирована скорость обучения alpha, потому как она была постоянной. Проблема возникает в том, что скорость обучения влияет на все параметры и не всегда при постоянной скорости обучения алгоритм работает эффективно. Решением данной проблемы может выступать AdaGrad.
При использовании AdaGrad обновление параметров происходит точечно, поэтому скорость обучения является адаптивным параметром.
Выполняется реализация данного метода. Вся программа готова, нужно лишь изменить основную функцию. Называться она будетadagrad. Функция представлена ниже:
def adagrad(model, X_train, y_train, batch_size):
batches = get_batch(X_train, y_train, batch_size)
for iter in range(1, n_iter + 1):
idx = np.random.randint(0, len(batches))
X_mini, y_mini = batches
grad = get_batch_grad(model, X_mini, y_mini)
cache[k] += grad[k]**2
return model
Можно заметить, что происходит нормализация скорости обучения. Она теперь может быть больше или меньше в зависимости от того, как ведут себя последние градиенты.
2.4 Реализация RMSProp
Можно заметить, что в накопительной части Adagrad, значение cache[k] += grad[k]**2 монотонно возрастает в следствие суммы и квадрата. Это может быть проблематичным, так как скорость обучения будет монотонно убывать к очень крошечной скорости обучения.
Для борьбы с этой проблемой, RMSProp раскладывает прошлое накопленное значение градиента, так чтобы рассматривалась только часть последних градиентов. Теперь, вместо того, чтобы рассматривать все последние градиенты, RMSProp ведет себя как скользящая средняя.
Выполняется реализация данного метода. Вся программа готова, нужно лишь изменить основную функцию. Называться она будетrmsprop. Функция представлена ниже:
def rmsprop(model, X_train, y_train, batch_size):
cache = {k: np.zeros_like(v) for k, v in model.items()}
gamma =.9
batches = get_batch(X_train, y_train, batch_size)
for iter in range(1, n_iter + 1):
idx = np.random.randint(0, len(batches))
X_mini, y_mini = batches
grad = get_batch_grad(model, X_mini, y_mini)
cache[k] = gamma * cache[k] + (1 - gamma) * (grad[k]**2)
model[k] += alpha * grad[k] / (np.sqrt(cache[k]) + eps)
Основное отличие в вычислении значения cache[k] и теперь накопленное значение градиента не будет агрессивно монотонно возрастать.
3. Тестирование и сравнение
В данной главе будет проводиться тестирование реализации и анализ полученных результатов.
3.1 Тестирование стандартного стохастического градиентного спуска
На данном этапе будет проводиться тестирование стандартного стохастического градиентного спуска. Процедура будет выполняться 100 раз и затем будет вычислено среднее значение точности.
n_experiment = 100
accs = np.zeros(n_experiment)
for k in range(n_experiment):
model = make_network()
model = sgd(model, X_train, y_train, minibatch_size)
prob = forward(x, model)
y = np.argmax(prob)
Выполнив данный код, я получил следующие значения:
Средняя точность: 0.8765040000000001
Таким образом, можно сделать вывод, что в среднем точность выполнения 87%.
3.2 Тестирование Momentum
На данном этапе будет проводиться тестирование стохастического градиентного спуска на основе реализации Momentum. Процедура будет выполняться 100 раз и затем будет вычислено среднее значение точности.
Программа для тестирования приведена ниже:
n_experiment = 100
accs = np.zeros(n_experiment)
for k in range(n_experiment):
model = make_network()
model = momentum(model, X_train, y_train, minibatch_size)
y_pred = np.zeros_like(y_test)
for i, x in enumerate(X_test):
prob = forward(x, model)
y = np.argmax(prob)
accs[k] = (y_pred == y_test).sum() / y_test.size
print("Средняя точность: {}, Полученное значение: {}".format(accs.mean(), accs.std()))
Средняя точность:
1) 0.3152, при alpha = 0.5
2) 0.8554666666666666, при alpha = 1e-2
3) 0.8613333333333334, при alpha = 1e-5
Таким образом, можно сделать вывод, что при более низких значениях скорости обучения точность выполнения заметно выше.
3.3 Тестирование AdaGrad
На данном этапе будет проводиться тестирование стохастического градиентного спуска на основе реализации AdaGrad. Процедура будет выполняться 100 раз и затем будет вычислено среднее значение точности.
Программа для тестирования приведена ниже:
n_experiment = 100
accs = np.zeros(n_experiment)
for k in range(n_experiment):
model = make_network()
model = adagrad(model, X_train, y_train, minibatch_size)
y_pred = np.zeros_like(y_test)
for i, x in enumerate(X_test):
prob = forward(x, model)
y = np.argmax(prob)
accs[k] = (y_pred == y_test).sum() / y_test.size
print("Средняя точность: {}, Полученное значение: {}".format(accs.mean(), accs.std()))
Выполнив данный код, получены следующие значения:
Средняя точность:
1) 0.8754666666666667, при alpha = 0.5
2) 0.8786666666666667, при alpha = 1e-2
3) 0.504, при alpha = 1e-5
Таким образом, можно сделать вывод, что при очень низких значениях скорости обучения точность выполнения сильно уменьшается.
3.4 Тестирование RMSProp
На данном этапе будет проводиться тестирование стохастического градиентного спуска на основе реализации RMSProp. Процедура будет выполняться 100 раз и затем будет вычислено среднее значение точности.
Программа для тестирования приведена ниже:
n_experiment = 100
accs = np.zeros(n_experiment)
for k in range(n_experiment):
model = make_network()
model = rmsprop(model, X_train, y_train, minibatch_size)
y_pred = np.zeros_like(y_test)
for i, x in enumerate(X_test):
prob = forward(x, model)
y = np.argmax(prob)
accs[k] = (y_pred == y_test).sum() / y_test.size
print("Средняя точность: {}, Полученное значение: {}".format(accs.mean(), accs.std()))
Выполнив данный код, получены следующие значения:
Средняя точность:
1) 0.8506666666666667, при alpha = 0.5
2) 0.8727999999999999, при alpha = 1e-2
3) 0.30693333333333334, при alpha = 1e-5
Таким образом, можно сделать вывод, что при очень низких значениях скорости обучения точность его выполнения аналогично AdaGrad сильно уменьшается.
Заключение
Из сравнительного анализа понятно, что при использовании большого значения скорости обучения, методы с адаптивной скоростью обучения выигрывают у методов с постоянной скоростью обучения.
Однако при использовании небольшого значения скорости обучения происходит обратное, например, 1e-5. Для стандартного варианта стохастического градиентного спуска и метода импульса достаточно малые значения позволяют им хорошо работать. С другой стороны, если скорость обучения очень мала, и происходит ее нормализация в адаптивных методах скорости обучения, то она становится еще меньше, что влияет на скорость сходимости. Это делает обучение очень медленным, и данные методы работают хуже, чем стандартный стохастический градиентный спуск с тем же числом итераций.
Список использованных источников
1. Machinelearning - Стохастический градиентный спуск
2. Искусственный интеллект по-русски - Градиентные спуски
3. Вики учебник - Реализации алгоритмов/Градиентный спуск
4. Stanford University - Adaptive Subgradient Methods
5. Cambridge University Press - Online Algorithms and Stochastic Approximations
6. Sanjoy Dasgupta and David Mcallester - On the importance of initialization and momentum in deep learning [Электронный ресурс].
Размещено на Allbest.ru
...Подобные документы
Необходимые условия экстремума. Разработка машинного алгоритма и программы многомерной оптимизации для градиентного метода с использованием метода равномерного поиска. Проверка необходимых и достаточных условий экстремума для найденной точки минимума.
курсовая работа , добавлен 25.09.2013
Программная реализация приложения для вычисления заданных функций. Процедура поиска минимума функции. Применение методов Хука-Дживса и градиентного спуска для решения задачи. Исследование функции в окрестности базисной точки, определение ее координат.
контрольная работа , добавлен 02.02.2014
Оптимизация решения задачи с помощью алгоритма отжига. Анализ теории оптимизации как целевой функции. Метод градиентного спуска. Переменные и описание алгоритма отжига. Представление задачи коммивояжера через граф. Сведение задачи к переменным и решение.
курсовая работа , добавлен 21.05.2015
Обучение простейшей и многослойной искусственной нейронной сети. Метод обучения перцептрона по принципу градиентного спуска по поверхности ошибки. Реализация в программном продукте NeuroPro 0.25. Использование алгоритма обратного распространения ошибки.
курсовая работа , добавлен 05.05.2015
Решение задачи на тему максимизации функций многих переменных. Описание метода дихотомии, его применение для решения нелинейных уравнений. Решение данной задачи с использованием метода покоординатного спуска. Составление алгоритмов, листинг программы.
курсовая работа , добавлен 01.10.2009
Идентификация объектов методом наименьших квадратов. Анализ коэффициентов парной, частной и множественной корреляции. Построение линейной модели и модели с распределенными параметрами. Итерационный численный метод нахождения корня (нуля) заданной функции.
курсовая работа , добавлен 20.03.2014
Основа технологии использования программного комплекса LabVIEW, достоинства системы. Программирование, основанное на архитектуре потоков данных. Методы нахождения экстремума. Использование метода Гаусса-Зейделя для поиска максимума двумерной функции.
контрольная работа , добавлен 18.03.2011
Назначение и классификация методов поисковой оптимизации. Эффективность поискового метода. Методы поиска нулевого порядка: исходные данные, условия, недостатки и применение. Структура градиентного метода поиска. Основная идея метода наискорейшего спуска.
лекция , добавлен 04.03.2009
Постановка задачи и ее формализация. Поиск значений интерполяционного многочлена в точках x1 и x2. Поиск минимума функции F(x) на отрезке . Проверка условий сходимости методов. Тестирование программных модулей. Детализированная схема алгоритма.
курсовая работа , добавлен 04.02.2011
Численные методы в задачах без ограничений. Схема методов спуска. Среда редактора Visual Basic. Использование объектов ActiveX в формах. Блок-схема алгоритма моделирования. Задачи оптимизирования детерменированных функций с единственной точкой экстремума.
где f i – функция, подсчитанная на i-м батче, i выбирается случайным образом;
Шаг обучения является гиперпараметром; при слишком больших значениях алгоритм обучения будет расходиться, при слишком маленьких – будет сходиться медленно.
Стохастический градиентный спуск с инерцией
В методе стохастического градиентного спуска нередка ситуация, когда градиент на каждой итерации изменяется в большой степени. Это происходит из-за того, что функционал вычисляется на различных данных, которые могут в значительной степени отличаться. Такое изменение можно сгладить, если использовать градиенты, вычисленные на предыдущих итерациях и масштабированные на гиперпараметр инерции μ:
 | (14) |
 | (15) |
Как несложно догадаться, гиперпараметр инерции μ имеет такое название из-за того, что, подобно так называемой ньютоновой силе инерции, т.е. силе противодействия, «сопротивляется» изменениям градиента и смягчает изменения весовых коэффициентов на протяжении обучения. Такой алгоритм обучения называется стохастическим градиентным спуском с инерцией или SGDМ (stochastic gradient descent with momentum).
Метод адаптивного градиента
Метод адаптивного градиента (Adagrad – от англ. «adaptive gradient algorithm») основан на идее масштабирования. Он перемасштабирует скорость обучения для каждого настраиваемого параметра в отдельности, при этом учитывая историю всех прошлых градиентов для этого параметра. Для этого каждый элемент градиента делится на квадратный корень от суммы квадратов предыдущих соответствующих элементов градиента. Такой подход эффективно уменьшает скорость обучения для тех весовых коэффициентов, которые имеют большое значение градиента, а также со временем снижает скорость обучения для всех параметров, так как сумма квадратов неуклонно увеличивается для всех параметров при каждой итерации. При задании нулевого начального масштабирующего параметра g = 0 формула для пересчета весовых коэффициентов имеет вид (деление выполняется поэлементно).
