Gradientní sestup

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání
Gradientní sestup a vrstevnice minimalizované 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.

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í.

Popis[editovat | editovat zdroj]

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 | editovat zdroj]

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 | editovat zdroj]