AlphaTensor, se bazează pe AlphaZero, un agent care a demonstrat performanțe supraomenești în jocurile de masă, cum ar fi șahul, Go și shogi, iar această lucrare arată călătoria AlphaZero de la jocuri până la abordarea problemelor matematice nerezolvate pentru prima dată.
Vechii egipteni au creat un algoritm pentru a înmulți două numere fără a necesita o tabelă de înmulțire, iar matematicianul grec Euclid a descris un algoritm pentru a calcula cel mai mare divizor comun, care este încă în uz astăzi.
În timpul Epocii de Aur islamice, matematicianul persan Muhammad ibn Musa al-Khwarizmi a conceput noi algoritmi pentru a rezolva ecuații liniare și pătratice. De fapt, numele lui al-Khwarizmi, tradus în latină ca Algoritmi, a condus la termenul de algoritm. Dar, în ciuda familiarității cu algoritmii de astăzi – folosiți în întreaga societate, de la algebra de clasă până la cercetarea științifică de ultimă oră – procesul de descoperire de noi algoritmi este incredibil de dificil și un exemplu al abilităților uimitoare de raționament ale minții umane.
Au publicat în Nature. AlphaTensor este primul sistem de inteligență artificială (AI) pentru descoperirea de algoritmi noi, eficienți și corect corecti pentru sarcini fundamentale, cum ar fi multiplicarea matricei. Acest lucru pune în lumină o întrebare deschisă de 50 de ani în matematică despre găsirea celei mai rapide modalități de a înmulți două matrici.
Antrenat de la zero, AlphaTensor descoperă algoritmi de multiplicare matrice care sunt mai eficienți decât algoritmii existenți de om și proiectați pe computer. În ciuda îmbunătățirii unor algoritmi cunoscuți, ei observă că o limitare a AlphaTensor este necesitatea de a predefini un set de intrări potențiale de factori F, care discretizează spațiul de căutare, dar poate duce la pierderea unor algoritmi eficienți. O direcție interesantă pentru cercetările viitoare este adaptarea AlphaTensor pentru a căuta F. Un punct forte important al AlphaTensor este flexibilitatea sa de a sprijini recompense stocastice complexe și nediferențiabile (de la rangul tensorului la eficiența practică pe hardware specific), pe lângă găsirea de algoritmi. pentru operații personalizate într-o mare varietate de spații (cum ar fi câmpuri finite). Ei cred că acest lucru va stimula aplicațiile AlphaTensor către proiectarea de algoritmi care optimizează valorile pe care nu le-am luat în considerare aici, cum ar fi stabilitatea numerică sau utilizarea energiei.
Descoperirea algoritmilor de multiplicare a matricei are implicații de anvergură, deoarece multiplicarea matricei se află în centrul multor sarcini de calcul, cum ar fi inversarea matricei, calcularea determinantului și rezolvarea sistemelor liniare.
Procesul și progresul automatizării descoperirii algoritmice
În primul rând, au transformat problema găsirii unor algoritmi eficienți pentru multiplicarea matricelor într-un joc pentru un singur jucător. În acest joc, tabla este un tensor tridimensional (matrice de numere), surprinzând cât de departe de corect este algoritmul curent. Printr-un set de mișcări permise, corespunzătoare instrucțiunilor algoritmului, jucătorul încearcă să modifice tensorul și să anuleze intrările acestuia. Când jucătorul reușește să facă acest lucru, acest lucru are ca rezultat un algoritm de multiplicare a matricei care se dovedește corect pentru orice pereche de matrice, iar eficiența sa este surprinsă de numărul de pași făcuți pentru a zero tensorul.
Acest joc este incredibil de provocator – numărul de algoritmi posibili de luat în considerare este mult mai mare decât numărul de atomi din univers, chiar și pentru cazurile mici de multiplicare a matricei. În comparație cu jocul Go, care a rămas o provocare pentru AI timp de decenii, numărul de mișcări posibile la fiecare pas al jocului lor este cu 30 de ordine de mărime mai mare (peste 10^33 pentru una dintre setările pe care le consideră).
În esență, pentru a juca bine acest joc, trebuie să identifici cele mai mici ace dintr-un car de fân gigantic de posibilități. Pentru a face față provocărilor acestui domeniu, care se îndepărtează semnificativ de jocurile tradiționale, am dezvoltat mai multe componente cruciale, inclusiv o nouă arhitectură de rețea neuronală care încorporează părtiniri inductive specifice problemei, o procedură pentru a genera date sintetice utile și o rețetă pentru a valorifica simetriile problemă.
Apoi au instruit un agent AlphaTensor folosind învățare prin întărire pentru a juca jocul, începând fără nicio cunoștință despre algoritmii de multiplicare matrice existente. Prin învățare, AlphaTensor se îmbunătățește treptat în timp, redescoperind algoritmi istorici de multiplicare rapidă a matricei, cum ar fi ai lui Strassen, depășind în cele din urmă tărâmul intuiției umane și descoperind algoritmi mai rapid decât se știa anterior.
Explorarea impactului asupra cercetărilor și aplicațiilor viitoare
Din punct de vedere matematic, rezultatele lor pot ghida cercetările ulterioare în teoria complexității, care își propune să determine cei mai rapidi algoritmi pentru rezolvarea problemelor de calcul. Explorând spațiul unor posibili algoritmi într-un mod mai eficient decât abordările anterioare, AlphaTensor ajută la progresul înțelegerii noastre asupra bogăției algoritmilor de multiplicare matriceală. Înțelegerea acestui spațiu poate debloca noi rezultate pentru a ajuta la determinarea complexității asimptotice a înmulțirii matricelor, una dintre cele mai fundamentale probleme deschise din informatică.
Deoarece multiplicarea matricei este o componentă de bază în multe sarcini de calcul, care cuprinde grafica pe computer, comunicațiile digitale, formarea rețelelor neuronale și calculul științific, algoritmii descoperiți de AlphaTensor ar putea face calculele în aceste domenii semnificativ mai eficiente. Flexibilitatea AlphaTensor de a lua în considerare orice fel de obiectiv ar putea, de asemenea, să stimuleze noi aplicații pentru proiectarea algoritmilor care optimizează metrici, cum ar fi utilizarea energiei și stabilitatea numerică, ajutând la prevenirea erorilor mici de rotunjire din bulgăre de zăpadă pe măsură ce algoritmul funcționează.
Deși s-au concentrat aici pe problema particulară a înmulțirii matricelor, sperăm că lucrarea noastră îi va inspira pe alții în utilizarea AI pentru a ghida descoperirea algoritmică pentru alte sarcini de calcul fundamentale. Cercetările lor arată, de asemenea, că AlphaZero este un algoritm puternic care poate fi extins cu mult dincolo de domeniul jocurilor tradiționale pentru a ajuta la rezolvarea problemelor deschise de matematică. Bazându-se pe cercetările noastre, ei speră să stimuleze un corp mai mare de muncă - aplicarea AI pentru a ajuta societatea să rezolve unele dintre cele mai importante provocări din matematică și din științe.
Natura – Descoperirea unor algoritmi de multiplicare matrice mai rapidă cu învățare prin întărire
Abstract
Îmbunătățirea eficienței algoritmilor pentru calcule fundamentale poate avea un impact larg răspândit, deoarece poate afecta viteza generală a unui număr mare de calcule. Înmulțirea matricelor este una dintre aceste sarcini primitive, care apare în multe sisteme - de la rețele neuronale la rutine de calcul științifice. Descoperirea automată a algoritmilor folosind învățarea automată oferă perspectiva de a depăși intuiția umană și de a depăși cei mai buni algoritmi actuali proiectați de om. Cu toate acestea, automatizarea procedurii de descoperire a algoritmului este complicată, deoarece spațiul posibililor algoritmi este enorm. Aici raportăm o abordare de învățare prin consolidare profundă bazată pe AlphaZero1 pentru descoperirea unor algoritmi eficienți și corecti pentru multiplicarea matricelor arbitrare. Agentul nostru, AlphaTensor, este antrenat să joace un joc cu un singur jucător în care obiectivul este găsirea descompunerilor tensorilor într-un spațiu finit al factorilor. AlphaTensor a descoperit algoritmi care depășesc complexitatea de ultimă generație pentru multe dimensiuni de matrice. Deosebit de relevant este cazul matricelor 4 × 4 într-un câmp finit, unde algoritmul AlphaTensor îmbunătățește algoritmul cu două niveluri al lui Strassen pentru prima dată, după cunoștințele noastre, de la descoperirea sa în urmă cu 50 de ani2. Prezentăm în continuare flexibilitatea AlphaTensor prin diferite cazuri de utilizare: algoritmi cu complexitate de ultimă generație pentru multiplicarea matricei structurate și eficiența practică îmbunătățită prin optimizarea înmulțirii matricei pentru timpul de execuție pe hardware specific. Rezultatele noastre evidențiază capacitatea AlphaTensor de a accelera procesul de descoperire algoritmică pentru o serie de probleme și de a optimiza pentru diferite criterii.
Brian Wang este un lider gânditor futurist și un popular blogger științific, cu 1 milion de cititori pe lună. Blogul său Nextbigfuture.com este clasat pe locul 1 pe Știrile știrilor. Acoperă multe tehnologii și tendințe perturbatoare, inclusiv spațiu, robotică, inteligență artificială, medicină, biotehnologie anti-îmbătrânire și nanotehnologie.
Cunoscut pentru identificarea tehnologiilor de vârf, el este în prezent co-fondator al unui startup și strângere de fonduri pentru companii cu potențial ridicat în faza incipientă. El este șeful cercetării pentru alocări pentru investiții în tehnologie profundă și un investitor înger la Space Angels.
Vorbitor frecvent la corporații, a fost vorbitor TEDx, vorbitor al Singularity University și invitat la numeroase interviuri pentru radio și podcast-uri. El este deschis vorbirii publice și consilierii angajamentelor.
