당시 알파고의 마법의 손길을 재현해보세요! DeepMind의 새로운 AI는 70% 속도 향상 정렬 알고리즘을 발견했으며, 10년 동안 업데이트되지 않았던 C++ 라이브러리가 업데이트되었습니다.

DeepMind가 다시 한 번 큰 성과를 거두며 Nature에 등장했습니다!

이번에 그들은 또 다른 강화 학습 AI를 만들어 컴퓨터 분야에서 가장 기본적인 두 가지 알고리즘에 새로운 돌파구를 마련했습니다.

하나는 정렬 알고리즘으로, 속도를 최대 70까지 높일 수 있는 새로운 구현을 발견했습니다. %;

또 다른 방법은 속도를 30% 높이는 새로운 방법을 찾은 해싱 알고리즘입니다.

그뿐만 아니라, 이 AI가 사용한 방식은 "당시 알파고의 마법의 손길을 재현한다"고 하는데, 이는 직관을 어기는 것처럼 보였지만 실제로는 인간 사부 이세돌을 물리쳤던 시절이다. 하나가 떨어졌습니다.

이 소식이 나오자마자 학계는 즉시 폭발했습니다. 일부 네티즌들은

이렇게 오래되고 기본적인 알고리즘이 더욱 개선될 수 있을 것이라고는 예상하지 못했습니다.

그리고 10년 동안 업데이트되지 않았던 LLVM 표준 C++ 라이브러리가 업데이트되어 수십억 명의 사람들이 혜택을 누릴 수 있는 것은 바로 이 최신 성과 때문입니다.

정렬이든 해싱이든 그들의 응용 시나리오는 온라인 쇼핑, 클라우드 컴퓨팅, 공급망 관리 등 다양한 시나리오에서 사용될 수 있고 매일 수억 번 호출되기 때문입니다!

그러나 DeepMind가 말했듯이:

너무 흥분하지 마십시오. 코드 효율성을 향상시키는 AI의 힘은 이제 막 시작되었습니다.

Alpha 계열의 "upstart"가 더 빠른 정렬 알고리즘을 발견합니다

이 AI는 AlphaDev라고 하며, Alpha 계열의 "upstart"에 속하며 AlphaZero(체스에서 패배한 AI)를 기반으로 합니다. 2017년 세계 챔피언).

그 발견은 기존 알고리즘을 기반으로 하는 것이 아니라 가장 낮은 수준의 조립 지침부터 시작됩니다.

DeepMind 연구진은 이를 위해 싱글 플레이어 "조립" 게임을 설계했습니다.

적절한 지침(아래 그림의 프로세스 A)을 검색하고 선택할 수 있는 한 데이터를 올바르고 빠르게 정렬합니다(아래 그림의 프로세스 B). 아래 그림), 보상을 받을 수 있습니다.

하지만 이 게임의 과제는 검색 공간의 크기(결합 가능한 명령의 수는 우주의 입자 수와 동일)뿐만 아니라 보상의 성격에도 있습니다. 잘못된 명령 하나가 전체 알고리즘을 중단시킬 수 있기 때문입니다.

AlphaDev에는 학습 알고리즘과 표현 기능이라는 두 가지 핵심 구성 요소가 있습니다.

그 중 학습 알고리즘은 주로 DRL과 무작위 검색 최적화 알고리즘을 결합하여 대규모 명령어 검색을 수행할 수 있는 강력한 AlphaZero에서 확장됩니다. 주요 표현 기능은 어셈블러의 기본 구조를 캡처할 수 있는 Transformer를 기반으로 합니다. , 특수 시퀀스로 표현됩니다.

AlphaDev가 계속해서 몬스터와 싸우고 업그레이드함에 따라 연구원들은 수행할 수 있는 단계 수와 정렬할 시퀀스 길이도 제한할 것입니다.

마지막으로 AlphaDev는 새로운 정렬 알고리즘을 발견했습니다.

시퀀스가 짧은 경우 인간 기준 정렬 알고리즘에 비해 속도가 70% 증가할 수 있으며, 시퀀스 길이가 25,000개 요소를 초과하면 속도가 1.7% 증가합니다. .

단순 정렬은 실제로 널리 사용되며, 특히 대규모 정렬 기능의 중요한 구성 요소로 여러 번 호출됩니다. 짧은 시퀀스를 개선하면 모든 시퀀스의 정렬 속도도 향상될 수 있습니다. )

구체적으로 이 알고리즘의 혁신은 주로 두 가지 명령 시퀀스에 있습니다.

(1) AlphaDev Swap Move(스왑 이동)
(2) AlphaDev Copy Move(복사 이동)

아래 그림과 같이 왼쪽 min(A,B,C)의 원래 sort3 구현이 사용됩니다. 오른쪽은 min(A,B) 구현만 필요한 "AlphaDev Swap Move"를 통한 것입니다. 명령어의 한 단계를 생략할 수 있으며, A와 B의 최소값만 계산하면 되는 것을 알 수 있다.

저자는 이 참신한 방식이 알파고의 '무브 37'을 연상시킨다고 한다. 전설적인 바둑기사 이세돌을 직접 꺾고 관객들을 놀라게 한 반직관적인 방식이다.

마찬가지로 AlphaDev는 동작을 교환하고 복사하여 단계를 건너뛰고 잘못된 것처럼 보이지만 실제로는 지름길인 방식으로 목표를 달성합니다.

아래 그림과 같이 8개 요소를 정렬하는 알고리즘에서 AlphaDev도 "AlphaDev Copy Move"를 사용하여 원래 구현의 더 복잡한 최대값을 max (B, min (A, C)) (B, min(A, C, D)) 명령이 줄어들고, 전체 알고리즘의 총 명령 수도 한 단계 줄어듭니다.

더 빠른 정렬 알고리즘을 발견한 후 저자는 AlphaDev로 해싱 알고리즘을 시도하여 다용성을 입증했습니다.

결과는 실망스럽지 않았습니다. AlphaDev는 9~16바이트 길이 범위에서 30% 속도 증가도 달성했습니다.

정렬 알고리즘과 마찬가지로 Abseil 라이브러리에 새로운 방법을 통합했으며 현재 전 세계 수백만 명의 개발자가 사용할 수 있습니다.

마지막으로 저자는 두 가지 새로운 알고리즘의 구현은 AlphaDev가 독창적인 솔루션을 발견하는 강력한 능력을 가지고 있음을 보여주며 컴퓨터 분야의 기본 알고리즘을 개선할 방법에 대해 더 많이 생각하게 만들 것이라고 말했습니다.

그러나 이 연구에 사용된 어셈블리 언어의 한계로 인해 다음에는 고급 언어(예: C++)에서 알고리즘을 최적화하는 AlphaDev의 기능을 시험해 볼 계획입니다.

네티즌: 새로운 정렬 알고리즘의 발견은 포함되지 않습니다

많은 사람들이 이 성과에 매우 기뻐하고 있습니다.

이 네티즌이 말했듯이:

AlphaGo가 세상을 놀라게 한 후에 강화 학습은 또 무엇을 할 수 있습니까? 실질적으로 중요한 일을 할 수 있습니까? 이것이 답입니다.

하지만 이번에는 DeepMind가 제목을 과장했다는 의혹을 받는 것 같다는 지적이 많이 나왔습니다.

전통적인 의미의 시간 복잡도가 아닌 알고리즘 지연을 계산합니다. 시간 복잡도를 실제로 계산하면 데이터가 좋아 보이지 않을 수 있습니다.

개선 사항은 정렬 알고리즘 자체가 아니라 최신 CPU(특히 짧은 시퀀스의 경우)에 대한 새로운 정렬 최적화에 있습니다. 이 접근 방식은 실제로 매우 일반적입니다. 예를 들어 FFTW 및 ATLAS와 같은 라이브러리에서는 이 방법을 채택했습니다.

동의했습니다. 그들은 새로운 정렬 알고리즘이 아니라 특정 CPU에 대한 더 빠른 기계 최적화를 찾았습니다. 방법 자체는 훌륭하지만 획기적인 연구는 아닙니다.

어떻게 생각하세요?

논문 주소:https://www.php.cn/link/a3fefe83288ecb0e40ebe40b2bde29fe
공식 블로그:https://www.php.cn/link/f5b2aa928f940f3f09a0d14f45a27875

참조 링크:
[1]https ://www.php.cn/link/5383c7318a3158b9bc261d0b6996f7c2
[2]https://www.php.cn/link/ecf9902e0f61677c8de25ae60b654669
[3]https://www.php.cn/ 0383314bf626052313b8275638fcccce

위 내용은 당시 알파고의 마법의 손길을 재현해보세요! DeepMind의 새로운 AI는 70% 속도 향상 정렬 알고리즘을 발견했으며, 10년 동안 업데이트되지 않았던 C++ 라이브러리가 업데이트되었습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!