수학자들은 좋은 퍼즐을 좋아합니다. 곱셈 행렬(18차원 숫자 표)과 같은 추상적인 것조차도 가장 효율적인 방법을 찾으려고 할 때 게임처럼 느껴질 수 있습니다. 도전적이지만 매혹적인, 가능한 적은 수의 동작으로 루빅스 큐브를 풀려고 하는 것과 약간 비슷합니다. 루빅스 큐브의 경우를 제외하고 각 단계에서 가능한 이동 수는 10입니다. 행렬 곱셈의 경우 비교적 간단한 경우에도 모든 단계는 XNUMX개 이상을 나타낼 수 있습니다.¹² 옵션을 제공합니다.

지난 50년 동안 연구자들은 인간의 직관에 의한 컴퓨터 검색을 기반으로 여러 가지 방법으로 이 문제에 접근했습니다. 지난 달 인공 지능 회사 DeepMind의 한 팀은 새로운 방향에서 문제를 해결하는 방법을 보여주었습니다. 종이 in 자연 행렬 곱셈을 위한 새로운 빠른 알고리즘을 발견하기 위해 신경망을 성공적으로 훈련시켰습니다. 마치 AI가 엄청나게 복잡한 루빅스 큐브를 풀기 위한 알려지지 않은 전략을 찾은 것 같았습니다.

"매우 깔끔한 결과"라고 말했습니다. 조쉬 알만, Columbia University의 컴퓨터 과학자. 그러나 그와 다른 행렬 곱셈 전문가들은 그러한 AI 지원이 적어도 단기적으로는 기존 방법을 대체하기보다는 보완할 것이라고 강조했습니다. Alman은 "이것은 돌파구가 될 수 있는 무언가에 대한 개념 증명과 같습니다."라고 말했습니다. 그 결과는 연구자들의 탐색에 도움이 될 것입니다.

그 점을 증명이라도 하듯 XNUMX일 후 자연 종이가 나왔을 때 한 쌍의 오스트리아 연구원이 새로운 방법과 기존 방법이 서로를 보완할 수 있는 방법을 설명했습니다. 그들은 기존의 컴퓨터 지원 검색을 사용하여 더 개선하다 신경망이 발견한 알고리즘 중 하나입니다.

그 결과는 루빅스 큐브를 푸는 과정과 마찬가지로 더 나은 알고리즘으로 가는 길이 우여곡절이 많을 것임을 암시합니다.

행렬 곱하기

행렬 곱셈은 모든 수학에서 가장 기본적이고 보편적인 연산 중 하나입니다. 쌍을 곱하려면 n-으로-n 행렬, 각각 n² 요소를 곱하고 특정 조합으로 이러한 요소를 함께 추가하여 제품을 생성합니다. n-으로-n 행렬. XNUMX를 곱하기 위한 표준 레시피 n-으로-n 행렬이 필요합니다 n³ 예를 들어 2x2 행렬에는 XNUMX번의 곱셈이 필요합니다.

수천 개의 행과 열이 있는 더 큰 행렬의 경우 이 프로세스가 빠르게 번거로워집니다. 그러나 1969년 수학자 Volker Strassen은 절차를 발견했습니다 더 많은 덧셈 단계를 도입하는 비용으로 2개가 아닌 2개의 곱셈 단계를 사용하여 XNUMXxXNUMX 행렬 쌍을 곱합니다.

2x2 행렬 쌍을 곱하기만 하면 Strassen의 알고리즘이 불필요하게 복잡해집니다. 그러나 그는 그것이 더 큰 매트릭스에서도 작동한다는 것을 깨달았습니다. 행렬의 요소 자체가 행렬일 수 있기 때문입니다. 예를 들어, 20,000개의 행과 20,000개의 열이 있는 행렬은 2개의 요소가 각각 2x10,000 행렬인 10,000x5,000 행렬로 다시 생각할 수 있습니다. 그런 다음 각 행렬을 5,000개의 2 x 2 블록 등으로 세분할 수 있습니다. Strassen은 그의 방법을 적용하여 이 중첩 계층 구조의 각 수준에서 XNUMXxXNUMX 행렬을 곱할 수 있습니다. 행렬 크기가 증가함에 따라 더 적은 곱셈으로 인한 절감 효과가 커집니다.

Strassen의 발견은 행렬 곱셈을 위한 효율적인 알고리즘에 대한 검색으로 이어졌고, 이후 두 개의 서로 다른 하위 필드에 영감을 주었습니다. 하나는 원칙의 문제에 초점을 맞춥니다. XNUMX를 곱하는 것을 상상한다면 n-으로-n 행렬과 let n 무한대로 실행하면 가능한 가장 빠른 알고리즘의 곱셈 단계 수는 n? 그만큼 현재 기록 최상의 스케일링을 위해 n^2.3728596, Alman에 속하며 버지니아 바실 레프 스카 윌리엄스, Massachusetts Institute of Technology의 컴퓨터 과학자. (최근 공개되지 않은 프리 프린트 새로운 기술을 사용하여 약간의 개선을 보고했습니다.) 그러나 이러한 알고리즘은 순전히 이론적인 관심사이며 터무니없이 큰 행렬에 대해서만 Strassen과 같은 방법을 이겼습니다.

두 번째 하위 필드는 더 작은 규모로 생각합니다. Strassen의 작업 직후, 이스라엘계 미국인 컴퓨터 과학자인 Shmuel Winograd는 보여 Strassen은 이론적 한계에 도달했습니다. 2개 미만의 곱셈 단계로 2xXNUMX 행렬을 곱하는 것은 불가능합니다. 그러나 다른 모든 행렬 크기의 경우 필요한 곱셈의 최소 수는 아직 미해결 문제로 남아 있습니다. 그리고 작은 행렬에 대한 빠른 알고리즘은 큰 영향을 미칠 수 있습니다. 이러한 알고리즘의 반복 반복은 합리적인 크기의 행렬이 곱해질 때 Strassen의 알고리즘을 능가할 수 있기 때문입니다.

불행히도 가능성의 순전한 수는 엄청납니다. 3x3 행렬의 경우에도 "가능한 알고리즘의 수는 우주의 원자 수를 초과합니다."라고 말했습니다. 알후세인 포지, DeepMind 연구원이자 새로운 작업의 리더 중 한 명입니다.

이 어지러운 옵션 메뉴에 직면한 연구자들은 행렬 곱셈을 컴퓨터가 다루기 더 쉬운 완전히 다른 수학 문제처럼 보이는 것으로 변환함으로써 진전을 이루었습니다. 두 개의 행렬을 곱하는 추상적인 작업을 특정한 종류의 수학적 객체, 즉 텐서라고 하는 숫자의 1차원 배열로 나타낼 수 있습니다. 그런 다음 연구원은 이 텐서를 "랭크-XNUMX" 텐서라고 하는 기본 구성 요소의 합계로 분해할 수 있습니다. 이들 각각은 해당 행렬 곱셈 알고리즘의 다른 단계를 나타냅니다. 즉, 효율적인 곱셈 알고리즘을 찾는 것이 텐서 분해에서 항의 수를 최소화하는 것과 같습니다. 항이 적을수록 관련된 단계도 적습니다.

이런 식으로 연구자들은 새로운 것을 발견했습니다. 알고리즘 곱하는 n-으로-n 표준보다 적게 사용하는 행렬 n³ 많은 작은 행렬 크기에 대한 곱셈 단계. 그러나 표준뿐만 아니라 작은 행렬에 대한 Strassen의 알고리즘을 능가하는 알고리즘은 지금까지 도달하지 못했습니다.

게임 온

DeepMind 팀은 텐서 분해를 싱글 플레이어 게임으로 전환하여 문제에 접근했습니다. 그들은 2016년에 또 다른 DeepMind AI인 AlphaGo의 후손인 딥 러닝 알고리즘으로 시작했습니다. 보드게임 바둑을 배웠다 최고의 인간 플레이어를 이길만큼 충분히.

모든 딥 러닝 알고리즘은 신경망을 기반으로 구축됩니다. 즉, 각 뉴런이 다음 계층의 뉴런에 미치는 영향을 나타내는 강도가 다양할 수 있는 연결과 함께 레이어로 분류된 인공 뉴런의 웹입니다. 이러한 연결의 강도는 신경망이 수신하는 각 입력을 알고리즘이 전체 목표를 달성하는 데 도움이 되는 출력으로 변환하는 방법을 학습하는 훈련 절차의 여러 반복을 통해 조정됩니다.

AlphaTensor라고 불리는 DeepMind의 새로운 알고리즘에서 입력은 유효한 행렬 곱셈 방식으로 가는 단계를 나타냅니다. 신경망에 대한 첫 번째 입력은 원래 행렬 곱셈 텐서이고 그 출력은 AlphaTensor가 첫 번째 이동을 위해 선택한 순위 1 텐서입니다. 알고리즘은 초기 입력에서 이 순위 1 텐서를 빼서 네트워크에 새로운 입력으로 피드백되는 업데이트된 텐서를 생성합니다. 이 프로세스는 결국 시작 텐서의 모든 요소가 1으로 줄어들 때까지 반복됩니다. 즉, 더 이상 제거할 랭크 XNUMX 텐서가 없습니다.

그 시점에서 신경망은 모든 순위 1 텐서의 합이 시작 텐서와 정확히 같다는 것을 수학적으로 보장하기 때문에 유효한 텐서 분해를 발견했습니다. 그리고 거기에 도달하기 위해 취한 단계는 해당 행렬 곱셈 알고리즘의 단계로 다시 변환될 수 있습니다.

게임은 다음과 같습니다. AlphaTensor는 텐서를 반복적으로 랭크 1 구성 요소 집합으로 분해합니다. 매번 AlphaTensor는 단계 수를 줄이는 방법을 찾으면 보상을 받습니다. 그러나 모든 것을 풀기 전에 루빅스 큐브에서 완벽하게 정렬된 얼굴을 뒤섞어야 하는 것처럼 승리로 가는 지름길은 전혀 직관적이지 않습니다.

팀은 이제 이론적으로 문제를 해결할 수 있는 알고리즘을 갖게 되었습니다. 그들은 그것을 먼저 훈련시켜야만 했다.

새로운 경로

모든 신경망과 마찬가지로 AlphaTensor는 훈련을 위해 많은 데이터가 필요하지만 텐서 분해는 매우 어려운 문제입니다. 연구자들이 네트워크에 공급할 수 있는 효율적인 분해의 예는 거의 없었습니다. 대신, 그들은 훨씬 더 쉬운 역 문제에 대해 알고리즘을 훈련함으로써 알고리즘이 시작되도록 도왔습니다. 즉, 무작위로 생성된 1순위 텐서 묶음을 합산하는 것입니다.

"그들은 어려운 문제에 대한 더 많은 데이터를 생성하기 위해 쉬운 문제를 사용하고 있습니다."라고 말했습니다. 마이클 리트만, Brown University의 컴퓨터 과학자. 이 후방 훈련 절차를 강화 학습과 결합하면 AlphaTensor가 효율적인 분해를 찾기 위해 실수하면서 자체 훈련 데이터를 생성하여 자체 훈련 방법보다 훨씬 더 잘 작동했습니다.

DeepMind 팀은 최대 12x12 행렬의 곱셈을 나타내는 텐서를 분해하도록 AlphaTensor를 훈련했습니다. 일반적인 실수의 행렬을 곱하기 위한 빠른 알고리즘과 모듈로 2 산술로 알려진 보다 제한된 설정에 특정한 알고리즘을 찾았습니다. (이것은 두 개의 숫자만을 기반으로 하는 수학이므로 행렬 요소는 0 또는 1, 1 + 1 = 0만 될 수 있습니다.) 연구자들은 종종 여기에서 발견된 알고리즘이 실수의 행렬에 대해 작업합니다.

훈련 후 AlphaTensor는 몇 분 안에 Strassen의 알고리즘을 재발견했습니다. 그런 다음 각 매트릭스 크기에 대해 최대 수천 개의 새로운 고속 알고리즘을 발견했습니다. 이들은 가장 잘 알려진 알고리즘과 다르지만 같은 수의 곱셈 단계를 가졌습니다.

경우에 따라 AlphaTensor는 기존 기록을 경신하기도 합니다. 가장 놀라운 발견은 모듈로 2 산술에서 일어났습니다. 여기에서 4개의 곱셈 단계에서 4x47 행렬을 곱하는 새로운 알고리즘을 발견했습니다. 이는 Strassen 알고리즘의 두 반복에 필요한 49단계보다 개선된 것입니다. 또한 5x5 모듈로 2 행렬에 대한 가장 잘 알려진 알고리즘을 능가하여 필요한 곱셈의 수를 이전 기록인 98에서 96으로 줄였습니다. 91x5 행렬을 사용하는 Strassen의 알고리즘.)

새로운 주목할만한 결과는 많은 흥분을 불러일으켰습니다. 일부 연구원 AI를 기반으로 한 현상 개선에 찬사를 보냅니다. 그러나 행렬 곱셈 커뮤니티의 모든 사람이 그렇게 감명받은 것은 아닙니다. Vassilevska Williams는 "약간 과장된 것 같은 느낌이 들었습니다."라고 말했습니다. “그것은 또 다른 도구입니다. '오, 컴퓨터가 인간을 이겼다'는 게 아니잖아요?”

연구원들은 또한 기록적인 4x4 알고리즘의 즉각적인 적용이 제한적일 것이라고 강조했습니다. 모듈로 2 산술에서만 유효할 뿐만 아니라 실생활에서는 속도 외에 중요한 고려 사항이 있습니다.

Fawzi는 실제로 이것은 시작에 불과하다는 데 동의했습니다. "개선과 연구의 여지가 많고 좋은 일입니다."라고 그는 말했습니다.

마지막 트위스트

잘 확립된 컴퓨터 검색 방법에 비해 AlphaTensor의 가장 큰 강점은 또한 가장 큰 약점이기도 합니다. 좋은 알고리즘이 어떤 것인지에 대한 인간의 직관에 의해 제약을 받지 않기 때문에 선택을 설명할 수 없습니다. 그것은 연구자들이 그 성과로부터 배우기 어렵게 만듭니다.

그러나 이것은 보이는 것처럼 큰 단점이 아닐 수 있습니다. AlphaTensor 결과가 나온 지 며칠 후 수학자 마누엘 카우어스 그리고 그의 대학원생 야콥 무스바우어, 오스트리아의 요하네스 케플러 대학교 린츠(Johannes Kepler University Linz)는 또 다른 진전을 보고했습니다.

DeepMind 논문이 나왔을 때 Kauers와 Moosbauer는 기존의 컴퓨터 지원 검색을 사용하여 새로운 곱셈 알고리즘을 검색하는 과정에 있었습니다. 그러나 새로운 기본 원리로 새로 시작하는 대부분의 검색과 달리, 그들의 방법은 더 많은 곱셈 절약을 짜내기 위해 기존 알고리즘을 반복적으로 조정하는 방식으로 작동합니다. 5 x 5 모듈로 2 행렬에 대한 AlphaTensor의 알고리즘을 출발점으로 삼았을 때, 그들은 그들의 방법이 단 몇 초의 계산 후에 곱셈 단계의 수를 96에서 95로 줄였다는 사실에 놀랐습니다.

AlphaTensor는 또 다른 개선을 간접적으로 도왔습니다. 이전에 Kauers와 Moosbauer는 Strassen 알고리즘의 두 반복을 이길 수 없다고 믿었기 때문에 4x4 행렬의 공간을 탐색하지 않았습니다. AlphaTensor 결과는 그들이 재고하도록 자극했고 처음부터 시작하여 일주일 간의 계산 시간 후에 그들의 방법은 AlphaTensor가 발견한 것과 관련이 없는 또 다른 47단계 알고리즘을 나타냈습니다. Kauers는 "누군가 우리에게 4x4에 대해 발견할 무언가가 있다고 말했다면 우리는 더 일찍 그렇게 할 수 있었을 것입니다."라고 말했습니다. "하지만 좋아요, 그게 작동하는 방식입니다."

Littman은 그 상황을 처음으로 주자가 XNUMX분 안에 XNUMX마일을 완주한 것에 비유하면서 더 많은 놀라움을 기대합니다. "사람들은 '오, 잠깐만요, 우리는 이것을 할 수 있습니다.'라고 말했고 이제 많은 사람들이 그것을 할 수 있습니다."라고 그는 말했습니다.

앞으로 Fawzi는 조상 AlphaGo가 결국 다른 게임으로 분기한 것처럼 AlphaTensor를 일반화하여 더 광범위한 수학 및 계산 작업을 처리하기를 희망합니다.

Kauers는 이것을 새로운 알고리즘을 발견하기 위한 기계 학습의 적용에 대한 진정한 리트머스 테스트로 보고 있습니다. 그는 빠른 행렬 곱셈 알고리즘에 대한 탐구는 사람의 도움이 있든 없든 컴퓨터 검색이 잘 맞는 조합 문제라고 지적합니다. 그러나 모든 수학 문제가 그렇게 쉽게 파악되는 것은 아닙니다. 기계 학습이 질적으로 새로운 알고리즘 아이디어를 발견할 수 있다면 "이것은 게임 체인저가 될 것"이라고 그는 말했습니다.