Gradient zejście - Gradient descent


Z Wikipedii, wolnej encyklopedii

Gradient zejście jest pierwszego rzędu iteracyjny optymalizacji algorytm do znalezienia minimum funkcji. W celu znalezienia minimum lokalne z funkcji z użyciem metoda gradientu prostego, bierze się etapy proporcjonalny do negatywnej z gradientem (lub w przybliżeniu gradient) funkcji w bieżącym momencie. Jeśli natomiast ktoś podejmuje działania proporcjonalne do dodatni gradientów, jeden zbliża się do lokalnego maksimum tej funkcji; Następnie procedura znana jako wejście gradientu .

Gradient zejście jest również znany jako największego spadku . Jednak metoda gradientu prostego nie powinien być mylony z metoda najszybszego spadku do zbliżenia całki.

Opis

Ilustracja opadania gradientu na serii zestawów szczebla .

Gradient zejście opiera się na obserwacji, że jeśli funkcja multi-zmienna jest określona i różniczkowalna w pewnym otoczeniu punktu , a następnie maleje najszybciej jeśli ktoś idzie od w kierunku ujemnym nachyleniem w , . Wynika stąd, że jeśli

na tyle mała, wtedy . Innymi słowy, termin jest odejmowany od , ponieważ chcemy, aby przejść przed gradient w kierunku minimum. Z tej obserwacji na uwadze, jeden zaczyna się domyślać do lokalnego minimum i uważa sekwencję taką, że

Mamy monotoniczny ciąg

więc mieć nadzieję, że sekwencja jest zbieżny do pożądanego miejscowego minimum. Zauważ, że wartość wielkości kroku może się zmienić w każdej iteracji. Przy pewnych założeniach w funkcji (na przykład wypukłymi i Lipschitz ) i poszczególnych wyborów (na przykład, wybranych albo przez poszukiwanie linii , które spełniałyby warunki Wolfe i metody Barzilai-Borwein pokazany jako następne)

Zbieżność do miejscowego minimum, może być zagwarantowana. Gdy funkcja jest wypukła , wszystkie lokalne minima są również globalne minima, więc w tym przypadku metoda gradientu prostego może zbiegać się do globalnego rozwiązania.

Proces ten jest zilustrowany na sąsiednim zdjęciu. Tutaj zakłada się być definiowane na płaszczyźnie, a jej wykres ma miska kształt. Niebieskie krzywe są linie konturu , to znaczy obszary, w której wartość jest stała. Czerwony strzałkę A, inicjującego w punkcie pokazują kierunek ujemny gradient w tym punkcie. Zauważ, że (ujemna) gradientu w punkcie jest prostopadły do linii konturu przeżywa tego punktu. Widzimy, że nachylenie zejście prowadzi nas do dna miski, czyli do momentu, w którym wartość funkcji jest minimalne.

Przykłady

Gradient zejście ma problemy z patologicznych funkcji, takich jak funkcja rosenbrocka pokazanego tutaj.

Funkcja Rosenbrocka ma wąski zakrzywiony doliny, który zawiera minimalną. Dno doliny jest bardzo płaska. Ze względu na zakrzywione płaską dolinę optymalizacja jest zygzakiem powoli małych rozmiarach krok w kierunku minimum.

Banana-SteepDesc.gif

Natura tej metody „zygzakiem” jest również widoczne poniżej, gdzie gradient metoda jest stosowana do zejścia .

Gradient algorytm zejście w działaniu.  (1: konturu)Gradient algorytm zejście w działaniu.  (2: Powierzchnia)

ograniczenia

Dla niektórych z powyższych przykładów, metoda gradientu prostego jest stosunkowo powolny blisko do minimum: technicznie, jego asymptotyczne tempo konwergencji jest gorsza od wielu innych metod. W przypadku źle uwarunkowanych problemów wypukłe metoda gradientu prostego bardziej „zygzaki” jako gradienty wskazują prawie prostopadle do kierunku najkrótszym do punktu minimum. Aby uzyskać więcej informacji, patrz § Komentarze poniżej.

Dla funkcji nie różniczkowalnymi metody gradientu są odpowiednio określone. Lokalnie Lipschitz problemów i szczególnie dla problemów minimalizacji wypukłych, wiązka metody pochodzenia są dobrze zdefiniowane. Metody dla zanurzania, jak subgradient metody projekcji może być również wykorzystane. Sposoby te są zwykle wolniejsze niż metoda gradientu prostego. Inną alternatywą dla funkcji nie różniczkowalnymi jest „gładka” funkcję lub funkcje związane gładką funkcji. W tym podejściu, gładka problem jest rozwiązany w nadziei, że odpowiedź jest zbliżona do odpowiedzi na nie-gładkich problemu (od czasu do czasu, to może być wykonane rygorystyczny).

Rozwiązanie układu liniowego

Gradient zejście może być wykorzystywana do rozwiązania układu równań liniowych, sformułowane jako kwadratowego problemu minimalizacji, np stosując liniową metodę najmniejszych kwadratów . Roztwór

w sensie metodą najmniejszych kwadratów jest zdefiniowana jako minimalizacji funkcji

W tradycyjnych liniowych najmniejszych kwadratów dla prawdziwych i na euklidesowej normą jest używany, w którym to przypadku

W tym przypadku, szukaj linii minimalizacja znalezienie lokalnie optymalną wielkość skoku na każdej iteracji, można przeprowadzić analitycznie i wyraźne wzory na lokalnie optymalny są znane.

Do rozwiązywania równań liniowych, algorytm ten jest rzadko używany, przy czym metoda sprzężoną Gradient jest jednym z najbardziej popularnych alternatyw. Szybkość zbieżności metoda gradientu prostego zależy od stosunku maksimum do minimum wartości własnych o , podczas gdy szybkość zbieżności sprzężonych nachylenia jest bardziej złożona zależność wartości własnych, można korzystać ze wstępnego kondycjonowania . Gradient zejście korzysta również z przygotowaniem wstępnym, ale to nie jest zrobione, jak zwykle.

Rozwiązanie systemu nieliniowej

Gradient zejście może być również wykorzystywana do rozwiązania układ równań nieliniowych . Poniżej jest przykład, który pokazuje, jak używać metoda gradientu prostego rozwiązania dla trzech nieznanych zmiennych x 1 , x 2 i x 3 . Przykład ten pokazuje, jednej iteracji metoda gradientu prostego.

Rozważmy układ równań nieliniowych

Pozwól nam wprowadzić funkcję związaną

gdzie

Jeden może teraz zdefiniować funkcję celu

które będziemy starali się zminimalizować. Jako wstępnego odgadnięcia, użyjmy

Wiemy to

gdzie

Jakobian matryca jest przez

Oceny i w wydajności

A zatem

i

Animacja pokazujący pierwsze 83 iteracji metoda gradientu prostego stosowane do tego przykładu. Powierzchnie są isosurfaces od w bieżącym odgadnięcia , a strzałki pokazują kierunek opadania. Ze względu na niewielką i stałą wielkością kroku, zbieżność jest powolny.

Teraz, odpowiednia należy znaleźć takie, że . Można to zrobić z dowolnej z różnych wyszukiwarek linia algorytmów. Można też po prostu odgadnąć , co daje

Oceny funkcji celu w tej wartości plonów

Spadek od wartości Następnym krokiem jest o to spory spadek w funkcji celu. Kolejne etapy to obniża jego wartość dalej, aż do osiągnięcia w przybliżeniu rozwiązanie układu stwierdzono.

Komentarze

Gradient zejście działa w pomieszczeniach o dowolnej liczbie wymiarów, nawet w tych nieskończonych-wymiarowej. W tym ostatnim przypadku, przestrzeń poszukiwań jest zwykle funkcji miejsca i oblicza się pochodną Fréchet z funkcjonalną być zminimalizowana w celu określenia kierunku opadania.

Zejście Gradient może przybierać wiele iteracji do obliczania lokalnego minimum z wymaganą dokładnością , jeśli krzywizna w różnych kierunkach jest bardzo różna dla danej funkcji. W odniesieniu do takich funkcji, kondycjonowania wstępnego , który zmienia geometrię powierzchni kształtować zestawów poziom funkcji jak koncentrycznych okręgów , leczy powolne zbieżności. Konstruowania i stosowania Wstępne mogą być kosztowne obliczeniowo, jednak.

Zejście gradientu można łączyć ze poszukiwaniu linii , znalezienie lokalnie optymalny rozmiar krok na każdej iteracji. Przeprowadzanie wyszukiwania linia może być czasochłonne. Z drugiej strony, przy użyciu stałego Małe mogą dawać słabą zbieżność.

Sposoby oparte na metodzie Newtona i inwersji juty stosując skoniugowane gradientu techniki mogą być lepsze alternatywy. Na ogół, takie metody są zbieżne w mniejszej liczbie iteracji, ale koszt z każdej iteracji jest wyższa. Przykładem jest metoda BFGS która polega na obliczaniu na każdym kroku matrycę o której wektor gradientu mnoży się iść w kierunku, „lepszy”, w połączeniu z bardziej wyrafinowanym wyszukiwania linia algorytm, aby znaleźć „najlepszego” wartość Dla ekstremalnie duże problemy, gdzie problemy z pamięcią komputera dominują, metoda ograniczoną pamięć, takich jak L-BFGS powinien być stosowany zamiast BFGS lub stromego zejścia.

Gradient zejście może być postrzegana jako stosując metodę Eulera do rozwiązywania równań różniczkowych zwyczajnych do przepływu gradientu .

Przykłady obliczeniowe

Pyton

Algorytm metoda gradientu prostego jest stosowany, aby znaleźć lokalne minimum funkcji , z pochodnej . Oto implementacja w języku programowania Python .

# From calculation, it is expected that the local minimum occurs at x=9/4

cur_x = 6 # The algorithm starts at x=6
gamma = 0.01 # step size multiplier
precision = 0.00001
previous_step_size = 1 
max_iters = 10000 # maximum number of iterations
iters = 0 #iteration counter

df = lambda x: 4 * x**3 - 9 * x**2

while previous_step_size > precision and iters < max_iters:
    prev_x = cur_x
    cur_x -= gamma * df(prev_x)
    previous_step_size = abs(cur_x - prev_x)
    iters+=1

print("The local minimum occurs at", cur_x)
#The output for the above will be: ('The local minimum occurs at', 2.2499646074278457)

Scala

Oto implementacja w języku programowania Scala

import math._ 

val curX = 6
val gamma = 0.01 
val precision = 0.00001 
val previousStepSize = 1 / precision

def df(x: Double): Double = 4 * pow(x, 3) - 9 * pow(x, 2)

def gradientDescent(precision: Double, previousStepSize: Double, curX: Double): Double = {
	if (previousStepSize > precision) {
		 val newX = curX + -gamma * df(curX)	
		 println(curX)
		 gradientDescent(precision, abs(newX - curX), newX)
	} else curX	 
}

val ans = gradientDescent(precision, previousStepSize, curX)
println(s"The local minimum occurs at $ans")

Jawa

Sama realizacja, aby uruchomić w Javie z JShell (Java 9 minimalna):jshell <scriptfile>

import java.util.function.Function;
import static java.lang.Math.*;
import static java.lang.System.out;

double gamma = 0.01;
double precision = 0.00001;

Function<Double,Double> df = x ->  4 * pow(x, 3) - 9 * pow(x, 2);
	
double gradientDescent(Function<Double,Double> f) {

	double curX = 6.0;
	double previousStepSize = 1.0;

	while (previousStepSize > precision) {
	    double prevX = curX;
	    curX -= gamma * f.apply(prevX);
	    previousStepSize = abs(curX - prevX);
	}
	return curX;
}
	
double res = gradientDescent(df);
out.printf("The local minimum occurs at %f", res);

Julia

Oto sam algorytm zaimplementowany w języku programowania Julia .

cur_x = 6;
gamma = 0.01;
precision = 0.00001;
previous_step_size = 1;

df = (x) -> 4x^3 - 9x^2;

while previous_step_size > precision
    prev_x = cur_x;
    cur_x -= gamma * df(prev_x);
    previous_step_size = abs(cur_x - prev_x);
end

println("The local minimum occurs at $cur_x");

do

Oto sam algorytm zaimplementowany w języku programowania C .

#include <stdio.h>
#include <stdlib.h>

double dfx(double x) {
    return 4*(x*x*x) - 9*(x*x);
}

double abs_val(double x) {
    return x > 0 ? x : -x;
}

double gradient_descent(double dx, double error, double gamma, unsigned int max_iters) {
    double c_error = error + 1;
    unsigned int iters = 0;
    double p_error;
    while(error < c_error && iters < max_iters) {
        p_error = dx;
        dx -= dfx(p_error) * gamma;
	    c_error = abs_val(p_error-dx);
        printf("\nc_error %f\n", c_error);
        iters++;
    }
    return dx;
}

int main() {
    double dx = 6;
    double error = 1e-6;
    double gamma = 0.01;
    unsigned int max_iters = 10000;
    printf("The local minimum is: %f\n", gradient_descent(dx, error, gamma, max_iters));
    return 0;
}

Powyższy fragment kodu ma być modyfikowany w odniesieniu do zwiększenia wielkości zgodnie z systemem w dłoni i zbieżności może być wykonany szybciej, za pomocą adaptacyjnego rozmiar kroku. W powyższym przypadku wielkość kroku nie jest adaptacyjne. To pozostaje w 0,01 we wszystkich kierunkach, co może czasami powodować metoda na niepowodzenie przez odbiegających od minimum.

JavaScript (ES6)

Oto przykład z gradientem zniżania przed randomizacją wartości, squareMeter i cenie, napisany w JavaScript , używając ECMAScript 6 możliwości:

// adjust training set size

const M = 10;

// generate random training set

const DATA = [];

const getRandomIntFromInterval = (min, max) =>
  Math.floor(Math.random() * (max - min + 1) + min);

const createRandomPortlandHouse = () => ({
  squareMeter: getRandomIntFromInterval(0, 100),
  price: getRandomIntFromInterval(0, 100),
});

for (let i = 0; i < M; i++) {
  DATA.push(createRandomPortlandHouse());
}

const _x = DATA.map(date => date.squareMeter);
const _y = DATA.map(date => date.price);

// linear regression and gradient descent

const LEARNING_RATE = 0.0003;

let thetaOne = 0;
let thetaZero = 0;

const hypothesis = x => thetaZero + thetaOne * x;

const learn = (x, y, alpha) => {
  let thetaZeroSum = 0;
  let thetaOneSum = 0;

  for (let i = 0; i < M; i++) {
    thetaZeroSum += hypothesis(x[i]) - y[i];
    thetaOneSum += (hypothesis(x[i]) - y[i]) * x[i];
  }

  thetaZero = thetaZero - (alpha / M) * thetaZeroSum;
  thetaOne = thetaOne - (alpha / M) * thetaOneSum;
}

const MAX_ITER = 1500;
for (let i = 0; i < MAX_ITER; i++) {
  learn(_x, _y, LEARNING_RATE);
  console.log('thetaZero ', thetaZero, 'thetaOne', thetaOne);
}

MATLAB

Poniższy MATLAB kod demonstruje konkretne rozwiązania dla rozwiązywania układu nieliniowego równań przedstawionych w poprzednim rozdziale :

% Multi-variate vector-valued function G(x)
G = @(x) [
    3*x(1) - cos(x(2)*x(3)) - 3/2           ;
    4*x(1)^2 - 625*x(2)^2 + 2*x(2) - 1      ;
    exp(-x(1)*x(2)) + 20*x(3) + (10*pi-3)/3];

% Jacobian of G
JG = @(x) [
    3,                     sin(x(2)*x(3))*x(3),   sin(x(2)*x(3))*x(2) ;
    8*x(1),                -1250*x(2)+2,          0                   ;
    -x(2)*exp(-x(1)*x(2)), -x(1)*exp(-x(1)*x(2)), 20                 ];

% Objective function F(x) to minimize in order to solve G(x)=0
F = @(x) 0.5 * sum(G(x).^2);

% Gradient of F (partial derivatives)
dF = @(x) JG(x).' * G(x);

% Parameters
GAMMA = 0.001;    % step size (learning rate)
MAX_ITER = 1000;  % maximum number of iterations
FUNC_TOL = 0.1;   % termination tolerance for F(x)

fvals = [];       % store F(x) values across iterations
progress = @(iter,x) fprintf('iter = %3d: x = %-32s, F(x) = %f\n', ...
    iter, mat2str(x,6), F(x));

% Iterate
iter = 1;         % iterations counter
x = [0; 0; 0];    % initial guess
fvals(iter) = F(x);
progress(iter, x);
while iter < MAX_ITER && fvals(end) > FUNC_TOL
    iter = iter + 1;
    x = x - GAMMA * dF(x);  % gradient descent
    fvals(iter) = F(x);     % evaluate objective function
    progress(iter, x);      % show progress
end

% Plot
plot(1:iter, fvals, 'LineWidth',2); grid on;
title('Objective Function'); xlabel('Iteration'); ylabel('F(x)');

% Evaluate final solution of system of equations G(x)=0
disp('G(x) = '); disp(G(x))

% Output:
%
% iter =   1: x = [0;0;0]                         , F(x) = 58.456136
% iter =   2: x = [0.0075;0.002;-0.20944]         , F(x) = 23.306394
% iter =   3: x = [0.015005;0.0015482;-0.335103]  , F(x) = 10.617030
% ...
% iter = 187: x = [0.683335;0.0388258;-0.52231]   , F(x) = 0.101161
% iter = 188: x = [0.684666;0.0389831;-0.522302]  , F(x) = 0.099372
%
% (converged in 188 iterations after exceeding termination tolerance for F(x))

R

Poniższa R języka programowania kod jest przykładem realizacji algorytmu metoda gradientu prostego znaleźć minimum funkcji w poprzedniej części. Należy pamiętać, że szukamy „s minimum rozwiązując jego pochodna jest równa zero.

I x mogą być aktualizowane z metodą gradientu schodzenia każdej iteracji w formie

gdzie k = 1, 2, ..., maksymalna iteracji i α jest wielkością kroku.

# set up a stepsize
alpha = 0.003

# set up a number of iteration
iter = 500

# define the objective function f(x) = x^4 - 3*x^3 + 2
objFun = function(x) return(x^4 - 3*x^3 + 2)

# define the gradient of f(x) = x^4 - 3*x^3 + 2
gradient = function(x) return((4*x^3) - (9*x^2))

# randomly initialize a value to x
set.seed(100)
x = floor(runif(1)*10)

# create a vector to contain all xs for all steps
x.All = vector("numeric",iter)

# gradient descent method to find the minimum
for(i in 1:iter){
        x = x - alpha*gradient(x)
        x.All[i] = x
        print(x)
}

# print result and plot all xs for every iteration
print(paste("The minimum of f(x) is ", objFun(x), " at position x = ", x, sep = ""))
plot(x.All, type = "l")

rozszerzenia

Gradient zejście może być przedłużony do obsługi ograniczeń poprzez włączenie projekcji na zestaw ograniczeń. Metoda ta jest możliwa tylko wtedy, gdy występ jest efektywnie obliczalna na komputerze. W odpowiednich założeń, metoda ta jest zbieżna. Metoda ta jest szczególnym przypadkiem algorytmu przód-tył dla inkluzji Monotonia (która obejmuje wypukłą programowanie i wariacyjnych nierówności ).

Szybkich metod gradientowych

Innym rozszerzeniem jest metoda gradientu prostego powodu Jurija Nesterov od 1983 roku, a następnie został uogólniony. Zapewnia on prostą modyfikację algorytmu, który umożliwia szybszą konwergencję dla wypukłych problemów. Dla nieograniczonym gładkich problemów metoda nazywana jest Szybka metoda Gradient (FGM) lub szybszej metody Gradient (AGM). W szczególności, jeżeli funkcja różniczkowalną jest wypukła i ma Lipschitz i nie zakłada się, że jest silnie wypukły , to błąd wartości obiektywnej generowanej w każdym etapie nachyleniem metodą opadania będzie ograniczony . Stosując technikę przyspieszania Nesterov, błąd zmniejsza się . Wiadomym jest, że tempo tego spadku w funkcji kosztu jest optymalna dla pierwszego rzędu metod optymalizacji. Niemniej jednak istnieje możliwość poprawy algorytmu poprzez ograniczenie stały czynnik. Zoptymalizowane metody gradientowe (OGM) redukuje się, że stały się o współczynnik dwa, a sposób optymalnego pierwszego rzędu problemów na dużą skalę.

Na ograniczonej lub niegładkich problemów FGM niestierowskim jest nazywany szybkim bliższy sposób gradientowy (FPGM) Przyspieszenie bliższego metodą gradientu .

Metoda pęd

Jeszcze innym rozszerzeniem, które zmniejsza ryzyko utknięcia w lokalnym minimum, jak również przyspiesza konwergencję znacznie w przypadkach, gdy proces będzie inaczej zygzakowata ciężko jest metoda pęd , który używa terminu pędu analogicznie do " masa newtonowskiej cząstek, które poruszają się lepkiego ośrodka, w polu siły konserwatywne”. Metoda ta jest często wykorzystywana jako rozszerzenie do wstecznej propagacji błędów algorytmów wykorzystywanych do szkolenia sztucznych sieci neuronowych .

Analogia dla zrozumienia pochodzenia gradientu

Mgła w górach

Podstawowa intuicja za opadania gradientu można zilustrować hipotetycznego scenariusza. Osoba tkwi w górach i stara się w dół (tj próbując znaleźć minima). Jest ciężka mgła taka, że ​​widoczność jest bardzo niska. Dlatego ścieżka w dół góry nie jest widoczny, więc musi korzystać z lokalnych informacji znaleźć minima. może on zastosować metodę metoda gradientu prostego, co wiąże się patrząc na nachylenie wzgórzu w jego aktualnej pozycji, a następnie postępując w kierunku z największego spadku (czyli w dół). Jeśli próbował znaleźć szczyt góry (czyli maxima), wtedy on postępować w kierunku stromego wznoszenia (czyli pod górę). Stosując tę ​​metodę, by w końcu znaleźć drogę w dół góry. Jednak zakładamy również, że nachylenie wzgórza nie jest oczywiste z prostej obserwacji, ale to wymaga wyrafinowanego przyrządu do pomiaru, którego osoba zdarza się mieć w tej chwili. To zajmuje trochę czasu, aby zmierzyć kąt nachylenia wzgórza z instrumentu, a więc powinien zminimalizować jego wykorzystania instrumentu, jeśli chciał zejść z góry przed zachodem słońca. wtedy trudność wybiera częstotliwość, przy której powinien mierzyć stromość wzgórzu więc nie zgaśnie utwór.

W tej analogii, osoba reprezentuje algorytmu, a ścieżka zdjęty góra reprezentuje sekwencję parametryzacji, że algorytm będzie badać. Kąt nachylenia wzniesienia oznacza nachylenie powierzchni błędu w tym punkcie. Przyrząd do pomiaru stromość jest różnicowanie (nachylenie powierzchni błędu może być obliczona na podstawie pochodnej funkcji błędu kwadratowego w tym punkcie). Kierunek zechce podróżować w jednej linii z gradientem powierzchni błędu w tym punkcie. Ilość czasu jedzie przed wykonaniem kolejnego pomiaru jest szybkość uczenia algorytmu. Zobacz wstecznej propagacji błędów § Ograniczenia omówienie ograniczeń tego typu algorytmu „wspinaczka wzgórze”.

Zobacz też

Referencje

źródła

Linki zewnętrzne