Размещено на 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) Momentum

2) AdaGrad

3) RMSProp

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

n_feature = 2

n_class = 2

n_iter = 10

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 model

Также определяется две операции: прямое распространение и обратное распространение. Сначала сделаем первый вариант:

def softmax(x):

return np.exp(x) / np.exp(x).sum()

def forward(x, model):

h = x @ model['W1']

h[h < 0] = 0

prob = softmax(h @ model['W2'])

return h, prob

Схема должна сделать ряд точек от входа до скрытого слоя и потом к выходному слою. В скрытом слое, также может примениться нелинейность, так чтобы нейронная сеть могла предсказать нелинейную границу решения. Ярким представителем нелинейной функции на сегодняшний день является ReLU.



ReLU определяется как f(x)=max(0,x), но, вместо того, чтобы делать np.max(0, x), есть ловкий трюк реализации: x[x < 0] = 0.

После того, как был достигнут выходной слой, выходные данные должны быть такими, чтобы распределение вероятностей Бернулли было точным, поэтому выходные данные разжимаются с помощью функции SoftMax, чтобы получить заданное распределение.

Теперь определяется вторая операция. Обратное распространение выглядит следующим образом:

def backward(model, xs, hs, errs):

dW2 = hs.T @ errs

dh = errs @ model['W2'].T

dh[hs <= 0] = 0

dW1 = xs.T @ dh

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[0], batch_size):

X_train_mini = X_train[i:i + batch_size]

y_train_mini = y_train[i:i + batch_size]

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[layer] += learning_rate * grad[layer]

return model

Выполняется реализация функции 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[int(cls_idx)] = 1.

err = y_true - y_pred

xs.append(x)

hs.append(h)

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

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[idx]

grad = get_batch_grad(model, X_mini, y_mini)

for layer in grad:

velocity[layer] = gamma * velocity[layer] + alpha * grad[layer]

model[layer] += velocity[layer]

return model

Включается новая переменная velocity, которая будет накапливать импульс для каждого параметра. Обновление переменной будет происходить слагаемым alpha*grad[layer] на каждом новом шаге градиентного спуска. Так же происходит небольшое уменьшение с помощью коэффициента gamma значения переменной velocity, которая была вычислена на предыдущем шаге.

2.3 Реализация AdaGrad

До сих пор была игнорирована скорость обучения alpha, потому как она была постоянной. Проблема возникает в том, что скорость обучения влияет на все параметры и не всегда при постоянной скорости обучения алгоритм работает эффективно. Решением данной проблемы может выступать AdaGrad.

При использовании AdaGrad обновление параметров происходит точечно, поэтому скорость обучения является адаптивным параметром.

Выполняется реализация данного метода. Вся программа готова, нужно лишь изменить основную функцию. Называться она будетadagrad. Функция представлена ниже:

def adagrad(model, X_train, y_train, batch_size):

cache = {k: np.zeros_like(v) for k, v in model.items()}

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[idx]

grad = get_batch_grad(model, X_mini, y_mini)

for k in grad:

cache[k] += grad[k]**2

model[k] += alpha * grad[k] / (np.sqrt(cache[k]) + eps)

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[idx]

grad = get_batch_grad(model, X_mini, y_mini)

for k in grad:

cache[k] = gamma * cache[k] + (1 - gamma) * (grad[k]**2)

model[k] += alpha * grad[k] / (np.sqrt(cache[k]) + eps)

return model

Основное отличие в вычислении значения cache[k] и теперь накопленное значение градиента не будет агрессивно монотонно возрастать.

3. Тестирование и сравнение

В данной главе будет проводиться тестирование реализации и анализ полученных результатов.

3.1 Тестирование стандартного стохастического градиентного спуска

На данном этапе будет проводиться тестирование стандартного стохастического градиентного спуска. Процедура будет выполняться 100 раз и затем будет вычислено среднее значение точности.

Программа для тестирования приведена ниже:

batch_size = 1

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)

y_pred = np.zeros_like(y_test)

for i, x in enumerate(X_test):

prob = forward(x, model)

y = np.argmax(prob)

y_pred[i] = y

accs[k] = (y_pred == y_test).sum() / y_test.size

print('Средняя точность: {}, Полученное значение: {}'.format(accs.mean(), accs.std()))

Выполнив данный код, я получил следующие значения:

Средняя точность: 0.8765040000000001

Таким образом, можно сделать вывод, что в среднем точность выполнения 87%.

3.2 Тестирование Momentum

На данном этапе будет проводиться тестирование стохастического градиентного спуска на основе реализации Momentum. Процедура будет выполняться 100 раз и затем будет вычислено среднее значение точности.

Программа для тестирования приведена ниже:

n_iter = 100

batch_size = 1

eps = 1e-8

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)

y_pred[i] = y

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_iter = 100

batch_size = 1

eps = 1e-8

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)

y_pred[i] = y

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_iter = 100

batch_size = 1

eps = 1e-8

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)

y_pred[i] = y

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

...