Методика разработки программного продукта для поиска причин в изменениях трендов в данных. Градиентные спуски: batch и stochastic gradient descents

Цель - минимизировать функцию F в пространстве все возможных точек. График F представляет собой параболическую поверхность, и у неё должен быть один-единственный минимум. А вопрос о том, как исправлять точки так, чтобы двигаться в сторону этого минимума, давным-давно решён в математическом анализе. Для этого нужно двигаться в направлении, противоположном градиенту - вектору, вдоль которого производная максимальна. Градиент вычисляется следующим образом:

Т.е. для вычисления градиента мы должны использовать производную от заданной функции при соответствующих точках (переменных).

Таким образом, чтобы определить, как правильно исправлять координаты точек, мы должны вычислить градиент и отнять вектор какой-нибудь наперёд заданной длины (в нашем случае этой длинной выступает заданный шаг а) от имеющегося вектора точек:

Чтобы реализовать это программно, нужно научиться дифференцировать функцию F:

Пример 1 - алгоритм градиентного спуска для одной точки.

GradientDescent()

• 1. Инициализировать маленькими случайными значениями.
• 2. Повторить Number_of_Steps раз:
  • а) Для всех i от 1 до n
  • б) Для всех j от 1 до m :
    • (i) Для всех i от 1 до n

• 3. выдать значения.

Это значит, что нам нужно подправлять координаты точек после каждого тестового примера так:

Новый, изменённый алгоритм показан в примере 1. Правда, нужно внести и другие изменения. Во-первых, мы больше не можем рассчитывать на то, что в какой-то момент достигнем идеальной гармонии с исходными данными, и нам нужно научиться останавливаться в какой-то момент. В качестве условия для остановки здесь принято то, что алгоритм выполняется пока разности значений функции меньше ранее заданной точности. Другое изменение - в том, что если оставлять а постоянным, то на каком-то этапе точка перестанет приближаться к искомому минимуму, а начнёт его «перепрыгивать» на каждой итерации, то в одну сторону, то в другую. Поэтому a нужно уменьшать со временем. В данной программе мы уменьшаем шаг на два.

Этот алгоритм может находить локальные минимумы (у рассматривавшегося нами параболоида есть один локальный минимум). Его отличие в том, что он не собирает всю информацию со всех тестовых примеров, а модифицирует точки сразу же, после каждого шага итерации.

где f i – функция, подсчитанная на i-м батче, i выбирается случайным образом;

Шаг обучения является гиперпараметром; при слишком больших значениях алгоритм обучения будет расходиться, при слишком маленьких – будет сходиться медленно.

Стохастический градиентный спуск с инерцией

В методе стохастического градиентного спуска нередка ситуация, когда градиент на каждой итерации изменяется в большой степени. Это происходит из-за того, что функционал вычисляется на различных данных, которые могут в значительной степени отличаться. Такое изменение можно сгладить, если использовать градиенты, вычисленные на предыдущих итерациях и масштабированные на гиперпараметр инерции μ:

	(14)
	(15)

Как несложно догадаться, гиперпараметр инерции μ имеет такое название из-за того, что, подобно так называемой ньютоновой силе инерции, т.е. силе противодействия, «сопротивляется» изменениям градиента и смягчает изменения весовых коэффициентов на протяжении обучения. Такой алгоритм обучения называется стохастическим градиентным спуском с инерцией или SGDМ (stochastic gradient descent with momentum).

Метод адаптивного градиента

Метод адаптивного градиента (Adagrad – от англ. «adaptive gradient algorithm») основан на идее масштабирования. Он перемасштабирует скорость обучения для каждого настраиваемого параметра в отдельности, при этом учитывая историю всех прошлых градиентов для этого параметра. Для этого каждый элемент градиента делится на квадратный корень от суммы квадратов предыдущих соответствующих элементов градиента. Такой подход эффективно уменьшает скорость обучения для тех весовых коэффициентов, которые имеют большое значение градиента, а также со временем снижает скорость обучения для всех параметров, так как сумма квадратов неуклонно увеличивается для всех параметров при каждой итерации. При задании нулевого начального масштабирующего параметра g = 0 формула для пересчета весовых коэффициентов имеет вид (деление выполняется поэлементно).

Стохастический градиент оценивается по формуле :

т. е. представляет собой сумму всех случайных векторов с весами, равными приращениям минимизируемой функции в данных случайных направлениях.

Если в качестве взять орты, т. то эта оценка при как легко заметить из (3.3.22), дает точное значение градиента.

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

Градиентный поиск (3.3.21) является частным случаем по крайней мере двух алгоритмов случайного поиска. Первый алгоритм:

где - по-прежнему единичный случайный -мерный вектор. Это известный градиентный алгоритм случайного поиска . Второй алгоритм имеет вид (3.3.23), но оценка градиента вычисляется по формуле

При как легко заметить, оба алгоритма вырождаются, в градиентный алгоритм поиска (3.3.21).

Таким образом, случайный поиск является естественным расширением, продолжением и обобщением известных регулярных методов поиска.

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

Так, алгоритм случайного поиска с линейной тактикой (3.3.12) является стохастической моделью алгоритма наискорейшего спуска:

в которой случайный вектор моделирует оценку градиента. Любопытно, что подобную «оценку» нельзя даже назвать грубой, так как ее стохастические свойства и не напоминают свойств оцениваемого градиента. Однако, как показано выше, алгоритм случайного поиска не только работоспособен, но в ряде случаев и более эффективен, чем алгоритм наискорейшего спуска. Здесь

оператор случайного шага заменяет громоздкий оператор оценки градиента, например, по формуле (3.3.22).

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

Следовательно, глобальность алгоритмов случайного поиска является как бы «премией» за использование случайности и чем-то вроде «бесплатного приложения» к алгоритму. Это обстоятельство особенно важно при оптимизации объектов с неизвестной структурой, когда нет полной уверенности в одноэкстремальности задачи и возможно (хотя и не ожидается) наличие нескольких экстремумов. Использование в таком случае методов глобального поиска было бы неразумной расточительностью. Методы локального случайного поиска здесь наиболее приемлемы, так как они эффективно решают локальную задачу и могут в принципе решить глобальную, если таковая будет иметь место. Это обеспечивает случайному поиску своеобразную психологическую надежность, которую очень ценят пользователи.

Алгоритмическая простота случайного поиска делает его привлекательным в первую очередь для потребителей . Опыт показывает, что известные алгоритмы случайного поиска являются лишь «канвой», на которой пользователь в каждом конкретном случае «вышивает узоры» новых алгоритмов, отражающих не только его вкусы и наклонности (что нельзя не учитывать), но и специфику оптимизируемого объекта. Последнее создает благоприятную основу для реализации известного принципа, что алгоритм должен конструироваться «под объект». Наконец, алгоритмическая простота случайного поиска обусловливает простоту его аппаратурной реализации. Это не только дает возможность строить простые, компактные и надежные оптимизаторы с неограниченным числом оптимизируемых параметров , но и позволяет довольно просто организовать их оптимальный синтез на ЭВМ .

В рамках моей домашней работы меня попросили реализовать стохастический градиентный спуск, чтобы решить проблему линейной регрессии (хотя у меня всего 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, и пакет будут сходиться к точному решению.