Kunstig intelligens finder nye smarte måder til matrix-multiplikation

Multiplikation af to 2x2 matricer kræver to multiplikationer for hvert element i den endelige matrix udført på den sædvanlige måde. Men det kan udføres smartere med kun syv multiplikationer. Illustration: arkiv

Multiplikation af matricer er ikke kun noget, man plager elever og studerende med i matematikundervisningen. Matrixmultiplikation anvendes i stor stil i forbindelse med billedbehandling, talegenkendelse, computergrafik, vejrsimulationer og meget mere. At kunne multiplicere matricer effektivt og hurtigt er helt afgørende for mange tekniske og videnskabelige applikationer.

En ny artikel i Nature præsenter en række nye algoritmer til matrixmultiplikation, der typisk kan speede beregningerne op med 10-20 pct.

Det opsigtsvækkende er, at de alle er fundet med brug af kunstig intelligens!

I skolen lærer vi at multiplicere matricer som vist i illustrationen i toppen af denne artikel, hvor det kræver otte multiplikationer og fire additioner at udføre multiplikationen af to 2x2 matricer.

I 1969 chokerede den tyske matematiker Volker Strassen den matematiske verden ved at vise, at operationen kunne udføres med kun syv multiplikationer mod, at man til gengæld accepterede at bruge flere additioner.

>
Konventionel multiplikation af to 2x2 matricer kræver otte multiplikationer. Med Volker Strassens metode kan man nøjes med kun syv mod at have flere additioner. For en computer er multiplikationer langt mere krævende end additioner, så Strassens metode er mere effektiv. (Forstør billedet ved at klikke på det) Illustration: DeepMind

Strassen sat gang i eftersøgning af nye algoritmer

Siden da har matematikere og dataloger søgt at finde metoder til multiplikation af også større matricer med færrest muligt antal multiplikationer.

I 1976 beskrev Julian D. Laderman eksempelvis en metode til multiplikation af to 3x3 matricer, der kun kræver 23 multiplikationer frem for de 27, som skal bruges med den sædvandlige skolemetode.

I Nature præsenterer forskere fra DeepMind nu en lang række metoder til effektiv multiplikation af større matricer, der er bedre end de allerede kendte i den forstand, at de bruger færre antal multiplikationer.

Det interessante er, at alle de disse metoder er fundet af et system kaldet AlphaTensor, der er en videreudvikling af AlphaZero, som lærte sig selv at spille en lang række brætspil herunder skak på en overnaturlig måde.

Som eksempel kan nævnes, at multiplikation af en 4x5 matrix med en 5x5 matrix kan udføres med kun 76 multiplikationer. Med den konventionelle metode kræver det 100 multiplikationer, og den hidtil bedste alternative metode kræver 80 multiplikationer.

Et avanceret tensor-spil

AlphaTensor finder nye former for matrixmultiplikation ved en form for spil, som det spiller på lidt samme måde, som AlphaZero lærte sig skak ved at spille mod sig selv.

Metoden er ganske kompliceret, og spillet er langt mere krævende end at lære at spille skak. I matrixmultiplikationsspillet er antallet af mulige træk eksempelvis ved hvert skridt omkring 10^30 gange større end i brætspil.

Under sin oplæring finder matrixmultiplikationsspillet selv frem til Strassens algoritme for 2x2 matricer og Ladermans algoritme for 3x3 matricer (ligesom AlphaZero også fandt frem til de mest benyttede åbninger i skak), men altså også nye og mere effektive algoritmer for multiplikation af større matricer.

Ofte vil de mest effektive former for matrixmultiplikation i praksis afhænge af hvilken form for hardware, man benytter i sin computer. Så udover at finde de former for matrixmultiplikation, der har færrest antal multiplikationer, har DeepMind også fundet de algoritmer, der fungerer bedst på specifik hardware som f.eks. Nvidia V100 GPU og Google TPU v2.

Generelt er de nye algoritmer 10-20 pct. hurtigere end de algoritmer, som bruges i dag.

Matrixmultiplikationsspillet opererer med tensorer.

Multiplikation af 2x2 matricer kan repræsenteres med en 3D tensor, hvor blå angiver tallet 1, mens de øvrige elementer har værdien 0. Tensoren indikerer f.eks., at c1=a1b1 + a2b3, som er vist ved, at tensorelementerne (a1,b1,c1) og (a2,b3,c1) er 1 Illustration: Nature

For en given matrixmultiplikation, f.eks multiplikation af en 4x5 matrix med en 5x5 matrix, tager AlphaTensor en given tensor som input. Spillet går så ud på at opdatere denne tensor, som man kommer frem til en simpel tensor, der fører til samme resultat for matrixmultiplikationen. Mere teknisk skal man finde en ny tensor med en lavere rang.

DeepMind forskerne bemærker, at deres nuværende metode rent faktisk er baseret på, at AlphaTensor skal hjælpes lidt på vej, og metoden derfor i princippet kan overse endnu mere effektive algoritmer end dem, som nu er fundet. Forskerne skriver derfor også, at yderligere forskning og forbedringer kan føre frem til endnu bedre algoritmer for matrixmultiplikation.

De bemærker endvidere, at man kan forestille sig, at principperne bag AlphaTensor bruges til andre optimeringsopgaver f.eks. inden for energiforbrug.

sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først

Jeg syntes ikke en reduktion af antallet af multiplikationer med 20% lyder af meget. Der kan være andre faktorer, der har større betydning, end antallet af multiplikationer. Har vi f.eks. en chip, og sparer nogle multiplikationer, så kan vi måske få et mindre areal - men det er ikke sikkert, for en regulær og simpel struktur, giver måske reelt det laveste areal. Ofte, så er det forsinkelsen - altså vejen fra input til output som er afgørende, og så betyder det ikke noget, at bruge flere multiplikationer, hvis forsinkelse kan reduceres. Det er helt normalt, at man på en chip ødsler med antallet af transistorer og multiplikatorer, for at bringe delayet ned, da delayet er det kritiske. Nogle gange bruges endda flere multiplikatorer til at regne flere værdier ud, for at kunne bruge den korrekte senere. Det interessante er oftest, at kunne parallelisere opgaven, og få svaret så hurtigt som muligt igennem en parallel struktur.

Vi kan sammenligne det med at optimere logiske udtryk: Vi kan få færre gates, og færre transistorer, men ofte bliver forsinkelsen større, end hvis vi anvender en ikke optimeret struktur. Og en ikke optimeret struktur, har måske endda færre skifts, og lavere strømforbrug, fordi at signalerne ikke går igennem komponenter der får signalerne til at skifte flere gange. Det er ikke ualmindeligt, at vi anvender ekstra komponenter, alene for at få en lavere delay, og en hurtigere chip.

  • 0
  • 20

Jeg syntes ikke en reduktion af antallet af multiplikationer med 20% lyder af meget.

I det software system vi byggede til styringen af spejlene i ESO's ELT teleskop ganges en vector med en 6000x10000 matrix 500 gange per sekund per maskine.

En forbedring på 20% ville gøre det muligt at styre spejlene med 600Hz i stedet og det ville iflg forskerne hos ESO give konkrete og målbare forbedringer i billedkvalitet.

Jeg tror primært at disse nye algoritmer er interessante i hardware-implementeringer, hvor en multiplikator kræver kvadratisk flere transistorer end adder.

I software baserede systemer tror jeg ikke umiddelbart at disse nye "moderne" algoritmer vil være hurtigere, både fordi der skal bruges meget mere memory-båndbredde til informationen om hvad der skal ske i hvilken rækkefølge, enten i form af instruktioner eller tabeller, men også fordi de resulterende memory-operationer, iflg. mit øjemål, ikke kan tilrettelægges nær så optimalt for i forhold til den begrænsende båndbredde mellem CPU, Cache og Memory.

Desuden vil det være mere vanskeligt at validere korrektheden af resultatet uden den simple ortogonalitet i en normal MVM. Man være nødt til, at eftervise at alle celler i matricerne dukker op præcis hvor de skal og ingen andre steder. En simpel brute-force kørsel over alle cellepar er ikke garanteret vandtæt, når der også indgår subtraktioner.

  • 30
  • 1

Altså, en 20% optimering er vildt meget!!! Jeg sidder pt med et kæmpe projekt med FEM implementering i C++, hvor netop matrix multiplikation udgør langt størstedelen af beregningerne. Så jeg skal da læse artiklen i Nature omhyggeligt igennem.

  • 24
  • 1

Jeg er lidt skuffet. (Undskyld mig Ram)

Der er enkle metoder, der klarer N^3 multiplikation omkring 10 gange så hurtigt, som konventionelle metoder.

Som jeg viste i mit bachelorprojekt (2011), skal man bruge matrixtransposition:

  • Lad A, B og C være matricer, hvor A*B=C.
  • Lad T(B) være transpositionen af B.
  • Og lad 'x' betegne en liniær multiplikation således at: AxT(B)=C.
  • Alle rækker i A multipliceres med alle rækker i T(B).

Virker fint ved matrixstørrelser op til ca 20000^2. Har ikke prøvet større pga af RAM-størrelsen og regnetiden (for den konventionelle løsning).

Man kan opnå bedre ved bruge af AVX-instruktioner eller tilsvarende.

Er man rigtig doven, kan man nå ca 11 gange hurtigere med Intels Math Kernel Library.

Det, der skuffer mig (i dette forum), er at ingen (inkl Jens D M) har ulejliget sig med at efterprøve metoden.

  • 7
  • 2

I det software system vi byggede til styringen af spejlene i ESO's ELT teleskop ganges en vector med en 6000x10000 matrix 500 gange per sekund per maskine.

Ja, det læste vi om dengang, men en MV er ikke det samme som MM.

Har du i øvrigt lavet dig BOAE (back of an envelope) beregning og sikret dig at det rent faktisk kan lad sig gøre?

Hint: Teoretisk maxmum: freq * cores * CPUantal.

Jeg siger ikke, at du tager fejl; kun at der er detaljer, du ikke har redegjort for her - endnu.

  • 2
  • 6

I det software system vi byggede til styringen af spejlene i ESO's ELT teleskop ganges en vector med en 6000x10000 matrix 500 gange per sekund per maskine.

En forbedring på 20% ville gøre det muligt at styre spejlene med 600Hz i stedet og det ville iflg forskerne hos ESO give konkrete og målbare forbedringer i billedkvalitet.

Jeg tror primært at disse nye algoritmer er interessante i hardware-implementeringer, hvor en multiplikator kræver kvadratisk flere transistorer end adder.

I software baserede systemer tror jeg ikke umiddelbart at disse nye "moderne" algoritmer vil være hurtigere, både fordi der skal bruges meget mere memory-båndbredde til informationen om hvad der skal ske i hvilken rækkefølge, enten i form af instruktioner eller tabeller, men også fordi de resulterende memory-operationer, iflg. mit øjemål, ikke kan tilrettelægges nær så optimalt for i forhold til den begrænsende båndbredde mellem CPU, Cache og Memory.

Desuden vil det være mere vanskeligt at validere korrektheden af resultatet uden den simple ortogonalitet i en normal MVM. Man være nødt til, at eftervise at alle celler i matricerne dukker op præcis hvor de skal og ingen andre steder. En simpel brute-force kørsel over alle cellepar er ikke garanteret vandtæt, når der også indgår subtraktioner.

Jeg er enig med dig i din software vurdering. Mange hardware implementeringer har samme problem som software implementeringer, men de har mulighed for større parallelisme. Ved hardware betyder 20% ikke meget - og man ofre gerne 20% ekstra transistorer på at reducere strømforbruget, eller opnå større hastighed. Kan opnås dobbelt hastighed med 20% ekstra transistorer, er det fuldt investeringen værd. Har vi eksempel et niveau af multiplikationer inden resultatet ved en normal udregning, men to ved vores "sparede" version, så bliver den mere end 20% sløvere.

  • 0
  • 3

https://medium.com/@kilichbekhaydarov/towa...

Idet Log_2 (7) = 2.8 kan ved hjælp af del og hersk (fordi matrix multiplikation kan gøres blokvis) eksponenten 3 i antallet af multiplikationer O(N^3) nøjes med O(N^2.8)

Dette skulle spille en rolle ved dimensioner N > 100 så ja fordi man kan halvere matricerne gentagne gange og på denne måde gennemføre matrix multiplikation som 2x2 blokmatricer så betyder det noget om der er 8 eller kun 7 multiplikations trin i hvert fald hvis matricerne er store

Strassen er ikke hvem som helst (antager jeg) hvis han er den som sammen med Solovay har opfundet Solovay-Strassen's stokastiske sammensatheds-test der hurtigt kan si sammensatte tal bort fra kandidater til primtal selv om den omtalte test ikke er en sikker primtalstest

  • 0
  • 0

God dag alle på kontoret Jeg hedder Thomas Richter, 61 år gamle og invalide siden 2012. De 4 grundregne tekniker har min interesse. jeg er per tilfælde stødt på noget, som ved nærmer undersøgelse viste sig som en ny vej til multiplikation. Dermed kommer jeg ved langt de fleste regnestykker på halvdelen og mmindre enkelte ekstra skrit en her beskrevet. Og med kendskab til sekvensperiode beregning, er det muligt at gange 1000vis af cifre med hinanden i hoved! men hvem har interesse at lægge grækernes hypoteser til side og bytte dem ud med tyske fakta? de må gerne kontaktee mig på "jtrichter@123dk.dk! Venligst Thomas Richter

  • 1
  • 1
Bidrag med din viden – log ind og deltag i debatten