강화학습으로 행렬 곱셈 알고리즘 발견, DeepMind가 Nature 표지에 등장, AlphaTensor 출시

알고리즘은 수천 년 동안 수학자들이 기본 작업을 수행하는 데 도움을 주었습니다. 오래 전, 고대 이집트인들은 구구단 없이 두 숫자를 곱하는 알고리즘을 발명했습니다. 그리스 수학자 유클리드는 오늘날에도 여전히 사용되는 최대 공약수를 계산하는 알고리즘을 설명했습니다. 이슬람 황금 시대에 페르시아 수학자 무함마드 이븐 무사 알콰리즈미(Muhammad ibn Musa al-Khwarizmi)는 후속 연구에 큰 영향을 미칠 1차 및 2차 방정식을 풀기 위한 새로운 알고리즘을 고안했습니다.

실제로 알고리즘이라는 단어의 출현에 대한 속담이 있습니다. 페르시아 수학자 Muhammad ibn Musa al-Khwarizmi의 이름에서 al-Khwarizmi라는 단어는 라틴어로 Algoritmi로 번역되어 알고리즘 1. 단어. 그러나 오늘날 우리는 알고리즘에 대해 매우 익숙하지만 교실에서 배울 수 있고 과학 연구 분야에서도 종종 접하게 됩니다. 사회 전체가 알고리즘을 사용하고 있는 것 같지만 새로운 알고리즘을 발견하는 과정은 매우 어렵습니다. . ​

이제 DeepMind는 AI를 사용하여 새로운 알고리즘을 발견합니다.

Nature 최신호 표지 논문 "강화 학습을 통해 더 빠른 행렬 곱셈 알고리즘 발견"에서 DeepMind는 AlphaTensor를 제안하며 행렬 곱셈과 같은 기본 작업을 위한 새롭고 효율적이며 증명 가능한 알고리즘을 최초로 발견했다고 밝혔습니다. .올바른 알고리즘을 갖춘 인공지능 시스템. 간단히 말해, AlphaTensor를 사용하면 새로운 알고리즘을 발견할 수 있습니다. 이 연구는 50년 동안 해결되지 않은 수학 문제, 즉 두 행렬을 곱하는 가장 빠른 방법을 찾는 문제를 조명합니다.

• 논문 주소: https://www.nature.com/articles/s41586-022-05172-4
• GitHub 주소: https:/ /github.com/deepmind/alphatensor ​

AlphaTensor는 체스, 바둑, 장기와 같은 보드 게임에서 인간을 이길 수 있는 에이전트인 AlphaZero를 기반으로 구축되었습니다. 이 작품은 AlphaZero가 게임에 사용되던 것에서 처음으로 미해결 수학 문제를 해결하는 데 사용되는 것으로 전환되는 과정을 보여줍니다. ​

행렬 곱셈

행렬 곱셈은 대수학에서 가장 간단한 연산 중 하나이며 일반적으로 고등학교 수학 수업에서 배웁니다. 그러나 교실 밖에서는 이 보잘것없는 수학적 연산이 현대 디지털 세계에 큰 영향을 미쳤으며 현대 컴퓨팅 어디에나 존재합니다.

두 개의 3x3 행렬을 곱하는 예입니다. ​

행렬 곱셈은 스마트폰의 이미지 처리, 음성 명령 인식, 컴퓨터 게임용 그래픽 생성 등 우리 생활 곳곳에 숨겨져 있다는 사실을 눈치채지 못했을 수도 있습니다. 이 모든 것이 그 뒤에서 작동합니다. 전 세계의 기업들은 행렬 곱셈을 효율적으로 해결하기 위해 컴퓨팅 하드웨어를 개발하는 데 막대한 시간과 돈을 기꺼이 투자하고 있습니다. 따라서 행렬 곱셈 효율이 조금만 향상되더라도 광범위한 효과를 가져올 수 있습니다.

수세기 동안 수학자들은 표준 행렬 곱셈 알고리즘을 가장 효율적인 알고리즘으로 간주해 왔습니다. 그러나 1969년 독일 수학자 볼켄 스트라센(Volken Strassen)은 더 나은 알고리즘이 존재한다는 것을 증명하여 수학계에 충격을 주었습니다.

표준 알고리즘과 Strassen 알고리즘을 비교하면 후자는 곱셈 연산이 한 번 덜 필요한(7배) 반면, 전자는 8배가 필요하므로 전반적인 효율성이 크게 향상됩니다. ​

스트라센은 매우 작은 행렬(2x2 크기)을 연구하여 행렬의 항을 결합하여 더 빠른 알고리즘을 생성하는 영리한 방법을 발견했습니다. 이후 수십 년 동안 연구자들은 더 큰 행렬을 연구해 왔지만 3x3 행렬을 곱하는 효율적인 방법을 찾는 것조차 아직 해결되지 않았습니다.

DeepMind의 새로운 연구에서는 현대 AI 기술이 어떻게 새로운 행렬 곱셈 알고리즘의 자동 발견을 주도하는지 탐구합니다. 인간 직관의 발전을 기반으로 AlphaTensor가 발견한 알고리즘은 더 큰 행렬에 대한 많은 SOTA 방법보다 더 효율적입니다. 이 연구는 AI가 설계한 알고리즘이 인간이 설계한 알고리즘보다 성능이 뛰어나다는 것을 보여 주며, 이는 알고리즘 발견 분야에서 중요한 진전입니다.

알고리즘 발견 자동화의 과정과 진행

먼저 행렬 곱셈을 위한 효율적인 알고리즘을 발견하는 문제를 싱글 플레이어 게임으로 전환하세요. 그 중 보드(board)는 현재 알고리즘이 얼마나 정확한지 파악하는 데 사용되는 3차원 텐서(숫자 배열)입니다. 알고리즘의 지침에 따라 허용된 일련의 이동을 통해 플레이어는 텐서를 수정하고 해당 항목을 0으로 되돌리려고 시도합니다.

플레이어가 이 작업을 수행하면 모든 행렬 쌍에 대해 입증 가능한 올바른 행렬 곱셈 알고리즘이 생성되고 그 효율성은 텐서를 0으로 만드는 단계 수로 측정됩니다.

이 게임은 매우 도전적이며 고려할 수 있는 알고리즘의 수는 행렬 곱셈만큼 작은 경우에도 우주의 원자 수보다 훨씬 많습니다. 수십 년 동안 AI의 도전이었던 바둑 게임과 비교하면 이 게임은 한 동작당 가능한 동작 수가 30배 더 많습니다(DeepMind가 고려한 한 설정은 10^33+였습니다.)

이를 해결하기 위해 DeepMind가 개발했습니다. 문제별 귀납적 편향을 통합하는 새로운 신경망 아키텍처, 유용한 합성 데이터를 생성하는 절차, 문제 대칭성을 활용하는 방법을 포함하여 기존 게임과 크게 다른 도메인의 과제를 해결하기 위한 몇 가지 주요 구성 요소입니다.

다음으로 DeepMind는 기존 행렬 곱셈 알고리즘에 대한 지식 없이 시작하여 강화 학습 에이전트인 AlphaTensor를 훈련하여 게임을 플레이했습니다. 학습을 통해 AlphaTensor는 시간이 지남에 따라 점진적으로 개선되어 역사적으로 빠른 행렬 알고리즘(예: Strassen의 알고리즘)을 재발견하고 이전에 알려진 것보다 빠른 알고리즘을 발견합니다.

AlphaTensor 올바른 행렬 곱셈 알고리즘을 찾는 것이 목표인 싱글 플레이어 게임입니다. 게임 상태는 수행해야 할 남은 작업을 나타내는 숫자의 입방체 배열(회색은 0, 파란색은 1, 녹색은 -1을 나타냄)입니다. ​

예를 들어, 학교에서 가르치는 기존 알고리즘이 100번의 곱셈을 사용하여 4x5 및 5x5 행렬을 곱할 수 있다면 인간의 독창성은 이 숫자를 80배로 줄일 수 있습니다. 이에 비해 AlphaTensor가 발견한 알고리즘은 아래 이미지와 같이 76번의 곱셈만을 사용하여 동일한 연산을 수행합니다.

위의 예 외에도 AlphaTensor가 발견한 알고리즘은 처음으로 유한 필드에서 Strassen의 2차 알고리즘을 개선합니다. 작은 행렬을 곱하는 이러한 알고리즘은 모든 크기의 더 큰 행렬을 곱하는 기본 요소로 사용될 수 있습니다.

AlphaTensor는 또한 각 크기의 최대 수천 개의 행렬 곱셈 알고리즘을 포함하는 SOTA 복잡성을 지닌 다양한 알고리즘 세트를 발견했습니다. 이는 행렬 곱셈 알고리즘의 공간이 이전에 생각했던 것보다 더 풍부하다는 것을 나타냅니다.

이 풍부한 공간의 알고리즘은 다양한 수학적, 실용적인 속성을 가지고 있습니다. 이러한 다양성을 활용하여 DeepMind는 AlphaTensor를 조정하여 특정 하드웨어(예: Nvidia V100 GPU, Google TPU v2)에서 빠르게 실행되는 알고리즘을 특별히 발견했습니다. 이러한 알고리즘은 동일한 하드웨어에서 일반적으로 사용되는 알고리즘보다 10-20% 더 빠르게 대규모 행렬 곱셈을 수행하여 임의의 목표를 최적화하는 데 있어 AlphaTensor의 유연성을 보여줍니다.

AlphaTensor에는 알고리즘의 런타임에 해당하는 대상이 있습니다. 올바른 행렬 곱셈 알고리즘이 발견되면 지정된 하드웨어에서 벤치마킹된 다음 AlphaTensor에 피드백되어 지정된 하드웨어에서 보다 효율적인 알고리즘을 학습합니다.

향후 연구 및 응용에 대한 시사점

수학적 관점에서 DeepMind의 결과는 계산 문제를 해결하기 위한 가장 빠른 알고리즘을 식별하는 것을 목표로 하는 복잡성 이론에 대한 추가 연구를 안내할 수 있습니다. AlphaTensor는 이전 방법보다 더 효율적으로 가능한 알고리즘의 공간을 탐색함으로써 행렬 곱셈 알고리즘의 풍부함에 대한 이해를 심화시키는 데 도움이 됩니다.

또한 행렬 곱셈은 컴퓨터 그래픽, 디지털 통신, 신경망 훈련 및 과학 컴퓨팅과 같은 많은 컴퓨팅 작업의 핵심 구성 요소이기 때문에 AlphaTensor가 발견한 알고리즘은 이러한 분야에서 컴퓨팅 효율성을 크게 향상시킬 수 있습니다.

이 기사는 행렬 곱셈의 특정 문제에만 초점을 맞추고 있지만 DeepMind는 더 많은 사람들이 AI를 사용하여 다른 기본 컴퓨팅 작업에 대한 알고리즘 발견을 안내하도록 영감을 주기를 희망합니다. 또한 DeepMind의 연구는 AlphaZero의 강력한 알고리즘이 기존 게임의 영역을 훨씬 뛰어넘어 수학 분야의 미해결 문제를 해결하는 데 도움이 될 수 있음을 보여줍니다.

앞으로 DeepMind는 더 많은 인공 지능을 사용하여 사회가 연구를 기반으로 수학과 과학의 가장 중요한 과제를 해결하도록 돕기를 희망합니다.

위 내용은 강화학습으로 행렬 곱셈 알고리즘 발견, DeepMind가 Nature 표지에 등장, AlphaTensor 출시의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!