Sissejuhatus
Matemaatikud armastavad head puslet. Isegi nii abstraktne asi nagu maatriksite korrutamine (kahemõõtmelised arvutabelid) võib tunduda mänguna, kui proovite leida selleks kõige tõhusama viisi. See on natuke nagu prooviks lahendada Rubiku kuubik võimalikult väheste liigutustega – see on väljakutsuv, kuid ahvatlev. Välja arvatud see, et Rubiku kuubiku puhul on võimalike käikude arv igal sammul 18; maatriksi korrutamise korral võib isegi suhteliselt lihtsatel juhtudel iga samm esitada rohkem kui 1012 võimalusi.
Viimase 50 aasta jooksul on teadlased sellele probleemile lähenenud mitmel viisil, mis kõik põhinevad inimintuitsioonil tehtud arvutiotsingutel. Eelmisel kuul näitas tehisintellektifirma DeepMind meeskond, kuidas probleemile uuest suunast läheneda. paber in loodus et nad olid edukalt koolitanud närvivõrku, et avastada uusi kiireid algoritme maatriksi korrutamiseks. Tundus, nagu oleks tehisintellekt leidnud tundmatu strateegia koletult keerulise Rubiku kuubiku lahendamiseks.
"See on väga kena tulemus," ütles Josh Alman, Columbia ülikooli arvutiteadlane. Kuid tema ja teised maatriksikorrutamise spetsialistid rõhutasid ka, et selline tehisintellekti abi pigem täiendab kui asendab olemasolevaid meetodeid – vähemalt lähiajal. "See on nagu tõestus kontseptsioonist millegi jaoks, mis võib saada läbimurdeks," ütles Alman. Tulemus lihtsalt aitab teadlasi nende otsingutel.
Justkui tõestamaks asja, kolm päeva pärast loodus paber ilmus, näitlikustas paar Austria teadlast, kuidas uued ja vanad meetodid võivad üksteist täiendada. Nad kasutasid tavapärast arvutipõhise otsingut veelgi parandada üks algoritmidest, mille närvivõrk oli avastanud.
Tulemused viitavad sellele, et nagu Rubiku kuubiku lahendamise protsess, on ka tee paremate algoritmide poole täis keerdkäike.
Maatriksite korrutamine
Maatrikskorrutamine on kogu matemaatikas üks põhilisemaid ja üldlevinud tehteid. Paari korrutamiseks n-kõrval-n maatriksid, millest igaühel on n2 elemendid, korrutate ja lisate need elemendid kokku konkreetsetes kombinatsioonides, et luua toode, kolmandik n-kõrval-n maatriks. Standardretsept kahe korrutamiseks n-kõrval-n maatriksid nõuavad n3 korrutustehte, nii et näiteks maatriks 2x2 nõuab kaheksat korrutamist.
Suuremate maatriksite puhul, kus on tuhandeid ridu ja veerge, muutub see protsess kiiresti tülikaks. Kuid 1969. aastal matemaatik Volker Strassen avastas protseduuri 2-kordsete maatriksite paari korrutamiseks, kasutades pigem seitset kui kaheksat korrutamisetappi, mille hinnaks on rohkem liitmisetappe.
Strasseni algoritm on asjatult keerutatud, kui soovite lihtsalt korrutada paari 2x2 maatriksit. Kuid ta mõistis, et see toimib ka suuremate maatriksite puhul. Seda seetõttu, et maatriksi elemendid võivad ise olla maatriksid. Näiteks 20,000 20,000 rea ja 2 2 veeruga maatriksi saab ümber kujutada 10,000x10,000 maatriksina, mille neli elementi on igaüks 5,000 5,000x2 2 maatriksist. Kõik need maatriksid saab seejärel jagada neljaks XNUMX x XNUMX plokiks jne. Strassen võiks rakendada oma meetodit XNUMX-XNUMX maatriksi korrutamiseks selle pesastatud hierarhia igal tasemel. Maatriksi suuruse kasvades suureneb korrutuste arvu vähenemine.
Strasseni avastus viis maatriksi korrutamise tõhusate algoritmide otsimiseni, mis on sellest ajast peale inspireerinud kahte erinevat alamvälja. Üks keskendub põhimõttelisele küsimusele: kui kujutate ette kahe korrutamist n-kõrval-n maatriksid ja lase n joosta lõpmatuse poole, kuidas korrutamise sammude arv kiireimas võimalikus algoritmi skaalas n? praegune rekord parimaks skaleerimiseks, n2.3728596, kuulub Almanile ja Virginia Vassilevska Williams, Massachusettsi Tehnoloogiainstituudi arvutiteadlane. (Hiljuti avaldamata eeltrükk teatas väikesest täiustusest, kasutades uut tehnikat.) Kuid need algoritmid pakuvad puhtalt teoreetiliselt huvi, võidavad selliseid meetodeid nagu Strasseni oma ainult absurdselt suurte maatriksite puhul.
Teine alamväli mõtleb väiksemas plaanis. Varsti pärast Strasseni tööd Iisraeli Ameerika arvutiteadlane Shmuel Winograd näitas et Strassen oli jõudnud teoreetilise piirini: 2-2-ga maatriksit pole võimalik korrutada vähem kui seitsme korrutusastmega. Kuid kõigi teiste maatriksisuuruste puhul jääb nõutavate korrutuste miinimumarv lahtiseks küsimuseks. Ja väikeste maatriksite kiiretel algoritmidel võib olla suurem mõju, kuna sellise algoritmi korduvad iteratsioonid võivad mõistliku suurusega maatriksite korrutamisel ületada Strasseni algoritmi.
Kahjuks on võimaluste hulk tohutu. Isegi 3 korda 3 maatriksite puhul ületab võimalike algoritmide arv universumi aatomite arvu. Alhussein Fawzi, DeepMindi uurija ja üks uue töö eestvedajaid.
Selle peadpööritava valikute menüüga silmitsi seistes on teadlased teinud edusamme, muutes maatrikskorrutamise täiesti erinevaks matemaatikaprobleemiks, mida arvutitel on lihtsam käsitleda. Abstraktset ülesannet kahe maatriksi korrutamiseks on võimalik kujutada teatud tüüpi matemaatilise objektina: kolmemõõtmelise arvude massiivi, mida nimetatakse tensoriks. Seejärel saavad teadlased selle tensori jagada elementaarsete komponentide summaks, mida nimetatakse "aste-1" tensoriteks; igaüks neist esindab erinevat etappi vastavas maatriksi korrutamisalgoritmis. See tähendab, et tõhusa korrutamisalgoritmi leidmine tähendab terminite arvu minimeerimist tensori lagunemises – mida vähem on termineid, seda vähem on kaasatud samme.
Sel viisil on teadlased avastanud uusi algoritme mis paljunevad n-kõrval-n maatriksid, mis kasutavad vähem kui standard n3 korrutamise sammud paljude väikeste maatriksi suuruste jaoks. Kuid algoritmid, mis ületavad mitte ainult standardset, vaid ka Strasseni algoritmi väikeste maatriksite jaoks, on jäänud seni kättesaamatuks.
Mäng on sisse lülitatud
DeepMindi meeskond lähenes probleemile, muutes tensorite lagunemise ühe mängijaga mänguks. Nad alustasid sügava õppimise algoritmiga, mis pärineb AlphaGost - teisest DeepMind AI-st, mis 2016. õppis mängima lauamängu Go piisavalt hästi, et võita tippmängijaid.
Kõik süvaõppe algoritmid on üles ehitatud närvivõrkude ümber: kihtidesse sorteeritud tehisneuronite võrgud, mille tugevused võivad erineda, mis näitavad, kui palju iga neuron mõjutab järgmises kihis olevaid. Nende ühenduste tugevust muudetakse treeningprotseduuri paljude iteratsioonide käigus, mille käigus närvivõrk õpib teisendama iga saadud sisendit väljundiks, mis aitab algoritmil oma üldist eesmärki täita.
DeepMindi uues algoritmis, mida nimetatakse AlphaTensoriks, tähistavad sisendid sammud kehtiva maatriksi korrutusskeemi suunas. Neuraalvõrgu esimene sisend on algne maatriksi korrutamise tensor ja selle väljund on 1. järgu tensor, mille AlphaTensor valis oma esimeseks käiguks. Algoritm lahutab selle 1. järgu tensori algsest sisendist, saades värskendatud tensori, mis suunatakse võrku tagasi uue sisendina. Protsess kordub, kuni lõpuks on kõik lähtetensoris olevad elemendid viidud nullini, mis tähendab, et 1. järgu tensoreid pole enam välja võtta.
Sel hetkel on närvivõrk avastanud kehtiva tensorite lagunemise, kuna on matemaatiliselt garanteeritud, et kõigi 1. järgu tensorite summa on täpselt võrdne algustensoriga. Ja sinna jõudmiseks tehtud sammud saab tõlkida tagasi vastava maatriksi korrutusalgoritmi sammudeks.
Mäng on järgmine: AlphaTensor lagundab tensori korduvalt 1. järgu komponentide komplektiks. AlphaTensor saab iga kord tasu, kui ta leiab võimaluse sammude arvu vähendamiseks. Kuid otseteed võiduni ei ole sugugi intuitiivsed, nii nagu peate mõnikord Rubiku kuubikul täiuslikult järjestatud näo välja rabelema, enne kui saate kogu asja lahendada.
Meeskonnal oli nüüd algoritm, mis võiks teoreetiliselt nende probleemi lahendada. Nad lihtsalt pidid selle kõigepealt välja õpetama.
Uued teed
Nagu kõik närvivõrgud, vajab ka AlphaTensor treenimiseks palju andmeid, kuid tensori lagunemine on kurikuulsalt raske probleem. Tõhusatest lagunemistest oli vähe näiteid, mida teadlased saaksid võrku toita. Selle asemel aitasid nad algoritmi käivitada, treenides seda palju lihtsama pöördprobleemi jaoks: liites kokku hulga juhuslikult genereeritud 1. järgu tensoreid.
"Nad kasutavad lihtsat probleemi, et toota raske probleemi jaoks rohkem andmeid," ütles Michael Littman, arvutiteadlane Browni ülikoolist. Selle tagurpidi treeningprotseduuri kombineerimine tugevdava õppega, kus AlphaTensor genereeris oma treeningandmed, kui ta eksib tõhusate lagunemiste otsimisel, toimis palju paremini kui kumbki koolitusmeetod eraldi.
DeepMindi meeskond koolitas AlphaTensorit lagundama tensoreid, mis esindavad maatriksite korrutamist kuni 12-12-ga. See otsis kiireid algoritme tavaliste reaalarvude maatriksite korrutamiseks ja ka algoritme, mis olid spetsiifilised kitsamale seadistusele, mida tuntakse modulo 2 aritmeetikana. (See on matemaatika, mis põhineb ainult kahel arvul, nii et maatriksi elemendid võivad olla ainult 0 või 1 ja 1 + 1 = 0.) Teadlased alustavad sageli sellest kitsamast, kuid siiski laiast ruumist, lootes, et siin avastatud algoritme saab kohandada reaalarvude maatriksite kallal töötamine.
Pärast treenimist avastas AlphaTensor Strasseni algoritmi mõne minuti jooksul uuesti. Seejärel avastas see iga maatriksi suuruse jaoks kuni tuhandeid uusi kiireid algoritme. Need erinevad kõige tuntumatest algoritmidest, kuid neil oli sama arv korrutamisetappe.
Mõnel juhul ületas AlphaTensor isegi olemasolevaid rekordeid. Selle kõige üllatavamad avastused juhtusid mooduli 2 aritmeetikas, kus leiti uus algoritm 4-kordsete maatriksite korrutamiseks 4 korrutamisetapis, mis on täiustus võrreldes 47 sammuga, mis on vajalikud Strasseni algoritmi kahe iteratsiooni jaoks. See ületas ka tuntuima algoritmi 49 korda 5 mooduli 5 maatriksite jaoks, vähendades nõutavate korrutuste arvu eelmiselt rekordilt 2-le. (Kuid see uus rekord jääb ikkagi maha 98 sammust, mida oleks vaja ületada Strasseni algoritm, kasutades 96 korda 91 maatriksit.)
Uus kõrgetasemeline tulemus tekitas palju elevust, koos mõned uurijad kuhjaga kiitust tehisintellektil põhineva status quo parandamise kohta. Kuid mitte kõik maatriksikorrutamise kogukonnas ei olnud nii muljet avaldanud. "Mulle tundus, et see oli pisut üleliigne," ütles Vassilevska Williams. "See on veel üks tööriist. See ei ole nii, et "Oh, arvutid võidavad inimesi", tead?"
Teadlased rõhutasid ka, et rekordilise 4x4 algoritmi kohesed rakendused oleksid piiratud: see ei kehti mitte ainult mooduli 2 aritmeetikas, vaid ka reaalses elus on lisaks kiirusele ka olulisi kaalutlusi.
Fawzi nõustus, et see on tõesti alles algus. "Parendus- ja uurimisruumi on palju ning see on hea," ütles ta.
Viimane keerdkäik
AlphaTensori suurim tugevus võrreldes väljakujunenud arvutiotsingumeetoditega on ka suurim nõrkus: seda ei piira inimlik intuitsioon heade algoritmide väljanägemise osas, seega ei saa ta oma valikuid selgitada. Seetõttu on teadlastel raske selle saavutustest õppida.
Kuid see ei pruugi olla nii suur puudus, kui tundub. Mõni päev pärast AlphaTensori tulemust, matemaatik Manuel Kauers ja tema magistrant Jakob Moosbauer, mõlemad Austria Linzi Johannes Kepleri ülikoolist, teatasid järjekordsest sammust edasi.
Sissejuhatus
Kui DeepMind paber ilmus, otsisid Kauers ja Moosbauer tavapärase arvutipõhise otsingu abil uusi korrutamisalgoritme. Kuid erinevalt enamikust sellistest otsingutest, mis algavad uuesti uue juhtpõhimõttega, töötab nende meetod olemasolevat algoritmi korduvalt kohandades, lootes sellest rohkem korrutamise kokkuhoidu välja pigistada. Võttes lähtepunktiks AlphaTensori algoritmi 5-kordsete mooduli 5 maatriksite jaoks, avastasid nad üllatusega, et nende meetod vähendas pärast mõnesekundilist arvutamist korrutamisetappide arvu 2-lt 96-le.
AlphaTensor aitas neil ka kaudselt veel ühe täiustuse teha. Varem ei olnud Kauers ja Moosbauer vaevunud 4x4 maatriksite ruumi uurima, uskudes, et Strasseni algoritmi kahte iteratsiooni pole võimalik ületada. AlphaTensori tulemus ajendas neid uuesti mõtlema ja pärast nädalast nullist alustamist arvutas nende meetod välja teise 47-astmelise algoritmi, mis ei olnud seotud AlphaTensori avastatuga. "Kui keegi oleks meile öelnud, et neljakaupa on midagi avastada, oleksime võinud seda varem teha," ütles Kauers. "Aga okei, nii see töötab."
Littman ootab selliseid üllatusi rohkem, võrdledes olukorda esimese korraga, kui jooksja läbis miili vähem kui nelja minutiga, mis on laialdaselt võimatuks peetud. "Inimesed ütlesid, et oodake, me saame seda teha," ütles ta.
Tulevikku vaadates loodab Fawzi AlphaTensori üldistada, et see saaks lahendada suurema hulga matemaatilisi ja arvutuslikke ülesandeid, nagu ka tema esivanem AlphaGo hargnes lõpuks teistesse mängudesse.
Kauers peab seda tõeliseks lakmustestiks masinõppe rakendamiseks uute algoritmide avastamisel. Ta juhib tähelepanu sellele, et kiirete maatrikskorrutusalgoritmide otsimine on kombinatoorne probleem, mille lahendamiseks sobivad hästi arvutiotsingud, kas inimabiga või ilma. Kuid mitte kõiki matemaatilisi probleeme pole nii lihtne kindlaks teha. Kui masinõpe suudab avastada kvalitatiivselt uue algoritmilise idee, ütles ta: "see oleks mängu muutja."
