Gradiens süllyedés

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. július 17-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A gradiens süllyedés, a gradiens süllyedés módszere  egy numerikus módszer egy függvény lokális minimumának vagy maximumának meghatározására egy gradiens mentén történő mozgással, amely a modern optimalizálás egyik fő numerikus módszere.

A számítási matematikában nem csak optimalizálási (minimalizálási) feladatok közvetlen megoldására, hanem az optimalizáló nyelven átírható feladatokra is aktívan alkalmazzák (nemlineáris egyenletek megoldása, egyensúlyok keresése, inverz feladatok stb.). A gradiens süllyedés módszere használható optimalizálási feladatok végtelen dimenziós terekben, például optimális szabályozási feladatok numerikus megoldására.

Az utóbbi években a gradiens módszerek iránti különösen nagy érdeklődés annak köszönhető, hogy a gradiens süllyedések és azok sztochasztikus/randomizált változatai szinte minden modern adatelemzési tanulási algoritmus alapját képezik.

Leírás

A célfüggvény nézzen ki így:

.

És az optimalizálási probléma a következő:

Abban az esetben, ha használat helyett a maximumot kell megtalálni

A módszer fő gondolata, hogy a legmeredekebb ereszkedés irányába menjünk, és ezt az irányt az antigradiens adja :

ahol a gradiens süllyedési sebességét határozza meg, és választható

Algoritmus

  1. Állítsa be a kezdeti közelítést és a számítási pontosságot
  2. Számold meg hol
  3. Ellenőrizze a leállás állapotát:
    • Ha , vagy (válasszon egyet a feltételek közül), akkor folytassa a 2. lépéssel.
    • Ellenkező esetben álljon meg.

A Kantorovich-reláció

Az alak másodfokú függvényében a legmeredekebb gradiens keresési módszer bármely kiindulási pontból egy geometriai haladási sebességgel (lineárisan) konvergál , amelynek nevezője nem haladja meg a . Ebben az esetben a következő becslések érvényesek:

, , ,

ahol és a második derivált mátrixának  minimális és maximális sajátértéke .

Így, mivel a függvény kis mértékben közel van a másodfokú közelítéséhez, a konvergencia sebessége a minimumpont közelében a sajátértékek arányától függ. Minél nagyobb ez az arány, annál rosszabb a módszer konvergenciája.

Példa

Alkalmazzuk a gradiens módszert a függvényre . Ekkor az egymást követő közelítések így fognak kinézni:

Ez egy tipikus példa a szakadék funkcióra. A gradiens módszer "ugrik" a szakadék egyik lejtőjéről a másikra és vissza, néha szinte anélkül, hogy a megfelelő irányba mozdulna el, ami jelentősen lelassítja a konvergenciát. Egy másik példa a tesztvízcsatorna függvényre a Rosenbrock függvény .

Fejlesztések, módosítások

A gradiens irányú függvényének minimalizálására egydimenziós optimalizálási módszereket alkalmaznak , például az aranymetszet módszert . Nem is a gradiens irányában kereshet a legjobb pontot, hanem az aktuálisnál jobbat.

A gradiens süllyedés módszere a legkönnyebben megvalósítható az összes helyi optimalizálási módszer közül. Meglehetősen gyengék a konvergencia feltételei, de a konvergencia ráta meglehetősen kicsi (lineáris). A gradiens módszer lépését gyakran használják más optimalizálási módszerek, például a Fletcher-Reeves módszer részeként .

A gradiens süllyedés módszere nagyon lassúnak bizonyul szakadék mentén haladva, és a célfüggvény-változók számának növekedésével a módszernek ez a viselkedése válik jellemzővé. A jelenség leküzdésére a szakadékos módszert alkalmazzák , amelynek lényege nagyon egyszerű. Két lépcsős ereszkedési lépés megtétele és három pont megszerzése után a harmadik lépést az első és harmadik pontot összekötő vektor irányába kell megtenni, a szakadék alján.

A másodfokúhoz közeli függvények esetén a konjugált gradiens módszer hatékony .

Alkalmazások mesterséges neurális hálózatokban

A gradiens leereszkedési módszert némi módosítással széles körben használják a perceptron képzésére, és a mesterséges neurális hálózatok elméletében backpropagation módszerként ismert . Perceptron típusú neurális hálózat betanításakor a hálózat súlyegyütthatóit úgy kell megváltoztatni, hogy a neurális hálózat kimenetének átlagos hibája minimális legyen, amikor a betanítási bemeneti adatok sorozatát betáplálják a bemenetre. . Formálisan ahhoz, hogy a gradiens süllyedés módszere szerint csak egy lépést tegyen meg (csak egy változtatást hajtson végre a hálózati paraméterekben), szükséges, hogy a teljes képzési adatkészletet szekvenciálisan betápláljuk a hálózati bemenetre, és ki kell számítani a hibát minden betanítási adatra. objektumot, és számítsa ki a hálózati együtthatók szükséges korrekcióját (de ne végezze el ezt a korrekciót), majd az összes adat elküldése után számítsa ki az egyes hálózati együtthatók korrekciójának összegét (gradiensek összege), és javítsa ki az együtthatókat „egy lépéssel” . Nyilvánvaló, hogy nagy mennyiségű betanítási adathalmaz esetén az algoritmus rendkívül lassan fog működni, ezért a gyakorlatban a hálózati együtthatókat gyakran minden egyes betanítási elem után módosítják, ahol a gradiens értékét a költségfüggvény csak egyre számított gradiensével közelítik. képzési elem. Ezt a módszert sztochasztikus gradiens süllyedésnek vagy operatív gradiens süllyedésnek nevezik . A sztochasztikus gradiens süllyedés a sztochasztikus közelítés egyik formája. A sztochasztikus közelítések elmélete feltételeket ad a sztochasztikus gradiens süllyedés módszerének konvergenciájához.

Linkek

Irodalom