Gradientní sestup
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
editovatGradientní 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
editovatV tomto článku byl použit překlad textu z článku Gradient descent na anglické Wikipedii.
- ↑ 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
- ↑ 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- Obrázky, zvuky či videa k tématu gradientní sestup na Wikimedia Commons