Riskantsete hiiglaslike sammudega saab optimeerimisprobleeme kiiremini lahendada | Quanta ajakiri

Optimeerimisprobleemid võivad olla keerulised, kuid need muudavad maailma paremaks. Selliseid küsimusi, mis püüavad midagi parimat teha, on absoluutselt igal pool. Teie telefoni GPS arvutab lühima marsruudi teie sihtkohta. Reisiveebisaidid otsivad teie marsruudile vastavat odavaimat lendude kombinatsiooni. Ja masinõpperakendused, mis õpivad andmete mustreid analüüsides, püüavad esitada igale küsimusele kõige täpsemaid ja inimlikumaid vastuseid.

Lihtsate optimeerimisülesannete puhul on parima lahenduse leidmine vaid aritmeetika küsimus. Kuid matemaatikuid ja teadlasi huvitavad reaalmaailma küsimused on harva lihtsad. 1847. aastal töötas prantsuse matemaatik Augustin-Louis Cauchy sobivalt keerulise näite – astronoomiliste arvutuste – kallal, kui ta lõi teerajajaks levinud optimeerimismeetodi, mida praegu tuntakse gradiendi laskumisena. Enamik masinõppeprogramme toetub tänapäeval suuresti tehnikale ning ka teised valdkonnad kasutavad seda andmete analüüsimiseks ja inseneriprobleemide lahendamiseks.

Matemaatikud on gradiendi laskumist täiustanud üle 150 aasta, kuid eelmisel kuul uuringus tõestas, et põhieeldus tehnika kohta võib olla vale. "Olin lihtsalt mitu korda üllatunud, [nagu] mu intuitsioon on katki," ütles Ben Grimmer, Johns Hopkinsi ülikooli rakendusmatemaatik ja uuringu ainus autor. Tema intuitiivsed tulemused näitasid, et gradiendiga laskumine võib töötada peaaegu kolm korda kiiremini, kui see rikub kaua aktsepteeritud reeglit, kuidas leida antud küsimusele parim vastus. Kuigi teoreetiline edusamm tõenäoliselt ei kehti masinõppega lahendatavate suuremate probleemide kohta, on see pannud teadlasi uuesti läbi vaatama, mida nad tehnikast teavad.

"Selgub, et meil ei olnud täielikku arusaamist gradiendi laskumise teooriast," ütles Shuvomoy Das Gupta, Massachusettsi Tehnoloogiainstituudi optimeerimise uurija. Nüüd, ütles ta, oleme "lähemal mõistmisele, mida gradient laskumine teeb."

Tehnika ise on petlikult lihtne. See kasutab midagi, mida nimetatakse kulufunktsiooniks, mis näeb välja nagu sujuv kõverjoon, mis lookleb üle graafiku üles-alla. Selle joone mis tahes punkti puhul tähistab kõrgus mingil viisil kulusid – kui palju aega, energiat või viga kulub toimingule, kui see on häälestatud konkreetsele seadistusele. Mida kõrgem on punkt, seda kaugemal on süsteem ideaalist. Loomulikult soovite leida sellel real madalaima punkti, kus kulu on kõige väiksem.

Gradiendi laskumise algoritmid tunnevad teed põhja, valides punkti ja arvutades seda ümbritseva kõvera kalde (või gradiendi), seejärel liikudes suunas, kus kalle on kõige järsem. Kujutage ette, et tunneksite end pimedas mäest alla. Te ei pruugi täpselt teada, kuhu liikuda, kui kaua peate matkama või kui lähedale merepinnale lõpuks jõuate, kuid kui suundute kõige järsemalt laskumisele, peaksite lõpuks jõudma piirkonna madalaimasse punkti.

Erinevalt metafoorsest mägironijast saavad optimeerimise uurijad programmeerida oma gradiendi laskumise algoritme, et astuda mis tahes suurusega samme. Hiiglaslikud hüpped on ahvatlevad, kuid ka riskantsed, kuna võivad vastusest ületada. Selle asemel on aastakümneid valdkonna tavapärane tarkus olnud beebisammude tegemine. Gradiendi laskumise võrrandites tähendab see sammu suurust, mis ei ole suurem kui 2, kuigi keegi ei suutnud tõestada, et väiksemad sammud olid alati paremad.

Arvutipõhise tõestustehnika arenguga on optimeerimisteoreetikud hakanud katsetama äärmuslikumaid tehnikaid. Ühes uuringus esiteks postitanud aastal 2022 ja hiljuti avaldatud in Matemaatiline programmeerimine, Das Gupta ja teised tegid arvutile ülesandeks leida parimad sammude pikkused algoritmile, mis piirdus ainult 50 sammuga. See on omamoodi meta-optimeerimise probleem, kuna see üritas optimeerimist optimeerida. Nad leidsid, et kõige optimaalsemate 50 sammu pikkus varieerus märkimisväärselt, üks samm jada keskel ulatus peaaegu pikkuseni 37, mis on palju üle tüüpilise pikkuse 2.

Tulemused viitasid sellele, et optimeerimisuurijad olid millestki kahe silma vahele jätnud. Huvitatud Grimmer püüdis muuta Das Gupta arvulised tulemused üldisemaks teoreemiks. Suvalise 50 sammu ületamiseks uuris Grimmer, millised oleksid optimaalsed sammude pikkused korduva jada jaoks, jõudes iga kordusega optimaalsele vastusele lähemale. Ta käis arvutis läbi miljoneid sammupikkuste jadade permutatsioone, aidates leida need, mis vastusele kõige kiiremini lähenesid.

Grimmer leidis, et kiirematel jadadel oli alati üks ühine joon: keskmine samm oli alati suur. Selle suurus sõltus sammude arvust korduvas järjestuses. Kolmeastmelise jada puhul oli suure sammu pikkus 4.9. 15-astmelise jada jaoks soovitas algoritm ühte sammu pikkusega 29.7. Ja 127-sammulise jada puhul, mis on pikim testitud, oli suur hüpe 370. Alguses kõlab see absurdselt suure arvuna, ütles Grimmer, kuid samme oli kokku piisavalt, et see hiiglaslik hüpe korvata. isegi kui põhjast mööda puhuksid, saaksid ikka kiiresti tagasi. Tema artikkel näitas, et see jada võib jõuda optimaalsesse punkti peaaegu kolm korda kiiremini kui pidevate beebisammudega. "Mõnikord peaksite tõesti üle pingutama," ütles ta.

See tsükliline lähenemine esindab gradiendi laskumise teistsugust mõtlemisviisi, ütles Aymeric Dieuleveut, optimeerimise uurija École Polytechnique'is Palaiseau's, Prantsusmaal. "See intuitsioon, et ma ei peaks mõtlema samm-sammult, vaid mitme järjestikuse sammuna - ma arvan, et see on midagi, mida paljud inimesed ignoreerivad," ütles ta. "See pole nii, nagu seda õpetatakse." (Grimmer märgib, et ka see ümberkujundamine oli pakutud sarnase probleemide klassi jaoks 2018. aasta magistritöös, mille autor on praegu Pennsylvania ülikooli optimeerimise uurija Jason Altschuler.)

Kuigi need teadmised võivad muuta seda, kuidas teadlased mõtlevad gradiendi laskumisele, ei muuda need tõenäoliselt seda, kuidas tehnikat praegu kasutatakse. Grimmeri paber keskendus ainult sujuvatele funktsioonidele, millel pole teravaid kõverusi, ja kumeratele funktsioonidele, mis on kausi kujulised ja millel on ainult üks optimaalne väärtus allosas. Seda tüüpi funktsioonid on teoorias põhilised, kuid praktikas vähem olulised; optimeerimisprogrammid, mida masinõppe teadlased kasutavad, on tavaliselt palju keerulisemad. Need nõuavad gradiendi laskumise versioone, millel on "nii palju kellasid ja vilesid ning nii palju nüansse," ütles Grimmer.

Mõned neist täiustatud tehnikatest võivad minna kiiremini kui Grimmeri suure sammuga lähenemisviis, ütles Gauthier Gidel, optimeerimise ja masinõppe teadur Montreali ülikoolis. Kuid need tehnikad toovad kaasa täiendavaid tegevuskulusid, seega on lootus olnud, et regulaarne laskumine kallakuga võidab õige sammusuuruste kombinatsiooniga. Kahjuks ei piisa uue uuringu kolmekordsest kiirendamisest.

"See näitab marginaalset paranemist," ütles Gidel. "Kuid ma arvan, et tõeline küsimus on: kas me saame selle lõhe tõesti kaotada?"

Tulemused tõstatavad ka täiendava teoreetilise mõistatuse, mis on Grimmerit öösel üleval hoidnud. Miks olid astmesuuruste ideaalsed mustrid nii sümmeetrilise kujuga? Ta ütles, et suurim aste ei jää alati keskele, vaid sama muster ilmub selle mõlemale küljele: jätkake suumimist ja järjestuse jagamist, ütles ta, ning saate suurematest sammudest koosneva "peaaegu fraktaalmustri", mida ümbritsevad väiksemad sammud. . Kordus viitab alusstruktuurile, mis juhib parimaid lahendusi, mida keegi pole veel suutnud selgitada. Kuid vähemalt Grimmer on lootusrikas.

"Kui mina seda lahti murda ei saa, teeb seda keegi teine," ütles ta.