Conjugate gradient vs steepest descent

mrlngtng

Als minimisatie methoden kunnen deze gebruikt worden, maar ik snap niet goed wat het verschil is tussen beiden?

Er staat " In the steepest descent method zijn zowel gradiënt als richting loodrecht, in de conjugated gradient is de gradiënt loodrecht maar de richting geconjugeerd". Is dit het verschil tussen beiden? En wat wilt dat dan eigenlijk zeggen, ik kan er mij weinig bij voorstellen...

Flisk

Kan je wat meer achtergrondinformatie geven? Je praat hier over steepest decent en de gradiënt dus ik denk direct aan wiskunde (meer bepaald analyse in meerdere variabelen) en het numeriek zoeken van lokale minima. Maar je hebt dit geplaatst in moleculaire biologie en biochemie, dus het gaat niet over dat soort wiskunde?

mrlngtng

Flisk schreef: Kan je wat meer achtergrondinformatie geven? Je praat hier over steepest decent en de gradiënt dus ik denk direct aan wiskunde (meer bepaald analyse in meerdere variabelen) en het numeriek zoeken van lokale minima. Maar je hebt dit geplaatst in moleculaire biologie en biochemie, dus het gaat niet over dat soort wiskunde?

In bio-informatica wilt men de conformatie zoeken met de minimale energie, aangezien dit het meest stabiele conformeer is. Hiervoor worden afgeleide en niet - afgeleide energie minimisation methods gebruikt.

De afgeleide methoden omvatten de steepest descent method en de conjugated gradient.
Ik denk dus wel dat dit wiskundige methoden zijn, maar ik snap ze niet zo goed.

Flisk

Met de steepest decent methode kan ik misschien wel helpen. Uit de context gaat het hier dus over gradient descent (er is nog iets anders dat 'method of steepest decent' noemt, maar dat gaat over integratie.). Van conjugated gradient weet ik niet veel af en kan misschien iemand anders helpen.

De zin (of richting in Nederland) van de gradiënt van een functie geeft steeds de zin van maximale toename weer. Er geldt ook dat de tegengestelde zin, de zin van maximale afname geeft (weet je waarom? anders probeer ik het uit te leggen).

Wat die steepest decent methode doet is vanaf een bepaald punt vertrekken, kijken wat de gradiënt in dit punt is, en in tegengestelde zin van deze gradiënt naar het volgende punt gaan. Je blijft dit herhalen, zo krijg je steeds een kleinere waarde en zal je (bij een functie die 'braaf' genoeg is) steeds dichter bij het minimum naderen.

EDIT: de gradiënt staat altijd loodrecht op de niveaukrommen (of niveauoppervlakken, afhankelijk van aantal variabelen) van een functie. Logischerwijs, zal bij de steepest decent methode, de zin waarin je nieuwe punten zoekt ook steeds loodrecht op deze krommen zijn. Want die is immers evenwijdig met de gradiënt (maar met tegengestelde zin).

mrlngtng

Flisk schreef: Met de steepest decent methode kan ik misschien wel helpen. Uit de context gaat het hier dus over gradient descent (er is nog iets anders dat 'method of steepest decent' noemt, maar dat gaat over integratie.). Van conjugated gradient weet ik niet veel af en kan misschien iemand anders helpen.

De zin (of richting in Nederland) van de gradiënt van een functie geeft steeds de zin van maximale toename weer. Er geldt ook dat de tegengestelde zin, de zin van maximale afname geeft (weet je waarom? anders probeer ik het uit te leggen).

Wat die steepest decent methode doet is vanaf een bepaald punt vertrekken, kijken wat de gradiënt in dit punt is, en in tegengestelde zin van deze gradiënt naar het volgende punt gaan. Je blijft dit herhalen, zo krijg je steeds een kleinere waarde en zal je (bij een functie die 'braaf' genoeg is) steeds dichter bij het minimum naderen.

EDIT: de gradiënt staat altijd loodrecht op de niveaukrommen (of niveauoppervlakken, afhankelijk van aantal variabelen) van een functie. Logischerwijs, zal bij de steepest decent methode, de zin waarin je nieuwe punten zoekt ook steeds loodrecht op deze krommen zijn. Want die is immers evenwijdig met de gradiënt (maar met tegengestelde zin).

Bedankt, ik snap het al wat beter, maar is nog beetje onduidelijk voor mij wat die gradiënt etc nu juist is. Dus die gradiënt is de eerste afgeleide van de energie functie? Dus zou dit dan geen raaklijn aan uw oppervlak zijn? Hoe kan je dan weten wat die zin of richting hiervan is? En hoe weet je dat de zin ook loodrecht op de kromme staat?

Bij een conjugated gradiënt zeggen ze dat de gradiënt in elk punt loodrecht staat op de kromme, maar dat de zin (richting) geconjugeerd is?

Alvast bedankt!! Snap het al een stuk beter

Typhoner

mrlngtng schreef:
Bedankt, ik snap het al wat beter, maar is nog beetje onduidelijk voor mij wat die gradiënt etc nu juist is. Dus die gradiënt is de eerste afgeleide van de energie functie?

Ja, maar dus typisch in meerdere variabelen. Zeker als je praat over conformaties van moleculen, dan hebben we het over een grote set variabelen. De gradiënt is een vector van lengte N (aantal variablen), met respectivelijk de afgeleide naar de eerste, tweede, ... Nde variabele.

Xenion

Ik ken zelf ook niet alle details, maar ik kwam op deze paper die de intuïtie achter beide algoritmes beschrijft. (Geen lichte lectuur, maar wel heel verhelderend.)

Het komt erop neer dat de CG methode sneller convergeert, vooral in scenarios waar de kostfunctie een 'moeilijke' vorm zou hebben en waar gradient descent dus een lang zig-zag pad zou volgen. Zie bv de figuren op deze site.

Typhoner

Ikzelf heb wel wat ervaring met optimalisatie in een structuurchemische contekst, maar kijk er dan ook zeer pragmatisch naar. CG gaat inderdaad convergentie verbeteren, zeker dicht bij het minimum: er wordt niet alleen informatie van de huidige stap (dus gewoon de gradiënt) gebruikt, maar ook die van de vorige stappen. In de praktijk zou dit dan moeten leiden tot minder oscillaties eens je dicht bij het mimimum zit.

Flisk

mrlngtng schreef: Dus zou dit dan geen raaklijn aan uw oppervlak zijn? Hoe kan je dan weten wat die zin of richting hiervan is? En hoe weet je dat de zin ook loodrecht op de kromme staat?

Niet zo vanzelfsprekend om allemaal uit te leggen. Mijn cursus analyse doet er toch zeker 15 pagina's over, en dan moet je de kettingregel in meerdere variabelen kennen. Daar ga ik je nu niet mee lastigvallen.

Ik zal proberen het zo intuïtief mogelijk uit te leggen.

Eerst en vooral, beschouw gewoon de afgeleide in één variabele. Dit geeft in elk punt een getal, dit is dan de rico van de raaklijn. Dit getal is dus niet de raaklijn (maar de rico ervan). Je zou dan de gradiënt kunnen definiëren als de één dimensionale vector met als lengte de afgeleide. Er zijn dus maar twee mogelijkheden als zin, positief en negatief. Ook bij één variabele geeft de gradiënt de zin van maximale toename. Is de afgeleide immers positief, stijgt de functie wanneer je x positief laat toenemen. Is de afgeleide negatief, stijgt de functie wanneer je x laat afnemen. Het omgekeerde geldt wanneer je de richting van maximale afname zoekt.

Terug naar een functie met twee variabelen. Neem even aan dat ook hier de gradiënt de richting van maximaal stijgen/dalen geeft. De functie stelt dan een oppervlak voor. Die niveaukrommen waarover ik sprak, zijn de krommen die je krijgt wanneer je op dit oppervlak de punten met dezelfde functiewaarde verbindt. De zin van de gradiënt is dan loodrecht op deze krommen. Je kan dit wiskundig bewijzen, maar ook wel aanvoelen. Volg je immers de zin van de niveaukromme, dan verandert de functiewaarde helemaal niet. De niveaukromme heeft immers overal dezelfde waarde. Om dan maximaal te stijgen of dalen, moet je zoveel mogelijk uit de richting van deze niveaukromme bewegen (dus loodrecht erop). Nu volgt een tekening van een oppervlak met zijn niveaukrommen, merk op dat je deze krommen kan projecteren op het xy vlak en verifieer daarna visueel dat wanneer je loodrecht op deze krommen 'beweegt', de functiewaarde maximaal zal toenemen/afnemen:

: contour.JPG (27.03 KiB) 578 keer bekeken

Typhoner schreef:De gradiënt is een vector van lengte N (aantal variablen), met respectivelijk de afgeleide naar de eerste, tweede, ... Nde variabele.

De lengte is niet standaard gelijk aan N. De gradiënt heeft gelijk welke lengte, dit hang af van hoe stijl de functie in een punt is. In bijvoorbeeld minima of maxima, is de gradiënt de nulvector (met dus lengte nul).

Typhoner

Flisk schreef:
De lengte is niet standaard gelijk aan N. De gradiënt heeft gelijk welke lengte, dit hang af van hoe stijl de functie in een punt is. In bijvoorbeeld minima of maxima, is de gradiënt de nulvector (met dus lengte nul).

lengte als in "aantal elementen"

Wiskundig misschien niet de mooiste manier om het te verwoorden, maar iets wat een programmeur zou zeggen (en ook eigenlijk prima te begrijpen op basis van de rest van de zin)

mrlngtng

Oke, ik snap het nu goed genoeg in de termen van bio-informatica.

Nog 1 kleine opmerking: het verschil tussen de steepest descent (dus eigenlijk de gradient descent) en conjugated gradiënt is dat bij de conjugated gradiënt de zin geconjugeerd is (letterlijk staat er : "but the direction is conjugate"). Wat wil dit dan concreet zeggen? Laatste vraagje hoor, bedankt voor alle verduidelijking.

Wetenschapsforum

Laatste berichten

Nieuwsberichten

Conjugate gradient vs steepest descent

Conjugate gradient vs steepest descent

Re: Conjugate gradient vs steepest descent

Re: Conjugate gradient vs steepest descent

Re: Conjugate gradient vs steepest descent

Re: Conjugate gradient vs steepest descent

Re: Conjugate gradient vs steepest descent

Re: Conjugate gradient vs steepest descent

Re: Conjugate gradient vs steepest descent

Re: Conjugate gradient vs steepest descent

Re: Conjugate gradient vs steepest descent

Re: Conjugate gradient vs steepest descent