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