Градієнтний спуск- Найбільш використовуваний алгоритм навчання, він застосовується майже в кожній моделі. Градієнтний спуск - це, по суті, і є те, як навчаються моделі. Без ГС машинне навчання не було б там, де зараз. Метод градієнтного спуску з деякою модифікацією широко використовується для навчання і глибоких і відомий як помилки.
У цьому пості ви знайдете пояснення градієнтного спуску з невеликою кількістю математики. Короткий зміст:
- Сенс ГС - пояснення всього алгоритму;
- Різні варіації алгоритму;
- Реалізація коду: написання коду мовою 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. Mini-batch: тут замість перебирання всіх прикладів навчання і з кожною ітерацією, що виконує обчислення тільки одному прикладі навчання, ми обробляємо n навчальних прикладів відразу. Цей вибір хороший для великих наборів даних.
2.Стохастичний градієнтний спуск: у цьому випадку замість використання та зациклювання на кожному прикладі навчання, ми ПРОСТО ВИКОРИСТОВУЄМО ОДИН РАЗ. Є кілька речей зауважень:
- З кожною ітерацією ГС вам потрібно перемішати набір навчання та вибрати випадковий прикладнавчання.
- Оскільки ви використовуєте лише один приклад навчання, ваш шлях до локальних мінімумів буде дуже галасливим, як у п'яної людини, яка багато випила.
3. Серія ГС: це те, про що написано в попередніх розділах Цикл кожному прикладі навчання.
Картинка, що порівнює 3 влучення в локальні мінімуми Приклад коду на python
Стосовно серії ГС, так буде виглядати блок навчального коду на 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. 1. Iterate over all examples, # 2. Compute gradients of weights and biases in w_grad and b_grad, # 3. Update dW by add w_grad and dB by add 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.
От і все. Тепер ви повинні добре розуміти, що таке метод градієнтного спуску.
У цій лекції ми обговоримо різні способиреалізації, про їх переваги та недоліки. Я б хотів поговорити про три основні типи градієнтного спуску - повний, пакетний і стохастичне.
У більшості попередніх курсів ми скористалися повним градієнтним спуском.
Чому так?
Тому що це приносить більше користіякщо ми хочемо максимізувати правдоподібність для всього навчального набору:
Недоліком такого підходу є те, що обчислення градієнта займає багато часу, оскільки залежить від кожного прикладу (спостереження).
Повною протилежністю є стохастичний градієнтний спуск. Він залежить від помилки лише одного конкретного спостереження:
Метод ґрунтується на тому факті, що всі спостереження є незалежними та рівномірно розподіленими, тому в довгостроковій перспективі помилка буде зменшуватися, адже всі спостереження беруться з одного розподілу. У такому випадку, коли розрахунки скоротилися від Nспостережень до 1, це чудове поліпшення методу.
У чому ж недолік?
Справа в тому, що якщо при повному градієнтному спуску логарифм функції правдоподібності завжди покращується на кожній ітерації, то при стохастичному логарифм правдоподібності може навіть погіршитися. Насправді поведінка функції витрат хаотично змінюватиметься при кожній ітерації, але в довгостроковій перспективі вона все ж таки зменшиться.
Вдалим компромісів між цими двома методами є пакетний градієнтний спуск. Якщо ми маємо, наприклад, 10 000 спостережень, ми можемо розділити їх у 100 пакетів по 100 спостережень у кожному і обчислювати функцію витрат, грунтуючись кожному пакеті за кожної итерации:
Що буде з функцією витрат?
Вона теж може ставати більше, але буде менш хаотичною, ніж у випадку суто стохастичного градієнтного спуску.
І, користуючись нагодою, хочу зазначити, що якщо ви бажаєте отримати безкоштовний матеріал, пов'язаний з глибоким і машинним навчанням, а також обробкою даних, відвідайте мій сайт lazyprogrammer.me. Я постійно пишу нові матеріали на ці теми, так що перевіряйте частіше. Там має з'явитися пропозиція підписатися, так що ви можете передплатити моє безкоштовне введенняу обробку даних. У ньому багато чудових ресурсів для вивчення мови Python, алгоритми і структури даних, а також купони на курси на .
Повний, пакетний та стохастичний градієнтний спуск у коді
Тепер порівняємо зміну функції витрат у трьох випадках градієнтного спуску – повного, пакетного та стохастичного. Оскільки в цьому прикладі багато коду скопійовано з інших файлів, ми просто пройдемося по тексту програми.
Отже, спочатку файлу ми імпортуємо всі звичайні бібліотеки. З файлу util.py ми імпортуємо функцію get_transformed_data, щоб перетворити дані методом головних компонент, і навіть функції forward, error_date, cost, gradW, gradbі y2індикатор.
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
від sklearn.utils import shuffle
від 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): # так дуже 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 * (grad W (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
Надіслати свою гарну роботу до бази знань просто. Використовуйте форму нижче
Студенти, аспіранти, молоді вчені, які використовують базу знань у своєму навчанні та роботі, будуть вам дуже вдячні.
Розміщено на http://www.allbest.ru/
Міністерство освіти та науки РФ
Федеральна державна автономна освітня установа
Вищої освіти
«КАЗАНСЬКИЙ (ПРИВОЛЖСЬКИЙ) ФЕДЕРАЛЬНИЙ УНІВЕРСИТЕТ»
ВИЩА ШКОЛА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ ТА ІНФОРМАЦІЙНИХ СИСТЕМ
КУРСОВА РОБОТА
Стохастичний градієнт спуску. Варіанти реалізації
Вступ
Градієнтний спуск - метод знаходження локального екстремуму (мінімуму чи максимуму) функції за допомогою руху вздовж градієнта.
З усіх методів локальної оптимізації є найпростішим у реалізації. Має досить слабкі умови збіжності, та заодно швидкість збіжності досить мала.
Градієнтний спуск є популярним алгоритмом для широкого спектру моделей машинного навчання, у тому числі знаходження опорних векторів, логістичної регресії та графічних моделей. У поєднанні з алгоритмом зворотного поширення це стандартний алгоритм для навчання штучних нейронних мереж. Стохастичний градієнтний спуск конкурує з алгоритмом L-BFGS, що також широко використовується. Стохастичний градієнтний спуск був використаний, Крайній мірі, в 1960 році для навчання лінійних регресійних моделей, спочатку під назвою Adaline.
Метою даної курсової роботиє розгляд реалізації кількох варіантів стохастичного градієнтного спуску, подальше їх порівняння, з'ясування переваг та недоліків.
1. Стохастичний градієнтний спуск
Стохастичний градієнтний спуск відноситься до оптимізаційних алгоритмів і часто використовується для налаштування параметрів моделі машинного навчання.
При стандартному спуску градієнта для зміни параметрів моделі використовується градієнт. Градієнт зазвичай обчислюється як сума градієнтів, спричинених кожним елементом навчання. Вектор параметрів змінюється у напрямку антиградієнта із заданим кроком. Тому стандартному градієнтному спуску потрібен один прохід за навчальними даними, перш ніж він зможе змінювати параметри.
При стохастичному спуску градієнта значення градієнта приблизно обчислюється градієнтом функції вартості, обчисленому тільки на одному елементі навчання. Потім параметри змінюються пропорційно до наближеного градієнта. Таким чином, параметри моделі змінюються після кожного об'єкта навчання. Для великих масивів даних стохастичний спуск градієнта може дати значну перевагу в швидкості в порівнянні зі стандартним градієнтним спуском.
Між цими двома видами градієнтного спуску існує компроміс, який іноді називають «mini-batch». У цьому випадку градієнт апроксимується сумою для невеликої кількості навчальних зразків.
1.1 Передумови
Статистичні оцінки та машинне навчання розглядають завдання мінімізації функції, яка має вигляд:
де параметр, що зводить до мінімуму, має бути оцінений. Кожне доданок зазвичай асоціюється з i-ым спостереженням у наборі даних (використовується навчання).
У класичній статистиці проблема мінімізації сум виникає в методі найменших квадратів, а також у методі максимальної правдоподібності (для незалежних спостережень). Загальний клас оцінок, що є результатом мінімізації сум, називається M-оцінкою. Однак у статистиці вже давно визнано, що вимога навіть локальної мінімізації надто обмежена для деяких завдань оцінки максимальної правдоподібності. Таким чином, сучасні статистичні теоретики часто розглядають стаціонарні точки на функції правдоподібності (нуль похідної, функція оцінки та інші оціночні рівняння).
Проблема мінімізації сум виникає також у мінімізації емпіричного ризику. У цьому випадку це значення функції втрат при i-омнаборі, і емпіричний ризик.
При мінімізації функції стандартний (або «batch») градієнтний спуск виконуватиме наступні ітерації:
де це розмір кроку (іноді званий швидкістю навчання у машинному навчанні).
У багатьох випадках функція доданку має просту модель, що включає нескладні обчислення функції суми та суми градієнтів. Наприклад, у статистиці, експоненційні сімейства з одним параметром допускають економічні обчислення функції та градієнтів.
Проте, в інших випадках, оцінки сумарного градієнта можуть вимагати дорогу оцінку градієнтів від усіх функцій доданків. Коли навчальний набір величезний і не існує простих формулоцінка суми градієнтів стає дуже дорогою, тому що оцінка градієнта вимагає оцінки всіх градієнтів функцій доданком. Для того, щоб заощадити на вартості обчислень на кожній ітерації, у стохастичному спуску градієнта вибіркою є підмножина функцій доданків на кожному кроці. Це дуже ефективно у разі великомасштабних завдань машинного навчання.
1.2 Ітераційний метод
У стохастичному градієнтному узвозі справжній градієнт приблизно виражається градієнтом на даному прикладі:
Оскільки алгоритм мчить через навчальний набір, він виконує вищеописані оновлення кожному за навчальним прикладом. Декілька проходів можуть бути зроблені по навчальній множині, поки алгоритм не сходиться. Дані можуть бути перемішані для кожного проходу, щоб запобігти циклам. Типові реалізації можуть використовувати адаптивну швидкість навчання те щоб алгоритм сходився.
У псевдокод стохастичний градієнтний спуск може бути представлений наступним чином:
1) Вибрати вихідний вектор параметра та швидкість навчання.
2) Повторювати доти, доки не буде приблизно отримано мінімальне:
2.1) Випадково перетасувати приклади у навчальному наборі.
2.2) Для i = 1,2, ..., n, робити:
Схожість стохастичного градієнтного спуску була проаналізована за допомогою теорії опуклої мінімізації та стохастичної апроксимації. Коли швидкість навчання зменшується з потрібною швидкістю, і за відносно слабких припущенні, стохастичний градієнтний спуск сходиться до глобального мінімуму, коли функція є опуклою чи псевдовыпуклой, інакше сходиться до локального мінімуму.
1.3 Варіанти реалізації
Безліч покращень було запропоновано та використано порівняно з основним методом стохастичного градієнтного спуску. Зокрема, у машинному навчанні необхідність встановлення швидкості навчання (розмір кроку) було визнано проблематичним.
Якщо задати цей параметр занадто великим, це може призвести до того, що алгоритм розходитися. Якщо навпаки, то алгоритм сходитиметься повільно.
Концептуально просте розширення стохастичного градієнтного узвозу зробити швидкість навчання як спадної функції, залежить від кількості ітерацій m.
Проробивши дану операцію, видно, що перші ітерації викликають великі зміни в параметрах, в той час як пізніші роблять більш тонке налаштування.
У рамках цієї роботи будуть розглянуті такі варіанти реалізації стохастичного градієнтного спуску:
1. 4 Momentum
Momentum, так само відомий як метод імпульсу, з'явився завдяки американському психологу Девіду Рамелхарту, а також на основі робіт Джеффрі Хінтонаї Роналда J Уїльям сапрививченні методу зворотного поширення. Стохастичний спуск градієнта з імпульсом запам'ятовує оновлення на кожній ітерації, і визначає наступне оновлення у вигляді лінійної комбінації градієнта і попереднього оновлення:
Що приводить до:
де параметр, який зводить до мінімуму, повинен бути оцінений і розмір кроку (іноді званий швидкістю навчання в машинному навчанні).
Назва імпульсу відбувається за аналогією з імпульсом у фізиці: вектор ваги. Думка про те, що переміщення матеріальної точки через простір параметрів, спричиняє прискорення завдяки силі, якою виступає градієнт втрат.
На відміну від класичного методу стохастичного спуску градієнта, він прагне тримати рух в одному напрямку, запобігаючи коливанням. Momentum був успішно застосований протягом кількох десятиліть.
1.5 AdaGrad
AdaGrad являє собою модифікований стохастичний градієнтний спуск з попереднім параметромшвидкість навчання. Вперше опубліковано в 2011 році. Неформально, він збільшує швидкість навчання для більш розріджених параметрів і зменшує швидкість навчання менш розріджений з них. Ця стратегія часто підвищує ймовірність збіжності порівняно з стандартним алгоритмомстохастичного градієнтного спуску в тих місцях, де дані нечисленні та рідкісні параметри є більш інформативними.
Приклади таких застосувань включають обробку природної мови та розпізнавання образів.
Він, як і раніше, має базу швидкості навчання, але множиться на елементи вектора, який є діагоналлю тензорного твору матриці.
де градієнт при ітерації m.
Діагональ задається у вигляді:
Вектор оновлюється після кожної ітерації. Формула для оновлення тепер виглядає так:
або записується у вигляді оновлення попереднього параметра,
Кожен підвищує масштабованість коефіцієнта швидкості навчання, який застосовується до одного параметру.
Оскільки знаменник є евклідовою нормою попередніх похідних, граничні значення параметрів оновлення стримують, у той час як параметри, які мали невеликі оновлення отримують більш високий рівень навчання.
В той час, як велася робота над проблемами опуклої оптимізації, AdaGrad був успішно використаний до завдань опуклої оптимізації.
1.6 RMSProp
RMSProp також є способом, у якому швидкість навчання адаптована для кожного параметра. Ідея полягає в тому, щоб розділити швидкість навчання для певної ваги на ковзну середню величин останніх градієнтів для цієї ваги. Таким чином, перша ковзна середня розраховується у вигляді квадрата:
де це параметр експонентного зважування, або параметр «забуття» («forgetting factor»)
Параметри оновлюються за допомогою формули:
RMSProp показав відмінну адаптацію швидкості навчання у різних додатках. RMSProp можна розглядати як узагальнення Rprop і він здатний працювати з таким варіантом градієнтного спуску як mini-batch, який протиставлений звичайному градієнтному спуску.
2. Реалізація стохастичного градієнтного спуску
на даному етапібудуть виконані реалізації декількох варіантів градієнтного стохастичного у вигляді програмного кодумовою програмування Python.
2.1 Реалізація стандартного стохастичного градієнтного спуску
По-перше, потрібний набір даних. У цьому випадку створюється набір даних за допомогою бібліотеки Scikit-Learn:
градієнт стохастичний алгоритм навчання
від sklearn.datasets import make_moons
від sklearn.cross_validation import train_test_split
X, y = make_moons(n_samples=5000, random_state=42, noise=0.1)
X_train, X_test, y_train, y_test = train_test_split (X, y, random_state = 42)
Ось що ми отримали:
Малюнок 1 - Графічне уявленнянабору даних
Далі визначається модель нейронної мережі. Це буде три шари мережі (один прихований шар):
import numpy as np
def make_network(n_hidden=100):
model = dict(W1=np.random.randn(n_feature, n_hidden),
W2=np.random.randn(n_hidden, n_class)
Також визначається дві операції: пряме поширення та зворотне поширення. Спочатку зробимо перший варіант:
return np.exp(x) / np.exp(x).sum()
def forward(x, model):
h = x @ model["W1"]
prob = softmax(h @ model["W2"])
Схема повинна зробити ряд точок від входу до прихованого шару та потім до вихідного шару. У прихованому шарі також може застосовуватися нелінійність, так щоб нейронна мережа могла передбачити нелінійну межу рішення. Яскравим представником нелінійної функції сьогодні є ReLU.
ReLU визначається як f(x)=max(0,x), але замість того, щоб робити np.max(0, x), є спритний трюк реалізації: x = 0.
Після того, як було досягнуто вихідний шар, вихідні дані повинні бути такими, щоб розподіл ймовірностей Бернуллі був точним, тому вихідні дані розтискаються за допомогою функції SoftMax, щоб отримати заданий розподіл.
Наразі визначається друга операція. Зворотне поширення має такий вигляд:
def backward(model, xs, hs, errs):
dW2 = hs.T@errs
dh = errs @ model["W2"].T
dh = 0
return dict(W1=dW1, W2=dW2)
Створюється основа алгоритму. Виконується реалізація функції sgd. Виглядає вона так:
def sgd(model, X_train, y_train, batch_size):
for iter in range(n_iter):
print("Iteration()".format(iter))
X_train, y_train = shuffle (X_train, y_train)
for i in range(0, X_train.shape, batch_size):
X_train_mini = X_train
y_train_mini = y_train
model = sgd_step(model, X_train_mini, y_train_mini)
return model
Виконується реалізація функції sgd_step. Виглядає вона так:
def sgd_step(model, X_train, y_train):
grad = get_batch_grad(model, X_train, y_train)
model = model.copy()
for layer in grad:
model += learning_rate * grad
Виконується функція get_batch_grad. Виглядає вона так:
def get_batch_grad(model, X_train, y_train):
xs, hs, errs = , ,
для x, cls_idx в zip(X_train, y_train):
h, y_pred = forward(x, model)
y_true = np.zeros(n_class)
y_true = 1.
err = y_true - y_pred
errs.append(err)
return backward(model, np.array(xs), np.array(hs), np.array(errs))
У цій функції перебирається кожна точка даних у batch, потім відправляється в мережу і порівнюється результат істинної мітки стій, що була отримана навчальними даними. Помилка визначається різницею ймовірності істинної мітки та ймовірності нашого прогнозу.
2.2 Реалізація Momentum
Momentum працює за принципом фізичного закону руху, він проходить через локальні оптимуми (невеликі пагорби). Додавання імпульсу буде призводити до того, що збіжність алгоритму відбуватиметься швидше, оскільки відбувається накопичення швидкості та крок методу може бути більшим, ніж постійний крок у звичайному методі.
Враховуючи, що заготовок програми вже готовий, потрібно реалізувати лише основну функцію цього методу. Функція momentum наведена нижче:
def momentum(model, X_train, y_train, batch_size):
velocity = (k: np.zeros_like(v) for k, v in model.items())
gamma =.9
X_mini, y_mini = batches
for layer in grad:
velocity = gamma * velocity + alpha * grad
model += velocity
Включається нова змінна velocity, яка накопичуватиме імпульс для кожного параметра. Оновлення змінної відбуватиметься доданком alpha*grad на кожному новому кроці градієнтного спуску. Також відбувається невелике зменшення за допомогою коефіцієнта gamma значення змінної velocity, яка була обчислена на попередньому кроці.
2.3 Реалізація AdaGrad
До цього часу була ігнорована швидкість навчання alpha, оскільки вона була постійною. Проблема виникає в тому, що швидкість навчання впливає на всі параметри і не завжди за постійної швидкості навчання алгоритм працює ефективно. Вирішенням цієї проблеми може бути AdaGrad.
У разі використання AdaGrad оновлення параметрів відбувається точково, тому швидкість навчання є адаптивним параметром.
Виконується реалізація цього методу. Вся програма готова, потрібно лише змінити основну функцію. Називатися вона буде adagrad. Функція представлена нижче:
def adagrad(model, X_train, y_train, batch_size):
batches = get_batch(X_train, y_train, batch_size)
for iter in range(1, n_iter + 1):
idx = np.random.randint(0, len(batches))
X_mini, y_mini = batches
grad = get_batch_grad(model, X_mini, y_mini)
cache[k] += grad[k]**2
return model
Можна помітити, що відбувається нормалізація швидкості навчання. Вона тепер може бути більшою або меншою залежно від того, як поводяться останні градієнти.
2.4 Реалізація RMSProp
Можна помітити, що в накопичувальній частині Adagrad значення cache[k] += grad[k]**2 монотонно зростає внаслідок суми і квадрата. Це може бути проблематичним, оскільки швидкість навчання монотонно зменшуватиметься до дуже крихітної швидкості навчання.
Для боротьби з цією проблемою, RMSProp розкладає минуле накопичене значення градієнта, щоб розглядалася лише частина останніх градієнтів. Тепер, замість того, щоб розглядати всі останні градієнти, RMSProp поводиться як ковзна середня.
Виконується реалізація цього методу. Вся програма готова, потрібно лише змінити основну функцію. Називатися вона будеrmsprop. Функція представлена нижче:
def rmsprop(model, X_train, y_train, batch_size):
cache = (k: np.zeros_like(v) for k, v in model.items())
gamma =.9
batches = get_batch(X_train, y_train, batch_size)
for iter in range(1, n_iter + 1):
idx = np.random.randint(0, len(batches))
X_mini, y_mini = batches
grad = get_batch_grad(model, X_mini, y_mini)
cache[k] = gamma * cache[k] + (1 - gamma) * (grad[k]**2)
model [k] + = alpha * grad [k] / (np.sqrt (cache [k]) + eps)
Основна відмінність у обчисленні значення cache [k] і тепер накопичене значення градієнта не агресивно монотонно зростатиме.
3. Тестування та порівняння
У цьому розділі проводитиметься тестування реалізації та аналіз отриманих результатів.
3.1 Тестування стандартного стохастичного градієнтного спуску
На даному етапі проводитиметься тестування стандартного градієнтного стохастичного спуску. Процедура буде виконуватися 100 разів, а потім буде обчислено середнє значення точності.
n_experiment = 100
accs = np.zeros(n_experiment)
for k in range(n_experiment):
model = make_network()
model = sgd(model, X_train, y_train, minibatch_size)
prob = forward(x, model)
y = np.argmax(prob)
Виконавши даний код, я отримав такі значення:
Середня точність: 0.8765040000000001
Таким чином, можна дійти невтішного висновку, що у середньому точність виконання 87%.
3.2 Тестування Momentum
На даному етапі проводитиметься тестування стохастичного градієнтного спуску на основі реалізації Momentum. Процедура буде виконуватися 100 разів, а потім буде обчислено середнє значення точності.
Програму для тестування наведено нижче:
n_experiment = 100
accs = np.zeros(n_experiment)
for k in range(n_experiment):
model = make_network()
model = momentum(model, X_train, y_train, minibatch_size)
y_pred = np.zeros_like(y_test)
for i, x in enumerate(X_test):
prob = forward(x, model)
y = np.argmax(prob)
accs[k] = (y_pred == y_test).sum() / y_test.size
print("Середня точність: (), Отримане значення: ()".format(accs.mean(), accs.std()))
Середня точність:
1) 0.3152 при alpha = 0.5
2) 0.85546666666666666, при alpha = 1e-2
3) 0.86133333333333334, при alpha = 1e-5
Отже, можна дійти невтішного висновку, що з нижчих значеннях швидкості навчання точність виконання помітно вище.
3.3 Тестування AdaGrad
На даному етапі проводитиметься тестування стохастичного градієнтного спуску на основі реалізації AdaGrad. Процедура буде виконуватися 100 разів, а потім буде обчислено середнє значення точності.
Програму для тестування наведено нижче:
n_experiment = 100
accs = np.zeros(n_experiment)
for k in range(n_experiment):
model = make_network()
model = adagrad(model, X_train, y_train, minibatch_size)
y_pred = np.zeros_like(y_test)
for i, x in enumerate(X_test):
prob = forward(x, model)
y = np.argmax(prob)
accs[k] = (y_pred == y_test).sum() / y_test.size
print("Середня точність: (), Отримане значення: ()".format(accs.mean(), accs.std()))
Виконавши цей код, отримано такі значення:
Середня точність:
1) 0.87546666666666667, при alpha = 0.5
2) 0.87866666666666667, при alpha = 1e-2
3) 0.504 при alpha = 1e-5
Отже, можна дійти невтішного висновку, що з дуже низьких значеннях швидкості навчання точність виконання сильно зменшується.
3.4 Тестування RMSProp
На даному етапі проводитиметься тестування стохастичного градієнтного спуску на основі реалізації RMSProp. Процедура буде виконуватися 100 разів, а потім буде обчислено середнє значення точності.
Програму для тестування наведено нижче:
n_experiment = 100
accs = np.zeros(n_experiment)
for k in range(n_experiment):
model = make_network()
model = rmsprop(model, X_train, y_train, minibatch_size)
y_pred = np.zeros_like(y_test)
for i, x in enumerate(X_test):
prob = forward(x, model)
y = np.argmax(prob)
accs[k] = (y_pred == y_test).sum() / y_test.size
print("Середня точність: (), Отримане значення: ()".format(accs.mean(), accs.std()))
Виконавши цей код, отримано такі значення:
Середня точність:
1) 0.85066666666666667, при alpha = 0.5
2) 0.87279999999999999, при alpha = 1e-2
3) 0.306933333333333334, при alpha = 1e-5
Таким чином, можна зробити висновок, що при дуже низьких значеннях швидкості навчання точність виконання аналогічно AdaGrad сильно зменшується.
Висновок
З порівняльного аналізузрозуміло, що при використанні великого значення швидкості навчання, методи з адаптивною швидкістю навчання виграють у методів постійною швидкістюнавчання.
Однак, при використанні невеликого значення швидкості навчання відбувається зворотне, наприклад, 1e-5. Для стандартного варіантустохастичного градієнтного спуску та методу імпульсу досить малі значення дозволяють їм добре працювати. З іншого боку, якщо швидкість навчання дуже мала, і відбувається її нормалізація в адаптивні методишвидкості навчання, вона стає ще менше, що впливає швидкість збіжності. Це робить навчання дуже повільним, і ці методи працюють гірше, ніж стандартний стохастичний градієнтний спуск з тим самим числом ітерацій.
Список використаних джерел
1. Machinelearning – Стохастичний градієнтний спуск
2. Штучний інтелектукраїнською - Градієнтні спуски
3. Вікі підручник - Реалізація алгоритмів / Градієнтний спуск
4. Stanford University - Adaptive Subgradient Methods
5. Cambridge University Press - Online Algorithms and Stochastic Approximations
6. Sanjoy Dasgupta і David Mcallester - На важливість ініціативи і часу в deep learning[Електронний ресурс].
Розміщено на Allbest.ru
...Подібні документи
Необхідні умови екстремуму. Розробка машинного алгоритмута програми багатовимірної оптимізації для градієнтного методу з використанням методу рівномірного пошуку Перевіряє необхідні та достатні умови екстремуму для знайденої точки мінімуму.
курсова робота , доданий 25.09.2013
Програмна реалізаціядодатки для обчислення заданих функцій. Процедура пошуку мінімуму функції. Застосування методів Хука-Джівса та градієнтного спуску для вирішення задачі. Дослідження функції на околиці базисної точки, визначення її координат.
контрольна робота , доданий 02.02.2014
Оптимізація розв'язання задачі за допомогою алгоритму відпалу. Аналіз теорії оптимізації як цільової функції. Метод градієнтного спуску. Змінні та опис алгоритму відпалу. Подання завдання комівояжера через граф. Зведення завдання до змінних та розв'язання.
курсова робота , доданий 21.05.2015
Навчання найпростішої та багатошарової штучної нейронної мережі. Метод навчання перцептрону за принципом градієнтного спуску поверхнею помилки. Реалізація у програмному продукті NeuroPro 0.25. Використання алгоритму зворотного розповсюдження помилки.
курсова робота , доданий 05.05.2015
Розв'язання задачі на тему максимізації функцій багатьох змінних. Опис методу дихотомії, його застосування на вирішення нелінійних рівнянь. Розв'язання цієї задачі з використанням методу покоординатного спуску. Складання алгоритмів, лістинг програми.
курсова робота , доданий 01.10.2009
Ідентифікація об'єктів шляхом найменших квадратів. Аналіз коефіцієнтів парної, приватної та множинної кореляції. Побудова лінійної моделі та моделі з розподіленими параметрами. Ітераційний чисельний метод знаходження кореня (нуля) заданої функції.
курсова робота , доданий 20.03.2014
Основа технології використання програмного комплексу LabVIEW, переваги системи. Програмування, що базується на архітектурі потоків даних. Методи знаходження екстремуму. Використання методу Гауса-Зейделя для пошуку максимуму двовимірної функції.
контрольна робота , доданий 18.03.2011
Призначення та класифікація методів пошукової оптимізації. Ефективність пошукового методу. Методи пошуку нульового порядку: вихідні дані, умови, недоліки та застосування. Структура градієнтного пошуку. Основна ідея методу якнайшвидшого спуску.
лекція, доданий 04.03.2009
Постановка задачі та її формалізація. Пошук значень інтерполяційного багаточлена у точках x1 та x2. Пошук мінімуму функції F(x) на відрізку . Перевіряє умови збіжності методів. Тестування програмних модулів. Деталізована схема алгоритму.
курсова робота , доданий 04.02.2011
Численні методи у завданнях без обмежень. Схема способів спуску. Середовище редактора Visual Basic. Використання об'єктів ActiveX у формах. Блок-схема алгоритму моделювання. Завдання оптимізування детерменованих функцій із єдиною точкою екстремуму.
Отже, у вас є завдання передбачити якесь значення на кшталт вартості будинку за його розміром. Або час обробки якогось запиту вашою системою. Та мало що.
Ви вирішили скористатися лінійною регресією і тепер хочете знайти коефіцієнти, при яких різниця між ціною, яку передбачає ваша модель, і реальною вартістю проданих будинків буде мінімальною. Для цього ви можете використовувати один із таких методів:
- 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 у загальному вигляді не сходиться до мінімуму, але є його модифікації, які дозволяють досягти збіжності.
