DeepMind izumil nov algoritem za množenje matrik, človek ga je hitro izboljšal

Umetna inteligenca, ki jo razvija DeepMind, je iznašla nov, hitrejši način za množenje matrik. Njihov program AlphaTensor iz družine Alpha je s tem popravil 50 let stari algoritem, nato pa sta ga teden dni pozneje nepričakovano prekosila avstrijska matematika z Univerze v Linzu.

Množenje matrik je izjemno pomembna računska operacija v računalništvu, ki se ponavlja pri obdelavi in izrisu slik, stiskanju, prepoznavanju govora in slik in drugod. Najučinkovitejši pri množenju matrik so grafični procesorji, ki lahko nalogo razkosajo na manjše podnaloge, nato pa se vzporedno ukvarjajo z njimi. Naivno množenje matrik, kot se ga učimo v šoli, terja množenje vsake vrstice z vsakim stolpcem, kar za matriki dimenzij n x n terja n³ operacij množenja. A s premislekom gre tudi hitreje. Nemški matematik Volker Strassen je že leta 1969 odkril algoritem, ki na primer za množenje matrik 2 x 2 namesto osmih potrebuje sedem operacij množenja, za matriki 4 x 4 pa namesto 64 le 49. Njegova zahtevnost ni O(n³), temveč O(n^2,81).

Kasneje so raziskovalci odkrili algoritme s še nižjo zahtevnostjo, a v praksi to ni prineslo pohitritev. Čeprav so imeli nižji eksponent, so bili predfaktorji tako veliki, da bi bili hitrejši le pri tako ogromnih matrikah, ki jih v praksi nikoli ne srečamo. Takšne algoritme imenujemo galaktični algoritmi. Zato se je še vedno uporabljal Strassnov algoritem, ki na račun manj operacij množenja potrebuje več operacij seštevanja, a so te bistveno hitrejše.

AlphaTensor pa je odkril vrsto algoritmov za množenje matrik, ki ljudem niso intuitivni in jih zato človeški raziskovalci še niso odkrili. Večina je bila počasnejših od Strassnovega algoritma, a med njimi je bil tudi hitrejši. Številke so res velike. Za matrike 4x4 je AlphaTensor odkril 14.000 algoritmov. AlphaTensor je odkril algoritme za matrike različnih dimenzij, ki so še malce hitrejši. Testi na Nvidii V100 in Google TPU so pokazali, da je pohitritev 10- do 20-odstotna. Konkretno, namesto 49 operacij množenja na matrikah 4x4 potrebuje novi algoritem le 47 operacij množenja.

Novi algoritem je matematično preverjen in pravilen, čeprav nihče ne ve, kako ga je AlphaTensor lahko odkril in zakaj se ga ni bil domislil noben človek. In ko je že kazalo, da bo to za nekaj časa nov rekord, sta Manuel Kauers in Jakob Moosbauer odkril še en algoritem, ki je za poseben primer še malce hitrejši. Za množenje matrik 5x5 namesto 96 operacij, kolikor jih je potreboval AlphaTensor, zadostuje 95 operacij množenja. Strassnov algoritem jih potrebuje 98. Kauers in Moosbauer sta povedala, da sta kot izhodišče uporabila AlphaTensorjev algoritem in ga še izboljšala. Ljudje torej še niso odslužili.

DeepMind je doslej razvil umetno inteligenco za cel kup problemov, ne le množenje matrik. Njegovi izdelki so igrali go, brali z ustnic, simulirali jedrsko fuzijo, razvozlavali povezave v teoretični matematiki, analizirali starodavna besedila, izračunavali zvijanje beljakovin itd. Zdi se, da se lahko lotijo skoraj kateregakoli problema in izboljšajo človeške rešitve. Zadnje odkritje avstrijskih matematikov pa kaže, da je človek še vedno nujen, da osmisli rezultate in jih morda še izboljša. Računalniki so pač naši pomočniki.