Tässä on yhteinen kehys sekä kaltevuuslaskun että Newtonin menetelmän tulkinnalle, mikä on ehkä hyödyllinen tapa ajatella eroa @ Sycoraxin vastauksen täydennyksenä. (BFGS lähentää Newtonin menetelmää; en puhu siitä erityisesti tässä.)

Pienennämme funktion $ f $, mutta emme tiedä miten se tehdään suoraan. Joten sen sijaan otamme paikallisen likiarvon nykyiseen pisteeseemme $ x $ ja pienennämme sen.

Newtonin menetelmä liki funktion toisen asteen Taylorin laajennuksella: $$ f (y) \ noin N_x ( y): = f (x) + \ nabla f (x) ^ T (y - x) + \ tfrac12 (y - x) ^ T \, \ nabla ^ 2 f (x) \, (y - x), $$ jossa $ \ nabla f (x) $ merkitsee $ f $ kaltevuutta pisteessä $ x $ ja $ \ nabla ^ 2 f (x) $ hessiläistä kohdassa $ x $ .Se siirtyy sitten $ \ arg \ min_y N_x (y) $ ja toistuu.

Laskeutuminen kaltevuudella, jolla on vain kaltevuus eikä hessiläinen, ei voi vain tehdä ensimmäisen kertaluvun likiarvoa ja minimoida sen, koska kuten @Hurkyl totesi, sillä ei ole vähintään. Sen sijaan määritämme askeleen koon $ t $ ja siirrymme kohtaan $ x - t \ nabla f (x) $. Huomaa kuitenkin, että \ begin {tasaa} x - t \, \ nabla f (x) & = \ arg \ max_y \ left [f (x) + \ nabla f (x) ^ T (y - x) + \ tfrac { 1} {2 t} \ lVert y - x \ rVert ^ 2 \ oikea] \\ & = \ arg \ max_y \ vasen [f (x) + \ nabla f (x) ^ T (y - x) + \ tfrac12 (yx) ^ T \ tfrac {1} {t} I (y - x) \ oikea]. \ end {tasaus} Täten kaltevuuslasku minimoi funktion $$ G_x (y): = f (x) + \ nabla f (x) ^ T (y - x) + \ tfrac12 (yx) ^ T \ tfrac {1} {t} I (y - x). $$

Siten kaltevuuslasku on eräänlainen kuin Newtonin menetelmän käyttö, mutta sen sijaan, että ottaisimme toisen asteen Taylorin laajennuksen, teeskennämme, että hessiläinen on $ \ tfrac1t I $. Tämä $ G $ on usein huomattavasti huonompi likiarvo dollariin $ $ kuin $ N $, ja siksi kaltevuuslasku vie usein paljon huonompia vaiheita kuin Newtonin menetelmä. Tätä tasapainottaa tietysti se, että jokainen kaltevuuslaskun vaihe on niin paljon halvempi laskea kuin jokainen Newtonin menetelmän vaihe. Mikä on parempi, riippuu kokonaan ongelman luonteesta, laskennallisista resursseistasi ja tarkkuusvaatimuksistasi.

Tarkastellaan @ Sycoraxin esimerkkiä neliöllisen $$ f (x) minimoimisesta. = \ tfrac12 x ^ TA x + d ^ T x + c $$ hetkeksi, on syytä huomata, että tämä näkökulma auttaa ymmärtämään molempia menetelmiä.

Newtonin menetelmällä meillä on $ N = f $ siten, että se päättyy tarkalla vastauksella (aina liukuluvun tarkkuuskysymyksiin saakka) yhdessä vaiheessa.

Toisaalta kaltevuuslasku käyttää $$ G_x (y) = f (x) + (A x + d) ^ T y + \ tfrac12 (x - y) ^ T \ tfrac1t I (xy) $$, jonka tangenttitaso $ x $: ssa on oikea, mutta jonka kaarevuus on täysin väärä, ja heittää todellakin merkittäviä eroja eri suuntiin, kun $ A $: n ominaisarvot vaihtelevat huomattavasti.

Newtonin menetelmän kaltaisen toisen johdannaisen menetelmän etuna on pohjimmiltaan se, että sillä on toisen asteen päättymisen laatu. Tämä tarkoittaa, että se voi minimoida asteen funktion rajallisella määrällä vaiheita. Gradientin laskeutumisen kaltainen menetelmä riippuu suuresti oppimisnopeudesta, mikä voi saada optimoinnin joko lähentymään hitaasti, koska se hyppää optimin ympärille, tai eroamaan kokonaan. Vakaa oppimisnopeus löytyy ... mutta siihen sisältyy hessian laskeminen. Jopa vakaan oppimisnopeuden avulla sinulla voi olla ongelmia, kuten värähtely optimin ympärillä, ts. Et aina kulje "suoraa" tai "tehokasta" polkua kohti minimiä. Joten lopettaminen voi kestää monia iteraatioita, vaikka olisit suhteellisen lähellä sitä. BFGS ja Newtonin menetelmä voivat lähentyä nopeammin, vaikka jokaisen vaiheen laskennallinen työ on kalliimpaa.

Esimerkkipyyntösi: Oletetaan, että sinulla on tavoitefunktio $$ F (x) = \ frac {1 } {2} x ^ TAx + d ^ Tx + c $$ Gradientti on $$ \ nabla F (x) = Ax + d $$ ja sen asettaminen jyrkimpään laskeutumismuotoon tasaisella oppimisnopeudella $$ x_ {k + 1} = x_k- \ alpha (Ax_k + d) = (I- \ alpha A) x_k- \ alpha d. $$

Tämä on vakaa, jos $ I- \: n ominaisvektorien suuruudet alfa A $ ovat alle 1. Voimme käyttää tätä ominaisuutta osoittamaan, että vakaa oppimisnopeus täyttää $$ \ alpha< \ frac {2} {\ lambda_ {max}}, $$, jossa $ \ lambda_ {max} $ on suurin ominaisarvo $ A $. Jyrkimmän laskeutumisalgoritmin lähentymisnopeutta rajoittaa suurin ominaisarvo, ja rutiini lähestyy nopeimmin vastaavan ominaisvektorinsa suuntaan. Samoin se yhtyy hitaimmin pienimmän ominaisarvon ominaisvektorin suuntiin. Kun $ A $: n suurten ja pienten ominaisarvojen välillä on suuri ero, gradientin lasku on hidasta. Kaikki $ A $, joilla on tämä ominaisuus, lähestyvät hitaasti kaltevuuslaskua.

Neuroverkkojen erityiskontekstissa kirjassa Neural Network Design on melko vähän tietoa numeerisista optimointimenetelmistä. Yllä oleva keskustelu on tiivistelmä osioista 9-7.

Kuparissa optimoinnissa arvioit funktion toisen asteen polynomina yhden ulottuvuuden tapauksessa: $$ f (x) = c + \ beta x + \ alpha x ^ 2 $$

Tässä tapauksessa toinen johdannainen $$ \ osittainen ^ 2 f (x) / \ osittainen x ^ 2 = 2 \ alfa $$

Jos tiedät johdannaiset, on helppo saada seuraava arvaus optimaaliseksi : $$ \ text {guess} = - \ frac {\ beta} {2 \ alpha} $$

Monimuuttujatapa on hyvin samanlainen, käytä vain gradientteja johdannaisiin.

@Dougal antoi jo erinomaisen teknisen vastauksen.

Ei-matematiikan selitys on, että vaikka lineaarinen (järjestys 1) likiarviointi antaa "tason", joka on tangentiaalinen virhepinnan pisteeseen, toisen asteen approksimaatio (järjestys 2) tarjoaa pinnan, joka halaavirhepinta.

Tämän linkin videot tekevät hienoa työtä tämän konseptin visualisoimisessa.Ne näyttävät järjestyksen 0, järjestyksen 1 ja 2 likiarvot funktion pinnalle, mikä vain intuitiivisesti tarkistaa, mitä muut vastaukset matemaattisesti esittävät.

Lisäksi hyvä blogiviesti aiheesta (jota sovelletaan neuroverkoihin) on täällä.