Newtonov 300-ročný algoritmus získal revolučné vylepšenie. Mal významný nedostatok, tvrdia vedci

Každý deň sa výskumníci snažia nájsť optimálne riešenia. Možno chcú zistiť, kde postaviť hlavný letiskový uzol, alebo určiť, ako maximalizovať návratnosť pri minimalizácii rizika v investičnom portfóliu. Prípadne vyvinúť samojazdiace autá, ktoré dokážu rozlíšiť medzi semaformi a značkami stop.

Z matematického hľadiska sa tieto problémy prekladajú do hľadania minimálnych hodnôt funkcií. Ale vo všetkých týchto situáciách sú funkcie príliš komplikované na priame posúdenie. Vedci musia namiesto toho minimálne hodnoty aproximovať.

Matematická navigácia v tmách

Ako informuje quantamagazine a štúdia uverejnená na arxiv, ukazuje sa, že jedným z najlepších spôsobov, ako to urobiť, je použitie algoritmu, ktorý Isaac Newton vyvinul pred viac ako 300 rokmi. Tento algoritmus je pomerne jednoduchý. Je to trochu ako hľadanie najnižšieho bodu v neznámej krajine so zaviazanými očami. Ako kladieš jednu nohu pred druhú, jediné informácie, ktoré potrebuješ, sú, či ideš do kopca alebo z kopca a či sa sklon zväčšuje alebo zmenšuje. Pomocou týchto informácií môžeš pomerne rýchlo získať dobrú aproximáciu minima.

Hoci je táto metóda nesmierne výkonná – stáročia po jej objavení je Newtonova metóda stále kľúčová na riešenie súčasných problémov v logistike, financiách, počítačovom videní a dokonca aj v čistej matematike – má aj významný nedostatok. Nefunguje dobre pre všetky funkcie. Preto matematici pokračujú v štúdiu tejto techniky a hľadajú rôzne spôsoby, ako rozšíriť jej rozsah bez obetovania efektivity.

Ako funguje Newtonova metóda

Matematické funkcie transformujú vstupy na výstupy. Často najdôležitejšou vlastnosťou funkcie je jej minimálna hodnota – kombinácia vstupov, ktorá produkuje najmenší možný výstup.

Nájsť minimum je však ťažké. Funkcie môžu mať desiatky premenných umocnených na vysoké mocniny, čo bráni formulovej analýze. Grafy ich riešení tvoria mnohorozmerné krajiny, ktoré nikto nedokáže preskúmať z vtáčej perspektívy.

V 80. rokoch 17. storočia Newton spoznal, že aj keď pracuješ s veľmi komplikovanou funkciou, stále budeš mať prístup aspoň k dvom informáciám, ktoré ti pomôžu nájsť jej najhlbšie údolie. Po prvé, môžeš vypočítať takzvanú prvú deriváciu funkcie alebo sklon: strmosť funkcie v danom bode. Po druhé, môžeš vypočítať rýchlosť, akou sa samotný sklon mení (druhá derivácia funkcie).

Povedzme, že sa snažíš nájsť minimum nejakej komplikovanej funkcie. Najprv vyber bod na funkcii, o ktorom si myslíš, že by mohol byť blízko skutočného minima. Vypočítaj prvú a druhú deriváciu funkcie v tomto bode. Tieto derivácie použiješ na zostrojenie špeciálnej kvadratickej rovnice – paraboly, ak tvoja funkcia existuje v 2D rovine, a miskovitého tvaru nazývaného paraboloid, ak je tvoja funkcia viacrozmerná. Táto kvadratická rovnica, ktorá sa nazýva Taylorova aproximácia, zhruba pripomína tvoju funkciu v bode, ktorý si vybral.

Teraz vypočítaj minimum kvadratickej rovnice namiesto pôvodnej – niečo, čo môžeš urobiť ľahko pomocou známeho vzorca. Dostaneš bod. Potom vlož súradnice tohto bodu späť do pôvodnej funkcie a dostaneš nový bod na funkcii, ktorý sa nachádza bližšie k jej skutočnému minimu. Začni celý proces znova.

Nové prekvapivé vylepšenia

Minulé leto traja výskumníci oznámili najnovšie vylepšenie Newtonovej metódy. Amir Ali Ahmadi z Princetonskej univerzity spolu so svojimi bývalými študentmi Abraarom Chaudhrym a Jeffreym Zhangom rozšírili Newtonovu metódu tak, aby efektívne fungovala na najširšej triede funkcií doteraz.

V storočiach odvtedy matematici pracovali na rozšírení jeho metódy, aby preskúmali, koľko informácií môžu získať zo zložitejších Taylorových aproximácií svojich funkcií. V 19. storočí napríklad ruský matematik Pafnutij Čebyšov navrhol verziu Newtonovej metódy, ktorá približovala funkcie kubickými rovnicami (ktoré majú exponent 3). No jeho algoritmus nefungoval, keď pôvodná funkcia zahŕňala viacero premenných.

Celkom nedávno, v roku 2021, Jurij Nesterov demonštroval, ako efektívne aproximovať funkcie ľubovoľného počtu premenných kubickými rovnicami. Ale jeho metóda sa nemohla rozšíriť na aproximáciu funkcií pomocou kvartických rovníc, kvintických a tak ďalej bez straty efektívnosti.

Teraz Ahmadi, Chaudhry a Zhang posunuli Nesterovov výsledok o ďalší krok vpred. Ich algoritmus funguje pre ľubovoľný počet premenných a ľubovoľne veľa derivácií. Navyše zostáva efektívny pre všetky tieto prípady – niečo, čo doteraz nikto nedokázal.

Budúcnosť optimalizácie

Neexistuje rýchla všeobecná metóda na nájdenie miním funkcií umocnených na vysoké exponenty. To vždy predstavovalo hlavné obmedzenie Newtonovej metódy. Ale existujú určité typy funkcií, ktoré majú charakteristiky, vďaka ktorým ich možno ľahko minimalizovať. V novej práci Ahmadi, Chaudhry a Zhang dokazujú, že vždy môžeš nájsť aproximujúce rovnice, ktoré majú tieto charakteristiky.

Aké vlastnosti uľahčujú minimalizáciu rovnice? Dve veci: Prvá je, že rovnica by mala mať tvar misky alebo byť „konvexná“. Namiesto mnohých údolí má len jedno – to znamená, že keď sa ju snažíš minimalizovať, nemusíš sa obávať, že zamieňaš ľubovoľné údolie za najnižšie.

Druhou vlastnosťou je, že rovnicu možno napísať ako súčet štvorcov. Napríklad 5x² + 16x + 13 možno napísať ako súčet (x + 2)² + (2x + 3)². V posledných rokoch matematici vyvinuli techniky na minimalizáciu rovníc s ľubovoľne veľkými exponentmi, pokiaľ sú konvexné a sú súčtom štvorcov.

Ahmadi, Chaudhry a Zhang prišli na to, ako použiť techniku nazývanú semidefinitné programovanie na „zahýbanie“ Taylorovej aproximácie dostatočne. Potrebovali, aby bola súčtom štvorcov aj konvexná, ale nie natoľko vzdialená od pôvodnej funkcie, ktorú mala pripomínať.

Rovnako ako pôvodná verzia Newtonovej metódy, každá iterácia tohto nového algoritmu vyžaduje viac výpočtového výkonu než metódy ako zostup gradientu. V dôsledku toho nová práca zatiaľ nezmení spôsob, akým fungujú samojazdiace autá, algoritmy strojového učenia alebo systémy riadenia letovej prevádzky.

„Náš algoritmus je teraz preukázateľne rýchlejší, teoreticky,“ povedal Ahmadi. Dúfa, že za 10 až 20 rokov, keď výpočtová technika pokročí, ich algoritmus prekoná zostup gradientu pre všetky aplikácie vrátane strojového učenia.

Čítajte viac z kategórie: Zaujímavosti