Искусственный интеллект (ИИ), созданный компанией DeepMind, обнаружил новый способ умножения чисел, что стало первым подобным достижением за последние 50 лет. Это открытие может увеличить скорость некоторых вычислений на 20%, поскольку целый ряд программ зависит от выполнения этой задачи в больших масштабах.

Умножение матриц – перемножение двух массивов чисел – является фундаментальной вычислительной задачей, в той или иной степени используемой практически во всех программах, но особенно в графике, ИИ и научном моделировании. Даже небольшое повышение эффективности этих алгоритмов может дать значительный прирост производительности или значительную экономию энергии.

На протяжении многих веков считалось, что наиболее эффективный способ умножения матриц пропорционален количеству перемножаемых элементов, а значит, задача становится пропорционально сложнее для всё более крупных матриц.

Но математик Фолькер Штрассен (Volker Strassen) в 1969 году доказал, что умножение матрицы, состоящей из двух строк по два числа, на другую матрицу такого же размера не обязательно требует восьми умножений и что с помощью хитрого трюка его можно сократить до семи. Такой подход, названный алгоритмом Штрассена, требует дополнительного сложения, но это допустимо, поскольку сложение в компьютере занимает гораздо меньше времени, чем умножение.

Этот алгоритм уже более 50 лет является наиболее эффективным для матриц большинства размеров, хотя были найдены некоторые незначительные улучшения, которые нелегко адаптировать к компьютерному коду. Но теперь ИИ DeepMind обнаружил более быстрый метод, который прекрасно работает на современном оборудовании. Новый ИИ компании – AlphaTensor – начал работу, не зная никаких решений, и ему необходимо было создать работающий алгоритм, который бы решал поставленную задачу за минимальное количество шагов.

Он нашел алгоритм умножения двух матриц из четырех строк по четыре числа, используя всего 47 умножений, что превосходит 49 умножений Штрассена. Также были разработаны улучшенные методы умножения матриц других размеров – всего 70.

AlphaTensor обнаружил тысячи функциональных алгоритмов для матриц каждого размера, в том числе 14000 только для матриц 4×4. Но лишь небольшое число алгоритмов оказалось лучше, чем существующие на сегодняшний день. Исследование основано на AlphaZero, игровой модели DeepMind, и готовилось в течение двух лет.

Хуссейн Фаузи (Hussein Fawzi) из DeepMind говорит, что результаты математически обоснованы, но далеко не интуитивны для человека. "Мы не знаем, почему система пришла именно к такому решению", – говорит он. "Почему это лучший способ умножения матриц? Это непонятно".

"Каким-то образом нейронные сети получают интуитивное представление о том, что выглядит хорошо, а что плохо. Я, честно говоря, не могу сказать, как именно это происходит. Я думаю, что предстоит теоретическая работа над тем, как именно глубокое обучение справляется с подобными задачами", – говорит Фаузи.

DeepMind установил, что алгоритмы могут увеличить скорость вычислений на 10-20% на некоторых аппаратных средствах, таких как графический процессор Nvidia V100 и тензорный процессор Google TPU v2, однако нет гарантии, что этот результат будет достигнут и на обычных устройствах, таких как смартфон или ноутбук.

Джеймс Найт (James Knight) из Сассекского университета (Великобритания) утверждает, что целый ряд программ, выполняемых на суперкомпьютерах и мощном оборудовании, например, исследования в области ИИ и моделирование погоды, по сути, являются матричным умножением в больших масштабах.

"Если бы такой подход был действительно реализован, то это могло бы стать своего рода универсальным ускорением", – говорит он. "Если бы Nvidia реализовала это в своей библиотеке CUDA [инструмент, позволяющий графическим процессорам работать совместно], я бы сказал, что это снизит скорость большинства рабочих нагрузок, связанных с глубоким обучением, на несколько процентов".

Одед Лачиш (Oded Lachish) из Лондонского университета Биркбека считает, что новые алгоритмы могут повысить эффективность широкого спектра программного обеспечения, поскольку умножение матриц является столь распространенной проблемой, и, скорее всего, за ними последуют новые алгоритмы.

"Я полагаю, что мы увидим результаты, полученные с помощью ИИ, и для других задач аналогичного характера, хотя и не столь ключевых, как умножение матриц. “Для такой технологии существует значительная мотивация, поскольку меньшее количество операций в алгоритме означает не только более быстрый результат, но и меньшие затраты энергии”, – говорит он. Если задача решается чуть более эффективно, то ее можно выполнять на менее мощном, менее энергоемком оборудовании или на том же оборудовании за меньшее время, затрачивая меньше энергии.

Впрочем, успехи DeepMind не обязательно означают, что программисты останутся без работы. "Стоит ли программистам беспокоиться? Может быть, в далеком будущем. Автоматическая оптимизация уже десятилетиями применяется в индустрии проектирования микрочипов, и это просто еще один важный инструмент в арсенале программиста", – говорит Лачиш.

Мэтью Спаркес