Az AI új lehetőségeket tár fel a mátrixszorzásban

A matematikusok szeretik a jó rejtvényeket. Még az olyan elvont dolgok is, mint a szorzómátrixok (kétdimenziós számtáblák), játéknak tűnhetnek, ha megpróbáljuk megtalálni ennek leghatékonyabb módját. Kicsit olyan, mintha a Rubik-kockát a lehető legkevesebb mozdulattal próbálnánk megoldani – kihívást jelent, de csábító. Kivéve, hogy egy Rubik-kocka esetében a lehetséges lépések száma lépésenként 18; mátrixszorzásnál még viszonylag egyszerű esetekben is minden lépés 10-nél többet mutathat¹² lehetőségeket.

Az elmúlt 50 év során a kutatók sokféleképpen közelítették meg ezt a problémát, mindezt az emberi intuíció által támogatott számítógépes keresések alapján. A múlt hónapban a DeepMind mesterséges intelligenciával foglalkozó cég egyik csapata megmutatta, hogyan lehet új irányból kezelni a problémát, és beszámolt egy papír in Természet hogy sikeresen betanítottak egy neurális hálózatot új, gyors mátrixszorzási algoritmusok felfedezésére. Mintha az AI ismeretlen stratégiát talált volna egy szörnyen bonyolult Rubik-kocka megoldására.

„Nagyon szép eredmény” – mondta Josh Alman, a Columbia Egyetem informatikusa. De ő és más mátrixszorzási szakértők azt is hangsúlyozták, hogy az AI-segély inkább kiegészíti, mintsem helyettesíti a meglévő módszereket – legalábbis a közeljövőben. „Olyan ez, mint valami olyan koncepció bizonyítéka, ami áttörést jelenthet” – mondta Alman. Az eredmény egyszerűen segíti a kutatókat a kutatásban.

Mintha bizonyítani akarná a lényeget, három nappal azután, hogy Természet papír jelent meg, osztrák kutatópáros szemléltette, hogyan egészíthetik ki egymást az új és a régi módszerek. Hagyományos számítógépes keresést alkalmaztak tovább javítani az egyik algoritmus, amelyet a neurális hálózat fedezett fel.

Az eredmények arra utalnak, hogy a Rubik-kocka megoldásához hasonlóan a jobb algoritmusokhoz vezető út is tele lesz fordulatokkal.

Mátrixok szorzása

A mátrixszorzás az egyik legalapvetőbb és mindenütt megtalálható művelet az egész matematikában. Egy pár szorozásához n-által-n mátrixok, mindegyik n² elemeket, ezeket az elemeket össze kell szorozni és összeadni bizonyos kombinációkban a termék előállításához, egy harmadikat n-által-n mátrix. A standard recept a kettő szorzásához n-által-n mátrixok megkövetelik n³ szorzási műveletek, így például egy 2-szeres mátrixhoz nyolc szorzás szükséges.

Nagyobb, több ezer sorból és oszlopból álló mátrixok esetén ez a folyamat gyorsan nehézkessé válik. De 1969-ben a matematikus Volker Strassen eljárást fedezett fel egy 2-szeres mátrix pár szorzásához nyolc helyett hét szorzási lépéssel, további összeadási lépések bevezetése árán.

Strassen algoritmusa szükségtelenül bonyolult, ha csak egy 2-szeres mátrixpárt akarunk szorozni. De rájött, hogy ez nagyobb mátrixoknál is működne. Ennek az az oka, hogy a mátrix elemei maguk is mátrixok lehetnek. Például egy 2 20,000 sorból és 20,000 2 oszlopból álló mátrix újragondolható 2 x 10,000 mátrixként, amelynek négy eleme egyenként 10,000 5,000 x 5,000 2 mátrix. Ezeknek a mátrixoknak mindegyike négy 2 x XNUMX blokkra osztható, és így tovább. Strassen alkalmazhatja módszerét XNUMX-XNUMX mátrixok szorzására ennek a beágyazott hierarchiának minden szintjén. A mátrix méretének növekedésével a kevesebb szorzásból származó megtakarítás nő.

Strassen felfedezése eredményeként hatékony algoritmusokat keresett a mátrixszorzáshoz, amely azóta két különálló részterületet inspirált. Az egyik egy elvi kérdésre összpontosít: Ha elképzeled, hogy kettőt szorozunk n-által-n mátrixok és hagyjuk n fut a végtelen felé, hogyan skálázódik a szorzási lépések száma a lehető leggyorsabb algoritmusban n? A aktuális rekord a legjobb méretezés érdekében, n^2.3728596, Almanhoz tartozik és Virginia Vassilevska Williams, a Massachusetts Institute of Technology informatikusa. (A közelmúltban kiadatlan előnyomtatás apró javulásról számolt be egy új technikával.) De ezek az algoritmusok pusztán elméleti érdeklődésre tartanak számot, és csak abszurd nagy mátrixok esetén győzik le az olyan módszereket, mint a Strassen-féle.

A második részterület kisebb léptékben gondolkodik. Nem sokkal Strassen munkája után az izraeli amerikai informatikus, Shmuel Winograd kimutatta, hogy Strassen elért egy elméleti határt: Nem lehet 2-2 mátrixot szorozni hétnél kevesebb szorzási lépéssel. De az összes többi mátrixméret esetében a szükséges szorzások minimális száma nyitott kérdés marad. A kis mátrixok gyors algoritmusainak pedig túlméretezett hatása lehet, mivel az ilyen algoritmusok ismételt iterációi felülmúlhatják Strassen algoritmusát, amikor ésszerű méretű mátrixokat szoroznak.

Sajnos a lehetőségek száma óriási. Még a 3x3 mátrixok esetében is „a lehetséges algoritmusok száma meghaladja az univerzum atomjainak számát” – mondta. Alhussein Fawzi, a DeepMind kutatója és az új munka egyik vezetője.

A lehetőségek e szédítő menüjével szembesülve a kutatók előrehaladást értek el a mátrixszorzás átalakításával egy teljesen más matematikai feladattá, amelyet a számítógépek könnyebben kezelhetnek. A két mátrix szorzásának absztrakt feladatát egy bizonyos típusú matematikai objektumként ábrázolhatjuk: egy háromdimenziós számtömbként, amelyet tenzornak neveznek. A kutatók ezután ezt a tenzort elemi komponensek összegére bonthatják fel, amelyeket „rang-1” tenzoroknak neveznek; ezek mindegyike más-más lépést képvisel a megfelelő mátrixszorzó algoritmusban. Ez azt jelenti, hogy egy hatékony szorzóalgoritmus megtalálása azt jelenti, hogy minimalizáljuk a tagok számát a tenzorbontásban – minél kevesebb tag, annál kevesebb lépésre van szükség.

Ily módon a kutatók újat fedeztek fel algoritmusok hogy szaporodnak n-által-n a szabványnál kevesebbet használó mátrixokat n³ szorzási lépések sok kis mátrixmérethez. De azok az algoritmusok, amelyek nem csak a szabványos, hanem a Strassen-féle kis mátrixok algoritmusát is felülmúlják, elérhetetlenek maradtak – egészen mostanáig.

Kezdődjön a játék

A DeepMind csapata úgy közelítette meg a problémát, hogy a tenzorbontást egyjátékossá alakította. Egy mély tanulási algoritmussal kezdték, amely az AlphaGo leszármazottja – egy másik DeepMind AI, amely 2016-ban megtanult játszani a Go társasjátékkal elég jól ahhoz, hogy legyőzze a legjobb emberi játékosokat.

Minden mélytanulási algoritmus neurális hálózatok köré épül: mesterséges neuronok rétegeibe rendezett hálói, amelyek erőssége változó lehet, és azt jelzi, hogy az egyes neuronok mennyire befolyásolják a következő rétegben lévőket. Ezeknek a kapcsolatoknak az erőssége egy betanítási eljárás számos iterációja során módosítható, amelyek során a neurális hálózat megtanulja, hogy minden egyes bemenetet olyan kimenetté alakítson át, amely segít az algoritmusnak elérni általános célját.

A DeepMind új, AlphaTensor nevű algoritmusában a bemenetek az érvényes mátrixszorzási séma felé vezető lépéseket jelentik. A neurális hálózat első bemenete az eredeti mátrixszorzó tenzor, kimenete pedig az 1. rangú tenzor, amelyet az AlphaTensor az első lépéshez választott. Az algoritmus kivonja ezt az 1. rangú tenzort a kezdeti bemenetből, így egy frissített tenzort kap, amely új bemenetként visszakerül a hálózatba. A folyamat addig ismétlődik, amíg végül a kezdő tenzor minden eleme nullára csökken, ami azt jelenti, hogy nincs több 1. rangú tenzor, amelyet ki kell venni.

Ezen a ponton a neurális hálózat egy érvényes tenzorbontást fedezett fel, mivel matematikailag garantált, hogy az összes rang-1 tenzor összege pontosan megegyezik a kezdő tenzorral. Az odáig tartó lépések pedig visszafordíthatók a megfelelő mátrixszorzó algoritmus lépéseire.

Íme a játék: Az AlphaTensor ismételten lebontja a tenzort az 1. rangú összetevők halmazára. Az AlphaTensor minden alkalommal jutalmat kap, ha módot talál a lépések számának csökkentésére. De a győzelemhez vezető utak egyáltalán nem intuitívak, mint ahogy néha egy tökéletesen rendezett arcot is össze kell keverni a Rubik-kockán, mielőtt az egészet megoldhatná.

A csapatnak most volt egy algoritmusa, amely elméletileg meg tudta oldani a problémát. Csak először ki kellett képezniük.

Új utak

Mint minden neurális hálózatnak, az AlphaTensornak is sok adatra van szüksége a képzéshez, de a tenzorbontás köztudottan nehéz probléma. Kevés olyan hatékony lebontásra volt példa, amelyet a kutatók táplálni tudtak a hálózatban. Ehelyett segítettek az algoritmus beindulásában azzal, hogy megtanították a sokkal egyszerűbb inverz problémára: összeadtak egy csomó véletlenszerűen generált 1. rangú tenzort.

„Az egyszerű problémát arra használják, hogy több adatot állítsanak elő a nehéz problémához” – mondta Michael Littman, a Brown Egyetem informatikusa. Ennek a visszafelé történő képzési eljárásnak a megerősítő tanulással való kombinálása, amelyben az AlphaTensor saját képzési adatait generálta, miközben hatékony dekompozíciókat keresett, sokkal jobban működött, mint bármelyik képzési módszer önmagában.

A DeepMind csapata kiképezte az AlphaTensort, hogy bontsa le a mátrixok 12-szeres szorzását reprezentáló tenzorokat. Gyors algoritmusokat keresett a közönséges valós számok mátrixainak szorzására, valamint olyan algoritmusokat, amelyek a modulo 12 aritmetika néven ismert, korlátozottabb beállításhoz specifikusak. (Ez csak két számon alapuló matematika, tehát a mátrixelemek csak 2 vagy 0 lehetnek, és 1 + 1 = 1.) A kutatók gyakran ebből a szűkebb, de még mindig hatalmas térből indulnak ki, abban a reményben, hogy az itt felfedezett algoritmusok adaptálhatók dolgozzunk valós számok mátrixain.

Edzés után az AlphaTensor perceken belül újra felfedezte Strassen algoritmusát. Ezután akár több ezer új gyors algoritmust fedezett fel minden mátrixmérethez. Ezek különböztek a legismertebb algoritmusoktól, de ugyanannyi szorzási lépést tartalmaztak.

Néhány esetben az AlphaTensor a meglévő rekordokat is megdöntötte. A legmeglepőbb felfedezései a modulo 2 aritmetikában történtek, ahol új algoritmust talált a 4-4 mátrixok 47 szorzási lépésben történő szorzására, ami jobb a Strassen-algoritmus két iterációjához szükséges 49 lépéshez képest. Megverte az 5x5 modulo 2 mátrixok legismertebb algoritmusát is, így a szükséges szorzások számát a korábbi 98-ról 96-ra csökkentette. (Ez az új rekord azonban még mindig elmarad a legyőzéséhez szükséges 91 lépéstől. Strassen algoritmusa 5x5 mátrixok használatával.)

Az új, nagy horderejű eredmény sok izgalmat keltett néhány kutató halmozott dicséret a mesterséges intelligencia alapú javulása a status quo. A mátrixszorzó közösségben azonban nem mindenkit nyűgözött le ennyire. „Úgy éreztem, egy kicsit túlzásba vitték” – mondta Vassilevska Williams. „Ez egy másik eszköz. Ez nem olyan, hogy „Ó, a számítógépek legyőzik az embereket”, tudod?

A kutatók azt is hangsúlyozták, hogy a rekordot döntõ 4-szeres algoritmus azonnali alkalmazása korlátozott lesz: nemcsak a modulo 4 aritmetikában érvényes, de a való életben a sebesség mellett fontos szempontok is vannak.

Fawzi egyetértett abban, hogy valójában ez csak a kezdet. „Rengeteg tere van a fejlesztésre és a kutatásra, és ez jó dolog” – mondta.

Egy utolsó csavar

Az AlphaTensor legnagyobb erőssége a jól bevált számítógépes keresési módszerekhez képest egyben a legnagyobb gyengesége is: nem korlátozza az emberi megérzés a jó algoritmusok megjelenésével kapcsolatban, így nem tudja megmagyarázni a választásait. Ez megnehezíti a kutatók számára, hogy tanuljanak az eredményeiből.

De ez nem lehet olyan nagy hátrány, mint amilyennek látszik. Néhány nappal az AlphaTensor eredmény után a matematikus Manuel Kauers és végzős hallgatója Jakob Moosbauer, mindketten az ausztriai Linzi Johannes Kepler Egyetem munkatársai újabb előrelépésről számoltak be.

Amikor a DeepMind papír megjelent, Kauers és Moosbauer éppen új szorzási algoritmusokat keresett egy hagyományos számítógépes keresés segítségével. De ellentétben a legtöbb ilyen kereséssel, amelyek egy új vezérelvvel kezdődnek, a módszerük úgy működik, hogy ismételten módosít egy meglévő algoritmust, abban a reményben, hogy további szorzási megtakarításokat tud kiszorítani belőle. Az AlphaTensor 5x5 modulo 2 mátrixokra vonatkozó algoritmusát véve kiindulópontnak, meglepődve tapasztalták, hogy módszerük néhány másodperces számítás után 96-ról 95-re csökkentette a szorzási lépések számát.

Az AlphaTensor közvetett módon is segített nekik egy újabb fejlesztésben. Korábban Kauers és Moosbauer nem foglalkozott a 4-szeres mátrixok terének feltárásával, mert azt hitték, hogy a Strassen-algoritmus két iterációját nem lehet legyőzni. Az AlphaTensor eredménye újragondolásra késztette őket, és egy hét elölről induló számítási idő után módszerük egy másik, 4 lépésből álló algoritmust talált ki, amely nem volt kapcsolatban az AlphaTensor által felfedezett algoritmussal. „Ha valaki azt mondta volna nekünk, hogy van mit felfedezni négyszeresben, megtehettük volna korábban is” – mondta Kauers. – De jó, ez így működik.

Littman még több ilyen meglepetésre számít, és ahhoz hasonlítja a helyzetet, amikor egy futó négy perc alatt ért el egy mérföldet, amit széles körben lehetetlennek tartottak. „Az emberek azt mondták: „Ó, várj, meg tudjuk csinálni”, és most sokan megtehetik” – mondta.

A jövőre nézve Fawzi azt reméli, hogy általánosítani tudja az AlphaTensort, hogy matematikai és számítási feladatok szélesebb körét tudjon megoldani, ahogyan az AlphaGo őse is más játékokba ágazott.

Kauers ezt tekinti az igazi lakmusz tesztnek a gépi tanulás új algoritmusok felfedezésére való alkalmazásához. Rámutat arra, hogy a gyors mátrixszorzó algoritmusok keresése olyan kombinatorikus probléma, amelyre a számítógépes keresés, emberi segítséggel vagy anélkül, jól alkalmazható. De nem minden matematikai feladatot olyan könnyű leszögezni. Ha a gépi tanulás képes felfedezni egy minőségileg új algoritmikus ötletet, akkor „az a játék megváltoztatja” – mondta.