AlphaTensor основан на AlphaZero, агенте, который показал сверхчеловеческую производительность в настольных играх, таких как шахматы, го и сёги, и эта работа впервые показывает путь AlphaZero от игр до решения нерешенных математических задач.
Древние египтяне создали алгоритм умножения двух чисел без использования таблицы умножения, а греческий математик Евклид описал алгоритм вычисления наибольшего общего делителя, который используется до сих пор.
Во времена Золотого века ислама персидский математик Мухаммад ибн Муса аль-Хорезми разработал новые алгоритмы для решения линейных и квадратных уравнений. Фактически, имя аль-Хорезми, переведенное на латынь как Алгоритми, привело к появлению термина «алгоритм». Но, несмотря на знакомство с алгоритмами сегодня, которые используются во всем обществе от школьной алгебры до передовых научных исследований, процесс открытия новых алгоритмов невероятно сложен и является примером удивительных мыслительных способностей человеческого разума.
Они опубликованы в Nature. AlphaTensor — это первая система искусственного интеллекта (ИИ) для обнаружения новых, эффективных и доказуемо правильных алгоритмов для фундаментальных задач, таких как умножение матриц. Это проливает свет на 50-летний открытый вопрос в математике о поиске самого быстрого способа умножения двух матриц.
Обученный с нуля, AlphaTensor обнаруживает алгоритмы умножения матриц, которые более эффективны, чем существующие алгоритмы, разработанные человеком или компьютером. Несмотря на улучшение по сравнению с известными алгоритмами, они отмечают, что ограничением AlphaTensor является необходимость предварительного определения набора потенциальных входов факторов F, что дискретизирует пространство поиска, но может привести к упущению эффективных алгоритмов. Интересным направлением будущих исследований является адаптация AlphaTensor для поиска F. Одной из важных сильных сторон AlphaTensor является его гибкость для поддержки сложных стохастических и недифференцируемых вознаграждений (от ранга тензора до практической эффективности на конкретном оборудовании), в дополнение к поиску алгоритмов. для пользовательских операций в самых разных пространствах (например, в конечных полях). Они считают, что это подтолкнет применение AlphaTensor к разработке алгоритмов, оптимизирующих показатели, которые мы здесь не рассматривали, такие как числовая стабильность или энергопотребление.
Открытие алгоритмов умножения матриц имеет далеко идущие последствия, поскольку умножение матриц лежит в основе многих вычислительных задач, таких как обращение матриц, вычисление определителя и решение линейных систем.
Процесс и прогресс автоматизации алгоритмического обнаружения
Во-первых, они превратили задачу поиска эффективных алгоритмов умножения матриц в игру для одного игрока. В этой игре доска представляет собой трехмерный тензор (массив чисел), отражающий, насколько далек от правильного текущий алгоритм. С помощью набора разрешенных ходов, соответствующих инструкциям алгоритма, игрок пытается изменить тензор и обнулить его элементы. Когда игроку удается это сделать, это приводит к доказуемо правильному алгоритму умножения матриц для любой пары матриц, а его эффективность определяется количеством шагов, предпринятых для обнуления тензора.
Эта игра невероятно сложна — количество возможных алгоритмов для рассмотрения намного превышает количество атомов во Вселенной, даже для небольших случаев матричного умножения. По сравнению с игрой в го, которая десятилетиями оставалась проблемой для ИИ, количество возможных ходов на каждом этапе их игры на 30 порядков больше (выше 10^33 для одной из рассматриваемых ими настроек).
По сути, чтобы хорошо играть в эту игру, нужно определить мельчайшие иголки в гигантском стоге сена возможностей. Чтобы решить проблемы этой области, которая значительно отличается от традиционных игр, мы разработали несколько важных компонентов, включая новую архитектуру нейронной сети, которая включает индуктивные смещения для конкретных задач, процедуру для создания полезных синтетических данных и рецепт использования симметрии проблема.
Затем они обучили агента AlphaTensor, используя обучение с подкреплением, играть в игру, начав без каких-либо знаний о существующих алгоритмах умножения матриц. Благодаря обучению AlphaTensor со временем постепенно совершенствуется, заново открывая исторические алгоритмы быстрого умножения матриц, такие как алгоритм Штрассена, в конечном итоге превосходя область человеческой интуиции и открывая алгоритмы быстрее, чем были известны ранее.
Изучение влияния на будущие исследования и приложения
С математической точки зрения их результаты могут направить дальнейшие исследования в области теории сложности, целью которых является определение самых быстрых алгоритмов для решения вычислительных задач. Изучая пространство возможных алгоритмов более эффективно, чем предыдущие подходы, AlphaTensor помогает нам лучше понять богатство алгоритмов умножения матриц. Понимание этого пространства может открыть новые результаты для определения асимптотической сложности матричного умножения, одной из самых фундаментальных открытых проблем в информатике.
Поскольку умножение матриц является ключевым компонентом во многих вычислительных задачах, охватывающих компьютерную графику, цифровую связь, обучение нейронных сетей и научные вычисления, алгоритмы, открытые AlphaTensor, могут сделать вычисления в этих областях значительно более эффективными. Гибкость AlphaTensor для рассмотрения любых целей может также стимулировать новые приложения для разработки алгоритмов, которые оптимизируют такие показатели, как потребление энергии и числовая стабильность, помогая предотвратить лавинообразное увеличение небольших ошибок округления в процессе работы алгоритма.
Хотя они сосредоточились здесь на конкретной проблеме матричного умножения, мы надеемся, что наша статья вдохновит других на использование ИИ для руководства алгоритмическими открытиями для других фундаментальных вычислительных задач. Их исследование также показывает, что AlphaZero — это мощный алгоритм, который можно расширить далеко за пределы области традиционных игр, чтобы помочь решать открытые математические задачи. Опираясь на наши исследования, они надеются стимулировать большую работу — применение ИИ, чтобы помочь обществу решить некоторые из наиболее важных проблем в математике и других науках.
Природа — обнаружение более быстрых алгоритмов умножения матриц с обучением с подкреплением
Абстрактные
Повышение эффективности алгоритмов фундаментальных вычислений может иметь широкое значение, поскольку может повлиять на общую скорость большого количества вычислений. Умножение матриц — одна из таких примитивных задач, встречающаяся во многих системах — от нейронных сетей до процедур научных вычислений. Автоматическое обнаружение алгоритмов с использованием машинного обучения дает возможность выйти за пределы человеческой интуиции и превзойти лучшие на сегодняшний день алгоритмы, разработанные человеком. Однако автоматизация процедуры обнаружения алгоритма сложна, так как пространство возможных алгоритмов огромно. Здесь мы сообщаем о подходе к глубокому обучению с подкреплением, основанном на AlphaZero1, для обнаружения эффективных и доказуемо правильных алгоритмов умножения произвольных матриц. Наш агент, AlphaTensor, обучен играть в однопользовательскую игру, целью которой является поиск тензорных разложений в конечном факторном пространстве. AlphaTensor обнаружил алгоритмы, которые превосходят самые современные по сложности для многих размеров матриц. Особенно актуален случай матриц 4 × 4 в конечном поле, где алгоритм AlphaTensor впервые, насколько нам известно, улучшает двухуровневый алгоритм Штрассена с момента его открытия 50 лет назад2. Кроме того, мы демонстрируем гибкость AlphaTensor в различных вариантах использования: алгоритмы современной сложности для структурированного умножения матриц и повышенная практическая эффективность за счет оптимизации умножения матриц для времени выполнения на определенном оборудовании. Наши результаты подчеркивают способность AlphaTensor ускорять процесс обнаружения алгоритмов в ряде задач и оптимизировать его по различным критериям.
Брайан Ван - идейный лидер футуризма и популярный научный блоггер с 1 миллионом читателей в месяц. Его блог Nextbigfuture.com занимает первое место среди новостных научных блогов. Он охватывает многие прорывные технологии и тенденции, включая космос, робототехнику, искусственный интеллект, медицину, биотехнологию против старения и нанотехнологии.
Известный тем, что выявляет передовые технологии, он в настоящее время является соучредителем стартапа и сборщиком средств для компаний с высоким потенциалом на ранней стадии. Он является руководителем отдела исследований ассигнований на инвестиции в глубокие технологии и ангел-инвестором в Space Angels.
Часто выступая в корпорациях, он был спикером TEDx, спикером Университета сингулярности и гостем на многочисленных интервью для радио и подкастов. Он открыт для публичных выступлений и консультирования.
