DeepMind가 세상을 뒤흔드는 정렬 알고리즘을 출시하고 C++ 라이브러리가 업데이트 중입니다!

51CTO 웹사이트 콘텐츠 설문지에 참여하려면 클릭하세요

편집됨 | Wang Ruiping, Yan Zheng

AlphaGo에 또 다른 "동생"이 합류했습니다!

Google DeepMind는 Alpha 시리즈를 정렬 알고리즘에 "롤링"하고 AlphaDev를 출시했습니다. .

강화학습 AI를 사용해 정렬 알고리즘과 해싱 알고리즘을 찾아내면 인간 프로그래머가 설계한 알고리즘의 속도가 각각 약 70%, 30% 정도 빨라진다.

연구 결과가 공개되자 즉시 소프트웨어 업계에 불이 붙었습니다! 갑자기 전 세계 수백만 개의 소프트웨어 실행 속도가 급증하여 수십 년 동안 과학자와 엔지니어의 업적을 직접 능가했으며 10년 동안 업데이트되지 않은 LLVM 표준 C++ 라이브러리가 업데이트되었습니다.

(출처: Nature)

이 역시 Google의 두 AI 부서가 합병된 후 출시된 파괴적인 기술입니다. 이 논문은 "심층 강화 학습을 사용하여 발견된 더 빠른 정렬 알고리즘"이라는 제목으로 Nature에 게재되었습니다. 이 논문의 첫 번째 저자는 DeepMind의 컴퓨터 과학자인 Daniel Mankowitz입니다.

1. 진화: 정렬 알고리즘의 기원

정렬은 많은 항목을 특정 순서로 구성하는 방법입니다. 예를 들어 알파벳 순서로 3글자, 큰 숫자에서 가장 작은 숫자로 5개 숫자 또는 정렬 데이터베이스를 포함하는 쌍을 들 수 있습니다. 수백만 개의 기록.

주문 방법은 2~3세기까지 거슬러 올라가며 여전히 진화하고 있습니다. 처음에 학자들은 알렉산드리아 도서관 서가에 있는 수천 권의 책을 알파벳 순서로 수동으로 분류했습니다.

산업 혁명 이후 1890년 미국 인구 조사 결과를 수집하기 위해 자체 분류 기계, 즉 천공 카드에 정보를 저장하는 도표 작성 기계가 발명되었습니다.

1950년대에는 상업용 컴퓨터가 등장하기 시작했고, 정렬 알고리즘이 곧바로 탄생했습니다. 정렬되지 않은 숫자를 정렬 알고리즘에 입력하면 정렬된 숫자 시퀀스가 ​​생성됩니다.

대량의 데이터를 처리하기 위해 다양한 정렬 기술과 알고리즘이 여전히 모든 곳의 코드 베이스에서 사용되고 있습니다.​​

수십 년간의 연구 개발 끝에 이러한 정렬 알고리즘의 효율성은 지속적으로 향상되었으며 컴퓨터 과학자와 프로그래머로부터 인정을 받았습니다. 그러나 추가적인 개선을 위해서는 여전히 중요한 과제가 남아 있습니다.

2. 하이라이트: AlphaDev를 사용하여 새로운 정렬 알고리즘을 생성하는 방법은 무엇입니까?

연구원들은 원래 AlphaDev를 사용하여 주어진 작업을 효율적으로 완료하기 위한 새로운 알고리즘을 생성했습니다.

AlphaDev는 완전히 새로운 알고리즘을 구축했으며 이전 알고리즘을 기반으로 개발되지 않았으므로 독창적인 것으로 간주될 수 있습니다. 그 과정에서 어셈블리 코드의 중간언어를 적용한다. AlphaDev를 사용하면 언어가 컴퓨터 바이너리 명령어에 더 가깝기 때문에 효율적인 알고리즘을 더 쉽게 만들 수 있습니다.

구체적으로 AlphaDev는 매번 명령을 생성한 다음 출력이 올바른지 테스트합니다. 또한 가장 짧은 알고리즘을 생성하기 위해 모델에 요구 사항을 설정합니다.

정렬 알고리즘 재설계를 요청받았을 때 AlphaDev는 기존 알고리즘보다 70% 빠르고 동시에 5개의 데이터를 정렬할 수 있는 새로운 정렬 알고리즘을 무작위로 생성했습니다. 또한 250,000개의 데이터를 정렬할 때 최고 알고리즘보다 1.7% 더 빨랐습니다.

정렬 알고리즘은 다양한 일반 소프트웨어에서 널리 사용되므로 이 혁신은 글로벌 알고리즘에 큰 영향을 미칠 것입니다. DeepMind는 이를 오픈 소스화하고 Libc++ 표준 라이브러리에 통합했습니다.

DeepMind 연구원에 따르면: "엄청난 수의 명령 조합으로 인해 겉보기에 단순해 보이는 연구 과정은 매우 어렵습니다."

3. Origin: 게임을 하면서 최고의 알고리즘을 찾는 것

게다가 AlphaDev는 더욱 발전된 모델입니다. AlphaZero의 구조를 기반으로 합니다. AlphaZero는 이전에 바둑, 체스 및 기타 체스 게임에서 세계 챔피언을 물리친 DeepMind의 강화 학습 모델이었습니다.

이 실험을 통해 새로운 모델 AlphaDev는 게임 플레이에서 과학적 문제 해결로, 실험 시뮬레이션에서 실제 응용으로 전환하는 데 있어 고유한 이점을 발휘합니다.

연구원들은 AlphaDev가 새로운 알고리즘을 발견하도록 훈련시키기 위해 정렬을 싱글 플레이 "조립 게임"으로 시뮬레이션했습니다. 각 게임 턴 동안 AlphaDev는 생성된 알고리즘과 CPU에 포함된 정보를 관찰한 다음 각 동작을 수행하기 위해 알고리즘에 추가할 명령을 선택합니다.

문서에서는 정렬 가능한 알고리즘을 얻기 위해 AlphaDev가 가능한 많은 명령 조합을 효율적으로 검색할 수 있어야 하기 때문에 조립 게임이 매우 어렵다고 언급합니다.

명령 조합 수는 우주의 입자 수 또는 체스(10120개 게임) 및 바둑(10700개 게임)에서 가능한 동작 조합 수와 유사합니다. 각각의 잘못된 동작은 전체 알고리즘을 무효화합니다.

그런 다음 모델은 알고리즘을 출력하고 이를 예상 출력과 비교하여 알고리즘의 정확성과 대기 시간을 기준으로 에이전트에 보상을 제공합니다.

알고리즘을 구축할 때 명령이 입력될 때마다 AlphaDev는 출력 알고리즘을 예상 결과와 비교하여 정확성을 확인합니다(정렬 알고리즘의 경우 순서가 지정되지 않은 숫자를 입력한 후 올바르게 정렬된 숫자를 출력할 수 있음을 의미).

이 모델은 AlphaDev의 올바른 숫자 순서와 효율성에 대해 보상합니다. 결국 AlphaDev는 더 정확하고 빠른 프로그램을 발견하여 경쟁에서 승리했습니다.

4. 알고리즘 혁신: 이동 및 복사 명령 시퀀스 교체

AlphaDev는 더 빠른 알고리즘을 생성할 뿐만 아니라 두 개의 명령 시퀀스도 혁신합니다.

구체적으로 생성되는 정렬 알고리즘에는 두 개의 새로운 명령어 시퀀스인 스왑 이동과 복사 이동이 포함되며, 사용될 때마다 하나의 명령어가 저장됩니다. 연구원들은 이를 "AlphaDev의 스왑 이동 및 복사 이동"이라고 부릅니다.

이 참신한 접근 방식은 구경꾼에게 충격을 주고 전설적인 체스 선수를 패배시킨 "반직관적인" 체스 플레이인 AlphaGo의 "37단계"를 연상시킵니다.

이동 및 복사 명령 시퀀스를 교체함으로써 AlphaDev는 한 단계를 건너뛰고 실수처럼 보이지만 실제로는 지름길인 방식으로 목표를 완료합니다. 이는 AlphaDev가 초기 솔루션을 발견하고 컴퓨터 과학 알고리즘을 개선하려고 노력할 수 있는 능력을 가지고 있음을 의미합니다.

5. 테스트: 해시 알고리즘 홍보 및 개선

더 빠른 정렬 알고리즘을 발견한 후 연구자들은 이를 또 다른 컴퓨터 과학 알고리즘인 해시 알고리즘의 홍보 및 개선에 적용하려고 했습니다.

해시 알고리즘은 컴퓨팅의 기본 알고리즘으로 데이터를 검색, 저장 및 압축하는 데 사용됩니다. 사서가 특정 책을 찾기 위해 분류 시스템을 사용하는 것처럼, 해싱 알고리즘은 사용자가 무엇을 찾고 있는지, 어디서 찾을 수 있는지 알 수 있도록 도와줍니다.

이러한 알고리즘은 특정 키(예: 사용자 이름 "Jane Doe")에 대한 데이터를 가져와 해시 정렬하여 원시 데이터를 고유한 문자열(예: 1234ghty)로 변환할 수 있습니다.

컴퓨터는 모든 데이터를 검색하는 대신 이 해시를 사용하여 키와 관련된 데이터를 빠르게 검색합니다.

연구원들은 더 빠른 알고리즘을 발견하기 위해 데이터 구조에서 가장 일반적으로 사용되는 해싱 알고리즘 중 하나에 AlphaDev를 적용했습니다. 9~16바이트 범위의 해시 함수에 적용했을 때 AlphaDev는 30% 더 빠른 알고리즘을 생성했습니다.

올해 초 AlphaDev에서 생성된 새로운 해싱 알고리즘이 오픈 소스 Abseil 라이브러리에 출시되어 전 세계 수백만 명의 개발자가 사용할 수 있게 되었으며 현재 매일 수조 번 사용되는 것으로 추정됩니다.

6. 모멘텀: AGI 개발의 첫 단계

AlphaDev는 "정렬 및 해싱 알고리즘"을 최적화하여 다양하고 실용적인 새로운 알고리즘을 생성하는 능력을 보여주었습니다.

이것은 또한 일반 인공 지능(AGI) 도구를 개발하기 위한 AlphaDev의 첫 번째 단계이기도 합니다. 유사한 AI 도구는 전체 컴퓨팅 생태계를 최적화하고 사회에 도움이 되는 다른 문제를 해결하는 데도 도움이 될 수 있습니다.

낮은 수준의 조립 명령 공간에서 알고리즘을 최적화하는 것은 매우 강력하지만 한계도 있습니다. 현재 팀은 고급 언어(예: C++)에서 알고리즘을 최적화하는 AlphaDev의 능력을 연구하고 있으며, 이는 개발자에게 더욱 도움이 될 것입니다.

요컨대, 이러한 새로운 발견이 개발자에게 영감을 주어 새로운 기술과 방법을 개발하고 기본 알고리즘을 더욱 최적화하며 더욱 강력하고 지속 가능한 컴퓨팅 생태계를 만들 수 있기를 바랍니다.

7. 오픈 소스: AI 최적화 코드의 획기적인 발전

이전에는 정렬 알고리즘이 매일 수조 번 사용되었습니다. 컴퓨팅 요구가 증가함에 따라 사람들은 알고리즘에 대한 성능 요구 사항이 점점 더 높아지고 있습니다. 인간 엔지니어가 다양한 정렬 알고리즘을 발견했지만 수십 년 동안 최적화한 후에는 돌파구를 마련하기 어렵고 증가하는 수요를 충족할 수 없습니다.

이제 AlphaDev는 데이터 정렬을 위한 더 빠른 정렬 알고리즘을 발견했습니다.

새로운 순위 알고리즘은 다목적이며 온라인 검색 결과와 소셜 게시물의 순위를 매기는 데 사용할 수 있을 뿐만 아니라 컴퓨터와 휴대폰에서 데이터를 처리하는 데에도 사용할 수 있습니다.

새로운 정렬 알고리즘이 기본 C++ 라이브러리에서 오픈 소스로 공개되었다는 사실은 축하할 가치가 있습니다. 현재 전 세계 수백만 명의 개발자와 회사에서 클라우드 컴퓨팅, 온라인 쇼핑, 공급망 관리 등을 위해 사용하고 있습니다.

간단히 말하면, 인공 지능 도구를 사용하여 알고리즘을 최적화하면 기존 프로그래밍 방식이 완전히 바뀔 것입니다. 정렬 라이브러리가 변경된 것은 10년여 만에 처음이며, 강화학습 모델로 설계한 알고리즘이 정렬 라이브러리에 추가된 것은 처음이다. 코드를 최적화합니다.

8. 사용자: 어쩌면 그냥 속임수일 수도 있습니다.

사용자는 연구 결과에 대해 엇갈린 의견을 가지고 있습니다. 트위터에서 대부분의 목소리는 다음과 같습니다.

기본적인 정렬 작업을 배우는 것은 프로그래머가 초기에 익히는 기술 중 하나입니다. 이 스킬을 사용하면 속도가 70% 향상됩니다. AI를 활용하여 우리 모두가 의존하는 알고리즘과 라이브러리에 상당한 가속화를 제공하는 것을 보는 것은 매우 흥미롭습니다."

"곧 일반 사람들도 고급 프로그래머가 될 수 있을 것입니다."

"어셈블리 수준 최적화에서 시작하는 흥미로운 접근 방식"

그러나 일부 프로그래머는 이것이 단지 속임수라고 생각하며 DeepMind는 알고리즘의 기능을 과장합니다.

우선 효율성의 관점에서 볼 때 실제로 시간을 변경하는 것이 아니라 알고리즘의 지연만 계산합니다.

또한 순서가 실제로 변경되지는 않습니다. 이러한 종류의 작업은 다양한 다른 코드 기반에서 일반적입니다.

참조:

1. 06004- 9

2.https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithms

3.https://www.deepmind.com/blog/optimising-computer-systems- with- more-generalised-ai-tools

4. https://twitter.com/demishassabis

위 내용은 DeepMind가 세상을 뒤흔드는 정렬 알고리즘을 출시하고 C++ 라이브러리가 업데이트 중입니다!의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!