Springen naar inhoud

Conjugate gradient vs steepest descent


  • Log in om te kunnen reageren

#1

mrlngtng

    mrlngtng


  • >250 berichten
  • 251 berichten
  • Ervaren gebruiker

Geplaatst op 22 juni 2014 - 19:58

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


Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Flisk

    Flisk


  • >1k berichten
  • 1270 berichten
  • Moderator

Geplaatst op 22 juni 2014 - 20:16

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? 

Je leest maar niet verder want je, je voelt het begin van wanhoop.

#3

mrlngtng

    mrlngtng


  • >250 berichten
  • 251 berichten
  • Ervaren gebruiker

Geplaatst op 22 juni 2014 - 20:24

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.


#4

Flisk

    Flisk


  • >1k berichten
  • 1270 berichten
  • Moderator

Geplaatst op 22 juni 2014 - 20:43

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

Veranderd door Flisk, 22 juni 2014 - 20:59

Je leest maar niet verder want je, je voelt het begin van wanhoop.

#5

mrlngtng

    mrlngtng


  • >250 berichten
  • 251 berichten
  • Ervaren gebruiker

Geplaatst op 23 juni 2014 - 08:53

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


#6

Typhoner

    Typhoner


  • >1k berichten
  • 2446 berichten
  • VIP

Geplaatst op 23 juni 2014 - 10:15

 

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.

This is weird as hell. I approve.

#7

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 23 juni 2014 - 11:35

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.


#8

Typhoner

    Typhoner


  • >1k berichten
  • 2446 berichten
  • VIP

Geplaatst op 23 juni 2014 - 12:27

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.

This is weird as hell. I approve.

#9

Flisk

    Flisk


  • >1k berichten
  • 1270 berichten
  • Moderator

Geplaatst op 23 juni 2014 - 13:30

Dus die gradiënt is de eerste afgeleide van de energie functie?

Ik zal proberen te illustreren wat de gradiënt is. Meest eenvoudige geval: 
Stel we hebben een functie f(x,y) die twee variabelen x en y afbeeld op één enkel getal. Plotten we dit in een ruimte met 3 assen (x, y en z=f(x,y) as), dan krijgen we een oppervlak. 

Je hebt dus meerdere variabelen, dus er bestaat niet zomaar één afgeleide. Wat we wel kunnen doen is elke variabele als vast beschouwen, behalve één ervan, en dan afleiden naar die ene. Dit noemt de partieel afgeleide naar die bepaalde variabele. Bij een functie van N veranderlijken zijn er dus N partieel afgeleiden.

Terug naar ons voorbeeld, in elk punt (x,y) noemt men de gradiënt de volgende vector: LaTeX

. Die eerste component is de partieel afgeleide naar x, de tweede component is de partieel afgeleide naar y. De gradiënt wordt vaak genoteerd als LaTeX
 

 

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
 

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

Je leest maar niet verder want je, je voelt het begin van wanhoop.

#10

Typhoner

    Typhoner


  • >1k berichten
  • 2446 berichten
  • VIP

Geplaatst op 23 juni 2014 - 17:31

 

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)

Veranderd door Typhoner, 23 juni 2014 - 17:35

This is weird as hell. I approve.

#11

mrlngtng

    mrlngtng


  • >250 berichten
  • 251 berichten
  • Ervaren gebruiker

Geplaatst op 23 juni 2014 - 19:56

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.  






0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures