Математика для штучних нейронних мереж для новачків, частина 3 — градієнтний спуск продовження

Частина 2 — градієнтний спуск початок

У попередній частині я почав розбір алгоритму оптимізації під назвою градієнтний спуск. Попередня стаття обірвалося на письмі варіанти алгоритму під назвою пакетний градієнтний спуск.

Існує й інша версія алгоритму — стохастичний градієнтний спуск. Стохастичний = випадковий.

Повторювати, поки не зійдеться
 

 
{
 
for i in train_set
 
{
 
<img src="https://habrastorage.org/files/315/021/f18/315021f1836946cf9809242aa70dc04e.png"/>
 
}
 
}
 

Також нагадаю як виглядає пакетний:

Повторювати, поки не зійдеться
 
{
 
<img src="https://habrastorage.org/files/278/d47/22d/278d4722d3f048ac8d24eec1fa1b38ca.png"/>
 
}
 

Формули схожі, але, як видно, пакетний градієнтний спуск обчислює один крок, використовуючи відразу весь набір даних, тоді як стохастичний за крок використовує тільки 1 елемент. Можна два варіанти схрестити, отримавши міні-пакетний (mini-batch) спуск, який за раз обробляє, приміром, 100 елементів, а не всі або один.

Два варіанти ведуть себе схоже, але не однаково. Пакетний спуск дійсно слід в напрямку найшвидшого спуску, тоді як стохастичний, використовуючи тільки один елемент з навчальної вибірки, не може вірно обчислити градієнт для всієї вибірки. Це розходження простіше пояснити графічно. Для цього я модифицирую код з першої частини, в якому обчислювалися коефіцієнти лінійної регресії. Функція вартості для неї виглядає наступним чином:

Як видно, це трохи витягнутий параболоїд. І також його «вигляд зверху», де відзначений хрестом істинний мінімум, знайдений аналітично.

Спершу розглянемо, як веде себе пакетний спуск:

Код
def batch_descent(A, Y, speed=0.001):
theta = np.array(INITIAL_THETA.copy(), dtype=np.float32)
theta.reshape((len(theta), 1))
previous_cost = 10 ** 6
current_cost = cost_function(A, Y, theta)
while np.abs(previous_cost - current_cost) > EPS:
previous_cost = current_cost
derivatives = [0] * len(theta)
# ---------------------------------------------
for j in range(len(theta)):
summ = 0
for i in range(len(Y)):
summ += (Y[i] - A[i]@theta) * A[i][j]
derivatives[j] = summ
# Виконання вимоги одновремменности
theta[0] += speed * derivatives[0]
theta[1] += speed * derivatives[1]
# ---------------------------------------------
current_cost = cost_function(A, Y, theta)
print("Batch cost:", current_cost)
plt.plot(theta[0], theta[1], 'ro')
return theta


Пакетний-анімація

З-за того, що параболоїд витягнутий, з його «дна» проходить «яр», в який ми потрапляємо. З-за цього останні кроки вздовж цього яру дуже маленькі, але тим не менш рано чи пізно градієнтний спуск добереться до мінімуму. Спуск відбувається по лінії антиградієнта, кожен крок наближаючись до мінімуму.

Тепер та ж сама функція, але для стохастичного спуску:

Код
def stochastic_descent(A, Y, speed=0.1):
theta = np.array(INITIAL_THETA.copy(), dtype=np.float32)
previous_cost = 10 ** 6
current_cost = cost_function(A, Y, theta)
while np.abs(previous_cost - current_cost) > EPS:
previous_cost = current_cost
# --------------------------------------
# for i in range(len(Y)):
i = np.random.randint(0, len(Y))
derivatives = [0] * len(theta)
for j in range(len(theta)):
derivatives[j] = (Y[i] - A[i]@theta) * A[i][j]
theta[0] += speed * derivatives[0]
theta[1] += speed * derivatives[1]
current_cost = cost_function(A, Y, theta)
print("Stochastic cost:", current_cost)
plt.plot(theta[0], theta[1], 'ro')
# --------------------------------------
current_cost = cost_function(A, Y, theta)
return theta


У визначенні сказано, що вибирається тільки один елемент — в цьому коді кожен наступний елемент вибирається випадковим чином.

Стохастичний-анімація

Як видно, у разі стохастичного варіанти, спуск йде не по лінії антиградієнта, а взагалі незрозуміло як — кожен крок відхиляючись у випадкову сторону. Може здатися, що такими випадковими дергаными рухами до мінімуму можна прийти тільки випадково, однак було доведено, що стохастичний градієнтний спуск сходиться майже напевно. Пару посилання, наприклад.

Весь код цілком
import numpy as np
import matplotlib.pyplot as plt

TOTAL = 200
STEP = 0.25
EPS = 0.1
INITIAL_THETA = [9, 14]


def func(x):
return 0.2 * x + 3


def generate_sample(total=TOTAL):
x = 0
while $ x < total * STEP:
yield func(x) + np.random.uniform(-1, 1) * np.random.uniform(2, 8)
x += STEP


def cost_function(A, Y, theta):
return (Y - A@theta).T@(Y - A@theta)


def batch_descent(A, Y, speed=0.001):
theta = np.array(INITIAL_THETA.copy(), dtype=np.float32)
theta.reshape((len(theta), 1))
previous_cost = 10 ** 6
current_cost = cost_function(A, Y, theta)
while np.abs(previous_cost - current_cost) > EPS:
previous_cost = current_cost
derivatives = [0] * len(theta)
# ---------------------------------------------
for j in range(len(theta)):
summ = 0
for i in range(len(Y)):
summ += (Y[i] - A[i]@theta) * A[i][j]
derivatives[j] = summ
# Виконання вимоги одновремменности
theta[0] += speed * derivatives[0]
theta[1] += speed * derivatives[1]
# ---------------------------------------------
current_cost = cost_function(A, Y, theta)
print("Batch cost:", current_cost)
plt.plot(theta[0], theta[1], 'ro')
return theta


def stochastic_descent(A, Y, speed=0.1):
theta = np.array(INITIAL_THETA.copy(), dtype=np.float32)
previous_cost = 10 ** 6
current_cost = cost_function(A, Y, theta)
while np.abs(previous_cost - current_cost) > EPS:
previous_cost = current_cost
# --------------------------------------
# for i in range(len(Y)):
i = np.random.randint(0, len(Y))
derivatives = [0] * len(theta)
for j in range(len(theta)):
derivatives[j] = (Y[i] - A[i]@theta) * A[i][j]
theta[0] += speed * derivatives[0]
theta[1] += speed * derivatives[1]
# --------------------------------------
current_cost = cost_function(A, Y, theta)
print("Stochastic cost:", current_cost)
plt.plot(theta[0], theta[1], 'ro')
return theta

X = np.arange(0, TOTAL * STEP, STEP)
Y = np.array([y for y in generate_sample(TOTAL)])

# Нормалізацію вкрячил, щоб гарний був парабалоид
X = (X - X min()) / (X. max() - X. min())

A = np.empty(TOTAL, 2))
A[:, 0] = 1
A[:, 1] = X

theta = np.linalg.pinv(A).dot(Y)
print(theta, cost_function(A, Y, theta))

import time
start = time.clock()
theta_stochastic = stochastic_descent(A, Y, 0.001)
print("St:", time.clock() - start, theta_stochastic)

start = time.clock()
theta_batch = batch_descent(A, Y, 0.001)
print("Btch:", time.clock() - start, theta_batch)


На 200 елементах різниці в швидкості майже ніякої немає, однак, збільшивши кількість елементів до 2000 (що теж дуже мало) і підкоригувавши швидкість навчання, стохастичний варіант б'є пакетний, як хоче. Однак, в силу стохастичної природи, метод іноді промахується, осциллируя біля мінімуму без можливості зупинитися. Якось так:



Цей факт робить непридатною чисту реалізацію. Щоб якось закликати до порядку і знизити «випадковість» можна зменшити швидкість навчання. На практиці застосовують mini-batch варіацію — від стохастичної вона відрізняється тим, що замість одного випадково обраного елемента вибирають більше одного.

Про різницю, плюси і мінуси даних двох підходів написано досить багато, коротко підведу підсумок:

— Пакетний спуск хороший для строго опуклих функцій, тому що впевнено прагне до мінімуму глобального або локального.
— Стохастичний в свою чергу краще працює на функціях з великою кількістю локальних мінімумів — кожен крок є шанс, що чергове значення «виб'є» з локальної ями і кінцеве рішення буде більш оптимальним, ніж для пакетного спуску.
— Стохастичний обчислюється швидше — на кожному кроці потрібні не всі елементи вибірки. Вся вибірка цілком може не влізти в пам'ять. Але потрібно більше кроків.
— Для стохастичного легко додати нові елементи, під час роботи (онлайн навчання).
— У разі mini-batch, можна також векторизовать код, що значно прискорить його виконання.

Також у градієнтного спуску існує безліч модифікацій — momentum, найшвидшого спуску, усереднення, Adagrad, AdaDelta, RMSProp та інші. Тут можна подивитися короткий огляд деяких. Частенько вони використовують значення градієнта з попередніх кроків або автоматично обчислюють найкраще значення швидкості для даного кроку. Використання цих методів для простої гладкої функції МНК не має особливого сенсу, але в разі нейронних мереж і мереж з великою кількістю шарів\нейронів, функція вартості стає зовсім сумною і градієнтний спуск може застрягти в локальній ямі, так і не досягнувши оптимального рішення. Для таких проблем підходять методи на стероїдах. Ось приклад функції простий для мінімізації (двовимірна лінійна регресія з МНК):

І приклад нелінійної функції:



Градієнтний спуск — метод оптимізації першого порядку (перша похідна). Також існує багато методів другого порядку — для них необхідно обчислювати другу похідну і будувати гессе (досить витратна операція — ). Наприклад, градієнтний спуск другого порядку (швидкість навчання замінили на гессе), BFGS, пов'язані градієнти, метод Ньютона і ще величезна кількість інших методів. Загалом, оптимізація — це окремий і дуже широкий пласт проблем. Втім, ось приклад (правда, всього лише презентація) роботи + відео Яна Лекуна, в який він каже, що можна не париться і просто використовувати градієнтні методи. Навіть враховуючи, що презентація 2007 року, останні експерименти з великими ІНС використовували градієнтні методи. Наприклад.

На голих циклах далеко не заїдеш — код потребує векторизації. Основний алгоритм для векторизації — пакетний градієнтний спуск, із застереженням, що , де k — кількість елементів в тестовій вибірці. Таким чином векторизація підходить для mini-batch методу. Як і в минулий раз я випишу все в розкритих векторах. Зверніть увагу, що перша матриця транспонирована —



Для доказу, пройдемо кілька кроків у зворотний бік:





З попередньої формули, в кожному рядку індекс j зафіксований, а i — змінюється від 1 до n. Звернувши суму:



Це вираз точно таке ж, що і у визначенні градієнтного спуску. Нарешті, завершальний етап — згортання векторів і матриць:



Вартість одного такого кроку — , де n — кількість елементів, p — кількість ознак. Багато краще . Також зустрічається вираз, тотожне цього:



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

» Для запуску прикладів необхідні: numpy, matplotlib.
» Матеріали, використані в статті — github.com/m9psy/neural_network_habr_guide
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.