Telegram Group & Telegram Channel
[DeepMind AlphaTensor] Discovering faster matrix multiplication algorithms with reinforcement learning
Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, David Silver, Demis Hassabis & Pushmeet Kohli
Статья: https://www.nature.com/articles/s41586-022-05172-4
Пост: https://www.deepmind.com/blog/discovering-novel-algorithms-with-alphatensor
Код: https://github.com/deepmind/alphatensor (только найденные алгоритмы и сопутствующее)

После статьи уже прошло сколько-то времени, но она важная, надо разобрать.

В этот раз подход AlphaGo (точнее его вариант Sampled AlphaZero для пространств действий высокой размерности, https://proceedings.mlr.press/v139/hubert21a) применили к задаче нахождения эффективного алгоритма для перемножения матриц.

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

Классический ручной алгоритм перемножения матриц, как его учат в школе-институте, прямолинейный и неэффективный, его сложность O(n^3) операций умножения, а в типовых процессорах это более дорогая операция, чем сложение. Для матриц 2x2 это соответственно 8 умножений. В 1969-м году Штрассен показал, что этот алгоритм неоптимален и предложил алгоритм с 7 умножениями. С тех пор понеслось, и учёные пытаются подобраться к квадратичному алгоритму, текущая SoTA O(n^2.37286) (https://www.quantamagazine.org/mathematicians-inch-closer-to-matrix-multiplication-goal-20210323/). Перебрать все возможные алгоритмы нереально, пространство огромно, поэтому поиск нужно делать по-умному.

Интересна репрезентация проблемы. Задача перемножения матриц заданной размерности сводится к тензорам особого вида (matrix multiplication tensor или Strassen’s tensor), которые могут описывать любую билинейную операцию (то есть бинарную операцию, линейную по каждому из аргументов), каковым перемножение матриц и является.

Кстати, хорошая статья “Tensors in computations” (https://www.stat.uchicago.edu/~lekheng/work/acta.pdf) про тензоры есть в предпоследнем Acta Numerica (https://www.cambridge.org/core/journals/acta-numerica). Там вообще хорошие статьи регулярно, следите за ними. В том же номере 2021 года (https://www.cambridge.org/core/journals/acta-numerica/volume/6A0DA33B45D0E5A6BABD1EF331B5E4F0), кстати, есть и известная статья Михаила Белкина, да и много другого интересного.

Тензор, описывающий произведение любых матриц n×n имеет размерность n^2 × n^2 × n^2 и содержит {0, 1}. Этот тензор описывает какие элементы из входных матриц брать, и куда писать результат. Например, для операции c1 = a1*b1 + a2*b3, где ai, bi, ci — элементы квадратных матриц A, B и C, элементы которых пронумерованы от единицы до макс.индекса слева-направо и сверху-вниз, в единицу выставляются элементы тензора с индексами (a1, b1, c1) и (a2, b3, c1).

Когда есть такой тензор, то его можно декомпозировать в сумму R outer products векторов (тензоров ранга 1) u,v,w, и каждая декомпозиция будет очередным рецептом, как именно выполнить умножение матриц, а число термов в этой сумме, R, будет числом операций умножения в данном рецепте. Таким образом, задача поиска алгоритма перемножения матриц сводится к задаче поиска по декомпозициям соответствующего тензора.



group-telegram.com/gonzo_ML/1146
Create:
Last Update:

[DeepMind AlphaTensor] Discovering faster matrix multiplication algorithms with reinforcement learning
Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, David Silver, Demis Hassabis & Pushmeet Kohli
Статья: https://www.nature.com/articles/s41586-022-05172-4
Пост: https://www.deepmind.com/blog/discovering-novel-algorithms-with-alphatensor
Код: https://github.com/deepmind/alphatensor (только найденные алгоритмы и сопутствующее)

После статьи уже прошло сколько-то времени, но она важная, надо разобрать.

В этот раз подход AlphaGo (точнее его вариант Sampled AlphaZero для пространств действий высокой размерности, https://proceedings.mlr.press/v139/hubert21a) применили к задаче нахождения эффективного алгоритма для перемножения матриц.

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

Классический ручной алгоритм перемножения матриц, как его учат в школе-институте, прямолинейный и неэффективный, его сложность O(n^3) операций умножения, а в типовых процессорах это более дорогая операция, чем сложение. Для матриц 2x2 это соответственно 8 умножений. В 1969-м году Штрассен показал, что этот алгоритм неоптимален и предложил алгоритм с 7 умножениями. С тех пор понеслось, и учёные пытаются подобраться к квадратичному алгоритму, текущая SoTA O(n^2.37286) (https://www.quantamagazine.org/mathematicians-inch-closer-to-matrix-multiplication-goal-20210323/). Перебрать все возможные алгоритмы нереально, пространство огромно, поэтому поиск нужно делать по-умному.

Интересна репрезентация проблемы. Задача перемножения матриц заданной размерности сводится к тензорам особого вида (matrix multiplication tensor или Strassen’s tensor), которые могут описывать любую билинейную операцию (то есть бинарную операцию, линейную по каждому из аргументов), каковым перемножение матриц и является.

Кстати, хорошая статья “Tensors in computations” (https://www.stat.uchicago.edu/~lekheng/work/acta.pdf) про тензоры есть в предпоследнем Acta Numerica (https://www.cambridge.org/core/journals/acta-numerica). Там вообще хорошие статьи регулярно, следите за ними. В том же номере 2021 года (https://www.cambridge.org/core/journals/acta-numerica/volume/6A0DA33B45D0E5A6BABD1EF331B5E4F0), кстати, есть и известная статья Михаила Белкина, да и много другого интересного.

Тензор, описывающий произведение любых матриц n×n имеет размерность n^2 × n^2 × n^2 и содержит {0, 1}. Этот тензор описывает какие элементы из входных матриц брать, и куда писать результат. Например, для операции c1 = a1*b1 + a2*b3, где ai, bi, ci — элементы квадратных матриц A, B и C, элементы которых пронумерованы от единицы до макс.индекса слева-направо и сверху-вниз, в единицу выставляются элементы тензора с индексами (a1, b1, c1) и (a2, b3, c1).

Когда есть такой тензор, то его можно декомпозировать в сумму R outer products векторов (тензоров ранга 1) u,v,w, и каждая декомпозиция будет очередным рецептом, как именно выполнить умножение матриц, а число термов в этой сумме, R, будет числом операций умножения в данном рецепте. Таким образом, задача поиска алгоритма перемножения матриц сводится к задаче поиска по декомпозициям соответствующего тензора.

BY gonzo-обзоры ML статей




Share with your friend now:
group-telegram.com/gonzo_ML/1146

View MORE
Open in Telegram


Telegram | DID YOU KNOW?

Date: |

After fleeing Russia, the brothers founded Telegram as a way to communicate outside the Kremlin's orbit. They now run it from Dubai, and Pavel Durov says it has more than 500 million monthly active users. Channels are not fully encrypted, end-to-end. All communications on a Telegram channel can be seen by anyone on the channel and are also visible to Telegram. Telegram may be asked by a government to hand over the communications from a channel. Telegram has a history of standing up to Russian government requests for data, but how comfortable you are relying on that history to predict future behavior is up to you. Because Telegram has this data, it may also be stolen by hackers or leaked by an internal employee. The fake Zelenskiy account reached 20,000 followers on Telegram before it was shut down, a remedial action that experts say is all too rare. Messages are not fully encrypted by default. That means the company could, in theory, access the content of the messages, or be forced to hand over the data at the request of a government. Russian President Vladimir Putin launched Russia's invasion of Ukraine in the early-morning hours of February 24, targeting several key cities with military strikes.
from us


Telegram gonzo-обзоры ML статей
FROM American