Noua versiune a AlphaZero a descoperit un mod mai rapid de a efectua inmultirea matricelor, o problema esentiala in informatica, ce afecteaza mii de task-uri informatice derulate zilnic.
DeepMind si-a folosit softul de inteligenta artificiala AlphaZero pentru a descoperi un mod mai rapid de a rezolva o problema fundamentala de mamtematica folosita in informatica, reusind astfel sa bata un record ce a rezistat peste 50 de ani.
Problema – inmultirea matricelor – este un tip esential de calcul ce sta la baza multor aplicatii diferite, incepand de la afisarea imaginilor pe un ecran si ajungand pana la simulari fizice complexe. De asemenea, ea este fundamentala si pentru invatarea automata in sine. Accelerarea acestui calcul ar putea avea un efect foarte important asupra a mii de sarcini informatice, reducand costurile si conservand energie.
“Este un rezultat uimitor” spune Francois Le Gall, matematician la Universitatea Nagoiya din Japonia, care nu a fost implicat in aceasta lucrare. “Inmultirea matricelor este folosita peste tot in inginerie. Pentru orice vrei sa rezolvi numeric, folosesti in general matrice” explica el.
In ciuda ubicuitatii acestui calcul, el nu este inca foarte bine inteles. O matrice este pur si simplu o retea de numere, reprezentand orice vrei. Inmultirea a doua matrice implica in general inmultirea randurilor uneia dintre matrice cu coloanele de pe cealalta. Tehnica de baza pentru rezolvarea problemei este predata in liceu. “Este ca un fel de ABC al informaticii” spune Pushmeet Kohli, director al echipei AI pentru Stiinta in cadrul DeepMind.
Insa lucrurile se complica atunci cand incerci sa gasesti o metoda mai rapida de calcul. “Nimeni nu stie care este cel mai bun algoritm pentru rezolvarea sa. Este una dintre cele mai mari probleme deschise din informatica” spune Le Gall.
Explicatia este ca numarul de moduri prin care se pot inmulti doua matrice este mai mare decat numarul de atomi din univers (10 la puterea 33 pentru unele dintre cazurile analizate de cercetatori). “Numarul de actiuni posibile este aproape infinit” spune Thomas Hubert, inginer la DeepMind.
Secretul a fost transformarea problemei intr-un fel de board-game tridimensional, numit TensorGame. Jocul in sine consta in aceasta problema de inmultire care trebuie rezolvata, iar fiecare mutare reprezinta urmatorul pas in rezolvarea acestei probleme. Seria de mutari dintr-un joc reprezinta, asadar, un algoritm.
Cercetatorii au antrenat o noua versiune a AlphaZero, numita AlphaTensor, pentru a juca acest joc. In loc sa invete cea mai buna serie de miscari care se poate face in GO sau in sah, AlphaTensor a invatat cea mai buna serie de pasi ce trebuie parcursa atunci cand inmultesti matrice. El a fost recompensat pentru ca a castigat jocul in cat mai putine miscari.
„Am transformat aceasta problema intr-un joc, tipul nostru preferat de cadru”, spune Hubert, unul dintre cercetatorii principali ai AlphaZero.
Cercetatorii si-au descris munca intr-o lucrare publicata in luna octombrie in “Nature”. Rezultatul principal al muncii lor este acela ca AlphaTensor a descoperit o modalitate de a inmulti doua matrice de ordinul patru, mai rapida decat o metoda conceputa in 1969 de catre matematicianul german Volker Strassen si care nu a mai putut fi imbunatatita niciodata de atunci. Metoda de baza invatata in liceu implica 64 de pasi, iar metoda lui Strassen face 49 de pasi. Acum, AlphaTensor a gasit o modalitate de a face acest calcul in 47 de pasi.
Per ansamblu, AlphaTensor a invins cei mai buni algoritmi existenti pentru peste 70 de dimensiuni diferite de matrice. El a redus numarul de pasi necesari pentru a inmulti doua matrice de ordin 9 de la 511 la 498 si numarul de pasi necesar pentru inmultirea a doua matrice de ordin 11 de la 919 la 896. In multe alte cazuri, AlphaTensor a redescoperit cel mai bun algoritm existent.
Cercetatorii au fost surprinsi de cati algoritmi corecti diferiti a gasit AlphaTensor pentru fiecare dimensiune a matricei. „Este de neimaginat sa vezi ca exista cel putin 14.000 de moduri de a inmulti matrice de ordinul 4”, spune Hussein Fawzi, cercetator la DeepMind.
Dupa ce a cautat cei mai rapizi algoritmi in teorie, echipa DeepMind a vrut sa stie apoi care ar fi cel mai rapid in practica. Fiecare algoritm poate functiona mai bine pe alt hardware, pentru ca cipurile de computer sunt adesea proiectate pentru anumite tipuri de calcul. Echipa DeepMind a folosit AlphaTensor pentru a cauta algoritmi adaptati pentru procesoarele GPU Nvidia V100 si Google TPU, doua dintre cele mai comune cipuri utilizate pentru antrenarea retelelor neuronale.
Algoritmii pe care i-au gasit au fost cu 10 pana la 20% mai rapizi la inmultirea matricelor decat cei folositi in mod normal pe aceste cipuri.
Virginia Williams, cercetator informatician la Laboratorul de Informatica si Inteligenta Artificiala al MIT, este incantata de rezultate. Ea observa ca oamenii folosesc de ceva timp abordari computationale pentru a gasi noi algoritmi pentru inmultirea matricelor – iar multi dintre cei mai rapizi algoritmi existenti au fost conceputi in acest fel. Insa niciunul nu a reusit sa imbunatateasca rezultatele lui Strassen, care au rezistat atat de mult timp.
„Aceasta noua metoda vine cu ceva complet diferit fata de ceea ce au facut ceilalti”, spune Williams. „Ar fi frumos sa ne dam seama daca aceasta noua metoda le inglobeaza de fapt pe toate cele anterioare sau daca le poti combina obtinand astfel ceva si mai bun”.
DeepMind are acum in plan sa foloseasca AlphaTensor pentru a cauta alte tipuri de algoritmi. „Este un nou mod de a face informatica”, spune Kohli.
