Rozumíte někdo mechanismu toho, jak funguje Powell Method - hledání minima/maxima funkce bez použití gradientů? Používám
scipy.optimize.minimize ve snaze najít globální maximum mé funkce MyFunction s mnoha proměnnými (500+). (MyFunction je bohužel step function a její derivace je pro jakoukoli hodnotu zero gradient, takže nejde použít metody využívající derivace).
Když to hledání maxima spustím s nějakými náhodnými výchozími hodnotami, třeba to začne na úrovni, kdy moje funkce dá hodnotu -7000000 - tak to většinou udělá celkem rychle progres a najde hodnotu funkce o dost vyšší než ta výchozí hodnota - třeba skončí na -1000000 nebo +500000. Měl jsem zato, že to je tedy maximální hodnota funkce, kterou to dokáže najít a tím jsem měl věc za uzavřenou.
Jenže sem si všimnul, že když si uložím ty koeficienty z toho jakoby nejúspěšnějšího pokusu a spustím hledání znovu s těmito koeficienty jako výchozími hodnotami - tak to v některých případech vrátí výsledek, který je malinko lepší.
Takže jsem si udělal loop, který vypadá takhle:
start = np.random.sample(532)
res = minimize(MyFunction, start, method='Powell')
while True:
res = minimize(MyFunction, start, method='Powell')
start = res.x
Takhle se to postupně propracovává k lepšímu a lepšímu výsledku, příklad:
2 1210270.0
1 1210780.0
1 1213950.0
141 1214800.0
1 1216230.0
7 1219820.0
2 1220800.0
1 1222210.0
7 1222500.0
1 1228050.0
4 1229650.0
43 1231510.0
95 1232520.0
22 1234020.0
38 1234320.0
3 1243910.0
60 1245490.0
20 1245700.0
14 1245840.0
1 1246830.0
1 1247830.0
117 1247940.0
15 1250220.0
38 1255260.0
11 1256940.0
44 1257950.0
11 1258060.0
362 1265900.0
94 1267220.0
8 1269460.0
428 1270720.0
604 1271960.0
94 1272000.0
5 1272840.0
141 1275320.0
5 1275520.0
200 1276930.0
Ten druhý sloupeček je aktuální hodnota globálního maxima MyFunction, je vidět, že to hledání funguje. Problém je v tom prvním čísle - to je kolikrát skript spustil minimize() s koeficienty odpovídajícími jedné hodnotě funkce než to našlo vyšší.
Problém je v tom, že jedno to spuštění funkce minimize udělá cca 3-5000 evaluací MyFunction a to na AMD EPYC 7B13 (CPU MHz: 3049.996, BogoMIPS: 6099.99) trvá cca 90-120 sekund. Takže když to bylo aktuálně na hodnotě 1271960, tak trvalo asi 16 hodin než to malinko popostoupilo a našlo vyšší hodnotu.
Máte někdo nápad, jak tohle zrychlit? (Pozn: Už jsem to hodně zrychlil použitím JIT - jedna evaluace MyFunction je teď podle mého odhadu (neměřil jsem) 100x rychlejší než bez JIT - výše uvedeného hodnoty už jsou s JIT)
Zobrazit příspěvky
.
Jak geniální, že? .. Jenže samozřejmě sázet vždy na favorita se statisticky absolutně nevyplatí a kdyby někdo vsadil 1000 Kč na favorita ve všech těch 130k zápasech, tak skončí necelý 3 miliony v mínusu.
