Поиск быстрых алгоритмов умножения матриц при помощи обучения с подкреплением

В данной работе мы применили модифицированную программу AlphaZero для поиска быстрых алгоритмов умножения матриц в символьном виде. Мы фокусируемся на поиске быстрых алгоритмов умножения матриц небольшого размера, например, 2х2, а затем используем найденные алгоритмы рекурсивно. В результате, в работе получилось уменьшить число скалярных умножений, которое требуется для умножения матриц разных размеров. Умножения матриц – это билинейная операция, и (как любую линейную операцию можно представить при помощи матрицы) ее можно представить при помощи трехмерного тензора. Низкоранговые разложения данного тензора соответствуют алгоритмам умножения матриц, а ранг разложения соответствует числу скалярных умножений. Таким образом, задача генерации алгоритмов умножения матриц трансформируется в эквивалентную задачу поиска низкоранговых разложений фиксированного тензора. Мы обучили AlphaZero искать эти разложения, применив такие приемы, как генерация синтетических данных, эксплуатация симметрий задачи, обучение одного агента раскладывать несколько разных тензоров одновременно, и использовать нейросетевую архитектуру, заточенную под особенности задачи.