Игровой искусственный интеллект DeepMind побил 50-летний рекорд компьютерных наук

DeepMind использовала свою настольную игру AI AlphaZero, чтобы найти более быстрый способ решения фундаментальной математической задачи в области компьютерных наук, побив рекорд, который стоял более 50 лет.

Задача умножения матриц — это важнейший тип вычислений, лежащий в основе множества различных приложений, от вывода изображений на экран до моделирования сложной физики. Это также имеет фундаментальное значение для самого машинного обучения. Ускорение этого вычисления могло бы существенно повлиять на тысячи ежедневных вычислительных задач, сократить расходы и сэкономить энергию.

"Это действительно невероятный результат", – говорит Франсуа Ле Галль, математик из Университета Нагои в Японии, который не участвовал в работе. «Матричное умножение используется повсеместно в технике», — говорит он. "Все, что вы хотите решить численно, вы обычно используете матрицы."

Несмотря на повсеместное распространение исчисления, оно до сих пор недостаточно изучено. Матрица — это просто сетка чисел, представляющая все, что вы хотите. Умножение двух матриц вместе обычно включает умножение строк одной на столбцы другой. Базовая техника решения задачи преподается в средней школе. «Это похоже на азбуку информатики, — говорит Пушмит Кохли, руководитель группы ИИ для науки в DeepMind.

Но все становится сложнее, когда вы пытаетесь найти более быстрый метод. «Никто не знает лучшего алгоритма для ее решения», — говорит Ле Галл. "Это одна из самых больших открытых проблем в информатике."

Это связано с тем, что существует больше способов перемножения двух матриц, чем атомов во Вселенной (10 в степени 33 для некоторых случаев, изученных исследователями). «Количество возможных действий почти бесконечно», — объясняет Томас Хьюберт, инженер DeepMind.

Хитрость заключалась в том, чтобы превратить задачу в своеобразную трехмерную настольную игру под названием TensorGame. Доска представляет собой задачу на умножение, которую нужно решить, и каждый ход представляет собой следующий шаг в решении этой задачи. Таким образом, серия ходов, сделанных в игре, представляет собой алгоритм.

Исследователи обучили новую версию AlphaZero под названием AlphaTensor для игры в эту игру. Вместо того, чтобы изучать лучшие последовательности ходов для выполнения в го или шахматах, AlphaTensor изучала наилучшие последовательности шагов для выполнения при умножении матриц. Он был вознагражден за победу в игре за минимальное количество ходов.

"Мы превратили это в игру, нашу любимую платформу", – говорит Хьюберт, один из главных исследователей AlphaZero.

Исследователи описывают свою работу в статье, опубликованной сегодня в журнале Nature. Главный результат заключается в том, что AlphaTensor обнаружил способ умножения двух матриц четыре на четыре вместе, который работает быстрее, чем метод, разработанный в 1969 году немецким математиком Фолькером Штрассеном, который с тех пор никто не смог улучшить. Базовый метод средней школы состоит из 64 шагов; Штрассен делает 49 шагов. AlphaTensor нашел способ сделать это за 47 шагов.

В целом, AlphaTensor превосходит лучшие алгоритмы для более чем 70 различных размеров матриц. Он сократил количество шагов, необходимых для умножения двух матриц 9 на 9, с 511 до 498, а количество шагов, необходимых для умножения двух матриц 11 на 11, с 919 до 896. Во многих других случаях AlphaTensor заново открыл лучший из существующих алгоритмов. .

Исследователи были удивлены количеством различных правильных алгоритмов, найденных AlphaTensor для каждого размера массива. «Удивительно, но существует по меньшей мере 14 000 способов умножения матриц размера четыре на четыре, — говорит исследователь DeepMind Хусейн Фаузи.

Изучив теоретически самые быстрые алгоритмы, команда DeepMind решила выяснить, какие из них окажутся быстрыми на практике. Разные алгоритмы могут лучше работать на разном оборудовании, потому что компьютерные чипы часто разрабатываются для определенных типов вычислений. Команда DeepMind использовала AlphaTensor для исследования подходящих алгоритмов для графических процессоров Nvidia V100 и Google TPU, двух наиболее часто используемых чипов для обучения нейронных сетей. Алгоритмы, которые они нашли, были на 10-20% быстрее при умножении матриц, чем те, которые обычно используются с этими чипами.

Вирджиния Уильямс, специалист по информатике из Лаборатории компьютерных наук и искусственного интеллекта Массачусетского технологического института, воодушевлена ​​результатами. Она отмечает, что люди использовали вычислительные подходы, чтобы найти...