Kockázatos óriási lépések gyorsabban megoldhatják az optimalizálási problémákat | Quanta Magazin

Az optimalizálási problémák bonyolultak lehetnek, de jobbá teszik a világot. Az ilyen kérdések, amelyek valaminek a legjobb módjára törekednek, abszolút mindenhol megtalálhatók. A telefon GPS-je kiszámítja a legrövidebb utat az úticélhoz. Az utazási webhelyek az útvonalának megfelelő legolcsóbb járatkombinációt keresik. A gépi tanulási alkalmazások pedig, amelyek az adatok mintáinak elemzésével tanulnak, igyekeznek a legpontosabb és legemberibb válaszokat adni az adott kérdésre.

Az egyszerű optimalizálási feladatoknál a legjobb megoldás megtalálása csak aritmetika kérdése. De a matematikusokat és tudósokat érdeklő valós kérdések ritkán egyszerűek. 1847-ben a francia matematikus, Augustin-Louis Cauchy egy kellően bonyolult példán – csillagászati ​​számításokon – dolgozott, amikor úttörőként dolgozott egy általános optimalizálási módszeren, amelyet ma gradiens süllyedésként ismernek. A legtöbb gépi tanulási program manapság nagymértékben támaszkodik a technikára, és más területek is használják adatok elemzésére és mérnöki problémák megoldására.

A matematikusok több mint 150 éve tökéletesítik a gradiens süllyedést, de a múlt hónapban Egy tanulmány bebizonyította, hogy a technikával kapcsolatos alapfeltevés téves lehet. „Csak néhányszor meglepődtem, [mintha] megtört az intuícióm” – mondta Ben Grimmer, a Johns Hopkins Egyetem alkalmazott matematikusa és a tanulmány egyetlen szerzője. Ellentétes eredményei azt mutatták, hogy a gradiens süllyedés közel háromszor gyorsabban működhet, ha megszegi azt a régóta elfogadott szabályt, hogy hogyan találjuk meg a legjobb választ egy adott kérdésre. Noha az elméleti előrelépés valószínűleg nem vonatkozik a gépi tanulás által kezelt súlyosabb problémákra, a kutatókat arra késztette, hogy újragondolják, mit tudnak a technikáról.

„Kiderült, hogy nem értettük meg teljesen” a gradiens süllyedés mögötti elméletet – mondta Shuvomoy Das Gupta, a Massachusetts Institute of Technology optimalizálási kutatója. Most, mondta, „közelebb vagyunk ahhoz, hogy megértsük, mit csinál a gradiens süllyedés”.

Maga a technika megtévesztően egyszerű. Valami költségfüggvényt használ, amely úgy néz ki, mint egy sima, görbe vonal, amely fel-le kanyarodik a grafikonon. A vonal bármely pontján a magasság valamilyen módon költséget jelent – ​​mennyi időt, energiát vagy hibát jelent a művelet, ha egy adott beállításra hangolják. Minél magasabb a pont, annál távolabb van a rendszer az ideálistól. Természetesen ezen a vonalon szeretné megtalálni a legalacsonyabb pontot, ahol a legkisebb a költség.

A gradiens süllyedés algoritmusai úgy érzik az utat a mélyre, hogy kiválasztanak egy pontot, és kiszámítják a körülötte lévő görbe meredekségét (vagy gradiensét), majd abba az irányba mozognak, ahol a lejtő a legmeredekebb. Képzelje el ezt úgy, mintha a sötétben lefelé haladna egy hegyről. Előfordulhat, hogy nem tudja pontosan, hova kell költöznie, mennyi ideig kell túráznia, vagy milyen közel kerül a tengerszinthez, de ha a legélesebb lejtőn halad le, végül meg kell érkeznie a terület legalacsonyabb pontjára.

A metaforikus hegymászóval ellentétben az optimalizálás kutatói be tudják programozni a gradiens süllyedés algoritmusait, hogy bármilyen méretű lépést tegyenek. Az óriási ugrások csábítóak, de kockázatosak is, mivel túlszárnyalhatják a választ. Ehelyett a terület hagyományos bölcsessége évtizedek óta a babalépések megtétele volt. A gradiens süllyedési egyenletekben ez 2-nél nem nagyobb lépést jelent, bár senki sem tudta bizonyítani, hogy a kisebb lépések mindig jobbak voltak.

A számítógéppel segített bizonyítási technikák fejlődésével az optimalizálási teoretikusok extrémebb technikákat kezdtek tesztelni. Egy tanulmányban először kiküldött A 2022 és nemrégiben megjelent in Matematikai programozás, Das Gupta és mások megbíztak egy számítógépet, hogy találja meg a legjobb lépéshosszokat egy mindössze 50 lépésre korlátozódó algoritmushoz – ez egyfajta metaoptimalizálási probléma, mivel az optimalizálást próbálta optimalizálni. Azt találták, hogy a legoptimálisabb 50 lépés hossza szignifikánsan változott, a sorozat közepén egy lépés közel elérte a 37-es hosszt, ami messze meghaladja a tipikus 2-es hosszt.

Az eredmények azt sugallták, hogy az optimalizálás kutatói valamit kihagytak. Érdekelt Grimmer arra törekedett, hogy Das Gupta numerikus eredményeit egy általánosabb tétellé alakítsa. Ahhoz, hogy túllépjen egy tetszőleges, 50 lépésből álló felső határon, Grimmer megvizsgálta, mi lenne az optimális lépéshossz egy olyan sorozathoz, amely ismétlődik, és minden ismétléssel közelebb kerül az optimális válaszhoz. Végigfuttatta a számítógépet a lépéshosszúságú sorozatok millióinak permutációján, így segített megtalálni azokat, amelyek a leggyorsabban konvergáltak a válaszhoz.

Grimmer úgy találta, hogy a leggyorsabb sorozatokban mindig volt egy közös vonás: a középső lépés mindig nagy volt. Mérete az ismétlődő sorozat lépéseinek számától függött. Egy háromlépéses sorozatnál a nagy lépés hossza 4.9 volt. Egy 15 lépésből álló sorozathoz az algoritmus egy 29.7 hosszúságú lépést javasolt. Egy 127 lépésből álló sorozatnál pedig, a leghosszabb tesztelt, a nagy központi ugrás óriási 370 volt. Elsőre ez abszurd nagy számnak hangzik, mondta Grimmer, de volt elég lépés az óriási ugrás ellensúlyozására. még ha túl is fújnál az alján, akkor is gyorsan vissza tudna jutni. Tanulmánya kimutatta, hogy ez a sorozat közel háromszor gyorsabban tud eljutni az optimális ponthoz, mint állandó babalépésekkel. „Néha tényleg túl kell vállalni” – mondta.

Ez a ciklikus megközelítés a gradiens származás másfajta gondolkodásmódját képviseli, mondta Aymeric Dieuleveut, a franciaországi Palaiseau-i École Polytechnique optimalizálási kutatója. „Ezt az intuíciót, hogy ne lépésről lépésre, hanem több egymást követő lépésben kell gondolkodnom – azt hiszem, ezt sokan figyelmen kívül hagyják” – mondta. – Nem így tanítják. (Grimmer megjegyzi, hogy ez az átkeretezés is az volt javasolt egy hasonló problémakörhöz Jason Altschuler, jelenleg a Pennsylvaniai Egyetem optimalizálási kutatója 2018-as mesterdolgozatában.)

Bár ezek a felismerések megváltoztathatják a kutatók gondolkodását a gradiens süllyedésről, valószínűleg nem változtatják meg a technika jelenlegi alkalmazását. A Grimmer papírja csak a sima funkciókra összpontosított, amelyeknek nincs éles hajlása, és a konvex függvényekre, amelyek tál alakúak, és csak egy optimális értékük van az alján. Az ilyen típusú függvények alapvetőek az elméletben, de kevésbé relevánsak a gyakorlatban; a gépi tanulással foglalkozó kutatók által használt optimalizálási programok általában sokkal bonyolultabbak. Ezekhez a gradiens süllyedés olyan verzióira van szükségük, amelyekben „annyi csengő és síp, és annyi árnyalat van” – mondta Grimmer.

Ezeknek a kifinomult technikáknak némelyike ​​gyorsabban megy, mint Grimmer nagy lépésű megközelítése, mondta Gauthier Gidel, a Montreali Egyetem optimalizálási és gépi tanulási kutatója. Ezek a technikák azonban további üzemeltetési költségekkel járnak, így a remény az volt, hogy a szabályos lejtős ereszkedés győzni fog a lépésméretek megfelelő kombinációjával. Sajnos az új tanulmány háromszoros gyorsítása nem elég.

„Ez marginális javulást mutat” – mondta Gidel. „De azt hiszem, az igazi kérdés az: valóban be tudjuk-e zárni ezt a szakadékot?”

Az eredmények egy további elméleti rejtélyt is felvetnek, amely Griimmert éjjel is ébren tartotta. Miért volt a lépcsőméretek ideális mintái mind olyan szimmetrikus alakúak? Nemcsak a legnagyobb lépés van mindig a közepén, hanem ugyanaz a minta jelenik meg mindkét oldalán: Ha tovább nagyít, és felosztja a sorozatot, mondta, akkor egy „majdnem fraktálmintát” kapsz nagyobb lépésekből, amelyeket kisebb lépések vesznek körül. . Az ismétlés a legjobb megoldásokat irányító mögöttes struktúrát sugallja, amelyet még senkinek nem sikerült megmagyaráznia. De Grimmer legalább reménykedik.

„Ha én nem tudom feltörni, akkor valaki más megteszi” – mondta.