Sztuczna inteligencja rozwiązała 50-letni problem matematyków

Zespół DeepMind, którego sztuczna inteligencja AlphaZero używana była do wyszukiwania najlepszych rozwiązań w grach takich jak Go czy szachy, posłużyła tym razem do odkrycia szybszego sposobu na rozwiązanie jednego z fundamentalnych problemów w matematyce oraz informatyce. Udało się, a jednocześnie SI pobiła ponad 50-letni rekord!

Problem, o którym mowa, czyli mnożenie macierzy, jest kluczowym rodzajem obliczeń w wielu różnych aplikacjach, od wyświetlania obrazów na ekranie do złożonych symulacji fizyki. Jest on również fundamentalny dla samego uczenia maszynowego. Przyspieszenie tych obliczeń mogłoby mieć duży wpływ na tysiące codziennych zadań komputerów, obniżając koszty i oszczędzając energię.

To naprawdę niesamowity wynik – mówi François Le Gall, matematyk z Uniwersytetu Nagoya w Japonii, który nie był zaangażowany w prace.

Mnożenie macierzy jest używane wszędzie w inżynierii. W praktycznie każdej metodzie numerycznej używa się matryc – mówi.

Pomimo wszechobecności tych obliczeń, wciąż nie są one dobrze rozumiane. Macierz to po prostu siatka liczb, reprezentująca wszystko, co użytkownik tam podepnie. Mnożenie dwóch macierzy polega zazwyczaj na mnożeniu wierszy jednej z nich z kolumnami drugiej. Ta podstawowa technika rozwiązywania problemu jest w podręcznikach szkolnych.

To jak ABC informatyki – mówi Pushmeet Kohli, szef zespołu DeepMind AI for Science.

Ale sprawy się komplikują, gdy próbujemy znaleźć szybszą metodę. Dzieje się tak dlatego, że istnieje więcej sposobów na pomnożenie dwóch macierzy razem niż jest ziaren piasku na całej Ziemi – 10³³ w niektórych przypadkach, które sprawdzali badacze.

Liczba sposobów jest niemal nieskończona – mówi Thomas Hubert, inżynier w DeepMind.

Sztuczna inteligencja gra w TensorGame

Sztuką było przekształcenie problemu w rodzaj trójwymiarowej gry, zwanej TensorGame. Plansza reprezentuje problem mnożenia do rozwiązania, a każdy ruch reprezentuje kolejny krok w rozwiązaniu tego problemu. Seria ruchów wykonywanych w grze reprezentuje zatem algorytm.

Badacze wytrenowali w tym celu nową wersję AlphaZero, nazwaną AlphaTensor. Sztuczna inteligencja uczyła się najlepszej serii kroków do wykonania podczas mnożenia macierzy i była nagradzana za wygranie gry w jak najmniejszej liczbie ruchów.

Najważniejszym osiągnięciem jest to, że sztuczna inteligencja AlphaTensor odkryła sposób na pomnożenie dwóch matryc 4×4, który jest szybszy niż metoda opracowana w 1969 roku przez niemieckiego matematyka Volkera Strassena zwana algorytmem Strassena. Od tego czasu nikt nie był w stanie znaleźć szybszego rozwiązania problemu. Metoda znana ze szkoły wymaga 64 kroków; metoda Strassena – 49 kroków. Sztuczna inteligencja AlphaTensor znalazła sposób, by zrobić to w 47 krokach!

Ogólnie rzecz biorąc, SI pokonała najlepsze istniejące algorytmy dla ponad 70 różnych rozmiarów macierzy. Zmniejszyła liczbę kroków potrzebnych do pomnożenia dwóch matryc 9×9 z 511 do 498, a liczbę wymaganą do pomnożenia dwóch matryc 11×11 z 919 do 896. W wielu innych przypadkach AlphaTensor odkrył na nowo najlepszy istniejący algorytm.

Badacze byli zaskoczeni tym, jak wiele różnych poprawnych algorytmów dla każdego rozmiaru macierzy znalazła sztuczna inteligencja.

To zadziwiające, że istnieje co najmniej 14 000 sposobów mnożenia macierzy cztery na cztery – mówi Hussein Fawzi, naukowiec z DeepMind.

Po znalezieniu teoretycznie najszybszych algorytmów, zespół DeepMind sprawdził, które z nich będą również szybkie w praktyce. Wykorzystali SI do wyszukania wśród nich metod dostosowanych do możliwości procesorów Nvidia V100 i Google TPU, czyli dwóch układów najczęściej wykorzystywanych do szkolenia sieci neuronowych. Algorytmy, które znalazła sztuczna inteligencja, były od 10 do 20% szybsze w mnożeniu macierzy niż te, które są zwykle używane z tymi chipami.

Sztuczna inteligencja, która wykrywa deepfake z prawie 100% precyzją

Virginia Williams, informatyk z Laboratorium Informatyki i Sztucznej Inteligencji MIT, jest podekscytowana wynikami. Zauważa, że ludzie od jakiegoś czasu używali metod obliczeniowych do znajdowania nowych algorytmów mnożenia macierzy – wiele z istniejących najszybszych algorytmów zostało opracowanych w ten sposób. Ale żaden nie był w stanie pobić wyniku Strassena!

Ta nowa metoda to coś zupełnie innego niż to, co robili inni. Byłoby miło dowiedzieć się, czy ta nowa metoda faktycznie podporządkowuje sobie wszystkie poprzednie, czy też można je połączyć i uzyskać coś jeszcze lepszego – mówi Williams.

Źródło: MIT Technology Review