DeepMind slår 50-års matterekord ved bruk av AI; ny rekord faller en uke senere

Matrisemultiplikasjon er i hjertet av mange maskinlæringsgjennombrudd, og det ble bare raskere – to ganger. Forrige uke, DeepMind annonsert den oppdaget en mer effektiv måte å utføre matrisemultiplikasjon, og erobret en 50 år gammel rekord. Denne uken har to østerrikske forskere ved Johannes Kepler University Linz krav de har overgått den nye rekorden med ett skritt.

Matrisemultiplikasjon, som involverer å multiplisere to rektangulære rekker med tall, er ofte funnet i hjertet av talegjenkjenning, bildegjenkjenning, bildebehandling av smarttelefoner, komprimering og generering av datagrafikk. Grafikkbehandlingsenheter (GPUer) er spesielt gode til å utføre matrisemultiplikasjon på grunn av deres massivt parallelle natur. De kan dele et stort matriseproblem i mange deler og angripe deler av det samtidig med en spesiell algoritme.

I 1969, en tysk matematiker ved navn Volker Strassen oppdaget den tidligere beste algoritmen for å multiplisere 4×4-matriser, som reduserer antall trinn som er nødvendige for å utføre en matriseberegning. For eksempel vil det å multiplisere to 4×4-matriser sammen ved hjelp av en tradisjonell skoleromsmetode ta 64 multiplikasjoner, mens Strassens algoritme kan utføre den samme prestasjonen i 49 multiplikasjoner.

Ved å bruke et nevralt nettverk kalt AlphaTensor, oppdaget DeepMind en måte å redusere antallet til 47 multiplikasjoner, og dets forskere publiserte en artikkel om prestasjonen i Nature forrige uke.

Å gå fra 49 trinn til 47 høres ikke så mye ut, men når du tenker på hvor mange billioner av matriseberegninger som finner sted i en GPU hver dag, kan selv trinnvise forbedringer føre til store effektivitetsgevinster, slik at AI-applikasjoner kan kjøres raskere på eksisterende maskinvare.

Når matematikk bare er et spill, vinner AI

AlphaTensor er en etterkommer av AlphaGo (som best verdensmester Gå spillere i 2017) og AlphaZero, som taklet sjakk og shogi. DeepMind kaller AlphaTensor “det “første AI-systemet for å oppdage nye, effektive og beviselig riktige algoritmer for grunnleggende oppgaver som matrisemultiplikasjon.”

For å oppdage mer effektive matrisealgoritmer, satte DeepMind opp problemet som et enkeltspillerspill. Firmaet skrev om prosessen mer detaljert i et blogginnlegg forrige uke:

I dette spillet er brettet en tredimensjonal tensor (array av tall), som fanger opp hvor langt fra riktig den gjeldende algoritmen er. Gjennom et sett med tillatte trekk, tilsvarende algoritmeinstruksjoner, prøver spilleren å modifisere tensoren og nullstille oppføringene. Når spilleren klarer å gjøre det, resulterer dette i en beviselig korrekt matrisemultiplikasjonsalgoritme for et hvilket som helst matrisepar, og effektiviteten fanges opp av antall trinn som tas for å nullstille tensoren.

DeepMind trente deretter AlphaTensor ved å bruke forsterkningslæring for å spille dette fiktive mattespillet – på samme måte som AlphaGo lærte å spille Gå– Og det ble gradvis bedre over tid. Etter hvert gjenoppdaget den Strassens arbeid og andre menneskelige matematikere, så overgikk den dem, ifølge DeepMind.

I et mer komplisert eksempel oppdaget AlphaTensor en ny måte å utføre 5×5 matrisemultiplikasjon i 96 trinn (mot 98 for den eldre metoden). Denne uken, Manuel Kauers og Jakob Moosbauer av Johannes Kepler University i Linz, Østerrike, publiserte en artikkel hevder at de har redusert det antallet med én, ned til 95 multiplikasjoner. Det er ingen tilfeldighet at denne tilsynelatende rekordbrytende nye algoritmen kom så raskt fordi den bygget på DeepMinds arbeid. I papiret deres skriver Kauers og Moosbauer: “Denne løsningen ble oppnådd fra ordningen med [DeepMind’s researchers] ved å bruke en sekvens av transformasjoner som fører til et skjema der en multiplikasjon kan elimineres.”

Teknisk fremgang bygger av seg selv, og med AI som nå søker etter nye algoritmer, er det mulig at andre langvarige matterekorder snart kan falle. I likhet med hvordan datastøttet design (CAD) muliggjør utvikling av mer komplekse og raskere datamaskiner, kan AI hjelpe menneskelige ingeniører med å akselerere sin egen utrulling.