esittely
Matemaatikot rakastavat hyvää palapeliä. Jopa niin abstrakti asia kuin matriisien kertominen (kaksiulotteiset lukutaulukot) voi tuntua peliltä, kun yrität löytää tehokkaimman tavan tehdä se. Se on vähän kuin yrittäisi ratkaista Rubikin kuution mahdollisimman harvoilla liikkeillä – haastavaa, mutta houkuttelevaa. Lukuun ottamatta sitä, että Rubikin kuutiolla mahdollisten liikkeiden määrä kussakin vaiheessa on 18; matriisin kertolaskussa, jopa suhteellisen yksinkertaisissa tapauksissa, jokainen askel voi esittää enemmän kuin 1012 vaihtoehtoja.
Viimeisten 50 vuoden aikana tutkijat ovat lähestyneet tätä ongelmaa monin tavoin, jotka kaikki perustuvat ihmisen intuition tukemiin tietokonehakuihin. Viime kuussa tekoälyyrityksen DeepMind-tiimi osoitti, kuinka ongelmaa voidaan käsitellä uudesta suunnasta. paperi in luonto että he olivat onnistuneesti kouluttaneet hermoverkkoa löytämään uusia nopeita algoritmeja matriisin kertomiseen. Oli kuin tekoäly olisi löytänyt tuntemattoman strategian hirvittävän monimutkaisen Rubikin kuution ratkaisemiseksi.
"Se on erittäin siisti tulos", sanoi Josh Alman, tietojenkäsittelytieteilijä Columbian yliopistossa. Mutta hän ja muut matriisin kertomisen asiantuntijat korostivat myös, että tällainen AI-apu täydentää olemassa olevia menetelmiä sen sijaan, että se korvaa - ainakin lähitulevaisuudessa. "Se on kuin todiste konseptista jostakin, josta voi tulla läpimurto", Alman sanoi. Tulos yksinkertaisesti auttaa tutkijoita heidän etsinnässään.
Ikään kuin todistaakseen asian, kolmen päivän kuluttua luonto Paperi ilmestyi, itävaltalainen tutkijapari havainnollistaa, kuinka uudet ja vanhat menetelmät voisivat täydentää toisiaan. He käyttivät tavanomaista tietokoneavusteista hakua parantaa edelleen yksi neuroverkkojen löytämistä algoritmeista.
Tulokset viittaavat siihen, että kuten Rubikin kuution ratkaiseminen, polku parempiin algoritmeihin on täynnä käänteitä.
Matriisien kertominen
Matriisikertominen on yksi perustavanlaatuisimmista ja kaikkialla esiintyvistä operaatioista koko matematiikan alueella. Kerrotaan pari n-by-n matriiseja, joista jokaisessa on n2 elementtejä, kerrot ja lisäät nämä elementit yhteen tietyissä yhdistelmissä tuotteen luomiseksi, kolmanneksen n-by-n matriisi. Vakioresepti kahden kertomiseen n-by-n matriisit vaativat n3 kertolaskuoperaatioita, joten esimerkiksi 2 x 2 -matriisi vaatii kahdeksan kertolaskua.
Suuremmissa matriiseissa, joissa on tuhansia rivejä ja sarakkeita, tämä prosessi tulee nopeasti hankalaksi. Mutta vuonna 1969 matemaatikko Volker Strassen löysi menettelyn 2-x2-matriisin parin kertomiseen käyttämällä seitsemää kertolaskuvaihetta kahdeksan sijaan, lisättyjen yhteenlaskuvaiheiden kustannuksella.
Strassenin algoritmi on turhaan mutkikas, jos haluat vain kertoa 2-x2-matriisien parin. Mutta hän tajusi, että se toimisi myös isommille matriiseille. Tämä johtuu siitä, että matriisin elementit voivat itse olla matriiseja. Esimerkiksi matriisi, jossa on 20,000 20,000 riviä ja 2 2 saraketta, voidaan kuvitella uudelleen 10,000 x 10,000 matriisiksi, jonka neljä elementtiä ovat kukin 5,000 5,000 x 2 2 matriisi. Jokainen näistä matriiseista voidaan sitten jakaa neljään XNUMX XNUMX x XNUMX XNUMX lohkoon ja niin edelleen. Strassen voisi soveltaa menetelmäään kertoakseen XNUMX x XNUMX matriisit tämän sisäkkäisen hierarkian kullakin tasolla. Kun matriisin koko kasvaa, säästöt pienemmästä kertolaskusta kasvavat.
Strassenin löytö johti tehokkaiden algoritmien etsimiseen matriisin kertolaskulle, mikä on sittemmin inspiroinut kahta erillistä alakenttää. Yksi keskittyy periaatekysymykseen: Jos kuvittelet kertovasi kaksi n-by-n matriisit ja anna n ajaa kohti ääretöntä, kuinka kertolaskuaskelten määrä nopeimmassa mahdollisessa algoritmissa skaalaus n? nykyinen ennätys parhaan skaalauksen saamiseksi, n2.3728596, kuuluu Almanille ja Virginia Vassilevska Williams, Massachusetts Institute of Technologyn tietojenkäsittelytieteilijä. (Äskettäin julkaisematon preprint raportoivat pienestä parannuksesta käyttämällä uutta tekniikkaa.) Mutta nämä algoritmit ovat puhtaasti teoreettisesti kiinnostavia, ja ne voittivat Strassenin kaltaiset menetelmät vain järjettömän suurille matriiseille.
Toinen alakenttä ajattelee pienemmässä mittakaavassa. Pian Strassenin työn jälkeen israelilainen amerikkalainen tietojenkäsittelytieteilijä Shmuel Winograd osoittivat että Strassen oli saavuttanut teoreettisen rajan: Ei ole mahdollista kertoa 2-x2-matriiseja alle seitsemällä kertolaskuvaiheella. Mutta kaikkien muiden matriisikokojen osalta vaadittujen kertolaskujen vähimmäismäärä on avoin kysymys. Ja nopeilla algoritmeilla pienille matriiseille voi olla suurempi vaikutus, koska tällaisen algoritmin toistuvat iteraatiot saattavat voittaa Strassenin algoritmin, kun kohtuullisen kokoisia matriiseja kerrotaan.
Valitettavasti mahdollisuuksia on valtava määrä. Jopa 3 x 3 matriiseilla "mahdollisten algoritmien määrä ylittää universumin atomien määrän", sanoi. Alhussein Fawzi, DeepMind-tutkija ja yksi uuden työn johtajista.
Tämän huiman vaihtoehtovalikon edessä tutkijat ovat edistyneet muuttamalla matriisikertolaskua täysin erilaiselta matemaattiselta ongelmalta – ongelmaksi, jota tietokoneiden on helpompi käsitellä. On mahdollista esittää abstrakti tehtävä kertoa kaksi matriisia tietynlaisena matemaattisena objektina: kolmiulotteisena numeroryhmänä, jota kutsutaan tensoriksi. Tutkijat voivat sitten jakaa tämän tensorin alkeiskomponenttien summaksi, joita kutsutaan "rank-1"-tensoreiksi; kukin näistä edustaa eri vaihetta vastaavassa matriisin kertolaskualgoritmissa. Tämä tarkoittaa, että tehokkaan kertolaskualgoritmin löytäminen merkitsee termien määrän minimoimista tensorihajotelmassa - mitä vähemmän termejä, sitä vähemmän vaiheita.
Tällä tavalla tutkijat ovat löytäneet uutta algoritmit joka moninkertaistuu n-by-n matriiseja, jotka käyttävät vähemmän kuin standardi n3 kertolaskuaskelia monille pienille matriisikoille. Mutta algoritmit, jotka ylittävät paitsi standardin myös Strassenin algoritmin pienille matriiseille, ovat pysyneet ulottumattomissa - tähän asti.
Peli päällä
DeepMind-tiimi lähestyi ongelmaa muuttamalla tensorihajoamisen yhden pelaajan peliksi. He aloittivat syväoppimisalgoritmilla, joka on peräisin AlphaGosta – toisesta DeepMind AI:stä, joka vuonna 2016 oppi pelaamaan lautapeliä Go tarpeeksi hyvin voittamaan parhaat ihmispelaajat.
Kaikki syväoppimisalgoritmit on rakennettu hermoverkkojen ympärille: keinotekoisten hermosolujen verkkoja, jotka on lajiteltu kerroksiin, ja niiden yhteydet voivat vaihdella vahvuudeltaan osoittaen, kuinka paljon kukin neuroni vaikuttaa seuraavan kerroksen hermosoluihin. Näiden yhteyksien vahvuutta säädellään useissa harjoitusmenettelyn iteraatioissa, joiden aikana hermoverkko oppii muuttamaan jokaisen vastaanottamansa syötteen ulostuloksi, joka auttaa algoritmia saavuttamaan yleistavoitteensa.
DeepMindin uudessa algoritmissa, nimeltään AlphaTensor, syötteet edustavat vaiheita kelvollisen matriisin kertolaskumenetelmän luomisessa. Ensimmäinen syöte neuroverkkoon on alkuperäinen matriisin kertolaskutensori, ja sen lähtö on rank-1-tensori, jonka AlphaTensor on valinnut ensimmäiselle siirrolleen. Algoritmi vähentää tämän rank-1-tensorin alkuperäisestä syötteestä ja tuottaa päivitetyn tensorin, joka syötetään takaisin verkkoon uutena syötteenä. Prosessi toistuu, kunnes lopulta jokainen alkutensorin elementti on pienennetty nollaan, mikä tarkoittaa, että enää ei ole poistettavia rank-1 tensoreita.
Siinä vaiheessa hermoverkko on löytänyt kelvollisen tensorihajotelman, koska on matemaattisesti taattu, että kaikkien rank-1-tensorien summa on täsmälleen yhtä suuri kuin aloitustensori. Ja siihen pääsemiseen tarvittavat vaiheet voidaan kääntää takaisin vastaavan matriisin kertolaskualgoritmin vaiheiksi.
Tässä on peli: AlphaTensor hajottaa toistuvasti tensorin joukoksi ykköskomponentteja. Joka kerta AlphaTensor saa palkinnon, jos se löytää tavan vähentää vaiheiden määrää. Mutta voiton oikopolut eivät ole lainkaan intuitiivisia, aivan kuten sinun on joskus sekoitettava täydellisesti järjestetyt kasvot Rubikin kuutioon ennen kuin voit ratkaista koko asian.
Ryhmällä oli nyt algoritmi, joka voisi teoreettisesti ratkaista heidän ongelmansa. Heidän täytyi vain kouluttaa se ensin.
Uusia polkuja
Kuten kaikki hermoverkot, AlphaTensor tarvitsee paljon dataa harjoitellakseen, mutta tensorin hajottaminen on tunnetusti vaikea ongelma. Tehokkaasta hajoamisesta oli vain vähän esimerkkejä, joita tutkijat voisivat syöttää verkkoon. Sen sijaan he auttoivat algoritmia pääsemään alkuun kouluttamalla sitä paljon helpompaan käänteiseen ongelmaan: laskemalla yhteen joukko satunnaisesti luotuja rank-1-tensoreja.
"He käyttävät helppoa ongelmaa tuottaakseen lisää tietoa vaikeaan ongelmaan", sanoi Michael Littman, tietojenkäsittelytieteilijä Brownin yliopistosta. Tämän taaksepäin harjoittelun yhdistäminen vahvistusoppimiseen, jossa AlphaTensor loi omat harjoitustietonsa, kun se sekoitti etsiessään tehokkaita hajotuksia, toimi paljon paremmin kuin kumpikaan harjoitusmenetelmä yksinään.
DeepMind-tiimi koulutti AlphaTensorin hajottamaan tensorit, jotka edustavat matriisien kertolaskua jopa 12-12:een. Se etsi nopeita algoritmeja tavallisten reaalilukujen matriisien kertomiseen sekä algoritmeja, jotka ovat spesifisiä rajoitetummalle asetukselle, joka tunnetaan nimellä modulo 2 -aritmetiikka. (Tämä on matematiikkaa, joka perustuu vain kahteen numeroon, joten matriisielementit voivat olla vain 0 tai 1 ja 1 + 1 = 0.) Tutkijat aloittavat usein tästä suppeammasta mutta silti laajasta tilasta toivoen, että täältä löydetyt algoritmit voidaan mukauttaa työstää reaalilukumatriiseja.
Harjoittelun jälkeen AlphaTensor löysi Strassenin algoritmin uudelleen muutamassa minuutissa. Sitten se löysi jopa tuhansia uusia nopeita algoritmeja kullekin matriisikokolle. Nämä erosivat tunnetuimmista algoritmeista, mutta niissä oli sama määrä kertolaskuvaiheita.
Muutamissa tapauksissa AlphaTensor jopa ylitti olemassa olevat ennätykset. Sen yllättävimmät löydöt tapahtuivat modulo 2 -aritmetiikassa, jossa se löysi uuden algoritmin 4-x4-matriisien kertomiseen 47 kertolaskuvaiheessa, mikä on parannus verrattuna Strassenin algoritmin kahteen iteraatioon vaadittavaan 49 vaiheeseen. Se myös päihitti tunnetuimman algoritmin 5 x 5 modulo 2 -matriiseille vähentäen vaadittujen kertolaskujen määrää aiemmasta ennätyksestä 98:een 96:een. (Mutta tämä uusi ennätys on edelleen jäljessä 91 askelta, jotka vaadittaisiin voittamaan Strassenin algoritmi käyttäen 5 x 5 matriiseja.)
Uusi korkean profiilin tulos loi paljon jännitystä, mm jotkut tutkijat ylistää tekoälyyn perustuvaa status quon parannusta. Mutta kaikki matriisin kertolaskuyhteisössä eivät olleet niin vaikuttuneita. "Minusta tuntui, että se oli hieman liioiteltu", sanoi Vassilevska Williams. "Se on toinen työkalu. Se ei ole kuin "Oi, tietokoneet voittivat ihmiset", tiedätkö?"
Tutkijat korostivat myös, että ennätysten rikkovan 4x4-algoritmin välittömät sovellukset olisivat rajoitettuja: Se ei päde vain modulo 2 -aritmetiikassa, vaan tosielämässä on nopeuden lisäksi tärkeitä näkökohtia.
Fawzi myönsi, että tämä on todellakin vasta alkua. "On paljon parantamisen ja tutkimuksen varaa, ja se on hyvä asia", hän sanoi.
Viimeinen käänne
AlphaTensorin suurin vahvuus vakiintuneisiin tietokonehakumenetelmiin verrattuna on myös sen suurin heikkous: sitä ei rajoita ihmisen intuitio siitä, miltä hyvät algoritmit näyttävät, joten se ei voi selittää valintojaan. Tämän vuoksi tutkijoiden on vaikea oppia sen saavutuksista.
Mutta tämä ei ehkä ole niin suuri haitta kuin miltä näyttää. Muutama päivä AlphaTensorin tuloksen jälkeen matemaatikko Manuel Kauers ja hänen jatko-opiskelijansa Jakob Moosbauer, molemmat Johannes Kepler University Linzissä Itävallassa, raportoivat uudesta askeleesta eteenpäin.
esittely
Kun DeepMind-paperi julkaistiin, Kauers ja Moosbauer olivat etsimässä uusia kertolaskualgoritmeja tavanomaisella tietokoneavusteisella haulla. Mutta toisin kuin useimmat tällaiset haut, jotka alkavat alusta uudella ohjausperiaatteella, niiden menetelmä toimii säätämällä toistuvasti olemassa olevaa algoritmia toivoen saavansa siitä lisää kertolaskujen säästöjä. Ottaen lähtökohtana AlphaTensorin algoritmin 5 x 5 modulo 2 -matriiseille, he yllättyivät huomatessaan, että heidän menetelmänsä vähensi kertolaskuvaiheiden lukumäärän 96:sta 95:een vain muutaman sekunnin laskennan jälkeen.
AlphaTensor auttoi heitä myös tekemään toisen parannuksen epäsuorasti. Aikaisemmin Kauers ja Moosbauer eivät olleet vaivautuneet tutkimaan 4 x 4 matriisien avaruutta, koska he uskoivat, että Strassenin algoritmin kahta iteraatiota ei olisi mahdollista voittaa. AlphaTensorin tulos sai heidät harkitsemaan asiaa uudelleen, ja viikon tyhjästä alkaneen laskenta-ajan jälkeen heidän menetelmänsä löysi toisen 47-vaiheisen algoritmin, joka ei liittynyt AlphaTensorin löytämään algoritmiin. "Jos joku olisi kertonut meille, että neljä kertaa neljässä on jotain löydettävää, olisimme voineet tehdä sen aikaisemmin", Kauers sanoi. "Mutta okei, niin se toimii."
Littman odottaa lisää tällaisia yllätyksiä ja vertaa tilannetta ensimmäiseen kertaan, kun juoksija suoritti mailin alle neljässä minuutissa, mikä on ollut laajalti mahdotonta. "Ihmiset olivat kuin "Oh, odota, me voimme tehdä tämän", ja nyt monet ihmiset voivat tehdä sen", hän sanoi.
Tulevaisuudessa Fawzi toivoo voivansa yleistää AlphaTensorin käsittelemään laajempia matemaattisia ja laskennallisia tehtäviä, aivan kuten sen esi-isä AlphaGo lopulta haarautui muihin peleihin.
Kauers näkee tämän todellisena lakmuskokeena koneoppimisen soveltamiselle uusien algoritmien löytämiseen. Hän huomauttaa, että nopeiden matriisikerto-algoritmien etsiminen on kombinatorinen ongelma, johon tietokonehaku, ihmisen avustuksella tai ilman, sopii hyvin. Mutta kaikkia matemaattisia ongelmia ei ole niin helppo paikantaa. Jos koneoppiminen voi löytää laadullisesti uuden algoritmisen idean, hän sanoi, "tämä olisi silloin pelin muuttaja."
