Исследовать
Первое распространение AlphaZero на математику открывает новые возможности для исследований
Алгоритмы помогали математикам выполнять фундаментальные операции на протяжении тысячелетий. Древние египтяне создали алгоритм умножения двух чисел без использования таблицы умножения, а греческий математик Евклид описал алгоритм вычисления наибольшего общего делителя, который используется до сих пор.
Во времена Золотого века ислама персидский математик Мухаммад ибн Муса аль-Хорезми разработал новые алгоритмы для решения линейных и квадратных уравнений. Фактически, имя аль-Хорезми, переведенное на латынь как Алгоритми, привело к термину алгоритм. Но, несмотря на то, что сегодня алгоритмы знакомы – они используются во всем обществе – от школьной алгебры до передовых научных исследований – процесс открытия новых алгоритмов невероятно сложен и является примером удивительных способностей человеческого разума к рассуждению.
В нашем бумагаопубликовано сегодня в журнале Nature, мы представляем АльфаТензор, первая система искусственного интеллекта (ИИ) для обнаружения новых, эффективных и доказуемо правильных алгоритмов для фундаментальных задач, таких как умножение матриц. Это проливает свет на 50-летний открытый вопрос математики о поиске самого быстрого способа умножения двух матриц.
Эта статья является ступенькой в миссии DeepMind по развитию науки и решению наиболее фундаментальных проблем с использованием ИИ. Наша система AlphaTensor основана на AlphaZero, агенте, который продемонстрировал сверхчеловеческие способности в настольных играх, таких как шахматы, го и сёги, и эта работа впервые показывает путь AlphaZero от игр до решения нерешенных математических задач.
Умножение матрицы
Умножение матриц — одна из простейших операций алгебры, которую обычно преподают на уроках математики в средней школе. Но за пределами классной комнаты эта скромная математическая операция имеет огромное влияние в современном цифровом мире и повсеместно используется в современных компьютерах.
Пример процесса умножения двух матриц 3х3.
Эта операция используется для обработки изображений на смартфонах, распознавания речевых команд, создания графики для компьютерных игр, запуска моделирования для прогнозирования погоды, сжатия данных и видео для обмена в Интернете и многого другого. Компании по всему миру тратят много времени и денег на разработку вычислительного оборудования для эффективного умножения матриц. Таким образом, даже незначительное повышение эффективности матричного умножения может иметь широкомасштабное воздействие.
На протяжении веков математики считали, что стандартный алгоритм умножения матриц является лучшим с точки зрения эффективности. Но в 1969 году немецкий математик Фолькер Штрассен шокировал математическое сообщество показав, что существуют лучшие алгоритмы.
Стандартный алгоритм по сравнению с алгоритмом Штрассена, который использует на одно скалярное умножение меньше (7 вместо 8) для умножения матриц 2х2. Для общей эффективности умножение имеет гораздо большее значение, чем сложение.
Изучая очень маленькие матрицы (размером 2×2), он обнаружил гениальный способ объединения элементов матриц для получения более быстрого алгоритма. Несмотря на десятилетия исследований, последовавших за открытием Штрассена, более масштабные версии этой проблемы остались нерешенными – вплоть до того, что неизвестно, насколько эффективно можно перемножать две матрицы размером всего 3×3.
В нашей статье мы исследовали, как современные методы искусственного интеллекта могут способствовать автоматическому открытию новых алгоритмов умножения матриц. Опираясь на развитие человеческой интуиции, AlphaTensor обнаружила алгоритмы, которые более эффективны, чем современные, для многих размеров матриц. Наши алгоритмы, разработанные ИИ, превосходят алгоритмы, разработанные человеком, что является важным шагом вперед в области алгоритмических открытий.
Процесс и ход автоматизации алгоритмических открытий
Во-первых, мы превратили задачу поиска эффективных алгоритмов умножения матриц в однопользовательскую игру. В этой игре доска представляет собой трехмерный тензор (массив чисел), показывающий, насколько далек от правильного текущий алгоритм. С помощью набора разрешенных ходов, соответствующих инструкциям алгоритма, игрок пытается изменить тензор и обнулить его записи. Когда игроку удается это сделать, это приводит к доказуемо правильному алгоритму умножения матриц для любой пары матриц, а его эффективность определяется количеством шагов, предпринятых для обнуления тензора.
Эта игра невероятно сложна — количество возможных алгоритмов, которые нужно рассмотреть, намного превышает количество атомов во Вселенной, даже для небольших случаев матричного умножения. По сравнению с игрой Го, которая осталась вызов ИИ на десятилетияколичество возможных ходов на каждом шаге нашей игры на 30 порядков больше (более 1033 для одного из рассматриваемых нами параметров).
По сути, чтобы хорошо играть в эту игру, нужно найти малейшую иголку в гигантском стоге сена возможностей. Чтобы решить проблемы этой области, которая значительно отличается от традиционных игр, мы разработали несколько важнейших компонентов, включая новую архитектуру нейронной сети, которая включает в себя индуктивные смещения для конкретных задач, процедуру генерации полезных синтетических данных и рецепт использования симметрии игр. проблема.
Затем мы обучили агента AlphaTensor с помощью обучения с подкреплением играть в эту игру, начав без каких-либо знаний о существующих алгоритмах умножения матриц. Посредством обучения AlphaTensor постепенно совершенствуется, заново открывая исторические алгоритмы быстрого умножения матриц, такие как алгоритм Штрассена, в конечном итоге превосходя сферу человеческой интуиции и открывая алгоритмы быстрее, чем известные ранее.
Однопользовательская игра, в которую играет AlphaTensor, цель которой — найти правильный алгоритм умножения матриц. Состояние игры представляет собой кубический массив чисел (отображается серым цветом для 0, синим для 1 и зеленым для -1), обозначающим оставшуюся работу, которую необходимо выполнить.
Например, если традиционный алгоритм, которому учили в школе, умножает матрицу 4×5 на 5×5, используя 100 умножений, и это число было уменьшено до 80 благодаря человеческой изобретательности, AlphaTensor нашел алгоритмы, которые выполняют ту же операцию, используя всего 76 умножений.
Алгоритм, обнаруженный AlphaTensor, использует 76 умножений, что является улучшением по сравнению с современными алгоритмами.
Помимо этого примера, алгоритм AlphaTensor улучшает двухуровневый алгоритм Штрассена в конечном поле впервые с момента его открытия 50 лет назад. Эти алгоритмы умножения небольших матриц можно использовать в качестве примитивов для умножения гораздо больших матриц произвольного размера.
Более того, AlphaTensor также обнаруживает разнообразный набор алгоритмов высочайшей сложности — до тысяч алгоритмов умножения матриц для каждого размера, показывая, что пространство алгоритмов умножения матриц богаче, чем считалось ранее.
Алгоритмы в этом богатом пространстве обладают разными математическими и практическими свойствами. Используя это разнообразие, мы адаптировали AlphaTensor специально для поиска быстрых алгоритмов на конкретном оборудовании, таком как графический процессор Nvidia V100 и Google TPU v2. Эти алгоритмы умножают большие матрицы на 10–20 % быстрее, чем обычно используемые алгоритмы на том же оборудовании, что демонстрирует гибкость AlphaTensor в оптимизации произвольных целей.
AlphaTensor с целью, соответствующей времени выполнения алгоритма. Когда обнаруживается правильный алгоритм умножения матриц, он проверяется на целевом оборудовании, а затем передается обратно в AlphaTensor для изучения более эффективных алгоритмов на целевом оборудовании.
Изучение влияния на будущие исследования и приложения
С математической точки зрения наши результаты могут направить дальнейшие исследования в области теории сложности, целью которых является определение самых быстрых алгоритмов решения вычислительных задач. Исследуя пространство возможных алгоритмов более эффективным способом, чем предыдущие подходы, AlphaTensor помогает нам лучше понять богатство алгоритмов умножения матриц. Понимание этого пространства может открыть новые результаты, помогающие определить асимптотическую сложность умножения матриц. одна из самых фундаментальных открытых проблем в информатике.
Поскольку умножение матриц является ключевым компонентом во многих вычислительных задачах, включая компьютерную графику, цифровую связь, обучение нейронных сетей и научные вычисления, алгоритмы, открытые AlphaTensor, могут сделать вычисления в этих областях значительно более эффективными. Гибкость AlphaTensor для рассмотрения любых задач может также стимулировать новые приложения для разработки алгоритмов, которые оптимизируют такие показатели, как потребление энергии и числовая стабильность, помогая предотвратить лавинообразный рост небольших ошибок округления во время работы алгоритма.
Хотя мы сосредоточились здесь на конкретной проблеме умножения матриц, мы надеемся, что наша статья вдохновит других на использование ИИ для разработки алгоритмов для других фундаментальных вычислительных задач. Наше исследование также показывает, что AlphaZero — это мощный алгоритм, который можно расширить далеко за пределы традиционных игр и помочь решать открытые математические задачи. Опираясь на наши исследования, мы надеемся стимулировать расширение масштабов работы – применение ИИ, чтобы помочь обществу решить некоторые из наиболее важных проблем в математике и других науках.
Более подробную информацию вы можете найти в Репозиторий AlphaTensor на GitHub.