Sztuczna inteligencja ujawnia nowe możliwości mnożenia macierzy

Matematycy uwielbiają dobre puzzle. Nawet coś tak abstrakcyjnego jak mnożenie macierzy (dwuwymiarowe tablice liczb) może sprawiać wrażenie gry, jeśli spróbujesz znaleźć najbardziej efektywny sposób na zrobienie tego. To trochę jak próba ułożenia kostki Rubika w jak najmniejszej liczbie ruchów — wyzwanie, ale kuszące. Z wyjątkiem tego, że dla kostki Rubika liczba możliwych ruchów na każdym kroku wynosi 18; dla mnożenia macierzy, nawet w stosunkowo prostych przypadkach, każdy krok może przedstawiać więcej niż 10¹² opcje.

W ciągu ostatnich 50 lat naukowcy podeszli do tego problemu na wiele sposobów, a wszystkie opierały się na wyszukiwaniu komputerowym wspomaganym ludzką intuicją. W zeszłym miesiącu zespół DeepMind, firmy zajmującej się sztuczną inteligencją, pokazał, jak rozwiązać problem z nowego kierunku, raportując w papier in Natura że udało im się wytrenować sieć neuronową w celu odkrycia nowych szybkich algorytmów mnożenia macierzy. To było tak, jakby sztuczna inteligencja znalazła nieznaną strategię rozwiązania potwornie złożonej kostki Rubika.

„To bardzo dobry wynik” — powiedział Josha Almana, informatyk z Columbia University. Ale on i inni specjaliści od mnożenia macierzy podkreślili również, że taka pomoc sztucznej inteligencji będzie raczej uzupełniać niż zastępować istniejące metody – przynajmniej w najbliższej przyszłości. „To jak dowód słuszności koncepcji czegoś, co może stać się przełomem” — powiedział Alman. Wynik po prostu pomoże naukowcom w ich poszukiwaniach.

Jakby na dowód tej tezy, trzy dni po Natura ukazał się artykuł, para austriackich badaczy zilustrowała, w jaki sposób nowe i stare metody mogą się uzupełniać. Użyli konwencjonalnego wyszukiwania wspomaganego komputerowo dalsza poprawa jeden z algorytmów odkrytych przez sieć neuronową.

Wyniki sugerują, że podobnie jak w przypadku układania kostki Rubika, droga do lepszych algorytmów będzie pełna zwrotów akcji.

Mnożenie macierzy

Mnożenie macierzy jest jedną z najbardziej podstawowych i wszechobecnych operacji w całej matematyce. Aby pomnożyć parę n-przez-n macierze, każda z n² elementów, mnożysz i dodajesz te elementy razem w określonych kombinacjach, aby wygenerować produkt, trzeci n-przez-n matryca. Standardowy przepis na pomnożenie przez dwa n-przez-n wymaga matryc n³ operacji mnożenia, więc na przykład macierz 2 na 2 wymaga ośmiu mnożeń.

W przypadku większych macierzy, zawierających tysiące wierszy i kolumn, proces ten szybko staje się uciążliwy. Ale w 1969 roku matematyk Volker Strassen odkrył procedurę do mnożenia pary macierzy 2 na 2 przy użyciu siedmiu zamiast ośmiu kroków mnożenia, kosztem wprowadzenia większej liczby kroków dodawania.

Algorytm Strassena jest niepotrzebnie zawiły, jeśli chcesz tylko pomnożyć parę macierzy 2 na 2. Zdał sobie jednak sprawę, że zadziała to również w przypadku większych matryc. To dlatego, że elementy macierzy mogą same być macierzami. Na przykład macierz z 20,000 20,000 wierszy i 2 2 kolumn można ponownie wyobrazić sobie jako macierz 10,000 na 10,000, której cztery elementy to macierze 5,000 5,000 na 2 2. Każdą z tych macierzy można następnie podzielić na cztery bloki o wymiarach XNUMX na XNUMX i tak dalej. Strassen mógł zastosować swoją metodę do pomnożenia macierzy XNUMX na XNUMX na każdym poziomie tej zagnieżdżonej hierarchii. Wraz ze wzrostem rozmiaru macierzy rosną oszczędności wynikające z mniejszej liczby mnożeń.

Odkrycie Strassena doprowadziło do poszukiwania wydajnych algorytmów mnożenia macierzy, które od tego czasu zainspirowały dwie odrębne dziedziny. Jeden koncentruje się na zasadzie: jeśli wyobrażasz sobie mnożenie przez dwa n-przez-n macierze i niech n biegnie w kierunku nieskończoności, jak skaluje się liczba kroków mnożenia w najszybszym możliwym algorytmie n? Aktualny zapis dla najlepszego skalowania, n^2.3728596, należy do Almana i Virginia Wasilewska Williams, informatyk z Massachusetts Institute of Technology. (Ostatnio niepublikowane przedruk zgłosił niewielką poprawę przy użyciu nowej techniki.) Ale te algorytmy mają znaczenie czysto teoretyczne i wygrywają z metodami takimi jak Strassen tylko w przypadku absurdalnie dużych macierzy.

Drugie podobszar myśli na mniejszą skalę. Wkrótce po pracy Strassena, izraelski amerykański informatyk Shmuel Winograd pokazał że Strassen osiągnął teoretyczną granicę: nie jest możliwe pomnożenie macierzy 2 na 2 z mniej niż siedmioma krokami mnożenia. Ale dla wszystkich innych rozmiarów macierzy minimalna liczba wymaganych mnożeń pozostaje kwestią otwartą. A szybkie algorytmy dla małych macierzy mogą mieć ogromny wpływ, ponieważ powtarzane iteracje takiego algorytmu mogą pokonać algorytm Strassena, gdy mnożone są macierze o rozsądnej wielkości.

Niestety, sama liczba możliwości jest ogromna. Nawet w przypadku macierzy 3 na 3 „liczba możliwych algorytmów przekracza liczbę atomów we wszechświecie”, powiedział Alhusseina Fawziego, badacz DeepMind i jeden z liderów nowej pracy.

W obliczu tego zawrotnego menu opcji badacze poczynili postępy, przekształcając mnożenie macierzy w coś, co wydaje się zupełnie innym problemem matematycznym — takim, który jest łatwiejszy w obsłudze dla komputerów. Możliwe jest przedstawienie abstrakcyjnego zadania mnożenia dwóch macierzy jako określonego rodzaju obiektu matematycznego: trójwymiarowej tablicy liczb zwanej tensorem. Badacze mogą następnie rozbić ten tensor na sumę elementarnych składowych, zwanych tensorami „rangi 1”; każdy z nich będzie reprezentował inny krok w odpowiednim algorytmie mnożenia macierzy. Oznacza to, że znalezienie wydajnego algorytmu mnożenia sprowadza się do zminimalizowania liczby wyrazów w rozkładzie tensorowym — im mniej wyrazów, tym mniej wymaganych kroków.

W ten sposób naukowcy odkryli nowe Algorytmy to mnożyć n-przez-n matryce używające mniej niż standardowe n³ kroki mnożenia dla wielu małych rozmiarów macierzy. Ale algorytmy, które przewyższają nie tylko standard, ale także algorytm Strassena dla małych macierzy, pozostawały poza zasięgiem - aż do teraz.

Game On

Zespół DeepMind podszedł do problemu, przekształcając dekompozycję tensora w grę dla jednego gracza. Zaczęli od algorytmu głębokiego uczenia się wywodzącego się z AlphaGo — kolejnej sztucznej inteligencji DeepMind, która pojawiła się w 2016 roku nauczył się grać w grę planszową Go wystarczająco dobrze, aby pokonać najlepszych graczy.

Wszystkie algorytmy głębokiego uczenia są zbudowane wokół sieci neuronowych: sieci sztucznych neuronów posortowanych w warstwy, z połączeniami, które mogą różnić się siłą, reprezentującymi, jak bardzo każdy neuron wpływa na neurony w następnej warstwie. Siła tych połączeń jest dostosowywana w wielu iteracjach procedury szkoleniowej, podczas której sieć neuronowa uczy się przekształcać każde otrzymane dane wejściowe w dane wyjściowe, które pomagają algorytmowi osiągnąć ogólny cel.

W nowym algorytmie DeepMind, nazwany AlphaTensor, dane wejściowe reprezentują kroki na drodze do poprawnego schematu mnożenia macierzy. Pierwszym wejściem do sieci neuronowej jest oryginalny tensor mnożenia macierzy, a jego wyjściem jest tensor rangi 1, który AlphaTensor wybrał jako pierwszy ruch. Algorytm odejmuje ten tensor rangi 1 od początkowego wejścia, uzyskując zaktualizowany tensor, który jest wprowadzany z powrotem do sieci jako nowe wejście. Proces powtarza się, aż w końcu każdy element początkowego tensora zostanie zredukowany do zera, co oznacza, że ​​nie ma już tensorów rangi 1 do wyjęcia.

W tym momencie sieć neuronowa odkryła prawidłową dekompozycję tensorów, ponieważ jest matematycznie gwarantowane, że suma wszystkich tensorów rzędu 1 jest dokładnie równa początkowemu tensorowi. A kroki, które trzeba było wykonać, aby się tam dostać, można przełożyć z powrotem na kroki odpowiedniego algorytmu mnożenia macierzy.

Oto gra: AlphaTensor wielokrotnie rozkłada tensor na zestaw komponentów rangi 1. Za każdym razem AlphaTensor otrzymuje nagrodę, jeśli znajdzie sposób na zmniejszenie liczby kroków. Ale skróty do zwycięstwa wcale nie są intuicyjne, tak jak czasem trzeba ułożyć idealnie ułożoną ściankę na kostce Rubika, zanim uda się rozwiązać całość.

Zespół miał teraz algorytm, który teoretycznie mógłby rozwiązać ich problem. Po prostu musieli go najpierw wyszkolić.

Nowe ścieżki

Podobnie jak wszystkie sieci neuronowe, AlphaTensor potrzebuje dużej ilości danych do trenowania, ale dekompozycja tensorów jest niezwykle trudnym problemem. Było kilka przykładów wydajnych dekompozycji, które naukowcy mogli zasilić sieć. Zamiast tego pomogli w uruchomieniu algorytmu, szkoląc go w zakresie znacznie łatwiejszego problemu odwrotnego: dodawania losowo generowanych tensorów rangi 1.

„Używają łatwego problemu, aby uzyskać więcej danych dla trudnego problemu” – powiedział Michała Littmana, informatyk z Brown University. Połączenie tej procedury treningu wstecznego z uczeniem się ze wzmacnianiem, w którym AlphaTensor generował własne dane treningowe podczas szukania efektywnych dekompozycji, działało znacznie lepiej niż każda z tych metod osobno.

Zespół DeepMind przeszkolił AlphaTensor w rozkładaniu tensorów reprezentujących mnożenie macierzy do 12 na 12. Poszukiwano szybkich algorytmów do mnożenia macierzy zwykłych liczb rzeczywistych, a także algorytmów specyficznych dla bardziej ograniczonego ustawienia znanego jako arytmetyka modulo 2. (Jest to matematyka oparta tylko na dwóch liczbach, więc elementami macierzy mogą być tylko 0 lub 1, a 1 + 1 = 0). Badacze często zaczynają od tej bardziej ograniczonej, ale wciąż ogromnej przestrzeni, w nadziei, że odkryte tutaj algorytmy będą mogły zostać dostosowane praca na macierzach liczb rzeczywistych.

Po treningu AlphaTensor w ciągu kilku minut na nowo odkrył algorytm Strassena. Następnie odkrył do tysięcy nowych szybkich algorytmów dla każdego rozmiaru macierzy. Różniły się one od najbardziej znanych algorytmów, ale miały taką samą liczbę kroków mnożenia.

W kilku przypadkach AlphaTensor pobił nawet istniejące rekordy. Jego najbardziej zaskakujące odkrycia miały miejsce w arytmetyce modulo 2, gdzie znalazł nowy algorytm mnożenia macierzy 4 na 4 w 47 krokach mnożenia, co stanowi ulepszenie w stosunku do 49 kroków wymaganych dla dwóch iteracji algorytmu Strassena. Pobił również najbardziej znany algorytm dla macierzy modulo 5 5 na 2, zmniejszając liczbę wymaganych mnożeń z poprzedniego rekordu z 98 do 96. (Ale ten nowy rekord wciąż pozostaje w tyle za 91 krokami, które byłyby wymagane do pokonania Algorytm Strassena wykorzystujący macierze 5 na 5).

Nowy głośny wynik wywołał wiele emocji, m.in niektórzy badacze gromadząc pochwały na temat poprawy status quo opartej na sztucznej inteligencji. Ale nie wszyscy w społeczności mnożenia macierzy byli pod takim wrażeniem. „Czułem, że to było trochę przesadzone” - powiedziała Vassilevska Williams. „To kolejne narzędzie. To nie jest tak: „Och, komputery pokonały ludzi”, rozumiesz?

Naukowcy podkreślili również, że natychmiastowe zastosowania rekordowego algorytmu 4 na 4 byłyby ograniczone: nie tylko sprawdza się on tylko w arytmetyce modulo 2, ale w prawdziwym życiu poza szybkością ważne są względy.

Fawzi zgodził się, że tak naprawdę to dopiero początek. „Jest dużo miejsca na ulepszenia i badania, i to dobrze” – powiedział.

Ostateczny zwrot akcji

Największa siła AlphaTensor w stosunku do dobrze ugruntowanych metod wyszukiwania komputerowego jest również jego największą słabością: nie jest ograniczona ludzką intuicją co do tego, jak wyglądają dobre algorytmy, więc nie może wyjaśnić swoich wyborów. Utrudnia to naukowcom wyciąganie wniosków z jej osiągnięć.

Ale to może nie być tak duża wada, jak się wydaje. Kilka dni po wyniku AlphaTensor matematyk Manuela Kauersa i jego absolwent Jakuba Moosbauera, obaj z Uniwersytetu Johannesa Keplera w Linz w Austrii, poinformowali o kolejnym kroku naprzód.

Kiedy ukazał się artykuł DeepMind, Kauers i Moosbauer byli w trakcie poszukiwania nowych algorytmów mnożenia przy użyciu konwencjonalnego wyszukiwania wspomaganego komputerowo. Ale w przeciwieństwie do większości takich wyszukiwań, które rozpoczynają się od nowa z nową zasadą przewodnią, ich metoda polega na wielokrotnym poprawianiu istniejącego algorytmu w nadziei na wyciśnięcie z niego większej oszczędności mnożenia. Biorąc za punkt wyjścia algorytm AlphaTensor dla macierzy modulo 5 5 na 2, byli zaskoczeni, gdy odkryli, że ich metoda zmniejszyła liczbę kroków mnożenia z 96 do 95 po zaledwie kilku sekundach obliczeń.

AlphaTensor pomógł im również pośrednio wprowadzić kolejne udoskonalenie. Wcześniej Kauers i Moosbauer nie zawracali sobie głowy badaniem przestrzeni macierzy 4 na 4, wierząc, że nie będzie możliwe pokonanie dwóch iteracji algorytmu Strassena. Wynik AlphaTensor skłonił ich do ponownego rozważenia i po tygodniu obliczeń rozpoczynających się od zera ich metoda ujawniła kolejny 47-etapowy algorytm niezwiązany z tym, który odkrył AlphaTensor. „Gdyby ktoś powiedział nam, że jest coś do odkrycia dla 4 na 4, moglibyśmy to zrobić wcześniej”, powiedział Kauers. „Ale OK, cóż, tak to działa”.

Littman spodziewa się więcej takich niespodzianek, porównując sytuację do sytuacji, w której biegacz po raz pierwszy pokonał milę w mniej niż cztery minuty, co powszechnie uważano za niemożliwe. „Ludzie mówili:„ Och, czekaj, możemy to zrobić ”, a teraz wiele osób może to zrobić” - powiedział.

Patrząc w przyszłość, Fawzi ma nadzieję uogólnić AlphaTensor, aby poradzić sobie z szerszym zakresem zadań matematycznych i obliczeniowych, tak jak jego przodek AlphaGo ostatecznie rozgałęził się na inne gry.

Kauers postrzega to jako prawdziwy papierek lakmusowy zastosowania uczenia maszynowego do odkrywania nowych algorytmów. Wskazuje, że poszukiwanie algorytmów szybkiego mnożenia macierzy jest problemem kombinatorycznym, do którego dobrze nadają się wyszukiwania komputerowe, z pomocą człowieka lub bez niego. Ale nie wszystkie problemy matematyczne są tak łatwe do ustalenia. Jeśli uczenie maszynowe może odkryć jakościowo nową ideę algorytmiczną, powiedział, „byłoby to wtedy przełomem”.