Pașii uriași riscanți pot rezolva problemele de optimizare mai rapid | Revista Quanta

Problemele de optimizare pot fi dificile, dar fac ca lumea să funcționeze mai bine. Aceste tipuri de întrebări, care se străduiesc pentru cel mai bun mod de a face ceva, sunt absolut peste tot. GPS-ul telefonului dvs. calculează cea mai scurtă rută către destinație. Site-urile de călătorie caută cea mai ieftină combinație de zboruri care se potrivește cu itinerariul dvs. Iar aplicațiile de învățare automată, care învață analizând modele în date, încearcă să prezinte cele mai precise și mai asemănătoare răspunsuri umane la orice întrebare dată.

Pentru probleme simple de optimizare, găsirea celei mai bune soluții este doar o chestiune de aritmetică. Dar întrebările din lumea reală care îi interesează pe matematicieni și oamenii de știință sunt rareori simple. În 1847, matematicianul francez Augustin-Louis Cauchy lucra la un exemplu destul de complicat - calcule astronomice - când a lansat o metodă comună de optimizare cunoscută acum sub numele de coborâre în gradient. Majoritatea programelor de învățare automată de astăzi se bazează în mare măsură pe tehnică, iar alte domenii o folosesc și pentru a analiza date și a rezolva probleme de inginerie.

Matematicienii au perfecţionat coborârea în gradient de peste 150 de ani, dar luna trecută, un studiu a demonstrat că o presupunere de bază despre tehnică poate fi greșită. „Au fost de câteva ori în care am fost surprins, [cum ar fi] intuiția mea este ruptă”, a spus Ben Grimmer, un matematician aplicat la Universitatea Johns Hopkins și singurul autor al studiului. Rezultatele sale contraintuitive au arătat că coborârea în gradient poate funcționa de aproape trei ori mai rapid dacă încalcă o regulă acceptată de mult timp pentru a găsi cel mai bun răspuns pentru o anumită întrebare. În timp ce progresul teoretic probabil nu se aplică problemelor mai noioase abordate de învățarea automată, acesta i-a determinat pe cercetători să reconsidere ceea ce știu despre tehnică.

„Se pare că nu am avut o înțelegere deplină” a teoriei din spatele coborârii gradientului, a spus Shuvomoy Das Gupta, un cercetător în optimizare la Institutul de Tehnologie din Massachusetts. Acum, a spus el, suntem „mai aproape de a înțelege ce face coborârea în gradient”.

Tehnica în sine este înșelător de simplă. Folosește ceva numit funcție de cost, care arată ca o linie netedă, curbă, care șerpuiește în sus și în jos pe un grafic. Pentru orice punct de pe acea linie, înălțimea reprezintă într-un fel costul - cât timp, energie sau eroare va suporta operația atunci când este reglată la o anumită setare. Cu cât este mai mare punctul, cu atât sistemul este mai departe de ideal. Desigur, doriți să găsiți cel mai jos punct de pe această linie, unde costul este cel mai mic.

Algoritmii de coborâre în gradient își parcurg drumul spre partea de jos alegând un punct și calculând panta (sau gradientul) curbei din jurul acestuia, apoi deplasându-se în direcția în care panta este cea mai abruptă. Imaginați-vă că vă simțiți în jos pe un munte în întuneric. Este posibil să nu știți exact unde să vă deplasați, cât timp va trebui să faceți drumeții sau cât de aproape de nivelul mării vă veți ajunge în cele din urmă, dar dacă vă îndreptați spre coborârea cea mai bruscă, ar trebui să ajungeți în cele din urmă în cel mai jos punct din zonă.

Spre deosebire de alpinismul metaforic, cercetătorii în optimizare își pot programa algoritmii de coborâre în gradient pentru a face pași de orice dimensiune. Salturile uriașe sunt tentante, dar și riscante, deoarece ar putea depăși răspunsul. În schimb, înțelepciunea convențională a domeniului de zeci de ani a fost aceea de a face pași mici. În ecuațiile de coborâre a gradientului, aceasta înseamnă o dimensiune a pasului care nu este mai mare de 2, deși nimeni nu a putut dovedi că dimensiunile mai mici ale treptei au fost întotdeauna mai bune.

Odată cu progresele în tehnicile de demonstrare asistată de computer, teoreticienii în optimizare au început să testeze tehnici mai extreme. Într-un studiu, mai întâi postat în 2022 şi publicat recent in Programare matematică, Das Gupta și alții au însărcinat un computer să găsească cele mai bune lungimi de pași pentru un algoritm limitat la rularea a doar 50 de pași - un fel de problemă de meta-optimizare, deoarece încerca să optimizeze optimizarea. Ei au descoperit că cei mai optimi 50 de pași au variat semnificativ în lungime, cu un pas în mijlocul secvenței ajungând aproape la lungimea 37, cu mult peste limita tipică de lungime 2.

Descoperirile au sugerat că cercetătorii în optimizare au omis ceva. Intrigat, Grimmer a căutat să transforme rezultatele numerice ale lui Das Gupta într-o teoremă mai generală. Pentru a depăși un plafon arbitrar de 50 de pași, Grimmer a explorat care ar fi lungimile optime de pași pentru o secvență care s-ar putea repeta, apropiindu-se de răspunsul optim cu fiecare repetare. El a condus computerul prin milioane de permutări ale secvențelor lungi de pași, ajutând să le găsească pe cele care convergeau cel mai rapid către răspuns.

Grimmer a descoperit că cele mai rapide secvențe au întotdeauna un lucru în comun: pasul din mijloc a fost întotdeauna unul mare. Mărimea sa depindea de numărul de pași din secvența care se repetă. Pentru o secvență în trei pași, pasul mare avea lungimea de 4.9. Pentru o secvență de 15 pași, algoritmul a recomandat un pas cu lungimea de 29.7. Și pentru o secvență de 127 de pași, cea mai lungă testată, marele salt central a fost uriaș de 370. La început pare un număr absurd de mare, a spus Grimmer, dar au existat destui pași totali pentru a compensa acel salt uriaș, așa că chiar dacă ai suflat dincolo de fund, ai putea să te întorci repede. Lucrarea sa a arătat că această secvență poate ajunge la punctul optim de aproape trei ori mai repede decât ar face-o făcând pași constanti de copil. „Uneori, ar trebui să te depășești”, a spus el.

Această abordare ciclică reprezintă un mod diferit de a gândi coborârea gradientului, a spus Aymeric Dieuleveut, cercetător în optimizare la École Polytechnique din Palaiseau, Franța. „Această intuiție, că ar trebui să mă gândesc nu pas cu pas, ci ca un număr de pași consecutiv – cred că este ceva pe care mulți oameni îl ignoră”, a spus el. „Nu este modul în care este predat.” (Grimmer observă că această reîncadrare a fost și propus pentru o clasă similară de probleme într-o teză de master din 2018 de Jason Altschuler, un cercetător în optimizare acum la Universitatea din Pennsylvania.)

Cu toate acestea, deși aceste informații pot schimba modul în care cercetătorii gândesc despre coborârea gradientului, probabil că nu vor schimba modul în care tehnica este utilizată în prezent. Lucrarea lui Grimmer s-a concentrat doar pe funcții netede, care nu au îndoituri ascuțite și funcții convexe, care au forma unui bol și au o singură valoare optimă în partea de jos. Aceste tipuri de funcții sunt fundamentale pentru teorie, dar mai puțin relevante în practică; programele de optimizare pe care le folosesc cercetătorii de învățare automată sunt de obicei mult mai complicate. Acestea necesită versiuni de coborâre în gradient care au „atât de multe clopote și fluiere și atât de multe nuanțe”, a spus Grimmer.

Unele dintre aceste tehnici supuse pot merge mai repede decât abordarea cu pas mare a lui Grimmer, a spus Gauthier Gidel, un cercetător în optimizare și învățare automată la Universitatea din Montreal. Dar aceste tehnici au un cost operațional suplimentar, așa că speranța a fost că coborârea obișnuită a gradientului ar putea câștiga cu combinația potrivită de dimensiuni ale pașilor. Din păcate, accelerarea de trei ori a noului studiu nu este suficientă.

„Arată o îmbunătățire marginală”, a spus Gidel. „Dar cred că adevărata întrebare este: putem cu adevărat să reducem acest decalaj?”

Rezultatele ridică, de asemenea, un mister teoretic suplimentar care l-a ținut pe Grimmer treaz noaptea. De ce modelele ideale de dimensiuni ale pașilor aveau toate o formă atât de simetrică? Nu numai că cel mai mare pas este întotdeauna plasat în centru, dar același model apare pe ambele părți ale acestuia: Continuați să măriți și să subdivizați secvența, a spus el, și veți obține un „model aproape fractal” de pași mai mari înconjurat de pași mai mici. . Repetarea sugerează o structură de bază care guvernează cele mai bune soluții pe care nimeni nu a reușit încă să le explice. Dar Grimmer, cel puțin, are speranță.

„Dacă eu nu pot să-l sparg, altcineva o va face”, a spus el.