AlphaTensor opiera się na AlphaZero, agencie, który wykazał się nadludzką wydajnością w grach planszowych, takich jak szachy, Go i Shogi, a ta praca pokazuje drogę AlphaZero od grania w gry do rozwiązywania nierozwiązanych problemów matematycznych po raz pierwszy.
Starożytni Egipcjanie stworzyli algorytm do mnożenia dwóch liczb bez konieczności stosowania tabliczki mnożenia, a grecki matematyk Euklides opisał algorytm do obliczania największego wspólnego dzielnika, który jest nadal używany.
Podczas Złotego Wieku Islamu perski matematyk Muhammad ibn Musa al-Khwarizmi zaprojektował nowe algorytmy do rozwiązywania równań liniowych i kwadratowych. W rzeczywistości imię al-Khwarizmi, przetłumaczone na łacinę jako Algoritmi, doprowadziło do terminu algorytm. Ale pomimo znajomości dzisiejszych algorytmów – używanych w całym społeczeństwie, od algebry w klasie po najnowocześniejsze badania naukowe – proces odkrywania nowych algorytmów jest niezwykle trudny i stanowi przykład niesamowitych zdolności rozumowania ludzkiego umysłu.
Opublikowali w Nature. AlphaTensor to pierwszy system sztucznej inteligencji (AI) do odkrywania nowatorskich, wydajnych i dających się udowodnić poprawnych algorytmów do podstawowych zadań, takich jak mnożenie macierzy. To rzuca światło na 50-letnie otwarte pytanie w matematyce dotyczące znalezienia najszybszego sposobu mnożenia dwóch macierzy.
Wyszkolony od podstaw AlphaTensor odkrywa algorytmy mnożenia macierzy, które są bardziej wydajne niż istniejące algorytmy zaprojektowane przez ludzi i komputery. Pomimo poprawy w stosunku do znanych algorytmów, zauważają, że ograniczeniem AlphaTensor jest konieczność wstępnego zdefiniowania zestawu potencjalnych wpisów czynników F, co dyskretyzuje przestrzeń poszukiwań, ale może prowadzić do pominięcia wydajnych algorytmów. Interesującym kierunkiem przyszłych badań jest przystosowanie AlphaTensor do wyszukiwania F. Jedną z ważnych zalet AlphaTensor jest jego elastyczność w obsłudze złożonych stochastycznych i nieróżnicujących się nagród (od rangi tensora do praktycznej wydajności na określonym sprzęcie), oprócz wyszukiwania algorytmów do niestandardowych operacji w wielu różnych przestrzeniach (takich jak skończone pola). Uważają, że zachęci to zastosowania AlphaTensor do projektowania algorytmów, które optymalizują metryki, których tutaj nie braliśmy pod uwagę, takie jak stabilność numeryczna czy zużycie energii.
Odkrycie algorytmów mnożenia macierzy ma dalekosiężne implikacje, ponieważ mnożenie macierzy leży u podstaw wielu zadań obliczeniowych, takich jak odwracanie macierzy, obliczanie wyznacznika i rozwiązywanie układów liniowych.
Proces i postęp automatyzacji odkrywania algorytmicznego
Najpierw przekształcili problem znalezienia wydajnych algorytmów mnożenia macierzy w grę dla jednego gracza. W tej grze plansza jest trójwymiarowym tensorem (tablicą liczb), która pokazuje, jak daleko od poprawnego jest obecny algorytm. Poprzez zestaw dozwolonych ruchów, odpowiadających instrukcjom algorytmu, gracz próbuje zmodyfikować tensor i wyzerować jego wpisy. Gdy graczowi uda się to zrobić, daje to w wyniku poprawny algorytm mnożenia macierzy dla dowolnej pary macierzy, a jego skuteczność jest wychwytywana przez liczbę kroków podjętych w celu wyzerowania tensora.
Ta gra jest niesamowicie wymagająca – liczba możliwych algorytmów do rozważenia jest znacznie większa niż liczba atomów we wszechświecie, nawet w małych przypadkach mnożenia macierzy. W porównaniu z grą Go, która przez dziesięciolecia pozostawała wyzwaniem dla sztucznej inteligencji, liczba możliwych ruchów na każdym etapie ich gry jest o 30 rzędów wielkości większa (powyżej 10^33 dla jednego z rozważanych przez nich ustawień).
Zasadniczo, aby dobrze grać w tę grę, trzeba zidentyfikować najmniejszą igłę w gigantycznym stogu siana. Aby sprostać wyzwaniom tej dziedziny, która znacznie odbiega od tradycyjnych gier, opracowaliśmy wiele kluczowych komponentów, w tym nowatorską architekturę sieci neuronowej, która zawiera błędy indukcyjne specyficzne dla problemu, procedurę generowania użytecznych danych syntetycznych oraz przepis na wykorzystanie symetrii problem.
Następnie przeszkolili agenta AlphaTensor, korzystając z uczenia się przez wzmacnianie, aby grać w tę grę, zaczynając bez żadnej wiedzy na temat istniejących algorytmów mnożenia macierzy. Dzięki uczeniu się, AlphaTensor stopniowo poprawia się z czasem, odkrywając na nowo historyczne algorytmy szybkiego mnożenia macierzy, takie jak Strassena, ostatecznie przekraczając sferę ludzkiej intuicji i odkrywając algorytmy szybciej niż wcześniej znane.
Badanie wpływu na przyszłe badania i zastosowania
Z matematycznego punktu widzenia ich wyniki mogą ukierunkować dalsze badania w teorii złożoności, których celem jest określenie najszybszych algorytmów rozwiązywania problemów obliczeniowych. Badając przestrzeń możliwych algorytmów w bardziej efektywny sposób niż poprzednie podejścia, AlphaTensor pomaga lepiej zrozumieć bogactwo algorytmów mnożenia macierzy. Zrozumienie tej przestrzeni może odblokować nowe wyniki pomagające określić asymptotyczną złożoność mnożenia macierzy, jednego z najbardziej podstawowych otwartych problemów w informatyce.
Ponieważ mnożenie macierzy jest podstawowym elementem wielu zadań obliczeniowych, obejmujących grafikę komputerową, komunikację cyfrową, trening sieci neuronowych i obliczenia naukowe, algorytmy odkryte przez AlphaTensor mogą znacznie zwiększyć wydajność obliczeń w tych dziedzinach. Elastyczność AlphaTensor w uwzględnianiu dowolnego celu może również pobudzić nowe aplikacje do projektowania algorytmów, które optymalizują metryki, takie jak zużycie energii i stabilność numeryczna, pomagając zapobiegać małym błędom zaokrąglania wynikającym z efektu kuli śniegowej podczas działania algorytmu.
Chociaż skupili się oni tutaj na konkretnym problemie mnożenia macierzy, mamy nadzieję, że nasz artykuł zainspiruje innych do wykorzystania sztucznej inteligencji do kierowania odkryciami algorytmicznymi do innych podstawowych zadań obliczeniowych. Ich badania pokazują również, że AlphaZero to potężny algorytm, który można rozszerzyć daleko poza domenę tradycyjnych gier, aby pomóc w rozwiązywaniu otwartych problemów matematycznych. Opierając się na naszych badaniach, mają nadzieję pobudzić do większej pracy – zastosowania sztucznej inteligencji, aby pomóc społeczeństwu w rozwiązywaniu niektórych z najważniejszych wyzwań w matematyce i naukach ścisłych.
Natura – Odkrywanie szybszych algorytmów mnożenia macierzy z uczeniem przez wzmacnianie
Abstrakcyjny
Poprawa wydajności algorytmów podstawowych obliczeń może mieć szeroki wpływ, ponieważ może wpływać na ogólną szybkość dużej liczby obliczeń. Mnożenie macierzy jest jednym z takich prymitywnych zadań, występującym w wielu systemach — od sieci neuronowych po naukowe procedury obliczeniowe. Automatyczne odkrywanie algorytmów z wykorzystaniem uczenia maszynowego oferuje perspektywę wyjścia poza ludzką intuicję i przewyższenia obecnie najlepszych algorytmów zaprojektowanych przez człowieka. Jednak automatyzacja procedury odkrywania algorytmów jest skomplikowana, ponieważ przestrzeń możliwych algorytmów jest ogromna. W tym miejscu przedstawiamy podejście do uczenia głębokiego wzmacniania oparte na AlphaZero1 do odkrywania wydajnych i potwierdzonych poprawnych algorytmów mnożenia dowolnych macierzy. Nasz agent, AlphaTensor, jest przeszkolony do gry jednoosobowej, w której celem jest znalezienie rozkładu tensorów w przestrzeni czynników skończonych. AlphaTensor odkrył algorytmy, które przewyższają najnowocześniejszą złożoność dla wielu rozmiarów macierzy. Szczególnie istotny jest przypadek macierzy 4 × 4 w polu skończonym, gdzie algorytm AlphaTensor ulepsza dwupoziomowy algorytm Strassena po raz pierwszy, według naszej wiedzy, od czasu jego odkrycia 50 lat temu2. Ponadto prezentujemy elastyczność AlphaTensor w różnych przypadkach użycia: algorytmy o najnowocześniejszej złożoności do strukturalnego mnożenia macierzy i ulepszonej wydajności praktycznej poprzez optymalizację mnożenia macierzy dla środowiska wykonawczego na określonym sprzęcie. Nasze wyniki podkreślają zdolność AlphaTensor do przyspieszania procesu algorytmicznego odkrywania szeregu problemów i optymalizacji pod kątem różnych kryteriów.
Brian Wang jest liderem myśli futurystycznej i popularnym blogerem naukowym z milionem czytelników miesięcznie. Jego blog Nextbigfuture.com zajmuje pierwsze miejsce w rankingu Science News Blog. Obejmuje wiele przełomowych technologii i trendów, w tym przestrzeń kosmiczną, robotykę, sztuczną inteligencję, medycynę, biotechnologię przeciwstarzeniową i nanotechnologię.
Znany z identyfikowania najnowocześniejszych technologii, obecnie jest współzałożycielem startupu i fundraiserem dla firm o wysokim potencjale we wczesnej fazie rozwoju. Pełni funkcję Szefa Działu Badań Alokacji dla inwestycji w głębokie technologie oraz Anioła Inwestora w Space Angels.
Częsty mówca w korporacjach, mówca TEDx, mówca Singularity University i gościnnie w licznych wywiadach dla radia i podcastów. Jest otwarty na wystąpienia publiczne i doradzanie.
