Стохастический градиентный спуск алгоритм. Градиентный спуск – полный, пакетный и стохастический
В этой лекции мы обсудим различные способы реализации , об их достоинствах и недостатках. Я бы хотел поговорить о трёх основных типах градиентного спуска – полном, пакетном и стохастическом.
В большинстве предыдущих курсов мы пользовались полным градиентным спуском.
Почему именно так?
Потому что это приносит больше пользы, если мы хотим максимизировать правдоподобие для всего учебного набора:
Недостатком такого подхода является то, что вычисление градиента занимает много времени, поскольку он зависит от каждого примера (наблюдения).
Полной противоположностью является стохастический градиентный спуск. Он зависит от ошибки лишь для одного конкретного наблюдения:
Метод основывается на том факте, что все наблюдения являются независимыми и равномерно распределёнными, поэтому в долгосрочной перспективе ошибка будет уменьшаться, ведь все наблюдения берутся из одного и того распределения. В таком случае, когда расчёты сократились от 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
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на 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 в пространстве все возможных точек. График F представляет собой параболическую поверхность, и у неё должен быть один-единственный минимум. А вопрос о том, как исправлять точки так, чтобы двигаться в сторону этого минимума, давным-давно решён в математическом анализе. Для этого нужно двигаться в направлении, противоположном градиенту - вектору, вдоль которого производная максимальна. Градиент вычисляется следующим образом:
Т.е. для вычисления градиента мы должны использовать производную от заданной функции при соответствующих точках (переменных).
Таким образом, чтобы определить, как правильно исправлять координаты точек, мы должны вычислить градиент и отнять вектор какой-нибудь наперёд заданной длины (в нашем случае этой длинной выступает заданный шаг а) от имеющегося вектора точек:
Чтобы реализовать это программно, нужно научиться дифференцировать функцию F:
Пример 1 - алгоритм градиентного спуска для одной точки.
GradientDescent()
- 1. Инициализировать маленькими случайными значениями.
- 2. Повторить Number_of_Steps раз:
- а) Для всех i от 1 до n
- б) Для всех j
от 1 до m
:
- (i) Для всех i от 1 до n
- 3. выдать значения.
Это значит, что нам нужно подправлять координаты точек после каждого тестового примера так:
Новый, изменённый алгоритм показан в примере 1. Правда, нужно внести и другие изменения. Во-первых, мы больше не можем рассчитывать на то, что в какой-то момент достигнем идеальной гармонии с исходными данными, и нам нужно научиться останавливаться в какой-то момент. В качестве условия для остановки здесь принято то, что алгоритм выполняется пока разности значений функции меньше ранее заданной точности. Другое изменение - в том, что если оставлять а постоянным, то на каком-то этапе точка перестанет приближаться к искомому минимуму, а начнёт его «перепрыгивать» на каждой итерации, то в одну сторону, то в другую. Поэтому a нужно уменьшать со временем. В данной программе мы уменьшаем шаг на два.
Этот алгоритм может находить локальные минимумы (у рассматривавшегося нами параболоида есть один локальный минимум). Его отличие в том, что он не собирает всю информацию со всех тестовых примеров, а модифицирует точки сразу же, после каждого шага итерации.
SVM
Метод опорных векторов (англ. SVM, support vector machine) -- набор схожих алгоритмов обучения с учителем, использующихся для задач классификации и регрессионного анализа. Принадлежит к семейству линейных классификаторов, может также рассматриваться как специальный случай регуляризации по Тихонову. Особым свойством метода опорных векторов является непрерывное уменьшение эмпирической ошибки классификации и увеличение зазора, поэтому метод также известен как метод классификатора с максимальным зазором.
Основная идея метода -- перевод исходных векторов в пространство более высокой размерности и поиск разделяющей гиперплоскости с максимальным зазором в этом пространстве. Две параллельных гиперплоскости строятся по обеим сторонам гиперплоскости, разделяющей наши классы. Разделяющей гиперплоскостью будет гиперплоскость, максимизирующая расстояние до двух параллельных гиперплоскостей. Алгоритм работает в предположении, что чем больше разница или расстояние между этими параллельными гиперплоскостями, тем меньше будет средняя ошибка классификатора.
Часто в алгоритмах машинного обучения возникает необходимость классифицировать данные. Каждый объект данных представлен как вектор (точка) в -мерном пространстве (последовательность p чисел). Каждая из этих точек принадлежит только одному из двух классов. Нас интересует, можем ли мы разделить точки гиперплоскостью размерностью Это типичный случай линейной разделимости. Таких гиперплоскостей может быть много. Поэтому вполне естественно полагать, что максимизация зазора между классами способствует более уверенной классификации. То есть можем ли мы найти такую гиперплоскость, чтобы расстояние от неё до ближайшей точки было максимальным. Это бы означало, что расстояние между двумя ближайшими точками, лежащими по разные стороны гиперплоскости, максимально. Если такая гиперплоскость существует, то она нас будет интересовать больше всего; она называется оптимальной разделяющей гиперплоскостью, а соответствующий ей линейный классификатор называется оптимально разделяющим классификатором.
Формально можно описать задачу следующим образом.
Полагаем, что точки имеют вид: , где принимает значение 1 или?1, в зависимости от того, какому классу принадлежит точка. Каждое -- это -мерный вещественный вектор, обычно нормализованный значениями или. Если точки не будут нормализованы, то точка с большими отклонениями от средних значений координат точек слишком сильно повлияет на классификатор. Мы можем рассматривать это как учебную коллекцию, в которой для каждого элемента уже задан класс, к которому он принадлежит. Мы хотим, чтобы алгоритм метода опорных векторов классифицировал их таким же образом. Для этого мы строим разделяющую гиперплоскость, которая имеет вид:
Вектор -- перпендикуляр к разделяющей гиперплоскости. Параметр равен по модулю расстоянию от гиперплоскости до начала координат. Если параметр равен нулю, гиперплоскость проходит через начало координат, что ограничивает решение.
Так как нас интересует оптимальное разделение, нас интересуют опорные вектора и гиперплоскости, параллельные оптимальной и ближайшие к опорным векторам двух классов. Можно показать, что эти параллельные гиперплоскости могут быть описаны следующими уравнениям (с точностью до нормировки).
Если обучающая выборка линейно разделима, то мы можем выбрать гиперплоскости таким образом, чтобы между ними не лежала ни одна точка обучающей выборки и затем максимизировать расстояние между гиперплоскостями. Ширину полосы между ними легко найти из соображений геометрии, она равна, таким образом наша задача минимизировать. Чтобы исключить все точки из полосы, мы должны убедиться для всех, что
Это может быть также записано в виде:
В случае линейной разделимости классов, проблема построения оптимальной разделяющей гиперплоскости сводится к минимизации при условии (1). Это задача квадратичной оптимизации, которая имеет вид:
По теореме Куна -- Таккера эта задача эквивалентна двойственной задаче поиска седловой точки функции Лагранжа.
Где -- вектор двойственных переменных
Сведем эту задачу к эквивалентной задаче квадратичного программирования, содержащую только двойственные переменные:
Допустим мы решили данную задачу, тогда и можно найти по формулам:
В итоге алгоритм классификации может быть записан в виде:
При этом суммирование идет не по всей выборке, а только по опорным векторам, для которых
В случае линейной неразделимости классов, для того, чтобы алгоритм мог работать, позволим ему допускать ошибки на обучающей выборке. Введем набор дополнительных переменных, характеризующих величину ошибки на объектах. Возьмем за отправную точку (2), смягчим ограничения неравенства, так же введём в минимизируемый функционал штраф за суммарную ошибку:
Коэффициент -- параметр настройки метода, который позволяет регулировать отношение между максимизацией ширины разделяющей полосы и минимизацией суммарной ошибки.
Аналогично, по теореме Куна-Таккера сводим задачу к поиску седловой точки функции Лагранжа:
По аналогии сведем эту задачу к эквивалентной:
На практике для построения машины опорных векторов решают именно эту задачу, а не (3), так как гарантировать линейную разделимость точек на два класса в общем случае не представляется возможным. Этот вариант алгоритма называют алгоритмом с мягким зазором (soft-margin SVM), тогда как в линейно разделимом случае говорят о жёстком зазоре (hard-margin SVM).
Для алгоритма классификации сохраняется формула (4), с той лишь разницей, что теперь ненулевыми обладают не только опорные объекты, но и объекты-нарушители. В определённом смысле это недостаток, поскольку нарушителями часто оказываются шумовые выбросы, и построенное на них решающее правило, по сути дела, опирается на шум.
Константу обычно выбирают по критерию скользящего контроля. Это трудоёмкий способ, так как задачу приходится решать заново при каждом значении.
Если есть основания полагать, что выборка почти линейно разделима, и лишь объекты-выбросы классифицируются неверно, то можно применить фильтрацию выбросов. Сначала задача решается при некотором C, и из выборки удаляется небольшая доля объектов, имеющих наибольшую величину ошибки. После этого задача решается заново по усечённой выборке. Возможно, придётся проделать несколько таких итераций, пока оставшиеся объекты не окажутся линейно разделимыми.
Алгоритм построения оптимальной разделяющей гиперплоскости, предложенный в 1963 году Владимиром Вапником и Алексеем Червоненкисом -- алгоритм линейной классификации. Однако в 1992 году Бернхард Босер, Изабелл Гийон и Вапник предложили способ создания нелинейного классификатора, в основе которого лежит переход от скалярных произведений к произвольным ядрам, так называемый kernel trick (предложенный впервые М.А. Айзерманом, Э.М. Браверманном и Л.В. Розоноэром для метода потенциальных функций), позволяющий строить нелинейные разделители. Результирующий алгоритм крайне похож на алгоритм линейной классификации, с той лишь разницей, что каждое скалярное произведение в приведённых выше формулах заменяется нелинейной функцией ядра (скалярным произведением в пространстве с большей размерностью). В этом пространстве уже может существовать оптимальная разделяющая гиперплоскость. Так как размерность получаемого пространства может быть больше размерности исходного, то преобразование, сопоставляющее скалярные произведения, будет нелинейным, а значит функция, соответствующая в исходном пространстве оптимальной разделяющей гиперплоскости, будет также нелинейной.
Стоит отметить, что если исходное пространство имеет достаточно высокую размерность, то можно надеяться, что в нём выборка окажется линейно разделимой.
Наиболее распространённые ядра:
1. Линейное ядро:
2. Полиномиальное (однородное):
3. RBF функция:
4. Сигмоид:
В рамках поставленной перед нами задачи будем использовать линейное однородное ядро. Данное ядро показало отличные результаты в задачах Document Classification, хотя по сравнению с Наивным Байесовским Классификатором обучение данного классификатора занимается сравнительно большой промежуток времени. Также проверена работа всех остальных ядер из данного списка и выявлено, что их обучение занимает значительно больший промежуток времени, при этом не привнося особых улучшений в точности классификации.
Для ускорения обучения мы будем использовать метод под названием Стохастический Градиентный Спуск, который позволяет значительно ускорить обучение классификатора, не сильно жертвуя его точностью.
Стохастический Градиентный Спуск
Градиентные методы - это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении. Здесь градиентный подход будет рассмотрен в качестве способа подбора вектора синаптических весов в линейном классификаторе. Пусть - целевая зависимость, известная только на объектах обучающей выборки:
Найдём алгоритм, аппроксимирующий зависимость. В случае линейного классификатора искомый алгоритм имеет вид:
где играет роль функции активации (в простейшем случае можно положить).
Согласно принципу минимизации эмпирического риска для этого достаточно решить оптимизационную задачу:
Где - заданная функция потерь.
Для минимизации применим метод градиентного спуска (gradient descent). Это пошаговый алгоритм, на каждой итерации которого вектор изменяется в направлении наибольшего убывания функционала (то есть в направлении антиградиента):
Где - положительный параметр, называемый темпом обучения (learning rate).
Возможны 2 основных подхода к реализации градиентного спуска:
1. Пакетный (batch), когда на каждой итерации обучающая выборка просматривается целиком, и только после этого изменяется. Это требует больших вычислительных затрат.
2. Стохастический (stochastic/online), когда на каждой итерации алгоритма из обучающей выборки каким-то (случайным) образом выбирается только один объект. Таким образом вектор настраивается на каждый вновь выбираемый объект.
Можно представить алгоритм стохастического градиентного спуска в виде псевдокода следующим образом:
· - обучающая выборка
· - темп обучения
· - параметр сглаживания функционала
1. Вектор весов
1) Инициализировать веса
2) Инициализировать текущую оценку функционала:
3) Повторять:
1. Выбрать объект из случайным образом
2. Вычислить выходное значение алгоритма и ошибку:
3. Сделать шаг градиентного спуска
4. Оценить значение функционала:
4) Пока значение не стабилизируется и/или веса не перестанут изменяться.
Главным достоинством SGD можно назвать его скорость обучения на избыточно больших данных. Именно это интересно для нас в рамках поставленной перед нами задачи ибо объем входных данных будет весьма велик. В то же время, алгоритм SGD в отличие от классического пакетного градиентного спуска дает несколько меньшую точность классификации. Также алгоритм SGD неприменим при обучении машины опорных векторов с нелинейным ядром.
Выводы
В рамках решаемой задачи нам потребуется воспользоваться алгоритмом преобразования исходных данных TF-IDF, который позволит нам повысить весомость редких событий и снизить вес частых событий. Полученные после преобразования данные мы будем передавать классификаторам, которые подходят для решения стоящей перед нами задачи, а именно: Наивный Байесовский Классификатор или Машина Опорных Векторов с Линейным ядром, обученная по методу стохастического градиентного спуска. Также мы осуществим проверку эффективности Машины Опорных Векторов с нелинейными ядрами, обученной по методу пакетного градиентного спуска. Однако, данный тип классификатора не кажется подходящим для поставленной задачи в силу слишком сложного ядра и склонности к переобучаемости, при которой классификатор плохо справляется с данными, которые не использовались для обучения классификатора.
программный машинный предобработка данный
Итак, у вас есть задача предсказать какое-то значение вроде стоимости дома по его размеру. Или время обработки какого-то запроса вашей системой. Да мало ли что.
Вы решили воспользоваться линейной регрессией и теперь хотите найти коэффициенты , при которых разница между ценой, которую предсказывает ваша модель, и реальной стоимостью проданных домов будет минимальной. Для этого вы можете использовать один из таких методов:
- Batch Gradient Descent (общий градиентный спуск)
- Stochastic Gradient Descent (стохастический градиентный спуск)
- Normal Equations (нормальные уравнения)
- Newton’s Method (метод Ньютона)
Сегодня мы поговорим о двух видах градиентного спуска.
Gradient Descent
Что вообще такое градиентный спуск?
Представьте себе какую-то сложную функцию от одной переменной. У нее есть какие-то максимумы и минимумы. В каждой точке этой функции мы можем взять производную:
Зеленая линия показывает, что в этой точке производная будет положительной, красная – отрицательной.
Выберите любую точку на функции. Вы хотите «спуститься» до ближайшего к этой точке минимума. Если производная в вашей точке положительная (зеленая линия), это значит, что минимум находится «позади» вас, и чтобы спуститься к нему, вам надо отнять от координаты вашей точки x значение вашей производной.
Если же в вашей точке производная отрицательная (красная линия), это значит, что минимум находится «перед» вами, и чтобы прийти к нему, вам надо, снова-таки, отнять от координаты x значение вашей производной. Значение ее отрицательное, и потому, отнимая отрицательное значение, вы будете увеличивать координату x .
Ну, а чтобы спуск не был мучительно долгим или ошибочно быстрым, умножьте значение вашей производной в выбранной точке на какой-то коэффициент.
Но это все для случая, когда функция зависит от одной координаты. В случае нашей модели для продажи домов функция стоимости зависит от двух переменных.
Вы можете представить эту функцию как «чашку» в трехмерном пространстве:
Производная функций от нескольких переменных называется градиентом. Градиент – это вектор размерностью в количество переменных, в котором каждый элемент вектора – производная от какой-то одной переменной.
Наша функция стоимости имеет вид:
Ее градиент обозначается как и будет вычисляться по такой формуле:
В каждой частной производной мы считаем ее от какой-то одной переменной. Все прочие переменные считаем константами, следовательно, их производные будут равны нулю:
После этого мы обновляем каждое значение по формуле:
Параметр называется learning rate и определяет, насколько быстро мы будем двигаться к минимальному значению функции. С каждым обновлением параметров мы делаем маленький шаг в сторону минимума. После этого повторяем процедуру. Параллельно с этим смотрим, насколько изменилось значение функции стоимости сравнительно с предыдущим шагом. Когда это изменение становится очень маленьким (мы топчемся на месте), мы можем останавливаться и считать, что пришли в точку минимума.
Это похоже на спуск с холма в направлении ближайшей ложбины. Градиентный спуск позволяет вам найти локальный минимум, но не глобальный. Это значит, что если есть несколько точек, в которых ваша функция минимальна, градиентный спуск приведет вас в одну из них – ту, которая ближе всего к точке старта, но вовсе не обязательно – в самую глубокую расщелину.
Перед самым первым шагом мы определяем параметры случайным образом, и от того, как именно мы их определим, зависит, в какой именно минимум попадем:
Здесь в скобках надо заметить, что вышеописанное касается градиентного спуска в общем виде, но не касается градиентного спуска конкретно для линейной регрессии. Функция стоимости линейной регрессии выпуклая и имеет только один минимум (вспомните трехмерную чашку), потому градиентный спуск всегда найдет его.
Чем ближе вы подбираетесь к минимуму функции стоимости (чем меньше разница между предсказанной ценой и реальной), тем лучше ваша прямая описывает ваши исторические данные:
Когда исторических примеров не много, все в порядке, но когда их миллионы, для каждого маленького шага к минимуму мы должны проделать миллионы вычислений, и это может занимать долгое время.
Альтернативой этому может быть stochastic gradient descent – метод, при котором мы берем какой-то один пример и обновляем значения , ориентируясь только на него. Потом берем следующий пример и обновляем параметры, ориентируясь уже на него. И так далее. Это приводит к тому, что мы не всегда «спускаемся» с холма, иногда мы делаем и шаг вверх или в сторону, но рано или поздно мы достигаем того самого минимума и начинаем кружить вокруг него. Когда значения начинают нас устраивать (достигают нужной нам точности), мы останавливаем спуск.
В псевдокоде stochastic gradient descent выглядит так:
Until Cost Function change is small: {
For j:= 1 to m {
Напоследок, особенности схождения алгоритма: batch gradient descent всегда сходится к минимуму при условии, что используется достаточно маленькое значение . Stochastic gradient descent в общем виде не сходится к минимуму, но есть его модификации, которые позволяют добиться сходимости.
Загрузка...
