Google DeepMind가 10년 간의 알고리즘 봉인을 깨고 AlphaDev가 놀라운 데뷔를 하여 인간 알고리즘 환경을 뒤집습니다!

오늘 "Alpha" 패밀리에 AlphaDev라는 새 멤버가 추가되었습니다.

AI가 만들어낸 새로운 알고리즘으로 전체 컴퓨팅 생태계의 기반이 무너질 수도 있습니다!

Google Brain과 DeepMind가 결합하여 이렇게 놀라운 작업을 수행하는 데는 오랜 시간이 걸리지 않았습니다.

AlphaDev는 정렬 알고리즘의 속도를 70%까지 높일 수 있을 뿐만 아니라 일부 알고리즘에서는 인간보다 3배나 더 빠를 수도 있습니다.

C++ 정렬 라이브러리가 10년 만에 처음으로 변경되었습니다. AI는 세계의 코드를 최적화하고 새로운 이정표에 도달합니다.

현재 최신 연구가 Nature에 게재되었습니다.

논문 주소: https://www.nature.com/articles/s41586-023-06004-9

AlphaDev는 강화 학습을 통해 수십 년을 직접 능가하는 더 효과적인 알고리즘을 발견했습니다. 과학자와 엔지니어의 세심한 연마.

이제 새로운 알고리즘은 두 개의 표준 C++ 코딩 라이브러리의 일부이며 전 세계 프로그래머가 매일 수조 번 사용하고 있습니다.

일부 네티즌들은 드디어 왔다고 말했습니다. 우리는 이제 미지의 영역에 들어서고 있습니다. 인공지능이 인공지능을 구축하고 있습니다!

강화 학습은 10년 간의 알고리즘 병목 현상을 해결합니다

AlphaZero 및 AlphaFold와 같은 이전 제품과 마찬가지로 AlphaDev도 현장에서 직접 변경을 시작했습니다.

DeepMind 컴퓨터 과학자이자 논문의 첫 번째 저자인 Daniel Mankowitz는 "처음에는 믿지 않았습니다."라고 말했습니다.

"솔직히 말하면 더 나은 결과를 얻을 것이라고 기대하지 않았습니다. 매우 짧은 프로그램이며 이러한 유형의 프로그램은 이미 수십 년 동안 연구되어 왔습니다. "

현재 GPT-4 및 Bard와 같은 대형 모델의 매개변수가 기하급수적으로 증가하고 있으며 컴퓨팅 성능 및 기타 리소스에 대한 수요가 계속되고 있습니다. 성장하기 위해. 지난 50년 동안 인간은 계속해서 칩 개선에 의존해 왔습니다.

그러나 마이크로칩이 물리적 한계에 접근함에 따라 컴퓨팅을 더욱 강력하고 지속 가능하게 만들기 위해 코드를 개선하는 것이 중요합니다. 이는 매일 수조 개의 코드를 실행하는 알고리즘의 경우 특히 그렇습니다.

오늘 Google DeepMind는 Nature에 게재된 논문에서 Alpha 제품군의 "신생" AlphaDev를 처음으로 소개했습니다.

AlphaDev는 수십억 명의 사람들이 자신도 모르게 매일 사용하는 더 빠른 정렬 알고리즘을 발견했습니다.

온라인 검색 결과부터 소셜 게시물, 컴퓨터와 휴대폰이 데이터를 처리하는 방식에 이르기까지 모든 것의 기초입니다. 이러한 알고리즘은 매일 수조 번 실행됩니다.

AI를 사용하여 더 나은 알고리즘을 생성하면 컴퓨터 프로그래밍 방식이 바뀌고 디지털 사회의 모든 측면에 영향을 미칠 것입니다.

Nature 논문의 데이터에 따르면 AlphaZero가 만든 알고리즘은 인간보다 3배 빠르게 데이터를 정렬할 수 있습니다.

오늘 Google DeepMind는 또한 메인 C++ 라이브러리의 최신 정렬 알고리즘을 오픈소스화하여 모든 사람이 사용할 수 있도록 했습니다.

오픈소스 주소: https://reviews.llvm.org/D118029

정렬이란 무엇인가요?

정렬은 여러 항목을 특정 순서로 정리하는 방법입니다.

세 글자를 알파벳순으로 배열하는 것처럼, 다섯 개의 숫자를 큰 숫자에서 가장 작은 숫자로 배열하거나, 수백만 개의 레코드가 포함된 데이터베이스를 정렬하는 것과 같습니다.

분류 방법은 인류 역사 전반에 걸쳐 진화해 왔습니다. 가장 초기의 사례는 학자들이 알렉산드리아 도서관 서가에 수천 권의 책을 알파벳 순서로 수동으로 정리했던 2~3세기로 거슬러 올라갑니다.

산업 혁명 이후 우리는 분류에 도움이 될 수 있는 기계를 발명했습니다. 천공 카드에 정보를 저장한 도표 기계는 1890년 미국 인구 조사 결과를 수집하는 데 사용되었습니다.

1950년대 상업용 컴퓨터가 등장하면서 최초의 컴퓨터 과학 정렬 알고리즘이 등장했습니다.

오늘날 전 세계의 코드베이스에서는 온라인에서 대량의 데이터를 구성하기 위해 다양한 정렬 기술과 알고리즘이 사용됩니다.

정렬 알고리즘, 즉 정렬되지 않은 일련의 숫자를 입력하고 정렬된 숫자를 출력하는 알고리즘입니다.

이러한 알고리즘은 컴퓨터 과학의 초석이 되었습니다.

오늘날 우리의 알고리즘은 컴퓨터 과학자와 프로그래머에게 수십 년의 연구 개발 투자를 요구합니다.

이는 기존 알고리즘이 매우 효율적이고 이를 개선하기 위해 앞으로 나아가는 모든 단계가 큰 도전이기 때문입니다.

이 정도의 난이도는 전기 에너지를 절약하는 새로운 방법을 찾는 것, 혹은 보다 효율적인 수학적 방법을 찾는 것과 같습니다.

새로운 알고리즘 찾기

AlphaDev의 혁신적인 의미는 기존 알고리즘을 개선하는 것이 아니라 더 빠른 알고리즘을 처음부터 완전히 발견한다는 것입니다.

게다가 실제로는 대부분의 인간이 생각하지 못하는 곳, 즉 컴퓨터 조립 설명서에서 시작됩니다.

어셈블리 명령어는 바이너리 코드를 생성하는 데 사용됩니다. 개발자는 코드를 작성할 때 C++와 같은 고급 언어를 사용하지만 컴퓨터가 이해하려면 이러한 고급 언어를 "저수준" 어셈블리 명령으로 변환해야 합니다.

보통 우리는 C++와 같은 고급 프로그래밍 언어를 사용하여 코드를 작성한 다음 컴파일러를 사용하여 이를 어셈블리 명령어인 저수준 CPU 명령어로 변환합니다. 그런 다음 어셈블러는 어셈블리 명령을 실행 가능한 기계 코드로 변환합니다

Google DeepMind의 연구원들은 이 하위 수준에는 개선의 여지가 많으며 이러한 개선은 상위 수준 프로그래밍 언어에서 가능하다고 믿습니다. 발견하기 어렵습니다. .

이 낮은 수준에서 컴퓨터는 저장 및 작업 측면에서 더 유연하므로 몇 가지 잠재적인 개선이 속도와 에너지에 큰 영향을 미칠 수 있습니다.

그림 A: 최대 두 개의 요소를 정렬하는 C++ 알고리즘

그림 B: 해당 코드 어셈블리

AlphaDev: AlphaZero의 어셈블리 버전

다들 아시다시피 DeepMind 강화 학습 모델은 바둑, 체스, 장기와 같은 게임에서 세계 챔피언을 반복적으로 이겼습니다.

그리고 이번 주인공인 AlphaDev는 AlphaZero를 기반으로 합니다.

AlphaDev는 보드 게임에서 각 동작을 선택하기 위해 컴퓨터 추론과 직관을 결합한 이전 버전인 AlphaZero와 유사하게 작동합니다.

AlphaDev는 다음 이동 방법을 선택하는 것이 아니라 추가할 지침을 선택합니다.

AlphaDev가 새로운 알고리즘을 발견하도록 훈련시키기 위해 DeepMind는 정렬 문제를 "조립 게임"으로 변환했습니다.

각 라운드에서 AlphaDev는 자신이 생성한 알고리즘과 중앙 처리 장치(CPU)에 포함된 정보를 관찰하고 알고리즘에 명령을 추가하여 움직여야 합니다.

그리고 이 조립 게임은 정렬이 가능하고 현재 최고의 알고리즘보다 빠른 알고리즘을 찾기 위해 AlphaDev가 가능한 많은 명령어 조합을 효율적으로 검색해야 하기 때문에 매우 어렵습니다.

"가능한 명령 조합"은 우주의 입자 수 또는 체스(10^120 게임) 및 바둑(10^700 게임)의 가능한 동작 조합과 직접 비교할 수도 있습니다.

또한 잘못된 움직임으로 인해 전체 알고리즘이 무효화될 수 있습니다.

결국 DeepMind는 숫자를 올바르게 정렬하는 능력과 정렬을 얼마나 빠르고 효율적으로 완료하는지에 따라 AlphaDev에 보상을 제공하며, AlphaDev는 정확하고 빠른 프로그램을 찾아 게임에서 승리해야 합니다.

그림 A: 조립 게임. Player AlphaDev는 시스템 상태 st를 입력으로 사용하고 이미 생성된 알고리즘에 추가할 어셈블리 명령을 선택하여 이동합니다.

그림 B: 보상 계산. 각 이동 후에 결과 알고리즘이 테스트되고 에이전트는 정확성과 응답 시간에 따라 보상을 받습니다.

특히, AlphaZero는 심층적인 사고(심의)를 수행할 때 각 결정 지점에서 다음으로 가능한 조치와 다음 단계를 고려합니다. 수형도처럼 단계별로 역방향으로 작업하여 어떤 작업이 성공할 가능성이 가장 높은지 알아보세요.

하지만 문제는 상황의 가능한 모든 지점을 고려하면 소요 시간이 우주의 나이보다 길어질 수 있다는 것입니다. 그래서 연구자들은 직관과 같은 것을 사용하여 범위를 좁힙니다.

각 단계에서 프로그램은 가장 적절한 동작을 찾기 위해 현재 상태를 신경망(복잡하고 조정 가능한 수학 함수)에 입력합니다. 동시에 훈련 과정에서 신경망은 결과에 따라 계속 업데이트됩니다. 때로는 가장 높은 등급을 받은 행동이 적극적 탐색을 위해 의도적으로 선택되지 않는 경우도 있습니다.

AlphaDev가 취할 수 있는 작업에는 서로 다른 값 비교, 값을 다른 위치로 이동, 프로그램의 다른 부분으로 이동 등 네 가지 작업이 있습니다.

각 단계를 마친 후 목록 집합을 정렬하고 올바르게 정렬된 목록의 값 수에 따라 보상을 받으세요.

전체 목록이 정렬되거나 프로그램 길이 제한에 도달하고 새 프로그램이 처음부터 시작될 때까지 계속됩니다.

C++ 실행 속도가 70% 증가했습니다

AlphaDev는 LLVM libc++ 정렬 라이브러리를 크게 개선한 새로운 정렬 알고리즘을 발견했습니다.

더 짧은 시퀀스의 경우 속도 향상은 70%인 반면, 요소가 250,000개가 넘는 시퀀스의 경우 속도 향상은 약 1.7%에 불과합니다.

연구원들은 더 짧은 3~5개 요소를 사용하여 시퀀스 정렬 알고리즘을 개선하는 데 중점을 둡니다.

이러한 알고리즘은 더 큰 정렬 기능의 일부로 여러 번 호출되는 경우가 많기 때문에 가장 널리 사용됩니다.

이러한 알고리즘을 개선하면 항목 수에 관계없이 전체 정렬 속도를 향상시킬 수 있습니다.

새로운 정렬 알고리즘을 모든 사람이 사용할 수 있도록 하기 위해 연구원들은 이를 역설계하여 "프로그래머"가 가장 일반적으로 사용하는 코딩 언어인 C++로 번역했습니다.

현재 이러한 알고리즘은 이제 LLVM libc++ 표준 정렬 라이브러리에서 사용할 수 있습니다.

해시 기능 효율성이 30% 증가했습니다

더 빠른 정렬 알고리즘을 발견한 후 DeepMind는 AlphaDev가 다른 컴퓨터 과학 알고리즘인 해싱을 일반화하고 개선할 수 있는지 테스트했습니다.

해싱은 컴퓨팅의 기본 알고리즘이며 데이터를 검색, 저장 및 압축하는 데 사용됩니다. 사서가 특정 도서를 찾기 위해 분류 시스템을 사용하는 것처럼, 해싱 알고리즘은 사용자가 찾고 있는 내용과 정확한 위치를 알 수 있도록 도와줍니다.

이러한 알고리즘은 특정 키(예: 사용자 이름 "Jane Doe")를 해시합니다. 즉, 원본 데이터를 고유한 문자열(예: 1234ghfty)로 변환합니다. 그런 다음 컴퓨터는 모든 데이터를 검색하는 대신 이 해시 값을 사용하여 키와 관련된 데이터를 빠르게 검색합니다.

결과에 따르면 AlphaDev가 발견한 알고리즘은 해시 함수의 9~16바이트 범위에 적용했을 때 기존 알고리즘보다 30% 더 빠릅니다.

이제 DeepMind는 오픈 소스 Abseil 라이브러리에 새로운 해싱 알고리즘도 출시했습니다. 이 알고리즘은 매일 수조 번 사용될 것으로 예상됩니다.

두 가지 새로운 전략: "스왑 이동" 및 "복사 이동"

AlphaDev는 더 빠른 알고리즘뿐만 아니라 새로운 방법도 발견했습니다.

정렬 알고리즘에는 새로운 명령 시퀀스가 ​​포함되어 있으며, 그 중 하나는 적용될 때마다 저장됩니다. 이러한 알고리즘은 매일 수조 번 사용되기 때문에 이는 큰 영향을 미칠 수 있습니다.

연구원들은 이를 "AlphaDev 스왑 이동" 및 "AlphaDev 복사 이동"이라고 부릅니다.

최신 방식은 알파고의 충격적인 '37단계'를 연상시킨다.

2016년 인간-기계 전쟁에서 알파고는 인간의 직관을 거스르는 체스 게임, 간단한 어깨 돌격으로 전설적인 바둑기사 이세돌을 물리쳤습니다.

두 전략을 모두 사용하면 AlphaDev는 잘못된 것처럼 보이지만 실제로는 지름길인 방식으로 프로젝트를 연결하는 단계를 건너뜁니다.

이는 독창적인 솔루션을 발견하고 컴퓨터 과학 알고리즘을 개선하는 방법에 대한 우리의 사고 방식에 도전하는 AlphaDev의 능력을 보여줍니다.

아래 그림에 표시된 것처럼 원래 sort3 구현에는 min(A, B, C)가 있습니다. AlphaDev Swap Move를 사용하면 AlphaDev는 min(A, B)만 필요하다는 것을 발견했습니다.

또 다른 예를 들어, 원래 구현에서는 max(B, min(A,C, D))의 더 큰 정렬 알고리즘을 사용하여 8개 요소를 정렬합니다.

AlphaDev는 "이동 교체 및 복사"를 사용하려면 max(B, min(A, C))만 필요하다는 것을 발견했습니다.

세계의 코드 최적화, 한 번에 하나의 알고리즘

전 세계 개발자가 사용하는 향상된 정렬 및 해싱 알고리즘을 최적화하고 출시함으로써 AlphaDev는 세계를 일반화하고 발견할 수 있는 능력이 있음을 입증했습니다. -클래스의 새로운 알고리즘.

Google DeepMind는 AlphaDev가 전체 컴퓨팅 생태계를 최적화하고 사회에 도움이 되는 기타 문제를 해결하는 데 도움이 되는 AGI 도구 개발을 향한 한 단계라고 믿습니다.

그러나 연구원들은 AlphaDev가 현재 낮은 수준의 어셈블리 명령을 최적화할 수 있는 능력이 뛰어나지만 알고리즘이 개발됨에 따라 한계가 있음을 인정합니다.

개발자가 더욱 유용하게 사용할 수 있도록 AlphaDev의 고급 언어(예: C++)에서 알고리즘을 최적화하는 기능이 연구되고 있습니다.

"AlphaDev swap move" 및 "AlphaDev copy move"와 같은 AlphaDev의 새로운 발견은 알고리즘을 향상시킬 수 있을 뿐만 아니라 새로운 솔루션을 찾을 수 있음을 보여줍니다.

연구원들은 이러한 발견이 연구원과 개발자에게 영감을 주어 기본 알고리즘을 더욱 최적화하여 더욱 강력하고 지속 가능한 컴퓨팅 생태계를 만드는 데 도움이 되기를 바랍니다.

네티즌들의 인기 댓글

NVIDIA 과학자 Jim Fan이 AlphaDev에 대해 심층적으로 요약했습니다.

정렬 알고리즘은 모든 주요 소프트웨어의 기초입니다. DeepMind의 AlphaDev는 작은 시퀀스(3-5개 항목)의 정렬 속도를 70% 향상시킵니다. 핵심 사항:

- 주요 RL 알고리즘은 원래 바둑, 체스, 장기를 플레이했던 AlphaZero를 기반으로 합니다. 검색 프로그램에도 동일한 아이디어가 적용됩니다!

- 연구원들은 C 코드가 아니라 어셈블리 코드를 최적화했습니다. 이는 낮은 수준으로 이동하여 저장된 모든 명령을 짜내려는 의도적인 선택입니다.

- 그런 다음 어셈블리 코드를 C++로 리버스 엔지니어링하고 LLVM에서 오픈 소스화했습니다.

- 대표 네트워크에서 Transformer를 사용하더라도 기본 모델은 아닙니다. 전체 프로세스는 정렬에만 작동하며 해싱과 같은 다른 작업을 위해서는 재교육이 필요합니다.

ML을 사용한 알고리즘 발견의 또 다른 중요한 이정표입니다!

AlphaDev는 핵심 컴퓨터 과학 알고리즘을 혁신하는 DeepMind의 판도를 바꾸는 인공 지능입니다. 짧은 시퀀스를 70% 더 빠르게 만들기 위해 시퀀싱 방법을 재구성하고 있습니다. 해싱 알고리즘의 검색 속도도 30% 향상되었습니다. 강화 학습은 알고리즘 환경을 재편하고 있습니다!

일부 네티즌들은 우리가 언어 모델에 대해 기대하고 있지만 다른 딥 러닝 알고리즘인 AlphaZero, AlphaFold, 그리고 이제 AlphaDev의 성공 사례를 잊어서는 안 된다고 말했습니다.

위 내용은 Google DeepMind가 10년 간의 알고리즘 봉인을 깨고 AlphaDev가 놀라운 데뷔를 하여 인간 알고리즘 환경을 뒤집습니다!의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!