[가상생명연구팀 전동준]

지난 10월 5일, DeepMind는 과학 학술지인 Nature지에 AlphaTensor가 행렬 연산의 최적화 방법을 찾아냈다고 발표하였습니다. 어떤 배경 지식 없이 바둑, 체스, 쇼기(일본 장기)를 학습한 AlphaZero의 확장 버전인 AlphaTensor는 두 행렬을 곱하는 가장 빠른 방법을 찾는 AI입니다. 50년전에 ‘슈트라센 알고리즘(Strassen algorithm)’이 발표된 이후 행렬의 연산에서 더 최적화된 방법이 나오지 않았는데 이를 AlphaTensor가 행렬 곱셈을 위한 효율적인 알고리즘을 찾는 문제를 게임으로 치환하여 해결하였습니다.

Matrix Multipication

행렬 곱셈은 선형대수에서 기본적인 연산중에 하나입니다. 행렬 연산은 이미지, 게임 그래픽 처리, 날씨 예측, 데이터 압축등 다양한 분야에서 기본으로 활용됩니다. 최근에는 GPU, TPU같은 하드웨어의 발전으로 행렬 연산을 더욱 효율적으로 하려는 접근이 많은데, AlphaTensor는 행렬 곱셈 알고리즘 자체를 효율화하여 광범위한 영향을 미칠 수 있다고 기대하고 있습니다.

수학자들은 수세기동안 표준 행렬 곱셈 알고리즘이 가장 효율적인 것이라고 믿고 있었는데, 1969년에 독일의 수학자인 슈트라센이 더욱 나은 알고리즘이 존재하는 것을 보여주었습니다. 슈트라센이 2X2 작은 행렬에서 효율적인 방법을 찾았지만, 더욱 큰 행렬에 대해서는 효율적인 방법들이 제시되지 않았습니다.

Algorithm Discovery

Deepmind는 행렬 곱셈의 효율적인 알고리즘을 찾는 문제를 강화학습 싱글 플레이어 게임으로 바꿨습니다. 게임의 상태는 텐서로 표현됩니다. 플레이어는 알고리즘이 허용한 이동을 통해서 텐서를 수정하고 최종적으로 텐서를 0으로 만드려고 합니다. 각 스텝마다 가장 짧은 경로를 찾기위해 강화학습에서 사용되는 보상을 설정하여 진행합니다.

이 게임은 경우의 수가 많기 때문에 매우 어려운 문제입니다. 바둑의 경우의 수보다 30배는 많습니다. AlphaZero 알고리즘을 이용하여 행렬 곱셈 알고리즘에 대한 사전 지식 없이 시작하여도 슈트라센 알고리즘과 같은 최적화 알고리즘을 찾아내고, 더욱 효율적인 알고리즘도 찾아냅니다.

4X5, 5X5 행렬 곱셈에서 100개의 곱셈을 이용하여 기본적으로 계산할 수 있습니다. 이를 사람이 80개의 계산으로 줄였는데, AlphaTensor는 76개의 곱셈을 사용하는 알고리즘을 찾았습니다.

또한 행렬의 다양한 사이즈에 대해서 최적화된 알고리즘을 찾아내서 이전의 생각보다 다양하다는 것을 발견하였습니다. 이 다양성을 이용하여 V100, TPU v2같은 하드웨어에서 더욱 빠르게 연산할 수 있는 알고리즘을 제시하였고 이는 10~20% 효율적이었습니다.

Future

Deepmind는 AlphaTensor가 발견한 알고리즘이 컴퓨터 그래픽, 디지털 통신, 신경망 학습등의 다양한 분야의 계산을 효율적으로 만들 수 있다고 말합니다. 지금은 행렬 곱셈의 특정 문제에 초점을 맞추었지만, 다른 계산에서도 영감을 주기를 바란다고 말하면서 AlphaZero가 게임 분야뿐만 아니라 수학에서의 문제를 푸는데도 강력한 알고리즘이라고 말하면서 수학과 과학 전반의 중요한 문제들을 풀면서 AI가 사회를 도울 수 있기를 바란다고 말하고 있습니다.

AlphaTensor의 코드는 github에 공개되어 있습니다.

参考

• https://www.deepmind.com/blog/discovering-novel-algorithms-with-alphatensor
• https://www.nature.com/articles/s41586-022-05172-4#Abs1
• https://github.com/deepmind/alphatensor