Képek: Google DeepMind
Az AlphaDev nevű új rendszer megtanult három-öt számot gyorsabban rendezni, mint a korábbi csúcstechnológiás módszerek. Az algoritmusok felgyorsításával tetszőleges méretű listák például keresőmotorok, e-kereskedelmi oldalak és mások számára is rövidebb idő alatt rendezhetők.
A legtöbb programozó a szortírozó algoritmusokat magasszintű programozási nyelven, például C++-ban valósítja meg, amelyet a fordítóprogram a processzort és a memóriát kontrolláló Assembly (összeállítási) utasításokká alakít át. Egy fordító a C++ egyetlen sorát összeállítási utasítások változatos szekvenciáivá fordítja le. Funkcionalitásuk megegyezik, sebességük viszont változó. Megerősítéses tanulással működő ágens azonban megtanulhatja, hogyan válassza ki a sebességet maximalizáló fordítást.
Mire kaptak jutalmat az algoritmusok?
Az AlphaDev közösen és megerősítéses tanulással tanuló neurális hálózatok gyűjteménye. A kutatók eredetileg úgy állították be a rendszert, hogy rendezetlen számokból álló sorozatot és összeállítási utasítások üres listáját adták meg neki.
Az algoritmusokat az utasítások egyenként történő hozzáadásával hozta létre. Akkor kaptak jutalmat, amikor a számokat helyesen és gyorsan rendező utasításokat választottak.
Minden egyes kiválasztott új utasításnál egy transzformer kiszámította az utasítások addigi beágyazását, egy másik idegháló pedig az utasítások alkalmazása után a számok sorrendjének beágyazását. A rendszer összefűzte a két beágyazást, hogy megjelenítse az aktuális állapotot.
Azokat figyelembe véve, két hálózat választotta ki az utasításokat. Az első előrejelzte a jelenlegi állapotért járó teljes jövőbeli jutalmat, és kiszámolta, hogy bármely adott utasítás javít-e az algoritmuson. A második minden lehetséges utasítás hozzáadásával kiszámolta a jutalmat, és előrejelezte az eredményként kapott állapotot megjelenítő beágyazást.
Játékmodellek a való világban
A rendszer lehetséges utasításszekvenciákon keresztül igyekezett rájönni, hogy melyik utasítás vezetett leggyakrabban a legmagasabb előrejelzett jutalmakhoz, majd az utasítást hozzáadta az algoritmushoz.
Mihelyst kidolgozott egy algoritmust, a fejlesztők feltöltötték a több mint egy évtizede nem frissített központi C++ könyvtárba. Az így kapott algoritmusok most nyílt forráskódú szubrutinokként funkcionálnak a C++ alapértelmezett szortírozó algoritmusában.
A rendszert többször tesztelték, az eredmények kifejezetten jók. Munkájukkal a kutatók a játékmodellek, például az AlphaZero tréningmódszerét és architektúráját valóvilágbeli problémák megoldására használják. A nóvum, hogy szortírozó algoritmusok írását megerősítéses tanulási feladatként definiálták újra.
