Сегодня мы рассмотрим: Настоящие ценители музыки знают, что для качественного...
Цель - минимизировать функцию F в пространстве все возможных точек. График F представляет собой параболическую поверхность, и у неё должен быть один-единственный минимум. А вопрос о том, как исправлять точки так, чтобы двигаться в сторону этого минимума, давным-давно решён в математическом анализе. Для этого нужно двигаться в направлении, противоположном градиенту - вектору, вдоль которого производная максимальна. Градиент вычисляется следующим образом:
Т.е. для вычисления градиента мы должны использовать производную от заданной функции при соответствующих точках (переменных).
Таким образом, чтобы определить, как правильно исправлять координаты точек, мы должны вычислить градиент и отнять вектор какой-нибудь наперёд заданной длины (в нашем случае этой длинной выступает заданный шаг а) от имеющегося вектора точек:
Чтобы реализовать это программно, нужно научиться дифференцировать функцию F:
Пример 1 - алгоритм градиентного спуска для одной точки.
GradientDescent()
- 1. Инициализировать маленькими случайными значениями.
- 2. Повторить Number_of_Steps раз:
- а) Для всех i от 1 до n
- б) Для всех j
от 1 до m
:
- (i) Для всех i от 1 до n
- 3. выдать значения.
Это значит, что нам нужно подправлять координаты точек после каждого тестового примера так:
Новый, изменённый алгоритм показан в примере 1. Правда, нужно внести и другие изменения. Во-первых, мы больше не можем рассчитывать на то, что в какой-то момент достигнем идеальной гармонии с исходными данными, и нам нужно научиться останавливаться в какой-то момент. В качестве условия для остановки здесь принято то, что алгоритм выполняется пока разности значений функции меньше ранее заданной точности. Другое изменение - в том, что если оставлять а постоянным, то на каком-то этапе точка перестанет приближаться к искомому минимуму, а начнёт его «перепрыгивать» на каждой итерации, то в одну сторону, то в другую. Поэтому a нужно уменьшать со временем. В данной программе мы уменьшаем шаг на два.
Этот алгоритм может находить локальные минимумы (у рассматривавшегося нами параболоида есть один локальный минимум). Его отличие в том, что он не собирает всю информацию со всех тестовых примеров, а модифицирует точки сразу же, после каждого шага итерации.
В рамках моей домашней работы меня попросили реализовать стохастический градиентный спуск, чтобы решить проблему линейной регрессии (хотя у меня всего 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, и пакет будут сходиться к точному решению.
В этой лекции мы обсудим различные способы реализации , об их достоинствах и недостатках. Я бы хотел поговорить о трёх основных типах градиентного спуска – полном, пакетном и стохастическом.
В большинстве предыдущих курсов мы пользовались полным градиентным спуском.
Почему именно так?
Потому что это приносит больше пользы, если мы хотим максимизировать правдоподобие для всего учебного набора:
Недостатком такого подхода является то, что вычисление градиента занимает много времени, поскольку он зависит от каждого примера (наблюдения).
Полной противоположностью является стохастический градиентный спуск. Он зависит от ошибки лишь для одного конкретного наблюдения:
Метод основывается на том факте, что все наблюдения являются независимыми и равномерно распределёнными, поэтому в долгосрочной перспективе ошибка будет уменьшаться, ведь все наблюдения берутся из одного и того распределения. В таком случае, когда расчёты сократились от 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
Итак, у вас есть задача предсказать какое-то значение вроде стоимости дома по его размеру. Или время обработки какого-то запроса вашей системой. Да мало ли что.
Вы решили воспользоваться линейной регрессией и теперь хотите найти коэффициенты , при которых разница между ценой, которую предсказывает ваша модель, и реальной стоимостью проданных домов будет минимальной. Для этого вы можете использовать один из таких методов:
- 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 в общем виде не сходится к минимуму, но есть его модификации, которые позволяют добиться сходимости.
Стохастический градиент оценивается по формуле :
т. е. представляет собой сумму всех случайных векторов с весами, равными приращениям минимизируемой функции в данных случайных направлениях.
Если в качестве взять орты, т. то эта оценка при как легко заметить из (3.3.22), дает точное значение градиента.
Обе описанные оценки градиента могут эффективно применяться при любых значениях в том числе и при что существенно отличает их от детерминированного способа оценивания (3.3.22), для которого строго Это же обстоятельство подтверждает, что детерминированные методы обобщаются случайными (см. конец подраздела 3.3.1). Приведем еще пример такого обобщения.
Градиентный поиск (3.3.21) является частным случаем по крайней мере двух алгоритмов случайного поиска. Первый алгоритм:
где - по-прежнему единичный случайный -мерный вектор. Это известный градиентный алгоритм случайного поиска . Второй алгоритм имеет вид (3.3.23), но оценка градиента вычисляется по формуле
При как легко заметить, оба алгоритма вырождаются, в градиентный алгоритм поиска (3.3.21).
Таким образом, случайный поиск является естественным расширением, продолжением и обобщением известных регулярных методов поиска.
Другой особенностью случайного поиска, которая открывает широкие возможности для его эффективного применения, является использование оператора случайного шага в качестве стохастической модели сложных регулярных операторов отыскания направлений поиска в пространстве оптимизируемых параметров
Так, алгоритм случайного поиска с линейной тактикой (3.3.12) является стохастической моделью алгоритма наискорейшего спуска:
в которой случайный вектор моделирует оценку градиента. Любопытно, что подобную «оценку» нельзя даже назвать грубой, так как ее стохастические свойства и не напоминают свойств оцениваемого градиента. Однако, как показано выше, алгоритм случайного поиска не только работоспособен, но в ряде случаев и более эффективен, чем алгоритм наискорейшего спуска. Здесь
оператор случайного шага заменяет громоздкий оператор оценки градиента, например, по формуле (3.3.22).
Следующей особенностью случайного поиска, выгодно отличающей его от регулярных методов, является глобальность, проявляющаяся прежде всего в локальных алгоритмах случайного поиска, не предназначенных для отыскания глобального экстремума. Так, алгоритм случайного спуска может найти глобальный экстремум, а регулярный алгоритм наискорейшего спуска в принципе не допускает такой возможности, поскольку он построен для отыскания локального экстремума.
Следовательно, глобальность алгоритмов случайного поиска является как бы «премией» за использование случайности и чем-то вроде «бесплатного приложения» к алгоритму. Это обстоятельство особенно важно при оптимизации объектов с неизвестной структурой, когда нет полной уверенности в одноэкстремальности задачи и возможно (хотя и не ожидается) наличие нескольких экстремумов. Использование в таком случае методов глобального поиска было бы неразумной расточительностью. Методы локального случайного поиска здесь наиболее приемлемы, так как они эффективно решают локальную задачу и могут в принципе решить глобальную, если таковая будет иметь место. Это обеспечивает случайному поиску своеобразную психологическую надежность, которую очень ценят пользователи.
Алгоритмическая простота случайного поиска делает его привлекательным в первую очередь для потребителей . Опыт показывает, что известные алгоритмы случайного поиска являются лишь «канвой», на которой пользователь в каждом конкретном случае «вышивает узоры» новых алгоритмов, отражающих не только его вкусы и наклонности (что нельзя не учитывать), но и специфику оптимизируемого объекта. Последнее создает благоприятную основу для реализации известного принципа, что алгоритм должен конструироваться «под объект». Наконец, алгоритмическая простота случайного поиска обусловливает простоту его аппаратурной реализации. Это не только дает возможность строить простые, компактные и надежные оптимизаторы с неограниченным числом оптимизируемых параметров , но и позволяет довольно просто организовать их оптимальный синтез на ЭВМ .
