Матричное умножение — фундаментальная операция, лежащая в основе компьютерной графики, нейронных сетей и квантовой физики. Несмотря на её кажущуюся простоту, десятилетиями математики искали способы сделать этот процесс более эффективным. В октябре 2022 года исследователи из лаборатории искусственного интеллекта Google DeepMind совершили прорыв, используя систему AlphaTensor для поиска алгоритмов, превосходящих методы, которые оставались рекордными более 50 лет.
🧮 Стандарт алгоритмов: от школьной программы до Штрассена 1:09
Традиционный метод умножения матриц, изучаемый в курсе линейной алгебры, предполагает умножение элементов строк матрицы А на элементы столбцов матрицы В. При увеличении размера матриц вычислительная сложность такого подхода растет кубически: при удвоении размера матрицы время вычислений увеличивается в восемь раз.
В 1969 году немецкий математик Фолькер Штрассен (Volker Strassen) предложил метод, который позволил перемножать матрицы 2x2, используя семь операций умножения вместо восьми. Хотя дополнительные операции сложения делают этот алгоритм сложнее, общая экономия времени при работе с большими массивами данных оказывается колоссальной. На протяжении полувека метод Штрассена считался эталонным; в 1970 году исследователь из IBM Шмуэль Виноград (Shmuel Winograd) доказал, что для умножения матриц 2x2 невозможно использовать менее семи операций умножения.
🧠 AlphaTensor: ИИ как математический исследователь 3:58
После успеха AlphaGo в 2016 году, когда нейросеть победила чемпиона мира по го Ли Седоля, команда DeepMind решила применить методы обучения с подкреплением (reinforcement learning) к более сложным научным задачам, включая матричное умножение.
Для обучения AlphaTensor исследователи сформулировали задачу как однопользовательскую игру, где «доской» выступает 3D-тензор, описывающий операцию умножения.
- Система использует процесс тензорного разложения, разбивая сложную структуру на более простые составляющие — тензоры ранга один.
- Каждый такой тензор соответствует одному шагу умножения в алгоритме.
- Цель ИИ — найти такую последовательность разложений, которая требует минимального количества операций.
Пространство поиска для этой задачи астрономически велико: даже для матриц 3x3 количество возможных разложений превышает число атомов во Вселенной. Тем не менее, AlphaTensor не только «переоткрыл» алгоритм Штрассена за несколько минут, но и обнаружил принципиально новые методы. В частности, для матриц 4x4 (с элементами 0 или 1) системе удалось снизить количество шагов умножения с 64 (стандарт) и 49 (Штрассен) до 47.
🤝 Человек и машина: будущее математики 11:13
Авторы исследования подчеркивают, что искусственный интеллект не заменяет математиков, а выступает мощным инструментом, помогающим направлять интуицию и находить неожиданные решения.
Эффективность такого симбиоза подтвердилась практически сразу после публикации результатов в журнале Nature. Австрийские математики Мануэль Кауэрс (Manuel Kauers) и Якоб Мосбауэр (Jakob Moosbauer) использовали алгоритм AlphaTensor для матриц 5x5 как отправную точку. Анализируя структуру, предложенную машиной, они обнаружили возможность дополнительного упрощения, сократив число операций с 96 до 95, что было позже опубликовано в архиве препринтов.
