Random search

[Drieske]

Ik weet nog niet zeker of ik het volledig snap. Op wikipedia lees ik als mogelijke terminatievoorwaarden: een gewenste nauwkeurigheid is bereikt. Hoe weet je wanneer die nauwkeurigheid is bereikt als je je (lokaal of globaal, maakt niet uit voor mij) maximum niet exact kent?

[Xenion]

Ik vermoed dat ze eerder iets bedoelen in de zin van 'als het geschatte maximum niet teveel meer verplaatst in opeenvolgende iteraties'.

[Drieske]

Okee. Dat begrijp ik dan wel. Dat was ook mijn bezwaar met de methode geschetst door TS. Bedoelt hij echter wat jij zegt, of niet? Uit zijn posts begrijp ik eerder niet...

[Xenion]

Ja hoor, hij zegt wel zoiets gelijkaardig.

Begin zomaar ergens in de hooiberg. Trek zes kleine random getallen ...

Beschouw een kostfunctie f(x) het huidige optimum u.

Genereer een 'kleine' random vector du.

(Merk op: bold letters om vectoren aan te duiden)

Vergelijk f(u) en f(u+du). Als de 2de groter is, beschouw dan die nieuwe waarde als het huidige optimum en herhaal. Indien kleiner, genereer een nieuwe du en kijk of die beter is.

Op die manier 'loop' je dus ook uiteindelijk in stijgende richting van f zonder de gradient of zelfs maar een analytische uitdrukking te moeten kennen. Maar door de willekeur van het algoritme is de convergentie relatief traag.

[Drieske]

Daar ben ik het mee eens. Maar zijn criterium om te stoppen doet me eerder denken aan dat je het maximum moet kennen. (In de openingspost staat zelfs geen criterium.)

[Xenion]

Jawel hoor: hij gebruikt een maximum aantal iteraties. Maar akkoord dat het niet zo'n goed criterium is

[JorisL]

Je kan ook gebruiken dat je punt nagenoeg vast blijft. Dus als je gedurende n (10 of 100 oid) iteraties hebt dat f(y)-f(x) < 1e-6 (Dus dat er slechts op 6 cijfers na de komma iets veranderd). Hierbij is y de coordinaat van het nieuwe extremum ( f(y)>f(x)). Zo kan je arbitrair dicht (tot bij de precisie van je machine) naderen naar de extreme waarde en zijn coordinaten.

Edit: Met een beetje programmeren kan je dan ook de convergentie versnellen in gevallen dat je functie sterk stijgt/daalt. Simpelweg door in een groter volume rond je huidige punt te werken om je nieuwe sample punt te bepalen. Maar dat is hier verder niet van belang.

[Drieske]

Volgens mij is dat het criterium dat Xenion ook omschreef. Als dat voldaan is, kan ik ermee leven dat het redelijk is. Maar als je proces stopt omdat je aantal iteraties is bereikt, ben je er (de uitkomst) niets mee lijkt me.

[JorisL]

Je kan natuurlijk tweeledig werken. Stel je wilt tot 6 cijfers na de komma juist zitten. Maar als je een vervelende functie hebt kan dat erg lang duren. Dus dan kan je er een extra maximaal aantal iteraties op zetten.

Het is dan belangrijk om bij de output aangeven dat het maximale aantal iteraties bereikt is. Dan weet je dus niet of je goed zit of niet. De eerste 3 na de komma waarschijnlijk wel maar verder begint het gokken. (Je kan natuurlijk het laatste verschil tussen de iteraties ook meegeven naar de output zodat je al iets meer weet.)

[JKZ]

Wat ik op Wiki las klopt niet met mijn ervaring. Ik kon op heel verkeerde punten in de hooiberg beginnen en de computer zat al heel gauw op het goede spoor. Maar misschien had ik geluk met mijn hooiberg.

Met dat "heel lanzaam" heeft hij soms gelijk in de zin van veel kleine stappen. Met de snelheid van computers van tegenwoordig is dat niet langzaam in termen van tijd. Het beste werkt met grote stappen beginnen en naarmate de geslaagde pogingen schaarser worden de stapgrootte verkleinen.

[JKZ]

Het optimaliseren van een functie van meerdere variabelen is een vak apart. Er is veel aan gedaan, er zijn in de loop der tijden vele strategieën bedacht en bij elke is het weer mogelijk een situatie te verzinnen waar het misgaat, met random search niet als uitzondering. Het gevaar dat je eindigt bovenop de verkeerde bult van de kameel bestaat bijvoorbeeld bij random search ook, hoewel er wel dingen zijn te verzinnen om dat risico te verkleinen.

Zeker is het geen kant-en -klaar machientje waarbij je alleen maar aan de slinger hoeft te draaien en je probleem is opgelost. En evenmin is dit een pleidooi om de andere manieren maar te vergeten en voortaan alles met random search te doen.

Het is iets om te overwegen als het met de “nette” manieren maar steeds niet wil lukken. Dan moet je vooral denken aan een project dat gaat over iets dat in werkelijkheid bestaat en waar je dingen van weet die je wellicht ook kunt meenemen.

Dit laatste maakt bijvoorbeeld dat het terminatieprobleem, punt van zorg voor Drieske, vaak geen groot probleem is. Ook al omdat het in de praktijk vaak weinig zin heeft de grootste nauwkeurigheid na te jagen, is het voor een bekeuring belangrijk of je snelheid 110,014 of 110, 015 was?

Besluit je aan de slag te gaan met random search, dan is het maatwerk, je zal er eigen werk en eigen creativiteit in moeten stoppen, slim manipuleren met de stapgrootte bijvoorbeeld.

Maar met de rekenkracht van tegenwoordig is het niet meer dom om manieren te proberen die vroeger te dom waren omdat het veel te veel werk was.