Цель - минимизировать функцию F в пространстве все возможных точек. График F представляет собой параболическую поверхность, и у неё должен быть один-единственный минимум. А вопрос о том, как исправлять точки так, чтобы двигаться в сторону этого минимума, давным-давно решён в математическом анализе. Для этого нужно двигаться в направлении, противоположном градиенту - вектору, вдоль которого производная максимальна. Градиент вычисляется следующим образом:
Т.е. для вычисления градиента мы должны использовать производную от заданной функции при соответствующих точках (переменных).
Таким образом, чтобы определить, как правильно исправлять координаты точек, мы должны вычислить градиент и отнять вектор какой-нибудь наперёд заданной длины (в нашем случае этой длинной выступает заданный шаг а) от имеющегося вектора точек:
Чтобы реализовать это программно, нужно научиться дифференцировать функцию F:
Пример 1 - алгоритм градиентного спуска для одной точки.
GradientDescent()
- 1. Инициализировать маленькими случайными значениями.
- 2. Повторить Number_of_Steps раз:
- а) Для всех i от 1 до n
- б) Для всех j
от 1 до m
:
- (i) Для всех i от 1 до n
- 3. выдать значения.
Это значит, что нам нужно подправлять координаты точек после каждого тестового примера так:
Новый, изменённый алгоритм показан в примере 1. Правда, нужно внести и другие изменения. Во-первых, мы больше не можем рассчитывать на то, что в какой-то момент достигнем идеальной гармонии с исходными данными, и нам нужно научиться останавливаться в какой-то момент. В качестве условия для остановки здесь принято то, что алгоритм выполняется пока разности значений функции меньше ранее заданной точности. Другое изменение - в том, что если оставлять а постоянным, то на каком-то этапе точка перестанет приближаться к искомому минимуму, а начнёт его «перепрыгивать» на каждой итерации, то в одну сторону, то в другую. Поэтому a нужно уменьшать со временем. В данной программе мы уменьшаем шаг на два.
Этот алгоритм может находить локальные минимумы (у рассматривавшегося нами параболоида есть один локальный минимум). Его отличие в том, что он не собирает всю информацию со всех тестовых примеров, а модифицирует точки сразу же, после каждого шага итерации.
В этой лекции мы обсудим различные способы реализации , об их достоинствах и недостатках. Я бы хотел поговорить о трёх основных типах градиентного спуска – полном, пакетном и стохастическом.
В большинстве предыдущих курсов мы пользовались полным градиентным спуском.
Почему именно так?
Потому что это приносит больше пользы, если мы хотим максимизировать правдоподобие для всего учебного набора:
Недостатком такого подхода является то, что вычисление градиента занимает много времени, поскольку он зависит от каждого примера (наблюдения).
Полной противоположностью является стохастический градиентный спуск. Он зависит от ошибки лишь для одного конкретного наблюдения:
Метод основывается на том факте, что все наблюдения являются независимыми и равномерно распределёнными, поэтому в долгосрочной перспективе ошибка будет уменьшаться, ведь все наблюдения берутся из одного и того распределения. В таком случае, когда расчёты сократились от N наблюдений до 1, – это замечательное улучшение метода.
В чём же недостаток?
Дело в том, что если при полном градиентном спуске логарифм функции правдоподобия всегда улучшается на каждой итерации, то при стохастическом логарифм функции правдоподобия может даже ухудшиться. На самом деле поведение функции затрат будет хаотично меняться при каждой итерации, но в долгосрочной перспективе она всё же уменьшится.
Удачным компромиссов между этими двумя методами является пакетный градиентный спуск. Если у нас есть, к примеру, 10 000 наблюдений, то мы можем разделить их на 100 пакетов по 100 наблюдений в каждом и вычислять функцию затрат, основываясь на каждом пакете при каждой итерации:
Что в этом случае будет с функцией затрат?
Она тоже может становиться больше, но будет менее хаотична, чем в случае чисто стохастического градиентного спуска.
И пользуясь случаем, хочу отметить, что если вы желаете получить бесплатный материал, связанный с глубоким и машинным обучением, а также обработке данных, посетите мой сайт lazyprogrammer.me. Я постоянно пишу новые материалы по этим темам, так что проверяйте почаще. Там должно появиться предложение подписаться, так что вы можете подписаться на моё бесплатное введение в обработку данных. В нём много замечательных ресурсов для изучения языка Python, алгоритмов и структур данных, а также купонов на курсы на .
Полный, пакетный и стохастический градиентный спуск в коде
Теперь сравним изменение функции затрат в трёх случаях градиентного спуска – полного, пакетного и стохастического. Поскольку в этом примере много кода скопировано из других файлов, мы просто последовательно пройдёмся по тексту программы.
Итак, в начале файла мы импортируем все обычные библиотеки. Из файла util.py мы импортируем функцию get_transformed_data , чтобы преобразовать данные по методу главных компонент, а также функции forward, error_date, cost, gradW, gradb и y2indicator.
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.utils import shuffle
from datetime import datetime
from util import get_transformed_data, forward, error_rate, cost, gradW, gradb, y2indicator
Для ускорения процесса мы вместо полной нейронной сети используем .
Итак, вначале мы используем функцию get_transformed_data , взяв лишь первые 300 столбцов. Далее нормализуем наши X путём вычитания среднего значения и деления на стандартное отклонение. Затем, поскольку функция get_transformed_data уже перемешала наши данные, мы оставляем последние 1 000 примеров в качестве проверочного набора, использую остальные в качестве учебного.
def main():
X, Y, _, _ = get_transformed_data()
X = X[:, :300]
# normalize X first
mu = X.mean(axis =0)
std = X.std(axis =0)
X = (X – mu) / std
print “Performing logistic regression…”
Xtrain = X[:-1000,]
Ytrain = Y[:-1000]
Xtest = X[-1000:,]
N, D = Xtrain.shape
Ytrain_ind = y2indicator(Ytrain)
Ytest_ind = y2indicator(Ytest)
Затем инициируем весовые коэффициенты и свободные члены. Обратите внимание, что инициируемые весовые коэффициенты установлены относительно малыми – пропорциональными квадратному корню из размерности. Ещё до записи этого видео я установил значения коэффициента обучения и штрафа регуляризации – 0,0001 и 0,01 соответственно. Количество итераций установим равным 200, чтобы вычисления шли не слишком долго.
# 1. full
b = np.zeros(10)
LL =
lr = 0.0001
reg = 0.01
t0 = datetime.now()
for i in xrange (200):
p_y = forward(Xtrain, W, b)
Далее обновляем значения и свободных членов при помощи градиентного спуска и . Используем также функцию forward , чтобы вычислить значение функции затрат при прохождении учебного набора. Будем выводить значение коэффициента ошибок через каждые десять итераций. Кроме того, будем выводить на экран потраченное на вычисления время, поскольку один из методов весьма быстро, а другой – весьма медлителен.
W += lr*(gradW(Ytrain_ind, p_y, Xtrain) – reg*W)
b += lr*(gradb(Ytrain_ind, p_y) – reg*b)
LL.append(ll)
if i % 10 == 0:
print “Error rate:”, err
p_y = forward(Xtest, W, b)
print “Elapsted time for full GD:”, datetime.now() – t0
В случае стохастического градиентного спуска мы в большой мере делаем то же самое, разве что мы делаем лишь один проход по данным, поскольку при стохастическом градиентном спуске мы рассматриваем лишь один пример и обновляем весовые коэффициенты и свободные члены отдельно при каждом проходе, после чего заново перемешиваем данные. Поскольку если проходить по всем примерам, то работать программа будет очень медленно, постольку мы ограничимся лишь 500 примеров.
Затем, как обычно, вычисляем градиент, обновляем весовые коэффициенты с применением регуляризации и вычисляем коэффициент ошибок, разве что выводим значение коэффициента лишь каждые N/2 прохода, поскольку в противном случае вычисления будут очень долгими. В остальном – всё то же самое.
# 2. stochastic
W = np.random.randn(D, 10) / 28
b = np.zeros(10)
LL_stochastic =
lr = 0.0001
reg = 0.01
t0 = datetime.now()
for i in xrange (1): # takes very long since we’re computing cost for 41k samples
for n in xrange (min(N, 500)): # shortcut so it won’t take so long…
x = tmpX.reshape(1,D)
y = tmpY.reshape(1,10)
p_y = forward(x, W, b)
p_y_test = forward(Xtest, W, b)
ll = cost(p_y_test, Ytest_ind)
LL_stochastic.append(ll)
if n % (N/2) == 0:
err = error_rate(p_y_test, Ytest)
print “Cost at iteration %d: %.6f” % (i, ll)
print “Error rate:”, err
p_y = forward(Xtest, W, b)
print “Final error rate:”, error_rate(p_y, Ytest)
print “Elapsted time for SGD:”, datetime.now() – t0
При пакетном градиентном спуске, опять-таки, почти всё то же самое. Установим, что в каждом пакете по 500 примеров, так что общее количество пакетов будет равно N, делённое на размер пакета.
# 3. batch
W = np.random.randn(D, 10) / 28
b = np.zeros(10)
LL_batch =
lr = 0.0001
reg = 0.01
batch_sz = 500
n_batches = N / batch_sz
t0 = datetime.now()
for i in xrange (50):
tmpX, tmpY = shuffle(Xtrain, Ytrain_ind)
for j in xrange (n_batches):
x = tmpX
y = tmpY
p_y = forward(x, W, b)
W += lr*(gradW(y, p_y, x) – reg*W)
b += lr*(gradb(y, p_y) – reg*b)
p_y_test = forward(Xtest, W, b)
ll = cost(p_y_test, Ytest_ind)
LL_batch.append(ll)
if j % (n_batches/2) == 0:
err = error_rate(p_y_test, Ytest)
print “Cost at iteration %d: %.6f” % (i, ll)
print “Error rate:”, err
p_y = forward(Xtest, W, b)
print “Final error rate:”, error_rate(p_y, Ytest)
print “Elapsted time for batch GD:”, datetime.now() – t0
И в конце мы выводим все наши данные на экран.
x1 = np.linspace(0, 1, len(LL))
plt.plot(x1, LL, label =”full”)
x2 = np.linspace(0, 1, len(LL_stochastic))
plt.plot(x2, LL_stochastic, label =”stochastic”)
x3 = np.linspace(0, 1, len(LL_batch))
plt.plot(x3, LL_batch, label =”batch”)
plt.legend()
plt.show()
if __name__ == ‘__main__’:
Итак, запустим программу.
Мы можем видеть, что в случае стохастического градиентного спуска ошибка почти не улучшилась. Это значит, что необходимо намного больше итераций, чтобы добиться улучшения при стохастическом градиентном спуске. Полный градиентный спуск, как мы видим, сходится быстрее, чем пакетный, но и работает он медленнее.
Если мы посмотрим на изменение функции затрат в увеличенном масштабе, то увидим, что в случае пакетного градиентного спуска оно является не очень гладким, в отличие от полного градиентного спуска, когда функция затрат изменяется плавно, поскольку в этом случае функция затрат всегда уменьшается. В случае стохастического градиентного спуска изменение функции затрат также не плавно:
Post Views: 588
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, который позволит нам повысить весомость редких событий и снизить вес частых событий. Полученные после преобразования данные мы будем передавать классификаторам, которые подходят для решения стоящей перед нами задачи, а именно: Наивный Байесовский Классификатор или Машина Опорных Векторов с Линейным ядром, обученная по методу стохастического градиентного спуска. Также мы осуществим проверку эффективности Машины Опорных Векторов с нелинейными ядрами, обученной по методу пакетного градиентного спуска. Однако, данный тип классификатора не кажется подходящим для поставленной задачи в силу слишком сложного ядра и склонности к переобучаемости, при которой классификатор плохо справляется с данными, которые не использовались для обучения классификатора.
программный машинный предобработка данный
В рамках моей домашней работы меня попросили реализовать стохастический градиентный спуск, чтобы решить проблему линейной регрессии (хотя у меня всего 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, и пакет будут сходиться к точному решению.
Градиентный спуск — самый используемый алгоритм обучения, он применяется почти в каждой модели . Градиентный спуск — это, по сути, и есть то, как обучаются модели. Без ГС машинное обучение не было бы там, где сейчас. Метод градиентного спуска с некоторой модификацией широко используется для обучения и глубоких , и известен как ошибки.
В этом посте вы найдете объяснение градиентного спуска с небольшим количеством математики. Краткое содержание:
- Смысл ГС — объяснение всего алгоритма;
- Различные вариации алгоритма;
- Реализация кода: написание кода на языке Phyton.
Что такое градиентный спуск
Градиентный спуск — метод нахождения минимального значения функции потерь (существует множество видов этой функции). Минимизация любой функции означает поиск самой глубокой впадины в этой функции. Имейте в виду, что функция используется, чтобы контролировать ошибку в прогнозах модели машинного обучения. Поиск минимума означает получение наименьшей возможной ошибки или повышение точности модели. Мы увеличиваем точность, перебирая набор учебных данных при настройке параметров нашей модели (весов и смещений).
Итак, градиентный спуск нужен для минимизации функции потерь.
Суть алгоритма – процесс получения наименьшего значения ошибки. Аналогично это можно рассматривать как спуск во впадину в попытке найти золото на дне ущелья (самое низкое значение ошибки).
Поиск минимума функции В дальнейшем, чтобы найти самую низкую ошибку (глубочайшую впадину) в функции потерь (по отношению к одному весу), нужно настроить параметры модели. Как мы их настраиваем? В этом поможет математический анализ. Благодаря анализу мы знаем, что наклон графика функции – производная от функции по переменной. Это наклон всегда указывает на ближайшую впадину!
На рисунке мы видим график функции потерь (названный «Ошибка» с символом «J») с одним весом. Теперь, если мы вычислим наклон (обозначим это dJ/dw) функции потерь относительно одного веса, то получим направление, в котором нужно двигаться, чтобы достичь локальных минимумов. Давайте пока представим, что наша модель имеет только один вес.
Функция потерь
Важно: когда мы перебираем все учебные данные, мы продолжаем добавлять значения dJ/dw для каждого веса. Так как потери зависят от примера обучения, dJ/dw также продолжает меняться. Затем делим собранные значения на количество примеров обучения для получения среднего. Потом мы используем это среднее значение (каждого веса) для настройки каждого веса.
Также обратите внимание: Функция потерь предназначена для отслеживания ошибки с каждым примером обучениям, в то время как производная функции относительного одного веса – это то, куда нужно сместить вес, чтобы минимизировать ее для этого примера обучения. Вы можете создавать модели даже без применения функции потерь. Но вам придется использовать производную относительно каждого веса (dJ/dw).
Теперь, когда мы определили направление, в котором нужно подтолкнуть вес, нам нужно понять, как это сделать. Тут мы используем коэффициент скорости обучения, его называют гипер-параметром. Гипер-параметр – значение, требуемое вашей моделью, о котором мы действительно имеем очень смутное представление. Обычно эти значения могут быть изучены методом проб и ошибок. Здесь не так: одно подходит для всех гипер-параметров. Коэффициент скорости обучения можно рассматривать как «шаг в правильном направлении», где направление происходит от dJ/dw.
Это была функция потерь построенная на один вес. В реальной модели мы делаем всё перечисленное выше для всех весов, перебирая все примеры обучения. Даже в относительно небольшой модели машинного обучения у вас будет более чем 1 или 2 веса. Это затрудняет визуализацию, поскольку график будет обладать размерами, которые разум не может себе представить.
Подробнее о градиентах
Кроме функции потерь градиентный спуск также требует градиент, который является dJ/dw (производная функции потерь относительно одного веса, выполненная для всех весов). dJ/dw зависит от вашего выбора функции потерь. Наиболее распространена функция потерь среднеквадратичной ошибки.
Производная этой функции относительно любого веса (эта формула показывает вычисление градиента для ):
Это – вся математика в ГС. Глядя на это можно сказать, что по сути, ГС не содержит много математики. Единственная математика, которую он содержит в себе – умножение и деление, до которых мы доберемся. Это означает, что ваш выбор функции повлияет на вычисление градиента каждого веса.
Коэффициент скорости обучения
Всё, о чём написано выше, есть в учебнике. Вы можете открыть любую книгу о градиентном спуске, там будет написано то же самое. Формулы градиентов для каждой функции потерь можно найти в интернете, не зная как вывести их самостоятельно.
Однако проблема у большинства моделей возникает с коэффициентом скорости обучения. Давайте взглянем на обновленное выражение для каждого веса (j лежит в диапазоне от 0 до количества весов, а Theta-j это j-й вес в векторе весов, k лежит в диапазоне от 0 до количества смещений, где B-k — это k-е смещение в векторе смещений). Здесь alpha – коэффициент скорости обучения. Из этого можно сказать, что мы вычисляем dJ/dTheta-j (градиент веса Theta-j), и затем шаг размера alpha в этом направлении. Следовательно, мы спускаемся по градиенту. Чтобы обновить смещение, замените Theta-j на B-k.
Если этот размера шага alpha слишком велик, мы преодолеем минимум: то есть промахнемся мимо минимума. Если alpha слишком мала, мы используем слишком много итераций, чтобы добраться до минимума. Итак, alpha должна быть подходящей.
Использование градиентного спуска
Что ж, вот и всё. Это всё, что нужно знать про градиентный спуск. Давайте подытожим всё в псевдокоде.
Примечание: Весы здесь представлены в векторах. В более крупных моделях они, наверное, будут матрицами.
От i = 0 до «количество примеров обучения»
1. Вычислите градиент функции потерь для i-го примера обучения по каждому весу и смещению. Теперь у вас есть вектор, который полон градиентами для каждого веса и переменной, содержащей градиент смещения.
2. Добавьте градиенты весов, вычисленные для отдельного аккумулятивного вектора, который после того, как вы выполнили итерацию по каждому учебному примеру, должен содержать сумму градиентов каждого веса за несколько итераций.
3. Подобно ситуации с весами, добавьте градиент смещения к аккумулятивной переменной.
Теперь, ПОСЛЕ перебирания всех примеров обучения, выполните следующие действия:
1. Поделите аккумулятивные переменные весов и смещения на количество примеров обучения. Это даст нам средние градиенты для всех весов и средний градиент для смещения. Будем называть их обновленными аккумуляторами (ОА).
2. Затем, используя приведенную ниже формулу, обновите все веса и смещение. Вместо dJ / dTheta-j вы будете подставлять ОА (обновленный аккумулятор) для весов и ОА для смещения. Проделайте то же самое для смещения.
Это была только одна итерация градиентного спуска.
Повторите этот процесс от начала до конца для некоторого количества итераций. Это означает, что для 1-й итерации ГС вы перебираете все примеры обучения, вычисляете градиенты, потом обновляете веса и смещения. Затем вы проделываете это для некоторого количества итераций ГС.
Различные типы градиентного спуска
Существует 3 варианта градиентного спуска:
1. Мini-batch : тут вместо перебирания всех примеров обучения и с каждой итерацией, выполняющей вычисления только на одном примере обучения, мы обрабатываем n учебных примеров сразу. Этот выбор хорош для очень больших наборов данных.
2. Стохастический градиентный спуск : в этом случае вместо использования и зацикливания на каждом примере обучения, мы ПРОСТО ИСПОЛЬЗУЕМ ОДИН РАЗ. Есть несколько вещей замечаний:
- С каждой итерацией ГС вам нужно перемешать набор обучения и выбрать случайный пример обучения.
- Поскольку вы используете только один пример обучения, ваш путь к локальным минимумам будет очень шумным, как у пьяного человека, который много выпил.
3. Серия ГС : это то, о чем написано в предыдущих разделах. Цикл на каждом примере обучения.
Картинка, сравнивающая 3 попадания в локальные минимумы Пример кода на python
Применимо к cерии ГС, так будет выглядеть блок учебного кода на Python.
Def train(X, y, W, B, alpha, max_iters): """ Performs GD on all training examples, X: Training data set, y: Labels for training data, W: Weights vector, B: Bias variable, alpha: The learning rate, max_iters: Maximum GD iterations. """ dW = 0 # Weights gradient accumulator dB = 0 # Bias gradient accumulator m = X.shape # No. of training examples for i in range(max_iters): dW = 0 # Reseting the accumulators dB = 0 for j in range(m): # 1. Iterate over all examples, # 2. Compute gradients of the weights and biases in w_grad and b_grad, # 3. Update dW by adding w_grad and dB by adding b_grad, W = W - alpha * (dW / m) # Update the weights B = B - alpha * (dB / m) # Update the bias return W, B # Return the updated weights and bias.
Вот и всё. Теперь вы должны хорошо понимать, что такое метод градиентного спуска.
