AI dezvăluie noi posibilități în multiplicarea matricelor

Matematicienilor le place un puzzle bun. Chiar și ceva atât de abstract precum înmulțirea matricelor (tabele bidimensionale de numere) poate fi un joc atunci când încerci să găsești cea mai eficientă modalitate de a face acest lucru. Este un pic ca și cum ai încerca să rezolvi un cub Rubik în cât mai puține mișcări posibil - provocator, dar atrăgător. Cu excepția faptului că pentru un cub Rubik, numărul de mișcări posibile la fiecare pas este 18; pentru înmulțirea matriceală, chiar și în cazuri relativ simple, fiecare pas poate prezenta mai mult de 10¹² opțiuni.

În ultimii 50 de ani, cercetătorii au abordat această problemă în multe feluri, toate bazate pe căutări computerizate ajutate de intuiția umană. Luna trecută, o echipă de la compania de inteligență artificială DeepMind a arătat cum să abordeze problema dintr-o nouă direcție, raportând într-un hârtie in Natură că au antrenat cu succes o rețea neuronală pentru a descoperi noi algoritmi rapidi pentru multiplicarea matricei. Era ca și cum AI-ul ar fi găsit o strategie necunoscută pentru a rezolva un cub Rubik monstruos de complex.

„Este un rezultat foarte frumos”, a spus Josh Alman, un informatician la Universitatea Columbia. Dar el și alți specialiști în multiplicarea matricelor au subliniat, de asemenea, că o astfel de asistență AI va completa mai degrabă decât înlocuiește metodele existente - cel puțin pe termen scurt. „Este ca o dovadă de concept pentru ceva care ar putea deveni o descoperire”, a spus Alman. Rezultatul va ajuta pur și simplu cercetătorii în căutarea lor.

Ca pentru a dovedi ideea, la trei zile după Natură A apărut o lucrare, o pereche de cercetători austrieci au ilustrat modul în care metodele noi și cele vechi s-ar putea completa reciproc. Au folosit o căutare convențională asistată de computer pentru a îmbunătăți în continuare unul dintre algoritmii pe care îi descoperise rețeaua neuronală.

Rezultatele sugerează că, la fel ca procesul de rezolvare a unui cub Rubik, calea către algoritmi mai buni va fi plină de întorsături.

Înmulțirea Matricilor

Înmulțirea matricelor este una dintre cele mai fundamentale și omniprezente operații din întreaga matematică. Pentru a multiplica o pereche de n-de-n matrici, fiecare cu n² elemente, înmulțiți și adăugați aceste elemente împreună în anumite combinații pentru a genera produsul, o treime n-de-n matrice. Rețeta standard pentru înmulțirea a doi n-de-n matricele necesită n³ operații de înmulțire, deci o matrice de 2 cu 2, de exemplu, necesită opt înmulțiri.

Pentru matrice mai mari, cu mii de rânduri și coloane, acest proces devine rapid greoi. Dar în 1969, matematicianul Volker Strassen a descoperit o procedură pentru înmulțirea unei perechi de matrici de 2 cu 2 folosind șapte pași de înmulțire în loc de opt, cu prețul introducerii mai multor pași de adunare.

Algoritmul lui Strassen este complicat în mod inutil dacă doriți doar să înmulțiți o pereche de matrice 2 cu 2. Dar și-a dat seama că va funcționa și pentru matrici mai mari. Asta pentru că elementele unei matrice pot fi ele însele matrici. De exemplu, o matrice cu 20,000 de rânduri și 20,000 de coloane poate fi reimaginată ca o matrice de 2 pe 2 ale cărei patru elemente sunt fiecare 10,000 pe 10,000 de matrice. Fiecare dintre aceste matrici poate fi apoi subdivizată în patru blocuri de 5,000 pe 5,000 și așa mai departe. Strassen și-ar putea aplica metoda pentru a multiplica matrice de 2 cu 2 la fiecare nivel al acestei ierarhii imbricate. Pe măsură ce dimensiunea matricei crește, economiile din mai puține înmulțiri cresc.

Descoperirea lui Strassen a condus la căutarea unor algoritmi eficienți pentru multiplicarea matricelor, care de atunci a inspirat două subcâmpuri distincte. Unul se concentrează pe o întrebare de principiu: dacă vă imaginați să înmulțiți doi n-de-n matrici și lasă n alergați spre infinit, cum se scalează numărul de pași de multiplicare în cel mai rapid algoritm posibil n? record curent pentru cea mai bună scalare, n^2.3728596, aparține lui Alman și Virginia Vassilevska Williams, un informatician la Institutul de Tehnologie din Massachusetts. (Un recent nepublicat preimprimare au raportat o mică îmbunătățire folosind o nouă tehnică.) Dar acești algoritmi sunt de interes pur teoretic, câștigând metode precum cea a lui Strassen doar pentru matrice absurd de mari.

Al doilea subdomeniu gândește la o scară mai mică. La scurt timp după munca lui Strassen, informaticianul israelian american Shmuel Winograd a arătat că Strassen a atins o limită teoretică: nu este posibil să se înmulțească matrici de 2 cu 2 cu mai puțin de șapte pași de înmulțire. Dar pentru toate celelalte dimensiuni de matrice, numărul minim de înmulțiri necesare rămâne o întrebare deschisă. Și algoritmii rapidi pentru matrice mici ar putea avea un impact enorm, deoarece iterațiile repetate ale unui astfel de algoritm ar putea învinge algoritmul lui Strassen atunci când matricele de dimensiuni rezonabile sunt înmulțite.

Din păcate, numărul mare de posibilități este uriaș. Chiar și pentru matrice de 3 pe 3, „numărul de algoritmi posibili depășește numărul de atomi din univers”, a spus Alhussein Fawzi, un cercetător DeepMind și unul dintre liderii noii lucrări.

În fața acestui meniu amețitor de opțiuni, cercetătorii au făcut progrese transformând înmulțirea matricei în ceea ce pare a fi o problemă de matematică total diferită - una care este mai ușor de gestionat de computere. Este posibil să se reprezinte sarcina abstractă de a înmulți două matrici ca un anumit tip de obiect matematic: o matrice tridimensională de numere numită tensor. Cercetătorii pot apoi împărți acest tensor într-o sumă de componente elementare, numite tensori „randul 1”; fiecare dintre acestea va reprezenta un pas diferit în algoritmul de multiplicare a matricei corespunzător. Aceasta înseamnă că găsirea unui algoritm de multiplicare eficient înseamnă reducerea la minimum a numărului de termeni dintr-o descompunere tensorală - cu cât sunt mai puțini termeni, cu atât mai puțini pași implicați.

În acest fel, cercetătorii au descoperit noi algoritmi care se inmultesc n-de-n matrice care utilizează mai puține decât standardul n³ etape de multiplicare pentru multe dimensiuni mici de matrice. Dar algoritmii care depășesc nu numai standardul, ci și algoritmul lui Strassen pentru matrice mici au rămas în afara accesului – până acum.

Joc început

Echipa DeepMind a abordat problema transformând descompunerea tensorilor într-un joc pentru un singur jucător. Au început cu un algoritm de învățare profundă derivat din AlphaGo - un alt AI DeepMind care în 2016 a învățat să joace jocul de societate Go suficient de bine pentru a-i învinge pe cei mai buni jucători umani.

Toți algoritmii de învățare profundă sunt construiți în jurul rețelelor neuronale: rețele de neuroni artificiali sortați în straturi, cu conexiuni care pot varia ca putere reprezentând cât de mult îi influențează fiecare neuron pe cei din stratul următor. Puterea acestor conexiuni este ajustată pe parcursul mai multor iterații ale unei proceduri de antrenament, în timpul căreia rețeaua neuronală învață să transforme fiecare intrare pe care o primește într-o ieșire care ajută algoritmul să-și atingă obiectivul general.

În noul algoritm al DeepMind, numit AlphaTensor, intrările reprezintă pași de-a lungul drumului către o schemă de multiplicare matriceală validă. Prima intrare în rețeaua neuronală este tensorul original de multiplicare a matricei, iar ieșirea sa este tensorul de rang 1 pe care AlphaTensor l-a ales pentru prima sa mișcare. Algoritmul scade acest tensor de rang 1 din intrarea inițială, obținând un tensor actualizat care este reintrodus în rețea ca o nouă intrare. Procesul se repetă până când în cele din urmă fiecare element din tensorul de pornire a fost redus la zero, ceea ce înseamnă că nu mai sunt tensori de rang 1 de scos.

În acel moment, rețeaua neuronală a descoperit o descompunere validă a tensorului, deoarece este garantat matematic că suma tuturor tensoarelor de rang 1 este exact egală cu tensorul de pornire. Iar pașii necesari pentru a ajunge acolo pot fi traduși înapoi în pași ai algoritmului de multiplicare a matricei corespunzător.

Iată jocul: AlphaTensor descompune în mod repetat un tensor într-un set de componente de rang 1. De fiecare dată, AlphaTensor este recompensat dacă găsește o modalitate de a reduce numărul de pași. Dar comenzile rapide către victorie nu sunt deloc intuitive, așa cum uneori trebuie să amesteci o față perfect ordonată pe un cub Rubik înainte de a putea rezolva totul.

Echipa avea acum un algoritm care ar putea, teoretic, să-și rezolve problema. Trebuiau doar să-l antreneze mai întâi.

Noi Căi

Ca toate rețelele neuronale, AlphaTensor are nevoie de o mulțime de date pentru a se antrena, dar descompunerea tensorilor este o problemă notoriu de grea. Au existat puține exemple de descompunere eficiente pe care cercetătorii le-ar putea alimenta rețeaua. În schimb, ei au ajutat algoritmul să înceapă antrenându-l pe problema inversă mult mai ușoară: adunând o grămadă de tensori de rang 1 generați aleatoriu.

„Ei folosesc problema simplă pentru a produce mai multe date pentru problema dificilă”, a spus Michael Littman, un informatician la Universitatea Brown. Combinând această procedură de antrenament înapoi cu învățarea prin întărire, în care AlphaTensor și-a generat propriile date de antrenament în timp ce gafă în căutarea descompunerilor eficiente, a funcționat mult mai bine decât oricare dintre metodele de antrenament în sine.

Echipa DeepMind a antrenat AlphaTensor să descompună tensori reprezentând înmulțirea matricelor până la 12 cu 12. A căutat algoritmi rapizi pentru înmulțirea matricelor de numere reale obișnuite și, de asemenea, algoritmi specifici unei setări mai restrânse cunoscute sub numele de aritmetică modulo 2. (Aceasta este matematică bazată pe doar două numere, deci elementele matricei pot fi doar 0 sau 1 și 1 + 1 = 0.) Cercetătorii încep adesea cu acest spațiu mai restrâns, dar încă vast, în speranța că algoritmii descoperiți aici pot fi adaptați la lucru pe matrice de numere reale.

După antrenament, AlphaTensor a redescoperit algoritmul lui Strassen în câteva minute. Apoi a descoperit până la mii de noi algoritmi rapidi pentru fiecare dimensiune de matrice. Aceștia erau diferiți de cei mai cunoscuți algoritmi, dar aveau același număr de pași de multiplicare.

În câteva cazuri, AlphaTensor a depășit chiar și recordurile existente. Cele mai surprinzătoare descoperiri ale sale s-au întâmplat în aritmetica modulo 2, unde a găsit un nou algoritm pentru înmulțirea matricilor 4 cu 4 în 47 de pași de multiplicare, o îmbunătățire față de cei 49 de pași necesari pentru două iterații ale algoritmului lui Strassen. De asemenea, a depășit cel mai cunoscut algoritm pentru matrice modulo 5 de 5 pe 2, reducând numărul de înmulțiri necesare față de înregistrarea anterioară de 98 la 96. (Dar acest nou record rămâne încă în urma celor 91 de pași care ar fi necesari pentru a le bate). Algoritmul lui Strassen folosind matrici de 5 pe 5.)

Noul rezultat de profil înalt a creat multă entuziasm, cu unii cercetători laude abundente pentru îmbunătățirea status quo-ului bazată pe inteligență artificială. Dar nu toată lumea din comunitatea de multiplicare matrice a fost atât de impresionată. „Am simțit că a fost puțin exagerat”, a spus Vassilevska Williams. „Este un alt instrument. Nu este de genul „Oh, computerele îi bat pe oameni”, știi?”

Cercetătorii au subliniat, de asemenea, că aplicațiile imediate ale algoritmului 4 pe 4 de record ar fi limitate: nu numai că este valabil doar în aritmetica modulo 2, dar și în viața reală există considerații importante în afară de viteză.

Fawzi a fost de acord că, într-adevăr, acesta este doar începutul. „Există mult loc de îmbunătățire și cercetare, iar acesta este un lucru bun”, a spus el.

O întorsătură finală

Cea mai mare putere a AlphaTensor în raport cu metodele bine stabilite de căutare pe computer este, de asemenea, cea mai mare slăbiciune: nu este constrâns de intuiția umană cu privire la cum arată algoritmii buni, așa că nu își poate explica alegerile. Acest lucru face dificil pentru cercetători să învețe din realizările sale.

Dar acesta poate să nu fie un dezavantaj atât de mare pe cât pare. La câteva zile după rezultatul AlphaTensor, matematicianul Manuel Kauers și studentul său absolvent Jakob Moosbauer, ambele de la Universitatea Johannes Kepler din Linz din Austria, au raportat un alt pas înainte.

Când a apărut lucrarea DeepMind, Kauers și Moosbauer erau în proces de căutare a unor noi algoritmi de multiplicare folosind o căutare convențională asistată de computer. Dar, spre deosebire de majoritatea acestor căutări, care încep din nou cu un nou principiu ghid, metoda lor funcționează prin modificarea în mod repetat a unui algoritm existent în speranța de a scoate mai multe economii de multiplicare din acesta. Luând ca punct de plecare algoritmul AlphaTensor pentru matrice modulo 5 de 5 pe 2, ei au fost surprinși să constate că metoda lor a redus numărul de pași de multiplicare de la 96 la 95 după doar câteva secunde de calcul.

AlphaTensor i-a ajutat, de asemenea, să facă o altă îmbunătățire indirect. Anterior, Kauers și Moosbauer nu s-au obosit să exploreze spațiul matricelor 4 pe 4, crezând că nu ar fi posibil să se bată două iterații ale algoritmului lui Strassen. Rezultatul AlphaTensor i-a determinat să-și reconsidere și, după o săptămână de timp de calcul pornind de la zero, metoda lor a generat un alt algoritm în 47 de pași, fără legătură cu cel descoperit de AlphaTensor. „Dacă cineva ne-ar fi spus că există ceva de descoperit pentru 4 pe 4, am fi putut face asta mai devreme”, a spus Kauers. „Dar OK, ei bine, așa funcționează.”

Littman se așteaptă la mai multe astfel de surprize, asemănând situația cu prima dată când un alergător a terminat o milă în mai puțin de patru minute, o performanță care a fost considerată în general imposibilă. „Oamenii au spus: „Oh, stai, putem face asta”, iar acum mulți oameni o pot face”, a spus el.

Privind cu nerăbdare, Fawzi speră să generalizeze AlphaTensor pentru a aborda o gamă mai largă de sarcini matematice și de calcul, așa cum strămoșul său AlphaGo s-a ramificat în cele din urmă în alte jocuri.

Kauers consideră că acesta este adevăratul test de turnesol pentru aplicarea învățării automate la descoperirea de noi algoritmi. El subliniază că căutarea algoritmilor de multiplicare rapidă a matricei este o problemă combinatorie pentru care căutările computerizate, cu sau fără asistență umană, sunt bine potrivite. Dar nu toate problemele matematice sunt atât de ușor de stabilit. Dacă învățarea automată poate descoperi o idee algoritmică nouă din punct de vedere calitativ, a spus el, „acest lucru ar schimba atunci jocul”.