Gradientní sestup

algoritmus pro nalezení lokálního minima diferencovatelné funkce

Gradientní sestup (anglicky gradient descent) je iterativní optimalizační algoritmus prvního řádu pro nalezení lokálního minima diferencovatelné funkce. Myšlenkou metody je posouvat se z výchozího bodu po krocích vždy v opačném směru gradientu (nebo přibližného gradientu) funkce v daném bodě, protože to je směr nejstrmějšího klesání její hodnoty. Naopak krokování ve směru gradientu povede k lokálnímu maximu této funkce; postup je pak známý jako gradientní výstup.

Gradientní sestup a vrstevnice minimalizované funkce

Algoritmus se přičítá Cauchymu, který ho poprvé zmínil v roce 1847, ale jeho konvergenční vlastnosti pro nelineární optimalizační problémy byly poprvé studovány Haskellem Currym v roce 1944.

Gradientní sestup je spojitou analogií metody hill-climbing (gradientní algoritmus). Sám je základem dalších metod, zejména algoritmu zpětného šíření chyby používaného pro učení umělých neuronových sítí.

Gradientní sestup je založen na pozorování, že pokud je funkce více proměnných   definována a diferencovatelná v sousedství bodu  , pak   klesá nejrychleji, pokud se jde z   ve směru záporného gradientu   v   . Z toho vyplývá, že se v řadě iterací z   posuneme k nižší hodnotě funkce   v bodě   pokud

 

pro   dost malé, aby platilo  . Jinými slovy člen   odčítáme od  , protože se chceme pohybovat proti nejstrmějšímu nárůstu směrem k lokálnímu minimu. Vyjděme tedy z libovolného (náhodně nebo záměrně zvoleného) bodu  , v němž je   definovaná a diferencovatelná, a zvažujme posloupnost   definovanou jako

 

Ta odpovídá monotónní posloupnosti

 

takže lze doufat, že   dokonverguje k nějakému lokálnímu minimu   (pokud nebude divergovat k minus nekonečnu, což by znamenalo nalezení globálního infima  , anebo pokud se v některém kroku nedostaneme mimo oblast, kde je   definovaná či „pěkná“). Všimněte si, že hodnota velikosti kroku   se může měnit při každé iteraci. S určitými předpoklady o funkci   – například   lokálně konvexní a   lipschitzovská – a o algoritmu výběru   – např. Barzilaiovou-Borweinovou metodou[1]

 

– lze zaručit konvergenci na lokální minimum. Pokud je funkce   konvexní, lze zaručit nalezení globálního řešení.

Gradientní sestup funguje v prostorech libovolné dimenze, dokonce i v nekonečněrozměrných prostorech. V tom případě se obvykle prohledává nějaký prostor funkcí a počítá se Fréchetova derivace funkcionálu, který se má minimalizovat, aby se určil směr sestupu.[2]

Reference

editovat

V tomto článku byl použit překlad textu z článku Gradient descent na anglické Wikipedii.

  1. Optimization and control with applications. New York: Springer Science+Business Media 1 online resource (xlvi, 561 pages) s. Dostupné online. ISBN 978-0-387-24255-2, ISBN 0-387-24255-4. OCLC 262677614 
  2. KANTOROVICH, L. V. (LEONID VITALʹEVICH), 1912-1986. Functional analysis. Second edition. vyd. Oxford: [s.n.] xiv, 589 pages s. Dostupné online. ISBN 0-08-026486-7, ISBN 0-08-023036-9. OCLC 7206036 

Externí odkazy

editovat