AI가 50년 만에 찾아낸 행렬 계산 알고리즘

딥마인드가 만든 AI인 알파고(AlphaGo)는 기능 강화를 통해 바둑 외에도 체스와 장기 등 모든 보드 게임 대응을 완수했다. 새롭게 알파고 계보를 계승하는 AI인 알파텐서(AlphaTensor)가 행렬 곱을 계산하는 최적의 방법을 요구하는 게임에 도전, 행렬 곱을 계산하는 미발견 알고리즘을 도출하는데 성공했다.

이번에 진행한 행렬 곱을 계산하는 알고리즘은 화상 처리나 게임 그래픽 처리, 일기 예보, 데이터 압축 등 일상 생활에 관계되는 다양한 분야에서 이용되고 있다. 행렬 계산을 가속화하기 위해 많은 기업이 컴퓨팅 하드웨어를 개발하고 향상시키려 노력하지만 알고리즘 자체가 효율화되면 행렬 계산 속도가 크게 높아질 수 있다.

행렬 곱을 빠르게 계산하는 알고리즘으로는 1969년 발표된 슈트라센 알고리즘(Strassen Algorithm)이 널리 알려져 있다. 하지만 슈트라센 알고리즘 발표 이후 50년 이상에 걸쳐 큰 효율성을 실현하지는 못했다. 따라서 딥마인드는 행렬 곱을 계산하는 최적의 방법을 찾는 게임을 설계해 알파텐서에서 플레이했다.

플레이를 시작할 때 알파텐서는 행렬의 곱을 계산하는 방법을 전혀 학습하지 않았지만 플레이를 반복하는 동안 효율적인 계산 방법을 습득하기 시작했다. 예를 들어 4×5 행렬과 5×5 행렬 곱을 구할 때에는 어리석게 계산하면 100회 계산이 필요하지만 알려진 알고리즘을 이용하면 계산 횟수를 80회로 줄일 수 있다. 이에 반해 알파텐서가 도출한 알고리즘에선 76회 계산으로 곱을 구할 수 있다.

플레이를 거듭한 결과 알파텐서는 슈트라센 알고리즘과 비슷한 알고리즘을 자력으로 이끌어 내고 기존 알고리즘보다 효율적으로 계산 가능한 알고리즘을 도출하는데 성공했다. 딥마인드에 따르면 알파텐서가 발견한 알고리즘은 수천 행이라는 방대한 크기 행렬에도 대응 가능하다고 한다. 또 엔비디아 V100과 구글 TPU v2 같은 특정 하드웨어에서 행렬 계산 속도를 10∼20% 고속화하는 알고리즘도 도출됐다.

딥마인드는 알파텐서가 발견한 알고리즘이 컴퓨터 그래픽과 통신 처리, 신경망 훈련 등 계산을 크게 효율화할 수 있다고 밝히고 있다. 또 딥마인드는 알파텐서에 의한 알고리즘 연구를 행렬 이외 계산 분야에도 도움이 될 가능성을 지적하고 있다. 한편 알파텐서가 발견한 행렬 곱셈 알고리즘은 깃허브 리포지토리에 공개되어 있다. 관련 내용은 이곳에서 확인할 수 있다.