Почему градиентный спуск стал стохастическим

Пошаговый путь от оптимизации на основе математического анализа к стохастическому градиентному спуску.

Делиться

В этой статье мы обсудим не только то, как , но и почему используются градиентный спуск и стохастический градиентный спуск .

О линейной регрессии мы уже знаем, и недавно я писал о ней в контексте векторов и проекций.

Теперь мы попытаемся понять градиентный спуск на примере задачи линейной регрессии.

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

Если вы уже знакомы с основными математическими принципами линейной регрессии, то можете сразу начать с раздела « Зачем нам нужен градиентный спуск?».

Допустим, мы начали свой путь в машинном обучении, и первым делом реализовали модель линейной регрессии с использованием Python.

Мы успешно реализовали это и получили наилучшие значения для наклона и точки пересечения с осью Y.

Теперь у нас возникает вопрос: что же на самом деле происходит за этим алгоритмом?

Мы хотим понять математическую основу этого процесса.

Краткий обзор линейной регрессии

Для этого рассмотрим следующие данные.

Теперь нам нужно понять математическую основу алгоритма.

Мы встречаем формулы для вычисления наклона и точки пересечения с осью Y.

[
beta_1 = frac{sum_{i=1}^{n} (x_i – bar{x})(y_i – bar{y})}{sum_{i=1}^{n} (x_i – bar{x})^2}
[

[
beta_0 = bar{y} – beta_1bar{x}
[

Теперь, используя эти формулы, мы вычисляем наклон и точку пересечения с осью Y.

Уравнение простой линейной регрессии выглядит следующим образом:

[
hat{y}
=
β₀ + β₁x
[

Формула для расчета наклона:

[
бета_1
=
frac{
sum_{i=1}^{n}(x_i-bar{x})(y_i-bar{y})
}{
sum_{i=1}^{n}(x_i-bar{x})^2
}
[

Формула для определения свободного члена уравнения выглядит следующим образом:

[
бета_0
=
bar{y}
–
β1̄x
[

Данный набор данных:

[
x=
[1.2,1.4,1.6,2.1,2.3,3.0,3.1,3.3,3.3,3.8]
] [
y=
[39344,46206,37732,43526,39892,56643,60151,54446,64446,57190]
[

Вычислите среднее значение x:

[
bar{x}
=
frac{1.2+1.4+1.6+2.1+2.3+3.0+3.1+3.3+3.3+3.8}{10}
] [
bar{x}
=
frac{25.1}{10}
=
2.51
[

Вычислите среднее значение y:

[
bar{y}
=
frac{
39344+46206+37732+43526+39892+56643+60151+54446+64446+57190
}{10}
] [
bar{y}
=
frac{499576}{10}
=
49957.6
[

Теперь вычислим:

[
sum(x_i-bar{x})(y_i-bar{y})
[

После подстановки и вычислений:

[
sum(x_i-bar{x})(y_i-bar{y})
=
41663.44
[

Теперь вычислим:

[
sum(x_i-bar{x})^2
[

После расчетов:

[
sum(x_i-bar{x})^2
=
4.619
[

Теперь вычислим наклон:

[
бета_1
=
frac{41663.44}{4.619}
] [
бета_1
=
9020.66
[

Теперь вычислим точку пересечения с осью Y:

[
бета_0
=
49957.6-(9020.66)(2.51)
] [
бета_0
=
27315.74
[

Поэтому:

[
β₀ = 27315,74
] [
β_1=9020.66
[

Итоговое уравнение регрессии:

[
hat{y}
=
27315.74+9020.66x
[

Мы получили значения, используя формулы, но нас это не устраивает, и мы хотим углубиться в анализ.

Теперь наша цель — выяснить, как мы получили эти формулы.

Чтобы это понять, рассмотрим теперь трехмерную чашеобразную кривую. Мы получаем эту чашеобразную кривую, когда строим график всех возможных комбинаций β0beta_0​, β1beta_1 и среднеквадратичной ошибки (MSE).

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

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

Далее мы дифференцируем функцию потерь, поскольку кривая в форме чаши является ее трехмерным представлением, и вы понимаете, что здесь у нас две переменные.

Итак, мы проводим частное дифференцирование, а затем решаем уравнение, чтобы получить формулы для наклона и точки пересечения с осью Y.

Вывод формул для наклона и пересечения с осью Y.

Начнём с функции потерь среднеквадратичной ошибки (MSE):

[
MSE(beta_0,beta_1)
=
frac{1}{n}
sum_{i=1}^{n}
(y_i-(beta_0+beta_1x_i))^2
[

Перестройте внутреннее выражение:

[
=
frac{1}{n}
sum_{i=1}^{n}
(y_i-beta_0-beta_1x_i)^2
[

Теперь возьмём частную производную по ( beta_0 ):

[
frac{partial MSE}{partial beta_0}
=
frac{partial}{partial beta_0}
левый(
frac{1}{n}
sum_{i=1}^{n}
(y_i-beta_0-beta_1x_i)^2
верно)
[

Постоянно бывать на улице:

[
=
frac{1}{n}
frac{partial}{partial beta_0}
sum_{i=1}^{n}
(y_i-beta_0-beta_1x_i)^2
[

Переместите производную внутрь суммы:

[
=
frac{1}{n}
sum_{i=1}^{n}
frac{partial}{partial beta_0}
(y_i-beta_0-beta_1x_i)^2
[

Примените правило цепочки:

[
=
frac{1}{n}
sum_{i=1}^{n}
2(y_i-beta_0-beta_1x_i)
cdot
frac{partial}{partial beta_0}
(y_i-beta_0-beta_1x_i)
[

Примените правила производных:

[
frac{d}{dbeta_0}(y_i)=0
] [
frac{d}{dbeta_0}(-beta_0)=-1
] [
frac{d}{dbeta_0}(-beta_1x_i)=0
[

Таким образом, скалярная производная принимает следующий вид:

[
frac{partial}{partial beta_0}
(y_i-beta_0-beta_1x_i)
=
-1
[

Заменить на обратную сторону:

[
frac{partial MSE}{partial beta_0}
=
frac{1}{n}
sum_{i=1}^{n}
2(y_i-beta_0-beta_1x_i)(-1)
[

Упрощать:

[
=
-frac{2}{n}
sum_{i=1}^{n}
(y_i-beta_0-beta_1x_i)
[

Приравняйте производную к нулю:

[
-frac{2}{n}
sum_{i=1}^{n}
(y_i-beta_0-beta_1x_i)
=
0
[

Умножьте обе стороны на:

[
-frac{n}{2}
] [
sum_{i=1}^{n}
(y_i-beta_0-beta_1x_i)
=
0
[

Расширять:

[
sum_{i=1}^{n}y_i
–
нбета_0
–
beta_1sum_{i=1}^{n}x_i
=
0
[

Переставьте:

[
нбета_0
=
sum_{i=1}^{n}y_i
–
beta_1sum_{i=1}^{n}x_i
[

Разделите на ( n ):

[
бета_0
=
frac{1}{n}sum_{i=1}^{n}y_i
–
бета_1
frac{1}{n}sum_{i=1}^{n}x_i
[

Использование средств:

[
bar{x}
=
frac{1}{n}sum_{i=1}^{n}x_i
] [
bar{y}
=
frac{1}{n}sum_{i=1}^{n}y_i
[

Формула для расчета конечного пересечения:

[
бета_0
=
bar{y}
–
β1̄x
[

Теперь возьмём частную производную по ( beta_1 ):

[
frac{partial MSE}{partial beta_1}
=
frac{partial}{partial beta_1}
левый(
frac{1}{n}
sum_{i=1}^{n}
(y_i-beta_0-beta_1x_i)^2
верно)
[

Постоянно бывать на улице:

[
=
frac{1}{n}
frac{partial}{partial beta_1}
sum_{i=1}^{n}
(y_i-beta_0-beta_1x_i)^2
[

Переместите производную внутрь суммы:

[
=
frac{1}{n}
sum_{i=1}^{n}
frac{partial}{partial beta_1}
(y_i-beta_0-beta_1x_i)^2
[

Примените правило цепочки:

[
=
frac{1}{n}
sum_{i=1}^{n}
2(y_i-beta_0-beta_1x_i)
cdot
frac{partial}{partial beta_1}
(y_i-beta_0-beta_1x_i)
[

Примените правила производных:

[
frac{d}{dbeta_1}(y_i)=0
] [
frac{d}{dbeta_1}(-beta_0)=0
] [
frac{d}{dbeta_1}(-beta_1x_i)=-x_i
[

Таким образом, скалярная производная принимает следующий вид:

[
frac{partial}{partial beta_1}
(y_i-beta_0-beta_1x_i)
=
-x_i
[

Заменить на обратную сторону:

[
frac{partial MSE}{partial beta_1}
=
frac{1}{n}
sum_{i=1}^{n}
2(y_i-beta_0-beta_1x_i)(-x_i)
[

Упрощать:

[
=
-frac{2}{n}
sum_{i=1}^{n}
x_i(y_i-beta_0-beta_1x_i)
[

Приравняйте производную к нулю:

[
-frac{2}{n}
sum_{i=1}^{n}
x_i(y_i-beta_0-beta_1x_i)
=
0
[

Умножьте обе стороны на:

[
-frac{n}{2}
] [
sum_{i=1}^{n}
x_i(y_i-beta_0-beta_1x_i)
=
0
[

Расширять:

[
sum_{i=1}^{n}x_iy_i
–
beta_0sum_{i=1}^{n}x_i
–
beta_1sum_{i=1}^{n}x_i^2
=
0
[

Заменять:

[
бета_0
=
bar{y}
–
β1̄x
[

в уравнение:

[
sum_{i=1}^{n}x_iy_i
–
(bar{y}-beta_1bar{x})
sum_{i=1}^{n}x_i
–
beta_1sum_{i=1}^{n}x_i^2
=
0
[

Расширять:

[
sum_{i=1}^{n}x_iy_i
–
bar{y}sum_{i=1}^{n}x_i
+
beta_1bar{x}sum_{i=1}^{n}x_i
–
beta_1sum_{i=1}^{n}x_i^2
=
0
[

С:

[
sum_{i=1}^{n}x_i=nbar{x}
[

Заменять:

[
sum_{i=1}^{n}x_iy_i
–
nbar{x}bar{y}
+
β1n x^2
–
beta_1sum_{i=1}^{n}x_i^2
=
0
[

Групповые члены ( beta_1 ):

[
бета_1
(nbar{x}^2-sum_{i=1}^{n}x_i^2)
=
nbar{x}bar{y}
–
sum_{i=1}^{n}x_iy_i
[

Умножьте обе стороны на -1:

[
бета_1
(sum_{i=1}^{n}x_i^2-nbar{x}^2)
=
sum_{i=1}^{n}x_iy_i
–
nbar{x}bar{y}
[

Формула для расчета окончательного уклона:

[
бета_1
=
frac{
sum_{i=1}^{n}x_iy_i
–
nbar{x}bar{y}
}{
sum_{i=1}^{n}x_i^2
–
nbar{x}^2
}
[

Эквивалентная форма ковариации:

[
бета_1
=
frac{
sum_{i=1}^{n}(x_i-bar{x})(y_i-bar{y})
}{
sum_{i=1}^{n}(x_i-bar{x})^2
}
[

Наконец, подставьте вычисленное значение ( beta_1 ) в уравнение свободного члена:

[
бета_0
=
bar{y}
–
β1̄x
[

Таким образом, окончательное уравнение регрессии принимает следующий вид:

[
hat{y}
=
бета_0
+
бета_1x
[

Итак, мы узнали, как получили формулы для наклона и точки пересечения с осью Y.

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

А что, если у нас более одного признака, как это обычно бывает в большинстве реальных наборов данных?

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

Вывод уравнения нормального состояния

В простой линейной регрессии мы вычислили один свободный член и один коэффициент наклона:

[
hat{y}
=
β₀ + β₁x
[

Однако реальные проблемы обычно содержат множество особенностей.

Например:

лет опыта
уровень образования
возраст

В таких случаях линейная регрессия принимает следующий вид:

[
hat{y}
=
бета_0
+
бета_1x_1
+
бета_2х_2
+
бета_3x_3
+
cdots
+
бета_px_p
[

где:

( beta_0 ) — это точка пересечения с осью Y, а
( beta_1,beta_2,beta_3,dots,beta_p ) — это наклоны для различных характеристик.

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

Для упрощения решения этой задачи линейная регрессия переписывается с использованием матричной записи.

Предположим, у нас есть ( n ) наблюдений и ( p ) признаков.

Сначала определите целевой вектор:

[
Я
=
begin{bmatrix}
y_1\
y_2\
y_3\
vdots\
y_n
end{bmatrix}
[

Теперь определим матрицу признаков.

В первом столбце содержатся только единицы, представляющие собой свободный член.

[
X
=
begin{bmatrix}
1 & x_{11} & x_{12} & cdots & x_{1p}\
1 & x_{21} & x_{22} & cdots & x_{2p}\
1 & x_{31} & x_{32} & cdots & x_{3p}\
vdots & vdots & vdots & ddots & vdots\
1 & x_{n1} & x_{n2} & cdots & x_{np}
end{bmatrix}
[

Теперь определим вектор параметров:

[
бета
=
begin{bmatrix}
бета_0
бета_1\
бета_2
vdots\
бета_п
end{bmatrix}
[

Использование матричного умножения:

[
Xбета
=
begin{bmatrix}
1 & x_{11} & x_{12} & cdots & x_{1p}\
1 & x_{21} & x_{22} & cdots & x_{2p}\
1 & x_{31} & x_{32} & cdots & x_{3p}\
vdots & vdots & vdots & ddots & vdots\
1 & x_{n1} & x_{n2} & cdots & x_{np}
end{bmatrix}
begin{bmatrix}
бета_0
бета_1\
бета_2
vdots\
бета_п
end{bmatrix}
[

Выполнение умножения:

[
=
begin{bmatrix}
beta_0+beta_1x_{11}+beta_2x_{12}+cdots+beta_px_{1p}\
beta_0+beta_1x_{21}+beta_2x_{22}+cdots+beta_px_{2p}\
beta_0+beta_1x_{31}+beta_2x_{32}+cdots+beta_px_{3p}\
vdots\
β₀ + β₁xn₁ + β₂xn₂ + cdots + βpxnp
end{bmatrix}
[

Это даёт вектор прогноза:

[
hat{Y}=Xbeta
[

Теперь определим вектор остатков.

Остаточные значения представляют собой разницу между фактическими и прогнозируемыми значениями.

[
Y-hat{Y}
[

Замена:

[
YXбета
[

Среднеквадратичная ошибка (MSE) принимает следующий вид:

[
МСЕ
=
frac{1}{n}
(YXbeta)^T(YXbeta)
[

Транспонирование необходимо, потому что:

[
(YXbeta)
[

является вектор-столбцом.

Умножение на транспонированную матрицу преобразует выражение в скалярную сумму квадратов остатков.

Теперь разверните выражение.

[
МСЕ
=
frac{1}{n}
(YXbeta)^T(YXbeta)
] [
=
frac{1}{n}
левый(
Y^TY
–
Y^TXбета
–
(Xbeta)^TY
+
(Xbeta)^TXbeta
верно)
[

Использование свойства транспонирования:

[
(Xbeta)^T
=
βTXT
[

Подставьте в уравнение:

[
МСЕ
=
frac{1}{n}
левый(
Y^TY
–
Y^TXбета
–
βTXTY
+
β^TX^TXβ
верно)
[

Обратите внимание, что:

[
Y^TXбета
[

является скалярной величиной.

Скаляры равны своим транспонированным значениям.

Поэтому:

[
Y^TXбета
=
βTXTY
[

Таким образом, два средних термина объединяются:

[
МСЕ
=
frac{1}{n}
левый(
Y^TY
–
2beta^TX^TY
+
β^TX^TXβ
верно)
[

Для минимизации среднеквадратичной ошибки (MSE) возьмите производную по ( beta ).

Производная от:

[
Y^TY
[

равно нулю, потому что не содержит ( beta ).

Производная от:

[
-2beta^TX^TY
[

становится:

[
-2X^TY
[

Производная от:

[
β^TX^TXbeta
[

становится:

[
2X^TXbeta
[

Поэтому:

[
frac{partial MSE}{partial beta}
=
frac{1}{n}
левый(
-2X^TY
+
2X^TXbeta
верно)
[

Упрощать:

[
=
frac{-2}{n}X^TY
+
frac{2}{n}X^TXbeta
[

Для минимизации приравняйте производную к нулю:

[
frac{-2}{n}X^TY
+
frac{2}{n}X^TXbeta
=
0
[

Умножьте обе стороны на:

[
frac{n}{2}
] [
-X^TY
+
X^TXбета
=
0
[

Переставьте:

[
X^TXбета
=
X^TY
[

Теперь умножьте обе стороны на:

[
(X^TX)^{-1}
] [
(X^TX)^{-1}X^TXbeta
=
(X^TX)^{-1}X^TY
[

Используя свойство единичной матрицы:

[
(X^TX)^{-1}(X^TX)=I
[

мы получаем:

[
Iбета
=
(X^TX)^{-1}X^TY
[

С:

[
Ibeta=beta
[

В итоге уравнение нормального распределения принимает следующий вид:

[
бета
=
(X^TX)^{-1}X^TY
[

Это уравнение одновременно вычисляет:

перехват
все склоны
оптимальные параметры

которые минимизируют среднеквадратичную ошибку.

В общем случае, нормальное уравнение выводится путем минимизации суммы квадратов остатков (RSS). Однако, поскольку среднеквадратичная ошибка (MSE) — это просто сумма квадратов остатков, деленная на количество наблюдений, минимизация MSE также приводит к тому же нормальному уравнению.

Теперь у нас есть уравнение нормального распределения. Давайте снова найдем наклон и точку пересечения с осью Y, используя это уравнение.

Определение наклона и точки пересечения с осью Y с помощью уравнения нормального распределения

Матричная форма линейной регрессии выглядит следующим образом:

[
β=(X^TX)^{-1}X^TY
[

Постройте матрицу признаков.

В первом столбце в качестве свободного члена указаны единицы.

[
X
=
begin{bmatrix}
1 и 1.2\
1 и 1.4\
1 и 1.6\
1 и 2.1\
1 и 2.3\
1 и 3.0\
1 и 3.1\
1 и 3.3\
1 и 3.3\
1 и 3.8
end{bmatrix}
[

Сформируйте целевой вектор:

[
Я
=
begin{bmatrix}
39344\
46206\
37732\
43526\
39892\
56643\
60151\
54446\
64446\
57190
end{bmatrix}
[

Вектор параметров:

[
бета
=
begin{bmatrix}
бета_0
бета_1
end{bmatrix}
[

Теперь вычислим транспонированную матрицу:

[
X^T
=
begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\
1.2 & 1.4 & 1.6 & 2.1 & 2.3 & 3.0 & 3.1 & 3.3 & 3.3 & 3.8
end{bmatrix}
[

Вычислить:

[
X^TX
=
begin{bmatrix}
10 и 25.1\
25.1 и 67.89
end{bmatrix}
[

Теперь вычислим обратную функцию:

[
(X^TX)^{-1}
=
begin{bmatrix}
1.4547 и -0.5378\
-0,5378 и 0,2142
end{bmatrix}
[

Теперь вычислим:

[
X^TY
=
begin{bmatrix}
493576\
1326200.7
end{bmatrix}
[

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

[
бета
=
begin{bmatrix}
1.4547 и -0.5378\
-0,5378 и 0,2142
end{bmatrix}
begin{bmatrix}
493576\
1326200.7
end{bmatrix}
[

После умножения:

[
бета
=
begin{bmatrix}
27315.02\
9020.93
end{bmatrix}
[

Поэтому:

[
β₀ = 27315,02
] [
β1=9020.93
[

Итоговое уравнение регрессии:

[
hat{y}
=
27315.02+9020.93x
[

Зачем нам нужен градиентный спуск?

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

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

Рассмотрим уравнение нормального распределения:

[
β = (X^TX)^{-1}X^Ty
[

Из уравнения видно, что обратный расчет необходим, и именно здесь вычисление наклона и точки пересечения с осью Y с помощью уравнения нормального распределения становится вычислительно затратным.

Этот метод хорошо работает для небольших наборов данных, но в реальном мире мы часто имеем дело с тысячами признаков и миллионами точек данных.

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

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

Чтобы понять, как работает градиентный спуск, давайте рассмотрим математическую основу этого процесса.

Математические основы градиентного спуска

При выводе уравнения нормального распределения мы пришли к этому уравнению.

[
frac{partial MSE}{partial beta}
=
frac{2}{n}X^T(Xbeta-Y)
[

Это уравнение представляет собой градиент (наклон) чашеобразной кривой потерь.

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

Однако в градиентном спуске мы останавливаемся на этом уравнении и инициализируем случайными значениями βbeta . Используя эти значения, мы вычисляем градиент (наклон) и постепенно шаг за шагом приближаемся к минимальной функции потерь.

Предположим, мы выполним инициализацию:

β0=2beta_0 = 2 и β1=5beta_1 = 5

[
β(0) =
begin{bmatrix}
бета_0
бета_1
end{bmatrix}
=
begin{bmatrix}
2 \
5
end{bmatrix}
[

Далее мы вычисляем наклон кривой чаши, подставляя эти значения в уравнение градиента.

Мы уже знаем, что уравнение градиента имеет вид:

[
frac{partial MSE}{partial beta}
=
frac{-2}{n}X^Ty
+
frac{2}{n}X^TXbeta
[

Начальные значения параметров следующие:

[
β(0) =
begin{bmatrix}
2 \
5
end{bmatrix}
[

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

Теперь давайте построим матрицу признаков.

Поскольку у нас есть одна характеристика, матрица (X) принимает следующий вид:

[
X=
begin{bmatrix}
1 и 1.2 \
1 и 1.4 \
1 и 1.6 \
1 и 2.1 \
1 и 2.3 \
1 и 3.0 \
1 и 3.1 \
1 и 3.3 \
1 и 3.3 \
1 и 3.8
end{bmatrix}
[

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

Теперь произведите:

[
X^T
] [
X^T=
begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \
1.2 & 1.4 & 1.6 & 2.1 & 2.3 & 3.0 & 3.1 & 3.3 & 3.3 & 3.8
end{bmatrix}
[

Теперь произведите:

[
X^TX
] [
X^TX=
begin{bmatrix}
10 и 25.1 \
25.1 и 67.89
end{bmatrix}
[

Далее, пусть целевой вектор будет следующим:

[
y=
begin{bmatrix}
39344 \
46206 \
37732 \
43526 \
39892 \
56643 \
60151 \
54446 \
64446 \
57190
end{bmatrix}
[

Теперь произведите:

[
X^Ty
] [
X^Ty=
begin{bmatrix}
493576 \
1326200.7
end{bmatrix}
[

Поскольку наш набор данных содержит:

[
n=10
[

Теперь подставьте все значения в уравнение градиента:

[
frac{partial MSE}{partial beta}
=
frac{-2}{10}
begin{bmatrix}
493576 \
1326200.7
end{bmatrix}
+
frac{2}{10}
begin{bmatrix}
10 и 25.1 \
25.1 и 67.89
end{bmatrix}
begin{bmatrix}
2 \
5
end{bmatrix}
[

Сначала вычислим умножение матриц:

[
begin{bmatrix}
10 и 25.1 \
25.1 и 67.89
end{bmatrix}
begin{bmatrix}
2 \
5
end{bmatrix}
=
begin{bmatrix}
(10)(2)+(25.1)(5) \
(25.1)(2)+(67.89)(5)
end{bmatrix}
] [
=
begin{bmatrix}
20+125.5 \
50.2+339.45
end{bmatrix}
] [
=
begin{bmatrix}
145.5 \
389.65
end{bmatrix}
[

Теперь умножьте на:

[
frac{2}{10}
] [
frac{2}{10}
begin{bmatrix}
145.5 \
389.65
end{bmatrix}
=
begin{bmatrix}
29.1 \
77.93
end{bmatrix}
[

Далее произведите расчет:

[
frac{-2}{10}
begin{bmatrix}
493576 \
1326200.7
end{bmatrix}
=
begin{bmatrix}
-98715.2 \
-265240.14
end{bmatrix}
[

Теперь верните все на свои места:

[
frac{partial MSE}{partial beta}
=
begin{bmatrix}
-98715.2 \
-265240.14
end{bmatrix}
+
begin{bmatrix}
29.1 \
77.93
end{bmatrix}
[

Окончательно:

[
frac{partial MSE}{partial beta}
=
begin{bmatrix}
-98686.1 \
-265162.21
end{bmatrix}
[

Этот градиент представляет собой наклон чашеобразной кривой потерь MSE при текущих значениях параметров.

Здесь:

[
-98686.1
[

представляет собой наклон относительно (beta_0)

и

[
-265162.21
[

представляет собой наклон относительно (beta_1)

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

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

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

[
beta:=beta-alphafrac{partial MSE}{partial beta}
[

где:

[
альфа
[

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

Уравнение обновления можно понять шаг за шагом.

[
бета
[

представляет текущие значения параметров.

[
frac{partial MSE}{partial beta}
[

представляет собой наклон (градиент) чашеобразной кривой потерь в текущей точке.

Градиент показывает нам направление, в котором потери возрастают быстрее всего.

Следовательно, чтобы уменьшить потери, мы движемся в направлении, противоположном градиенту.

Вот почему в уравнении обновления вычитается градиент:

[
beta:=beta-alphafrac{partial MSE}{partial beta}
[

Здесь:

[
альфа
[

управляет величиной каждого шага при движении к минимальной точке.

Если градиент положительный, градиентный спуск движется влево.

Если градиент отрицательный, градиентный спуск движется вправо.

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

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

Здесь мы можем заметить, что обратные вычисления не требуются.

Скорость обучения

Здесь важно понимать один важный момент — скорость обучения.

Предположим:

[
α = 0,01
[

а вычисленный градиент равен:

[
frac{partial MSE}{partial beta}
=
begin{bmatrix}
-98686.1 \
-265162.21
end{bmatrix}
[

Теперь подставьте эти значения в уравнение обновления:

[
бета=
begin{bmatrix}
2 \
5
end{bmatrix}
–
0,01
begin{bmatrix}
-98686.1 \
-265162.21
end{bmatrix}
[

Сначала умножим скорость обучения на градиент:

[
0,01
begin{bmatrix}
-98686.1 \
-265162.21
end{bmatrix}
=
begin{bmatrix}
-986.861 \
-2651.6221
end{bmatrix}
[

Теперь вернёмся обратно:

[
бета=
begin{bmatrix}
2 \
5
end{bmatrix}
–
begin{bmatrix}
-986.861 \
-2651.6221
end{bmatrix}
[

затем

[
бета=
begin{bmatrix}
2+986.861 \
5+2651.6221
end{bmatrix}
[

Окончательно:

[
бета=
begin{bmatrix}
988.861 \
2656.6221
end{bmatrix}
[

После одной итерации градиентного спуска:

[
бета_0
[

изменено с:

[
2 rightarrow 988.861
[

и

[
бета_1
[

изменено с:

[
5 rightarrow 2656.6221
[

Эти обновленные значения параметров приближают нас к минимальной точке кривой потерь MSE чашеобразной формы.

Теперь, используя эти обновленные значения, весь процесс повторяется снова:

[
Прогнозы
rightarrow
Остатки
rightarrow
Убыток
rightarrow
Градиент
rightarrow
Обновление параметров
[

Этот итеративный процесс продолжается до тех пор, пока потери не станут минимальными и модель не достигнет оптимальных параметров.

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

Если скорость обучения очень мала:

[
α = 0,000001
[

тогда обновления становятся крайне незначительными.

Как результат:

[
Очень медленное обучение
[

А для достижения минимальной точки методом градиентного спуска могут потребоваться тысячи итераций.

С другой стороны, если скорость обучения очень высока:

[
α = 10
[

тогда обновления становятся чрезвычайно большими.

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

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

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

Теперь у нас есть представление о том, что такое градиентный спуск.

В этом методе мы можем заметить, что для вычисления градиентов перед обновлением параметров мы использовали весь набор данных.

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

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

Для каждого шага обновления градиентному спуску потребуется:

[
Обработка всего набора данных
] [
text{Рассчитать потери}
] [
Вычисление градиентов
[

и наконец, обновить параметры.

Повторяющиеся вычисления становятся вычислительно затратным и трудоемким процессом.

Именно здесь вступает в игру стохастический градиентный спуск (SGD).

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

Формула обновления остается неизменной:

[
beta:=beta-alphafrac{partial MSE}{partial beta}
[

Единственное отличие заключается в том, что теперь градиент рассчитывается на основе одного наблюдения, а не всего набора данных.

Мы можем это понять, используя одну точку данных из нашего набора данных.

Значения параметров следующие:

[
β(0) =
begin{bmatrix}
2 \
5
end{bmatrix}
[

а скорость обучения составляет:

[
α = 0,01
[

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

[
(x,y)=(3.0,56643)
[

В отношении этого единственного наблюдения:

[
X=
begin{bmatrix}
1 и 3.0
end{bmatrix}
[

и

[
y=
begin{bmatrix}
56643
end{bmatrix}
[

Теперь произведите:

[
X^T=
begin{bmatrix}
1 \
3.0
end{bmatrix}
[

Далее выполните расчет:

[
X^TX
] [
=
begin{bmatrix}
1 \
3.0
end{bmatrix}
begin{bmatrix}
1 и 3.0
end{bmatrix}
] [
=
begin{bmatrix}
1 и 3.0 \
3.0 и 9.0
end{bmatrix}
[

Теперь произведите:

[
X^Ty
] [
=
begin{bmatrix}
1 \
3.0
end{bmatrix}
begin{bmatrix}
56643
end{bmatrix}
] [
=
begin{bmatrix}
56643 \
169929
end{bmatrix}
[

Поскольку SGD использует только одно наблюдение:

[
n=1
[

Теперь подставим все значения в уравнение градиента:

[
frac{partial MSE}{partial beta}
=
frac{-2}{n}X^Ty
+
frac{2}{n}X^TXbeta
[

Замена:

[
=
frac{-2}{1}
begin{bmatrix}
56643 \
169929
end{bmatrix}
+
frac{2}{1}
begin{bmatrix}
1 и 3.0 \
3.0 и 9.0
end{bmatrix}
begin{bmatrix}
2 \
5
end{bmatrix}
[

Сначала вычислите умножение матриц:

[
begin{bmatrix}
1 и 3.0 \
3.0 и 9.0
end{bmatrix}
begin{bmatrix}
2 \
5
end{bmatrix}
] [
=
begin{bmatrix}
(1)(2)+(3.0)(5) \
(3.0)(2)+(9.0)(5)
end{bmatrix}
] [
=
begin{bmatrix}
2+15 \
6+45
end{bmatrix}
] [
=
begin{bmatrix}
17 \
51
end{bmatrix}
[

Теперь умножьте на:

[
frac{2}{1}
] [
=
begin{bmatrix}
34 \
102
end{bmatrix}
[

Теперь произведите:

[
frac{-2}{1}
begin{bmatrix}
56643 \
169929
end{bmatrix}
=
begin{bmatrix}
-113286 \
-339858
end{bmatrix}
[

Теперь верните все на свои места:

[
frac{partial MSE}{partial beta}
=
begin{bmatrix}
-113286 \
-339858
end{bmatrix}
+
begin{bmatrix}
34 \
102
end{bmatrix}
[

Окончательно:

[
frac{partial MSE}{partial beta}
=
begin{bmatrix}
-113252 \
-339756
end{bmatrix}
[

Этот градиент представляет собой наклон чашеобразной кривой функции потерь для данного единственного обучающего примера.

Теперь обновите параметры, используя:

[
beta:=beta-alphafrac{partial MSE}{partial beta}
[

Подставляем значения:

[
бета=
begin{bmatrix}
2 \
5
end{bmatrix}
–
0,01
begin{bmatrix}
-113252 \
-339756
end{bmatrix}
[

Сначала умножьте скорость обучения:

[
=
begin{bmatrix}
2 \
5
end{bmatrix}
–
begin{bmatrix}
-1132.52 \
-3397.56
end{bmatrix}
[

Теперь вычтем:

[
=
begin{bmatrix}
2+1132.52 \
5+3397.56
end{bmatrix}
[

Окончательно:

[
бета=
begin{bmatrix}
1134.52 \
3402.56
end{bmatrix}
[

После решения задачи для одного наблюдения параметры немедленно обновляются.

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

В отличие от пакетного градиентного спуска, который ожидает обработки всего набора данных перед обновлением параметров, SGD обновляет параметры после каждого отдельного обучающего примера.

Благодаря частым обновлениям, SGD быстрее находит решение.

Мы можем наблюдать, насколько упрощается вычисление при использовании всего одного наблюдения.

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

Однако путь к точке минимума становится шумным и извилистым.

Благодаря этому метод SGD чрезвычайно полезен для решения современных задач машинного обучения и глубокого обучения, связанных с очень большими наборами данных.

Заключение

Теперь у нас есть представление как о градиентном спуске, так и о стохастическом градиентном спуске.

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

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

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

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

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

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

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

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

Лицензия на набор данных

В этом блоге используется набор данных о зарплатах .

Он находится в открытом доступе на Kaggle и распространяется под лицензией Creative Commons Zero (CC0 Public Domain) . Это означает, что его можно свободно использовать, изменять и распространять как в некоммерческих, так и в коммерческих целях без ограничений.

Надеюсь, теперь вы лучше понимаете, что такое градиентный спуск и стохастический градиентный спуск.

Если вы хотите прочитать другие мои статьи, вы также можете найти их на Medium и LinkedIn.

Недавно я написал подробный анализ регрессии Lasso с геометрической и интуитивной точек зрения.

Вы можете прочитать это здесь.

Спасибо за прочтение!

Нихил Дасари Посмотреть все от Нихила Дасари

Источник: towardsdatascience.com