AI razkriva nove možnosti pri množenju matrik

Matematiki imajo radi dobro uganko. Celo nekaj tako abstraktnega, kot je množenje matrik (dvodimenzionalnih tabel števil), se lahko zdi kot igra, ko poskušate najti najučinkovitejši način za to. Podobno je, kot če bi poskušali zložiti Rubikovo kocko v čim manj potezah – zahtevno, a privlačno. Le da je pri Rubikovi kocki število možnih potez na vsakem koraku 18; za matrično množenje lahko tudi v razmeroma preprostih primerih vsak korak predstavlja več kot 10¹² opcije.

V zadnjih 50 letih so se raziskovalci tega problema lotili na številne načine, vse pa so temeljili na računalniških iskanjih s pomočjo človeške intuicije. Prejšnji mesec je ekipa podjetja za umetno inteligenco DeepMind pokazala, kako se problema lotiti iz nove smeri, in poročala v papirja in Narava da so uspešno usposobili nevronsko mrežo za odkrivanje novih hitrih algoritmov za množenje matrik. Bilo je, kot da je umetna inteligenca našla neznano strategijo za reševanje pošastno zapletene Rubikove kocke.

"To je zelo lep rezultat," je rekel Josh Alman, računalniški znanstvenik na univerzi Columbia. Toda on in drugi strokovnjaki za množenje matrik so tudi poudarili, da bo taka pomoč z umetno inteligenco dopolnila in ne nadomestila obstoječih metod - vsaj v bližnji prihodnosti. "To je kot dokaz koncepta za nekaj, kar bi lahko postalo preboj," je dejal Alman. Rezultat bo preprosto pomagal raziskovalcem pri njihovem iskanju.

Kot v dokaz, tri dni po Narava izšel članek, sta dva avstrijska raziskovalca prikazala, kako se lahko nove in stare metode dopolnjujejo. Uporabili so običajno računalniško podprto iskanje še izboljšati eden od algoritmov, ki jih je odkrila nevronska mreža.

Rezultati kažejo, da bo, tako kot postopek reševanja Rubikove kocke, tudi pot do boljših algoritmov polna preobratov.

Množenje matrik

Matrično množenje je ena najbolj temeljnih in vseprisotnih operacij v vsej matematiki. Če želite pomnožiti par n-z-n matrice, vsaka s n² elemente, te elemente pomnožite in seštejete v določenih kombinacijah, da ustvarite izdelek, tretjino n-z-n matrica. Standardni recept za množenje dveh n-z-n matrice zahteva n³ operacije množenja, zato matrika 2 krat 2 na primer zahteva osem množenj.

Pri večjih matrikah s tisoči vrstic in stolpcev ta postopek hitro postane okoren. Toda leta 1969 je matematik Volker Strassen odkril postopek za množenje para matrik 2 krat 2 z uporabo sedmih namesto osmih korakov množenja, za ceno uvedbe več korakov seštevanja.

Strassenov algoritem je po nepotrebnem zapleten, če želite samo pomnožiti par matrik 2 na 2. Vendar je ugotovil, da bi delovalo tudi za večje matrice. To je zato, ker so lahko elementi matrike sami matrike. Na primer, matriko z 20,000 vrsticami in 20,000 stolpci je mogoče ponovno zamisliti kot matriko 2 krat 2, katere štirje elementi so vsak matrika 10,000 krat 10,000. Vsako od teh matrik lahko nato razdelimo na štiri bloke velikosti 5,000 krat 5,000 in tako naprej. Strassen bi lahko uporabil svojo metodo za množenje matrik 2 na 2 na vsaki ravni te ugnezdene hierarhije. Ko se velikost matrike poveča, se povečajo prihranki zaradi manj množitev.

Strassenovo odkritje je pripeljalo do iskanja učinkovitih algoritmov za množenje matrik, kar je od takrat navdihnilo dve različni podpolji. Eden se osredotoča na načelno vprašanje: če si predstavljate, da pomnožite dva n-z-n matrice in pustimo n teči proti neskončnosti, kako se število korakov množenja v najhitrejšem možnem algoritmu meri z n? trenutni zapis za najboljše skaliranje, n^2.3728596, pripada Almanu in Virginia Vassilevska Williams, računalničar na tehnološkem inštitutu Massachusetts. (Nedavno neobjavljeno predtisk je poročal o majhnem izboljšanju z uporabo nove tehnike.) Toda ti algoritmi so povsem teoretičnega pomena in zmagajo nad metodami, kot je Strassenova, samo za absurdno velike matrike.

Drugo podpolje razmišlja v manjšem merilu. Kmalu za Strassenovim delom je izraelski ameriški računalniški znanstvenik Shmuel Winograd je pokazala, da je Strassen dosegel teoretično mejo: ni mogoče pomnožiti matrik 2 krat 2 z manj kot sedmimi koraki množenja. Toda za vse druge velikosti matrik ostaja najmanjše število zahtevanih množenj odprto vprašanje. In hitri algoritmi za majhne matrike bi lahko imeli prevelik učinek, saj bi ponavljajoče se ponovitve takšnega algoritma lahko premagale Strassenov algoritem, ko se množijo matrike razumne velikosti.

Na žalost je samo število možnosti ogromno. Tudi za matrike 3 krat 3 "število možnih algoritmov presega število atomov v vesolju," je dejal Alhussein Fawzi, raziskovalec DeepMinda in eden od vodij novega dela.

Soočeni s tem vrtoglavim menijem možnosti so raziskovalci dosegli napredek s preoblikovanjem matričnega množenja v nekaj, kar se zdi kot popolnoma drugačen matematični problem - takšen, ki ga računalniki lažje obravnavajo. Abstraktno nalogo množenja dveh matrik je mogoče predstaviti kot posebno vrsto matematičnega objekta: tridimenzionalni niz števil, imenovan tenzor. Raziskovalci lahko nato ta tenzor razdelijo na vsoto osnovnih komponent, imenovanih tenzorji "ranga 1"; vsak od teh bo predstavljal drugačen korak v ustreznem algoritmu množenja matrike. To pomeni, da iskanje učinkovitega algoritma množenja pomeni minimiziranje števila členov v tenzorski razgradnji - manj kot je členov, manj je vključenih korakov.

Na ta način so raziskovalci odkrili nove algoritmi ki se množijo n-z-n matrike, ki uporabljajo manj kot standard n³ koraki množenja za številne majhne velikosti matrik. Toda algoritmi, ki presegajo ne samo standard, ampak tudi Strassenov algoritem za majhne matrike, so ostali nedosegljivi - do zdaj.

Igra se je začela

Ekipa DeepMind se je problema lotila tako, da je dekompozicijo tenzorjev spremenila v igro za enega igralca. Začeli so z algoritmom globokega učenja, ki izvira iz AlphaGo – drugega DeepMind AI, ki je leta 2016 naučil igrati družabno igro Go dovolj dobro, da premaga vrhunske človeške igralce.

Vsi algoritmi globokega učenja so zgrajeni okoli nevronskih mrež: mreže umetnih nevronov, razvrščenih v plasti, s povezavami, ki se lahko razlikujejo po moči, ki predstavljajo, koliko vsak nevron vpliva na tiste v naslednji plasti. Moč teh povezav se prilagodi v številnih iteracijah postopka usposabljanja, med katerim se nevronska mreža nauči preoblikovati vsak vhod, ki ga prejme, v izhod, ki pomaga algoritmu doseči njegov splošni cilj.

V novem algoritmu DeepMinda, imenovanem AlphaTensor, vhodi predstavljajo korake na poti do veljavne sheme množenja matrike. Prvi vhod v nevronsko mrežo je izvirni tenzor množenja matrike, njegov izhod pa je tenzor ranga 1, ki ga je AlphaTensor izbral za svojo prvo potezo. Algoritem ta tenzor ranga 1 odšteje od začetnega vnosa, kar prinese posodobljen tenzor, ki se vrne v omrežje kot nov vhod. Postopek se ponavlja, dokler na koncu ni vsak element v začetnem tenzorju reduciran na nič, kar pomeni, da ni več tenzorjev ranga 1, ki bi jih bilo treba odstraniti.

Na tej točki je nevronska mreža odkrila veljavno tenzorsko razgradnjo, saj je matematično zagotovljeno, da je vsota vseh tenzorjev ranga 1 popolnoma enaka začetnemu tenzorju. In korake, potrebne za dosego cilja, je mogoče prevesti nazaj v korake ustreznega algoritma množenja matrik.

Tukaj je igra: AlphaTensor večkrat razgradi tenzor na niz komponent ranga 1. Vsakič je AlphaTensor nagrajen, če najde način za zmanjšanje števila korakov. Toda bližnjice do zmage sploh niso intuitivne, tako kot morate včasih sestaviti popolnoma urejen obraz na Rubikovi kocki, preden lahko rešite celotno stvar.

Ekipa je zdaj imela algoritem, ki bi lahko teoretično rešil njihov problem. Najprej so ga morali usposobiti.

Nove poti

Kot vse nevronske mreže potrebuje tudi AlphaTensor veliko podatkov za usposabljanje, vendar je dekompozicija tenzorja znano težka težava. Bilo je nekaj primerov učinkovite razgradnje, s katerimi bi lahko raziskovalci nahranili mrežo. Namesto tega so algoritmu pomagali začeti tako, da so ga učili na veliko lažjem obratnem problemu: seštevanju množice naključno ustvarjenih tenzorjev ranga 1.

"Uporabljajo lahek problem za pridobivanje več podatkov za težji problem," je rekel Michael Littman, računalniški znanstvenik na univerzi Brown. Združevanje tega postopka usposabljanja za nazaj z učenjem z okrepitvijo, pri katerem je AlphaTensor ustvaril lastne podatke o usposabljanju, medtem ko je brskal po iskanju učinkovitih razčlenitev, je delovalo veliko bolje kot katera koli metoda usposabljanja sama.

Ekipa DeepMind je usposobila AlphaTensor za razgradnjo tenzorjev, ki predstavljajo množenje matrik do 12-krat-12. Iskal je hitre algoritme za množenje matrik navadnih realnih števil in tudi algoritme, specifične za bolj omejeno nastavitev, znano kot aritmetika modula 2. (To je matematika, ki temelji na samo dveh številkah, zato so elementi matrike lahko le 0 ali 1 in 1 + 1 = 0.) Raziskovalci pogosto začnejo s tem bolj omejenim, a še vedno ogromnim prostorom, v upanju, da se lahko tukaj odkriti algoritmi prilagodijo delo na matrikah realnih števil.

Po usposabljanju je AlphaTensor v nekaj minutah ponovno odkril Strassenov algoritem. Nato je odkril na tisoče novih hitrih algoritmov za vsako velikost matrike. Ti so se razlikovali od najbolj znanih algoritmov, vendar so imeli enako število korakov množenja.

V nekaj primerih je AlphaTensor celo premagal obstoječe rekorde. Njegovo najbolj presenetljivo odkritje se je zgodilo pri aritmetiki po modulu 2, kjer je našel nov algoritem za množenje matrik 4 krat 4 v 47 korakih množenja, kar je izboljšava v primerjavi z 49 koraki, potrebnimi za dve ponovitvi Strassenovega algoritma. Prav tako je premagal najbolj znani algoritem za matrike 5 krat 5 modulo 2, s čimer je zmanjšal število zahtevanih množenj s prejšnjega rekorda 98 na 96. (Toda ta novi rekord še vedno zaostaja za 91 koraki, ki bi jih bilo potrebno premagati Strassenov algoritem, ki uporablja matrike 5 krat 5.)

Nov odmeven rezultat je poskrbel za veliko razburjenja, z nekateri raziskovalci hvale izboljšanje statusa quo, ki temelji na AI. Toda vsi v skupnosti množenja matrik niso bili tako navdušeni. "Počutila sem se, kot da je bilo malo prenapeto," je dejala Vassilevska Williams. »To je še eno orodje. Ne gre za 'Oh, računalniki premagajo ljudi,' veš?«

Raziskovalci so tudi poudarili, da bi bila takojšnja uporaba rekordnega algoritma 4-za-4 omejena: ne samo, da je veljaven samo v aritmetiki modula 2, ampak v resničnem življenju obstajajo poleg hitrosti še pomembni vidiki.

Fawzi se je strinjal, da je to res šele začetek. "Obstaja veliko prostora za izboljšave in raziskave, in to je dobro," je dejal.

Zadnji zasuk

Največja moč AlphaTensorja v primerjavi z dobro uveljavljenimi metodami računalniškega iskanja je tudi njegova največja slabost: ni omejen s človeško intuicijo o tem, kako izgledajo dobri algoritmi, zato ne more razložiti svojih odločitev. Zaradi tega se raziskovalci težko učijo iz njegovih dosežkov.

Vendar to morda ni tako velika pomanjkljivost, kot se zdi. Nekaj ​​dni po rezultatu AlphaTensor je matematik Manuel Kauers in njegov podiplomski študent Jakob Moosbauer, oba z Univerze Johannesa Keplerja v Linzu v Avstriji, sta poročala o novem koraku naprej.

Ko je dokument DeepMinda izšel, sta Kauers in Moosbauer iskala nove algoritme množenja z uporabo običajnega računalniško podprtega iskanja. Toda za razliko od večine takšnih iskanj, ki se začnejo znova z novim vodilnim načelom, njihova metoda deluje tako, da vedno znova spreminja obstoječi algoritem v upanju, da bo iz njega iztisnil več prihrankov pri množenju. Kot izhodišče so vzeli AlphaTensorjev algoritem za matrike 5-krat-5 modulo 2 in so presenečeni ugotovili, da je njihova metoda zmanjšala število korakov množenja s 96 na 95 po samo nekaj sekundah računanja.

AlphaTensor jim je posredno pomagal tudi pri še eni izboljšavi. Pred tem se Kauers in Moosbauer nista trudila raziskovati prostora matrik 4 krat 4, saj sta verjela, da ne bo mogoče premagati dveh ponovitev Strassenovega algoritma. Rezultat AlphaTensorja jih je spodbudil k ponovnemu premisleku in po enem tednu računanja, ki so ga začeli iz nič, je njihova metoda prikazala še en 47-stopenjski algoritem, ki ni povezan s tistim, ki ga je odkril AlphaTensor. "Če bi nam kdo povedal, da je treba nekaj odkriti za 4-na-4, bi to lahko storili že prej," je dejal Kauers. "Ampak OK, no, tako to deluje."

Littman pričakuje še več takšnih presenečenj in situacijo primerja s prvim primerom, ko je tekač končal miljo v manj kot štirih minutah, podvig, ki se je na splošno zdel nemogoč. »Ljudje so si mislili: 'Oh, počakaj, to zmoremo', zdaj pa to zmore veliko ljudi,« je dejal.

V prihodnosti Fawzi upa, da bo posplošil AlphaTensor za reševanje širšega nabora matematičnih in računalniških nalog, tako kot se je njegov prednik AlphaGo sčasoma razširil v druge igre.

Kauers vidi to kot pravi lakmusov test za uporabo strojnega učenja pri odkrivanju novih algoritmov. Poudarja, da je iskanje hitrih algoritmov za množenje matrik kombinatorni problem, za katerega so računalniška iskanja, z ali brez človeške pomoči, zelo primerna. Vendar ni vseh matematičnih problemov tako enostavno določiti. Če lahko strojno učenje odkrije kvalitativno novo algoritemsko idejo, je dejal, "bi to potem spremenilo igro."