Умножение матриц — фундаментальная математическая операция, лежащая в основе всего: от компьютерной графики и нейронных сетей до квантовой физики. Долгое время совершенствование алгоритмов этой операции считалось колоссальной задачей, однако исследователям из DeepMind удалось установить новый рекорд, превзошедший результаты полувековой давности. Используя систему AlphaTensor, разработчики доказали, что искусственный интеллект способен не только находить более эффективные методы вычислений, но и становиться полноценным соавтором в фундаментальных математических открытиях.
📈 Проблема полувековой давности 1:09
Традиционный метод умножения матриц, который изучают в рамках линейной алгебры, базируется на алгоритме, известном уже несколько столетий.
- При стандартном подходе умножение двух матриц $n \times n$ требует $n^3$ операций умножения.
- Для матриц $2 \times 2$ такой метод требует 8 шагов умножения.
Увеличение размера матриц приводит к экспоненциальному росту времени вычислений: если удвоить размер матрицы, время вычислений увеличится в 8 раз. В 1969 году немецкий математик Фолькер Штрассен (Volker Strassen) предложил алгоритм, сокращающий количество шагов умножения для матриц $2 \times 2$ с восьми до семи. Хотя дополнительные операции сложения в этом методе выглядят сложнее, для больших матриц выигрыш в скорости становится значительным, так как алгоритм можно рекурсивно применять к вложенным фрагментам.
Год спустя исследователь IBM Шмуэль Виноград доказал, что умножение матриц $2 \times 2$ невозможно выполнить менее чем за семь шагов, подтвердив оптимальность алгоритма Штрассена. Этот результат оставался непревзойденным более 50 лет.
🤖 Прорыв AlphaTensor 3:45
Компания DeepMind, известная своими успехами в обучении ИИ играм (например, победой AlphaGo над Ли Седолем в 2016 году), решила применить машинное обучение к задаче поиска оптимального умножения матриц. Исследователи предположили, что эта задача отлично подходит для техник машинного обучения.
Для решения была создана система AlphaTensor, построенная на базе алгоритма обучения с подкреплением AlphaZero.
- Система обучалась, играя в «игру», где целью было разложение трехмерного тензора на минимальное количество тензоров ранга 1.
- Каждый тензор ранга 1 соответствовал одному шагу умножения, поэтому минимизация количества таких тензоров прямо соответствовала ускорению вычислений.
- Поиск велся в пространстве, где количество возможных разложений тензора для матрицы $3 \times 3$ превышает число атомов во Вселенной.
В результате обучения AlphaTensor всего за несколько минут переоткрыл алгоритм Штрассена, а затем пошел дальше. В октябре 2022 года система нашла алгоритм для матриц $4 \times 4$ (в поле с элементами 0 или 1), требующий всего 47 умножений вместо 64 в стандартном методе или 49 в методе Штрассена.
🤝 Человек и ИИ: новая эра математики 11:13
Возникает закономерный вопрос: сделают ли подобные программы математиков ненужными? Ученые, работавшие над проектом, убеждены, что нет.
По словам разработчиков, AlphaTensor служит мощным инструментом, помогающим направлять интуицию исследователей. Эффективность такого сотрудничества подтвердилась практически сразу после публикации результатов в журнале Nature. Австрийские математики Мануэль Кауэрс и Якоб Мосбауэр использовали предложенный ИИ алгоритм для умножения матриц $5 \times 5$ (96 шагов) в качестве отправной точки.
Используя метод AlphaTensor как базу, исследователи смогли найти способ сократить количество шагов с 96 до 95, что было оформлено в отдельной научной публикации. Эксперты подчеркивают, что истинный потенциал заключается в коллаборации технологий и человеческого интеллекта, где ИИ расширяет возможности людей, позволяя достигать новых высот в науке.
