Risikable kæmpetrin kan løse optimeringsproblemer hurtigere | Quanta Magasinet

Optimeringsproblemer kan være vanskelige, men de får verden til at fungere bedre. Den slags spørgsmål, som stræber efter den bedste måde at gøre noget på, er absolut overalt. Din telefons GPS beregner den korteste rute til din destination. Rejsewebsteder søger efter den billigste kombination af fly, der matcher din rejseplan. Og maskinlæringsapplikationer, som lærer ved at analysere mønstre i data, forsøger at præsentere de mest nøjagtige og menneskelignende svar på ethvert givet spørgsmål.

For simple optimeringsproblemer er det kun et spørgsmål om aritmetik at finde den bedste løsning. Men de spørgsmål i den virkelige verden, som interesserer matematikere og videnskabsmænd, er sjældent enkle. I 1847 arbejdede den franske matematiker Augustin-Louis Cauchy på et passende kompliceret eksempel - astronomiske beregninger - da han var pioner for en almindelig optimeringsmetode, der nu er kendt som gradientnedstigning. De fleste maskinlæringsprogrammer i dag er stærkt afhængige af teknikken, og andre felter bruger den også til at analysere data og løse tekniske problemer.

Matematikere har perfektioneret gradientnedstigning i over 150 år, men i sidste måned, et studie bevist, at en grundlæggende antagelse om teknikken kan være forkert. "Der var bare flere gange, hvor jeg blev overrasket, [som] min intuition er brudt," sagde Ben Grimmer, en anvendt matematiker ved Johns Hopkins University og undersøgelsens eneste forfatter. Hans kontraintuitive resultater viste, at gradientnedstigning kan arbejde næsten tre gange hurtigere, hvis det bryder en længe accepteret regel for, hvordan man finder det bedste svar til et givet spørgsmål. Selvom det teoretiske fremskridt sandsynligvis ikke gælder for de mere grovere problemer, der håndteres af maskinlæring, har det fået forskere til at genoverveje, hvad de ved om teknikken.

"Det viser sig, at vi ikke havde fuld forståelse" af teorien bag gradientnedstigning, sagde Shuvomoy Das Gupta, en optimeringsforsker ved Massachusetts Institute of Technology. Nu, sagde han, er vi "tættere på at forstå, hvad gradientnedstigning gør."

Selve teknikken er vildledende enkel. Den bruger noget, der kaldes en omkostningsfunktion, som ligner en glat, buet linje, der bugter sig op og ned over en graf. For ethvert punkt på den linje repræsenterer højden omkostninger på en eller anden måde - hvor meget tid, energi eller fejl operationen vil medføre, når den er indstillet til en specifik indstilling. Jo højere punkt, jo længere fra ideelt er systemet. Naturligvis vil du gerne finde det laveste punkt på denne linje, hvor omkostningerne er mindst.

Gradient-nedstigningsalgoritmer føler sig vej til bunden ved at vælge et punkt og beregne hældningen (eller gradienten) af kurven omkring det, og derefter bevæge sig i den retning, hvor hældningen er stejlest. Forestil dig dette som at føle dig ned ad et bjerg i mørket. Du ved måske ikke præcist, hvor du skal bevæge dig, hvor længe du skal vandre, eller hvor tæt på havoverfladen du i sidste ende vil komme, men hvis du går ned ad den skarpeste nedstigning, bør du til sidst nå frem til det laveste punkt i området.

I modsætning til den metaforiske bjergbestiger kan optimeringsforskere programmere deres gradientnedstigningsalgoritmer til at tage skridt af enhver størrelse. Kæmpespring er fristende, men også risikable, da de kan overskride svaret. I stedet har feltets konventionelle visdom i årtier været at tage små skridt. I gradient-nedstigningsligninger betyder dette en trinstørrelse, der ikke er større end 2, selvom ingen kunne bevise, at mindre trinstørrelser altid var bedre.

Med fremskridt inden for computerstøttede bevisteknikker er optimeringsteoretikere begyndt at teste mere ekstreme teknikker. I en undersøgelse, først indsendt i 2022 og for nylig offentliggjort in Matematisk programmering, Das Gupta og andre gav en computer til opgave at finde de bedste trinlængder for en algoritme, der er begrænset til kun at køre 50 trin - en slags metaoptimeringsproblem, da den forsøgte at optimere optimering. De fandt ud af, at de mest optimale 50 trin varierede betydeligt i længden, hvor et trin i midten af ​​sekvensen nåede næsten til længden 37, langt over den typiske hætte med længde 2.

Resultaterne tydede på, at optimeringsforskere var gået glip af noget. Interessant søgte Grimmer at gøre Das Guptas numeriske resultater til en mere generel teorem. For at komme forbi en vilkårlig grænse på 50 trin, udforskede Grimmer, hvad de optimale trinlængder ville være for en sekvens, der kunne gentages, og komme tættere på det optimale svar for hver gentagelse. Han kørte computeren gennem millioner af permutationer af trinlængdesekvenser, og hjalp med at finde dem, der konvergerede til svaret hurtigst.

Grimmer fandt ud af, at de hurtigste sekvenser altid havde én ting til fælles: Mellemtrinnet var altid stort. Dens størrelse afhang af antallet af trin i den gentagne sekvens. For en sekvens med tre trin havde det store trin en længde på 4.9. For en 15-trins sekvens anbefalede algoritmen et trin med en længde på 29.7. Og for en sekvens på 127 trin, den længste testede, var det store centrale spring hele 370. I starten lyder det som et absurd stort tal, sagde Grimmer, men der var trin nok til at kompensere for det gigantiske spring, så selvom du blæste forbi bunden, kunne du stadig komme hurtigt tilbage. Hans papir viste, at denne sekvens kan nå det optimale punkt næsten tre gange hurtigere, end den ville ved at tage konstante små skridt. "Nogle gange burde man virkelig overcommitte," sagde han.

Denne cykliske tilgang repræsenterer en anden måde at tænke på gradientnedstigning, sagde Aymeric Dieuleveut, en optimeringsforsker ved École Polytechnique i Palaiseau, Frankrig. "Denne intuition, at jeg ikke skal tænke trin for trin, men som et antal trin i træk - jeg tror, ​​det er noget, som mange mennesker ignorerer," sagde han. "Det er ikke sådan, det er undervist." (Grimmer bemærker, at denne reframing også var foreslog for en lignende klasse af problemer i en kandidatafhandling fra 2018 af Jason Altschuler, en optimeringsforsker nu ved University of Pennsylvania.)

Men selvom disse indsigter kan ændre, hvordan forskere tænker på gradientnedstigning, vil de sandsynligvis ikke ændre, hvordan teknikken bruges i øjeblikket. Grimmers papir fokuserede kun på glatte funktioner, som ikke har skarpe knæk, og konvekse funktioner, der er formet som en skål og kun har én optimal værdi i bunden. Den slags funktioner er grundlæggende for teori, men mindre relevante i praksis; de optimeringsprogrammer, maskinlæringsforskere bruger, er normalt meget mere komplicerede. Disse kræver versioner af gradientnedstigning, der har "så mange klokker og fløjter og så mange nuancer," sagde Grimmer.

Nogle af disse supped-up teknikker kan gå hurtigere end Grimmers store trin tilgang, sagde Gauthier Gidel, en optimerings- og maskinlæringsforsker ved University of Montreal. Men disse teknikker har en ekstra driftsomkostning, så håbet har været, at regelmæssig gradientnedstigning kunne vinde frem med den rigtige kombination af trinstørrelser. Desværre er den nye undersøgelses tredobbelte speedup ikke nok.

"Det viser en marginal forbedring," sagde Gidel. "Men jeg gætter på, at det virkelige spørgsmål er: Kan vi virkelig lukke dette hul?"

Resultaterne rejser også et yderligere teoretisk mysterium, der har holdt Grimmer vågen om natten. Hvorfor havde de ideelle mønstre af trinstørrelser alle sådan en symmetrisk form? Ikke alene er det største trin altid i midten, men det samme mønster vises på begge sider af det: Bliv ved med at zoome ind og underinddele sekvensen, sagde han, og du får et "næsten fraktalt mønster" af større trin omgivet af mindre trin . Gentagelsen antyder en underliggende struktur, der styrer de bedste løsninger, som ingen endnu har formået at forklare. Men Grimmer er i det mindste håbefuld.

"Hvis jeg ikke kan knække det, vil en anden," sagde han.