DeepMind, 행렬 곱셈을 1인용 게임으로 바꿔 50년 기록을 깨다

Ars Technica는 2022년 10월 DeepMind가 행렬을 곱하는 더 효율적인 방법을 찾아 50년 된 기록을 깼다고 보도했다. 1969년 폴커 스트라센은 두 4x4 행렬을 학교식 방법의 64번이 아니라 49번의 곱셈으로 계산하는 알고리즘을 찾아냈다. DeepMind는 AlphaTensor라는 신경망을 사용해 이를 47번으로 수행하는 방법을 찾아냈고, 그 결과를 Nature에 발표했다.

DeepMind는 이 문제를 1인용 게임으로 구성했다. '보드'는 현재 알고리즘이 정답에서 얼마나 떨어져 있는지를 담은 3차원 텐서이고, 허용되는 이동은 알고리즘 명령에 해당하며, 플레이어는 텐서의 원소들을 0으로 만들려고 한다. 그렇게 하면 어떤 행렬 쌍에 대해서도 증명 가능하게 올바른 알고리즘이 나오며, 효율성은 단계 수로 표현된다. AlphaGo처럼 강화 학습으로 훈련된 AlphaTensor는 먼저 스트라센의 연구와 다른 수학자들의 연구를 재발견한 뒤 이를 능가했다고 DeepMind는 밝혔다.

5x5 행렬의 경우 AlphaTensor는 기존의 98단계에 맞서 96단계 방법을 찾아냈다. 일주일 뒤 요하네스 케플러 린츠 대학의 마누엘 카우어스와 야코프 모스바우어는 95단계를 보고하며, 자신들의 해법은 한 번의 곱셈을 제거하는 일련의 변환을 통해 DeepMind의 방식에서 얻어졌다고 썼다. Ars는 행렬 곱셈이 음성 및 이미지 인식과 그래픽의 기반에 있으며, 매일 수조 건의 그러한 계산이 GPU에서 실행되므로 작은 절감도 누적될 수 있다고 언급했다.

더 빠른 행렬 알고리즘을 찾는 작업을 텐서 위의 1인용 게임으로 재구성하여, 게임을 하는 AI가 증명 가능하게 올바른 알고리즘을 발견할 수 있게 했다.

올바른 알고리즘은 0으로 줄어든 텐서이므로, 정확성이 게임 규칙에 내장되어 있다.

사용된 단계 수는 명확한 점수이므로, AI는 어떤 이동이 더 짧은 알고리즘으로 이어지는지 학습할 수 있다.

행렬 곱셈은 워낙 널리 쓰이기 때문에 49단계에서 47단계로 줄이는 것만으로도 GPU 규모에서는 중요하다.

발견된 방식을 공개한 덕분에 인간 연구자들이 일주일 안에 그 위에 발전시킬 수 있었다.

연구 문제가 명확한 점수를 가진 게임으로 구성될 수 있다면, 게임을 하는 AI가 그것을 탐색할 수 있고 그 결과는 인간의 추가 개선을 위한 출발점이 될 수 있다.

DeepMind의 발표 일주일 뒤, 오스트리아의 두 연구자는 DeepMind의 방식을 바탕으로 5x5 행렬에 대해 95번 곱셈 방식이라고 주장했다. Ars는 이제 AI가 새로운 알고리즘을 탐색하고 있으므로 다른 오래된 수학 기록들도 곧 깨질 수 있다고 추측했다.