Discovering Faster Matrix Multiplication Algorithms with Reinforcement Learning [in Russian]

Speaker: Alexander Novikov, DeepMind
Slides: https://github.com/bayesgroup/bayesgroup.github.io/blob/master/bmml_sem/2022/Novikov%20et%20al._Discovering%20faster%20matrix%20multiplication%20algorithms%20with%20reinforcement%20learning.pdf

В данной работе мы применили модифицированную программу AlphaZero для поиска быстрых алгоритмов умножения матриц в символьном виде. Мы фокусируемся на поиске быстрых алгоритмов умножения матриц небольшого размера, например, 2х2, а затем используем найденные алгоритмы рекурсивно. В результате, в работе получилось уменьшить число скалярных умножений, которое требуется для умножения матриц разных размеров. Умножения матриц – это билинейная операция, и (как любую линейную операцию можно представить при помощи матрицы) ее можно представить при помощи трехмерного тензора. Низкоранговые разложения данного тензора соответствуют алгоритмам умножения матриц, а ранг разложения соответствует числу скалярных умножений. Таким образом, задача генерации алгоритмов умножения матриц трансформируется в эквивалентную задачу поиска низкоранговых разложений фиксированного тензора. Мы обучили AlphaZero искать эти разложения, применив такие приемы, как генерация синтетических данных, эксплуатация симметрий задачи, обучение одного агента раскладывать несколько разных тензоров одновременно, и использовать нейросетевую архитектуру, заточенную под особенности задачи.
Результаты работы опубликованы в: Fawzi, Alhussein, et al. "Discovering faster matrix multiplication algorithms with reinforcement learning." Nature 610.7930 (2022): 47-53.

Chat: https://drive.google.com/file/d/17shnMdEodA2KWCRypCyXUuwGnvtnl9Xl/view?usp=sharing

Видео Discovering Faster Matrix Multiplication Algorithms with Reinforcement Learning [in Russian] канала BayesGroup.ru