Deep Mind AlphaTensor는 새로운 알고리즘을 발견합니다

Deep Mind는 AlphaZero를 수학으로 확장하여 연구 알고리즘의 새로운 가능성을 열어줍니다.

AlphaTensor는 체스, 바둑, 장기와 같은 보드 게임에서 초인적인 성능을 보여준 에이전트인 AlphaZero를 기반으로 하며, 이 작업은 AlphaZero가 게임에서 처음으로 미해결 수학 문제를 해결하기까지의 여정을 보여줍니다.

고대 이집트인들은 곱셈표 없이 두 수를 곱하는 알고리즘을 만들었고, 그리스 수학자 유클리드는 오늘날에도 여전히 사용되는 최대공약수를 계산하는 알고리즘을 설명했습니다.

이슬람 황금기 동안 페르시아 수학자 무하마드 이븐 무사 알 콰리즈미는 선형 및 이차 방정식을 풀기 위한 새로운 알고리즘을 설계했습니다. 사실, 라틴어로 Algoritmi로 번역된 al-Khwarizmi의 이름은 알고리즘이라는 용어로 이어졌습니다. 그러나 교실 대수학에서 최첨단 과학 연구에 이르기까지 사회 전반에 걸쳐 사용되는 오늘날 알고리즘에 대한 친숙함에도 불구하고 새로운 알고리즘을 발견하는 과정은 매우 어렵고 인간 정신의 놀라운 추론 능력의 한 예입니다.

그들은 Nature에 발표했습니다. AlphaTensor는 행렬 곱셈과 같은 기본 작업에 대한 새롭고 효율적이며 입증 가능한 정확한 알고리즘을 발견하기 위한 최초의 인공 지능(AI) 시스템입니다. 이것은 두 행렬을 곱하는 가장 빠른 방법을 찾는 것에 대한 수학의 50년 된 열린 질문에 빛을 비춰줍니다.

처음부터 훈련된 AlphaTensor는 기존의 인간 및 컴퓨터 설계 알고리즘보다 효율적인 행렬 곱셈 알고리즘을 발견합니다. 알려진 알고리즘을 통해 개선했음에도 불구하고 AlphaTensor의 한계는 검색 공간을 이산화하지만 효율적인 알고리즘을 놓칠 수 있는 잠재적인 요소 항목 F 집합을 미리 정의해야 한다는 것입니다. 향후 연구의 흥미로운 방향은 AlphaTensor를 F 검색에 적용하는 것입니다. AlphaTensor의 중요한 강점 중 하나는 알고리즘을 찾는 것 외에도 복잡한 확률론적 및 미분할 수 없는 보상(텐서 순위에서 특정 하드웨어의 실질적인 효율성까지)을 지원하는 유연성입니다. 다양한 공간(예: 유한 필드)에서 사용자 지정 작업을 위해 그들은 이것이 수치적 안정성이나 에너지 사용과 같이 여기에서 고려하지 않은 메트릭을 최적화하는 알고리즘을 설계하기 위한 AlphaTensor의 응용 프로그램에 박차를 가할 것이라고 믿습니다.

행렬 곱셈 알고리즘의 발견은 행렬 역전, 행렬식 계산 및 선형 시스템 해결과 같은 많은 계산 작업의 핵심에 있기 때문에 행렬 곱셈 알고리즘의 발견은 광범위한 의미를 갖습니다.

알고리즘 발견 자동화 프로세스 및 진행 상황
첫째, 행렬 곱셈을 위한 효율적인 알고리즘을 찾는 문제를 싱글 플레이어 게임으로 전환했습니다. 이 게임에서 보드는 XNUMX차원 텐서(숫자 배열)로 현재 알고리즘이 얼마나 정확한지 캡처합니다. 알고리즘 명령에 따라 허용된 일련의 이동을 통해 플레이어는 텐서를 수정하고 해당 항목을 XNUMX으로 만들려고 합니다. 플레이어가 그렇게 하면 모든 행렬 쌍에 대해 증명할 수 있는 올바른 행렬 곱셈 알고리즘이 생성되고 그 효율성은 텐서를 XNUMX으로 만들기 위해 취한 단계 수로 캡처됩니다.

이 게임은 매우 도전적입니다. 고려할 수 있는 알고리즘의 수는 행렬 곱셈의 작은 경우에도 우주의 원자 수보다 훨씬 많습니다. 수십 년 동안 AI의 도전 과제로 남아 있던 바둑 게임과 비교할 때 게임의 각 단계에서 가능한 이동 수는 30배 더 많습니다(그들이 고려하는 설정 중 하나의 경우 10^33 이상).

본질적으로, 이 게임을 잘 하기 위해서는 가능성의 거대한 건초더미에서 가장 작은 바늘을 식별할 필요가 있습니다. 기존 게임과 크게 다른 이 영역의 과제를 해결하기 위해 문제별 귀납적 편향을 통합하는 새로운 신경망 아키텍처, 유용한 합성 데이터를 생성하는 절차, 대칭성을 활용하는 방법을 비롯한 여러 중요한 구성 요소를 개발했습니다. 문제.

그런 다음 기존 행렬 곱셈 알고리즘에 대한 지식 없이 시작하여 강화 학습을 사용하여 AlphaTensor 에이전트를 훈련하여 게임을 시작했습니다. 학습을 통해 AlphaTensor는 시간이 지남에 따라 점진적으로 개선되어 Strassen의 것과 같은 역사적 고속 행렬 곱셈 알고리즘을 재발견하여 결국 인간의 직관 영역을 능가하고 이전에 알려진 것보다 빠르게 알고리즘을 발견합니다.

미래 연구 및 응용 분야에 대한 영향 탐색
수학적 관점에서 그들의 결과는 계산 문제를 해결하기 위한 가장 빠른 알고리즘을 결정하는 것을 목표로 하는 복잡성 이론에 대한 추가 연구를 안내할 수 있습니다. AlphaTensor는 이전 접근 방식보다 더 효과적인 방식으로 가능한 알고리즘의 공간을 탐색함으로써 행렬 곱셈 알고리즘의 풍부함에 대한 이해를 높이는 데 도움이 됩니다. 이 공간을 이해하면 컴퓨터 과학에서 가장 근본적인 미해결 문제 중 하나인 행렬 곱셈의 점근적 복잡성을 결정하는 데 도움이 되는 새로운 결과를 얻을 수 있습니다.

행렬 곱셈은 컴퓨터 그래픽, 디지털 통신, 신경망 교육 및 과학 컴퓨팅에 이르는 많은 계산 작업의 핵심 구성 요소이기 때문에 AlphaTensor가 발견한 알고리즘은 이러한 분야의 계산을 훨씬 더 효율적으로 만들 수 있습니다. 모든 종류의 목표를 고려할 수 있는 AlphaTensor의 유연성은 에너지 사용량 및 수치 안정성과 같은 메트릭을 최적화하는 알고리즘을 설계하기 위한 새로운 애플리케이션에 박차를 가하여 알고리즘이 작동할 때 작은 반올림 오류가 눈덩이처럼 커지는 것을 방지하는 데 도움이 될 수 있습니다.

그들이 여기에서 행렬 곱셈의 특정 문제에 초점을 맞추었지만, 우리는 우리 논문이 다른 사람들이 AI를 사용하여 다른 기본적인 계산 작업에 대한 알고리즘 발견을 안내하는 데 영감을 주기를 바랍니다. 그들의 연구는 또한 AlphaZero가 수학의 미해결 문제를 해결하는 데 도움을 주기 위해 전통적인 게임의 영역을 훨씬 넘어서 확장할 수 있는 강력한 알고리즘임을 보여줍니다. 우리의 연구를 바탕으로 그들은 더 많은 작업에 박차를 가하기를 희망합니다. 즉, AI를 적용하여 사회가 수학 및 과학 전반에 걸쳐 가장 중요한 문제를 해결하는 데 도움이 되기를 바랍니다.

Nature – 강화 학습으로 더 빠른 행렬 곱셈 알고리즘 발견

추상
기본 계산을 위한 알고리즘의 효율성을 높이는 것은 많은 계산의 전체 속도에 영향을 줄 수 있으므로 광범위한 영향을 미칠 수 있습니다. 행렬 곱셈은 신경망에서 과학 컴퓨팅 루틴에 이르기까지 많은 시스템에서 발생하는 그러한 원시적인 작업 중 하나입니다. 기계 학습을 사용한 알고리즘의 자동 검색은 인간의 직관을 넘어 도달하고 현재 최고의 인간이 설계한 알고리즘을 능가할 가능성을 제공합니다. 그러나 알고리즘 발견 절차를 자동화하는 것은 가능한 알고리즘의 공간이 방대하기 때문에 복잡합니다. 여기에서 우리는 임의의 행렬의 곱셈을 위한 효율적이고 입증 가능한 올바른 알고리즘을 발견하기 위해 AlphaZero1을 기반으로 하는 심층 강화 학습 접근 방식을 보고합니다. 우리 에이전트 AlphaTensor는 유한 요소 공간 내에서 텐서 분해를 찾는 것이 목표인 싱글 플레이어 게임을 하도록 훈련되었습니다. AlphaTensor는 다양한 행렬 크기에 대해 최첨단 복잡성을 능가하는 알고리즘을 발견했습니다. AlphaTensor의 알고리즘이 4년 전에 발견된 이후 처음으로 Strassen의 4단계 알고리즘을 개선한 유한 필드의 50 × 2 행렬의 경우와 관련이 있습니다. 우리는 다양한 사용 사례를 통해 AlphaTensor의 유연성을 추가로 보여줍니다. 구조화된 행렬 곱셈을 위한 최첨단 복잡성을 가진 알고리즘과 특정 하드웨어에서 런타임에 대한 행렬 곱셈을 최적화하여 실용적인 효율성을 개선했습니다. 우리의 결과는 다양한 문제에 대한 알고리즘 발견 프로세스를 가속화하고 다양한 기준에 맞게 최적화하는 AlphaTensor의 능력을 강조합니다.